[Freeciv-Dev] Re: very simple specvecs

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

On Sat, 15 May 2004, Jason Dorje Short wrote:

> It would be possible to make the specvec a simple array.
>
>    struct {
>      int a, b;
>    } foo;
>
>    #define SPECVEC_TAG foo
>    #include "specvec.h"
>
>    {
>      foo_vector foo;
>
>      foo_vector_init(&foo);
>      foo_vector_reserve(&foo, 2);
>
>      foo[0].a = 1;
>      foo[0].b = 2;
>      foo[1].a = 2;
>      foo[1].b = 4;
>
>      for (i = 0; i < foo_vector_size(&foo); i++) {
>        printf("%d, %d\n", foo[i].a, foo[i].b);
>      }
>
>      foo_vector_free(&foo);
>    }
>
> However it would be _somewhat_ slower.  Lookups would obviously be a
> fast O(1) operation.  All other operations would still be O(1) but would
> be slightly slower.
>
> Disregarding the potential ugliness of the implementation (no crazy
> memory tricks would be needed, don't worry Vasco), how useful would this be?
>
> ---
>
> One implementation:
>
> Obviously we now have a
>
>    typedef struct foo *foo_vector;
>
> As well we have a global hash of existing vector arrays (all vectors,
> not just foo_vectors).  When the _init is done this vector is added to
> the hash, and the size and size_alloc are put into the value stored in
> the hash (a second malloc is needed here).  Then these values are looked
> up in the hash (a slow O(1) operation) every time the vector's functions
> are accessed.
>
> Perhaps this is too much of a reimplementation of malloc?

If that is the alternative, Gimme the stupid memory tricks. :-)

Just malloc a chunk and store the size before the beggining of the array.
Then return a pointer to the beggining of the array. To know the size,
access the memory before the pointer to the beggining. That should do what
you want.

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