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