add linklist stack macros, use where over allocating an array was previously done.
authorCampbell Barton <ideasman42@gmail.com>
Sat, 17 Aug 2013 05:33:55 +0000 (05:33 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Sat, 17 Aug 2013 05:33:55 +0000 (05:33 +0000)
source/blender/blenlib/BLI_linklist_stack.h [new file with mode: 0644]
source/blender/blenlib/CMakeLists.txt
source/blender/bmesh/operators/bmo_connect.c
source/blender/bmesh/operators/bmo_connect_nonplanar.c
source/blender/bmesh/operators/bmo_normals.c
source/blender/editors/mesh/editmesh_select.c
source/blender/editors/transform/transform_conversions.c

diff --git a/source/blender/blenlib/BLI_linklist_stack.h b/source/blender/blenlib/BLI_linklist_stack.h
new file mode 100644 (file)
index 0000000..82ca986
--- /dev/null
@@ -0,0 +1,90 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): none yet.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef __BLI_LINKLIST_STACK_H__
+#define __BLI_LINKLIST_STACK_H__
+
+/** \file BLI_linklist_stack.h
+ * \ingroup bli
+ * \brief BLI_LINKSTACK_*** wrapper macros for using a \a LinkNode
+ *        to store a stack of pointers, using a single linked list
+ *        allocated from a mempool.
+ *
+ * \note These macros follow STACK_* macros defined in 'BLI_utildefines.h'
+ *       and should be kept (mostly) interchangeable.
+ *
+ * \note _##var##_type is a dummy var only used for typechecks.
+ */
+
+#define BLI_LINKSTACK_DECLARE(var, type) \
+       LinkNode *var; \
+       BLI_mempool *_##var##_pool; \
+       type _##var##_type
+
+#define BLI_LINKSTACK_INIT(var)  { \
+       var = NULL; \
+       _##var##_pool = BLI_mempool_create(sizeof(LinkNode), 1, 64, 0); \
+} (void)0
+
+#define BLI_LINKSTACK_SIZE(var) \
+       BLI_mempool_count(_##var##_pool)
+
+/* check for typeof() */
+#ifdef __GNUC__
+#define BLI_LINKSTACK_PUSH(var, ptr)  ( \
+       CHECK_TYPE_INLINE(ptr, typeof(_##var##_type)), \
+       BLI_linklist_prepend_pool(&(var), ptr, _##var##_pool))
+#define BLI_LINKSTACK_POP(var) \
+       (var ? (typeof(_##var##_type))BLI_linklist_pop_pool(&(var), _##var##_pool) : NULL)
+#define BLI_LINKSTACK_POP_ELSE(var, r) \
+       (var ? (typeof(_##var##_type))BLI_linklist_pop_pool(&(var), _##var##_pool) : r)
+#else  /* non gcc */
+#define BLI_LINKSTACK_PUSH(var, ptr)  ( \
+       BLI_linklist_prepend_pool(&(var), ptr, _##var##_pool))
+#define BLI_LINKSTACK_POP(var) \
+       (var ? BLI_linklist_pop_pool(&(var), _##var##_pool) : NULL)
+#define BLI_LINKSTACK_POP_ELSE(var, r) \
+       (var ? BLI_linklist_pop_pool(&(var), _##var##_pool) : r)
+#endif  /* gcc check */
+
+#define BLI_LINKSTACK_SWAP(var_a, var_b)  { \
+       CHECK_TYPE_PAIR(_##var_a##_type, _##var_b##_type); \
+       SWAP(LinkNode *, var_a, var_b); \
+       SWAP(BLI_mempool *, _##var_a##_pool, _##var_b##_pool); \
+} (void)0
+
+#define BLI_LINKSTACK_FREE(var)  { \
+       BLI_mempool_destroy(_##var##_pool); \
+       _##var##_pool = NULL; (void)_##var##_pool; \
+       var = NULL; (void)var; \
+       (void)_##var##_type; \
+} (void)0
+
+#include "BLI_linklist.h"
+#include "BLI_mempool.h"
+
+#endif  /* __BLI_LINKLIST_STACK_H__ */
index b6b6911..8b604e4 100644 (file)
@@ -25,7 +25,7 @@
 
 # XXX allowing blenkernel and RNA includes in blenlib is a hack,
 # but needed in a few places atm (bpath.c for instance)
-set(INC 
+set(INC
        .
        # ../blenkernel  # dont add this back!
        ../makesdna
@@ -125,6 +125,7 @@ set(SRC
        BLI_kdtree.h
        BLI_lasso.h
        BLI_linklist.h
+       BLI_linklist_stack.h
        BLI_listbase.h
        BLI_math.h
        BLI_math_base.h
index c718cac..b3a42ba 100644 (file)
@@ -31,6 +31,7 @@
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 #include "BLI_alloca.h"
+#include "BLI_linklist_stack.h"
 
 #include "bmesh.h"
 
@@ -117,10 +118,9 @@ void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
        BMIter iter;
        BMVert *v;
        BMFace *f;
-       BMFace **faces = MEM_mallocN(sizeof(BMFace *) * bm->totface, __func__);
-       STACK_DECLARE(faces);
+       BLI_LINKSTACK_DECLARE(faces, BMFace *);
 
-       STACK_INIT(faces);
+       BLI_LINKSTACK_INIT(faces);
 
        /* add all faces connected to verts */
        BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
@@ -129,20 +129,20 @@ void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
                        if (!BMO_elem_flag_test(bm, f, FACE_TAG)) {
                                BMO_elem_flag_enable(bm, f, FACE_TAG);
                                if (f->len > 3) {
-                                       STACK_PUSH(faces, f);
+                                       BLI_LINKSTACK_PUSH(faces, f);
                                }
                        }
                }
        }
 
        /* connect faces */
-       while ((f = STACK_POP(faces))) {
+       while ((f = BLI_LINKSTACK_POP(faces))) {
                if (bm_face_connect_verts(bm, f) == -1) {
                        BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
                }
        }
 
-       MEM_freeN(faces);
+       BLI_LINKSTACK_FREE(faces);
 
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
 }
index 6d30b32..6108559 100644 (file)
@@ -31,6 +31,7 @@
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 #include "BLI_alloca.h"
+#include "BLI_linklist_stack.h"
 
 #include "bmesh.h"
 
@@ -179,9 +180,7 @@ void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
        BMOIter siter;
        BMFace *f;
        int totface = 0, totloop = 0;
-       int tottris;
-       BMFace **fstack;
-       STACK_DECLARE(fstack);
+       BLI_LINKSTACK_DECLARE(fstack, BMFace *);
 
        const float angle_limit = BMO_slot_float_get(op->slots_in, "angle_limit");
 
@@ -197,32 +196,28 @@ void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
                return;
        }
 
-       /* over alloc, if we split every face */
-       tottris = poly_to_tri_count(totface, totloop);
-       fstack = MEM_mallocN(sizeof(BMFace *) * tottris, __func__);
-
-       STACK_INIT(fstack);
+       BLI_LINKSTACK_INIT(fstack);
 
        BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
                if (f->len > 3) {
-                       STACK_PUSH(fstack, f);
+                       BLI_LINKSTACK_PUSH(fstack, f);
                }
        }
 
-       while ((f = STACK_POP(fstack))) {
+       while ((f = BLI_LINKSTACK_POP(fstack))) {
                BMFace *f_pair[2];
                if (bm_face_split_by_angle(bm, f, f_pair, angle_limit)) {
                        int j;
                        for (j = 0; j < 2; j++) {
                                BM_face_normal_update(f_pair[j]);
                                if (f_pair[j]->len > 3) {
-                                       STACK_PUSH(fstack, f_pair[j]);
+                                       BLI_LINKSTACK_PUSH(fstack, f_pair[j]);
                                }
                        }
                }
        }
 
-       MEM_freeN(fstack);
+       BLI_LINKSTACK_FREE(fstack);
 
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
index b645766..93d7d1a 100644 (file)
@@ -29,6 +29,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_math.h"
+#include "BLI_linklist_stack.h"
 
 #include "bmesh.h"
 
@@ -65,8 +66,7 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f
        float f_len_best;
        BMFace *f;
 
-       BMFace **fstack = MEM_mallocN(sizeof(*fstack) * faces_len, __func__);
-       STACK_DECLARE(fstack);
+       BLI_LINKSTACK_DECLARE(fstack, BMFace *);
 
        zero_v3(cent);
 
@@ -103,12 +103,12 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f
         * have the same winding.  this is done recursively, using a manual
         * stack (if we use simple function recursion, we'd end up overloading
         * the stack on large meshes). */
-       STACK_INIT(fstack);
+       BLI_LINKSTACK_INIT(fstack);
 
-       STACK_PUSH(fstack, faces[f_start_index]);
+       BLI_LINKSTACK_PUSH(fstack, faces[f_start_index]);
        BMO_elem_flag_enable(bm, faces[f_start_index], FACE_TEMP);
 
-       while ((f = STACK_POP(fstack))) {
+       while ((f = BLI_LINKSTACK_POP(fstack))) {
                const bool flip_state = BMO_elem_flag_test_bool(bm, f, FACE_FLIP);
                BMLoop *l_iter, *l_first;
 
@@ -120,13 +120,13 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f
                                if (!BMO_elem_flag_test(bm, l_other->f, FACE_TEMP)) {
                                        BMO_elem_flag_enable(bm, l_other->f, FACE_TEMP);
                                        BMO_elem_flag_set(bm, l_other->f, FACE_FLIP, (l_other->v == l_iter->v) != flip_state);
-                                       STACK_PUSH(fstack, l_other->f);
+                                       BLI_LINKSTACK_PUSH(fstack, l_other->f);
                                }
                        }
                } while ((l_iter = l_iter->next) != l_first);
        }
 
-       MEM_freeN(fstack);
+       BLI_LINKSTACK_FREE(fstack);
 
        /* apply flipping to oflag'd faces */
        for (i = 0; i < faces_len; i++) {
index a1f1f6b..a89a6f8 100644 (file)
@@ -33,6 +33,7 @@
 
 #include "BLI_listbase.h"
 #include "BLI_linklist.h"
+#include "BLI_linklist_stack.h"
 #include "BLI_math.h"
 #include "BLI_rand.h"
 #include "BLI_array.h"
@@ -2609,8 +2610,7 @@ static int edbm_select_linked_flat_faces_exec(bContext *C, wmOperator *op)
        BMEditMesh *em = BKE_editmesh_from_object(obedit);
        BMesh *bm = em->bm;
 
-       BMFace **stack = MEM_mallocN(sizeof(BMFace *) * bm->totface, __func__);
-       STACK_DECLARE(stack);
+       BLI_LINKSTACK_DECLARE(stack, BMFace *);
 
        BMIter iter, liter, liter2;
        BMFace *f;
@@ -2628,7 +2628,7 @@ static int edbm_select_linked_flat_faces_exec(bContext *C, wmOperator *op)
                        continue;
                }
 
-               STACK_INIT(stack);
+               BLI_LINKSTACK_INIT(stack);
 
                do {
                        BM_face_select_set(bm, f, true);
@@ -2648,16 +2648,14 @@ static int edbm_select_linked_flat_faces_exec(bContext *C, wmOperator *op)
                                        angle = angle_normalized_v3v3(f->no, l2->f->no);
 
                                        if (angle < angle_limit) {
-                                               STACK_PUSH(stack, l2->f);
+                                               BLI_LINKSTACK_PUSH(stack, l2->f);
                                        }
                                }
                        }
-               } while ((f = STACK_POP(stack)));
+               } while ((f = BLI_LINKSTACK_POP(stack)));
        }
 
-       STACK_FREE(stack);
-
-       MEM_freeN(stack);
+       BLI_LINKSTACK_FREE(stack);
 
        WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
 
index 0160500..1849bfe 100644 (file)
 #include "MEM_guardedalloc.h"
 
 #include "BLI_math.h"
-#include "BLI_blenlib.h"
 #include "BLI_utildefines.h"
 #include "BLI_smallhash.h"
+#include "BLI_listbase.h"
+#include "BLI_linklist_stack.h"
+#include "BLI_string.h"
+#include "BLI_rect.h"
 
 #include "BKE_DerivedMesh.h"
 #include "BKE_action.h"
 #include "transform.h"
 #include "bmesh.h"
 
-#include "BLI_sys_types.h" // for intptr_t support
-
 /* when transforming islands */
 struct TransIslandData {
        float co[3];
@@ -1848,15 +1849,13 @@ static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float
        /* need to be very careful of feedback loops here, store previous dist's to avoid feedback */
        float *dists_prev = MEM_mallocN(bm->totvert * sizeof(float), __func__);
 
-       BMVert **queue = MEM_mallocN(bm->totvert * sizeof(BMVert *), __func__);
-       STACK_DECLARE(queue);
+       BLI_LINKSTACK_DECLARE(queue, BMVert *);
 
        /* any BM_ELEM_TAG'd vertex is in 'queue_next', so we don't add in twice */
-       BMVert **queue_next = MEM_mallocN(bm->totvert * sizeof(BMVert *), __func__);
-       STACK_DECLARE(queue_next);
+       BLI_LINKSTACK_DECLARE(queue_next, BMVert *);
 
-       STACK_INIT(queue);
-       STACK_INIT(queue_next);
+       BLI_LINKSTACK_INIT(queue);
+       BLI_LINKSTACK_INIT(queue_next);
 
        {
                BMIter viter;
@@ -1871,7 +1870,7 @@ static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float
                                dists[i] = FLT_MAX;
                        }
                        else {
-                               STACK_PUSH(queue, v);
+                               BLI_LINKSTACK_PUSH(queue, v);
 
                                dists[i] = 0.0f;
                        }
@@ -1880,11 +1879,11 @@ static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float
 
        do {
                BMVert *v;
-               unsigned int i;
+               LinkNode *lnk;
 
                memcpy(dists_prev, dists, sizeof(float) * bm->totvert);
 
-               while ((v = STACK_POP(queue))) {
+               while ((v = BLI_LINKSTACK_POP(queue))) {
                        BMIter iter;
                        BMEdge *e;
                        BMLoop *l;
@@ -1896,7 +1895,7 @@ static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float
                                        if (bmesh_test_dist_add(v, v_other, dists, dists_prev, mtx)) {
                                                if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == 0) {
                                                        BM_elem_flag_enable(v_other, BM_ELEM_TAG);
-                                                       STACK_PUSH(queue_next, v_other);
+                                                       BLI_LINKSTACK_PUSH(queue_next, v_other);
                                                }
                                        }
                                }
@@ -1912,7 +1911,7 @@ static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float
                                                if (bmesh_test_dist_add(v, v_other, dists, dists_prev, mtx)) {
                                                        if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == 0) {
                                                                BM_elem_flag_enable(v_other, BM_ELEM_TAG);
-                                                               STACK_PUSH(queue_next, v_other);
+                                                               BLI_LINKSTACK_PUSH(queue_next, v_other);
                                                        }
                                                }
                                        } while ((l = l->next) != l_end);
@@ -1921,22 +1920,20 @@ static void editmesh_set_connectivity_distance(BMesh *bm, float mtx[3][3], float
                }
 
                /* clear for the next loop */
-               for (i = 0; i < STACK_SIZE(queue_next); i++) {
-                       BM_elem_flag_disable(queue_next[i], BM_ELEM_TAG);
+               for (lnk = queue_next; lnk; lnk = lnk->next) {
+                       BM_elem_flag_disable((BMVert *)lnk->link, BM_ELEM_TAG);
                }
 
-               STACK_SWAP(queue, queue_next);
+               BLI_LINKSTACK_SWAP(queue, queue_next);
 
                /* none should be tagged now since 'queue_next' is empty */
                BLI_assert(BM_iter_mesh_count_flag(BM_VERTS_OF_MESH, bm, BM_ELEM_TAG, true) == 0);
 
-       } while (STACK_SIZE(queue));
+       } while (BLI_LINKSTACK_SIZE(queue));
 
-       STACK_FREE(queue);
-       STACK_FREE(queue_next);
+       BLI_LINKSTACK_FREE(queue);
+       BLI_LINKSTACK_FREE(queue_next);
 
-       MEM_freeN(queue);
-       MEM_freeN(queue_next);
        MEM_freeN(dists_prev);
 }