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