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