[Freeciv-Dev] (PR#10077) genlist cleanup

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=10077 >

I started out just tryping to make some function parameters const.  But 
in the end the changes were larger:

- Make the parameters of genlist_size, genlist_get, 
find_genlist_element, and the corresponding speclist functions into 
const parameters.  Currently if you have a const player * you can't call 
city_list_size(pplayer->cities)!

- Remove null_link from the genlist pointers.  Instead NULL is used.  A 
comment already said it was dubious by comparison to NULL.  And it won't 
work with the previous const changes.  The reason is really that the 
null_ptr must be const, you can never change it or its dataptr.  But 
it's way too easy for a user to do so by mistake.

- Remove static variables from genlist.c.  These are unthreadsafe, 
inefficient, and take more code.  Instead I just use variable-sized 
stack arrays.

- Remove some pointer casts.  Such casts can hide bugs (particularly 
when casting a const to a non-const pointer) and are simply unnecessary.

jason

? diff
? diff2
? settler_recursion_crash
Index: utility/genlist.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/genlist.c,v
retrieving revision 1.14
diff -u -r1.14 genlist.c
--- utility/genlist.c   1 Nov 2003 01:02:38 -0000       1.14
+++ utility/genlist.c   13 Sep 2004 01:19:58 -0000
@@ -21,7 +21,7 @@
 
 #include "genlist.h"
 
-static struct genlist_link *find_genlist_position(struct genlist *pgenlist,
+static struct genlist_link *find_genlist_position(const struct genlist 
*pgenlist,
                                                  int pos);
 
 /************************************************************************
@@ -31,18 +31,15 @@
 void genlist_init(struct genlist *pgenlist)
 {
   pgenlist->nelements=0;
-  pgenlist->head_link=&pgenlist->null_link;
-  pgenlist->tail_link=&pgenlist->null_link;
-  pgenlist->null_link.next=&pgenlist->null_link;
-  pgenlist->null_link.prev=&pgenlist->null_link;
-  pgenlist->null_link.dataptr = NULL;
+  pgenlist->head_link = NULL;
+  pgenlist->tail_link = NULL;
 }
 
 
 /************************************************************************
   Returns the number of elements stored in the genlist.
 ************************************************************************/
-int genlist_size(struct genlist *pgenlist)
+int genlist_size(const struct genlist *pgenlist)
 {
   return pgenlist->nelements;
 }
@@ -51,14 +48,18 @@
 /************************************************************************
   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 0 (the dataptr of null_link).
+  returns NULL.
   Recall 'idx' can be -1 meaning the last element.
 ************************************************************************/
-void *genlist_get(struct genlist *pgenlist, int idx)
+void *genlist_get(const struct genlist *pgenlist, int idx)
 {
   struct genlist_link *link=find_genlist_position(pgenlist, idx);
 
-  return link->dataptr;
+  if (link) {
+    return link->dataptr;
+  } else {
+    return NULL;
+  }
 }
 
 
@@ -75,10 +76,10 @@
     do {
       plink2=plink->next;
       free(plink);
-    } while((plink=plink2)!=&pgenlist->null_link);
+    } while ((plink = plink2) != NULL);
 
-    pgenlist->head_link=&pgenlist->null_link;
-    pgenlist->tail_link=&pgenlist->null_link;
+    pgenlist->head_link = NULL;
+    pgenlist->tail_link = NULL;
 
     pgenlist->nelements=0;
   }
