Cleanup: use '_len' instead of '_size' w/ BLI API
[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  * Contributor(s): Daniel Dunbar, Joseph Eagar
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/blenlib/intern/edgehash.c
24  *  \ingroup bli
25  *
26  * An (edge -> pointer) chaining hash table.
27  * Using unordered int-pairs as keys.
28  *
29  * \note Based on 'BLI_ghash.c', which is a more generalized hash-table
30  * make sure these stay in sync.
31  */
32
33 #include <stdlib.h>
34 #include <string.h>
35 #include <limits.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_utildefines.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_mempool.h"
42 #include "BLI_strict_flags.h"
43
44 /**************inlined code************/
45 static const uint _ehash_hashsizes[] = {
46         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
47         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
48         4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
49         268435459
50 };
51
52 /* internal flag to ensure sets values aren't used */
53 #ifndef NDEBUG
54 #  define EDGEHASH_FLAG_IS_SET (1 << 8)
55 #  define IS_EDGEHASH_ASSERT(eh) BLI_assert((eh->flag & EDGEHASH_FLAG_IS_SET) == 0)
56 // #  define IS_EDGESET_ASSERT(es) BLI_assert((es->flag & EDGEHASH_FLAG_IS_SET) != 0)
57 #else
58 #  define IS_EDGEHASH_ASSERT(eh)
59 // #  define IS_EDGESET_ASSERT(es)
60 #endif
61
62 /* ensure v0 is smaller */
63 #define EDGE_ORD(v0, v1)            \
64         if (v0 > v1) {                  \
65                 SWAP(uint, v0, v1); \
66         } (void)0
67
68 /***/
69
70 typedef struct EdgeEntry {
71         struct EdgeEntry *next;
72         uint v0, v1;
73         void *val;
74 } EdgeEntry;
75
76 struct EdgeHash {
77         EdgeEntry **buckets;
78         BLI_mempool *epool;
79         uint nbuckets, nentries;
80         uint cursize, flag;
81 };
82
83
84 /* -------------------------------------------------------------------- */
85 /* EdgeHash API */
86
87 /** \name Internal Utility API
88  * \{ */
89
90 /**
91  * Compute the hash and get the bucket-index.
92  */
93 BLI_INLINE uint edgehash_bucket_index(EdgeHash *eh, uint v0, uint v1)
94 {
95         BLI_assert(v0 < v1);
96
97         return ((v0 * 65) ^ (v1 * 31)) % eh->nbuckets;
98 }
99
100 /**
101  * Check if the number of items in the GHash is large enough to require more buckets.
102  */
103 BLI_INLINE bool edgehash_test_expand_buckets(const uint nentries, const uint nbuckets)
104 {
105         return (nentries > nbuckets * 3);
106 }
107
108 /**
109  * Expand buckets to the next size up.
110  */
111 BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const uint nbuckets)
112 {
113         EdgeEntry **buckets_old = eh->buckets;
114         EdgeEntry **buckets_new;
115         const uint nbuckets_old = eh->nbuckets;
116         uint i;
117
118         BLI_assert(eh->nbuckets != nbuckets);
119
120         eh->nbuckets = nbuckets;
121         buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
122
123         for (i = 0; i < nbuckets_old; i++) {
124                 for (EdgeEntry *e = buckets_old[i], *e_next; e; e = e_next) {
125                         const unsigned bucket_index = edgehash_bucket_index(eh, e->v0, e->v1);
126                         e_next = e->next;
127                         e->next = buckets_new[bucket_index];
128                         buckets_new[bucket_index] = e;
129                 }
130         }
131
132         eh->buckets = buckets_new;
133         MEM_freeN(buckets_old);
134 }
135
136 /**
137  * Increase initial bucket size to match a reserved amount.
138  */
139 BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const uint nentries_reserve)
140 {
141         while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
142                 eh->nbuckets = _ehash_hashsizes[++eh->cursize];
143         }
144 }
145
146 /**
147  * Internal lookup function.
148  * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
149  */
150 BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(
151         EdgeHash *eh, uint v0, uint v1,
152         const uint bucket_index)
153 {
154         EdgeEntry *e;
155         BLI_assert(v0 < v1);
156         for (e = eh->buckets[bucket_index]; e; e = e->next) {
157                 if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
158                         return e;
159                 }
160         }
161         return NULL;
162 }
163
164 /**
165  * Internal lookup function, returns previous entry of target one too.
166  * Takes bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
167  * Useful when modifying buckets somehow (like removing an entry...).
168  */
169 BLI_INLINE EdgeEntry *edgehash_lookup_entry_prev_ex(
170         EdgeHash *eh, uint v0, uint v1,
171         EdgeEntry **r_e_prev, const uint bucket_index)
172 {
173         BLI_assert(v0 < v1);
174         for (EdgeEntry *e_prev = NULL, *e = eh->buckets[bucket_index]; e; e_prev = e, e = e->next) {
175                 if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
176                         *r_e_prev = e_prev;
177                         return e;
178                 }
179         }
180
181         *r_e_prev = NULL;
182         return NULL;
183 }
184
185 /**
186  * Internal lookup function. Only wraps #edgehash_lookup_entry_ex
187  */
188 BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1)
189 {
190         EDGE_ORD(v0, v1);
191         const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
192         return edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
193 }
194
195
196 static EdgeHash *edgehash_new(const char *info,
197                               const uint nentries_reserve,
198                               const uint entry_size)
199 {
200         EdgeHash *eh = MEM_mallocN(sizeof(*eh), info);
201
202         eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
203         eh->nentries = 0;
204         eh->cursize = 0;
205         eh->flag = 0;
206
207         /* if we have reserved the number of elements that this hash will contain */
208         if (nentries_reserve) {
209                 edgehash_buckets_reserve(eh, nentries_reserve);
210         }
211
212         eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
213         eh->epool = BLI_mempool_create(entry_size, nentries_reserve, 512, BLI_MEMPOOL_NOP);
214
215         return eh;
216 }
217
218 /**
219  * Internal insert function.
220  * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
221  */
222 BLI_INLINE void edgehash_insert_ex(
223         EdgeHash *eh, uint v0, uint v1, void *val,
224         const uint bucket_index)
225 {
226         EdgeEntry *e = BLI_mempool_alloc(eh->epool);
227
228         BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
229         IS_EDGEHASH_ASSERT(eh);
230
231         /* this helps to track down errors with bad edge data */
232         BLI_assert(v0 < v1);
233         BLI_assert(v0 != v1);
234
235         e->next = eh->buckets[bucket_index];
236         e->v0 = v0;
237         e->v1 = v1;
238         e->val = val;
239         eh->buckets[bucket_index] = e;
240
241         if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
242                 edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
243         }
244 }
245
246 /**
247  * Insert function that doesn't set the value (use for EdgeSet)
248  */
249 BLI_INLINE void edgehash_insert_ex_keyonly(
250         EdgeHash *eh, uint v0, uint v1,
251         const uint bucket_index)
252 {
253         EdgeEntry *e = BLI_mempool_alloc(eh->epool);
254
255         BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
256
257         /* this helps to track down errors with bad edge data */
258         BLI_assert(v0 < v1);
259         BLI_assert(v0 != v1);
260
261         e->next = eh->buckets[bucket_index];
262         e->v0 = v0;
263         e->v1 = v1;
264         eh->buckets[bucket_index] = e;
265
266         if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
267                 edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
268         }
269 }
270
271 /**
272  * Insert function that doesn't set the value (use for EdgeSet)
273  */
274 BLI_INLINE void edgehash_insert_ex_keyonly_entry(
275         EdgeHash *eh, uint v0, uint v1,
276         const uint bucket_index,
277         EdgeEntry *e)
278 {
279         BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
280
281         /* this helps to track down errors with bad edge data */
282         BLI_assert(v0 < v1);
283         BLI_assert(v0 != v1);
284
285         e->next = eh->buckets[bucket_index];
286         e->v0 = v0;
287         e->v1 = v1;
288         /* intentionally leave value unset */
289         eh->buckets[bucket_index] = e;
290
291         if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
292                 edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
293         }
294 }
295
296 BLI_INLINE void edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val)
297 {
298         EDGE_ORD(v0, v1);
299         const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
300         edgehash_insert_ex(eh, v0, v1, val, bucket_index);
301 }
302
303 /**
304  * Remove the entry and return it, caller must free from eh->epool.
305  */
306 BLI_INLINE EdgeEntry *edgehash_remove_ex(
307         EdgeHash *eh, uint v0, uint v1,
308         EdgeHashFreeFP valfreefp,
309         const uint bucket_index)
310 {
311         EdgeEntry *e_prev;
312         EdgeEntry *e = edgehash_lookup_entry_prev_ex(eh, v0, v1, &e_prev, bucket_index);
313
314         BLI_assert(v0 < v1);
315
316         if (e) {
317                 EdgeEntry *e_next = e->next;
318
319                 if (valfreefp) {
320                         valfreefp(e->val);
321                 }
322
323                 if (e_prev) {
324                         e_prev->next = e_next;
325                 }
326                 else {
327                         eh->buckets[bucket_index] = e_next;
328                 }
329
330                 eh->nentries--;
331                 return e;
332         }
333
334         return e;
335 }
336
337 /**
338  * Run free callbacks for freeing entries.
339  */
340 static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp)
341 {
342         uint i;
343
344         BLI_assert(valfreefp);
345
346         for (i = 0; i < eh->nbuckets; i++) {
347                 EdgeEntry *e;
348
349                 for (e = eh->buckets[i]; e; ) {
350                         EdgeEntry *e_next = e->next;
351
352                         valfreefp(e->val);
353
354                         e = e_next;
355                 }
356         }
357 }
358
359 /** \} */
360
361
362 /** \name Public API
363  * \{ */
364
365 /* Public API */
366
367 EdgeHash *BLI_edgehash_new_ex(const char *info,
368                               const uint nentries_reserve)
369 {
370         return edgehash_new(info,
371                             nentries_reserve,
372                             sizeof(EdgeEntry));
373 }
374
375 EdgeHash *BLI_edgehash_new(const char *info)
376 {
377         return BLI_edgehash_new_ex(info, 0);
378 }
379
380 /**
381  * Insert edge (\a v0, \a v1) into hash with given value, does
382  * not check for duplicates.
383  */
384 void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val)
385 {
386         edgehash_insert(eh, v0, v1, val);
387 }
388
389 /**
390  * Assign a new value to a key that may already be in edgehash.
391  */
392 bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *val)
393 {
394         IS_EDGEHASH_ASSERT(eh);
395
396         EDGE_ORD(v0, v1);
397         const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
398
399         EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
400         if (e) {
401                 e->val = val;
402                 return false;
403         }
404         else {
405                 edgehash_insert_ex(eh, v0, v1, val, bucket_index);
406                 return true;
407         }
408 }
409
410 /**
411  * Return pointer to value for given edge (\a v0, \a v1),
412  * or NULL if key does not exist in hash.
413  */
414 void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1)
415 {
416         EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
417         IS_EDGEHASH_ASSERT(eh);
418         return e ? &e->val : NULL;
419 }
420
421 /**
422  * Ensure \a (v0, v1) is exists in \a eh.
423  *
424  * This handles the common situation where the caller needs ensure a key is added to \a eh,
425  * constructing a new value in the case the key isn't found.
426  * Otherwise use the existing value.
427  *
428  * Such situations typically incur multiple lookups, however this function
429  * avoids them by ensuring the key is added,
430  * returning a pointer to the value so it can be used or initialized by the caller.
431  *
432  * \returns true when the value didn't need to be added.
433  * (when false, the caller _must_ initialize the value).
434  */
435 bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_val)
436 {
437         EDGE_ORD(v0, v1);
438         const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
439         EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
440         const bool haskey = (e != NULL);
441
442         if (!haskey) {
443                 e = BLI_mempool_alloc(eh->epool);
444                 edgehash_insert_ex_keyonly_entry(eh, v0, v1, bucket_index, e);
445         }
446
447         *r_val = &e->val;
448         return haskey;
449 }
450
451 /**
452  * Return value for given edge (\a v0, \a v1), or NULL if
453  * if key does not exist in hash. (If need exists
454  * to differentiate between key-value being NULL and
455  * lack of key then see BLI_edgehash_lookup_p().
456  */
457 void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1)
458 {
459         EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
460         IS_EDGEHASH_ASSERT(eh);
461         return e ? e->val : NULL;
462 }
463
464 /**
465  * A version of #BLI_edgehash_lookup which accepts a fallback argument.
466  */
467 void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *val_default)
468 {
469         EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
470         IS_EDGEHASH_ASSERT(eh);
471         return e ? e->val : val_default;
472 }
473
474 /**
475  * Remove \a key (v0, v1) from \a eh, or return false if the key wasn't found.
476  *
477  * \param v0, v1: The key to remove.
478  * \param valfreefp  Optional callback to free the value.
479  * \return true if \a key was removed from \a eh.
480  */
481 bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP valfreefp)
482 {
483         EDGE_ORD(v0, v1);
484         const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
485         EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, valfreefp, bucket_index);
486         if (e) {
487                 BLI_mempool_free(eh->epool, e);
488                 return true;
489         }
490         else {
491                 return false;
492         }
493 }
494
495 /* same as above but return the value,
496  * no free value argument since it will be returned */
497 /**
498  * Remove \a key (v0, v1) from \a eh, returning the value or NULL if the key wasn't found.
499  *
500  * \param v0, v1: The key to remove.
501  * \return the value of \a key int \a eh or NULL.
502  */
503 void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint v1)
504 {
505         EDGE_ORD(v0, v1);
506         const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
507         EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, NULL, bucket_index);
508         IS_EDGEHASH_ASSERT(eh);
509         if (e) {
510                 void *val = e->val;
511                 BLI_mempool_free(eh->epool, e);
512                 return val;
513         }
514         else {
515                 return NULL;
516         }
517 }
518
519 /**
520  * Return boolean true/false if edge (v0,v1) in hash.
521  */
522 bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1)
523 {
524         return (edgehash_lookup_entry(eh, v0, v1) != NULL);
525 }
526
527 /**
528  * Return number of keys in hash.
529  */
530 int BLI_edgehash_len(EdgeHash *eh)
531 {
532         return (int)eh->nentries;
533 }
534
535 /**
536  * Remove all edges from hash.
537  */
538 void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
539                            const uint nentries_reserve)
540 {
541         if (valfreefp)
542                 edgehash_free_cb(eh, valfreefp);
543
544         eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
545         eh->nentries = 0;
546         eh->cursize = 0;
547
548         if (nentries_reserve) {
549                 edgehash_buckets_reserve(eh, nentries_reserve);
550         }
551
552         MEM_freeN(eh->buckets);
553         eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
554
555         BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1);
556 }
557
558 /**
559  * Wraps #BLI_edgehash_clear_ex with zero entries reserved.
560  */
561 void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp)
562 {
563         BLI_edgehash_clear_ex(eh, valfreefp, 0);
564 }
565
566 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
567 {
568         BLI_assert((int)eh->nentries == BLI_mempool_len(eh->epool));
569
570         if (valfreefp)
571                 edgehash_free_cb(eh, valfreefp);
572
573         BLI_mempool_destroy(eh->epool);
574
575         MEM_freeN(eh->buckets);
576         MEM_freeN(eh);
577 }
578
579
580 void BLI_edgehash_flag_set(EdgeHash *eh, uint flag)
581 {
582         eh->flag |= flag;
583 }
584
585 void BLI_edgehash_flag_clear(EdgeHash *eh, uint flag)
586 {
587         eh->flag &= ~flag;
588 }
589
590 /** \} */
591
592
593 /* -------------------------------------------------------------------- */
594 /* EdgeHash Iterator API */
595
596 /** \name Iterator API
597  * \{ */
598
599 /**
600  * Create a new EdgeHashIterator. The hash table must not be mutated
601  * while the iterator is in use, and the iterator will step exactly
602  * BLI_edgehash_len(eh) times before becoming done.
603  */
604 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
605 {
606         EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter");
607         BLI_edgehashIterator_init(ehi, eh);
608         return ehi;
609 }
610
611 /**
612  * Init an already allocated EdgeHashIterator. The hash table must not
613  * be mutated while the iterator is in use, and the iterator will
614  * step exactly BLI_edgehash_len(eh) times before becoming done.
615  *
616  * \param ehi The EdgeHashIterator to initialize.
617  * \param eh The EdgeHash to iterate over.
618  */
619 void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh)
620 {
621         ehi->eh = eh;
622         ehi->curEntry = NULL;
623         ehi->curBucket = UINT_MAX;  /* wraps to zero */
624         if (eh->nentries) {
625                 do {
626                         ehi->curBucket++;
627                         if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) {
628                                 break;
629                         }
630
631                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
632                 } while (!ehi->curEntry);
633         }
634 }
635
636 /**
637  * Steps the iterator to the next index.
638  */
639 void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
640 {
641         if (ehi->curEntry) {
642                 ehi->curEntry = ehi->curEntry->next;
643                 while (!ehi->curEntry) {
644                         ehi->curBucket++;
645                         if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) {
646                                 break;
647                         }
648
649                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
650                 }
651         }
652 }
653
654 /**
655  * Free an EdgeHashIterator.
656  */
657 void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
658 {
659         MEM_freeN(ehi);
660 }
661
662 /* inline functions now */
663 #if 0
664 /**
665  * Retrieve the key from an iterator.
666  */
667 void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, uint *r_v0, uint *r_v1)
668 {
669         *r_v0 = ehi->curEntry->v0;
670         *r_v1 = ehi->curEntry->v1;
671 }
672
673 /**
674  * Retrieve the value from an iterator.
675  */
676 void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi)
677 {
678         return ehi->curEntry->val;
679 }
680
681 /**
682  * Retrieve the pointer to the value from an iterator.
683  */
684 void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi)
685 {
686         return &ehi->curEntry->val;
687 }
688
689 /**
690  * Set the value for an iterator.
691  */
692 void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val)
693 {
694         ehi->curEntry->val = val;
695 }
696
697 /**
698  * Determine if an iterator is done.
699  */
700 bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi)
701 {
702         return (ehi->curEntry == NULL);
703 }
704 #endif
705
706 /** \} */
707
708 /* -------------------------------------------------------------------- */
709 /* EdgeSet API */
710
711 /* Use edgehash API to give 'set' functionality */
712
713 /** \name EdgeSet Functions
714  * \{ */
715 EdgeSet *BLI_edgeset_new_ex(const char *info,
716                                   const uint nentries_reserve)
717 {
718         EdgeSet *es = (EdgeSet *)edgehash_new(info,
719                                               nentries_reserve,
720                                               sizeof(EdgeEntry) - sizeof(void *));
721 #ifndef NDEBUG
722         ((EdgeHash *)es)->flag |= EDGEHASH_FLAG_IS_SET;
723 #endif
724         return es;
725 }
726
727 EdgeSet *BLI_edgeset_new(const char *info)
728 {
729         return BLI_edgeset_new_ex(info, 0);
730 }
731
732 int BLI_edgeset_len(EdgeSet *es)
733 {
734         return (int)((EdgeHash *)es)->nentries;
735 }
736
737 /**
738  * Adds the key to the set (no checks for unique keys!).
739  * Matching #BLI_edgehash_insert
740  */
741 void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
742 {
743         EDGE_ORD(v0, v1);
744         const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
745         edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
746 }
747
748 /**
749  * A version of BLI_edgeset_insert which checks first if the key is in the set.
750  * \returns true if a new key has been added.
751  *
752  * \note EdgeHash has no equivalent to this because typically the value would be different.
753  */
754 bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1)
755 {
756         EDGE_ORD(v0, v1);
757         const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
758
759         EdgeEntry *e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, bucket_index);
760         if (e) {
761                 return false;
762         }
763         else {
764                 edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
765                 return true;
766         }
767 }
768
769 bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1)
770 {
771         return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL);
772 }
773
774
775 void BLI_edgeset_free(EdgeSet *es)
776 {
777         BLI_edgehash_free((EdgeHash *)es, NULL);
778 }
779
780 void BLI_edgeset_flag_set(EdgeSet *es, uint flag)
781 {
782         ((EdgeHash *)es)->flag |= flag;
783 }
784
785 void BLI_edgeset_flag_clear(EdgeSet *es, uint flag)
786 {
787         ((EdgeHash *)es)->flag &= ~flag;
788 }
789
790 /** \} */
791
792 /** \name Debugging & Introspection
793  * \{ */
794 #ifdef DEBUG
795
796 /**
797  * Measure how well the hash function performs
798  * (1.0 is approx as good as random distribution).
799  */
800 double BLI_edgehash_calc_quality(EdgeHash *eh)
801 {
802         uint64_t sum = 0;
803         uint i;
804
805         if (eh->nentries == 0)
806                 return -1.0;
807
808         for (i = 0; i < eh->nbuckets; i++) {
809                 uint64_t count = 0;
810                 EdgeEntry *e;
811                 for (e = eh->buckets[i]; e; e = e->next) {
812                         count += 1;
813                 }
814                 sum += count * (count + 1);
815         }
816         return ((double)sum * (double)eh->nbuckets /
817                 ((double)eh->nentries * (eh->nentries + 2 * eh->nbuckets - 1)));
818 }
819 double BLI_edgeset_calc_quality(EdgeSet *es)
820 {
821         return BLI_edgehash_calc_quality((EdgeHash *)es);
822 }
823
824 #endif
825 /** \} */