Commit: dcd90d67c8a6e6beae37fc02515b8c75942332ca
Author: Campbell Barton
Date: Sun Feb 2 16:22:05 2014 +1100
https://developer.blender.org/rBdcd90d67c8a6e6beae37fc02515b8c75942332ca
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
===================================================================
M source/blender/blenlib/intern/smallhash.c
===================================================================
diff --git a/source/blender/blenlib/intern/smallhash.c
b/source/blender/blenlib/intern/smallhash.c
index fa953f0..be5f70c 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;
}
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
