[Bf-blender-cvs] [3369b0b0ee9] temp-trimesh-sculpt: inline SmallHash
Joseph Eagar
noreply at git.blender.org
Wed Oct 14 04:05:49 CEST 2020
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. @@
More information about the Bf-blender-cvs
mailing list