=bmesh=
[blender.git] / source / blender / blenlib / BLI_smallhash.h
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 #ifndef BLI_SMALLHASH_H
29 #define BLI_SMALLHASH_H
30
31 /*******a light stack-friendly hash library******
32  *      (it uses stack space for smallish hash tables)     */
33
34 /*based on a doubling non-chaining approach */
35
36 #include "MEM_guardedalloc.h"
37 #include "BLO_sys_types.h"
38 #include "BLI_utildefines.h"
39
40 extern unsigned int hashsizes[];
41 #define NONHASH -25436536
42 typedef struct entry {intptr_t key; void *val;} entry;
43
44 #define SMSTACKSIZE     521
45 typedef struct SmallHash {
46         entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE];
47         entry *stacktable, *copytable;
48         int used;
49         int curhash;
50         int size;
51 } SmallHash;
52
53 /*CELL_UNUSED means this cell is inside a key series, while CELL_FREE
54   means this cell terminates a key series.
55   
56   no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
57   imagine.  hopefully. */
58 #define CELL_UNUSED     ((void*)0x7FFFFFFF)
59 #define CELL_FREE       ((void*)0x7FFFFFFD)
60
61 #define NONZERO(n) ((n) + !(n))
62 #define HASHNEXT(h, hoff) ABS(((h) + ((hoff=NONZERO(hoff*2)+1), hoff)))
63
64 BM_INLINE void BLI_smallhash_init(SmallHash *hash)
65 {
66         int i;
67         
68         memset(hash, 0, sizeof(*hash));
69         
70         hash->table = hash->_stacktable;
71         hash->curhash = 2;
72         hash->size = hashsizes[hash->curhash];
73         
74         hash->copytable = hash->_copytable;
75         hash->stacktable = hash->_stacktable;
76         
77         for (i=0; i<hash->size; i++) {
78                 hash->table[i].val = CELL_FREE;
79         }
80 }
81
82 /*NOTE: does *not* free *hash itself!  only the direct data!*/
83 BM_INLINE void BLI_smallhash_release(SmallHash *hash)
84 {
85         if (!hash)
86                 return;
87         
88         if (hash->table != hash->stacktable)
89                 MEM_freeN(hash->table);
90 }
91
92 BM_INLINE void BLI_smallhash_insert(SmallHash *hash, intptr_t key, void *item) 
93 {
94         int h, hoff=1;
95
96         key = ABS(key);
97
98         if (hash->size < hash->used*3) {
99                 int newsize = hashsizes[++hash->curhash];
100                 entry *tmp;
101                 int i = 0;
102                 
103                 if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
104                         tmp = MEM_callocN(sizeof(*hash->table)*newsize, "new hashkeys");
105                 } else {
106                         SWAP(entry*, hash->stacktable, hash->copytable);
107                         tmp = hash->stacktable;
108                 }
109                 
110                 SWAP(entry*, tmp, hash->table);
111                 
112                 hash->size = newsize;
113                 
114                 for (i=0; i<hash->size; i++) {
115                         hash->table[i].val = CELL_FREE;
116                 }
117                 
118                 for (i=0; i<hashsizes[hash->curhash-1]; i++) {
119                         if (ELEM(tmp[i].val, CELL_UNUSED, CELL_FREE))
120                                 continue;
121                         
122                         h = tmp[i].key; hoff = 1;
123                         while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE))
124                                 h = HASHNEXT(h, hoff);
125                         
126                         h %= newsize;
127                         
128                         hash->table[h].key = tmp[i].key;
129                         hash->table[h].val = tmp[i].val;
130                 }
131                 
132                 if (tmp != hash->stacktable && tmp != hash->copytable) {
133                         MEM_freeN(tmp);
134                 }
135         }
136         
137         h = key; hoff = 1;
138         while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE))
139                 h = HASHNEXT(h, hoff);
140         
141         h %= hash->size;
142         hash->table[h].key = key;
143         hash->table[h].val = item;
144         
145         hash->used++;
146 }
147
148 BM_INLINE void BLI_smallhash_remove(SmallHash *hash, intptr_t key)
149 {
150         int h, hoff=1;
151
152         key = ABS(key);
153         h = key;
154         
155         while (hash->table[h % hash->size].key != key 
156               || hash->table[h % hash->size].val == CELL_UNUSED)
157         {
158                 if (hash->table[h % hash->size].val == CELL_FREE)
159                         return;
160                 h = HASHNEXT(h, hoff);
161         }
162         
163         h %= hash->size;
164         hash->table[h].key = 0;
165         hash->table[h].val = CELL_UNUSED;
166 }
167
168 BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, intptr_t key)
169 {
170         int h, hoff=1;
171
172         key = ABS(key);
173         h = key;
174         
175         if (!hash->table)
176                 return NULL;
177         
178         while (hash->table[h % hash->size].key != key 
179               || hash->table[h % hash->size].val == CELL_UNUSED)
180         {
181                 if (hash->table[h % hash->size].val == CELL_FREE)
182                         return NULL;
183                 h = HASHNEXT(h, hoff);
184         }
185         
186         return hash->table[h % hash->size].val;
187 }
188
189
190 BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, intptr_t key)
191 {
192         int h = ABS(key), hoff=1;
193         key = ABS(key);
194         
195         if (!hash->table)
196                 return 0;
197         
198         while (hash->table[h % hash->size].key != key 
199               || hash->table[h % hash->size].val == CELL_UNUSED)
200         {
201                 if (hash->table[h % hash->size].val == CELL_FREE)
202                         return 0;
203                 h = HASHNEXT(h, hoff);
204         }
205         
206         return 1;
207 }
208
209 BM_INLINE int BLI_smallhash_count(SmallHash *hash)
210 {
211         return hash->used;
212 }
213
214 #endif // BLI_SMALLHASH_H