Complete.Org: Mailing Lists: Archives: freeciv-dev: May 2005:
[Freeciv-Dev] (PR#11779) Re: (PR#11990) New genlist code
Home

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
Subject: [Freeciv-Dev] (PR#11779) Re: (PR#11990) New genlist code
From: "Per I. Mathisen" <per@xxxxxxxxxxx>
Date: Sat, 14 May 2005 15:03:40 -0700
Reply-to: bugs@xxxxxxxxxxx

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

New genlist patch, all the issues mentioned previously should be fixed.

New issues:

==11555== 10716 bytes in 893 blocks are definitely lost in loss record 16 of 20
==11555==    at 0x1B905A90: malloc (vg_replace_malloc.c:131)
==11555==    by 0x804BDC4: fc_real_malloc (mem.c:75)
==11555==    by 0x804E6FD: genlist_append (genlist.c:189)
==11555==    by 0x80A1ED9: section_file_read_dup (speclist.h:110)
==11555==    by 0x80A20B5: section_file_load (registry.c:603)
==11555==    by 0x807DE9D: openload_ruleset_file (ruleset.c:168)
==11555==    by 0x8082E41: load_rulesets (ruleset.c:2992)
==11555==    by 0x8051475: srv_main (srv_main.c:1677)
==11555==    by 0x804AAFA: main (civserver.c:242)

and

==13460== 1956 bytes in 163 blocks are definitely lost in loss record 23 of 24
==13460==    at 0x1B905A90: malloc (vg_replace_malloc.c:131)
==13460==    by 0x80A9E6B: fc_real_malloc (mem.c:75)
==13460==    by 0x80A79A2: genlist_append (genlist.c:189)
==13460==    by 0x80AAFD9: entry_list_append (speclist.h:110)
==13460==    by 0x80AAE00: section_file_read_dup (registry.c:561)
==13460==    by 0x80AB062: section_file_load (registry.c:603)
==13460==    by 0x8099165: scan_specfile (tilespec.c:1005)
==13460==    by 0x809ACE8: tileset_read_toplevel (tilespec.c:1507)
==13460==    by 0x8098ABD: tilespec_try_read (tilespec.c:777)
==13460==    by 0x80715EB: main (civclient.c:345)

I have no idea what the problem with these are.

  - Per

Index: client/civclient.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/civclient.c,v
retrieving revision 1.225
diff -u -r1.225 civclient.c
--- client/civclient.c  11 May 2005 19:31:37 -0000      1.225
+++ client/civclient.c  14 May 2005 19:52:11 -0000
@@ -287,6 +287,7 @@
   dont_run_as_root(argv[0], "freeciv_client");
 
   log_init(logfile, loglevel, NULL);
+  genlists_init();
 
   /* after log_init: */
 
@@ -378,6 +379,7 @@
   conn_list_free(game.all_connections);
   conn_list_free(game.est_connections);
   conn_list_free(game.game_connections);
+  genlists_free();
   exit(EXIT_SUCCESS);
 }
 
Index: client/helpdata.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/helpdata.c,v
retrieving revision 1.116
diff -u -r1.116 helpdata.c
--- client/helpdata.c   11 May 2005 14:11:20 -0000      1.116
+++ client/helpdata.c   14 May 2005 19:52:11 -0000
@@ -582,7 +582,7 @@
 void help_iter_start(void)
 {
   check_help_nodes_init();
-  help_nodes_iterator = help_nodes->list->head_link;
+  help_nodes_iterator = help_nodes->list->head;
 }
 
 /****************************************************************
Index: client/packhand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/packhand.c,v
retrieving revision 1.516
diff -u -r1.516 packhand.c
--- client/packhand.c   11 May 2005 20:03:07 -0000      1.516
+++ client/packhand.c   14 May 2005 19:52:11 -0000
@@ -778,6 +778,7 @@
     create_event(NULL, E_TURN_BELL, _("Start of turn %d"), game.info.turn);
   }
 
+  genlists_prune();
   agents_new_turn();
 }
 
Index: server/srv_main.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/srv_main.c,v
retrieving revision 1.260
diff -u -r1.260 srv_main.c
--- server/srv_main.c   10 May 2005 01:03:03 -0000      1.260
+++ server/srv_main.c   14 May 2005 19:52:16 -0000
@@ -198,6 +198,9 @@
   /* Initialize callbacks. */
   game.callbacks.unit_deallocate = dealloc_id;
 
+  /* Initialize genlists (only once) */
+  genlists_init();
+
   /* done */
   return;
 }
@@ -815,6 +818,7 @@
   diplhand_free();
   stdinhand_free();
   close_connections_and_socket();
