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

[Justin Moore <justin@xxxxxxxxxxx>]

   A patch for my new genlist.[ch] files against today's CVS is attached.
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.

   There are currently two kinds of list iteration macros: one (STABLE_*)
for lists where the number of elements doesn't change and another (REAL_*)
for those that do (REAL_ because that's what most use ATM).  The REAL_*
macros use the iterators, which are painfully slow but are very tolerant
of one or more elements being removed from underneath them.

   A side-effect of making the genlist iterators functions: they show up
in profiling so you can tell exactly what percentage of the old loops
you've removed by converting to the new macros.

> > > > I'm open to suggestions on how to cleanly remove elements from an
> > > > array without screwing over iterators.
> > >
> > > As pointed you: restarting the loop.
> > >
> > > > One possibility that comes to mind is to have an associated array of
> > > > boolean values which marks the entry as valid or not.
> > >
> > > Complicated.
> >
> >    Somewhat, but possibly more efficient than restarting the loop.  I'll
> > see as I go along the pros and cons of each.  Plus, what if there are
> > cases in which the loop must adhere to "only-once" semantics?  Some
> > function that will break or return incorrect results if certain items are
> > iterated over more than once?
>
> Another solution is a seperate list:
>
> init_list(&new_list);
>
> for(;;)
> {
>   if(list_get_size(list)==0)
>      break;
>   item=list_unlink_first(list);
>   if(condition)
>   {
>     destroy_item(item);
>   }
>   else
>   {
>      list_append(tmp_list,item);
>   }
> }
> list=tmp_list;
>
> Clean, safe and efficient (not for long lists). Only some more writing
> is needed. I can image a list_filter method which does all the above
> and only takes the list and two callbacks (for condition testing and
> destroying).

   The problem isn't so much lists where the destruction is done within
the body of the loop.  The problem is loops where three function calls
down from the body of the loop, THAT function MAY remove an element from
the list, so by the time you work back up the call stack, an element is
gone and you don't even know it in the original loop.  Which is where
having intelligent iterators comes in handy.

   For the time being I'm going to go with the approach of "If you think
this loop may remove elements from the list, use the iterators", and if
not, use the new ones.  I'm pretty sure we can migrate a good percentage
of the loops over to the new macros.

> >    Removing current data is ok, but not 'next'.  Another possible (but
> > more involved) solution is to keep track of how many iterators are
> > currently looping over a list.  When an item is removed from a list, go
> > through and find if that deletion messes with any of the iterators.  More
> > complex, but more robust.  Comments?
>
> Too complex. Just fix the code which does something like this. From a
> performance point of view: if you try to catch all cases you would be
> slow. And the whole point is to be fast(er).
>
>       Raimar
>
> --
>  email: rf13@xxxxxxxxxxxxxxxxx
>  "Premature optimization is the root of all evil."
>     -- D. E. Knuth in "Structured Programming with go to Statements"

   I enjoy how your last sentence is somewhat at odds with your sig. :)
IMHO, the _long-term_ goal is to be faster, but ATM it's just to get the
code correct because I *know* the code will be faster once we replace many
instances of iterators with STABLE_ macros.

   Not to fan an old flame, but I think this is a good argument for having
a development branch; we could put almost-100%-working code into it and
have a larger number of people bang on it.  For the moment I just have to
plead with the list to apply my patch and find where things break. :) It
hasn't crashed my games out or done any serious damage as far as I can
tell; please, give it a shot. *sad look in eyes*

-jdm

Department of Computer Science, Duke University, Durham, NC 27708-0129
Email:  justin@xxxxxxxxxxx

genlist-Aug-29-cvs.patch.gz
Description: new genlist functions