add some safety checks in debug mode to ensure sets/hashes aren't confused.
[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  * A general (pointer -> pointer) hash table ADT
27  *
28  * \note Based on 'BLI_ghash.c', make sure these stay in sync.
29  */
30
31
32 #include <stdlib.h>
33 #include <string.h>
34 #include <limits.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_edgehash.h"
40 #include "BLI_mempool.h"
41
42 #ifdef __GNUC__
43 #  pragma GCC diagnostic error "-Wsign-conversion"
44 #  if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406  /* gcc4.6+ only */
45 #    pragma GCC diagnostic error "-Wsign-compare"
46 #    pragma GCC diagnostic error "-Wconversion"
47 #  endif
48 #endif
49
50 /**************inlined code************/
51 static const unsigned int _ehash_hashsizes[] = {
52         1, 3, 5, 11, 17, 37, 67, 131, 257, 521, 1031, 2053, 4099, 8209,
53         16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
54         4194319, 8388617, 16777259, 33554467, 67108879, 134217757,
55         268435459
56 };
57
58 /* internal flag to ensure sets values aren't used */
59 #ifndef NDEBUG
60 #  define EDGEHASH_FLAG_IS_SET (1 << 8)
61 #  define IS_EDGEHASH_ASSERT(eh) BLI_assert((eh->flag & EDGEHASH_FLAG_IS_SET) == 0)
62 // #  define IS_EDGESET_ASSERT(es) BLI_assert((es->flag & EDGEHASH_FLAG_IS_SET) != 0)
63 #else
64 #  define IS_EDGEHASH_ASSERT(eh)
65 // #  define IS_EDGESET_ASSERT(es)
66 #endif
67
68 /* ensure v0 is smaller */
69 #define EDGE_ORD(v0, v1) \
70         if (v0 > v1) {       \
71                 v0 ^= v1;        \
72                 v1 ^= v0;        \
73                 v0 ^= v1;        \
74         } (void)0
75
76 /***/
77
78 typedef struct EdgeEntry {
79         struct EdgeEntry *next;
80         unsigned int v0, v1;
81         void *val;
82 } EdgeEntry;
83
84 struct EdgeHash {
85         EdgeEntry **buckets;
86         BLI_mempool *epool;
87         unsigned int nbuckets, nentries;
88         unsigned int cursize, flag;
89 };
90
91
92 /* -------------------------------------------------------------------- */
93 /* EdgeHash API */
94
95 /** \name Internal Utility API
96  * \{ */
97
98 BLI_INLINE bool edgehash_test_expand_buckets(const unsigned int nentries, const unsigned int nbuckets)
99 {
100         return (nentries > nbuckets * 3);
101 }
102
103 /**
104  * Increase initial bucket size to match a reserved ammount.
105  */
106 BLI_INLINE void edgehash_buckets_reserve(EdgeHash *eh, const unsigned int nentries_reserve)
107 {
108         while (edgehash_test_expand_buckets(nentries_reserve, eh->nbuckets)) {
109                 eh->nbuckets = _ehash_hashsizes[++eh->cursize];
110         }
111 }
112
113 BLI_INLINE unsigned int edgehash_keyhash(EdgeHash *eh, unsigned int v0, unsigned int v1)
114 {
115         BLI_assert(v0 < v1);
116
117         return ((v0 * 39) ^ (v1 * 31)) % eh->nbuckets;
118 }
119
120 BLI_INLINE EdgeEntry *edgehash_lookup_entry_ex(EdgeHash *eh, unsigned int v0, unsigned int v1,
121                                                const unsigned int hash)
122 {
123         EdgeEntry *e;
124         BLI_assert(v0 < v1);
125         for (e = eh->buckets[hash]; e; e = e->next) {
126                 if (v0 == e->v0 && v1 == e->v1) {
127                         return e;
128                 }
129         }
130         return NULL;
131 }
132
133 BLI_INLINE EdgeEntry *edgehash_lookup_entry(EdgeHash *eh, unsigned int v0, unsigned int v1)
134 {
135         unsigned int hash;
136         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
137         hash = edgehash_keyhash(eh, v0, v1);
138         return edgehash_lookup_entry_ex(eh, v0, v1, hash);
139 }
140
141 static EdgeHash *edgehash_new(const char *info,
142                               const unsigned int nentries_reserve,
143                               const size_t entry_size)
144 {
145         EdgeHash *eh = MEM_mallocN(sizeof(*eh), info);
146
147         eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
148         eh->nentries = 0;
149         eh->cursize = 0;
150         eh->flag = 0;
151
152         /* if we have reserved the number of elements that this hash will contain */
153         if (nentries_reserve) {
154                 edgehash_buckets_reserve(eh, nentries_reserve);
155         }
156
157         eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
158         eh->epool = BLI_mempool_create((int)entry_size, 512, 512, BLI_MEMPOOL_SYSMALLOC);
159
160         return eh;
161 }
162
163 static EdgeEntry *edgehash_insert_ex(EdgeHash *eh, unsigned int v0, unsigned int v1,
164                                      unsigned int hash)
165 {
166         EdgeEntry *e = BLI_mempool_alloc(eh->epool);
167
168         BLI_assert((eh->flag & EDGEHASH_FLAG_ALLOW_DUPES) || (BLI_edgehash_haskey(eh, v0, v1) == 0));
169
170         /* this helps to track down errors with bad edge data */
171         BLI_assert(v0 < v1);
172         BLI_assert(v0 != v1);
173
174         e->next = eh->buckets[hash];
175         e->v0 = v0;
176         e->v1 = v1;
177         /* intentionally don't set the value */
178         eh->buckets[hash] = e;
179
180         if (UNLIKELY(edgehash_test_expand_buckets(++eh->nentries, eh->nbuckets))) {
181                 EdgeEntry *e_iter;
182                 EdgeEntry **old = eh->buckets;
183                 const unsigned int nold = eh->nbuckets;
184                 unsigned int i;
185
186                 eh->nbuckets = _ehash_hashsizes[++eh->cursize];
187                 eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
188
189                 for (i = 0; i < nold; i++) {
190                         EdgeEntry *e_next;
191                         for (e_iter = old[i]; e_iter; e_iter = e_next) {
192                                 e_next = e_iter->next;
193                                 hash = edgehash_keyhash(eh, e_iter->v0, e_iter->v1);
194                                 e_iter->next = eh->buckets[hash];
195                                 eh->buckets[hash] = e_iter;
196                         }
197                 }
198
199                 MEM_freeN(old);
200         }
201         return e;
202 }
203
204 /**
205  * Run free callbacks for freeing entries.
206  */
207 static void edgehash_free_cb(EdgeHash *eh, EdgeHashFreeFP valfreefp)
208 {
209         unsigned int i;
210
211         BLI_assert(valfreefp);
212
213         for (i = 0; i < eh->nbuckets; i++) {
214                 EdgeEntry *e;
215
216                 for (e = eh->buckets[i]; e; ) {
217                         EdgeEntry *e_next = e->next;
218
219                         if (valfreefp) valfreefp(e->val);
220
221                         e = e_next;
222                 }
223         }
224 }
225
226 /** \} */
227
228
229 /** \name Public API
230  * \{ */
231
232 /* Public API */
233
234 EdgeHash *BLI_edgehash_new_ex(const char *info,
235                               const unsigned int nentries_reserve)
236 {
237         return edgehash_new(info,
238                             nentries_reserve,
239                             sizeof(EdgeEntry));
240 }
241
242 EdgeHash *BLI_edgehash_new(const char *info)
243 {
244         return BLI_edgehash_new_ex(info, 0);
245 }
246
247 /**
248  * Insert edge (\a v0, \a v1) into hash with given value, does
249  * not check for duplicates.
250  */
251 void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
252 {
253         unsigned int hash;
254         EdgeEntry *e;
255         IS_EDGEHASH_ASSERT(eh);
256         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
257         hash = edgehash_keyhash(eh, v0, v1);
258         e = edgehash_insert_ex(eh, v0, v1, hash);
259         e->val = val;
260 }
261
262 /**
263  * Assign a new value to a key that may already be in edgehash.
264  */
265 bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
266 {
267         unsigned int hash;
268         EdgeEntry *e;
269
270         IS_EDGEHASH_ASSERT(eh);
271
272         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
273         hash = edgehash_keyhash(eh, v0, v1);
274
275         e = edgehash_lookup_entry_ex(eh, v0, v1, hash);
276         if (e) {
277                 e->val = val;
278                 return false;
279         }
280         else {
281                 e = edgehash_insert_ex(eh, v0, v1, hash);
282                 e->val = val;
283                 return true;
284         }
285 }
286
287 /**
288  * Return pointer to value for given edge (\a v0, \a v1),
289  * or NULL if key does not exist in hash.
290  */
291 void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1)
292 {
293         EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
294         IS_EDGEHASH_ASSERT(eh);
295         return e ? &e->val : NULL;
296 }
297
298 /**
299  * Return value for given edge (\a v0, \a v1), or NULL if
300  * if key does not exist in hash. (If need exists
301  * to differentiate between key-value being NULL and
302  * lack of key then see BLI_edgehash_lookup_p().
303  */
304 void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1)
305 {
306         EdgeEntry *e = edgehash_lookup_entry(eh, v0, v1);
307         IS_EDGEHASH_ASSERT(eh);
308         return e ? e->val : NULL;
309 }
310
311 /**
312  * Return boolean true/false if edge (v0,v1) in hash.
313  */
314 bool BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1)
315 {
316         return (edgehash_lookup_entry(eh, v0, v1) != NULL);
317 }
318
319 /**
320  * Return number of keys in hash.
321  */
322 int BLI_edgehash_size(EdgeHash *eh)
323 {
324         return (int)eh->nentries;
325 }
326
327 /**
328  * Remove all edges from hash.
329  */
330 void BLI_edgehash_clear_ex(EdgeHash *eh, EdgeHashFreeFP valfreefp,
331                            const unsigned int nentries_reserve)
332 {
333         if (valfreefp)
334                 edgehash_free_cb(eh, valfreefp);
335
336         eh->nbuckets = _ehash_hashsizes[0];  /* eh->cursize */
337         eh->nentries = 0;
338         eh->cursize = 0;
339
340         if (nentries_reserve) {
341                 edgehash_buckets_reserve(eh, nentries_reserve);
342         }
343
344         MEM_freeN(eh->buckets);
345         eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
346
347         BLI_mempool_clear_ex(eh->epool, nentries_reserve ? (int)nentries_reserve : -1);
348 }
349
350 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
351 {
352         BLI_assert((int)eh->nentries == BLI_mempool_count(eh->epool));
353
354         if (valfreefp)
355                 edgehash_free_cb(eh, valfreefp);
356
357         BLI_mempool_destroy(eh->epool);
358
359         MEM_freeN(eh->buckets);
360         MEM_freeN(eh);
361 }
362
363
364 void BLI_edgehash_flag_set(EdgeHash *eh, unsigned int flag)
365 {
366         eh->flag |= flag;
367 }
368
369 void BLI_edgehash_flag_clear(EdgeHash *eh, unsigned int flag)
370 {
371         eh->flag &= ~flag;
372 }
373
374 /** \} */
375
376
377 /* -------------------------------------------------------------------- */
378 /* EdgeHash Iterator API */
379
380 /** \name Iterator API
381  * \{ */
382
383 struct EdgeHashIterator {
384         EdgeHash *eh;
385         unsigned int curBucket;
386         EdgeEntry *curEntry;
387 };
388
389
390 /**
391  * Create a new EdgeHashIterator. The hash table must not be mutated
392  * while the iterator is in use, and the iterator will step exactly
393  * BLI_edgehash_size(gh) times before becoming done.
394  */
395 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
396 {
397         EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter");
398         ehi->eh = eh;
399         ehi->curEntry = NULL;
400         ehi->curBucket = UINT_MAX;  /* wraps to zero */
401         while (!ehi->curEntry) {
402                 ehi->curBucket++;
403                 if (ehi->curBucket == ehi->eh->nbuckets)
404                         break;
405                 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
406         }
407         return ehi;
408 }
409
410 /**
411  * Free an EdgeHashIterator.
412  */
413 void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
414 {
415         MEM_freeN(ehi);
416 }
417
418 /**
419  * Retrieve the key from an iterator.
420  */
421 void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *v0_r, unsigned int *v1_r)
422 {
423         if (ehi->curEntry) {
424                 *v0_r = ehi->curEntry->v0;
425                 *v1_r = ehi->curEntry->v1;
426         }
427 }
428
429 /**
430  * Retrieve the value from an iterator.
431  */
432 void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi)
433 {
434         return ehi->curEntry ? ehi->curEntry->val : NULL;
435 }
436
437 /**
438  * Set the value for an iterator.
439  */
440 void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val)
441 {
442         if (ehi->curEntry) {
443                 ehi->curEntry->val = val;
444         }
445 }
446
447 /**
448  * Steps the iterator to the next index.
449  */
450 void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
451 {
452         if (ehi->curEntry) {
453                 ehi->curEntry = ehi->curEntry->next;
454                 while (!ehi->curEntry) {
455                         ehi->curBucket++;
456                         if (ehi->curBucket == ehi->eh->nbuckets) {
457                                 break;
458                         }
459
460                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
461                 }
462         }
463 }
464
465 /**
466  * Determine if an iterator is done.
467  */
468 bool BLI_edgehashIterator_isDone(EdgeHashIterator *ehi)
469 {
470         return (ehi->curEntry == NULL);
471 }
472
473 /** \} */
474
475 /* -------------------------------------------------------------------- */
476 /* EdgeSet API */
477
478 /* Use edgehash API to give 'set' functionality */
479
480 /** \name EdgeSet Functions
481  * \{ */
482 EdgeSet *BLI_edgeset_new_ex(const char *info,
483                                   const unsigned int nentries_reserve)
484 {
485         EdgeSet *es = (EdgeSet *)edgehash_new(info,
486                                               nentries_reserve,
487                                               sizeof(EdgeEntry) - sizeof(void *));
488 #ifndef NDEBUG
489         ((EdgeHash *)es)->flag |= EDGEHASH_FLAG_IS_SET;
490 #endif
491         return es;
492 }
493
494 EdgeSet *BLI_edgeset_new(const char *info)
495 {
496         return BLI_edgeset_new_ex(info, 0);
497 }
498
499 int BLI_edgeset_size(EdgeSet *es)
500 {
501         return (int)((EdgeHash *)es)->nentries;
502 }
503
504 /**
505  * Adds the key to the set (no checks for unique keys!).
506  * Matching #BLI_edgehash_insert
507  */
508 void BLI_edgeset_insert(EdgeSet *es, unsigned int v0, unsigned int v1)
509 {
510         unsigned int hash;
511         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
512         hash = edgehash_keyhash((EdgeHash *)es, v0, v1);
513         edgehash_insert_ex((EdgeHash *)es, v0, v1, hash);
514 }
515
516 /**
517  * Assign a new value to a key that may already be in edgehash.
518  */
519 bool BLI_edgeset_reinsert(EdgeSet *es, unsigned int v0, unsigned int v1)
520 {
521         unsigned int hash;
522         EdgeEntry *e;
523
524         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
525         hash = edgehash_keyhash((EdgeHash *)es, v0, v1);
526
527         e = edgehash_lookup_entry_ex((EdgeHash *)es, v0, v1, hash);
528         if (e) {
529                 return false;
530         }
531         else {
532                 edgehash_insert_ex((EdgeHash *)es, v0, v1, hash);
533                 return true;
534         }
535 }
536
537 bool BLI_edgeset_haskey(EdgeSet *es, unsigned int v0, unsigned int v1)
538 {
539         return (edgehash_lookup_entry((EdgeHash *)es, v0, v1) != NULL);
540 }
541
542
543 void BLI_edgeset_free(EdgeSet *es)
544 {
545         BLI_edgehash_free((EdgeHash *)es, NULL);
546 }
547
548 /** \} */