Commit: 3369b0b0ee936459a7df089e423ddbff61874a3f Author: Joseph Eagar Date: Sat Oct 10 01:15:57 2020 -0700 Branches: temp-trimesh-sculpt https://developer.blender.org/rB3369b0b0ee936459a7df089e423ddbff61874a3f
inline SmallHash =================================================================== M source/blender/blenlib/BLI_smallhash.h M source/blender/blenlib/intern/smallhash.c =================================================================== diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h index daea2fcd914..c9875caf7b3 100644 --- a/source/blender/blenlib/BLI_smallhash.h +++ b/source/blender/blenlib/BLI_smallhash.h @@ -23,7 +23,14 @@ * \ingroup bli */ +#define USE_SMALLHASH_REMOVE + +#include "BLI_utildefines.h" + #include "BLI_compiler_attrs.h" +#include "BLI_compiler_compat.h" +#include "BLI_compiler_typecheck.h" +#include "BLI_assert.h" #ifdef __cplusplus extern "C" { @@ -48,29 +55,281 @@ typedef struct SmallHash { typedef struct { const SmallHash *sh; - unsigned int i; + uintptr_t key; + void *val; + unsigned int i, done; } SmallHashIter; + +#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) \ + (CHECK_TYPE_INLINE(&(h), uintptr_t *), \ + CHECK_TYPE_INLINE(&(hoff), uintptr_t *), \ + ((h) + (((hoff) = ((hoff)*2) + 1), (hoff)))) + +BLI_INLINE int smallhash_val_is_used(const void *val) +{ +#ifdef USE_SMALLHASH_REMOVE + return !ELEM(val, SMHASH_CELL_FREE, SMHASH_CELL_UNUSED); +#else + return (val != SMHASH_CELL_FREE); +#endif +} + +BLI_INLINE uintptr_t smallhash_key(const uintptr_t key) +{ + return key; +} + +BLI_INLINE SmallHashEntry *smallhash_lookup(const SmallHash *sh, const uintptr_t key) +{ + SmallHashEntry *e; + uintptr_t h = smallhash_key(key); + uintptr_t hoff = 1; + + BLI_assert(key != SMHASH_KEY_UNUSED); + + /* note: there are always more buckets than entries, + * so we know there will always be a free bucket if the key isn't found. */ + for (e = &sh->buckets[h % sh->nbuckets]; e->val != SMHASH_CELL_FREE;) + { + if (e->key == key) { + /* should never happen because unused keys are zero'd */ + BLI_assert(e->val != SMHASH_CELL_UNUSED); + + return e; + } + + h = SMHASH_NEXT(h, hoff); + e = &sh->buckets[h % sh->nbuckets]; + } + + return NULL; +} + +BLI_INLINE void *BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key) +{ + SmallHashEntry *e = smallhash_lookup(sh, key); + + return e ? e->val : NULL; +} + +BLI_INLINE void **BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key) +{ + SmallHashEntry *e = smallhash_lookup(sh, key); + + return e ? &e->val : NULL; +} + +BLI_INLINE bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key) +{ + SmallHashEntry *e = smallhash_lookup(sh, key); + + return (e != NULL); +} + +BLI_INLINE int BLI_smallhash_len(const SmallHash *sh) +{ + return (int)sh->nentries; +} + +BLI_INLINE SmallHashEntry *smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +{ + while (iter->i < iter->sh->nbuckets) { + if (smallhash_val_is_used(iter->sh->buckets[iter->i].val)) { + SmallHashEntry *e = iter->sh->buckets + iter->i; + + iter->key = e->key; + iter->val = e->val; + + if (key) { + *key = iter->key; + } + + iter->i++; + return e; + } + + iter->i++; + } + + iter->done = 1; + return NULL; +} + +BLI_INLINE void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) +{ + SmallHashEntry *e = smallhash_iternext(iter, key); + + return e ? e->val : NULL; +} + +BLI_INLINE void **BLI_smallhash_iternext_p(SmallHashIter *iter, uintptr_t *key) +{ + SmallHashEntry *e = smallhash_iternext(iter, key); + + return e ? &e->val : NULL; +} + +BLI_INLINE void *BLI_smallhash_iternew(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key) +{ + iter->sh = sh; + iter->i = 0; + iter->key = 0; + iter->val = NULL; + iter->done = 0; + + return BLI_smallhash_iternext(iter, key); +} +void BLI_smallhash_clear(SmallHash *sh); + +BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const uint nbuckets); +extern const uint BLI_ghash_hash_sizes[]; + +/** +* Check if the number of items in the smallhash is large enough to require more buckets. +*/ +BLI_INLINE bool smallhash_test_expand_buckets(const uint nentries, const uint nbuckets) +{ + /* (approx * 1.5) */ + return (nentries + (nentries >> 1)) > nbuckets; +} + +BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *sh, const uintptr_t key) +{ + SmallHashEntry *e; + uintptr_t h = smallhash_key(key); + uintptr_t hoff = 1; + + for (e = &sh->buckets[h % sh->nbuckets]; smallhash_val_is_used(e->val); + h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) { + /* pass */ + } + + return e; +} + +BLI_INLINE void smallhash_init_empty(SmallHash *sh) +{ + uint i; + + for (i = 0; i < sh->nbuckets; i++) { + sh->buckets[i].key = SMHASH_KEY_UNUSED; + sh->buckets[i].val = SMHASH_CELL_FREE; + } +} + +BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const uint nbuckets) +{ + SmallHashEntry *buckets_old = sh->buckets; + const uint nbuckets_old = sh->nbuckets; + const bool was_alloc = (buckets_old != sh->buckets_stack); + uint i = 0; + + BLI_assert(sh->nbuckets != nbuckets); + if (nbuckets <= SMSTACKSIZE) { + const size_t size = sizeof(*buckets_old) * nbuckets_old; + buckets_old = alloca(size); + memcpy(buckets_old, sh->buckets, size); + + sh->buckets = sh->buckets_stack; + } + else { + sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * nbuckets, __func__); + } + + sh->nbuckets = nbuckets; + + smallhash_init_empty(sh); + + for (i = 0; i < nbuckets_old; i++) { + 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; + } + } + + if (was_alloc) { + MEM_freeN(buckets_old); + } +} + +BLI_INLINE bool BLI_smallhash_ensure_p(SmallHash *sh, uintptr_t key, void ***item) { + SmallHashEntry *e; + + if (UNLIKELY(smallhash_test_expand_buckets(++sh->nentries, sh->nbuckets))) { + smallhash_resize_buckets(sh, BLI_ghash_hash_sizes[++sh->cursize]); + } + + uintptr_t h = smallhash_key(key); + uintptr_t hoff = 1; + + e = smallhash_lookup(sh, key); + //* + for (e = &sh->buckets[h % sh->nbuckets]; e->key != key && smallhash_val_is_used((void*)e->val); + h = SMHASH_NEXT(h, hoff), e = &sh->buckets[h % sh->nbuckets]) { + }//*/ + + bool ret = true; + + if (e->key != key) { + //e = smallhash_lookup_first_free(sh, key); + ret = false; + e->key = key; + } else { + e->val = NULL; + } + + *item = &e->val; + return ret; +} + + +BLI_INLINE uintptr_t BLI_smallhash_iterkey(SmallHashIter *iter) { + return iter->key; +} + +BLI_INLINE void *BLI_smallhash_iterval(SmallHashIter *iter) { + return (void*)iter->val; +} + +BLI_INLINE void **BLI_smallhash_iternew_p(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key) +{ + iter->sh = sh; + iter->i = 0; + iter->key = 0; + iter->val = NULL; + iter->done = 0; + + return BLI_smallhash_iternext_p(iter, key); +} + +#define SMALLHASH_ITER(iter, sh)\ +for (BLI_smallhash_iternew(sh, &(iter), NULL); !(iter).done; BLI_smallhash_iternext(&(iter), NULL)) + void BLI_smallhash_init_ex(SmallHash *sh, const unsigned int nentries_reserve) ATTR_NONNULL(1); void BLI_smallhash_init(SmallHash *sh) ATTR_NONNULL(1); void BLI_smallhash_release(SmallHash *sh) ATTR_NONNULL(1); void BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *item) ATTR_NONNULL(1); bool BLI_smallhash_reinsert(SmallHash *sh, uintptr_t key, void *item) ATTR_NONNULL(1); -bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key) ATTR_NONNULL(1); -void *BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key) - ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; -void **BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key) - ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; -bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key) ATTR_NONNULL(1); -int BLI_smallhash_len(const SmallHash *sh) ATTR_NONNULL(1); -void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key) - ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; -void **BLI_smallhash_iternext_p(SmallHashIter *iter, uintptr_t *key) - ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; -void *BLI_smallhash_iternew(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key) - ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; -void **BLI_smallhash_iternew_p(const SmallHash *sh, SmallHashIter *iter, uintptr_t *key) - ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; +bool BLI_smallhash_remove(SmallHash *sh, uintptr_t key); +void BLI_smallhash_reserve(SmallHash *sh, uint size); + +SmallHash *BLI_smallhash_new(); +SmallHash *BLI_smallhash_new_ex(int reserve); +void BLI_smallhash_free(SmallHash *sh); + +//void *BLI_smallhash_lookup(const SmallHash *sh, uintptr_t key) +// ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; +//void **BLI_smallhash_lookup_p(const SmallHash *sh, uintptr_t key) +// ATTR_NONNULL(1) ATTR_WARN_UNUSED_RESULT; +//bool BLI_smallhash_haskey(const SmallHash *sh, uintptr_t key) ATTR_NONNULL(1); +//int BLI_smallhash_len(const SmallHash *sh) ATTR_NONNULL(1); /* void BLI_smallhash_print(SmallHash *sh); */ /* UNUSED */ #ifdef DEBUG diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c index 4a2915ef24e..1b47003f5bf 100644 --- a/source/blender/blenlib/intern/smallhash.c +++ b/source/blender/blenlib/intern/smallhash.c @@ -54,139 +54,24 @@ #include "BLI_utildefines.h" #include "BLI_smallhash.h" - #include "BLI_strict_flags.h" -#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) \ - (CHECK_TYPE_INLINE(&(h), uint *), \ - CHECK_TYPE_INLINE(&(hoff), uint *), \ - ((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 uint BLI_ghash_hash_sizes[]; #define hashsizes BLI_ghash_hash_sizes -BLI_INLINE uint smallhash_key(const uintptr_t key) -{ - return (uint)key; -} - -/** - * Check if the number of items in the smallhash @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list Bf-blender-cvs@blender.org https://lists.blender.org/mailman/listinfo/bf-blender-cvs