Smallhash: add reserve option to avoid resizing when size is known
authorCampbell Barton <ideasman42@gmail.com>
Sun, 2 Feb 2014 06:08:26 +0000 (17:08 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 2 Feb 2014 06:08:26 +0000 (17:08 +1100)
source/blender/blenlib/BLI_smallhash.h
source/blender/blenlib/intern/smallhash.c
source/blender/bmesh/intern/bmesh_core.c
source/blender/bmesh/operators/bmo_triangulate.c
source/blender/editors/mesh/editmesh_knife.c

index f394a224ca183945c031167cd7d3b1e1db5e2abf..b2fec6f870cbe7e32654ac72e69aa9f5d9025fd5 100644 (file)
@@ -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);
index be5f70c7f49b56d7462677736826f8b926254291..38ebdc53f53d61a894ac4d76bb82b4967799ebf8 100644 (file)
@@ -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)
 {
index c635f9d9d06bc083252e9fe03a7f3aed38818cb9..bbfee692df43c108cc2b8c43a7c370e692977b5c 100644 (file)
@@ -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);
 
index a1de265bc56f8d528dba1d54d6da7daaa0a53534..d26c10c24af72b17dc1f0dedf17e0944ed6ea927 100644 (file)
@@ -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);
        
index 0d1e43a709b5dcd28ca345b791fb587e3dbdf287..1fb3741380a6d29e67459d6f4c4b9c64aa464f2e 100644 (file)
@@ -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;