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 <ft2build.h>
43#include FT_INTERNAL_HASH_H
44#include FT_INTERNAL_MEMORY_H
45
46
47#define INITIAL_HT_SIZE 241
48
49
50 static FT_ULong
51 hash_str_lookup( FT_Hashkey* key )
52 {
53 const char* kp = key->str;
54 FT_ULong res = 0;
55
56
57 /* Mocklisp hash function. */
58 while ( *kp )
59 res = ( res << 5 ) - res + (FT_ULong)*kp++;
60
61 return res;
62 }
63
64
65 static FT_ULong
66 hash_num_lookup( FT_Hashkey* key )
67 {
68 FT_ULong num = (FT_ULong)key->num;
69 FT_ULong res;
70
71
72 /* Mocklisp hash function. */
73 res = num & 0xFF;
74 res = ( res << 5 ) - res + ( ( num >> 8 ) & 0xFF );
75 res = ( res << 5 ) - res + ( ( num >> 16 ) & 0xFF );
76 res = ( res << 5 ) - res + ( ( num >> 24 ) & 0xFF );
77
78 return res;
79 }
80
81
82 static FT_Bool
83 hash_str_compare( FT_Hashkey* a,
84 FT_Hashkey* b )
85 {
86 if ( a->str[0] == b->str[0] &&
87 ft_strcmp( a->str, b->str ) == 0 )
88 return 1;
89
90 return 0;
91 }
92
93
94 static FT_Bool
95 hash_num_compare( FT_Hashkey* a,
96 FT_Hashkey* b )
97 {
98 if ( a->num == b->num )
99 return 1;
100
101 return 0;
102 }
103
104
105 static FT_Hashnode*
106 hash_bucket( FT_Hashkey key,
107 FT_Hash hash )
108 {
109 FT_ULong res = 0;
110 FT_Hashnode* bp = hash->table;
111 FT_Hashnode* ndp;
112
113
114 res = (hash->lookup)( &key );
115
116 ndp = bp + ( res % hash->size );
117 while ( *ndp )
118 {
119 if ( (hash->compare)( &(*ndp)->key, &key ) )
120 break;
121
122 ndp--;
123 if ( ndp < bp )
124 ndp = bp + ( hash->size - 1 );
125 }
126
127 return ndp;
128 }
129
130
131 static FT_Error
132 hash_rehash( FT_Hash hash,
133 FT_Memory memory )
134 {
135 FT_Hashnode* obp = hash->table;
136 FT_Hashnode* bp;
137 FT_Hashnode* nbp;
138
139 FT_UInt i, sz = hash->size;
140 FT_Error error = FT_Err_Ok;
141
142
143 hash->size <<= 1;
144 hash->limit = hash->size / 3;
145
146 if ( FT_NEW_ARRAY( hash->table, hash->size ) )
147 goto Exit;
148
149 for ( i = 0, bp = obp; i < sz; i++, bp++ )
150 {
151 if ( *bp )
152 {
153 nbp = hash_bucket( (*bp)->key, hash );
154 *nbp = *bp;
155 }
156 }
157
158 FT_FREE( obp );
159
160 Exit:
161 return error;
162 }
163
164
165 static FT_Error
166 hash_init( FT_Hash hash,
167 FT_Bool is_num,
168 FT_Memory memory )
169 {
170 FT_UInt sz = INITIAL_HT_SIZE;
171 FT_Error error;
172
173
174 hash->size = sz;
175 hash->limit = sz / 3;
176 hash->used = 0;
177
178 if ( is_num )
179 {
180 hash->lookup = hash_num_lookup;
181 hash->compare = hash_num_compare;
182 }
183 else
184 {
185 hash->lookup = hash_str_lookup;
186 hash->compare = hash_str_compare;
187 }
188
189 FT_MEM_NEW_ARRAY( hash->table, sz );
190
191 return error;
192 }
193
194
195 FT_Error
196 ft_hash_str_init( FT_Hash hash,
197 FT_Memory memory )
198 {
199 return hash_init( hash, 0, memory );
200 }
201
202
203 FT_Error
204 ft_hash_num_init( FT_Hash hash,
205 FT_Memory memory )
206 {
207 return hash_init( hash, 1, memory );
208 }
209
210
211 void
212 ft_hash_str_free( FT_Hash hash,
213 FT_Memory memory )
214 {
215 if ( hash )
216 {
217 FT_UInt sz = hash->size;
218 FT_Hashnode* bp = hash->table;
219 FT_UInt i;
220
221
222 for ( i = 0; i < sz; i++, bp++ )
223 FT_FREE( *bp );
224
225 FT_FREE( hash->table );
226 }
227 }
228
229
230 /* `ft_hash_num_free' is the same as `ft_hash_str_free' */
231
232
233 static FT_Error
234 hash_insert( FT_Hashkey key,
235 size_t data,
236 FT_Hash hash,
237 FT_Memory memory )
238 {
239 FT_Hashnode nn;
240 FT_Hashnode* bp = hash_bucket( key, hash );
241 FT_Error error = FT_Err_Ok;
242
243
244 nn = *bp;
245 if ( !nn )
246 {
247 if ( FT_NEW( nn ) )
248 goto Exit;
249 *bp = nn;
250
251 nn->key = key;
252 nn->data = data;
253
254 if ( hash->used >= hash->limit )
255 {
256 error = hash_rehash( hash, memory );
257 if ( error )
258 goto Exit;
259 }
260
261 hash->used++;
262 }
263 else
264 nn->data = data;
265
266 Exit:
267 return error;
268 }
269
270
271 FT_Error
272 ft_hash_str_insert( const char* key,
273 size_t data,
274 FT_Hash hash,
275 FT_Memory memory )
276 {
277 FT_Hashkey hk;
278
279
280 hk.str = key;
281
282 return hash_insert( hk, data, hash, memory );
283 }
284
285
286 FT_Error
287 ft_hash_num_insert( FT_Int num,
288 size_t data,
289 FT_Hash hash,
290 FT_Memory memory )
291 {
292 FT_Hashkey hk;
293
294
295 hk.num = num;
296
297 return hash_insert( hk, data, hash, memory );
298 }
299
300
301 static size_t*
302 hash_lookup( FT_Hashkey key,
303 FT_Hash hash )
304 {
305 FT_Hashnode* np = hash_bucket( key, hash );
306
307
308 return (*np) ? &(*np)->data
309 : NULL;
310 }
311
312
313 size_t*
314 ft_hash_str_lookup( const char* key,
315 FT_Hash hash )
316 {
317 FT_Hashkey hk;
318
319
320 hk.str = key;
321
322 return hash_lookup( hk, hash );
323 }
324
325
326 size_t*
327 ft_hash_num_lookup( FT_Int num,
328 FT_Hash hash )
329 {
330 FT_Hashkey hk;
331
332
333 hk.num = num;
334
335 return hash_lookup( hk, hash );
336 }
337
338
339/* END */
340