On Mon, 14 Feb 2011 16:39:24 -0500, spir <[email protected]> wrote:
On 02/14/2011 03:27 PM, Steven Schveighoffer wrote:
On Mon, 14 Feb 2011 06:31:25 -0500, spir <[email protected]> wrote:
Hello,
How would you wrap an AA to allow memorising insertion order, and be
able to
use it
for iteration?
* Indeed, one could store keys in a // (ordered) array. But this means
iteration requires a series of lookups by key.
* A slightly better method would be to store hash values, which anyway
are
computed at insertion time, and pass them to whatever internal routine
is
used to
fetch an item.
* Even better, store an array of pointers to the items.
Typically, items in hash tables are kinds of cells in the "bucket"
storing
pairs which "modulo-ed" hash values are equal. If I know the internal
representation of such cells, then I can get (key,value) pairs. I've
read once
such buckets are now linked lists, which can only make things simpler.
The issue for last 2 solutions is I need to catch some info at
insertion
time. The second one even requires calling an internal routine.
Any chance? In any case, a pointer to current implementation of D AAs
is
welcome.
Here is the main struct which calls the implementation functions:
https://github.com/D-Programming-Language/druntime/blob/master/src/object_.d#L2461
Hopefully the functions that it calls are clues as to where to find the
implementations (all in druntime). I warn you, they are based fully on
runtime
information, so they are going to be ugly.
-Steve
Thank you Steve. Would be a bit too complicated for me now, because this
struct does not expose what I need (internal operation of insertion),
only what corresponds to ordinary D lang operations. I'm not ready for
messing with lower level code (yet).
It's not that low level. The functions are basically C binded functions
from druntime. Do a tree-search for those symbols and you'll find the
implementations. The only ugly part is how it uses runtime information
for things like comparing two instances.
-Steve
