1 /****************************************************************************
2 *
3 * fthash.c
4 *
5 * Hashing functions (body).
6 *
7 */
8
9 /*
10 * Copyright 2000 Computing Research Labs, New Mexico State University
11 * Copyright 2001-2015
12 * Francesco Zappa Nardelli
13 *
14 * Permission is hereby granted, free of charge, to any person obtaining a
15 * copy of this software and associated documentation files (the "Software"),
16 * to deal in the Software without restriction, including without limitation
17 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 * and/or sell copies of the Software, and to permit persons to whom the
19 * Software is furnished to do so, subject to the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be included in
22 * all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY
28 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
29 * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
30 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 */
32
33 /**************************************************************************
34 *
35 * This file is based on code from bdf.c,v 1.22 2000/03/16 20:08:50
36 *
37 * taken from Mark Leisher's xmbdfed package
38 *
39 */
40
41
42 #include <freetype/internal/fthash.h>
43 #include <freetype/internal/ftmemory.h>
44
45
46 #define INITIAL_HT_SIZE 241
47
48
49 static FT_ULong
50 hash_str_lookup( FT_Hashkey* key )
51 {
52 const char* kp = key->str;
53 FT_ULong res = 0;
54
55
56 /* Mocklisp hash function. */
57 while ( *kp )
58 res = ( res << 5 ) - res + (FT_ULong)*kp++;
59
60 return res;
61 }
62
63
64 static FT_ULong
65 hash_num_lookup( FT_Hashkey* key )
66 {
67 FT_ULong num = (FT_ULong)key->num;
68 FT_ULong res;
69
70
71 /* Mocklisp hash function. */
72 res = num & 0xFF;
73 res = ( res << 5 ) - res + ( ( num >> 8 ) & 0xFF );
74 res = ( res << 5 ) - res + ( ( num >> 16 ) & 0xFF );
75 res = ( res << 5 ) - res + ( ( num >> 24 ) & 0xFF );
76
77 return res;
78 }
79
80
81 static FT_Bool
82 hash_str_compare( FT_Hashkey* a,
83 FT_Hashkey* b )
84 {
85 if ( a->str[0] == b->str[0] &&
86 ft_strcmp( a->str, b->str ) == 0 )
87 return 1;
88
89 return 0;
90 }
91
92
93 static FT_Bool
94 hash_num_compare( FT_Hashkey* a,
95 FT_Hashkey* b )
96 {
97 if ( a->num == b->num )
98 return 1;
99
100 return 0;
101 }
102
103
104 static FT_Hashnode*
105 hash_bucket( FT_Hashkey key,
106 FT_Hash hash )
107 {
108 FT_ULong res = 0;
109 FT_Hashnode* bp = hash->table;
110 FT_Hashnode* ndp;
111
112
113 res = (hash->lookup)( &key );
114
115 ndp = bp + ( res % hash->size );
116 while ( *ndp )
117 {
118 if ( (hash->compare)( &(*ndp)->key, &key ) )
119 break;
120
121 ndp--;
122 if ( ndp < bp )
123 ndp = bp + ( hash->size - 1 );
124 }
125
126 return ndp;
127 }
128
129
130 static FT_Error
131 hash_rehash( FT_Hash hash,
132 FT_Memory memory )
133 {
134 FT_Hashnode* obp = hash->table;
135 FT_Hashnode* bp;
136 FT_Hashnode* nbp;
137
138 FT_UInt i, sz = hash->size;
139 FT_Error error = FT_Err_Ok;
140
141
142 hash->size <<= 1;
143 hash->limit = hash->size / 3;
144
145 if ( FT_NEW_ARRAY( hash->table, hash->size ) )
146 goto Exit;
147
148 for ( i = 0, bp = obp; i < sz; i++, bp++ )
149 {
150 if ( *bp )
151 {
152 nbp = hash_bucket( (*bp)->key, hash );
153 *nbp = *bp;
154 }
155 }
156
157 FT_FREE( obp );
158
159 Exit:
160 return error;
161 }
162
163
164 static FT_Error
165 hash_init( FT_Hash hash,
166 FT_Bool is_num,
167 FT_Memory memory )
168 {
169 FT_UInt sz = INITIAL_HT_SIZE;
170 FT_Error error;
171
172
173 hash->size = sz;
174 hash->limit = sz / 3;
175 hash->used = 0;
176
177 if ( is_num )
178 {
179 hash->lookup = hash_num_lookup;
180 hash->compare = hash_num_compare;
181 }
182 else
183 {
184 hash->lookup = hash_str_lookup;
185 hash->compare = hash_str_compare;
186 }
187
188 FT_MEM_NEW_ARRAY( hash->table, sz );
189
190 return error;
191 }
192
193
194 FT_Error
195 ft_hash_str_init( FT_Hash hash,
196 FT_Memory memory )
197 {
198 return hash_init( hash, 0, memory );
199 }
200
201
202 FT_Error
203 ft_hash_num_init( FT_Hash hash,
204 FT_Memory memory )
205 {
206 return hash_init( hash, 1, memory );
207 }
208
209
210 void
211 ft_hash_str_free( FT_Hash hash,
212 FT_Memory memory )
213 {
214 if ( hash )
215 {
216 FT_UInt sz = hash->size;
217 FT_Hashnode* bp = hash->table;
218 FT_UInt i;
219
220
221 for ( i = 0; i < sz; i++, bp++ )
222 FT_FREE( *bp );
223
224 FT_FREE( hash->table );
225 }
226 }
227
228
229 /* `ft_hash_num_free' is the same as `ft_hash_str_free' */
230
231
232 static FT_Error
233 hash_insert( FT_Hashkey key,
234 size_t data,
235 FT_Hash hash,
236 FT_Memory memory )
237 {
238 FT_Hashnode nn;
239 FT_Hashnode* bp = hash_bucket( key, hash );
240 FT_Error error = FT_Err_Ok;
241
242
243 nn = *bp;
244 if ( !nn )
245 {
246 if ( FT_QNEW( nn ) )
247 goto Exit;
248 *bp = nn;
249
250 nn->key = key;
251 nn->data = data;
252
253 if ( hash->used >= hash->limit )
254 {
255 error = hash_rehash( hash, memory );
256 if ( error )
257 goto Exit;
258 }
259
260 hash->used++;
261 }
262 else
263 nn->data = data;
264
265 Exit:
266 return error;
267 }
268
269
270 FT_Error
271 ft_hash_str_insert( const char* key,
272 size_t data,
273 FT_Hash hash,
274 FT_Memory memory )
275 {
276 FT_Hashkey hk;
277
278
279 hk.str = key;
280
281 return hash_insert( hk, data, hash, memory );
282 }
283
284
285 FT_Error
286 ft_hash_num_insert( FT_Int num,
287 size_t data,
288 FT_Hash hash,
289 FT_Memory memory )
290 {
291 FT_Hashkey hk;
292
293
294 hk.num = num;
295
296 return hash_insert( hk, data, hash, memory );
297 }
298
299
300 static size_t*
301 hash_lookup( FT_Hashkey key,
302 FT_Hash hash )
303 {
304 FT_Hashnode* np = hash_bucket( key, hash );
305
306
307 return (*np) ? &(*np)->data
308 : NULL;
309 }
310
311
312 size_t*
313 ft_hash_str_lookup( const char* key,
314 FT_Hash hash )
315 {
316 FT_Hashkey hk;
317
318
319 hk.str = key;
320
321 return hash_lookup( hk, hash );
322 }
323
324
325 size_t*
326 ft_hash_num_lookup( FT_Int num,
327 FT_Hash hash )
328 {
329 FT_Hashkey hk;
330
331
332 hk.num = num;
333
334 return hash_lookup( hk, hash );
335 }
336
337
338 /* END */