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

[Justin Moore <justin@xxxxxxxxxxx>]

   In my quest to speed up the list stuff I've been able to categorize the
different kind of lists and have outlined a plan for migrating things
over.  But first off, in genlist.h is there any particular reason that the
TYPED_LIST_ITERATE* macros do an ITERATE_{PREV,NEXT} at the beginning of
the loop instead of at the end?  In many places in the code it's manually
done at the end, so there are potential inconsistancies.  The macros
(essentially) do this:

while(ITERATOR_PTR(X)) {
  ITERATOR_NEXT(X);
  /* Do stuff */
}

but many parts of the code do this (manually):

while(ITERATOR_PTR(X)) {
  /* Do stuff */
  ITERATOR_NEXT(X);
}

   Anyway, the various lists within the code fall into a few categories:

1. Lists that rely heavily on iterators and do nasty things in the middle
     of iterating such as remove elements from the list (often based on
     the contents of the iterator).
2. Lists that occasionally remove items during iteration, but for the most
     part are constant.
3. Lists for which it is preferable for them to be non-sorted.
4. Lists that are initialized at the start of the game and then only
     searched or the contents updated.

   Examples of these are:
1. Unit lists, private copies of the map, etc
2. Connection lists
3. Those mentioned in previous e-mails (order in which units are examined,
     order in which map tiles are looked at by the AI, etc)
4. List of diplomatic relations

   The new genlist API that I've worked on is backwards compatible with
the old one, and I think it's correct.  I've run a few all-AI games with
the old and new modules and seen identical results.  The underlying data
structure for all lists is now a dynamically resizeable array, but
iterator data structure operations are now painfully slow for a few
reasons.  I've created new macros -- SERIAL_TYPED_LIST_ITERATE* -- that
work for iterations in which no data is modified.  These would be very
good for packet_lsend.c and other type 2 lists.

   "So what's the plan?" you may ask?  In a nutshell:

- Add SERIAL_TYPED_LIST_ITERATE* macros as serial_{conn,unit,etc}_iterate
    macros and replace as many simple iteration loops with them as I can.
- Migrate all the category 4 lists and iterations over to the serial
    iterators as possible.  Potentially move them over to sortlists later.
- Beat my head against a wall for all the category 1 lists.

   I'm not sure of the side-effects of some functions that are calling
from within city_list_iterate blocks (for example), so this may take a
while to finish.

Questions?  Comments?  Flames?
-jdm

Department of Computer Science, Duke University, Durham, NC 27708-0129
Email:  justin@xxxxxxxxxxx