|parrotcode: Hash table|
|Contents | C|
src/hash.c - Hash table
A hashtable contains an array of bucket indexes.
Buckets are nodes in a linked list,
each containing a
void * key and value.
During hash creation,
the types of key and value as well as appropriate compare and hashing functions can be set.
This hash implementation uses just one piece of malloced memory.
hash->bs bucket store points to this region.
This hash doesn't move during GC, therefore a lot of the old caveats don't apply.
static size_t key_hash_STRING
value. See also string.c.
static int STRING_compare
static int pointer_compare
static size_t key_hash_pointer
static size_t key_hash_cstring
static int cstring_compare
static void hash_thaw
pinfois the visit info, (see include/parrot/pmc_freeze.h>).
static void hash_freeze
static void expand_hash
MAXFULL_PERCENT% of N as the number of buckets. This way, as soon as we run out of buckets on the free list, we know that it's time to resize the hashtable.
bucket_index = hash(key) % parrot_hash_size
parrot_hash_size). In fact, because the hashtable is always a power of two in size, it depends only on the next bit in the hash value, after the ones previously used.
->nextpointers, and they'll be all over memory.)
static void init_hash
Hash*is seen, it doesn't get properly marked (only the
Hash*buffer is marked, not its contents). By passing the
**hptrup to the Hash's init function, the newly constructed PMC is on the stack including this newly constructed Hash, so that it gets marked properly.
containerPMC gets stored in the Hash end the newly created Hash is in PMC_struct_val(container).
NULLif no bucket is found.
keyis not copied.