ghash and edgehash api, allow newly defined hashes to take in the size of the hash as an arg (avoids resizing in simple cases when the hash is created and filled immediately).

4 files changed, 42 insertions, 4 deletions

diff --git a/source/blender/blenlib/BLI_edgehash.h b/source/blender/blenlib/BLI_edgehash.h
index 1962201c8d2..f961d73cd79 100644
--- a/source/blender/blenlib/BLI_edgehash.h
+++ b/source/blender/blenlib/BLI_edgehash.h
@@ -40,6 +40,7 @@ enum {
 	EDGEHASH_FLAG_ALLOW_DUPES = (1 << 0),  /* only checked for in debug mode */
 };
 
+EdgeHash       *BLI_edgehash_new_ex(const unsigned int nentries_reserve);
 EdgeHash       *BLI_edgehash_new(void);
 void            BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp);
 void            BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val);
diff --git a/source/blender/blenlib/BLI_ghash.h b/source/blender/blenlib/BLI_ghash.h
index 4688c6e3831..5f748fcaecd 100644
--- a/source/blender/blenlib/BLI_ghash.h
+++ b/source/blender/blenlib/BLI_ghash.h
@@ -58,6 +58,8 @@ enum {
 
 /* *** */
 
+GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
+                        const unsigned int nentries_reserve);
 GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info);
 void   BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp);
 void   BLI_ghash_insert(GHash *gh, void *key, void *val);
diff --git a/source/blender/blenlib/intern/BLI_ghash.c b/source/blender/blenlib/intern/BLI_ghash.c
index 10a425ca12c..a1cbf8a5ce0 100644
--- a/source/blender/blenlib/intern/BLI_ghash.c
+++ b/source/blender/blenlib/intern/BLI_ghash.c
@@ -86,6 +86,11 @@ struct GHash {
 
 /* internal utility API */
 
+BLI_INLINE bool ghash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
+{
+	return (nentries > nbuckets / 2);
+}
+
 BLI_INLINE unsigned int ghash_keyhash(GHash *gh, const void *key)
 {
 	return gh->hashfp(key) % gh->nbuckets;
@@ -122,7 +127,7 @@ static void ghash_insert_ex(GHash *gh, void *key, void *val,
 	e->val = val;
 	gh->buckets[hash] = e;
 
-	if (UNLIKELY(++gh->nentries > gh->nbuckets / 2)) {
+	if (UNLIKELY(ghash_test_expand_buckets(++gh->nentries, gh->nbuckets))) {
 		Entry **old = gh->buckets;
 		const unsigned nold = gh->nbuckets;
 		unsigned int i;
@@ -147,7 +152,8 @@ static void ghash_insert_ex(GHash *gh, void *key, void *val,
 
 /* Public API */
 
-GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
+GHash *BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info,
+                        const unsigned int nentries_reserve)
 {
 	GHash *gh = MEM_mallocN(sizeof(*gh), info);
 
@@ -159,12 +165,24 @@ GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
 	gh->cursize = 0;
 	gh->flag = 0;
 
+	/* if we have reserved the number of elements that this hash will contain */
+	if (nentries_reserve) {
+		while (ghash_test_expand_buckets(nentries_reserve, gh->nbuckets)) {
+			gh->nbuckets = hashsizes[++gh->cursize];
+		}
+	}
+
 	gh->buckets = MEM_callocN(gh->nbuckets * sizeof(*gh->buckets), "buckets");
 	gh->entrypool = BLI_mempool_create(sizeof(Entry), 64, 64, 0);
 
 	return gh;
 }
 
+GHash *BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info)
+{
+	return BLI_ghash_new_ex(hashfp, cmpfp, info, 0);
+}
+
 int BLI_ghash_size(GHash *gh)
 {
 	return (int)gh->nentries;
diff --git a/source/blender/blenlib/intern/edgehash.c b/source/blender/blenlib/intern/edgehash.c
index 3263c69ee6a..738f1f0c7a1 100644
--- a/source/blender/blenlib/intern/edgehash.c
+++ b/source/blender/blenlib/intern/edgehash.c
@@ -86,6 +86,11 @@ struct EdgeHash {
 
 #define EDGE_HASH(v0, v1)  ((v0 * 39) ^ (v1 * 31))
 
+BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
+{
+	return (nentries > nbuckets / 2);
+}
+
 BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1)
 {
 	BLI_assert(v0 < v1);
@@ -130,7 +135,7 @@ static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, v
 	e->val = val;
 	eh->buckets[hash] = e;
 
-	if (UNLIKELY(++eh->nentries > eh->nbuckets / 2)) {
+	if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
 		EdgeEntry **old = eh->buckets;
 		const unsigned int nold = eh->nbuckets;
 		unsigned int i;
@@ -157,7 +162,7 @@ static void edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1, v
 
 /* Public API */
 
-EdgeHash *BLI_edgehash_new(void)
+EdgeHash *BLI_edgehash_new_ex(const unsigned int nentries_reserve)
 {
 	EdgeHash *eh = MEM_callocN(sizeof(*eh), "EdgeHash");
 
@@ -166,12 +171,24 @@ EdgeHash *BLI_edgehash_new(void)
 	eh->cursize = 0;
 	eh->flag = 0;
 
+	/* if we have reserved the number of elements that this hash will contain */
+	if (nentries_reserve) {
+		while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
+			eh->nbuckets = _ehash_hashsizes[++eh->cursize];
+		}
+	}
+
 	eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2");
 	eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, BLI_MEMPOOL_SYSMALLOC);
 
 	return eh;
 }
 
+EdgeHash *BLI_edgehash_new(void)
+{
+	return BLI_edgehash_new_ex(0);
+}
+
 /**
  * Insert edge (\a v0, \a v1) into hash with given value, does
  * not check for duplicates.