[Freeciv-Dev] Re: (PR#8800) [RFC] Usage of speclist vs specvec

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

<URL: http://rt.freeciv.org/Ticket/Display.html?id=8800 >

On Sat, May 22, 2004 at 02:15:32AM -0700, Jason Short wrote:
> 
> <URL: http://rt.freeciv.org/Ticket/Display.html?id=8800 >
> 
> Jason Short wrote:
> > <URL: http://rt.freeciv.org/Ticket/Display.html?id=8800 >
> > 
> > Raimar Falke wrote:
> > 
> > 
> >>I think this is a bit bold to say. If you for example change the size
> >>a lot the list has less overhead (malloc + copy).
> > 
> > I doubt that very much.  Can you show numbers?
> 
> Well, nevermind - that would be a waste of time.
> 
> Both speclist and specvec are O(1) on insert and most other operations.
> 
> Specvec is O(1) on indexed lookups, whereas speclist is O(n).
> 
> Speclist can only handle pointers, specvec can handle any data type.
> 
> Speclist's interface is a little easier for unordered lists.
> 
> With specvec it is impossible to delete elements from the middle.  Or at 
> best it's O(n) if you do it manually (compared to O(1) for speclist).

The specvec has one special property: it is an array (a contiguous
amount of memory). However only very few (if any) cases need that
special property. For all the other cases it doesn't matter for the
user if it is a speclist or specvec. So in the long term I want only
one interface here. Examples are
http://java.sun.com/j2se/1.4.2/docs/api/java/util/List.html and
http://www.python.org/doc/2.3.3/lib/typesseq.html.

Currently we have a lot more speclist users than specvec. So I propose:
 - change the specvec interface to be very similar to the speclist one:
   * free vs unlink
   * add copy and reserve to speclist
 - keep the number of specvec users low

A unified interface would get flags passed to init like
"many-inserts", "many-deletes", "only-append", "many-indexed-gets" and
so on. The init() function will than choose one implementation.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  reality.sys corrupt. Reboot Universe? (y,n,q)