123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152 |
- #pragma once
- #include <string.h> /* memcpy */
- #include <stddef.h> /* size_t */
- /* simplest possible insert-only single-linked hash table */
- typedef void *(*AHashAllocFunc)(void *alloc_param, size_t size);
- typedef unsigned long (*AHashKeyHashFunc)(const void *key);
- typedef int (*AHashKeyCompareFunc)(const void *left, const void *right);
- struct AHashBucket_;
- typedef struct {
- /* must be set before aHashInit */
- long nbuckets;
- /* note-to-self: it is actually trivially possible to have variable-size keys and items */
- long key_size;
- long value_size;
- /* must return properly aligned (e.g. 16) regions */
- void *alloc_param;
- AHashAllocFunc alloc;
- AHashKeyHashFunc key_hash;
- AHashKeyCompareFunc key_compare;
- struct {
- long item_size;
- long value_offset;
- long next_ptr_offset;
- struct AHashBucket_ *buckets;
- } impl_;
- struct {
- long items;
- long empty_buckets;
- long worst_bucket_items;
- } stat;
- } AHash;
- void aHashInit(AHash *hash);
- void *aHashInsert(AHash *hash, const void *key, const void *value);
- void *aHashGet(const AHash *hash, const void *key);
- /* helper for hashing memory contents, e.g. strings and binary data
- * DON'T use it to hash structs, as those might have holes due to alignment,
- * and actual memory contents of these holes is not specified (UB?) */
- unsigned long aHashBytesHash(const void *data, size_t size);
- /* can be directly used if key is a zero-terminated string */
- unsigned long aHashStringHash(const void *string);
- #define AHASH_IMPLEMENT
- #ifdef AHASH_IMPLEMENT
- #ifndef AHASH_VALUE_ALIGNMENT
- #define AHASH_VALUE_ALIGNMENT 16 /* worst case for SSE & friends */
- #endif
- struct AHashBucket_ {
- void *items;
- long count;
- };
- struct AHashItemData_ {
- void *key;
- void *value;
- void **next;
- };
- static struct AHashItemData_ a__hashGetItemData(const AHash *hash, void *item) {
- char *bytes = item;
- return (struct AHashItemData_){
- .key = bytes,
- .value = bytes + hash->impl_.value_offset,
- .next = (void**)(bytes + hash->impl_.next_ptr_offset)
- };
- }
- void aHashInit(AHash *hash) {
- #define AHASH_ALIGNED_SIZE(S,A) (((S+A-1)/A)*A)
- hash->impl_.value_offset = AHASH_ALIGNED_SIZE(hash->key_size, AHASH_VALUE_ALIGNMENT);
- hash->impl_.next_ptr_offset = hash->impl_.value_offset + AHASH_ALIGNED_SIZE(hash->value_size, sizeof(void*));
- hash->impl_.item_size = hash->impl_.next_ptr_offset + sizeof(void*);
- hash->impl_.buckets = hash->alloc(hash->alloc_param, sizeof(struct AHashBucket_) * hash->nbuckets);
- for (long i = 0; i < hash->nbuckets; ++i)
- hash->impl_.buckets[i] = (struct AHashBucket_){
- .items = 0,
- .count = 0
- };
- hash->stat.items = 0;
- hash->stat.empty_buckets = hash->nbuckets;
- hash->stat.worst_bucket_items = 0;
- }
- void *aHashInsert(AHash *hash, const void *key, const void *value) {
- const long index = hash->key_hash(key) % hash->nbuckets;
- struct AHashBucket_ *const bucket = hash->impl_.buckets + index;
- void *item = bucket->items;
- struct AHashItemData_ prev_item_data;
- prev_item_data.next = &bucket->items;
- while(item != 0) {
- prev_item_data = a__hashGetItemData(hash, item);
- item = *prev_item_data.next;
- }
- void *const new_item = hash->alloc(hash->alloc_param, hash->impl_.item_size);
- const struct AHashItemData_ item_data = a__hashGetItemData(hash, new_item);
- // FIXME key is string and is < key_size most of the time
- memcpy(item_data.key, key, hash->key_size);
- memcpy(item_data.value, value, hash->value_size);
- item_data.next[0] = 0;
- *prev_item_data.next = new_item;
- if (!bucket->count) hash->stat.empty_buckets--;
- ++bucket->count;
- if (bucket->count > hash->stat.worst_bucket_items) hash->stat.worst_bucket_items = bucket->count;
- ++hash->stat.items;
- return new_item;
- }
- void *aHashGet(const AHash *hash, const void *key) {
- const long index = hash->key_hash(key) % hash->nbuckets;
- const struct AHashBucket_ *const bucket = hash->impl_.buckets + index;
- void *item = bucket->items;
- while (item) {
- const struct AHashItemData_ data = a__hashGetItemData(hash, item);
- if (0 == hash->key_compare(key, data.key))
- return data.value;
- item = *data.next;
- }
- return 0;
- }
- /* FNV-1a */
- unsigned long aHashBytesHash(const void *data, size_t size) {
- #if __LP64__
- unsigned long hash = 0xcbf29ce484222325ul;
- const unsigned long mul = 1099511628211ul;
- #else
- unsigned long hash = 0x811c9dc5ul;
- const unsigned long mul = 16777619ul;
- #endif
- for (size_t i = 0; i < size; ++i) {
- hash ^= ((const unsigned char*)data)[i];
- hash *= mul;
- }
- return hash;
- }
- unsigned long aHashStringHash(const void *string) {
- return aHashBytesHash(string, strlen(string));
- }
- #endif
|