reduce sign conversion comparisons for smallhash and tweak warnings elsewhere.
[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 #ifdef __GNUC__
47 #  pragma GCC diagnostic error "-Wsign-conversion"
48 #  if (__GNUC__ * 100 + __GNUC_MINOR__) >= 406  /* gcc4.6+ only */
49 #    pragma GCC diagnostic error "-Wsign-compare"
50 #    pragma GCC diagnostic error "-Wconversion"
51 #  endif
52 #endif
53
54 /* typically this re-assigns 'h' */
55 #define SMHASH_NEXT(h, hoff)  ( \
56         CHECK_TYPE_INLINE(&(h),    unsigned int), \
57         CHECK_TYPE_INLINE(&(hoff), unsigned int), \
58         ((h) + (((hoff) = ((hoff) * 2) + 1), (hoff))) \
59         )
60
61 extern unsigned int hashsizes[];
62
63 void BLI_smallhash_init(SmallHash *hash)
64 {
65         unsigned int i;
66
67         memset(hash, 0, sizeof(*hash));
68
69         hash->table = hash->_stacktable;
70         hash->curhash = 2;
71         hash->size = hashsizes[hash->curhash];
72
73         hash->copytable = hash->_copytable;
74         hash->stacktable = hash->_stacktable;
75
76         for (i = 0; i < hash->size; i++) {
77                 hash->table[i].val = SMHASH_CELL_FREE;
78         }
79 }
80
81 /*NOTE: does *not* free *hash itself!  only the direct data!*/
82 void BLI_smallhash_release(SmallHash *hash)
83 {
84         if (hash->table != hash->stacktable) {
85                 MEM_freeN(hash->table);
86         }
87 }
88
89 void BLI_smallhash_insert(SmallHash *hash, uintptr_t key, void *item)
90 {
91         unsigned int h, hoff = 1;
92
93         if (hash->size < hash->used * 3) {
94                 unsigned int newsize = hashsizes[++hash->curhash];
95                 SmallHashEntry *tmp;
96                 unsigned int i = 0;
97
98                 if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
99                         tmp = MEM_callocN(sizeof(*hash->table) * newsize, __func__);
100                 }
101                 else {
102                         SWAP(SmallHashEntry *, hash->stacktable, hash->copytable);
103                         tmp = hash->stacktable;
104                 }
105
106                 SWAP(SmallHashEntry *, tmp, hash->table);
107
108                 hash->size = newsize;
109
110                 for (i = 0; i < hash->size; i++) {
111                         hash->table[i].val = SMHASH_CELL_FREE;
112                 }
113
114                 for (i = 0; i < hashsizes[hash->curhash - 1]; i++) {
115                         if (ELEM(tmp[i].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
116                                 continue;
117                         }
118
119                         h = (unsigned int)(tmp[i].key);
120                         hoff = 1;
121                         while (!ELEM(hash->table[h % newsize].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
122                                 h = SMHASH_NEXT(h, hoff);
123                         }
124
125                         h %= newsize;
126
127                         hash->table[h].key = tmp[i].key;
128                         hash->table[h].val = tmp[i].val;
129                 }
130
131                 if (tmp != hash->stacktable && tmp != hash->copytable) {
132                         MEM_freeN(tmp);
133                 }
134         }
135
136         h = (unsigned int)(key);
137         hoff = 1;
138
139         while (!ELEM(hash->table[h % hash->size].val, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
140                 h = SMHASH_NEXT(h, hoff);
141         }
142
143         h %= hash->size;
144         hash->table[h].key = key;
145         hash->table[h].val = item;
146
147         hash->used++;
148 }
149
150 void BLI_smallhash_remove(SmallHash *hash, uintptr_t key)
151 {
152         unsigned int h, hoff = 1;
153
154         h = (unsigned int)(key);
155
156         while ((hash->table[h % hash->size].key != key) ||
157                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
158         {
159                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
160                         return;
161                 }
162
163                 h = SMHASH_NEXT(h, hoff);
164         }
165
166         h %= hash->size;
167         hash->table[h].key = 0;
168         hash->table[h].val = SMHASH_CELL_UNUSED;
169 }
170
171 void *BLI_smallhash_lookup(SmallHash *hash, uintptr_t key)
172 {
173         unsigned int h, hoff = 1;
174         void *v;
175
176         h = (unsigned int)(key);
177
178         while ((hash->table[h % hash->size].key != key) ||
179                (hash->table[h % hash->size].val == SMHASH_CELL_UNUSED))
180         {
181                 if (hash->table[h % hash->size].val == SMHASH_CELL_FREE) {
182                         return NULL;
183                 }
184
185                 h = SMHASH_NEXT(h, hoff);
186         }
187
188         v = hash->table[h % hash->size].val;
189         if (ELEM(v, SMHASH_CELL_UNUSED, SMHASH_CELL_FREE)) {
190                 return NULL;
191         }
192
193         return v;
194 }
195
196
197 int BLI_smallhash_haskey(SmallHash *hash, uintptr_t key)
198 {
199         unsigned int h = (unsigned int)(key);
200         unsigned int hoff = 1;
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 (int)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