1 /*
2 * Copyright (C) 2000-2005 Chris Ross and various contributors
3 * Copyright (C) 1999-2000 Chris Ross
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * o Redistributions of source code must retain the above copyright notice, this
10 * list of conditions and the following disclaimer.
11 * o Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 * o Neither the name of the ferite software nor the names of its contributors may
15 * be used to endorse or promote products derived from this software without
16 * specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 #ifdef HAVE_CONFIG_HEADER
32 #include "../config.h"
33 #endif
34
35 #include "ferite.h"
36
37 /**
38 * @group Hashes
39 * @description How could any program survive without hashing? The hash functions
40 * below provide a good hashing system implementation which is used
41 * throughout the ferite engine. They can be used to store anything
42 * and form the basis for namespaces.
43 */
44
45 extern int ferite_pow_lookup[];
46
47 /**
48 * @function ferite_hash_gen
49 * @declaration unsigned int ferite_hash_gen( char *key, size_t keylen )
50 * @brief Generate a hash value given a key and a hash length
51 * @param char *key The value to hash
52 * @param size_t keylen The size of the hash
53 * @return An unsigned integer value representing the hash value
54 */
ferite_hash_gen(char * key,size_t keylen)55 unsigned int ferite_hash_gen( char *key, size_t keylen )
56 {
57 size_t i;
58 unsigned int hashval = 0;
59
60 FE_ENTER_FUNCTION;
61 for( i = 0; i < keylen; i++ )
62 hashval = *key++ + 31 * hashval;
63 FE_LEAVE_FUNCTION( hashval );
64 }
65
ferite_create_hash_bucket(FeriteScript * script,char * key,void * value)66 FeriteHashBucket *ferite_create_hash_bucket( FeriteScript *script, char *key, void *value )
67 {
68 FeriteHashBucket *ptr;
69 size_t len;
70
71 FE_ENTER_FUNCTION;
72 len = strlen( key );
73 ptr = fmalloc( sizeof( FeriteHashBucket ) + len + 1 );
74 ptr->id = (char *)ptr + sizeof( FeriteHashBucket );
75 ptr->hashval = ferite_hash_gen( key, len );
76 ptr->data = value;
77 ptr->next = NULL;
78 strcpy( ptr->id, key );
79 FE_LEAVE_FUNCTION( ptr );
80 }
81
82 /**
83 * @function ferite_create_hash
84 * @declaration FeriteHash *ferite_create_hash( FeriteScript *script, int size )
85 * @brief Create a hash table
86 * @param FeriteScript *script The script
87 * @param int size The initial size of the hash
88 * @return A new hash table
89 */
ferite_create_hash(FeriteScript * script,int size)90 FeriteHash *ferite_create_hash( FeriteScript *script, int size )
91 {
92 FeriteHash *ptr;
93 int i = 4; /* We don't want to small bucketsizes */
94
95 FE_ENTER_FUNCTION;
96 while( size > ferite_pow_lookup[i] )
97 i++;
98 size = ferite_pow_lookup[i];
99 ptr = fcalloc( 1, sizeof( FeriteHash ) + ( size * sizeof( FeriteHashBucket* ) ) );
100 ptr->size = size;
101 ptr->hash = (void*)((char *)ptr + sizeof( FeriteHash ));
102 FE_LEAVE_FUNCTION( ptr );
103 }
104
105 /**
106 * @function ferite_delete_hash
107 * @declaration void ferite_delete_hash( FeriteScript *script, FeriteHash *hash, void (*cb)(FeriteScript*,void *data) )
108 * @brief Delete a hash table
109 * @param FeriteScript *script The script
110 * @param FeriteHash *hash The hash table to delete
111 * @param void cb The function to call to delete the hash's contents
112 */
ferite_delete_hash(FeriteScript * script,FeriteHash * hash,void (* cb)(FeriteScript *,void * data))113 void ferite_delete_hash( FeriteScript *script, FeriteHash *hash, void (*cb)(FeriteScript*,void *data) )
114 {
115 int i;
116 FeriteHashBucket *bucket, *next;
117
118 FE_ENTER_FUNCTION;
119 FE_ASSERT( hash != NULL );
120 if( hash->hash != NULL )
121 {
122 for( i = 0; i < hash->size; i++ )
123 {
124 for( bucket = hash->hash[i]; bucket; bucket = next )
125 {
126 next = bucket->next;
127 if( cb )
128 (cb)( script, bucket->data );
129 ffree( bucket );
130 }
131 }
132 }
133
134 ffree( hash );
135 FE_LEAVE_FUNCTION( NOWT );
136 }
137
138 /**
139 * @function ferite_process_hash
140 * @declaration void ferite_process_hash( FeriteScript *script, FeriteHash *hash, void (*cb)(FeriteScript*,void *data) )
141 * @brief Process a hash table by calling a function on each element
142 * @param FeriteScript *script The script
143 * @param FeriteHash *hash The hash table to process
144 * @param void cb The function to call to process the hash's contents
145 */
ferite_process_hash(FeriteScript * script,FeriteHash * hash,void (* cb)(FeriteScript *,void * data,char * key))146 void ferite_process_hash( FeriteScript *script, FeriteHash *hash, void (*cb)(FeriteScript*,void *data,char *key) )
147 {
148 int i;
149 FeriteHashBucket *bucket, *next;
150
151 FE_ENTER_FUNCTION;
152 FE_ASSERT( hash != NULL );
153 for( i = 0; i < hash->size; i++ )
154 {
155 for( bucket = hash->hash[i]; bucket; bucket = next )
156 {
157 next = bucket->next;
158 if( cb )
159 (cb)( script, bucket->data, bucket->id );
160 }
161 }
162 FE_LEAVE_FUNCTION( NOWT );
163 }
164
165 /**
166 * @function ferite_hash_add
167 * @declaration void ferite_hash_add( FeriteScript *script, FeriteHash *hash, char *key, void *data )
168 * @brief Add data to the hash
169 * @param FeriteScript *script The script
170 * @param FeriteHash *hash The hash to insert the data into
171 * @param char *key The key on which to hash the data
172 * @param void *data A pointer to some data to keep
173 */
ferite_hash_add(FeriteScript * script,FeriteHash * hash,char * key,void * data)174 void ferite_hash_add( FeriteScript *script, FeriteHash *hash, char *key, void *data )
175 {
176 int loc;
177 unsigned int hashval;
178 FeriteHashBucket *ptr;
179
180 FE_ENTER_FUNCTION;
181 FE_ASSERT( hash != NULL && key != NULL );
182
183 hashval = ferite_hash_gen( key, strlen( key ) );
184 loc = hashval & hash->size - 1;
185 FUD(( "HASH: Adding %s to key %d\n", key, loc ));
186
187 ptr = ferite_create_hash_bucket( script, key, data );
188 ptr->next = hash->hash[loc];
189 hash->hash[loc] = ptr;
190 FE_LEAVE_FUNCTION( NOWT );
191 }
192
193 /**
194 * @function ferite_hash_get
195 * @declaration void *ferite_hash_get( FeriteScript *script, FeriteHash *hash, char *key )
196 * @brief Get the data at a specified key
197 * @param FeriteScript *script The script to pass around
198 * @param FeriteHash *hash The hash to get the data from
199 * @param char *key The key to obtain the data for
200 * @return The pointer to the data or NULL otherwise
201 */
ferite_hash_get(FeriteScript * script,FeriteHash * hash,char * key)202 void *ferite_hash_get( FeriteScript *script, FeriteHash *hash, char *key )
203 {
204 int loc;
205 unsigned int hashval;
206 FeriteHashBucket *ptr;
207
208 FE_ENTER_FUNCTION;
209
210 FE_ASSERT( hash != NULL && key != NULL );
211
212 hashval = ferite_hash_gen( key, strlen( key ) );
213 loc = hashval & hash->size - 1;
214 for( ptr = hash->hash[loc]; ptr != NULL; ptr = ptr->next )
215 {
216 FUD(("HASH: Testing \"%s\" for a match on \"%s\"\n", ptr->id, key ));
217 if( ptr->hashval == hashval && strcmp( key, ptr->id ) == 0 )
218 {
219 FUD(("HASH: located data\n"));
220 FE_LEAVE_FUNCTION( ptr->data );
221 }
222 }
223 FUD(("HASH: Could not find data, returning NULL\n"));
224 FE_LEAVE_FUNCTION( NULL );
225 }
226
227 /**
228 * @function ferite_create_iterator
229 * @declaration FeriteIterator *ferite_create_iterator( FeriteScript *script )
230 * @brief Create an iterator to iterate over a hash
231 * @param FeriteScript *script The script
232 * @return A pointer to an iterator
233 */
ferite_create_iterator(FeriteScript * script)234 FeriteIterator *ferite_create_iterator( FeriteScript *script )
235 {
236 FeriteIterator *iter;
237
238 FE_ENTER_FUNCTION;
239 iter = fmalloc(sizeof(FeriteIterator));
240 iter->curbucket = NULL;
241 iter->curindex = 0;
242 FE_LEAVE_FUNCTION( iter );
243 }
244
245 /**
246 * @function ferite_hash_walk
247 * @declaration FeriteHashBucket *ferite_hash_walk(FeriteScript *script, FeriteHash *hash, FeriteIterator *iter)
248 * @brief Walk the hash
249 * @param FeriteScript *script The script
250 * @param FeriteHash *hash The hash to walk over
251 * @param FeriteIterator *iter The iterator to use
252 * @description Each time this function is called it will return the next data value
253 * @return The next hash bucket, NULL if there are no more
254 */
ferite_hash_walk(FeriteScript * script,FeriteHash * hash,FeriteIterator * iter)255 FeriteHashBucket *ferite_hash_walk(FeriteScript *script, FeriteHash *hash, FeriteIterator *iter)
256 {
257 int i;
258
259 FE_ENTER_FUNCTION;
260
261 FE_ASSERT( hash != NULL && iter != NULL );
262
263 if(iter->curbucket == NULL)
264 {
265 for(i = 0; i < hash->size; i++)
266 {
267 if(hash->hash[i] != NULL)
268 {
269 iter->curbucket = hash->hash[i];
270 iter->curindex = i;
271 FE_LEAVE_FUNCTION( iter->curbucket );
272 }
273 }
274 FE_LEAVE_FUNCTION( iter->curbucket );
275 }
276
277 if(iter->curbucket->next != NULL)
278 {
279 iter->curbucket = iter->curbucket->next;
280 FE_LEAVE_FUNCTION( iter->curbucket );
281 }
282 else
283 {
284 iter->curindex++;
285 }
286
287 for(i = iter->curindex; i < hash->size; i++)
288 {
289 if(hash->hash[i] != NULL)
290 {
291 iter->curbucket = hash->hash[i];
292 iter->curindex = i;
293 FE_LEAVE_FUNCTION( iter->curbucket );
294 }
295 }
296
297 FE_LEAVE_FUNCTION( NULL );
298 }
299
300 /**
301 * @function ferite_hash_update
302 * @declaration void ferite_hash_update( FeriteScript *script, FeriteHash *hash, char *key, char *data )
303 * @brief Update a value at the specified hash key
304 * @param FeriteScript *script The script
305 * @param FeriteHash *hash The has to update
306 * @param char *key The key to the bucket to update
307 * @param char *data Pointer to the data
308 */
ferite_hash_update(FeriteScript * script,FeriteHash * hash,char * key,char * data)309 void ferite_hash_update( FeriteScript *script, FeriteHash *hash, char *key, char *data )
310 {
311 int loc;
312 unsigned int hashval;
313 FeriteHashBucket *ptr;
314
315 FE_ENTER_FUNCTION;
316 FE_ASSERT( hash != NULL && key != NULL );
317
318 hashval = ferite_hash_gen( key, strlen( key ) );
319 loc = hashval & hash->size - 1;
320 for( ptr = hash->hash[loc]; ptr != NULL; ptr = ptr->next )
321 {
322 FUD(("HASH: Testing \"%s\" for a match on \"%s\"\n", ptr->id, key ));
323 if( ptr->hashval == hashval && strcmp( key, ptr->id ) == 0 )
324 {
325 FUD(("HASH: located data\n"));
326 ptr->data = data;
327 FE_LEAVE_FUNCTION(NOWT);
328 }
329 }
330 FUD(("HASH: Could not find data, returning NULL\n"));
331 FE_LEAVE_FUNCTION(NOWT);
332 }
333
334 /**
335 * @function ferite_hash_delete
336 * @declaration void ferite_hash_delete( FeriteScript *script, FeriteHash *hash, char *key )
337 * @brief Delete a key from the hash
338 * @param FeriteScript *script The script to delete
339 * @param FeriteHash *hash The hash to delete from
340 * @param char *key The key to delete
341 */
ferite_hash_delete(FeriteScript * script,FeriteHash * hash,char * key)342 void ferite_hash_delete( FeriteScript *script, FeriteHash *hash, char *key )
343 {
344 int loc = 0;
345 unsigned int hashval = 0;
346 FeriteHashBucket *ptr = NULL;
347 FeriteHashBucket *optr = NULL;
348
349 FE_ENTER_FUNCTION;
350 FE_ASSERT( hash != NULL && key != NULL );
351
352 hashval = ferite_hash_gen( key, strlen( key ) );
353 loc = hashval & hash->size - 1;
354 for( ptr = hash->hash[loc]; ptr != NULL; optr = ptr, ptr = ptr->next )
355 {
356 FUD(("HASH: Testing \"%s\" for a match on \"%s\"\n", ptr->id, key ));
357 if( ptr->hashval == hashval && strcmp( key, ptr->id ) == 0 )
358 {
359 if( hash->hash[loc] == ptr )
360 hash->hash[loc] = ptr->next; /* remove head from array */
361 else
362 optr->next = ptr->next; /* remove buxket from list */
363 FUD(("HASH: located data\n"));
364 ffree( ptr );
365 FE_LEAVE_FUNCTION( NOWT );
366 }
367 }
368 FUD(("HASH: Could not find data, returning NULL\n"));
369 FE_LEAVE_FUNCTION( NOWT );
370 }
371
372 /**
373 * @function ferite_hash_dup
374 * @declaration FeriteHash *ferite_hash_dup( FeriteScript *script, FeriteHash *hash, void *(*ddup)( FeriteScript*,void *data,void *data2 ), void *data2 )
375 * @brief Duplicate a hash
376 * @param FeriteScript *script The script
377 * @param FeriteHash *hash The hash table to duplicate
378 * @param void *ddup The function that gets called with to duplicate a buckets data
379 * @return A new hash that is an exact copy of the original
380 */
ferite_hash_dup(FeriteScript * script,FeriteHash * hash,void * (* ddup)(FeriteScript *,void * data,void * data2),void * data2)381 FeriteHash *ferite_hash_dup( FeriteScript *script, FeriteHash *hash, void *(*ddup)( FeriteScript*,void *data,void *data2 ), void *data2 )
382 {
383 FeriteHash *ptr;
384 FeriteHashBucket *bptr, *nbptr;
385 int i;
386
387 FE_ENTER_FUNCTION;
388 FE_ASSERT( hash != NULL );
389 ptr = ferite_create_hash( script, hash->size );
390 for( i = 0; i < hash->size; i++ )
391 {
392 bptr = hash->hash[i];
393 while( bptr )
394 {
395 nbptr = ferite_create_hash_bucket( script, bptr->id, (ddup)(script,bptr->data,data2) );
396 nbptr->next = ptr->hash[i];
397 ptr->hash[i] = nbptr;
398 bptr = bptr->next;
399 }
400 }
401 FE_LEAVE_FUNCTION( ptr );
402 }
403
404 /**
405 * @function ferite_hash_grow
406 * @declaration FeriteHash *ferite_hash_grow( FeriteScript *script, FeriteHash *hash )
407 * @brief Grow the hash table to be faster
408 * @param FeriteScript *script The script
409 * @param FeriteHash *hash The hash to modify
410 * @return The pointer to the new hash (this may be the same as the passed in hash)
411 */
ferite_hash_grow(FeriteScript * script,FeriteHash * hash)412 FeriteHash *ferite_hash_grow( FeriteScript *script, FeriteHash *hash )
413 {
414 FeriteHash *newhash;
415 FeriteHashBucket *ptr, *next;
416 int size, i, loc;
417
418 FE_ENTER_FUNCTION;
419 if( (size = hash->size * 4) > 8192 )
420 size = 8192;
421 if( hash->size >= 8192 )
422 FE_LEAVE_FUNCTION( hash );
423 newhash = fcalloc( 1, sizeof( FeriteHash ) + ( size * sizeof( FeriteHashBucket ) ) );
424 newhash->hash = (void*)((char *)newhash + sizeof( FeriteHash ));
425 newhash->size = size;
426
427 for( i = 0; i < hash->size; i++ )
428 {
429 for( ptr = hash->hash[i]; ptr != NULL; ptr = next )
430 {
431 next = ptr->next;
432 loc = ptr->hashval & newhash->size - 1;
433 ptr->next = newhash->hash[loc];
434 newhash->hash[loc] = ptr;
435 }
436 }
437 ffree( hash );
438 FE_LEAVE_FUNCTION( newhash );
439 }
440
441 /**
442 * @function ferite_hash_print
443 * @declaration void ferite_hash_print( FeriteScript *script, FeriteHash *hash )
444 * @brief Print out the hash table if debug mode is turned on
445 * @param FeriteScript *script The script to delete
446 * @param FeriteHash *hash The has to print out
447 * @description This simply prints out what keys are in the hash for debug purposes
448 */
ferite_hash_print(FeriteScript * script,FeriteHash * hash)449 void ferite_hash_print( FeriteScript *script, FeriteHash *hash )
450 {
451 FeriteHashBucket *bptr = NULL;
452 int i = 0;
453
454 FE_ENTER_FUNCTION;
455 FE_ASSERT( hash != NULL );
456 FUD(("hash table-------------------------------\nsize: %d\n", hash->size));
457 for( i = 0; i < hash->size; i++ )
458 {
459 FUD(("hash->hash[%d]:", i));
460 if( hash->hash[i] != NULL )
461 {
462 for( bptr = hash->hash[i]; bptr != NULL; bptr = bptr->next )
463 {
464 FUD(("-->'%s'", bptr->id ));
465 }
466 FUD(("-->NULL\n"));
467 }
468 else
469 {
470 FUD(("-->NULL\n"));
471 }
472 }
473 FE_LEAVE_FUNCTION(NOWT);
474 }
475
476 /**
477 * @end
478 */
479