NAME ^

src/hash.c - Hash table

DESCRIPTION ^

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. The 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.

Functions ^

*/

#include "parrot/parrot.h" #include <assert.h>

#define INITIAL_BUCKETS 16

#define N_BUCKETS(n) ((n) - (n)/4) #define HASH_ALLOC_SIZE(n) (N_BUCKETS(n) * sizeof (HashBucket) + \ (n) * sizeof (HashBucket *))

/* HEADER: include/parrot/hash.h */

/*

FUNCDOC: Return the hashed value of the key value.

see also string.c

*/

static size_t key_hash_STRING(Interp *interp, STRING *value, size_t seed) { STRING * const s = value;

    if (s->hashval) {
        return s->hashval;
    }

    return string_hash(interp, s, seed);
}

/*

FUNCDOC: Compares the two strings, returning 0 if they are identical.

*/

static int STRING_compare(Parrot_Interp interp, const void *search_key, const void *bucket_key) { return string_equal(interp, (const STRING *)search_key, (const STRING *)bucket_key); }

/*

FUNCDOC: Compares the two pointers, returning 0 if they are identical

*/

static int pointer_compare(Parrot_Interp interp, const void * const a, const void * const b) { return a != b; }

/*

FUNCDOC: Returns a hashvalue for a pointer.

*/

static size_t key_hash_pointer(Interp *interp, void *value, size_t seed) { return ((size_t) value) ^ seed; }

static size_t key_hash_cstring(Interp *interp, const void *value /*NN*/, size_t seed) { register size_t h = seed; const unsigned char * p = (const unsigned char *) value; while (*p) { h += h << 5; h += *p++; } return h; }

/*

FUNCDOC: C string versions of the key_hash and compare functions.

*/

static int cstring_compare(Parrot_Interp interp, const char *a /*NN*/, const char *b /*NN*/) { UNUSED(interp); return strcmp(a, b); }

/*

FUNCDOC: Custom key_hash function.

*/

static size_t key_hash_int(Interp *interp, void *value, size_t seed) { UNUSED(interp); return (size_t)value ^ seed; }

/*

FUNCDOC: Custom compare function.

*/

/*

FUNCDOC: Custom compare function.

*/

static int int_compare(Parrot_Interp interp, const void *a, const void *b) { UNUSED(interp); return a != b; }

/*

FUNCDOC: Print out the hash in human-readable form. Except it's empty.

SEE ALSO ^

docs/pdds/pdd08_keys.pod.

HISTORY ^

TODO ^

Future optimizations:


 parrot