Merged changes in the trunk up to revision 51985.
[blender.git] / source / blender / blenlib / intern / smallhash.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) 2008 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Joseph Eagar.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #include <string.h>
29
30 #include "MEM_guardedalloc.h"
31 #include "BLI_utildefines.h"
32
33 #include "BLI_smallhash.h"
34
35 /* SMHASH_CELL_UNUSED means this cell is inside a key series,
36  * while SMHASH_CELL_FREE means this cell terminates a key series.
37  *
38  * no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
39  * imagine.  hopefully.
40  *
41  * note: these have the SMHASH suffix because we may want to make them public.
42  */
43 #define SMHASH_CELL_UNUSED  ((void *)0x7FFFFFFF)
44 #define SMHASH_CELL_FREE    ((void *)0x7FFFFFFD)
45
46 BLI_INLINE int smhash_nonzero(const int n)
47 {
48         return n + !n;
49 }
50
51 BLI_INLINE int smhash_abs_i(const int n)
52 {
53         return (n > 0) ? n : -n;
54 }
55
56 /* typically this re-assigns 'h' */
57 #define SMHASH_NEXT(h, hoff)  ( \
58         CHECK_TYPE_INLINE(&(h),    int), \
59         CHECK_TYPE_INLINE(&(hoff), int), \
60         smhash_abs_i((h) + (((hoff) = smhash_nonzero((hoff) * 2) + 1), (hoff))) \
61         )
62
63 extern unsigned int hashsizes[];
64
65 void BLI_smallhash_init(SmallHash *hash)
66 {
67         int i;
68
69         memset(hash, 0, sizeof(*hash));
70
71         hash->table = hash->_stacktable;
72         hash->curhash = 2;
73         hash->size = hashsizes[hash->curhash];
74
75         hash->copytable = hash->_copytable;
76         hash->stacktable = hash->_stacktable;
77
78         for (i = 0; i < hash->size; i++) {
79                 hash->table[i].val = SMHASH_CELL_FREE;
80         }
81 }
82
83 /*NOTE: does *not* free *hash itself!  only the direct data!*/
84 void BLI_smallhash_release(SmallHash *hash)
85 {
86         if (hash == NULL) {
87                 return;
88         }
89
90         if (hash->table != hash->stacktable) {
91                 MEM_freeN(hash->table);
92         }
93 }
94
95 void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
96 {
97         int h, hoff = 1;
98
99         if (hash->size < hash->used * 3) {
100                 int newsize = hashsizes[++hash->curhash];
101                 SmallHashEntry *tmp;
102                 int i = 0;
103
104                 if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
105                         tmp = MEM_callocN(sizeof(*hash->table) * newsize, __func__);
106                 }
107                 else {
108                         SWAP(SmallHashEntry *, hash->stacktable, hash->copytable);
109                         tmp = hash->stacktable;
110                 }
111
112                 SWAP(SmallHashEntry *, tmp, hash->table);
113
114                 hash->size = newsize;
115
116                 for (i = 0; i < hash->size; i++) {
117                         hash->table[i].val = SMHASH_CELL_FREE;
118                 }
119
120                 for (i = 0; i < hashsizes[hash->curhash - 1]; i++) {
121                         if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
122                                 continue;
123                         }
124
125                         h = ABS((int)(tmp[i].key));
126                         hoff = 1;
127                         while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
128                                 h = SMHASH_NEXT(h, hoff);
129                         }
130
131                         h %= newsize;
132
133                         hash->table[h].key = tmp[i].key;
134                         hash->table[h].val = tmp[i].val;
135                 }
136
137                 if (tmp != hash->stacktable && tmp != hash->copytable) {
138                         MEM_freeN(tmp);
139                 }
140         }
141
142         h = ABS((int)key);
143         hoff = 1;
144
145         while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
146                 h = SMHASH_NEXT(h, hoff);
147         }
148
149         h %= hash->size;
150         hash->table[h].key = key;
151         hash->table[h].val = item;
152
153         hash->used++;
154 }
155
156 void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
157 {
158         int h, hoff = 1;
159
160         h = ABS((int)key);
161
162         while ((hash->table[h % hash->size].key != key) ||
163                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
164         {
165                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
166                         return;
167                 }
168
169                 h = SMHASH_NEXT(h, hoff);
170         }
171
172         h %= hash->size;
173         hash->table[h].key = 0;
174         hash->table[h].val = SMHASH_CELL_UNUSED;
175 }
176
177 void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
178 {
179         int h, hoff = 1;
180         void *v;
181
182         h = ABS((int)key);
183
184         if (hash->table == NULL) {
185                 return NULL;
186         }
187
188         while ((hash->table[h % hash->size].key != key) ||
189                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
190         {
191                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
192                         return NULL;
193                 }
194
195                 h = SMHASH_NEXT(h, hoff);
196         }
197
198         v = hash->table[h % hash->size].val;
199         if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
200                 return NULL;
201         }
202
203         return v;
204 }
205
206
207 int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
208 {
209         int h = ABS((int)key);
210         int hoff = 1;
211
212         if (hash->table == NULL) {
213                 return 0;
214         }
215
216         while ((hash->table[h % hash->size].key != key) ||
217                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
218         {
219                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
220                         return 0;
221                 }
222
223                 h = SMHASH_NEXT(h, hoff);
224         }
225
226         return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
227 }
228
229 int BLI_smallhash_count(SmallHash *hash)
230 {
231         return hash->used;
232 }
233
234 void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
235 {
236         while (iter->i < iter->hash->size) {
237                 if (    (iter->hash->table[iter->i].val != SMHASH_CELL_UNUSED) &&
238                         (iter->hash->table[iter->i].val != SMHASH_CELL_FREE))
239                 {
240                         if (key) {
241                                 *key = iter->hash->table[iter->i].key;
242                         }
243
244                         iter->i++;
245
246                         return iter->hash->table[iter->i - 1].val;
247                 }
248
249                 iter->i++;
250         }
251
252         return NULL;
253 }
254
255 void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key)
256 {
257         iter->hash = hash;
258         iter->i = 0;
259
260         return BLI_smallhash_iternext(iter, key);
261 }
262
263 /* note, this was called _print_smhash in knifetool.c
264  * it may not be intended for general use - campbell */
265 #if 0
266 void BLI_smallhash_print(SmallHash *hash)
267 {
268         int i, linecol = 79, c = 0;
269
270         printf("{");
271         for (i = 0; i < hash->size; i++) {
272                 if (hash->table[i].val == SMHASH_CELL_UNUSED) {
273                         printf("--u-");
274                 }
275                 else if (hash->table[i].val == SMHASH_CELL_FREE) {
276                         printf("--f-");
277                 }
278                 else {
279                         printf("%2x", (unsigned int)hash->table[i].key);
280                 }
281
282                 if (i != hash->size - 1)
283                         printf(", ");
284
285                 c += 6;
286
287                 if (c >= linecol) {
288                         printf("\n ");
289                         c = 0;
290                 }
291         }
292
293         fflush(stdout);
294 }
295 #endif