144 lines
3.1 KiB
C
144 lines
3.1 KiB
C
#pragma once
|
|
/// Hash table for mapping string keys to indexes for another array
|
|
|
|
#include "qsort.h" /*macro qsort implementation*/
|
|
|
|
#include <stdint.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
typedef struct {
|
|
size_t size;
|
|
char ** keys;
|
|
uint64_t * hashes;
|
|
uint64_t * indexes;
|
|
} hashtab_t;
|
|
|
|
#define HASHTAB_INIT {\
|
|
.size = 0,\
|
|
.keys = NULL,\
|
|
.hashes = NULL,\
|
|
.indexes = NULL\
|
|
}
|
|
|
|
static inline void hashtab_free(hashtab_t *ht) {
|
|
|
|
for (size_t k=0; k < ht->size; k++) {
|
|
free( ht->keys[k] );
|
|
}
|
|
|
|
free( ht->keys );
|
|
free( ht->hashes );
|
|
free( ht->indexes );
|
|
}
|
|
|
|
static inline char *hashtab_strdup_len(const char *key, size_t key_len) {
|
|
|
|
char *key2 = malloc( key_len + 1 );
|
|
if ( key2 == NULL ) return NULL;
|
|
|
|
memcpy(key2, key, key_len);
|
|
key2[key_len] = 0;
|
|
|
|
return key2;
|
|
}
|
|
|
|
static inline char *hashtab_strdup(const char *key) {
|
|
|
|
size_t key_len = 0;
|
|
for (; key[key_len] != '\0'; key_len++);
|
|
|
|
return hashtab_strdup_len(key, key_len);
|
|
}
|
|
|
|
uint64_t hashtab_fnvhash(const char *s, size_t slen) {
|
|
|
|
static const uint64_t prime = 0x100000001B3;
|
|
uint64_t result = 0xcbf29ce484222325;
|
|
|
|
for (size_t k = 0; k < slen; k++)
|
|
result = (result * prime) ^ s[k];
|
|
|
|
return result;
|
|
}
|
|
|
|
static inline int hashtab_add(hashtab_t *ht, const char *key, uint64_t idx) {
|
|
|
|
char * key2 = hashtab_strdup(key);
|
|
if ( key2 == NULL ) return 0;
|
|
|
|
ht->keys = realloc(ht->keys, (1 + ht->size) * sizeof(char*));
|
|
if ( ht->keys == NULL ) {
|
|
free( key2 );
|
|
return 0;
|
|
}
|
|
ht->keys[ht->size] = key2;
|
|
|
|
ht->hashes = realloc(ht->hashes, (1 + ht->size) * sizeof(*ht->hashes));
|
|
if ( ht->hashes == NULL ) return 0;
|
|
ht->hashes[ht->size] = hashtab_fnvhash(key, strlen(key));
|
|
|
|
ht->indexes = realloc(ht->indexes, (1 + ht->size) * sizeof(*ht->indexes));
|
|
if ( ht->indexes == NULL ) return 0;
|
|
ht->indexes[ht->size] = idx;
|
|
ht->size++;
|
|
|
|
#define HASHTAB_CMP_LT(N, M) (ht->hashes[N] < ht->hashes[M])
|
|
|
|
uint64_t tmp_hash;
|
|
uint64_t tmp_idx;
|
|
char * tmp_key;
|
|
|
|
#define HASHTAB_SWAP(N, M) (\
|
|
tmp_hash = ht->hashes[N],\
|
|
tmp_idx = ht->indexes[N],\
|
|
tmp_key = ht->keys[N],\
|
|
ht->hashes[N] = ht->hashes[M],\
|
|
ht->indexes[N] = ht->indexes[M],\
|
|
ht->keys[N] = ht->keys[M],\
|
|
ht->hashes[M] = tmp_hash,\
|
|
ht->indexes[M] = tmp_idx,\
|
|
ht->keys[M] = tmp_key\
|
|
)
|
|
|
|
QSORT(ht->size, HASHTAB_CMP_LT, HASHTAB_SWAP);
|
|
|
|
return 1;
|
|
}
|
|
|
|
static inline size_t hashtab_bsrch(const hashtab_t *ht, uint64_t hash) {
|
|
|
|
size_t l = 0, r = ht->size - 1;
|
|
|
|
if ( ht->size == 0 ) goto NOT_FOUND;
|
|
|
|
while ( l <= r ) {
|
|
|
|
size_t m = (l + r) >> 1;
|
|
|
|
if ( ht->hashes[m] < hash ) {
|
|
|
|
l = m + 1;
|
|
|
|
} else if ( ht->hashes[m] > hash ) {
|
|
|
|
if ( m == 0 ) goto NOT_FOUND;
|
|
r = m - 1;
|
|
|
|
} else {
|
|
|
|
return m;
|
|
}
|
|
}
|
|
|
|
NOT_FOUND:
|
|
return SIZE_MAX;
|
|
}
|
|
|
|
static inline uint64_t hashtab_find(const hashtab_t *ht, const char *key) {
|
|
|
|
uint64_t hash = hashtab_fnvhash(key, strlen(key));
|
|
size_t n = hashtab_bsrch(ht, hash);
|
|
if ( n == SIZE_MAX ) return UINT64_MAX;
|
|
return ht->indexes[n];
|
|
}
|