AArray

An associative array implementation which grows by powers of two. Relies on the GC for memory. Does not handle hash collisions. Note: This code is a reference for understanding how hash maps work. It's not meant to be used in DIL. A fast version needs to be implemented which uses dil.Array for custom allocation.

struct AArray {

AANode*[] buckets;

size_t count;

size_t len();

size_t blen();

size_t toindex(Key key);

Value get(Key key);

void set(Key key, Value value);

void add(Key key, Value value);

AANode* getadd(Key key);

bool remove(Key key);

AANode* find(Key key);

void rehash();

static char[] toHex(size_t x);

static cstring keyPrinter(Key k);

static cstring valuePrinter(Value v);

char[] print(cstring function(Key) printKey = &keyPrinter, cstring function(Value) printValue = &valuePrinter);

}

Members

Functions

add void add(Key key, Value value): Adds a pair to the array, assuming it doesn't exist already.
blen size_t blen(): Returns the number of buckets.
find AANode* find(Key key): Finds the node matching the key.
get Value get(Key key): Returns the value of a key, or null if it doesn't exist.
getadd AANode* getadd(Key key): Finds a node by key or adds a new one if inexistent. Useful when the AA is on the lhs, e.g.: aa["b"] = 1;
len size_t len(): Returns the number of nodes.
print char[] print(cstring function(Key) printKey = &keyPrinter, cstring function(Value) printValue = &valuePrinter): Prints the contents of this array. Supply own functions for customization.
rehash void rehash(): Allocates a new bucket list and relocates the nodes from the old one.
remove bool remove(Key key): Removes a key value pair from the array.
set void set(Key key, Value value): Sets the value of a key.
toindex size_t toindex(Key key): Returns the index of a key in the buckets array.

Static functions

keyPrinter cstring keyPrinter(Key k): Prints as hex by default.
toHex char[] toHex(size_t x): Formats a number as a string with hexadecimal characters.
valuePrinter cstring valuePrinter(Value v): Prints as hex by default.

Variables

buckets AANode*[] buckets;: The number of buckets is a power of 2.
count size_t count;: Number of nodes.

AArray

Members

Functions

Static functions

Variables

Meta

Source