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