Blender  V3.3
edgehash.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
12 #include <limits.h>
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 
17 #include "MEM_guardedalloc.h"
18 
19 #include "BLI_edgehash.h"
20 #include "BLI_strict_flags.h"
21 #include "BLI_utildefines.h"
22 
23 typedef struct _EdgeHash_Edge Edge;
24 typedef struct _EdgeHash_Entry EdgeHashEntry;
25 
26 typedef struct EdgeHash {
34 
35 typedef struct EdgeSet {
42 
43 /* -------------------------------------------------------------------- */
47 #define ENTRIES_CAPACITY(container) (uint)(1 << (container)->capacity_exp)
48 #define MAP_CAPACITY(container) (uint)(1 << ((container)->capacity_exp + 1))
49 #define CLEAR_MAP(container) \
50  memset((container)->map, 0xFF, sizeof(int32_t) * MAP_CAPACITY(container))
51 #define UPDATE_SLOT_MASK(container) \
52  { \
53  (container)->slot_mask = MAP_CAPACITY(container) - 1; \
54  } \
55  ((void)0)
56 #define PERTURB_SHIFT 5
57 
58 #define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX) \
59  uint32_t hash = calc_edge_hash(EDGE); \
60  uint32_t mask = (CONTAINER)->slot_mask; \
61  uint32_t perturb = hash; \
62  int32_t *map = (CONTAINER)->map; \
63  uint32_t SLOT = mask & hash; \
64  int INDEX = map[SLOT]; \
65  for (;; SLOT = mask & ((5 * SLOT) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX = map[SLOT])
66 
67 #define SLOT_EMPTY -1
68 #define SLOT_DUMMY -2
69 
70 #define CAPACITY_EXP_DEFAULT 3
71 
74 /* -------------------------------------------------------------------- */
79 {
80  return (edge.v_low << 8) ^ edge.v_high;
81 }
82 
84 {
85  /* If there are use cases where we need this it could be removed (or flag to allow),
86  * for now this helps avoid incorrect usage (creating degenerate geometry). */
87  BLI_assert(v0 != v1);
88  Edge edge;
89  if (v0 < v1) {
90  edge.v_low = v0;
91  edge.v_high = v1;
92  }
93  else {
94  edge.v_low = v1;
95  edge.v_high = v0;
96  }
97  return edge;
98 }
99 
101 {
102  return memcmp(&e1, &e2, sizeof(Edge)) == 0;
103 }
104 
106 {
107  uint result = 1;
108  while (reserve >>= 1) {
109  result++;
110  }
111  return result;
112 }
113 
116 /* -------------------------------------------------------------------- */
120 #define EH_INDEX_HAS_EDGE(eh, index, edge) \
121  ((index) >= 0 && edges_equal((edge), (eh)->entries[index].edge))
122 
123 static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value)
124 {
125  if (free_value) {
126  for (uint i = 0; i < eh->length; i++) {
127  free_value(eh->entries[i].value);
128  }
129  }
130 }
131 
132 BLI_INLINE void edgehash_insert_index(EdgeHash *eh, Edge edge, uint entry_index)
133 {
134  ITER_SLOTS (eh, edge, slot, index) {
135  if (index == SLOT_EMPTY) {
136  eh->map[slot] = (int32_t)entry_index;
137  break;
138  }
139  }
140 }
141 
143 {
144  EdgeHashEntry *entry = &eh->entries[eh->length];
145  entry->edge = edge;
146  entry->value = value;
147  eh->map[slot] = (int32_t)eh->length;
148  eh->length++;
149  return entry;
150 }
151 
153 {
154  if (UNLIKELY(ENTRIES_CAPACITY(eh) <= eh->length + eh->dummy_count)) {
155  eh->capacity_exp++;
156  UPDATE_SLOT_MASK(eh);
157  eh->dummy_count = 0;
158  eh->entries = MEM_reallocN(eh->entries, sizeof(EdgeHashEntry) * ENTRIES_CAPACITY(eh));
159  eh->map = MEM_reallocN(eh->map, sizeof(int32_t) * MAP_CAPACITY(eh));
160  CLEAR_MAP(eh);
161  for (uint i = 0; i < eh->length; i++) {
162  edgehash_insert_index(eh, eh->entries[i].edge, i);
163  }
164  return true;
165  }
166  return false;
167 }
168 
170 {
171  ITER_SLOTS (eh, edge, slot, index) {
172  if (index == SLOT_EMPTY) {
173  return edgehash_insert_at_slot(eh, slot, edge, value);
174  }
175  if (index == SLOT_DUMMY) {
176  eh->dummy_count--;
177  return edgehash_insert_at_slot(eh, slot, edge, value);
178  }
179  }
180 }
181 
183 {
184  Edge edge = init_edge(v0, v1);
185 
186  ITER_SLOTS (eh, edge, slot, index) {
187  if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
188  return &eh->entries[index];
189  }
190  if (index == SLOT_EMPTY) {
191  return NULL;
192  }
193  }
194 }
195 
196 BLI_INLINE void edgehash_change_index(EdgeHash *eh, Edge edge, int new_index)
197 {
198  ITER_SLOTS (eh, edge, slot, index) {
199  if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
200  eh->map[slot] = new_index;
201  break;
202  }
203  }
204 }
205 
208 /* -------------------------------------------------------------------- */
212 EdgeHash *BLI_edgehash_new_ex(const char *info, const uint reserve)
213 {
214  EdgeHash *eh = MEM_mallocN(sizeof(EdgeHash), info);
216  UPDATE_SLOT_MASK(eh);
217  eh->length = 0;
218  eh->dummy_count = 0;
219  eh->entries = MEM_calloc_arrayN(ENTRIES_CAPACITY(eh), sizeof(EdgeHashEntry), "eh entries");
220  eh->map = MEM_malloc_arrayN(MAP_CAPACITY(eh), sizeof(int32_t), "eh map");
221  CLEAR_MAP(eh);
222  return eh;
223 }
224 
225 EdgeHash *BLI_edgehash_new(const char *info)
226 {
227  return BLI_edgehash_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
228 }
229 
231 {
232  edgehash_free_values(eh, free_value);
233  MEM_freeN(eh->map);
234  MEM_freeN(eh->entries);
235  MEM_freeN(eh);
236 }
237 
239 {
240  printf("Edgehash at %p:\n", eh);
241  printf(" Map:\n");
242  for (uint i = 0; i < MAP_CAPACITY(eh); i++) {
243  int index = eh->map[i];
244  printf(" %u: %d", i, index);
245  if (index >= 0) {
246  EdgeHashEntry entry = eh->entries[index];
247  printf(" -> (%u, %u) -> %p", entry.edge.v_low, entry.edge.v_high, entry.value);
248  }
249  printf("\n");
250  }
251  printf(" Entries:\n");
252  for (uint i = 0; i < ENTRIES_CAPACITY(eh); i++) {
253  if (i == eh->length) {
254  printf(" **** below is rest capacity ****\n");
255  }
256  EdgeHashEntry entry = eh->entries[i];
257  printf(" %u: (%u, %u) -> %p\n", i, entry.edge.v_low, entry.edge.v_high, entry.value);
258  }
259 }
260 
261 void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *value)
262 {
264  Edge edge = init_edge(v0, v1);
265  edgehash_insert(eh, edge, value);
266 }
267 
268 bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *value)
269 {
270  Edge edge = init_edge(v0, v1);
271 
272  ITER_SLOTS (eh, edge, slot, index) {
273  if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
274  eh->entries[index].value = value;
275  return false;
276  }
277  if (index == SLOT_EMPTY) {
278  if (edgehash_ensure_can_insert(eh)) {
279  edgehash_insert(eh, edge, value);
280  }
281  else {
282  edgehash_insert_at_slot(eh, slot, edge, value);
283  }
284  return true;
285  }
286  }
287 }
288 
289 void *BLI_edgehash_lookup_default(const EdgeHash *eh, uint v0, uint v1, void *default_value)
290 {
291  EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
292  return entry ? entry->value : default_value;
293 }
294 
295 void *BLI_edgehash_lookup(const EdgeHash *eh, uint v0, uint v1)
296 {
297  EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
298  return entry ? entry->value : NULL;
299 }
300 
302 {
303  EdgeHashEntry *entry = edgehash_lookup_entry(eh, v0, v1);
304  return entry ? &entry->value : NULL;
305 }
306 
307 bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_value)
308 {
309  Edge edge = init_edge(v0, v1);
310 
311  ITER_SLOTS (eh, edge, slot, index) {
312  if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
313  *r_value = &eh->entries[index].value;
314  return true;
315  }
316  if (index == SLOT_EMPTY) {
317  if (edgehash_ensure_can_insert(eh)) {
318  *r_value = &edgehash_insert(eh, edge, NULL)->value;
319  }
320  else {
321  *r_value = &edgehash_insert_at_slot(eh, slot, edge, NULL)->value;
322  }
323  return false;
324  }
325  }
326 }
327 
329 {
330  uint old_length = eh->length;
331  void *value = BLI_edgehash_popkey(eh, v0, v1);
332  if (free_value && value) {
333  free_value(value);
334  }
335  return old_length > eh->length;
336 }
337 
339 {
340  /* Same as #BLI_edgehash_remove but return the value,
341  * no free value argument since it will be returned */
342 
343  Edge edge = init_edge(v0, v1);
344 
345  ITER_SLOTS (eh, edge, slot, index) {
346  if (EH_INDEX_HAS_EDGE(eh, index, edge)) {
347  void *value = eh->entries[index].value;
348  eh->length--;
349  eh->dummy_count++;
350  eh->map[slot] = SLOT_DUMMY;
351  eh->entries[index] = eh->entries[eh->length];
352  if ((uint)index < eh->length) {
353  edgehash_change_index(eh, eh->entries[index].edge, index);
354  }
355  return value;
356  }
357  if (index == SLOT_EMPTY) {
358  return NULL;
359  }
360  }
361 }
362 
364 {
365  return edgehash_lookup_entry(eh, v0, v1) != NULL;
366 }
367 
369 {
370  return (int)eh->length;
371 }
372 
373 void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP free_value, const uint UNUSED(reserve))
374 {
375  /* TODO: handle reserve */
376  edgehash_free_values(eh, free_value);
377  eh->length = 0;
378  eh->dummy_count = 0;
380  CLEAR_MAP(eh);
381 }
382 
384 {
385  BLI_edgehash_clear_ex(eh, free_value, 0);
386 }
387 
390 /* -------------------------------------------------------------------- */
395 {
396  EdgeHashIterator *ehi = MEM_mallocN(sizeof(EdgeHashIterator), __func__);
397  BLI_edgehashIterator_init(ehi, eh);
398  return ehi;
399 }
400 
402 {
403  ehi->entries = eh->entries;
404  ehi->length = eh->length;
405  ehi->index = 0;
406 }
407 
409 {
410  MEM_freeN(ehi);
411 }
412 
415 /* -------------------------------------------------------------------- */
421 #define ES_INDEX_HAS_EDGE(es, index, edge) \
422  (index) >= 0 && edges_equal((edge), (es)->entries[index])
423 
424 EdgeSet *BLI_edgeset_new_ex(const char *info, const uint reserve)
425 {
426  EdgeSet *es = MEM_mallocN(sizeof(EdgeSet), info);
428  UPDATE_SLOT_MASK(es);
429  es->length = 0;
430  es->entries = MEM_malloc_arrayN(ENTRIES_CAPACITY(es), sizeof(Edge), "es entries");
431  es->map = MEM_malloc_arrayN(MAP_CAPACITY(es), sizeof(int32_t), "es map");
432  CLEAR_MAP(es);
433  return es;
434 }
435 
436 EdgeSet *BLI_edgeset_new(const char *info)
437 {
438  return BLI_edgeset_new_ex(info, 1 << CAPACITY_EXP_DEFAULT);
439 }
440 
442 {
443  MEM_freeN(es->entries);
444  MEM_freeN(es->map);
445  MEM_freeN(es);
446 }
447 
448 int BLI_edgeset_len(const EdgeSet *es)
449 {
450  return (int)es->length;
451 }
452 
453 static void edgeset_insert_index(EdgeSet *es, Edge edge, uint entry_index)
454 {
455  ITER_SLOTS (es, edge, slot, index) {
456  if (index == SLOT_EMPTY) {
457  es->map[slot] = (int)entry_index;
458  break;
459  }
460  }
461 }
462 
464 {
465  if (UNLIKELY(ENTRIES_CAPACITY(es) <= es->length)) {
466  es->capacity_exp++;
467  UPDATE_SLOT_MASK(es);
468  es->entries = MEM_reallocN(es->entries, sizeof(Edge) * ENTRIES_CAPACITY(es));
469  es->map = MEM_reallocN(es->map, sizeof(int32_t) * MAP_CAPACITY(es));
470  CLEAR_MAP(es);
471  for (uint i = 0; i < es->length; i++) {
472  edgeset_insert_index(es, es->entries[i], i);
473  }
474  }
475 }
476 
478 {
479  es->entries[es->length] = edge;
480  es->map[slot] = (int)es->length;
481  es->length++;
482 }
483 
485 {
487  Edge edge = init_edge(v0, v1);
488 
489  ITER_SLOTS (es, edge, slot, index) {
490  if (ES_INDEX_HAS_EDGE(es, index, edge)) {
491  return false;
492  }
493  if (index == SLOT_EMPTY) {
494  edgeset_insert_at_slot(es, slot, edge);
495  return true;
496  }
497  }
498 }
499 
501 {
503  Edge edge = init_edge(v0, v1);
504 
505  ITER_SLOTS (es, edge, slot, index) {
506  if (index == SLOT_EMPTY) {
507  edgeset_insert_at_slot(es, slot, edge);
508  return;
509  }
510  }
511 }
512 
513 bool BLI_edgeset_haskey(const EdgeSet *es, uint v0, uint v1)
514 {
515  Edge edge = init_edge(v0, v1);
516 
517  ITER_SLOTS (es, edge, slot, index) {
518  if (ES_INDEX_HAS_EDGE(es, index, edge)) {
519  return true;
520  }
521  if (index == SLOT_EMPTY) {
522  return false;
523  }
524  }
525 }
526 
528 {
529  EdgeSetIterator *esi = MEM_mallocN(sizeof(EdgeSetIterator), __func__);
530  esi->edges = es->entries;
531  esi->length = es->length;
532  esi->index = 0;
533  return esi;
534 }
535 
537 {
538  MEM_freeN(esi);
539 }
540 
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
void(* EdgeHashFreeFP)(void *key)
Definition: BLI_edgehash.h:34
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNUSED(x)
#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 const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
#define MEM_reallocN(vmemh, len)
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value)
Definition: edgehash.c:230
EdgeHash * BLI_edgehash_new_ex(const char *info, const uint reserve)
Definition: edgehash.c:212
BLI_INLINE Edge init_edge(uint v0, uint v1)
Definition: edgehash.c:83
BLI_INLINE EdgeHashEntry * edgehash_insert(EdgeHash *eh, Edge edge, void *value)
Definition: edgehash.c:169
#define MAP_CAPACITY(container)
Definition: edgehash.c:48
BLI_INLINE void edgehash_change_index(EdgeHash *eh, Edge edge, int new_index)
Definition: edgehash.c:196
void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *value)
Definition: edgehash.c:261
BLI_INLINE void edgehash_insert_index(EdgeHash *eh, Edge edge, uint entry_index)
Definition: edgehash.c:132
void ** BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1)
Definition: edgehash.c:301
void BLI_edgehash_print(EdgeHash *eh)
Definition: edgehash.c:238
BLI_INLINE void edgeset_ensure_can_insert(EdgeSet *es)
Definition: edgehash.c:463
static void edgeset_insert_index(EdgeSet *es, Edge edge, uint entry_index)
Definition: edgehash.c:453
#define CAPACITY_EXP_DEFAULT
Definition: edgehash.c:70
static void edgehash_free_values(EdgeHash *eh, EdgeHashFreeFP free_value)
Definition: edgehash.c:123
bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *value)
Definition: edgehash.c:268
void BLI_edgesetIterator_free(EdgeSetIterator *esi)
Definition: edgehash.c:536
EdgeSet * BLI_edgeset_new_ex(const char *info, const uint reserve)
Definition: edgehash.c:424
bool BLI_edgehash_haskey(const EdgeHash *eh, uint v0, uint v1)
Definition: edgehash.c:363
struct EdgeSet EdgeSet
void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh)
Definition: edgehash.c:401
void BLI_edgeset_free(EdgeSet *es)
Definition: edgehash.c:441
void * BLI_edgehash_lookup(const EdgeHash *eh, uint v0, uint v1)
Definition: edgehash.c:295
#define SLOT_DUMMY
Definition: edgehash.c:68
void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP free_value)
Definition: edgehash.c:383
EdgeSet * BLI_edgeset_new(const char *info)
Definition: edgehash.c:436
void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
Definition: edgehash.c:408
#define CLEAR_MAP(container)
Definition: edgehash.c:49
bool BLI_edgeset_haskey(const EdgeSet *es, uint v0, uint v1)
Definition: edgehash.c:513
#define ENTRIES_CAPACITY(container)
Definition: edgehash.c:47
EdgeHashIterator * BLI_edgehashIterator_new(EdgeHash *eh)
Definition: edgehash.c:394
EdgeSetIterator * BLI_edgesetIterator_new(EdgeSet *es)
Definition: edgehash.c:527
void * BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1)
Definition: edgehash.c:338
int BLI_edgeset_len(const EdgeSet *es)
Definition: edgehash.c:448
#define EH_INDEX_HAS_EDGE(eh, index, edge)
Definition: edgehash.c:120
BLI_INLINE EdgeHashEntry * edgehash_insert_at_slot(EdgeHash *eh, uint slot, Edge edge, void *value)
Definition: edgehash.c:142
bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP free_value)
Definition: edgehash.c:328
struct EdgeHash EdgeHash
static uint calc_capacity_exp_for_reserve(uint reserve)
Definition: edgehash.c:105
BLI_INLINE EdgeHashEntry * edgehash_lookup_entry(const EdgeHash *eh, uint v0, uint v1)
Definition: edgehash.c:182
#define UPDATE_SLOT_MASK(container)
Definition: edgehash.c:51
#define ITER_SLOTS(CONTAINER, EDGE, SLOT, INDEX)
Definition: edgehash.c:58
BLI_INLINE bool edges_equal(Edge e1, Edge e2)
Definition: edgehash.c:100
bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_value)
Definition: edgehash.c:307
BLI_INLINE uint32_t calc_edge_hash(Edge edge)
Definition: edgehash.c:78
bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1)
Definition: edgehash.c:484
EdgeHash * BLI_edgehash_new(const char *info)
Definition: edgehash.c:225
void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
Definition: edgehash.c:500
#define SLOT_EMPTY
Definition: edgehash.c:67
BLI_INLINE void edgeset_insert_at_slot(EdgeSet *es, uint slot, Edge edge)
Definition: edgehash.c:477
void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP free_value, const uint UNUSED(reserve))
Definition: edgehash.c:373
#define ES_INDEX_HAS_EDGE(es, index, edge)
Definition: edgehash.c:421
int BLI_edgehash_len(const EdgeHash *eh)
Definition: edgehash.c:368
BLI_INLINE bool edgehash_ensure_can_insert(EdgeHash *eh)
Definition: edgehash.c:152
void * BLI_edgehash_lookup_default(const EdgeHash *eh, uint v0, uint v1, void *default_value)
Definition: edgehash.c:289
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:34
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_calloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:32
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
T length(const vec_base< T, Size > &a)
unsigned int uint32_t
Definition: stdint.h:80
signed int int32_t
Definition: stdint.h:77
struct _EdgeHash_Entry * entries
Definition: BLI_edgehash.h:29
uint32_t slot_mask
Definition: edgehash.c:29
EdgeHashEntry * entries
Definition: edgehash.c:27
uint capacity_exp
Definition: edgehash.c:30
int32_t * map
Definition: edgehash.c:28
uint length
Definition: edgehash.c:31
uint dummy_count
Definition: edgehash.c:32
struct _EdgeHash_Edge * edges
Definition: BLI_edgehash.h:191
int32_t * map
Definition: edgehash.c:37
Edge * entries
Definition: edgehash.c:36
uint32_t slot_mask
Definition: edgehash.c:38
uint length
Definition: edgehash.c:40
uint capacity_exp
Definition: edgehash.c:39
Definition: BLI_edgehash.h:23
struct _EdgeHash_Edge edge
Definition: BLI_edgehash.h:24
void * value
Definition: BLI_edgehash.h:25