[Freeciv-Dev] Re: [PATCH] Re: {gen,spec,sort}list stuff

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Aug 31, 2001 at 02:25:18PM -0400, Justin Moore wrote:
> 
> > > > > I've started to notice some inconsistencies in games using the same 
> > > > > random
> > > > > seeds (map and game) between games that use the old genlist and ones 
> > > > > that
> > > > > use my genlist.  Yet I can't find any problems in my implementation of
> > > > > genlist (yes, I realize that by saying this I'm opening myself up to
> > > > > someone finding incredibly obvious bugs ... which is almost the 
> > > > > point).
> > > > > I'd appreciate any extra eyes looking at the code.
> > > >
> > > > Is it possible to have both lists in parallel and compare their results.
> > >
> > >    Yes, I'll get back to everyone on this.
> 
>    I just ran a test with both lists running in parallel using bunches of
> asserts around the wrapper calls to genlist_*.  There was no difference in
> the contents of the two lists throughout the game, so I have no idea why
> one would obtain slightly different results from the other when run
> separately.  In this light, I'm submitting my genlist.[ch] files as a
> patch to the current CVS tree.
> 
> > > > I'm not happy with the name REAL_.
> > >
> > >    SAFE_?
> 
>    For lack of comments, there are the new names.
> 
> > > >  - is this mess with the current genlist_sort and NULL needed? It is
> > > >  used.
> > >
> > >    Could you be more specific?  I'm just replicating the external behavior
> > > of genlist_sort when given a NULL compar pointer: nothing is done to the
> > > list.
> >
> > The external behavior is stupid IMHO. It isn't used anywhere in the
> > code. This can be removed in the current code. No need to code such
> > no-used features in new versions.
> 
> The code in question:
> 
>  void genlist_sort(struct genlist *pgenlist,
>                   int (*compar)(const void *, const void *))
>  {
>    if(compar == NULL)
>      return;
> 
>    qsort(pgenlist->data, pgenlist->nelements, sizeof(void*), compar);
>  }
> 
>    So what should I do if the compar is NULL?

Assert.

> >   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.
> >
> > +  idx = genlist_find_index(pgenlist, punlink);
> > +  if(idx == -1)
> > +    return;
> 
>    I've put an assert(idx != -1) after the function call.  This way we'll
> know when something's wrong in a development version but it won't break in
> a release.
> 
>    If this is accepted, I have a slew of patches (all small :)) that I can
> throw out to start moving from the slower iterators to the newer ones.

If I would accept the new version now there would be an improvement
loss. IMHO you should prepare the main code using patches so that the
introduction of the new version will yield an immediate performance
gain.

I still dislike the extra "if(!pgenlist->capacity) {" in
genlist_resize. It is unnecessary. Same in genlist_unlink_all.

Why do you make an extra "void **arr = pgenlist->data;" in
genlist_find_index? I'm sure the compiler will optimize this. Same in
genlist_unlink.

+  if(pos == pgenlist->nelements) {
+    pgenlist->data[pgenlist->nelements] = data;
+  } else {
+    int i;
+
+    /* Start at the end and move everything "up" one spot.
+     * We start at the end so as not to overwrite anything as we go. */
+    void **arr = pgenlist->data;
+    for(i = pgenlist->nelements;i > pos;i--)
+      arr[i] = arr[i-1];
+    arr[pos] = data;
   }

This can IMHO be folded in one case where the for loop is never
entered in the case "pos == pgenlist->nelements".

There are a some special cases like:
  +  if((idx < -1) || (idx >= pgenlist->nelements))
  +    return NULL;

or

+  /* If the insert position is invalid, put the data onto the end. */
+  if((pos < 0) || (pos >= pgenlist->nelements)) {
+    pos = pgenlist->nelements;
+  }

This is not so much to do with the patch but I would like to know if
these really exists?

It looks like this branch:
+        if(cp == -1) {
+          iter->curr_data = NULL;  /* Our data disappeared!! */
+          return NULL;
+        } else {
+          iter->curr_pos = cp;
+          iter->curr_data = list->data[cp];
+          return iter->curr_data;
+        }
and this one
+      if(cp == -1) {
+        iter->curr_data = NULL;
+        iter->curr_pos = -1;
+        return NULL;
+      } else {
+        iter->curr_pos = cp;
+        iter->curr_data = list->data[cp];
+        return iter->curr_data;
+      }
are the same/almost the same. Can they be merged?

It looks like some of the code of genlist_iterator_ptr,
genlist_iterator_next and genlist_iterator_prev can be merged. What
about a "ensure_valid_position" method?


IMHO the names STABLE and SAFE should be changed. STABLE means the
list can be used if the iteration won't change something. SAFE means
something other. SAFE should be MODIFYING or so.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 1 + 1 = 3, for large values of 1