[Freeciv-Dev] list cleaning

["Per I. Mathisen" <per@xxxxxxxxxxx>]

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.

I will code this if I get thumbs up.

  - Per