1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bmesh
19 *
20 * BMesh Walker API.
21 */
22
23 #include <stdlib.h>
24 #include <string.h> /* for memcpy */
25
26 #include "BLI_listbase.h"
27 #include "BLI_utildefines.h"
28
29 #include "bmesh.h"
30
31 #include "bmesh_walkers_private.h"
32
33 /**
34 * - joeedh -
35 * design notes:
36 *
37 * original design: walkers directly emulation recursive functions.
38 * functions save their state onto a worklist, and also add new states
39 * to implement recursive or looping behavior. generally only one
40 * state push per call with a specific state is desired.
41 *
42 * basic design pattern: the walker step function goes through its
43 * list of possible choices for recursion, and recurses (by pushing a new state)
44 * using the first non-visited one. This choice is the flagged as visited using
45 * the ghash. each step may push multiple new states onto the worklist at once.
46 *
47 * - Walkers use tool flags, not header flags.
48 * - Walkers now use ghash for storing visited elements,
49 * rather than stealing flags. ghash can be rewritten
50 * to be faster if necessary, in the far future :) .
51 * - tools should ALWAYS have necessary error handling
52 * for if walkers fail.
53 */
54
BMW_begin(BMWalker * walker,void * start)55 void *BMW_begin(BMWalker *walker, void *start)
56 {
57 BLI_assert(((BMHeader *)start)->htype & walker->begin_htype);
58
59 walker->begin(walker, start);
60
61 return BMW_current_state(walker) ? walker->step(walker) : NULL;
62 }
63
64 /**
65 * \brief Init Walker
66 *
67 * Allocates and returns a new mesh walker of a given type.
68 * The elements visited are filtered by the bitmask 'searchmask'.
69 */
BMW_init(BMWalker * walker,BMesh * bm,int type,short mask_vert,short mask_edge,short mask_face,BMWFlag flag,int layer)70 void BMW_init(BMWalker *walker,
71 BMesh *bm,
72 int type,
73 short mask_vert,
74 short mask_edge,
75 short mask_face,
76 BMWFlag flag,
77 int layer)
78 {
79 memset(walker, 0, sizeof(BMWalker));
80
81 walker->layer = layer;
82 walker->flag = flag;
83 walker->bm = bm;
84
85 walker->mask_vert = mask_vert;
86 walker->mask_edge = mask_edge;
87 walker->mask_face = mask_face;
88
89 walker->visit_set = BLI_gset_ptr_new("bmesh walkers");
90 walker->visit_set_alt = BLI_gset_ptr_new("bmesh walkers sec");
91
92 if (UNLIKELY(type >= BMW_MAXWALKERS || type < 0)) {
93 fprintf(stderr,
94 "%s: Invalid walker type in BMW_init; type: %d, "
95 "searchmask: (v:%d, e:%d, f:%d), flag: %u, layer: %d\n",
96 __func__,
97 type,
98 mask_vert,
99 mask_edge,
100 mask_face,
101 flag,
102 layer);
103 BLI_assert(0);
104 return;
105 }
106
107 if (type != BMW_CUSTOM) {
108 walker->begin_htype = bm_walker_types[type]->begin_htype;
109 walker->begin = bm_walker_types[type]->begin;
110 walker->yield = bm_walker_types[type]->yield;
111 walker->step = bm_walker_types[type]->step;
112 walker->structsize = bm_walker_types[type]->structsize;
113 walker->order = bm_walker_types[type]->order;
114 walker->valid_mask = bm_walker_types[type]->valid_mask;
115
116 /* safety checks */
117 /* if this raises an error either the caller is wrong or
118 * 'bm_walker_types' needs updating */
119 BLI_assert(mask_vert == 0 || (walker->valid_mask & BM_VERT));
120 BLI_assert(mask_edge == 0 || (walker->valid_mask & BM_EDGE));
121 BLI_assert(mask_face == 0 || (walker->valid_mask & BM_FACE));
122 }
123
124 walker->worklist = BLI_mempool_create(walker->structsize, 0, 128, BLI_MEMPOOL_NOP);
125 BLI_listbase_clear(&walker->states);
126 }
127
128 /**
129 * \brief End Walker
130 *
131 * Frees a walker's worklist.
132 */
BMW_end(BMWalker * walker)133 void BMW_end(BMWalker *walker)
134 {
135 BLI_mempool_destroy(walker->worklist);
136 BLI_gset_free(walker->visit_set, NULL);
137 BLI_gset_free(walker->visit_set_alt, NULL);
138 }
139
140 /**
141 * \brief Step Walker
142 */
BMW_step(BMWalker * walker)143 void *BMW_step(BMWalker *walker)
144 {
145 BMHeader *head;
146
147 head = BMW_walk(walker);
148
149 return head;
150 }
151
152 /**
153 * \brief Walker Current Depth
154 *
155 * Returns the current depth of the walker.
156 */
157
BMW_current_depth(BMWalker * walker)158 int BMW_current_depth(BMWalker *walker)
159 {
160 return walker->depth;
161 }
162
163 /**
164 * \brief Main Walking Function
165 *
166 * Steps a mesh walker forward by one element
167 */
BMW_walk(BMWalker * walker)168 void *BMW_walk(BMWalker *walker)
169 {
170 void *current = NULL;
171
172 while (BMW_current_state(walker)) {
173 current = walker->step(walker);
174 if (current) {
175 return current;
176 }
177 }
178 return NULL;
179 }
180
181 /**
182 * \brief Current Walker State
183 *
184 * Returns the first state from the walker state
185 * worklist. This state is the next in the
186 * worklist for processing.
187 */
BMW_current_state(BMWalker * walker)188 void *BMW_current_state(BMWalker *walker)
189 {
190 BMwGenericWalker *currentstate = walker->states.first;
191 if (currentstate) {
192 /* Automatic update of depth. For most walkers that
193 * follow the standard "Step" pattern of:
194 * - read current state
195 * - remove current state
196 * - push new states
197 * - return walk result from just-removed current state
198 * this simple automatic update should keep track of depth
199 * just fine. Walkers that deviate from that pattern may
200 * need to manually update the depth if they care about
201 * keeping it correct. */
202 walker->depth = currentstate->depth + 1;
203 }
204 return currentstate;
205 }
206
207 /**
208 * \brief Remove Current Walker State
209 *
210 * Remove and free an item from the end of the walker state
211 * worklist.
212 */
BMW_state_remove(BMWalker * walker)213 void BMW_state_remove(BMWalker *walker)
214 {
215 void *oldstate;
216 oldstate = BMW_current_state(walker);
217 BLI_remlink(&walker->states, oldstate);
218 BLI_mempool_free(walker->worklist, oldstate);
219 }
220
221 /**
222 * \brief Add a new Walker State
223 *
224 * Allocate a new empty state and put it on the worklist.
225 * A pointer to the new state is returned so that the caller
226 * can fill in the state data. The new state will be inserted
227 * at the front for depth-first walks, and at the end for
228 * breadth-first walks.
229 */
BMW_state_add(BMWalker * walker)230 void *BMW_state_add(BMWalker *walker)
231 {
232 BMwGenericWalker *newstate;
233 newstate = BLI_mempool_alloc(walker->worklist);
234 newstate->depth = walker->depth;
235 switch (walker->order) {
236 case BMW_DEPTH_FIRST:
237 BLI_addhead(&walker->states, newstate);
238 break;
239 case BMW_BREADTH_FIRST:
240 BLI_addtail(&walker->states, newstate);
241 break;
242 default:
243 BLI_assert(0);
244 break;
245 }
246 return newstate;
247 }
248
249 /**
250 * \brief Reset Walker
251 *
252 * Frees all states from the worklist, resetting the walker
253 * for reuse in a new walk.
254 */
BMW_reset(BMWalker * walker)255 void BMW_reset(BMWalker *walker)
256 {
257 while (BMW_current_state(walker)) {
258 BMW_state_remove(walker);
259 }
260 walker->depth = 0;
261 BLI_gset_clear(walker->visit_set, NULL);
262 BLI_gset_clear(walker->visit_set_alt, NULL);
263 }
264