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