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 /** \} */