[Freeciv-Dev] Re: list cleaning

[Vasco Alexandre Da Silva Costa <vasc@xxxxxxxxxxxxxx>]

On Sat, 29 Nov 2003, Raimar Falke wrote:

> On Sat, Nov 29, 2003 at 02:38:18PM +0000, Per I. Mathisen wrote:
> > No, I'm not talking about this list ;)
> >
> > Recently I rewrote genlist.c to do lazy deletes. Instead of removing nodes
> > in the linked list when they are 'deleted', they are just marked as
> > deleted and ignored from then on until a call to the list's prune()
> > function is done. When prune() is called, the deleted nodes are actually
> > deleted. This makes the lists safe to nest iterations deeply while
> > deleting nodes at will - currently such safety is kludged with
> > unit_list_iterate_safe(), which is uglier, slower (malloc for each use)
> > and less safe unless done everywhere.
> >
> > This worked fine in the server, since the number of lists is limited and
> > easily pruned in one key place. It is harder to do in a clean way for the
> > client, so some other maintainers want to 'normalize' iterators (no return
> > or goto inside iterators allowed) and count depth of iterator nesting, and
> > then when we're all the way out, we prune the list automatically.
> >
> > I am skeptical of this approach. Prune is fast (one quick iteration of the
> > entire list) but fast is relative. Consider this example:
> >
> >   players_iterate() {
> >     unit_list_iterate() {
> >       city_list_iterate() {
> >       } city_list_iterate_end;
> >     } list_two_iterate_end;
> >   } players_iterate_end;
> >
> > Now you will prune() the city list p * u * c times (where p is number of
> > players, u number of units in the game, c number of cities in the game).
> > That can be a very high number.
> >
> > Instead, I suggest this: The function genlist_init() (and by extension
> > *_list_init()) registers every list in a static, internal genlist of
> > genlists. When genlist_prune() is called, it cleans every registered list.
> > This way we can be certain that lists are only cleaned a limited number of
> > times and only when it is guaranteed safe to do so.
>
> This is possible to achieve faster code. Another idea is to use a bool
> flag in the genlist which is set to TRUE when a node is deleted and to
> FALSE after prune got called. prune will only be called if this
> deleted field is TRUE.

The modified version of Per's code I have already does this, but I still
need to fix the iterations. Now that delta is in CVS, I can resume work
on that.

---
Vasco Alexandre da Silva Costa @ Instituto Superior Tecnico, Lisboa