[Bf-blender-cvs] [d292d6a] master: Cleanup of BLI_smallhash

[Bastien Montagne]

Commit: d292d6ad74e12cb9bec9c1839e883183e19580ca
Author: Bastien Montagne
Date:   Sun Jan 26 15:17:06 2014 +0100
https://developer.blender.org/rBd292d6ad74e12cb9bec9c1839e883183e19580ca

Cleanup of BLI_smallhash

Factorized a bit the code here, think it's more readable now... No performance enhancement though.

Reviewed by: campbellbarton

Differential Revision: https://developer.blender.org/D259

===================================================================

M	source/blender/blenkernel/intern/cdderivedmesh.c
M	source/blender/blenlib/intern/smallhash.c

===================================================================

diff --git a/source/blender/blenkernel/intern/cdderivedmesh.c b/source/blender/blenkernel/intern/cdderivedmesh.c
index a646f10..04bd8d3 100644
--- a/source/blender/blenkernel/intern/cdderivedmesh.c
+++ b/source/blender/blenkernel/intern/cdderivedmesh.c
@@ -40,7 +40,6 @@
 #include "BLI_blenlib.h"
 #include "BLI_edgehash.h"
 #include "BLI_math.h"
-#include "BLI_smallhash.h"
 #include "BLI_utildefines.h"
 #include "BLI_scanfill.h"
 
diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c
index b6924af..45a9c58 100644
--- a/source/blender/blenlib/intern/smallhash.c
+++ b/source/blender/blenlib/intern/smallhash.c
@@ -89,9 +89,25 @@ void BLI_smallhash_release(SmallHash *hash)
 	}
 }
 
+BLI_INLINE SmallHashEntry *smallhash_lookup_first_free(SmallHash *hash, uintptr_t key)
+{
+	SmallHashEntry *entry;
+	unsigned int h = (unsigned int)key;
+	unsigned int hoff = 1;
+
+	for (entry = &hash->table[h % hash->size];
+		 !ELEM(entry->val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
+		 h = SMHASH_NEXT(h, hoff), entry = &hash->table[h % hash->size])
+	{
+		/* Nothing else to do! */
+	}
+
+	return entry;
+}
+
 void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
 {
-	unsigned int h, hoff = 1;
+	SmallHashEntry *entry;
 
 	if (hash->size < hash->used * 3) {
 		unsigned int newsize = hashsizes[++hash->curhash];
@@ -119,16 +135,9 @@ void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
 				continue;
 			}
 
-			h = (unsigned int)(tmp[i].key);
-			hoff = 1;
-			while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
-				h = SMHASH_NEXT(h, hoff);
-			}
-
-			h %= newsize;
-
-			hash->table[h].key = tmp[i].key;
-			hash->table[h].val = tmp[i].val;
+			entry = smallhash_lookup_first_free(hash, tmp[i].key);
+			entry->key = tmp[i].key;
+			entry->val = tmp[i].val;
 		}
 
 		if (tmp != hash->stacktable && tmp != hash->copytable) {
@@ -136,83 +145,52 @@ void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
 		}
 	}
 
-	h = (unsigned int)(key);
-	hoff = 1;
-
-	while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
-		h = SMHASH_NEXT(h, hoff);
-	}
-
-	h %= hash->size;
-	hash->table[h].key = key;
-	hash->table[h].val = item;
+	entry = smallhash_lookup_first_free(hash, key);
+	entry->key = key;
+	entry->val = item;
 
 	hash->used++;
 }
 
-void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
+BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *hash, uintptr_t key)
 {
-	unsigned int h, hoff = 1;
-
-	h = (unsigned int)(key);
+	SmallHashEntry *entry;
+	unsigned int h = (unsigned int)key;
+	unsigned int hoff = 1;
 
-	while ((hash->table[h % hash->size].key != key) ||
-	       (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
+	for (entry = &hash->table[h % hash->size];
+	     ((entry->key != key) || (entry->val == SMHASH_CELL_UNUSED)) && (entry->val != SMHASH_CELL_FREE);
+	     h = SMHASH_NEXT(h, hoff), entry = &hash->table[h % hash->size])
 	{
-		if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
-			return;
-		}
-
-		h = SMHASH_NEXT(h, hoff);
+		/* Nothing else to do! */
 	}
 
-	h %= hash->size;
-	hash->table[h].key = 0;
-	hash->table[h].val = SMHASH_CELL_UNUSED;
+	return entry;
 }
 
-void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
+void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
 {
-	unsigned int h, hoff = 1;
-	void *v;
+	SmallHashEntry *entry = smallhash_lookup(hash, key);
 
-	h = (unsigned int)(key);
-
-	while ((hash->table[h % hash->size].key != key) ||
-	       (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
-	{
-		if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
-			return NULL;
-		}
-
-		h = SMHASH_NEXT(h, hoff);
+	if (entry->val != SMHASH_CELL_FREE) {
+		entry->key = 0;
+		entry->val = SMHASH_CELL_UNUSED;
 	}
+}
 
-	v = hash->table[h % hash->size].val;
-	if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
-		return NULL;
-	}
+void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
+{
+	SmallHashEntry *entry = smallhash_lookup(hash, key);
 
-	return v;
+	return ELEM(entry->val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE) ? NULL : entry->val;
 }
 
 
 bool BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
 {
-	unsigned int h = (unsigned int)(key);
-	unsigned int hoff = 1;
+	SmallHashEntry *entry = smallhash_lookup(hash, key);
 
-	while ((hash->table[h % hash->size].key != key) ||
-	       (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
-	{
-		if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
-			return false;
-		}
-
-		h = SMHASH_NEXT(h, hoff);
-	}
-
-	return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
+	return !ELEM(entry->val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
 }
 
 int BLI_smallhash_count(SmallHash *hash)
@@ -230,9 +208,7 @@ void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
 				*key = iter->hash->table[iter->i].key;
 			}
 
-			iter->i++;
-
-			return iter->hash->table[iter->i - 1].val;
+			return iter->hash->table[iter->i++].val;
 		}
 
 		iter->i++;