@@ -95,8 +96,9 @@
   if(pgenlist->nelements > 0) {
     struct genlist_link *plink=pgenlist->head_link;
     
-    while(plink!=&pgenlist->null_link && plink->dataptr!=punlink)
-       plink=plink->next;
+    while (plink != NULL && plink->dataptr != punlink) {
+      plink = plink->next;
+    }
     
     if(plink->dataptr==punlink) {
       if(pgenlist->head_link==plink)
@@ -127,30 +129,28 @@
 {
   if(pgenlist->nelements == 0) { /*list is empty, ignore pos */
     
-    struct genlist_link *plink=(struct genlist_link *)
-                                 fc_malloc(sizeof(struct genlist_link));
+    struct genlist_link *plink = fc_malloc(sizeof(*plink));
 
     plink->dataptr=data;
-    plink->next=&pgenlist->null_link;
-    plink->prev=&pgenlist->null_link;
+    plink->next=NULL;
+    plink->prev=NULL;
 
     pgenlist->head_link=plink;
     pgenlist->tail_link=plink;
 
   }
   else {
-    struct genlist_link *plink=(struct genlist_link *)
-                                 fc_malloc(sizeof(struct genlist_link));
+    struct genlist_link *plink = fc_malloc(sizeof(*plink));
     plink->dataptr=data;
 
     if(pos==0) {
       plink->next=pgenlist->head_link;
-      plink->prev=&pgenlist->null_link;
+      plink->prev = NULL;
       pgenlist->head_link->prev=plink;
       pgenlist->head_link=plink;
     }
     else if(pos<=-1 || pos>=pgenlist->nelements) {
-      plink->next=&pgenlist->null_link;
+      plink->next = NULL;
       plink->prev=pgenlist->tail_link;
       pgenlist->tail_link->next=plink;
       pgenlist->tail_link=plink;
@@ -173,20 +173,21 @@
 /************************************************************************
   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 the null_link.
+  For pos out of range returns NULL.
   Traverses list either forwards or backwards for best efficiency.
 ************************************************************************/
-static struct genlist_link *find_genlist_position(struct genlist *pgenlist,
+static struct genlist_link *find_genlist_position(const struct genlist 
*pgenlist,
                                                  int pos)
 {
   struct genlist_link *plink;
 
-  if(pos==0)
+  if (pos == 0) {
     return pgenlist->head_link;
-  else if(pos==-1)
+  } else if (pos == -1) {
     return pgenlist->tail_link;
-  else if(pos<-1 || pos>=pgenlist->nelements)
-    return &pgenlist->null_link;
+  } else if (pos < -1 || pos >= pgenlist->nelements) {
+    return NULL;
+  }
 
   if(pos<pgenlist->nelements/2)   /* fastest to do forward search */
     for(plink=pgenlist->head_link; pos != 0; pos--)
@@ -209,44 +210,29 @@
  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.  This function will be called many times, so we use
- a static pointed to realloc-ed memory.  Calling this function with
- compar==NULL will free the memory and do nothing else.
+ the genlist.
 ************************************************************************/
 void genlist_sort(struct genlist *pgenlist,
                  int (*compar)(const void *, const void *))
 {
-  static void **sortbuf = 0;
-  static int n_alloc = 0;
-  
+  const int n = genlist_size(pgenlist);
+  void *sortbuf[n];
   struct genlist_link *myiter;
-  int i, n;
+  int i;
 
-  if(compar==NULL) {
-    free(sortbuf);
-    sortbuf = NULL;
-    n_alloc = 0;
+  if (n <= 1) {
     return;
   }
 
-  n = genlist_size(pgenlist);
-  if(n <= 1) {
-    return;
-  }
-  if(n > n_alloc) {
-    n_alloc = n+10;
-    sortbuf = (void **)fc_realloc(sortbuf, n_alloc*sizeof(void*));
-  }
-
   myiter = find_genlist_position(pgenlist, 0);  
   for(i=0; i<n; i++, ITERATOR_NEXT(myiter)) {
     sortbuf[i] = ITERATOR_PTR(myiter);
   }
   
-  qsort(sortbuf, n, sizeof(void*), compar);
+  qsort(sortbuf, n, sizeof(*sortbuf), compar);
   
   myiter = find_genlist_position(pgenlist, 0);  
   for(i=0; i<n; i++, ITERATOR_NEXT(myiter)) {
-     ITERATOR_PTR(myiter) = sortbuf[i];
+    myiter->dataptr = sortbuf[i];
   }
 }
Index: utility/genlist.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/genlist.h,v
retrieving revision 1.11
diff -u -r1.11 genlist.h
--- utility/genlist.h   1 Nov 2003 01:02:38 -0000       1.11
+++ utility/genlist.h   13 Sep 2004 01:19:58 -0000
@@ -60,22 +60,16 @@
 
 /* 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 address of the null_link is used to "terminate"
-   the ends of the list, and head_link and tail_link initially point
-   to null_link.  null_link always has dataptr==0.  (This is used to
-   conveniently deal with "out of range" results etc, though I'm not
-   sure if it really gives a big advantage compared to a scheme just
-   using NULL as a terminator/flag value  --dwp)
+   of the list.
 */
 struct genlist {
   int nelements;
-  struct genlist_link null_link;
   struct genlist_link *head_link;
   struct genlist_link *tail_link;
 };
 
-int genlist_size(struct genlist *pgenlist);
-void *genlist_get(struct genlist *pgenlist, int idx);
+int genlist_size(const struct genlist *pgenlist);
+void *genlist_get(const struct genlist *pgenlist, int idx);
 void genlist_init(struct genlist *pgenlist);
 void genlist_unlink_all(struct genlist *pgenlist);
 void genlist_insert(struct genlist *pgenlist, void *data, int pos);
@@ -84,7 +78,7 @@
 void genlist_sort(struct genlist *pgenlist,
                  int (*compar)(const void *, const void *));
 
-#define ITERATOR_PTR(iter) ((iter)->dataptr)
+#define ITERATOR_PTR(iter) ((iter) ? ((iter)->dataptr) : NULL)
 #define ITERATOR_NEXT(iter) (iter = (iter)->next)
 #define ITERATOR_PREV(iter) (iter = (iter)->prev)
 
Index: utility/speclist.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/utility/speclist.h,v
retrieving revision 1.6
diff -u -r1.6 speclist.h
--- utility/speclist.h  5 May 2004 20:39:16 -0000       1.6
+++ utility/speclist.h  13 Sep 2004 01:19:58 -0000
@@ -91,14 +91,14 @@
   genlist_unlink(&tthis->list, pfoo);
 }
 
-static inline int SPECLIST_FOO(_list_size) (SPECLIST_LIST *tthis)
+static inline int SPECLIST_FOO(_list_size) (const SPECLIST_LIST *tthis)
 {
   return genlist_size(&tthis->list);
 }
 
-static inline SPECLIST_TYPE *SPECLIST_FOO(_list_get) (SPECLIST_LIST *tthis, 
int index)
+static inline SPECLIST_TYPE *SPECLIST_FOO(_list_get) (const SPECLIST_LIST 
*tthis, int index)
 {
-  return (SPECLIST_TYPE *)genlist_get(&tthis->list, index);
+  return genlist_get(&tthis->list, index);
 }
 
 static inline void SPECLIST_FOO(_list_insert_back) (SPECLIST_LIST *tthis, 
SPECLIST_TYPE *pfoo)