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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Aug 28, 2001 at 03:14:56PM -0400, Justin Moore wrote:
> 
> > >    I rearranged the placement of the iterators and it broke things.  I'm
> > > digging through coredumps trying to find it, but IMHO there's something
> > > pretty broken here.  Not surprising, given the comment near the top of
> > > genlist.h about iterators and placement of said macros. :) The code is
> > > actually quite all right with the current element being removed from under
> > > it.  How odd.
> >
> > You could clean up such things with the current genlist implementation.
> 
>    That's the plan. :)
> 
> > > 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).

> > > Plus this whole "it's-ok-for-my-current-data-to-disappear" mindset
> > > is frustrating. ;p
> >
> > ??
> 
> >From genlist.h, lines 84-90 (in a comment):
> 
>    Be very careful if the genlist is modified while the iteration
>    is in progress.  The standard macros (based on TYPED_LIST_ITERATE
>    below) allow removing the "current" element, as the iterator
>    is advances at the start of the loop, but if the "next" element
>    is removed (including as a side effect of removing the current
>    element), expect core dumps.  See server/unitfunc.c:wipe_unit_safe()
>    as an example of protecting against this.
> 
>    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"