+  genlists_free();
   exit(EXIT_SUCCESS);
 }
 
@@ -1628,6 +1632,7 @@
       conn_list_do_unbuffer(game.game_connections);
     }
     end_turn();
+    genlists_prune();
     freelog(LOG_DEBUG, "Sendinfotometaserver");
     (void) send_server_info_to_metaserver(META_REFRESH);
 
@@ -1909,6 +1914,7 @@
 **************************************************************************/
 void server_game_free()
 {
+  genlists_prune();
   players_iterate(pplayer) {
     player_map_free(pplayer);
   } players_iterate_end;
Index: utility/genlist.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/genlist.c,v
retrieving revision 1.17
diff -u -r1.17 genlist.c
--- utility/genlist.c   22 Jan 2005 19:45:45 -0000      1.17
+++ utility/genlist.c   14 May 2005 19:52:16 -0000
@@ -1,5 +1,5 @@
-/********************************************************************** 
- Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
+/**********************************************************************
+ Freeciv - Copyright (C) 2005 - The Freeciv Project
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2, or (at your option)
@@ -10,256 +10,281 @@
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU 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"
 
-static struct genlist_link *find_genlist_position(const struct genlist 
*pgenlist,
-                                                 int pos);
-
-/************************************************************************
-  Create a new empty genlist.
-************************************************************************/
-struct genlist *genlist_new(void)
-{
-  struct genlist *pgenlist = fc_malloc(sizeof(*pgenlist));
+/* Tracker is a list of pointers to lists that we will prune when
+ * the time is right. */
+static struct genlist *tracker;
 
-  pgenlist->nelements=0;
-  pgenlist->head_link = NULL;
-  pgenlist->tail_link = NULL;
+static void genlist_prune(struct genlist *plist);
 
-  return pgenlist;
+/**************************************************************************
+  Initialize genlist module.
+**************************************************************************/
+void genlists_init(void)
+{
+  tracker = genlist_new();
 }
 
-/************************************************************************
-  Remove a genlist.  The list must be empty first!
-************************************************************************/
-void genlist_free(struct genlist *pgenlist)
+/**************************************************************************
+  Quit genlist module.  Returns FALSE if memory was not cleaned up
+  properly.
+**************************************************************************/
+void genlists_free(void)
 {
-  free(pgenlist);
+  genlist_free(tracker);
 }
 
-/************************************************************************
-  Returns the number of elements stored in the genlist.
-************************************************************************/
-int genlist_size(const struct genlist *pgenlist)
+/**************************************************************************
+  Create a genlist and insert it into the genlist tracker.
+**************************************************************************/
+struct genlist *genlist_new(void)
 {
-  return pgenlist->nelements;
-}
+  struct genlist *plist = calloc(sizeof(struct genlist), 1);
 
+  plist->nelements = 0;
+  plist->ndeleted = 0;
+  plist->head = NULL;
+  plist->tail = NULL;
+  plist->track = NULL;
 
-/************************************************************************
-  Returns the user-data pointer stored in the genlist at the position
-  given by 'idx'.  For idx out of range (including an empty list),
-  returns NULL.
-  Recall 'idx' can be -1 meaning the last element.
-************************************************************************/
-void *genlist_get(const struct genlist *pgenlist, int idx)
-{
-  struct genlist_link *link=find_genlist_position(pgenlist, idx);
+  if (tracker) {
+    struct genlist_link *plink;
 
-  if (link) {
-    return link->dataptr;
-  } else {
-    return NULL;
+    /* Insert list into tracker, unless we _are_ the tracker. */
+    genlist_prepend(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;
+}
 
-/************************************************************************
-  Frees all the internal data used by the genlist (but doesn't touch
-  the user-data).  At the end the state of the genlist will be the
-  same as when genlist_init() is called on a new genlist.
-************************************************************************/
-void genlist_unlink_all(struct genlist *pgenlist)
+/**************************************************************************
+  Get data from given position. -1 gives us last position.
+**************************************************************************/
+void *genlist_get(const struct genlist *plist, int idx)
 {
-  if(pgenlist->nelements > 0) {
-    struct genlist_link *plink=pgenlist->head_link, *plink2;
+  struct genlist_link *plink = plist->head;
+  int i = 0;
 
-    do {
-      plink2=plink->next;
-      free(plink);
-    } while ((plink = plink2) != NULL);
+  if (idx == -1) {
+    idx = genlist_size(plist);
+  }
 
-    pgenlist->head_link = NULL;
-    pgenlist->tail_link = NULL;
+  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;
+  }
 
-    pgenlist->nelements=0;
+  /* 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); */
+
+  free(plist);
+}
 
-/************************************************************************
-  Remove an element of the genlist with the specified user-data pointer
-  given by 'punlink'.  If there is no such element, does nothing.
-  If there are multiple such elements, removes the first one.
-************************************************************************/
-void genlist_unlink(struct genlist *pgenlist, void *punlink)
+/**************************************************************************
+  Remove first link from the list where the data pointers match.
+**************************************************************************/
+void genlist_unlink(struct genlist *plist, void *punlink)
 {
-  if(pgenlist->nelements > 0) {
-    struct genlist_link *plink=pgenlist->head_link;
-    
-    while (plink != NULL && plink->dataptr != punlink) {
-      plink = plink->next;
-    }
-    
-    if (plink) {
-      if(pgenlist->head_link==plink)
-        pgenlist->head_link=plink->next;
-      else
-        plink->prev->next=plink->next;
-
-      if(pgenlist->tail_link==plink)
-        pgenlist->tail_link=plink->prev;
-      else
-        plink->next->prev=plink->prev;
-      free(plink);
-      pgenlist->nelements--;
+  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;
   }
 }
 
-
-/************************************************************************
-  Insert a new element in the list, at position 'pos', with the specified
-  user-data pointer 'data'.  Existing elements at >= pos are moved one
-  space to the "right".  Recall 'pos' can be -1 meaning add at the
-  end of the list.  For an empty list pos has no effect.
-  A bad 'pos' value for a non-empty list is treated as -1 (is this
-  a good idea?)
-************************************************************************/
-static void genlist_insert(struct genlist *pgenlist, void *data, int pos)
-{
-  if(pgenlist->nelements == 0) { /*list is empty, ignore pos */
-    
-    struct genlist_link *plink = fc_malloc(sizeof(*plink));
-
-    plink->dataptr=data;
-    plink->next = NULL;
-    plink->prev = NULL;
-
-    pgenlist->head_link=plink;
-    pgenlist->tail_link=plink;
-
-  }
-  else {
-    struct genlist_link *plink = fc_malloc(sizeof(*plink));
-    plink->dataptr=data;
-
-    if(pos==0) {
-      plink->next=pgenlist->head_link;
-      plink->prev = NULL;
-      pgenlist->head_link->prev=plink;
-      pgenlist->head_link=plink;
-    }
-    else if(pos<=-1 || pos>=pgenlist->nelements) {
-      plink->next = NULL;
-      plink->prev=pgenlist->tail_link;
-      pgenlist->tail_link->next=plink;
-      pgenlist->tail_link=plink;
-    }
-    else {
-      struct genlist_link *left, *right;     /* left and right of new element 
*/
-      right = find_genlist_position(pgenlist, pos);
-      left = right->prev;
-      plink->next = right;
-      plink->prev = left;
-      right->prev = plink;
-      left->next = plink;
+/**************************************************************************
+  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;
   }
-
-  pgenlist->nelements++;
+  assert(plist->nelements == 0);
 }
 
-
-/************************************************************************
-  Insert an item at the start of the list.
-************************************************************************/
-void genlist_prepend(struct genlist *pgenlist, void *data)
-{
-  genlist_insert(pgenlist, data, 0); /* beginning */
+/**************************************************************************
+  Insert data at beginning of list.
+**************************************************************************/
+void genlist_prepend(struct genlist *plist, void *data)
+{
+  struct genlist_link *new_link = fc_malloc(sizeof(*new_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 an item at the end of the list.
-************************************************************************/
-void genlist_append(struct genlist *pgenlist, void *data)
+/**************************************************************************
+  Insert data at end of list.
+**************************************************************************/
+void genlist_append(struct genlist *plist, void *data)
 {
-  genlist_insert(pgenlist, data, -1); /* end */
+  struct genlist_link *new_link = fc_malloc(sizeof(*new_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++;
 }
 
-/************************************************************************
-  Returns a pointer to the genlist link structure at the specified
-  position.  Recall 'pos' -1 refers to the last position.
-  For pos out of range returns NULL.
-  Traverses list either forwards or backwards for best efficiency.
-************************************************************************/
-static struct genlist_link *find_genlist_position(const struct genlist 
*pgenlist,
-                                                 int pos)
+/**************************************************************************
+  Free all unused memory in all genlists.
+**************************************************************************/
+void genlists_prune(void)
 {
-  struct genlist_link *plink;
+  struct genlist_link *plink = tracker->head;
 
-  if (pos == 0) {
-    return pgenlist->head_link;
-  } else if (pos == -1) {
-    return pgenlist->tail_link;
-  } else if (pos < -1 || pos >= pgenlist->nelements) {
-    return NULL;
-  }
+  for (; plink != NULL; plink = plink->next) {
+    struct genlist *tmp = (struct genlist *)plink->dataptr;
 
-  if(pos<pgenlist->nelements/2)   /* fastest to do forward search */
-    for(plink=pgenlist->head_link; pos != 0; pos--)
-      plink=plink->next;
- 
-  else                           /* fastest to do backward search */
-    for(plink=pgenlist->tail_link,pos=pgenlist->nelements-pos-1; pos != 0; 
pos--)
-      plink=plink->prev;
- 
-  return plink;
+    if (!plink->deleted
+        && plink->dataptr != NULL
+        && tmp->ndeleted > 0) {
+      genlist_prune(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;
+    }
+  }
+}
 
-/************************************************************************
- Sort the elements of a genlist.
- 
- The comparison function should be a function usable by qsort; note
- that the const void * arguments to compar should really be "pointers to
- void*", where the void* being pointed to are the genlist dataptrs.
- That is, there are two levels of indirection.
- To do the sort we first construct an array of pointers corresponding
- the the genlist dataptrs, then sort those and put them back into
- the genlist.
-************************************************************************/
-void genlist_sort(struct genlist *pgenlist,
-                 int (*compar)(const void *, const void *))
-{
-  const int n = genlist_size(pgenlist);
-  void *sortbuf[n];
-  struct genlist_link *myiter;
+/**************************************************************************
+  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.
+**************************************************************************/
+void genlist_sort(struct genlist *plist, int (*compar)(const void *, 
+                                                       const void *))
+{
+  struct genlist_link *plink = plist->head;
   int i;
+  void *buffer[genlist_size(plist)];
+
+  if (compar == NULL || !plink || !plink->next || genlist_size(plist) <= 1) {
+    return; /* Nothing to do */
+  }
 
-  if (n <= 1) {
-    return;
+  /* Copy pointers into buffer */
+  for (i = 0; plink; plink = plink->next) {
+    if (!plink->deleted) {
+      buffer[i] = plink->dataptr;
+      i++;
+    }
   }
 
-  myiter = find_genlist_position(pgenlist, 0);  
-  for(i=0; i<n; i++, ITERATOR_NEXT(myiter)) {
-    sortbuf[i] = ITERATOR_PTR(myiter);
-  }
-  
-  qsort(sortbuf, n, sizeof(*sortbuf), compar);
-  
-  myiter = find_genlist_position(pgenlist, 0);  
-  for(i=0; i<n; i++, ITERATOR_NEXT(myiter)) {
-    myiter->dataptr = sortbuf[i];
+  /* Sort the array */
+  qsort(&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 = buffer[i];
+      i++;
+    }
   }
 }
Index: utility/genlist.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/genlist.h,v
retrieving revision 1.14
diff -u -r1.14 genlist.h
--- utility/genlist.h   7 Apr 2005 00:49:45 -0000       1.14
+++ utility/genlist.h   14 May 2005 19:52:16 -0000
@@ -1,5 +1,5 @@
-/********************************************************************** 
- Freeciv - Copyright (C) 1996 - A Kjeldberg, L Gregersen, P Unold
+/**********************************************************************
+ Freeciv - Copyright (C) 2005 - The Freeciv Project
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2, or (at your option)
@@ -13,112 +13,62 @@
 #ifndef FC__GENLIST_H
 #define FC__GENLIST_H
 
-/********************************************************************** 
-  MODULE: genlist
+#include "shared.h"
 
-  A "genlist" is a generic doubly-linked list.  That is:
-    generic:        stores (void*) pointers to arbitrary user data;
-    doubly-linked:  can be efficiently traversed both "forwards"
-                    and "backwards".
-                   
-  The list data structures are allocated dynamically, and list
-  elements can be added or removed at arbitrary positions.
-  
-  Positions in the list are specified starting from 0, up to n-1
-  for a list with n elements.  The position -1 can be used to
-  refer to the last element (that is, the same as n-1, or n when
-  adding a new element), but other negative numbers are not
-  meaningful.
-
-  There are two memory management issues:
-  
-  - The user-data pointed to by the genlist elements; these are
-    entirely the user's responsibility, and the genlist code just
-    treats these as opaque data, not doing any allocation or freeing.
-    
-  - The data structures used internally by the genlist to store
-    data for the links etc.  These are allocated by genlist_insert(),
-    and freed by genlist_unlink() and genlist_unlink_all().  That is,
-    it is the responsibility of the user to call the unlink functions
-    as necessary to avoid memory leaks.
-
-  A trap to beware of with iterators is modifying the list while the 
-  iterator is active, in particular removing the next element pointed 
-  to by the iterator (see further comments below).
-
-  See also the speclist module.
-***********************************************************************/
-
-/* A single element of a genlist, storing the pointer to user
-   data, and pointers to the next and previous elements:
-*/
+/* A single list link. The last link's next is NULL. */
 struct genlist_link {
-  struct genlist_link *next, *prev; 
+  struct genlist_link *next;
   void *dataptr;
+  bool deleted;
 };
 
-
-/* A genlist, storing the number of elements (for quick retrieval and
-   testing for empty lists), and pointers to the first and last elements
-   of the list.
-*/
+/* The nelements parameter contains the number of links in the list, while
+ * head and tail point to first and last link, respectively. The track 
+ * variable points to our entry in the tracker, if we are there. */
 struct genlist {
   int nelements;
-  struct genlist_link *head_link;
-  struct genlist_link *tail_link;
+  int ndeleted;
+  struct genlist_link *head;
+  struct genlist_link *tail;
+  struct genlist_link *track;
 };
 
-int genlist_size(const struct genlist *pgenlist);
-void *genlist_get(const struct genlist *pgenlist, int idx);
-struct genlist *genlist_new(void);
-void genlist_unlink_all(struct genlist *pgenlist);
-void genlist_free(struct genlist *pgenlist);
-void genlist_append(struct genlist *pgenlist, void *data);
-void genlist_prepend(struct genlist *pgenlist, void *data);
-void genlist_unlink(struct genlist *pgenlist, void *punlink);
+/* Operations on all lists */
+void genlists_init(void);
+void genlists_free(void);
+void genlists_prune(void);
 
-void genlist_sort(struct genlist *pgenlist,
-                 int (*compar)(const void *, const void *));
+/* Operations on a single list */
+struct genlist *genlist_new(void);
+#define genlist_size(plist) ((plist)->nelements)
+void *genlist_get(const struct genlist *plist, int idx);
+void genlist_prepend(struct genlist *plist, void *data);
+void genlist_append(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) ? ((iter)->dataptr) : NULL)
+#define ITERATOR_PTR(iter) ((iter)->dataptr)
 #define ITERATOR_NEXT(iter) (iter = (iter)->next)
 #define ITERATOR_PREV(iter) (iter = (iter)->prev)
 
-
 /* 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 *myiter = (typed_list)->list->head_link;             \
-  atype *var;                                                              \
-                                                                           \
-  for (; ITERATOR_PTR(myiter);) {                                          \
-    var = (atype *)ITERATOR_PTR(myiter);                                   \
-    ITERATOR_NEXT(myiter);
-
-/* Balance for above: */ 
-#define LIST_ITERATE_END                                                   \
-  }                                                                        \
-}
-
-
-/* Same, but iterate backwards: */
-#define TYPED_LIST_ITERATE_REV(atype, typed_list, var)                     \
-{                                                                          \
-  struct genlist_link *myiter = (typed_list)->list->tail_link;             \
-  atype *var;                                                              \
-                                                                           \
-  for (; ITERATOR_PTR(myiter);) {                                          \
-    var = (atype *)ITERATOR_PTR(myiter);                                   \
-    ITERATOR_PREV(myiter);
- 
-/* Balance for above: */ 
-#define LIST_ITERATE_REV_END                                               \
-  }                                                                        \
-}
+#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  /* FC__GENLIST_H */
+#endif
Index: utility/registry.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/registry.c,v
retrieving revision 1.70
diff -u -r1.70 registry.c
--- utility/registry.c  7 May 2005 18:45:13 -0000       1.70
+++ utility/registry.c  14 May 2005 19:52:16 -0000
@@ -210,10 +210,6 @@
        TYPED_LIST_ITERATE(struct section, seclist, psection)
 #define section_list_iterate_end  LIST_ITERATE_END
 
-#define section_list_iterate_rev(seclist, psection) \
-       TYPED_LIST_ITERATE_REV(struct section, seclist, psection)
-#define section_list_iterate_rev_end  LIST_ITERATE_REV_END
-
 /* The hash table and some extra data: */
 struct hash_data {
   struct hash_table *htbl;
@@ -674,7 +670,7 @@
     /* Following doesn't use entry_list_iterate() because we want to do
      * tricky things with the iterators...
      */
-    for(ent_iter = psection->entries->list->head_link;
+    for(ent_iter = psection->entries->list->head;
         ent_iter && (pentry = ITERATOR_PTR(ent_iter));
        ITERATOR_NEXT(ent_iter)) {
 

[Prev in Thread] Current Thread [Next in Thread]