copy BLI_edgehash changes from bmesh branch, main change is use of mempool.
[blender-staging.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  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: none of this file.
22  *
23  * Contributor(s): Daniel Dunbar, Joseph Eagar
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  * A general (pointer -> pointer) hash table ADT
27  */
28
29 /** \file blender/blenlib/intern/edgehash.c
30  *  \ingroup bli
31  */
32
33
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "MEM_guardedalloc.h"
38
39 #include "BLI_utildefines.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_mempool.h"
42
43 /**************inlined code************/
44 static 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 #define EDGE_HASH(v0, v1)  ((v0 * 39)^(v1 * 31))
52
53 /* ensure v0 is smaller */
54 #define EDGE_ORD(v0, v1) \
55         if (v0 < v1) {       \
56                 v0 ^= v1;        \
57                 v1 ^= v0;        \
58                 v0 ^= v1;        \
59         }
60
61 /***/
62
63 typedef struct EdgeEntry EdgeEntry;
64 struct EdgeEntry {
65         EdgeEntry *next;
66         unsigned int v0, v1;
67         void *val;
68 };
69
70 struct EdgeHash {
71         EdgeEntry **buckets;
72         BLI_mempool *epool;
73         int nbuckets, nentries, cursize;
74 };
75
76 /***/
77
78 EdgeHash *BLI_edgehash_new(void)
79 {
80         EdgeHash *eh = MEM_callocN(sizeof(*eh), "EdgeHash");
81         eh->cursize = 0;
82         eh->nentries = 0;
83         eh->nbuckets = _ehash_hashsizes[eh->cursize];
84         
85         eh->buckets = MEM_callocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets 2");
86         eh->epool = BLI_mempool_create(sizeof(EdgeEntry), 512, 512, TRUE, FALSE);
87
88         return eh;
89 }
90
91
92 void BLI_edgehash_insert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
93 {
94         unsigned int hash;
95         EdgeEntry *e = BLI_mempool_alloc(eh->epool);
96
97         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
98
99         hash = EDGE_HASH(v0, v1) % eh->nbuckets;
100
101         e->v0 = v0;
102         e->v1 = v1;
103         e->val = val;
104         e->next = eh->buckets[hash];
105         eh->buckets[hash]= e;
106
107         if (++eh->nentries>eh->nbuckets * 3) {
108                 EdgeEntry *e, **old = eh->buckets;
109                 int i, nold = eh->nbuckets;
110
111                 eh->nbuckets = _ehash_hashsizes[++eh->cursize];
112                 eh->buckets = MEM_mallocN(eh->nbuckets * sizeof(*eh->buckets), "eh buckets");
113                 memset(eh->buckets, 0, eh->nbuckets * sizeof(*eh->buckets));
114
115                 for (i = 0; i < nold; i++) {
116                         for (e = old[i]; e;) {
117                                 EdgeEntry *n = e->next;
118
119                                 hash = EDGE_HASH(e->v0, e->v1) % eh->nbuckets;
120                                 e->next = eh->buckets[hash];
121                                 eh->buckets[hash]= e;
122
123                                 e = n;
124                         }
125                 }
126
127                 MEM_freeN(old);
128         }
129 }
130
131 void **BLI_edgehash_lookup_p(EdgeHash *eh, unsigned int v0, unsigned int v1)
132 {
133         unsigned int hash;
134         EdgeEntry *e;
135
136         EDGE_ORD(v0, v1); /* ensure v0 is smaller */
137
138         hash = EDGE_HASH(v0, v1) % eh->nbuckets;
139         for (e = eh->buckets[hash]; e; e = e->next)
140                 if (v0 == e->v0 && v1 == e->v1)
141                         return &e->val;
142
143         return NULL;
144 }
145
146 void *BLI_edgehash_lookup(EdgeHash *eh, unsigned int v0, unsigned int v1)
147 {
148         void **value_p = BLI_edgehash_lookup_p(eh, v0, v1);
149
150         return value_p?*value_p:NULL;
151 }
152
153 int BLI_edgehash_haskey(EdgeHash *eh, unsigned int v0, unsigned int v1)
154 {
155         return BLI_edgehash_lookup_p(eh, v0, v1) != NULL;
156 }
157
158 int BLI_edgehash_size(EdgeHash *eh)
159 {
160         return eh->nentries;
161 }
162
163 void BLI_edgehash_clear(EdgeHash *eh, EdgeHashFreeFP valfreefp)
164 {
165         int i;
166         
167         for (i = 0; i<eh->nbuckets; i++) {
168                 EdgeEntry *e;
169                 
170                 for (e = eh->buckets[i]; e; ) {
171                         EdgeEntry *n = e->next;
172                         
173                         if (valfreefp) valfreefp(e->val);
174                         BLI_mempool_free(eh->epool, e);
175                         
176                         e = n;
177                 }
178                 eh->buckets[i] = NULL;
179         }
180
181         eh->nentries = 0;
182 }
183
184 void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP valfreefp)
185 {
186         BLI_edgehash_clear(eh, valfreefp);
187
188         BLI_mempool_destroy(eh->epool);
189
190         MEM_freeN(eh->buckets);
191         MEM_freeN(eh);
192 }
193
194
195 /***/
196
197 struct EdgeHashIterator {
198         EdgeHash *eh;
199         int curBucket;
200         EdgeEntry *curEntry;
201 };
202
203 EdgeHashIterator *BLI_edgehashIterator_new(EdgeHash *eh)
204 {
205         EdgeHashIterator *ehi = MEM_mallocN(sizeof(*ehi), "eh iter");
206         ehi->eh = eh;
207         ehi->curEntry = NULL;
208         ehi->curBucket = -1;
209         while (!ehi->curEntry) {
210                 ehi->curBucket++;
211                 if (ehi->curBucket == ehi->eh->nbuckets)
212                         break;
213                 ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
214         }
215         return ehi;
216 }
217 void BLI_edgehashIterator_free(EdgeHashIterator *ehi)
218 {
219         MEM_freeN(ehi);
220 }
221
222 void BLI_edgehashIterator_getKey(EdgeHashIterator *ehi, unsigned int *v0_r, unsigned int *v1_r)
223 {
224         if (ehi->curEntry) {
225                 *v0_r = ehi->curEntry->v0;
226                 *v1_r = ehi->curEntry->v1;
227         }
228 }
229 void *BLI_edgehashIterator_getValue(EdgeHashIterator *ehi)
230 {
231         return ehi->curEntry?ehi->curEntry->val:NULL;
232 }
233
234 void BLI_edgehashIterator_setValue(EdgeHashIterator *ehi, void *val)
235 {
236         if (ehi->curEntry) {
237                 ehi->curEntry->val = val;
238         }
239 }
240
241 void BLI_edgehashIterator_step(EdgeHashIterator *ehi)
242 {
243         if (ehi->curEntry) {
244                 ehi->curEntry = ehi->curEntry->next;
245                 while (!ehi->curEntry) {
246                         ehi->curBucket++;
247                         if (ehi->curBucket == ehi->eh->nbuckets) {
248                                 break;
249                         }
250
251                         ehi->curEntry = ehi->eh->buckets[ehi->curBucket];
252                 }
253         }
254 }
255 int BLI_edgehashIterator_isDone(EdgeHashIterator *ehi)
256 {
257         return !ehi->curEntry;
258 }
259