Mercurial > repo
view src/ploki/hash.c @ 6394:a4fca7594a0e
<FireFly> le/rn Bride theory/Bride theory is a theory involving a headhunter who dresses in yellow
author | HackBot |
---|---|
date | Thu, 17 Dec 2015 02:10:11 +0000 |
parents | ac0403686959 |
children |
line wrap: on
line source
#include "config.h" #include "hash.h" #include "main.h" #include "main_opt.h" #include "random.h" #include "xmalloc.h" #include <errno.h> #include <stddef.h> #include <stdio.h> #include <assert.h> struct h_entry { size_t hash; void *key; void *value; }; struct h_node { struct h_entry entry; struct h_node *next; }; enum {MAGIC = 112}; void h_init( Hash *h, size_t (*hash)(const void *, size_t), int (*cmp)(const void *, const void *), void (*delk)(void *), void (*delv)(void *) ) { size_t i; h->entries = 0; h->brk = -1; h->iter = -1; h->iterptr = NULL; h->seed = randval() * (size_t)-1; h->delk = delk; h->delv = delv; assert(hash != NULL); h->hash = hash; assert(cmp != NULL); h->cmp = cmp; h->table = xmalloc(h->newsize = h->size = MAGIC, sizeof *h->table); for (i = 0; i < h->size; ++i) { h->table[i] = NULL; } } #define DELKV(p) \ do { \ if (h->delk) { \ h->delk((p)->entry.key); \ } \ if (h->delv) { \ h->delv((p)->entry.value); \ } \ } while (0) void h_end(Hash *h) { size_t size, b; if (!h->table) return; for (b = 0, size = h->newsize; h->newsize; h->newsize--) { struct h_node *p; if ((p = h->table[h->newsize - 1])) { ++b; for (; p; p = h->table[h->newsize - 1]) { h->table[h->newsize - 1] = p->next; DELKV(p); xfree(p); } } } xfree(h->table); h->table = NULL; if (Opt.debug & DBG_HASH) { fprintf(stderr, "%s: hash[%lu/%lu/%lu]\n", Prog, (unsigned long)h->entries, (unsigned long)b, (unsigned long)size); } } ATTR_PURE static size_t xclip(const Hash *h, const size_t hash_unc) { size_t hash; hash = hash_unc % h->size; if (hash > h->brk) { hash = hash_unc % h->newsize; } return hash; } #if 0 ATTR_PURE static size_t xhash(const Hash *h, const void *key) { return xclip(h, h->hash(key, h->seed)); } #endif #define XRESIZN(h) ((h)->brk + 1u) #define XSTEP(h) do { if (XRESIZN(h)) xstep(h); } while (0) static void xstep(Hash *h) { struct h_node *rev = NULL; struct h_node *p; struct h_node *tmp; assert(h->table != NULL); for (p = h->table[h->brk]; p; p = tmp) { tmp = p->next; p->next = rev; rev = p; } h->table[h->brk--] = NULL; if (!XRESIZN(h)) { h->size = h->newsize; } for (p = rev; p; p = tmp) { const size_t i = xclip(h, p->entry.hash); tmp = p->next; p->next = h->table[i]; h->table[i] = p; } } static void xincentries(Hash *h) { h->entries++; if (!(XRESIZN(h)) && h->entries / h->size > 3u) { size_t i; h->table = xrealloc(h->table, h->newsize = h->size * 2u + 1u); for (i = h->size; i < h->newsize; ++i) { h->table[i] = NULL; } h->brk = h->size - 1u; xstep(h); } } int h_get(Hash *h, const void *key, void **res) { XSTEP(h); { const size_t hash_unc = h->hash(key, h->seed); const size_t hash = xclip(h, hash_unc); struct h_node *p; for (p = h->table[hash]; p; p = p->next) { if (hash_unc == p->entry.hash && h->cmp(p->entry.key, key) == 0) { if (res) { *res = p->entry.value; } return H_OK; } } } return H_NOENT; } int h_del(Hash *h, const void *key) { XSTEP(h); { const size_t hash_unc = h->hash(key, h->seed); const size_t hash = xclip(h, hash_unc); struct h_node **p; for (p = &h->table[hash]; *p; p = &(*p)->next) { if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) { struct h_node *tmp = *p; *p = (*p)->next; DELKV(tmp); xfree(tmp); h->entries--; return H_OK; } } } return H_NOENT; } #if 0 void h_push(Hash *h, void *key, void *val) { XSTEP(h); { const size_t hash_unc = h->hash(key, h->seed); const size_t hash = xclip(h, hash_unc); struct h_node *p; p = xmalloc(1, sizeof *p); p->entry.hash = hash_unc; p->entry.key = key; p->entry.value = val; p->next = h->table[hash]; h->table[hash] = p; xincentries(h); } } #endif int h_put(Hash *h, void *key, void *val, int replace) { XSTEP(h); { const size_t hash_unc = h->hash(key, h->seed); const size_t hash = xclip(h, hash_unc); struct h_node **p; for (p = &h->table[hash]; *p; p = &(*p)->next) { if (hash_unc == (*p)->entry.hash && h->cmp((*p)->entry.key, key) == 0) { if (replace) { DELKV(*p); (*p)->entry.key = key; (*p)->entry.value = val; return H_OK; } else { return H_EXIST; } } } *p = xmalloc(1, sizeof **p); (*p)->entry.hash = hash_unc; (*p)->entry.key = key; (*p)->entry.value = val; (*p)->next = NULL; xincentries(h); } return H_OK; } void h_reset(Hash *h) { h->iter = -1; h->iterptr = NULL; } int h_nextkv(Hash *h, void **k, void **v) { if (h->iterptr) { *k = h->iterptr->entry.key; *v = h->iterptr->entry.value; h->iterptr = h->iterptr->next; return H_OK; } for (h->iter++; h->iter < h->newsize; h->iter++) { if ((h->iterptr = h->table[h->iter])) { *k = h->iterptr->entry.key; *v = h->iterptr->entry.value; h->iterptr = h->iterptr->next; return H_OK; } } h->iter = -1; return H_NOENT; } #if 0 size_t (h_entries)(const Hash *h) { return h_entries(h); } #endif