Blender  V3.3
bmesh_walkers.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
9 #include <stdlib.h>
10 #include <string.h> /* for memcpy */
11 
12 #include "BLI_listbase.h"
13 #include "BLI_utildefines.h"
14 
15 #include "bmesh.h"
16 
17 #include "bmesh_walkers_private.h"
18 
40 void *BMW_begin(BMWalker *walker, void *start)
41 {
42  BLI_assert(((BMHeader *)start)->htype & walker->begin_htype);
43 
44  walker->begin(walker, start);
45 
46  return BMW_current_state(walker) ? walker->step(walker) : NULL;
47 }
48 
49 void BMW_init(BMWalker *walker,
50  BMesh *bm,
51  int type,
52  short mask_vert,
53  short mask_edge,
54  short mask_face,
55  BMWFlag flag,
56  int layer)
57 {
58  memset(walker, 0, sizeof(BMWalker));
59 
60  walker->layer = layer;
61  walker->flag = flag;
62  walker->bm = bm;
63 
64  walker->mask_vert = mask_vert;
65  walker->mask_edge = mask_edge;
66  walker->mask_face = mask_face;
67 
68  walker->visit_set = BLI_gset_ptr_new("bmesh walkers");
69  walker->visit_set_alt = BLI_gset_ptr_new("bmesh walkers sec");
70 
71  if (UNLIKELY(type >= BMW_MAXWALKERS || type < 0)) {
72  fprintf(stderr,
73  "%s: Invalid walker type in BMW_init; type: %d, "
74  "searchmask: (v:%d, e:%d, f:%d), flag: %u, layer: %d\n",
75  __func__,
76  type,
77  mask_vert,
78  mask_edge,
79  mask_face,
80  flag,
81  layer);
82  BLI_assert(0);
83  return;
84  }
85 
86  if (type != BMW_CUSTOM) {
88  walker->begin = bm_walker_types[type]->begin;
89  walker->yield = bm_walker_types[type]->yield;
90  walker->step = bm_walker_types[type]->step;
92  walker->order = bm_walker_types[type]->order;
94 
95  /* safety checks */
96  /* if this raises an error either the caller is wrong or
97  * 'bm_walker_types' needs updating */
98  BLI_assert(mask_vert == 0 || (walker->valid_mask & BM_VERT));
99  BLI_assert(mask_edge == 0 || (walker->valid_mask & BM_EDGE));
100  BLI_assert(mask_face == 0 || (walker->valid_mask & BM_FACE));
101  }
102 
103  walker->worklist = BLI_mempool_create(walker->structsize, 0, 128, BLI_MEMPOOL_NOP);
104  BLI_listbase_clear(&walker->states);
105 }
106 
107 void BMW_end(BMWalker *walker)
108 {
109  BLI_mempool_destroy(walker->worklist);
110  BLI_gset_free(walker->visit_set, NULL);
111  BLI_gset_free(walker->visit_set_alt, NULL);
112 }
113 
114 void *BMW_step(BMWalker *walker)
115 {
116  BMHeader *head;
117 
118  head = BMW_walk(walker);
119 
120  return head;
121 }
122 
124 {
125  return walker->depth;
126 }
127 
128 void *BMW_walk(BMWalker *walker)
129 {
130  void *current = NULL;
131 
132  while (BMW_current_state(walker)) {
133  current = walker->step(walker);
134  if (current) {
135  return current;
136  }
137  }
138  return NULL;
139 }
140 
142 {
143  BMwGenericWalker *currentstate = walker->states.first;
144  if (currentstate) {
145  /* Automatic update of depth. For most walkers that
146  * follow the standard "Step" pattern of:
147  * - read current state
148  * - remove current state
149  * - push new states
150  * - return walk result from just-removed current state
151  * this simple automatic update should keep track of depth
152  * just fine. Walkers that deviate from that pattern may
153  * need to manually update the depth if they care about
154  * keeping it correct. */
155  walker->depth = currentstate->depth + 1;
156  }
157  return currentstate;
158 }
159 
161 {
162  void *oldstate;
163  oldstate = BMW_current_state(walker);
164  BLI_remlink(&walker->states, oldstate);
165  BLI_mempool_free(walker->worklist, oldstate);
166 }
167 
168 void *BMW_state_add(BMWalker *walker)
169 {
170  BMwGenericWalker *newstate;
171  newstate = BLI_mempool_alloc(walker->worklist);
172  newstate->depth = walker->depth;
173  switch (walker->order) {
174  case BMW_DEPTH_FIRST:
175  BLI_addhead(&walker->states, newstate);
176  break;
177  case BMW_BREADTH_FIRST:
178  BLI_addtail(&walker->states, newstate);
179  break;
180  default:
181  BLI_assert(0);
182  break;
183  }
184  return newstate;
185 }
186 
187 void BMW_reset(BMWalker *walker)
188 {
189  while (BMW_current_state(walker)) {
190  BMW_state_remove(walker);
191  }
192  walker->depth = 0;
193  BLI_gset_clear(walker->visit_set, NULL);
195 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
GSet * BLI_gset_ptr_new(const char *info)
void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1032
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1037
void BLI_addhead(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:60
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
Definition: BLI_listbase.h:273
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
void BLI_remlink(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:100
@ BLI_MEMPOOL_NOP
Definition: BLI_mempool.h:99
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
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
Definition: BLI_mempool.c:253
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
Definition: BLI_mempool.c:319
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:707
#define UNLIKELY(x)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum type
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_EDGE
Definition: bmesh_class.h:384
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BMW_init(BMWalker *walker, BMesh *bm, int type, short mask_vert, short mask_edge, short mask_face, BMWFlag flag, int layer)
Init Walker.
Definition: bmesh_walkers.c:49
void BMW_end(BMWalker *walker)
End Walker.
void BMW_reset(BMWalker *walker)
Reset Walker.
int BMW_current_depth(BMWalker *walker)
Walker Current Depth.
void * BMW_begin(BMWalker *walker, void *start)
Definition: bmesh_walkers.c:40
void * BMW_current_state(BMWalker *walker)
Current Walker State.
void * BMW_step(BMWalker *walker)
Step Walker.
void * BMW_walk(BMWalker *walker)
Main Walking Function.
void * BMW_state_add(BMWalker *walker)
Add a new Walker State.
void BMW_state_remove(BMWalker *walker)
Remove Current Walker State.
@ BMW_DEPTH_FIRST
Definition: bmesh_walkers.h:14
@ BMW_BREADTH_FIRST
Definition: bmesh_walkers.h:15
BMWFlag
Definition: bmesh_walkers.h:18
@ BMW_CUSTOM
@ BMW_MAXWALKERS
BMWalker * bm_walker_types[]
int structsize
Definition: bmesh_walkers.h:29
struct GSet * visit_set_alt
Definition: bmesh_walkers.h:49
ListBase states
Definition: bmesh_walkers.h:38
BMWOrder order
Definition: bmesh_walkers.h:30
BMWFlag flag
Definition: bmesh_walkers.h:46
short mask_face
Definition: bmesh_walkers.h:44
int valid_mask
Definition: bmesh_walkers.h:31
struct GSet * visit_set
Definition: bmesh_walkers.h:48
BMesh * bm
Definition: bmesh_walkers.h:36
short mask_edge
Definition: bmesh_walkers.h:43
short mask_vert
Definition: bmesh_walkers.h:42
char begin_htype
Definition: bmesh_walkers.h:25
BLI_mempool * worklist
Definition: bmesh_walkers.h:37
void *(* yield)(struct BMWalker *walker)
Definition: bmesh_walkers.h:28
void(* begin)(struct BMWalker *walker, void *start)
Definition: bmesh_walkers.h:26
void *(* step)(struct BMWalker *walker)
Definition: bmesh_walkers.h:27
void * first
Definition: DNA_listBase.h:31