Blender V5.3
bmesh_walkers.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
29
30#include <cstdlib>
31#include <cstring> /* For `memcpy`. */
32
33#include "BLI_listbase.hh"
34#include "BLI_utildefines.hh"
35
36#include "bmesh.hh"
37
39
40namespace blender {
41
42void *BMW_begin(BMWalker *walker, void *start)
43{
44 BLI_assert(((BMHeader *)start)->htype & walker->begin_htype);
45
46 walker->begin(walker, start);
47
48 return BMW_current_state(walker) ? walker->step(walker) : nullptr;
49}
50
51void BMW_init(BMWalker *walker,
52 BMesh *bm,
53 int type,
54 short mask_vert,
55 short mask_edge,
56 short mask_face,
57 BMWFlag flag,
58 int layer,
59 BMWDelimitFlag delimit)
60{
61 memset(walker, 0, sizeof(BMWalker));
62
63 walker->layer = layer;
64 walker->flag = flag;
65 walker->delimit = delimit;
66 walker->bm = bm;
67
68 walker->mask_vert = mask_vert;
69 walker->mask_edge = mask_edge;
70 walker->mask_face = mask_face;
71
72 walker->visit_set = MEM_new<Set<const void *>>("bmesh walkers");
73 walker->visit_set_alt = MEM_new<Set<const void *>>("bmesh walkers sec");
74
75 if (type >= BMW_MAXWALKERS || type < 0) [[unlikely]] {
76 fprintf(stderr,
77 "%s: Invalid walker type in BMW_init; type: %d, "
78 "searchmask: (v:%d, e:%d, f:%d), flag: %d, layer: %d\n",
79 __func__,
80 type,
81 mask_vert,
82 mask_edge,
83 mask_face,
84 flag,
85 layer);
86 BLI_assert(0);
87 return;
88 }
89
90 if (type != BMW_CUSTOM) {
92 walker->begin = bm_walker_types[type]->begin;
93 walker->yield = bm_walker_types[type]->yield;
94 walker->step = bm_walker_types[type]->step;
95 walker->structsize = bm_walker_types[type]->structsize;
96 walker->order = bm_walker_types[type]->order;
97 walker->valid_mask = bm_walker_types[type]->valid_mask;
99
100 /* safety checks */
101 /* if this raises an error either the caller is wrong or
102 * 'bm_walker_types' needs updating */
103 BLI_assert(mask_vert == 0 || (walker->valid_mask & BM_VERT));
104 BLI_assert(mask_edge == 0 || (walker->valid_mask & BM_EDGE));
105 BLI_assert(mask_face == 0 || (walker->valid_mask & BM_FACE));
106 BLI_assert((delimit & ~walker->delimit_supported) == 0);
107 }
108
109 walker->worklist = BLI_mempool_create(walker->structsize, 0, 128, BLI_MEMPOOL_NOP);
110 walker->states.clear_no_delete();
111}
112
113void BMW_end(BMWalker *walker)
114{
116 MEM_delete(walker->visit_set);
117 MEM_delete(walker->visit_set_alt);
118}
119
120void *BMW_step(BMWalker *walker)
121{
122 BMHeader *head;
123
124 head = static_cast<BMHeader *>(BMW_walk(walker));
125
126 return head;
127}
128
130{
131 return walker->depth;
132}
133
134void *BMW_walk(BMWalker *walker)
135{
136 void *current = nullptr;
137
138 while (BMW_current_state(walker)) {
139 current = walker->step(walker);
140 if (current) {
141 return current;
142 }
143 }
144 return nullptr;
145}
146
148{
149 BMwGenericWalker *currentstate = walker->states.first();
150 if (currentstate) {
151 /* Automatic update of depth. For most walkers that
152 * follow the standard "Step" pattern of:
153 * - read current state
154 * - remove current state
155 * - push new states
156 * - return walk result from just-removed current state
157 * this simple automatic update should keep track of depth
158 * just fine. Walkers that deviate from that pattern may
159 * need to manually update the depth if they care about
160 * keeping it correct. */
161 walker->depth = currentstate->depth + 1;
162 }
163 return currentstate;
164}
165
167{
168 void *oldstate;
169 oldstate = BMW_current_state(walker);
170 BLI_remlink(&walker->states, oldstate);
171 BLI_mempool_free(walker->worklist, oldstate);
172}
173
175{
176 BMwGenericWalker *newstate;
177 newstate = static_cast<BMwGenericWalker *>(BLI_mempool_alloc(walker->worklist));
178 newstate->depth = walker->depth;
179 switch (walker->order) {
180 case BMW_DEPTH_FIRST:
181 BLI_addhead(&walker->states, newstate);
182 break;
184 BLI_addtail(&walker->states, newstate);
185 break;
186 default:
187 BLI_assert(0);
188 break;
189 }
190 return newstate;
191}
192
193void BMW_reset(BMWalker *walker)
194{
195 while (BMW_current_state(walker)) {
196 BMW_state_remove(walker);
197 }
198 walker->depth = 0;
199 walker->visit_set->clear();
200 walker->visit_set_alt->clear();
201}
202
203} // namespace blender
void clear()
Definition BLI_set.hh:570
#define layer
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BLI_addhead(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:98
void BMW_state_remove(BMWalker *walker)
Remove Current Walker State.
void * BMW_begin(BMWalker *walker, void *start)
void BMW_init(BMWalker *walker, BMesh *bm, int type, short mask_vert, short mask_edge, short mask_face, BMWFlag flag, int layer, BMWDelimitFlag delimit)
Initialize Walker.
@ BMW_BREADTH_FIRST
void * BMW_state_add(BMWalker *walker)
Add a new Walker State.
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
void * BMW_current_state(BMWalker *walker)
Current Walker State.
void BMW_end(BMWalker *walker)
End Walker.
void BLI_remlink(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:138
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
int BMW_current_depth(BMWalker *walker)
Walker Current Depth.
void BLI_addtail(ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition listbase.cc:118
const BMWalker * bm_walker_types[]
@ BLI_MEMPOOL_NOP
void BMW_reset(BMWalker *walker)
Reset Walker.
void * BMW_step(BMWalker *walker)
Step Walker.
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
void * BMW_walk(BMWalker *walker)
Main Walking Function.
void(*) begin(struct BMWalker *walker, void *start)
Set< const void * > * visit_set
BMWDelimitFlag delimit
ListBaseT< BMwGenericWalker > states
void *(*) yield(struct BMWalker *walker)
Set< const void * > * visit_set_alt
void *(*) step(struct BMWalker *walker)
BLI_mempool * worklist
BMWDelimitFlag delimit_supported