svn merge ^/trunk/blender -r44189:44204
[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 #define SMHASH_NONZERO(n) ((n) + !(n))
47 #define SMHASH_NEXT(h, hoff) ABS(((h) + ((hoff = SMHASH_NONZERO(hoff * 2) + 1), hoff)))
48
49 extern unsigned int hashsizes[];
50
51 void BLI_smallhash_init(SmallHash *hash)
52 {
53         int i;
54
55         memset(hash, 0, sizeof(*hash));
56
57         hash->table = hash->_stacktable;
58         hash->curhash = 2;
59         hash->size = hashsizes[hash->curhash];
60
61         hash->copytable = hash->_copytable;
62         hash->stacktable = hash->_stacktable;
63
64         for (i = 0; i < hash->size; i++) {
65                 hash->table[i].val = SMHASH_CELL_FREE;
66         }
67 }
68
69 /*NOTE: does *not* free *hash itself!  only the direct data!*/
70 void BLI_smallhash_release(SmallHash *hash)
71 {
72         if (hash == NULL) {
73                 return;
74         }
75
76         if (hash->table != hash->stacktable) {
77                 MEM_freeN(hash->table);
78         }
79 }
80
81 void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
82 {
83         int h, hoff=1;
84
85         if (hash->size < hash->used * 3) {
86                 int newsize = hashsizes[++hash->curhash];
87                 SmallHashEntry *tmp;
88                 int i = 0;
89
90                 if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
91                         tmp = MEM_callocN(sizeof(*hash->table) * newsize, __func__);
92                 }
93                 else {
94                         SWAP(SmallHashEntry *, hash->stacktable, hash->copytable);
95                         tmp = hash->stacktable;
96                 }
97
98                 SWAP(SmallHashEntry *, tmp, hash->table);
99
100                 hash->size = newsize;
101
102                 for (i = 0; i < hash->size; i++) {
103                         hash->table[i].val = SMHASH_CELL_FREE;
104                 }
105
106                 for (i = 0; i<hashsizes[hash->curhash - 1]; i++) {
107                         if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
108                                 continue;
109                         }
110
111                         h = ABS((int)(tmp[i].key));
112                         hoff = 1;
113                         while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
114                                 h = SMHASH_NEXT(h, hoff);
115                         }
116
117                         h %= newsize;
118
119                         hash->table[h].key = tmp[i].key;
120                         hash->table[h].val = tmp[i].val;
121                 }
122
123                 if (tmp != hash->stacktable && tmp != hash->copytable) {
124                         MEM_freeN(tmp);
125                 }
126         }
127
128         h = ABS((int)key);
129         hoff = 1;
130
131         while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
132                 h = SMHASH_NEXT(h, hoff);
133         }
134
135         h %= hash->size;
136         hash->table[h].key = key;
137         hash->table[h].val = item;
138
139         hash->used++;
140 }
141
142 void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
143 {
144         int h, hoff=1;
145
146         h = ABS((int)key);
147
148         while ((hash->table[h % hash->size].key != key) ||
149                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
150         {
151                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
152                         return;
153                 }
154
155                 h = SMHASH_NEXT(h, hoff);
156         }
157
158         h %= hash->size;
159         hash->table[h].key = 0;
160         hash->table[h].val = SMHASH_CELL_UNUSED;
161 }
162
163 void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
164 {
165         int h, hoff=1;
166         void *v;
167
168         h = ABS((int)key);
169
170         if (hash->table == NULL) {
171                 return NULL;
172         }
173
174         while ((hash->table[h % hash->size].key != key) ||
175                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
176         {
177                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
178                         return NULL;
179                 }
180
181                 h = SMHASH_NEXT(h, hoff);
182         }
183
184         v = hash->table[h % hash->size].val;
185         if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
186                 return NULL;
187         }
188
189         return v;
190 }
191
192
193 int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
194 {
195         int h = ABS((int)key);
196         int hoff =1;
197
198         if (hash->table == NULL) {
199                 return 0;
200         }
201
202         while ((hash->table[h % hash->size].key != key) ||
203                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
204         {
205                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
206                         return 0;
207                 }
208
209                 h = SMHASH_NEXT(h, hoff);
210         }
211
212         return !ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE);
213 }
214
215 int BLI_smallhash_count(SmallHash *hash)
216 {
217         return hash->used;
218 }
219
220 void *BLI_smallhash_iternext(SmallHashIter *iter, uintptr_t *key)
221 {
222         while (iter->i < iter->hash->size) {
223                 if (    (iter->hash->table[iter->i].val != SMHASH_CELL_UNUSED) &&
224                         (iter->hash->table[iter->i].val != SMHASH_CELL_FREE))
225                 {
226                         if (key) {
227                                 *key = iter->hash->table[iter->i].key;
228                         }
229
230                         iter->i++;
231
232                         return iter->hash->table[iter->i - 1].val;
233                 }
234
235                 iter->i++;
236         }
237
238         return NULL;
239 }
240
241 void *BLI_smallhash_iternew(SmallHash *hash, SmallHashIter *iter, uintptr_t *key)
242 {
243         iter->hash = hash;
244         iter->i = 0;
245
246         return BLI_smallhash_iternext(iter, key);
247 }
248
249 /* note, this was called _print_smhash in knifetool.c
250  * it may not be intended for general use - campbell */
251 #if 0
252 void BLI_smallhash_print(SmallHash *hash)
253 {
254         int i, linecol=79, c=0;
255
256         printf("{");
257         for (i=0; i<hash->size; i++) {
258                 if (hash->table[i].val == SMHASH_CELL_UNUSED) {
259                         printf("--u-");
260                 }
261                 else if (hash->table[i].val == SMHASH_CELL_FREE) {
262                         printf("--f-");
263                 }
264                 else    {
265                         printf("%2x", (unsigned int)hash->table[i].key);
266                 }
267
268                 if (i != hash->size-1)
269                         printf(", ");
270
271                 c += 6;
272
273                 if (c >= linecol) {
274                         printf("\n ");
275                         c = 0;
276                 }
277         }
278
279         fflush(stdout);
280 }
281 #endif