Re: Growable arrays?

[Thien-Thi Nguyen <ttn@gnuvola.org>]

() David Kastrup <dak@gnu.org>
() Sat, 09 Jun 2012 14:32:28 +0200

   Suggestions?

Guile-SDL implements (in C) collections of "enums" using both a C array
(static, used also for init) and a Scheme hash table for backing store:

http://git.savannah.gnu.org/cgit/guile-sdl.git/tree/src/sdlenums.c#n66

This is not dynamic (growable) as you specified, but i figure it
might be useful as an example building block.  The modifications
are straightforward.  You would have to add a container for the
set of arrays, and two (more) indirections to ‘lookup’ (line 97),
the first to distinguish between integer/otherwise ‘key’, the
second to index into the outer container.

Alternatively, keep track of collection size and add entries to
the hash table under both the user-given key and the monotonic
‘size - 1’ (two entries).  Extremely wasteful spacewise.

Less wasteful spacewise but more wasteful timewise would be to
combine the above approaches, where the initial (static, before
growth) set does not get a double entry, but in turn requires
another check (branch) in ‘lookup’.  Actually the cut-off index
need not be the initial set; it need only correspond to the
initial array allocation (possibly greater than the initial set).

I suspect some of these considerations have gone into the vlist
implementation (though not all since IIRC vlists alloc doubling
"on overflow"; there is not a single threshold), so another idea
is to use that, back-porting as necessary.

Tangential: I think vlists should be aggressively exercised,
debugged and then back-ported to 1.8 and before.  It's a nice
self-contained design.  This requires a change of policy, though.