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 bli
19 *
20 * An (edge -> pointer) hash table.
21 * Using unordered int-pairs as keys.
22 *
23 * \note The API matches BLI_ghash.c, but the implementation is different.
24 */
25
26 #include <limits.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_edgehash.h"
33 #include "BLI_strict_flags.h"
34 #include "BLI_utildefines.h"
35
36 typedef struct _EdgeHash_Edge Edge;
37 typedef struct _EdgeHash_Entry EdgeHashEntry;
38
39 typedef struct EdgeHash {
40 EdgeHashEntry *entries;
41 int32_t *map;
42 uint32_t slot_mask;
43 uint capacity_exp;
44 uint length;
45 uint dummy_count;
46 } EdgeHash;
47
48 typedef struct EdgeSet {
49 Edge *entries;
50 int32_t *map;
51 uint32_t slot_mask;
52 uint capacity_exp;
53 uint length;
54 } EdgeSet;
55
56 /* -------------------------------------------------------------------- */
57 /** \name Internal Helper Macros & Defines
58 * \{ */
59
60 #define ENTRIES_CAPACITY(container) (uint)(1 << (container)->capacity_exp)
61 #define MAP_CAPACITY(container) (uint)(1 << ((container)->capacity_exp + 1))
62 #define CLEAR_MAP(container) \
63 memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container))
64 #define UPDATE_SLOT_MASK(container) \
65 { \
66 (container)->slot_mask = MAP_CAPACITY(container) - 1; \
67 } \
68 ((void)0)
69 #define PERTURB_SHIFT 5
70
71 #define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX) \
72 uint32_t hash = calc_edge_hash(EDGE); \
73 uint32_t mask = (CONTAINER)->slot_mask; \
74 uint32_t perturb = hash; \
75 int32_t *map = (CONTAINER)->map; \
76 uint32_t SLOT = mask & hash; \
77 int INDEX = map[SLOT]; \
78 for (;; SLOT = mask & ((5 * SLOT) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX = map[SLOT])
79
80 #define SLOT_EMPTY -1
81 #define SLOT_DUMMY -2
82
83 #define CAPACITY_EXP_DEFAULT 3
84
85 /** \} */
86
87 /* -------------------------------------------------------------------- */
88 /** \name Internal Edge API
89 * \{ */
90
calc_edge_hash(Edge edge)91 BLI_INLINE uint32_t calc_edge_hash(Edge edge)
92 {
93 return (edge.v_low << 8) ^ edge.v_high;
94 }
95
init_edge(uint v0,uint v1)96 BLI_INLINE Edge init_edge(uint v0, uint v1)
97 {
98 /* If there are use cases where we need this it could be removed (or flag to allow),
99 * for now this helps avoid incorrect usage (creating degenerate geometry). */
100 BLI_assert(v0 != v1);
101 Edge edge;
102 if (v0 < v1) {
103 edge.v_low = v0;
104 edge.v_high = v1;
105 }
106 else {
107 edge.v_low = v1;
108 edge.v_high = v0;
109 }
110 return edge;
111 }
112
edges_equal(Edge e1,Edge e2)113 BLI_INLINE bool edges_equal(Edge e1, Edge e2)
114 {
115 return memcmp(&e1, &e2, sizeof(Edge)) == 0;
116 }
117
calc_capacity_exp_for_reserve(uint reserve)118 static uint calc_capacity_exp_for_reserve(uint reserve)
119 {
120 uint result = 1;
121 while (reserve >>= 1) {
122 result++;
123 }
124 return result;
125 }
126
127 /** \} */
128
129 /* -------------------------------------------------------------------- */
130 /** \name Internal Utility API
131 * \{ */
132
133 #define EH_INDEX_HAS_EDGE(eh, index, edge) \
134 ((index) >= 0 && edges_equal((edge), (eh)->entries[index].edge))
135
edgehash_free_values(EdgeHash * eh,EdgeHashFreeFP free_value)136 static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value)
137 {
138 if (free_value) {
139 for (uint i = 0; i < eh->length; i++) {
140 free_value(eh->entries[i].value);
141 }
142 }
143 }
144
edgehash_insert_index(EdgeHash * eh,Edge edge,uint entry_index)145 BLI_INLINE void edgehash_insert_index(EdgeHash *eh, Edge edge, uint entry_index)
146 {
147 ITER_SLOTS (eh, edge, slot, index) {
148 if (index == SLOT_EMPTY) {
149 eh->map[slot] = (int32_t)entry_index;
150 break;
151 }
152 }
153 }
154
edgehash_insert_at_slot(EdgeHash * eh,uint slot,Edge edge,void * value)155 BLI_INLINE EdgeHashEntry *edgehash_insert_at_slot(EdgeHash *eh, uint slot, Edge edge, void *value)
156 {
157 EdgeHashEntry *entry = &eh->entries[eh->length];
158 entry->edge = edge;
159 entry->value = value;
160 eh->map[slot] = (int32_t)eh->length;
161 eh->length++;
162 return entry;
163 }
164
edgehash_ensure_can_insert(EdgeHash * eh)165 BLI_INLINE bool edgehash_ensure_can_insert(EdgeHash *eh)
166 {
167 if (UNLIKELY(ENTRIES_CAPACITY(eh) <= eh->length + eh->dummy_count)) {
168 eh->capacity_exp++;
169 UPDATE_SLOT_MASK(eh);
170 eh->dummy_count = 0;
171 eh->entries = MEM_reallocN(eh->entries, sizeof(EdgeHashEntry) * ENTRIES_CAPACITY(eh));
172 eh->map = MEM_reallocN(eh->map, sizeof(int32_t) * MAP_CAPACITY(eh));
173 CLEAR_MAP(eh);
174 for (uint i = 0; i < eh->length; i++) {
175 edgehash_insert_index(eh, eh->entries[i].edge, i);
176 }
177 return true;
178 }
179 return false;
180 }
181
edgehash_insert(EdgeHash * eh,Edge edge,void * value)182 BLI_INLINE EdgeHashEntry *edgehash_insert(EdgeHash *eh, Edge edge, void *value)
183 {
184 ITER_SLOTS (eh, edge, slot, index) {
185 if (index == SLOT_EMPTY) {
186 return edgehash_insert_at_slot(eh, slot, edge, value);
187 }
188 if (index == SLOT_DUMMY) {
189 eh->dummy_count--;
190 return edgehash_insert_at_slot(eh, slot, edge, value);
191 }
192 }
193 }
194
edgehash_lookup_entry(EdgeHash * eh,uint v0,uint v1)195 BLI_INLINE EdgeHashEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1)
196 {
197 Edge edge = init_edge(v0, v1);
198
199 ITER_SLOTS (eh, edge, slot, index) {
200 if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
201 return &eh->entries[index];
202 }
203 if (index == SLOT_EMPTY) {
204 return NULL;
205 }
206 }
207 }
208
edgehash_change_index(EdgeHash * eh,Edge edge,int new_index)209 BLI_INLINE void edgehash_change_index(EdgeHash *eh, Edge edge, int new_index)
210 {
211 ITER_SLOTS (eh, edge, slot, index) {
212 if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
213 eh->map[slot] = new_index;
214 break;
215 }
216 }
217 }
218
219 /** \} */
220
221 /* -------------------------------------------------------------------- */
222 /** \name Edge Hash API
223 * \{ */
224
BLI_edgehash_new_ex(const char * info,const uint reserve)225 EdgeHash *BLI_edgehash_new_ex(const char *info, const uint reserve)
226 {
227 EdgeHash *eh = MEM_mallocN(sizeof(EdgeHash), info);
228 eh->capacity_exp = calc_capacity_exp_for_reserve(reserve);
229 UPDATE_SLOT_MASK(eh);
230 eh->length = 0;
231 eh->dummy_count = 0;
232 eh->entries = MEM_calloc_arrayN(sizeof(EdgeHashEntry), ENTRIES_CAPACITY(eh), "eh entries");
233 eh->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(eh), "eh map");
234 CLEAR_MAP(eh);
235 return eh;
236 }
237
BLI_edgehash_new(const char * info)238 EdgeHash *BLI_edgehash_new(const char *info)
239 {
240 return BLI_edgehash_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
241 }
242
BLI_edgehash_free(EdgeHash * eh,EdgeHashFreeFP free_value)243 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value)
244 {
245 edgehash_free_values(eh, free_value);
246 MEM_freeN(eh->map);
247 MEM_freeN(eh->entries);
248 MEM_freeN(eh);
249 }
250
BLI_edgehash_print(EdgeHash * eh)251 void BLI_edgehash_print(EdgeHash *eh)
252 {
253 printf("Edgehash at %p:\n", eh);
254 printf(" Map:\n");
255 for (uint i = 0; i < MAP_CAPACITY(eh); i++) {
256 int index = eh->map[i];
257 printf(" %u: %d", i, index);
258 if (index >= 0) {
259 EdgeHashEntry entry = eh->entries[index];
260 printf(" -> (%u, %u) -> %p", entry.edge.v_low, entry.edge.v_high, entry.value);
261 }
262 printf("\n");
263 }
264 printf(" Entries:\n");
265 for (uint i = 0; i < ENTRIES_CAPACITY(eh); i++) {
266 if (i == eh->length) {
267 printf(" **** below is rest capacity ****\n");
268 }
269 EdgeHashEntry entry = eh->entries[i];
270 printf(" %u: (%u, %u) -> %p\n", i, entry.edge.v_low, entry.edge.v_high, entry.value);
271 }
272 }
273
274 /**
275 * Insert edge (\a v0, \a v1) into hash with given value, does
276 * not check for duplicates.
277 */
BLI_edgehash_insert(EdgeHash * eh,uint v0,uint v1,void * value)278 void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *value)
279 {
280 edgehash_ensure_can_insert(eh);
281 Edge edge = init_edge(v0, v1);
282 edgehash_insert(eh, edge, value);
283 }
284
285 /**
286 * Assign a new value to a key that may already be in edgehash.
287 */
BLI_edgehash_reinsert(EdgeHash * eh,uint v0,uint v1,void * value)288 bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *value)
289 {
290 Edge edge = init_edge(v0, v1);
291
292 ITER_SLOTS (eh, edge, slot, index) {
293 if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
294 eh->entries[index].value = value;
295 return false;
296 }
297 if (index == SLOT_EMPTY) {
298 if (edgehash_ensure_can_insert(eh)) {
299 edgehash_insert(eh, edge, value);
300 }
301 else {
302 edgehash_insert_at_slot(eh, slot, edge, value);
303 }
304 return true;
305 }
306 }
307 }
308
309 /**
310 * A version of #BLI_edgehash_lookup which accepts a fallback argument.
311 */
BLI_edgehash_lookup_default(EdgeHash * eh,uint v0,uint v1,void * default_value)312 void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *default_value)
313 {
314 EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
315 return entry ? entry->value : default_value;
316 }
317
318 /**
319 * Return value for given edge (\a v0, \a v1), or NULL if
320 * if key does not exist in hash. (If need exists
321 * to differentiate between key-value being NULL and
322 * lack of key then see #BLI_edgehash_lookup_p().
323 */
BLI_edgehash_lookup(EdgeHash * eh,uint v0,uint v1)324 void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1)
325 {
326 EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
327 return entry ? entry->value : NULL;
328 }
329
330 /**
331 * Return pointer to value for given edge (\a v0, \a v1),
332 * or NULL if key does not exist in hash.
333 */
BLI_edgehash_lookup_p(EdgeHash * eh,uint v0,uint v1)334 void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1)
335 {
336 EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
337 return entry ? &entry->value : NULL;
338 }
339
340 /**
341 * Ensure \a (v0, v1) is exists in \a eh.
342 *
343 * This handles the common situation where the caller needs ensure a key is added to \a eh,
344 * constructing a new value in the case the key isn't found.
345 * Otherwise use the existing value.
346 *
347 * Such situations typically incur multiple lookups, however this function
348 * avoids them by ensuring the key is added,
349 * returning a pointer to the value so it can be used or initialized by the caller.
350 *
351 * \returns true when the value didn't need to be added.
352 * (when false, the caller _must_ initialize the value).
353 */
BLI_edgehash_ensure_p(EdgeHash * eh,uint v0,uint v1,void *** r_value)354 bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_value)
355 {
356 Edge edge = init_edge(v0, v1);
357
358 ITER_SLOTS (eh, edge, slot, index) {
359 if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
360 *r_value = &eh->entries[index].value;
361 return true;
362 }
363 if (index == SLOT_EMPTY) {
364 if (edgehash_ensure_can_insert(eh)) {
365 *r_value = &edgehash_insert(eh, edge, NULL)->value;
366 }
367 else {
368 *r_value = &edgehash_insert_at_slot(eh, slot, edge, NULL)->value;
369 }
370 return false;
371 }
372 }
373 }
374
375 /**
376 * Remove \a key (v0, v1) from \a eh, or return false if the key wasn't found.
377 *
378 * \param v0, v1: The key to remove.
379 * \param free_value: Optional callback to free the value.
380 * \return true if \a key was removed from \a eh.
381 */
BLI_edgehash_remove(EdgeHash * eh,uint v0,uint v1,EdgeHashFreeFP free_value)382 bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP free_value)
383 {
384 uint old_length = eh->length;
385 void *value = BLI_edgehash_popkey(eh, v0, v1);
386 if (free_value && value) {
387 free_value(value);
388 }
389 return old_length > eh->length;
390 }
391
392 /* same as above but return the value,
393 * no free value argument since it will be returned */
394 /**
395 * Remove \a key (v0, v1) from \a eh, returning the value or NULL if the key wasn't found.
396 *
397 * \param v0, v1: The key to remove.
398 * \return the value of \a key int \a eh or NULL.
399 */
BLI_edgehash_popkey(EdgeHash * eh,uint v0,uint v1)400 void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1)
401 {
402 Edge edge = init_edge(v0, v1);
403
404 ITER_SLOTS (eh, edge, slot, index) {
405 if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
406 void *value = eh->entries[index].value;
407 eh->length--;
408 eh->dummy_count++;
409 eh->map[slot] = SLOT_DUMMY;
410 eh->entries[index] = eh->entries[eh->length];
411 if ((uint)index < eh->length) {
412 edgehash_change_index(eh, eh->entries[index].edge, index);
413 }
414 return value;
415 }
416 if (index == SLOT_EMPTY) {
417 return NULL;
418 }
419 }
420 }
421
422 /**
423 * Return boolean true/false if edge (v0,v1) in hash.
424 */
BLI_edgehash_haskey(EdgeHash * eh,uint v0,uint v1)425 bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1)
426 {
427 return edgehash_lookup_entry(eh, v0, v1) != NULL;
428 }
429
430 /**
431 * Return number of keys in hash.
432 */
BLI_edgehash_len(EdgeHash * eh)433 int BLI_edgehash_len(EdgeHash *eh)
434 {
435 return (int)eh->length;
436 }
437
438 /**
439 * Remove all edges from hash.
440 */
BLI_edgehash_clear_ex(EdgeHash * eh,EdgeHashFreeFP free_value,const uint UNUSED (reserve))441 void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP free_value, const uint UNUSED(reserve))
442 {
443 /* TODO: handle reserve */
444 edgehash_free_values(eh, free_value);
445 eh->length = 0;
446 eh->dummy_count = 0;
447 eh->capacity_exp = CAPACITY_EXP_DEFAULT;
448 CLEAR_MAP(eh);
449 }
450
451 /**
452 * Wraps #BLI_edgehash_clear_ex with zero entries reserved.
453 */
BLI_edgehash_clear(EdgeHash * eh,EdgeHashFreeFP free_value)454 void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP free_value)
455 {
456 BLI_edgehash_clear_ex(eh, free_value, 0);
457 }
458
459 /** \} */
460
461 /* -------------------------------------------------------------------- */
462 /** \name Edge Hash Iterator API
463 * \{ */
464
465 /**
466 * Create a new EdgeHashIterator. The hash table must not be mutated
467 * while the iterator is in use, and the iterator will step exactly
468 * BLI_edgehash_len(eh) times before becoming done.
469 */
BLI_edgehashIterator_new(EdgeHash * eh)470 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
471 {
472 EdgeHashIterator *ehi = MEM_mallocN(sizeof(EdgeHashIterator), __func__);
473 BLI_edgehashIterator_init(ehi, eh);
474 return ehi;
475 }
476
477 /**
478 * Init an already allocated EdgeHashIterator. The hash table must not
479 * be mutated while the iterator is in use, and the iterator will
480 * step exactly BLI_edgehash_len(eh) times before becoming done.
481 *
482 * \param ehi: The EdgeHashIterator to initialize.
483 * \param eh: The EdgeHash to iterate over.
484 */
BLI_edgehashIterator_init(EdgeHashIterator * ehi,EdgeHash * eh)485 void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh)
486 {
487 ehi->entries = eh->entries;
488 ehi->length = eh->length;
489 ehi->index = 0;
490 }
491
492 /**
493 * Free an EdgeHashIterator.
494 */
BLI_edgehashIterator_free(EdgeHashIterator * ehi)495 void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
496 {
497 MEM_freeN(ehi);
498 }
499
500 /** \} */
501
502 /* -------------------------------------------------------------------- */
503 /** \name EdgeSet API
504 *
505 * Use edgehash API to give 'set' functionality
506 * \{ */
507
508 #define ES_INDEX_HAS_EDGE(es, index, edge) \
509 (index) >= 0 && edges_equal((edge), (es)->entries[index])
510
BLI_edgeset_new_ex(const char * info,const uint reserve)511 EdgeSet *BLI_edgeset_new_ex(const char *info, const uint reserve)
512 {
513 EdgeSet *es = MEM_mallocN(sizeof(EdgeSet), info);
514 es->capacity_exp = calc_capacity_exp_for_reserve(reserve);
515 UPDATE_SLOT_MASK(es);
516 es->length = 0;
517 es->entries = MEM_malloc_arrayN(sizeof(Edge), ENTRIES_CAPACITY(es), "es entries");
518 es->map = MEM_malloc_arrayN(sizeof(int32_t), MAP_CAPACITY(es), "es map");
519 CLEAR_MAP(es);
520 return es;
521 }
522
BLI_edgeset_new(const char * info)523 EdgeSet *BLI_edgeset_new(const char *info)
524 {
525 return BLI_edgeset_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
526 }
527
BLI_edgeset_free(EdgeSet * es)528 void BLI_edgeset_free(EdgeSet *es)
529 {
530 MEM_freeN(es->entries);
531 MEM_freeN(es->map);
532 MEM_freeN(es);
533 }
534
BLI_edgeset_len(EdgeSet * es)535 int BLI_edgeset_len(EdgeSet *es)
536 {
537 return (int)es->length;
538 }
539
edgeset_insert_index(EdgeSet * es,Edge edge,uint entry_index)540 static void edgeset_insert_index(EdgeSet *es, Edge edge, uint entry_index)
541 {
542 ITER_SLOTS (es, edge, slot, index) {
543 if (index == SLOT_EMPTY) {
544 es->map[slot] = (int)entry_index;
545 break;
546 }
547 }
548 }
549
edgeset_ensure_can_insert(EdgeSet * es)550 BLI_INLINE void edgeset_ensure_can_insert(EdgeSet *es)
551 {
552 if (UNLIKELY(ENTRIES_CAPACITY(es) <= es->length)) {
553 es->capacity_exp++;
554 UPDATE_SLOT_MASK(es);
555 es->entries = MEM_reallocN(es->entries, sizeof(Edge) * ENTRIES_CAPACITY(es));
556 es->map = MEM_reallocN(es->map, sizeof(int32_t) * MAP_CAPACITY(es));
557 CLEAR_MAP(es);
558 for (uint i = 0; i < es->length; i++) {
559 edgeset_insert_index(es, es->entries[i], i);
560 }
561 }
562 }
563
edgeset_insert_at_slot(EdgeSet * es,uint slot,Edge edge)564 BLI_INLINE void edgeset_insert_at_slot(EdgeSet *es, uint slot, Edge edge)
565 {
566 es->entries[es->length] = edge;
567 es->map[slot] = (int)es->length;
568 es->length++;
569 }
570
571 /**
572 * A version of BLI_edgeset_insert which checks first if the key is in the set.
573 * \returns true if a new key has been added.
574 *
575 * \note EdgeHash has no equivalent to this because typically the value would be different.
576 */
BLI_edgeset_add(EdgeSet * es,uint v0,uint v1)577 bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1)
578 {
579 edgeset_ensure_can_insert(es);
580 Edge edge = init_edge(v0, v1);
581
582 ITER_SLOTS (es, edge, slot, index) {
583 if (ES_INDEX_HAS_EDGE(es, index, edge)) {
584 return false;
585 }
586 if (index == SLOT_EMPTY) {
587 edgeset_insert_at_slot(es, slot, edge);
588 return true;
589 }
590 }
591 }
592
593 /**
594 * Adds the key to the set (no checks for unique keys!).
595 * Matching #BLI_edgehash_insert
596 */
BLI_edgeset_insert(EdgeSet * es,uint v0,uint v1)597 void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
598 {
599 edgeset_ensure_can_insert(es);
600 Edge edge = init_edge(v0, v1);
601
602 ITER_SLOTS (es, edge, slot, index) {
603 if (index == SLOT_EMPTY) {
604 edgeset_insert_at_slot(es, slot, edge);
605 return;
606 }
607 }
608 }
609
BLI_edgeset_haskey(EdgeSet * es,uint v0,uint v1)610 bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1)
611 {
612 Edge edge = init_edge(v0, v1);
613
614 ITER_SLOTS (es, edge, slot, index) {
615 if (ES_INDEX_HAS_EDGE(es, index, edge)) {
616 return true;
617 }
618 if (index == SLOT_EMPTY) {
619 return false;
620 }
621 }
622 }
623
BLI_edgesetIterator_new(EdgeSet * es)624 EdgeSetIterator *BLI_edgesetIterator_new(EdgeSet *es)
625 {
626 EdgeSetIterator *esi = MEM_mallocN(sizeof(EdgeSetIterator), __func__);
627 esi->edges = es->entries;
628 esi->length = es->length;
629 esi->index = 0;
630 return esi;
631 }
632
BLI_edgesetIterator_free(EdgeSetIterator * esi)633 void BLI_edgesetIterator_free(EdgeSetIterator *esi)
634 {
635 MEM_freeN(esi);
636 }
637
638 /** \} */
639