diff options
author | Campbell Barton <ideasman42@gmail.com> | 2014-02-02 09:22:05 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2014-02-02 09:24:33 +0400 |
commit | dcd90d67c8a6e6beae37fc02515b8c75942332ca (patch) | |
tree | f5503ebfd9e07d689d3c806aa5445592b204f047 /source/blender | |
parent | 7c9b1065895e0a6a12555075980d7a77d1dea8c7 (diff) |
Smallhash: fixes/improvements
- use magic numbers based on uintptr max, not uint max, to avoid possible collisions with real pointer values on 64bit systems.
- comment BLI_smallhash_remove for now, its not used.
- added smallhash_val_is_used replacing ELEM() checks
- updated docs
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/intern/smallhash.c | 57 |
1 files changed, 38 insertions, 19 deletions
diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c index fa953f0e44d..be5f70c7f49 100644 --- a/source/blender/blenlib/intern/smallhash.c +++ b/source/blender/blenlib/intern/smallhash.c @@ -31,7 +31,21 @@ * A light stack-friendly hash library, it uses stack space for smallish hash tables * but falls back to heap memory once the stack limits reached. * - * based on a doubling non-chaining approach + * based on a doubling non-chaining approach which uses more buckets then entries + * stepping over buckets when two keys share the same hash so any key can find a free bucket. + * + * + * #SmallHashEntry.key + * - ``SMHASH_KEY_UNUSED`` means the key in the cell has not been initialized. + * + * #SmallHashEntry.val + * - ``SMHASH_CELL_UNUSED`` means this cell is inside a key series. + * - ``SMHASH_CELL_FREE`` means this cell terminates a key series. + * + * Note that the values and keys are often pointers or index values, + * use the maximum values to avoid real pointers colliding with magic numbers. + * + * \note these have the SMHASH prefix because we may want to make them public. */ #include <string.h> @@ -46,17 +60,9 @@ #include "BLI_strict_flags.h" -/* SMHASH_CELL_UNUSED means this cell is inside a key series, - * while SMHASH_CELL_FREE means this cell terminates a key series. - * - * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I - * imagine. hopefully. - * - * note: these have the SMHASH prefix because we may want to make them public. - */ -#define SMHASH_CELL_UNUSED ((void *)0x7FFFFFFF) -#define SMHASH_CELL_FREE ((void *)0x7FFFFFFD) -#define SMHASH_KEY_UNUSED ((uintptr_t)-1) +#define SMHASH_KEY_UNUSED ((uintptr_t)(UINTPTR_MAX - 0)) +#define SMHASH_CELL_FREE ((void *) (UINTPTR_MAX - 1)) +#define SMHASH_CELL_UNUSED ((void *) (UINTPTR_MAX - 2)) /* typically this re-assigns 'h' */ #define SMHASH_NEXT(h, hoff) ( \ @@ -65,6 +71,19 @@ ((h) + (((hoff) = ((hoff) * 2) + 1), (hoff))) \ ) + +/* nothing uses BLI_smallhash_remove yet */ +// #define USE_REMOVE + +BLI_INLINE bool smallhash_val_is_used(const void *val) +{ +#ifdef USE_REMOVE + return !ELEM(val, SMHASH_CELL_FREE, SMHASH_CELL_UNUSED); +#else + return (val != SMHASH_CELL_FREE); +#endif +} + extern const unsigned int hashsizes[]; /** @@ -117,7 +136,7 @@ BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uint unsigned int hoff = 1; for (e = &sh->buckets[h % sh->nbuckets]; - !ELEM(e->val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE); + smallhash_val_is_used(e->val); h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) { /* pass */ @@ -150,7 +169,7 @@ BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuck smallhash_init_empty(sh); for (i = 0; i < nbuckets_old; i++) { - if (!ELEM(buckets_old[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) { + if (smallhash_val_is_used(buckets_old[i].val)) { SmallHashEntry *e = smallhash_lookup_first_free(sh, buckets_old[i].key); e->key = buckets_old[i].key; e->val = buckets_old[i].val; @@ -170,7 +189,7 @@ void BLI_smallhash_init(SmallHash *sh) sh->cursize = 2; sh->nbuckets = hashsizes[sh->cursize]; - sh->buckets = sh->buckets_stack; + sh->buckets = sh->buckets_stack; smallhash_init_empty(sh); } @@ -188,7 +207,7 @@ void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val) SmallHashEntry *e; BLI_assert(key != SMHASH_KEY_UNUSED); - BLI_assert(!ELEM(val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)); + BLI_assert(smallhash_val_is_used(val)); BLI_assert(BLI_smallhash_haskey(sh, key) == false); if (UNLIKELY(smallhash_test_expand_buckets(++sh->nentries, sh->nbuckets))) { @@ -200,6 +219,7 @@ void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *val) e->val = val; } +#ifdef USE_REMOVE bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key) { SmallHashEntry *e = smallhash_lookup(sh, key); @@ -215,6 +235,7 @@ bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key) return false; } } +#endif void *BLI_smallhash_lookup(SmallHash *sh, uintptr_t key) { @@ -245,9 +266,7 @@ int BLI_smallhash_count(SmallHash *sh) void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) { while (iter->i < iter->sh->nbuckets) { - if ((iter->sh->buckets[iter->i].val != SMHASH_CELL_UNUSED) && - (iter->sh->buckets[iter->i].val != SMHASH_CELL_FREE)) - { + if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) { if (key) { *key = iter->sh->buckets[iter->i].key; } |