2 * ***** BEGIN GPL LICENSE BLOCK *****
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.
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.
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.
18 * Contributor(s): Daniel Dunbar, Joseph Eagar
20 * ***** END GPL LICENSE BLOCK *****
23 /** \file blender/blenlib/intern/edgehash.c
26 * An (edge -> pointer) chaining hash table.
27 * Using unordered int-pairs as keys.
29 * \note Based on 'BLI_ghash.c', which is a more generalized hash-table
30 * make sure these stay in sync.
37 #include "MEM_guardedalloc.h"
39 #include "BLI_utildefines.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_mempool.h"
42 #include "BLI_strict_flags.h"
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,
52 /* internal flag to ensure sets values aren't used */
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)
58 # define IS_EDGEHASH_ASSERT(eh)
59 // # define IS_EDGESET_ASSERT(es)
62 /* ensure v0 is smaller */
63 #define EDGE_ORD(v0, v1) \
70 typedef struct EdgeEntry {
71 struct EdgeEntry *next;
79 uint nbuckets, nentries;
84 /* -------------------------------------------------------------------- */
87 /** \name Internal Utility API
91 * Compute the hash and get the bucket-index.
93 BLI_INLINE uint edgehash_bucket_index(EdgeHash *eh, uint v0, uint v1)
97 return ((v0 * 65) ^ (v1 * 31)) % eh->nbuckets;
101 * Check if the number of items in the GHash is large enough to require more buckets.
103 BLI_INLINE bool edgehash_test_expand_buckets(const uint nentries, const uint nbuckets)
105 return (nentries > nbuckets * 3);
109 * Expand buckets to the next size up.
111 BLI_INLINE void edgehash_resize_buckets(EdgeHash *eh, const uint nbuckets)
113 EdgeEntry **buckets_old = eh->buckets;
114 EdgeEntry **buckets_new;
115 const uint nbuckets_old = eh->nbuckets;
118 BLI_assert(eh->nbuckets != nbuckets);
120 eh->nbuckets = nbuckets;
121 buckets_new = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
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);
127 e->next = buckets_new[bucket_index];
128 buckets_new[bucket_index] = e;
132 eh->buckets = buckets_new;
133 MEM_freeN(buckets_old);
137 * Increase initial bucket size to match a reserved amount.
139 BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const uint nentries_reserve)
141 while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
142 eh->nbuckets = _ehash_hashsizes[++eh->cursize];
147 * Internal lookup function.
148 * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
150 BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(
151 EdgeHash *eh, uint v0, uint v1,
152 const uint bucket_index)
156 for (e = eh->buckets[bucket_index]; e; e = e->next) {
157 if (UNLIKELY(v0 == e->v0 && v1 == e->v1)) {
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...).
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)
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)) {
186 * Internal lookup function. Only wraps #edgehash_lookup_entry_ex
188 BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, uint v0, uint v1)
191 const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
192 return edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
196 static EdgeHash *edgehash_new(const char *info,
197 const uint nentries_reserve,
198 const uint entry_size)
200 EdgeHash *eh = MEM_mallocN(sizeof(*eh), info);
202 eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */
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);
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);
219 * Internal insert function.
220 * Takes a \a bucket_index argument to avoid calling #edgehash_bucket_index multiple times.
222 BLI_INLINE void edgehash_insert_ex(
223 EdgeHash *eh, uint v0, uint v1, void *val,
224 const uint bucket_index)
226 EdgeEntry *e = BLI_mempool_alloc(eh->epool);
228 BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
229 IS_EDGEHASH_ASSERT(eh);
231 /* this helps to track down errors with bad edge data */
233 BLI_assert(v0 != v1);
235 e->next = eh->buckets[bucket_index];
239 eh->buckets[bucket_index] = e;
241 if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
242 edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
247 * Insert function that doesn't set the value (use for EdgeSet)
249 BLI_INLINE void edgehash_insert_ex_keyonly(
250 EdgeHash *eh, uint v0, uint v1,
251 const uint bucket_index)
253 EdgeEntry *e = BLI_mempool_alloc(eh->epool);
255 BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
257 /* this helps to track down errors with bad edge data */
259 BLI_assert(v0 != v1);
261 e->next = eh->buckets[bucket_index];
264 eh->buckets[bucket_index] = e;
266 if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
267 edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
272 * Insert function that doesn't set the value (use for EdgeSet)
274 BLI_INLINE void edgehash_insert_ex_keyonly_entry(
275 EdgeHash *eh, uint v0, uint v1,
276 const uint bucket_index,
279 BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
281 /* this helps to track down errors with bad edge data */
283 BLI_assert(v0 != v1);
285 e->next = eh->buckets[bucket_index];
288 /* intentionally leave value unset */
289 eh->buckets[bucket_index] = e;
291 if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
292 edgehash_resize_buckets(eh, _ehash_hashsizes[++eh->cursize]);
296 BLI_INLINE void edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val)
299 const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
300 edgehash_insert_ex(eh, v0, v1, val, bucket_index);
304 * Remove the entry and return it, caller must free from eh->epool.
306 BLI_INLINE EdgeEntry *edgehash_remove_ex(
307 EdgeHash *eh, uint v0, uint v1,
308 EdgeHashFreeFP valfreefp,
309 const uint bucket_index)
312 EdgeEntry *e = edgehash_lookup_entry_prev_ex(eh, v0, v1, &e_prev, bucket_index);
317 EdgeEntry *e_next = e->next;
324 e_prev->next = e_next;
327 eh->buckets[bucket_index] = e_next;
338 * Run free callbacks for freeing entries.
340 static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp)
344 BLI_assert(valfreefp);
346 for (i = 0; i < eh->nbuckets; i++) {
349 for (e = eh->buckets[i]; e; ) {
350 EdgeEntry *e_next = e->next;
367 EdgeHash *BLI_edgehash_new_ex(const char *info,
368 const uint nentries_reserve)
370 return edgehash_new(info,
375 EdgeHash *BLI_edgehash_new(const char *info)
377 return BLI_edgehash_new_ex(info, 0);
381 * Insert edge (\a v0, \a v1) into hash with given value, does
382 * not check for duplicates.
384 void BLI_edgehash_insert(EdgeHash *eh, uint v0, uint v1, void *val)
386 edgehash_insert(eh, v0, v1, val);
390 * Assign a new value to a key that may already be in edgehash.
392 bool BLI_edgehash_reinsert(EdgeHash *eh, uint v0, uint v1, void *val)
394 IS_EDGEHASH_ASSERT(eh);
397 const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
399 EdgeEntry *e = edgehash_lookup_entry_ex(eh, v0, v1, bucket_index);
405 edgehash_insert_ex(eh, v0, v1, val, bucket_index);
411 * Return pointer to value for given edge (\a v0, \a v1),
412 * or NULL if key does not exist in hash.
414 void **BLI_edgehash_lookup_p(EdgeHash *eh, uint v0, uint v1)
416 EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
417 IS_EDGEHASH_ASSERT(eh);
418 return e ? &e->val : NULL;
422 * Ensure \a (v0, v1) is exists in \a eh.
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.
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.
432 * \returns true when the value didn't need to be added.
433 * (when false, the caller _must_ initialize the value).
435 bool BLI_edgehash_ensure_p(EdgeHash *eh, uint v0, uint v1, void ***r_val)
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);
443 e = BLI_mempool_alloc(eh->epool);
444 edgehash_insert_ex_keyonly_entry(eh, v0, v1, bucket_index, e);
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().
457 void *BLI_edgehash_lookup(EdgeHash *eh, uint v0, uint v1)
459 EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
460 IS_EDGEHASH_ASSERT(eh);
461 return e ? e->val : NULL;
465 * A version of #BLI_edgehash_lookup which accepts a fallback argument.
467 void *BLI_edgehash_lookup_default(EdgeHash *eh, uint v0, uint v1, void *val_default)
469 EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
470 IS_EDGEHASH_ASSERT(eh);
471 return e ? e->val : val_default;
475 * Remove \a key (v0, v1) from \a eh, or return false if the key wasn't found.
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.
481 bool BLI_edgehash_remove(EdgeHash *eh, uint v0, uint v1, EdgeHashFreeFP valfreefp)
484 const uint bucket_index = edgehash_bucket_index(eh, v0, v1);
485 EdgeEntry *e = edgehash_remove_ex(eh, v0, v1, valfreefp, bucket_index);
487 BLI_mempool_free(eh->epool, e);
495 /* same as above but return the value,
496 * no free value argument since it will be returned */
498 * Remove \a key (v0, v1) from \a eh, returning the value or NULL if the key wasn't found.
500 * \param v0, v1: The key to remove.
501 * \return the value of \a key int \a eh or NULL.
503 void *BLI_edgehash_popkey(EdgeHash *eh, uint v0, uint 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);
511 BLI_mempool_free(eh->epool, e);
520 * Return boolean true/false if edge (v0,v1) in hash.
522 bool BLI_edgehash_haskey(EdgeHash *eh, uint v0, uint v1)
524 return (edgehash_lookup_entry(eh, v0, v1) != NULL);
528 * Return number of keys in hash.
530 int BLI_edgehash_len(EdgeHash *eh)
532 return (int)eh->nentries;
536 * Remove all edges from hash.
538 void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
539 const uint nentries_reserve)
542 edgehash_free_cb(eh, valfreefp);
544 eh->nbuckets = _ehash_hashsizes[0]; /* eh->cursize */
548 if (nentries_reserve) {
549 edgehash_buckets_reserve(eh, nentries_reserve);
552 MEM_freeN(eh->buckets);
553 eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
555 BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1);
559 * Wraps #BLI_edgehash_clear_ex with zero entries reserved.
561 void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp)
563 BLI_edgehash_clear_ex(eh, valfreefp, 0);
566 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
568 BLI_assert((int)eh->nentries == BLI_mempool_len(eh->epool));
571 edgehash_free_cb(eh, valfreefp);
573 BLI_mempool_destroy(eh->epool);
575 MEM_freeN(eh->buckets);
580 void BLI_edgehash_flag_set(EdgeHash *eh, uint flag)
585 void BLI_edgehash_flag_clear(EdgeHash *eh, uint flag)
593 /* -------------------------------------------------------------------- */
594 /* EdgeHash Iterator API */
596 /** \name Iterator API
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.
604 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
606 EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter");
607 BLI_edgehashIterator_init(ehi, eh);
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.
616 * \param ehi The EdgeHashIterator to initialize.
617 * \param eh The EdgeHash to iterate over.
619 void BLI_edgehashIterator_init(EdgeHashIterator *ehi, EdgeHash *eh)
622 ehi->curEntry = NULL;
623 ehi->curBucket = UINT_MAX; /* wraps to zero */
627 if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) {
631 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
632 } while (!ehi->curEntry);
637 * Steps the iterator to the next index.
639 void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
642 ehi->curEntry = ehi->curEntry->next;
643 while (!ehi->curEntry) {
645 if (UNLIKELY(ehi->curBucket == ehi->eh->nbuckets)) {
649 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
655 * Free an EdgeHashIterator.
657 void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
662 /* inline functions now */
665 * Retrieve the key from an iterator.
667 void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, uint *r_v0, uint *r_v1)
669 *r_v0 = ehi->curEntry->v0;
670 *r_v1 = ehi->curEntry->v1;
674 * Retrieve the value from an iterator.
676 void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi)
678 return ehi->curEntry->val;
682 * Retrieve the pointer to the value from an iterator.
684 void **BLI_edgehashIterator_getValue_p(EdgeHashIterator *ehi)
686 return &ehi->curEntry->val;
690 * Set the value for an iterator.
692 void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val)
694 ehi->curEntry->val = val;
698 * Determine if an iterator is done.
700 bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi)
702 return (ehi->curEntry == NULL);
708 /* -------------------------------------------------------------------- */
711 /* Use edgehash API to give 'set' functionality */
713 /** \name EdgeSet Functions
715 EdgeSet *BLI_edgeset_new_ex(const char *info,
716 const uint nentries_reserve)
718 EdgeSet *es = (EdgeSet *)edgehash_new(info,
720 sizeof(EdgeEntry) - sizeof(void *));
722 ((EdgeHash *)es)->flag |= EDGEHASH_FLAG_IS_SET;
727 EdgeSet *BLI_edgeset_new(const char *info)
729 return BLI_edgeset_new_ex(info, 0);
732 int BLI_edgeset_len(EdgeSet *es)
734 return (int)((EdgeHash *)es)->nentries;
738 * Adds the key to the set (no checks for unique keys!).
739 * Matching #BLI_edgehash_insert
741 void BLI_edgeset_insert(EdgeSet *es, uint v0, uint v1)
744 const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
745 edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
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.
752 * \note EdgeHash has no equivalent to this because typically the value would be different.
754 bool BLI_edgeset_add(EdgeSet *es, uint v0, uint v1)
757 const uint bucket_index = edgehash_bucket_index((EdgeHash *)es, v0, v1);
759 EdgeEntry *e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, bucket_index);
764 edgehash_insert_ex_keyonly((EdgeHash *)es, v0, v1, bucket_index);
769 bool BLI_edgeset_haskey(EdgeSet *es, uint v0, uint v1)
771 return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL);
775 void BLI_edgeset_free(EdgeSet *es)
777 BLI_edgehash_free((EdgeHash *)es, NULL);
780 void BLI_edgeset_flag_set(EdgeSet *es, uint flag)
782 ((EdgeHash *)es)->flag |= flag;
785 void BLI_edgeset_flag_clear(EdgeSet *es, uint flag)
787 ((EdgeHash *)es)->flag &= ~flag;
792 /** \name Debugging & Introspection
797 * Measure how well the hash function performs
798 * (1.0 is approx as good as random distribution).
800 double BLI_edgehash_calc_quality(EdgeHash *eh)
805 if (eh->nentries == 0)
808 for (i = 0; i < eh->nbuckets; i++) {
811 for (e = eh->buckets[i]; e; e = e->next) {
814 sum += count * (count + 1);
816 return ((double)sum * (double)eh->nbuckets /
817 ((double)eh->nentries * (eh->nentries + 2 * eh->nbuckets - 1)));
819 double BLI_edgeset_calc_quality(EdgeSet *es)
821 return BLI_edgehash_calc_quality((EdgeHash *)es);