[Bf-blender-cvs] [dcd90d6] master: Smallhash: fixes/improvements

[Campbell Barton]

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;
 			}