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"

#define INITIAL_BUCKETS 16

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

/* HEADERIZER HFILE: include/parrot/hash.h */

/* HEADERIZER BEGIN: static */

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static int cstring_compare( SHIM_INTERP, NOTNULL(const char *a), NOTNULL(const char *b) ) __attribute__nonnull__(2) __attribute__nonnull__(3);

static void expand_hash( PARROT_INTERP, NOTNULL(Hash *hash) ) __attribute__nonnull__(1) __attribute__nonnull__(2);

static void hash_freeze( PARROT_INTERP, NOTNULL(const Hash * const hash), NOTNULL(visit_info* info) ) __attribute__nonnull__(1) __attribute__nonnull__(2) __attribute__nonnull__(3);

static void hash_thaw( PARROT_INTERP, NOTNULL(Hash *hash), NOTNULL(visit_info* info) ) __attribute__nonnull__(1) __attribute__nonnull__(2) __attribute__nonnull__(3);

static void init_hash( NOTNULL(Hash *hash), PARROT_DATA_TYPE val_type, Hash_key_type hkey_type, hash_comp_fn compare, hash_hash_key_fn keyhash ) __attribute__nonnull__(1);

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static int int_compare( SHIM_INTERP, NULLOK(const void *a), NULLOK(const void *b) );

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static size_t key_hash_cstring( SHIM_INTERP, NOTNULL(const void *value), size_t seed ) __attribute__nonnull__(2);

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static size_t key_hash_int( SHIM_INTERP, NULLOK(void *value), size_t seed );

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static size_t key_hash_pointer( SHIM_INTERP, NULLOK(void *value), size_t seed );

PARROT_WARN_UNUSED_RESULT static size_t key_hash_STRING( PARROT_INTERP, NOTNULL(STRING *value), size_t seed ) __attribute__nonnull__(1) __attribute__nonnull__(2);

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static int pointer_compare( SHIM_INTERP, NULLOK(const void *a), NULLOK(const void *b) );

PARROT_WARN_UNUSED_RESULT static int STRING_compare( PARROT_INTERP, NOTNULL(const void *search_key), NOTNULL(const void *bucket_key) ) __attribute__nonnull__(1) __attribute__nonnull__(2) __attribute__nonnull__(3);

/* HEADERIZER END: static */

/*

FUNCDOC: key_hash_STRING Return the hashed value of the key value. See also string.c.

*/

PARROT_WARN_UNUSED_RESULT static size_t key_hash_STRING(PARROT_INTERP, NOTNULL(STRING *value), size_t seed) { STRING * const s = value;

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

    return string_hash(interp, s, seed);
}

/*

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

*/

PARROT_WARN_UNUSED_RESULT static int STRING_compare(PARROT_INTERP, NOTNULL(const void *search_key), NOTNULL(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

*/

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static int pointer_compare(SHIM_INTERP, NULLOK(const void *a), NULLOK(const void *b)) { return a != b; }

/*

FUNCDOC: key_hash_pointer Returns a hashvalue for a pointer.

*/

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static size_t key_hash_pointer(SHIM_INTERP, NULLOK(void *value), size_t seed) { return ((size_t) value) ^ seed; }

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static size_t key_hash_cstring(SHIM_INTERP, NOTNULL(const void *value), 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: cstring_compare C string versions of the key_hash and compare functions.

*/

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static int cstring_compare(SHIM_INTERP, NOTNULL(const char *a), NOTNULL(const char *b)) { return strcmp(a, b); }

/*

FUNCDOC: key_hash_int Custom key_hash function.

*/

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static size_t key_hash_int(SHIM_INTERP, NULLOK(void *value), size_t seed) { return (size_t)value ^ seed; }

/*

FUNCDOC: int_compare Custom compare function.

*/

PARROT_WARN_UNUSED_RESULT PARROT_PURE_FUNCTION static int int_compare(SHIM_INTERP, NULLOK(const void *a), NULLOK(const void *b)) { return a != b; }

/*

FUNCDOC: parrot_dump_hash

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

SEE ALSO ^

docs/pdds/pdd08_keys.pod.

TODO ^

Future optimizations:


 parrot