[Freeciv-Dev] Re: list cleaning

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

On Sun, 30 Nov 2003, Raimar Falke wrote:
> On Sun, Nov 30, 2003 at 02:06:10PM +0000, Per I. Mathisen wrote:

> > I am not sure why we are having this meta-discussion, though. Can we get
> > back to the technical merits of the different approaches, please?
>
> Ok lets enumerate all possibilities
>
> 1) safe iterators
>  - low code impact
>  - low speed impact
>  - low memory impact
>  - not safe

> 2) safe iterators where needed
>  - requires balanced iterators (which have medium/high code impact)
>  - low code impact by itself
>  - low speed impact
>  - low memory impact
>  - safe

> 3) lazy deletion with explicit pruning (once per turn for example)
>  - medium/high code impact
>  - low speed impact
>  - low memory impact (higher if prune call is missed)
>  - safe

Don't be so sure about the low speed impact. I have experienced this
solution before. It trashes the cache a lot, besides, you get to test
lists which haven't even been modified, which isn't the case with most
of the other solutions.

> 4) lazy deletion with implicit pruning at leaving the outer most
> iterator
>  - requires balanced iterators (which have medium/high code impact)
>  - low code impact by itself
>  - low speed impact
>  - low memory impact
>  - safe

I prefer this solution in combination with 2). Because lists which haven't
been modified don't get tested, for one.

> 5) lazy deletion with explicit pruning via global list of current
> genlists
>  - low code impact
>  - low speed impact
>  - low memory impact
>  - safe

Better than 3, but I still don't like the fact that you get to test lists
which haven't changed, plus when do you do the pruning? I like to keep
things simple.

> 5) looks like the clear winner but has the problem that it won't work
> without an genlist_destroy function. Assume this code:
>
>  {
>   struct genlist list;
>
>   genlist_init(&list);
>   ... use list
>   genlist_unlink(&list, ...);
>   ... use list some more
>  }
>  ...
>  global_prune_function();
>
> global_prune_function will find random data at the time the function
> is called.
>
> We have such similar code in control.c:process_caravan_arrival() (with
> a static list variable).

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