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