Smallhash: fixes/improvements
authorCampbell Barton <ideasman42@gmail.com>
Sun, 2 Feb 2014 05:22:05 +0000 (16:22 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 2 Feb 2014 05:24:33 +0000 (16:24 +1100)
- 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

source/blender/blenlib/intern/smallhash.c

index fa953f0e44d0952458c9630e7006c543552b4900..be5f70c7f49b56d7462677736826f8b926254291 100644 (file)
  * 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>
 
 #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)  ( \
        ((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;
                        }