[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Growable arrays?

From: Thien-Thi Nguyen
Subject: Re: Growable arrays?
Date: Mon, 11 Jun 2012 10:14:00 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux)

() David Kastrup <address@hidden>
() Sat, 09 Jun 2012 14:32:28 +0200


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:

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.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]