Eep, seems I hit send...
On Thursday, 10 January 2013 at 05:47:01 UTC, H. S. Teoh wrote:
The basic idea behind static AA literals is to use CTFE to
compute the hashes of the keys, and therefore which slot(s)
they will fall in, at compile time. Armed with this
information, we can create an array of slots at compile-time
that contains the AA entries by declaring each slot as a static
variable and using the slot assignment information to
initialize the hash table (array of pointers to slots) to point
to these slots.
Hmmm somehow that doesn't seem like a good idea; I mean it will
work....
Alternative is to sorta have a pair of static arrays, then
either use a balanced tree, or a modulus to best hold (and
separate) the values.
Modulus based: It could be like...
//T obviously replace with appropriate type
ref T AA_lookup(name publicName)(uint hash) {
//offset for part1
//could be external to..
immutable static int offsets[]; //no need for pointers,
right?
immutable static T values[]; //contains actual item data
enum mod; //divider for table.
uint result = hash % mod;
//or branch to return empty? But can't be ref then...
assert(offsets[result] != -1);
return values[offsets[result]];
}
Then your CTFE increases the mod in it's calculations until
every element can fit only once, and make the offsets based on
them. Default values would be -1 (range error if called), course
if it's mod is rather large and wastes a lot of space then
perhaps it falls back on the tree structure (in those cases, > 3x
of array size)
Tree: I don't mind a minor performance hit, log(n) is a very
small hit in my mind. In that case a statically created tree is
rather easy. AA's created ahead of time are likely rather small
(<1 Million elements). So a tree structure of:
struct Node(T) {
//pointers don't seem like they are needed;
//Can even be ushorts or ubytes if small enough.
uint left, right;
T* value;
}
You get the idea.
