[Freeciv-Dev] Re: list cleaning

[Raimar Falke <i-freeciv-lists@xxxxxxxxxxxxx>]

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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  One nuclear bomb can ruin your whole day.