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