[Freeciv-Dev] Re: (PR#11779) New genlist code

["Per I. Mathisen" <per@xxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=11779 >

On Tue, 4 Jan 2005, Vasco Alexandre da Silva Costa wrote:
> One, it should be possible to create tracked and non-tracked
> genlists. The tracker list would be a non-tracked genlist. Instead of
> adding that special casing.

I've added genlist_temporary() and listname_list_temporary() that can
create non-tracked genlists. I made a link from the genlist to the
tracker, which makes the list free code _a lot_ faster.

> (Non-tracked genlists wouldn't use GC but simply free nodes?).

Simplest is to delay deletions until _free() is called, I think. It won't
make much difference either way.

> Two, I think you should try adding an extra integer field,
> ndeleted, which has the number of deleted but non-freed nodes in a list,
> to make pruning of lists faster. This should be benchmarked, to see
> how much faster it made things.

I tested this. The difference was quite small (0m36.1 vs 0m35.6 for my
tests), and it adds up some additional memory for each list, so I am not
sure if it is worth it, but I have added this.

Thanks for your comments. New genlist.c|h attached.

  - Per

/**********************************************************************
 Freeciv - Copyright (C) 2003 - The Freeciv Team
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation; either version 2.1, or (at
   your option) any later version.
                                                                                
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.
***********************************************************************/

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <assert.h>
#include <stdlib.h>

#include "log.h"
#include "mem.h"
#include "shared.h"
#include "support.h"

#include "genlist.h"

/* Tracker is a list of pointers to lists that we will prune when
 * the time is right. */
static struct genlist *tracker;

static void genlist_prune(struct genlist *plist);

/**************************************************************************
  Initialize genlist module.
**************************************************************************/
void genlists_init()
{
  tracker = genlist_new();
}

/**************************************************************************
  Quit genlist module.  Returns FALSE if memory was not cleaned up
  properly.
**************************************************************************/
void genlists_free()
{
  genlist_free(tracker);
}

/**************************************************************************
  Create a genlist and insert it into the genlist tracker.
**************************************************************************/
struct genlist *genlist_new()
{
  struct genlist *plist = calloc(sizeof(struct genlist), 1);

  plist->nelements = 0;
  plist->ndeleted = 0;
  plist->head = NULL;
  plist->sort_buffer = NULL;
  plist->buffer_size = 0;
  plist->tail = NULL;
  plist->track = NULL;

  if (tracker) {
    struct genlist_link *plink;

    /* Insert list into tracker, unless we _are_ the tracker. */
    genlist_insert(tracker, plist);

    /* Find our position in the tracker */
    for (plink = tracker->head; plink->dataptr != plist; plink = plink->next);

    /* Point plist->track at ourselves in the tracker */
    plist->track = plink;
  }

  return plist;
}

/**************************************************************************
  Create a genlist but do NOT insert it into the genlist tracker.
**************************************************************************/
struct genlist *genlist_temporary()
{
  struct genlist *plist = calloc(sizeof(struct genlist), 1);

  plist->nelements = 0;
  plist->ndeleted = 0;
  plist->head = NULL;
  plist->sort_buffer = NULL;
  plist->buffer_size = 0;
  plist->tail = NULL;
  plist->track = NULL;

  return plist;
}

/**************************************************************************
  Get data from given position. -1 gives us last position.
**************************************************************************/
void *genlist_get(const struct genlist *plist, int idx)
{
  struct genlist_link *plink = plist->head;
  int i = 0;

  if (idx == -1) {
    idx = genlist_size(plist);
  }

  if (!plist->head || genlist_size(plist) == 0) {
    /* List is empty */
    return NULL;
  } else if (idx == genlist_size(plist) && !plist->tail->deleted) {
    /* Last item */
    return plist->tail->dataptr;
  } else if (idx > genlist_size(plist) || idx < -1) {
    /* Trying to fetch out of bounds item */
    return NULL;
  }

  /* Ok, we have to search */
  for (;; plink = plink->next) {
    if (plink->deleted) {
      continue;
    }
    if (i == idx) {
      break;
    }
    i++;
  }
  return plink->dataptr;
}

/**************************************************************************
  Free list. Does not touch data inside the list. Calling this function
  while such data is still in the list is an error.
**************************************************************************/
void genlist_free(struct genlist *plist)
{
  /* Remove our entry in the tracker list. */
  if (plist->track) {
    plist->track->deleted = TRUE;
    tracker->nelements--;
  }
  /* assert(plist->nelements == 0); */

  if (plist->sort_buffer) {
    free(plist->sort_buffer);
  }
  free(plist);
}

/**************************************************************************
  Remove first link from the list where the data pointers match.
**************************************************************************/
void genlist_unlink(struct genlist *plist, void *punlink)
{
  struct genlist_link *next = plist->head;

  while (next) {
    if (!next->deleted && next->dataptr == punlink) {
      next->deleted = TRUE;
      plist->nelements--;
      plist->ndeleted++;
      break;
    }
    next = next->next;
  }
}

/**************************************************************************
  Empty the list.
**************************************************************************/
void genlist_unlink_all(struct genlist *plist)
{
  struct genlist_link *next = plist->head;

  while (next) {
    if (!next->deleted) {
      next->deleted = TRUE;
      plist->nelements--;
      plist->ndeleted++;
    }
    next = next->next;
  }
  assert(plist->nelements == 0);
}

/**************************************************************************
  Insert data at beginning of list.
**************************************************************************/
void genlist_insert(struct genlist *plist, void *data)
{
  struct genlist_link *new_link = fc_malloc(sizeof(struct genlist_link));

  new_link->dataptr = data;
  new_link->deleted = FALSE;
  new_link->next = plist->head;
  plist->head = new_link;
  if (plist->tail == NULL) {
    plist->tail = new_link;
  }
  plist->nelements++;
}

/**************************************************************************
  Insert data at end of list.
**************************************************************************/
void genlist_insert_back(struct genlist *plist, void *data)
{
  struct genlist_link *new_link = fc_malloc(sizeof(struct genlist_link));

  new_link->dataptr = data;
  new_link->deleted = FALSE;
  new_link->next = NULL;
  if (plist->tail) {
    plist->tail->next = new_link;
  } else {
    plist->head = new_link;
  }
  plist->tail = new_link;
  plist->nelements++;
}

/**************************************************************************
  Free all unused memory in all genlists.
**************************************************************************/
void genlists_prune()
{
  struct genlist_link *plink = tracker->head;

  for (; plink != NULL; plink = plink->next) {
    if (!plink->deleted
        && plink->dataptr != NULL
        && ((struct genlist *)(plink->dataptr))->ndeleted > 0) {
      genlist_prune((struct genlist *)plink->dataptr);
    }
  }
  genlist_prune(tracker);
}

/**************************************************************************
  Free unused memory. Call some time when we are certain that no calling 
  code uses the list.
**************************************************************************/
static void genlist_prune(struct genlist *plist)
{
  struct genlist_link *plink = plist->head;
  struct genlist_link *plink_prev = NULL;

  while (plink && plist->ndeleted > 0) {
    if (plink->deleted) {
      struct genlist_link *remove = plink;

      if (plist->head == plink) {
        plist->head = plink->next;
      }
      if (plist->tail == plink) {
        plist->tail = plink_prev;
      }
      if (plink_prev) {
        plink_prev->next = plink->next;
      }
      plink = plink->next;
      free(remove);
      plist->ndeleted--;
    } else {
      plink_prev = plink;
      plink = plink->next;
    }
  }
  if (plist->sort_buffer) {
    free(plist->sort_buffer);
    plist->sort_buffer = NULL;
  }
}

/**************************************************************************
  Generic sort function. Hand over a comparison function that can be 
  used by qsort. The arguments to this helper function are pointers to
  void*, which is a pointer to the list dataptr. Note, two levels of
  indirection.

  Since this function might be called repeatedly, we keep the buffer 
  around (per list).
**************************************************************************/
void genlist_sort(struct genlist *plist, int (*compar)(const void *, 
                                                       const void *))
{
  struct genlist_link *plink = plist->head;
  int i;

  if (compar == NULL) {
    if (plist->sort_buffer) {
      free(plist->sort_buffer);
      plist->sort_buffer = NULL;
      plist->buffer_size = 0;
    }
    return;
  }

  if (!plink || !plink->next) {
    return;
  }

  /* Nothing to do! */
  if (genlist_size(plist) <= 1) {
    return;
  }

  /* Increase size of buffer */
  if (!plist->sort_buffer || genlist_size(plist) > plist->buffer_size) {
    plist->buffer_size = genlist_size(plist) + 10;
    plist->sort_buffer = (void **)fc_realloc(plist->sort_buffer, 
                                             plist->buffer_size
                                              * sizeof(void *));
  }

  /* Copy pointers into buffer */
  for (i = 0; plink; plink = plink->next) {
    if (!plink->deleted) {
      plist->sort_buffer[i] = plink->dataptr;
      i++;
    }
  }

  /* Sort the array */
  qsort(plist->sort_buffer, genlist_size(plist), sizeof(void*), compar);

  /* Copy pointers back from buffer */
  plink = plist->head;
  for (i = 0; plink; plink = plink->next) {
    if (!plink->deleted) {
      plink->dataptr = plist->sort_buffer[i];
      i++;
    }
  }
}

/**********************************************************************
 Freeciv - Copyright (C) 2003 - The Freeciv Team
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU Lesser General Public License as
   published by the Free Software Foundation; either version 2.1, or (at
   your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU Lesser General Public License for more details.
***********************************************************************/
#ifndef FC__GENLIST_H
#define FC__GENLIST_H

#undef DEBUG_LISTS
#ifdef DEBUG_LISTS
#define DEBUG_INFO(p) __FILE__, __LINE__
#else
#define DEBUG_INFO(p)
#endif

#include "shared.h"

/* A single list link. The last link's next is NULL. */
struct genlist_link {
  struct genlist_link *next;
  void *dataptr;
  bool deleted;
};

/* A list. nelements contains the number of links in the list, while
 * head and tail point to first and last link, respectively. sortbuf
 * is a temporary storage buffer for qsort, emptied by prune() or by
 * calling the sort function with a NULL parameter. The track variable
 * points to our entry in the tracker, if we are there. */
struct genlist {
  int nelements;
int ndeleted;
  struct genlist_link *head;
  struct genlist_link *tail;
  struct genlist_link *track;
  void **sort_buffer;
  int buffer_size;
};

/* Operations on all lists */
void genlists_init(void);
void genlists_free(void);
void genlists_prune(void);

/* Operations on a single list */
struct genlist *genlist_new(void);
struct genlist *genlist_temporary(void);
#define genlist_size(plist) ((plist)->nelements)
void *genlist_get(const struct genlist *plist, int idx);
void genlist_insert(struct genlist *plist, void *data);
void genlist_insert_back(struct genlist *plist, void *data);
void genlist_unlink(struct genlist *plist, void *punlink);
void genlist_unlink_all(struct genlist *plist);
void genlist_free(struct genlist *plist);
void genlist_sort(struct genlist *plist,
                  int (*compar)(const void *, const void *));

#define ITERATOR_PTR(iter) ((iter)->dataptr)
#define ITERATOR_NEXT(iter) (iter = (iter)->next)
#define ITERATOR_PREV(iter) (iter = (iter)->prev)

/* The below does not really belong here but has to be here 
 * for specfile to work properly. */

/* This is to iterate for a type defined like:
     struct unit_list { struct genlist list; };
   where the pointers in the list are really pointers to "atype".
   Eg, see speclist.h, which is what this is really for.
*/
#define TYPED_LIST_ITERATE(atype, typed_list, var) {         \
  struct genlist_link *link = (typed_list)->list.head;       \
  atype *var;                                                \
  while (link && ITERATOR_PTR(link)) {                       \
    bool deleted = link->deleted;                            \
    var = (atype *)ITERATOR_PTR(link);                       \
    ITERATOR_NEXT(link);                                     \
    if (!deleted) {

/* Balance for above: */
#define LIST_ITERATE_END  }}}

#endif