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