ordered hash thoughts

5 views
Skip to first unread message

Leopold Toetsch

unread,
May 25, 2005, 9:34:14 AM5/25/05
to Perl 6 Internals
The OrderedHash PMC provides indexed access by a (string) key as well as
indexed access by insertion order. It's currently implemented as an hash
holding the index value into the data array.
The problem is of course deleting items (and adding items w/o string
key). The former is done by storing a new Undef item, the latter just
messes up the whole thing, IIRC.

Anyway, we can achieve the same effect by indexing into the hash bucket
store directly (at least after reversing the free_list order).

E.g. an (ordered) hash with 4 entries, these are hashed in the bucket
index and point to the bucket store:

buckets keys (bucket**)
b0 b1 b2 b3 h2 h1 h3 h0

The buckets just come in order from the free_list - or for the
specialized ordered hash - are just given away in array indexed order.

This would suffice for the planned used cases, which are typically:
- add (push) items by key
- retrieve items by key or by numeric index

E.g.:
- lexicals
- PMC/class types
- object attributes
- constant string table
- ...

leo

Dan Sugalski

unread,
May 25, 2005, 10:59:27 AM5/25/05
to Leopold Toetsch, Perl 6 Internals
At 3:34 PM +0200 5/25/05, Leopold Toetsch wrote:
>The OrderedHash PMC provides indexed access by a (string) key as
>well as indexed access by insertion order. It's currently
>implemented as an hash holding the index value into the data array.
>The problem is of course deleting items (and adding items w/o string
>key). The former is done by storing a new Undef item, the latter
>just messes up the whole thing, IIRC.

Given the usage this is supposed to be for, that is:

>E.g.:
>- lexicals
>- PMC/class types
>- object attributes
>- constant string table
>- ...

I'd just pitch an exception if code deletes an entry or adds one with
no string key. Or if you're going to make it work maybe it'd be worth
renaming the current PMC class into something else and creating a new
class. (Assuming the changes would slow down or add complexity to the
current class, since we'd really like it fast and simple enough to be
reasonably auditable)
--
Dan

--------------------------------------it's like this-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk

Reply all
Reply to author
Forward
0 new messages