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