Smallhash: add reserve option to avoid resizing when size is known

5 files changed, 33 insertions, 9 deletions

diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h
index f394a224ca1..b2fec6f870c 100644
--- a/source/blender/blenlib/BLI_smallhash.h
+++ b/source/blender/blenlib/BLI_smallhash.h
@@ -56,6 +56,8 @@ typedef struct {
 	unsigned int i;
 } SmallHashIter;
 
+void    BLI_smallhash_init_ex(SmallHash *sh,
+                              const unsigned int nentries_reserve) ATTR_NONNULL(1);
 void    BLI_smallhash_init(SmallHash *sh) ATTR_NONNULL(1);
 void    BLI_smallhash_release(SmallHash *sh) ATTR_NONNULL(1);
 void    BLI_smallhash_insert(SmallHash *sh, uintptr_t key, void *item) ATTR_NONNULL(1);
diff --git a/source/blender/blenlib/intern/smallhash.c b/source/blender/blenlib/intern/smallhash.c
index be5f70c7f49..38ebdc53f53 100644
--- a/source/blender/blenlib/intern/smallhash.c
+++ b/source/blender/blenlib/intern/smallhash.c
@@ -105,6 +105,16 @@ BLI_INLINE void smallhash_init_empty(SmallHash *sh)
 	}
 }
 
+/**
+ * Increase initial bucket size to match a reserved amount.
+ */
+BLI_INLINE void smallhash_buckets_reserve(SmallHash *sh, const unsigned int nentries_reserve)
+{
+	while (smallhash_test_expand_buckets(nentries_reserve, sh->nbuckets)) {
+		sh->nbuckets = hashsizes[++sh->cursize];
+	}
+}
+
 BLI_INLINE SmallHashEntry *smallhash_lookup(SmallHash *sh, const uintptr_t key)
 {
 	SmallHashEntry *e;
@@ -181,7 +191,8 @@ BLI_INLINE void smallhash_resize_buckets(SmallHash *sh, const unsigned int nbuck
 	}
 }
 
-void BLI_smallhash_init(SmallHash *sh)
+void BLI_smallhash_init_ex(SmallHash *sh,
+                           const unsigned int nentries_reserve)
 {
 	/* assume 'sh' is uninitialized */
 
@@ -191,9 +202,22 @@ void BLI_smallhash_init(SmallHash *sh)
 
 	sh->buckets = sh->buckets_stack;
 
+	if (nentries_reserve) {
+		smallhash_buckets_reserve(sh, nentries_reserve);
+
+		if (sh->nbuckets > SMSTACKSIZE) {
+			sh->buckets = MEM_mallocN(sizeof(*sh->buckets) * sh->nbuckets, __func__);
+		}
+	}
+
 	smallhash_init_empty(sh);
 }
 
+void BLI_smallhash_init(SmallHash *sh)
+{
+	BLI_smallhash_init_ex(sh, 0);
+}
+
 /*NOTE: does *not* free *sh itself!  only the direct data!*/
 void BLI_smallhash_release(SmallHash *sh)
 {
diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c
index c635f9d9d06..bbfee692df4 100644
--- a/source/blender/bmesh/intern/bmesh_core.c
+++ b/source/blender/bmesh/intern/bmesh_core.c
@@ -1971,7 +1971,7 @@ void bmesh_vert_separate(BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len
 	int i, maxindex;
 	BMLoop *l_new;
 
-	BLI_smallhash_init(&visithash);
+	BLI_smallhash_init_ex(&visithash, v_edgetot);
 
 	STACK_INIT(stack);
 
diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c
index a1de265bc56..d26c10c24af 100644
--- a/source/blender/bmesh/operators/bmo_triangulate.c
+++ b/source/blender/bmesh/operators/bmo_triangulate.c
@@ -70,7 +70,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op)
 	SmallHash hash;
 	float normal[3], *normal_pt;
 
-	BLI_smallhash_init(&hash);
+	BLI_smallhash_init_ex(&hash, BMO_slot_buffer_count(op->slots_in, "edges"));
 
 	BMO_slot_vec_get(op->slots_in, "normal", normal);
 	
diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c
index 0d1e43a709b..1fb3741380a 100644
--- a/source/blender/editors/mesh/editmesh_knife.c
+++ b/source/blender/editors/mesh/editmesh_knife.c
@@ -1293,9 +1293,6 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
 	/* First use bvh tree to find faces, knife edges, and knife verts that might
 	 * intersect the cut plane with rays v1-v3 and v2-v4.
 	 * This deduplicates the candidates before doing more expensive intersection tests. */
-	BLI_smallhash_init(&faces);
-	BLI_smallhash_init(&kfes);
-	BLI_smallhash_init(&kfvs);
 
 	tree = BKE_bmbvh_tree_get(kcd->bmbvh);
 	planetree = BLI_bvhtree_new(4, FLT_EPSILON * 4, 8, 8);
@@ -1308,13 +1305,14 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
 
 	results = BLI_bvhtree_overlap(tree, planetree, &tot);
 	if (!results) {
-		BLI_smallhash_release(&faces);
-		BLI_smallhash_release(&kfes);
-		BLI_smallhash_release(&kfvs);
 		BLI_bvhtree_free(planetree);
 		return;
 	}
 
+	BLI_smallhash_init(&faces);
+	BLI_smallhash_init(&kfes);
+	BLI_smallhash_init(&kfvs);
+
 	for (i = 0, result = results; i < tot; i++, result++) {
 		ls = (BMLoop **)kcd->em->looptris[result->indexA];
 		f = ls[0]->f;