diff options
Diffstat (limited to 'source/blender/blenlib/BLI_smallhash.h')
-rwxr-xr-x | source/blender/blenlib/BLI_smallhash.h | 225 |
1 files changed, 25 insertions, 200 deletions
diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h index 2fafda9b2b8..c956b8c63ea 100755 --- a/source/blender/blenlib/BLI_smallhash.h +++ b/source/blender/blenlib/BLI_smallhash.h @@ -28,221 +28,46 @@ #ifndef BLI_SMALLHASH_H #define BLI_SMALLHASH_H -/*******a light stack-friendly hash library****** - * (it uses stack space for smallish hash tables) */ +/** \file BLI_smallhash.h + * \ingroup bli + */ -/*based on a doubling non-chaining approach */ +/* a light stack-friendly hash library, + * (it uses stack space for smallish hash tables) */ -#include "MEM_guardedalloc.h" -#include "BLO_sys_types.h" -#include "BLI_utildefines.h" -#include <string.h> +/* based on a doubling non-chaining approach */ -extern unsigned int hashsizes[]; -#define NONHASH -25436536 -typedef struct entry {uintptr_t key; void *val;} entry; +typedef struct { + uintptr_t key; + void *val; +} SmallHashEntry; /*how much stack space to use before dynamically allocating memory*/ #define SMSTACKSIZE 521 typedef struct SmallHash { - entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE]; - entry *stacktable, *copytable; + SmallHashEntry *table; + SmallHashEntry _stacktable[SMSTACKSIZE]; + SmallHashEntry _copytable[SMSTACKSIZE]; + SmallHashEntry *stacktable, *copytable; int used; int curhash; int size; } SmallHash; -typedef struct SmallHashIter { +typedef struct { SmallHash *hash; int i; } SmallHashIter; -/*CELL_UNUSED means this cell is inside a key series, while CELL_FREE - means this cell terminates a key series. - - no chance of anyone shoving INT32_MAX-2 into a *val pointer, I - imagine. hopefully. */ -#define CELL_UNUSED ((void*)0x7FFFFFFF) -#define CELL_FREE ((void*)0x7FFFFFFD) - -#define NONZERO(n) ((n) + !(n)) -#define HASHNEXT(h, hoff) ABS(((h) + ((hoff=NONZERO(hoff*2)+1), hoff))) - -BM_INLINE void BLI_smallhash_init(SmallHash *hash) -{ - int i; - - memset(hash, 0, sizeof(*hash)); - - hash->table = hash->_stacktable; - hash->curhash = 2; - hash->size = hashsizes[hash->curhash]; - - hash->copytable = hash->_copytable; - hash->stacktable = hash->_stacktable; - - for (i=0; i<hash->size; i++) { - hash->table[i].val = CELL_FREE; - } -} - -/*NOTE: does *not* free *hash itself! only the direct data!*/ -BM_INLINE void BLI_smallhash_release(SmallHash *hash) -{ - if (!hash) - return; - - if (hash->table != hash->stacktable) - MEM_freeN(hash->table); -} - -BM_INLINE void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item) -{ - int h, hoff=1; - - if (hash->size < hash->used*3) { - int newsize = hashsizes[++hash->curhash]; - entry *tmp; - int i = 0; - - if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) { - tmp = MEM_callocN(sizeof(*hash->table)*newsize, "new hashkeys"); - } else { - SWAP(entry*, hash->stacktable, hash->copytable); - tmp = hash->stacktable; - } - - SWAP(entry*, tmp, hash->table); - - hash->size = newsize; - - for (i=0; i<hash->size; i++) { - hash->table[i].val = CELL_FREE; - } - - for (i=0; i<hashsizes[hash->curhash-1]; i++) { - if (ELEM(tmp[i].val, CELL_UNUSED, CELL_FREE)) - continue; - - h = ABS((int)(tmp[i].key)); - hoff = 1; - while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE)) - h = HASHNEXT(h, hoff); - - h %= newsize; - - hash->table[h].key = tmp[i].key; - hash->table[h].val = tmp[i].val; - } - - if (tmp != hash->stacktable && tmp != hash->copytable) { - MEM_freeN(tmp); - } - } - - h = ABS((int)key); - hoff = 1; - while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE)) - h = HASHNEXT(h, hoff); - - h %= hash->size; - hash->table[h].key = key; - hash->table[h].val = item; - - hash->used++; -} - -BM_INLINE void BLI_smallhash_remove(SmallHash *hash, uintptr_t key) -{ - int h, hoff=1; - - h = ABS((int)key); - - while (hash->table[h % hash->size].key != key - || hash->table[h % hash->size].val == CELL_UNUSED) - { - if (hash->table[h % hash->size].val == CELL_FREE) - return; - h = HASHNEXT(h, hoff); - } - - h %= hash->size; - hash->table[h].key = 0; - hash->table[h].val = CELL_UNUSED; -} - -BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key) -{ - int h, hoff=1; - void *v; - - h = ABS((int)key); - - if (!hash->table) - return NULL; - - while (hash->table[h % hash->size].key != key - || hash->table[h % hash->size].val == CELL_UNUSED) - { - if (hash->table[h % hash->size].val == CELL_FREE) - return NULL; - h = HASHNEXT(h, hoff); - } - - v = hash->table[h % hash->size].val; - if (ELEM(v, CELL_UNUSED, CELL_FREE)) - return NULL; - return v; -} - - -BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key) -{ - int h = ABS((int)key); - int hoff =1; - - if (!hash->table) - return 0; - - while (hash->table[h % hash->size].key != key - || hash->table[h % hash->size].val == CELL_UNUSED) - { - if (hash->table[h % hash->size].val == CELL_FREE) - return 0; - h = HASHNEXT(h, hoff); - } - - return !ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE); -} - -BM_INLINE int BLI_smallhash_count(SmallHash *hash) -{ - return hash->used; -} - -BM_INLINE void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) -{ - while (iter->i < iter->hash->size) { - if (iter->hash->table[iter->i].val != CELL_UNUSED && iter->hash->table[iter->i].val != CELL_FREE) { - if (key) - *key = iter->hash->table[iter->i].key; - - iter->i++; - return iter->hash->table[iter->i-1].val; - } - - iter->i++; - } - - return NULL; -} - -BM_INLINE void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key) -{ - iter->hash = hash; - iter->i = 0; - - return BLI_smallhash_iternext(iter, key); -} +void BLI_smallhash_init(SmallHash *hash); +void BLI_smallhash_release(SmallHash *hash); +void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item); +void BLI_smallhash_remove(SmallHash *hash, uintptr_t key); +void * BLI_smallhash_lookup(SmallHash *hash, uintptr_t key); +int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key); +int BLI_smallhash_count(SmallHash *hash); +void * BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key); +void * BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key); +/* void BLI_smallhash_print(SmallHash *hash); */ /* UNUSED */ #endif // BLI_SMALLHASH_H |