check NULL-ness on hash the key before calling find_item
[OpenSRF.git] / src / libopensrf / osrf_hash.c
1 /*
2 Copyright (C) 2007, 2008  Georgia Public Library Service
3 Bill Erickson <erickson@esilibrary.com>
4
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 as published by the Free Software Foundation; either version 2
8 of the License, or (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 GNU General Public License for more details.
14
15 -----------
16
17 An osrfHash is a hybrid between a hash table and a doubly linked
18 list.  The hash table supports random lookups by key.  The list
19 supports iterative traversals.  The sequence of entries in the
20 list reflects the sequence in which the entries were added.
21
22 osrfHashIterators are somewhat unusual in that, if an iterator
23 is positioned on a given entry, deletion of that entry does
24 not invalidate the iterator.  The entry to which it points is
25 logically but not physically deleted.  You can still advance
26 the iterator to the next entry in the list.
27
28 */
29
30 #include <opensrf/osrf_hash.h>
31
32 struct _osrfHashNodeStruct {
33         char* key;
34         void* item;
35         struct _osrfHashNodeStruct* prev;
36         struct _osrfHashNodeStruct* next;
37 };
38 typedef struct _osrfHashNodeStruct osrfHashNode;
39
40 struct _osrfHashStruct {
41         osrfList* hash; /* this hash */
42         void (*freeItem) (char* key, void* item);       /* callback for freeing stored items */
43         unsigned int size;
44         osrfHashNode* first_key;
45         osrfHashNode* last_key;
46 };
47
48 struct _osrfHashIteratorStruct {
49         osrfHash* hash;
50         osrfHashNode* curr_node;
51 };
52
53 /* 0x100 is a good size for small hashes */
54 //#define OSRF_HASH_LIST_SIZE 0x100  /* size of the main hash list */
55 #define OSRF_HASH_LIST_SIZE 0x10  /* size of the main hash list */
56
57
58 /* used internally */
59 #define OSRF_HASH_NODE_FREE(h, n) \
60         if(h && n) { \
61                 if(h->freeItem && n->key) h->freeItem(n->key, n->item);\
62                 free(n->key); free(n); \
63 }
64
65 osrfHash* osrfNewHash() {
66         osrfHash* hash;
67         OSRF_MALLOC(hash, sizeof(osrfHash));
68         hash->hash              = osrfNewList();
69         hash->first_key = NULL;
70         hash->last_key  = NULL;
71         return hash;
72 }
73
74 static osrfHashNode* osrfNewHashNode(char* key, void* item);
75
76 /* algorithm proposed by Donald E. Knuth 
77  * in The Art Of Computer Programming Volume 3 (more or less..)*/
78 /*
79 static unsigned int osrfHashMakeKey(char* str) {
80         if(!str) return 0;
81         unsigned int len = strlen(str);
82         unsigned int h = len;
83         unsigned int i = 0;
84         for(i = 0; i < len; str++, i++)
85                 h = ((h << 5) ^ (h >> 27)) ^ (*str);
86         return (h & (OSRF_HASH_LIST_SIZE-1));
87 }
88 */
89
90 /* macro version of the above function */
91 #define OSRF_HASH_MAKE_KEY(str,num) \
92    do {\
93       const char* k__ = str;\
94       unsigned int len__ = strlen(k__); \
95       unsigned int h__ = len__;\
96       unsigned int i__ = 0;\
97       for(i__ = 0; i__ < len__; k__++, i__++)\
98          h__ = ((h__ << 5) ^ (h__ >> 27)) ^ (*k__);\
99       num = (h__ & (OSRF_HASH_LIST_SIZE-1));\
100    } while(0)
101
102 /* Installs a callback function for freeing stored items */
103 void osrfHashSetCallback( osrfHash* hash, void (*callback) (char* key, void* item) )
104 {
105         if( hash ) hash->freeItem = callback;
106 }
107
108 /* Returns a pointer to the item's node if found; otherwise returns NULL. */
109 static osrfHashNode* find_item( const osrfHash* hash,
110                 const char* key, unsigned int* bucketkey ) {
111
112         // Find the sub-list in the hash table
113
114         if( hash->size < 6 && !bucketkey )
115         {
116                 // For only a few entries, when we don't need to identify
117                 // the hash bucket, it's probably faster to search the
118                 // linked list instead of hashing
119
120                 osrfHashNode* currnode = hash->first_key;
121                 while( currnode && strcmp( currnode->key, key ) )
122                          currnode = currnode->next;
123
124                 return currnode;
125         }
126                                 
127         unsigned int i = 0;
128         OSRF_HASH_MAKE_KEY(key,i);
129
130         // If asked, report which slot the key hashes to
131         if( bucketkey ) *bucketkey = i;
132
133         osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
134         if( !list ) { return NULL; }
135
136         // Search the sub-list
137         
138         int k;
139         osrfHashNode* node = NULL;
140         for( k = 0; k < list->size; k++ ) {
141                 node = OSRF_LIST_GET_INDEX(list, k);
142                 if( node && node->key && !strcmp(node->key, key) )
143                         return node;
144         }
145
146         return NULL;
147 }
148
149 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
150         if(!(key && item)) return NULL;
151         osrfHashNode* n;
152         OSRF_MALLOC(n, sizeof(osrfHashNode));
153         n->key = strdup(key);
154         n->item = item;
155         n->prev = NULL;
156         n->prev = NULL;
157         return n;
158 }
159
160 /* If an entry exists for a given key, update it; otherwise create it.
161    If an entry exists, and there is no callback function to destroy it,
162    return a pointer to it so that the calling code has the option of
163    destroying it.  Otherwise return NULL.
164 */
165 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
166         if(!(hash && item && key )) return NULL;
167
168         void* olditem = NULL;
169         unsigned int bucketkey;
170         
171         VA_LIST_TO_STRING(key);
172         osrfHashNode* node = find_item( hash, VA_BUF, &bucketkey );
173         if( node ) {
174
175                 // We already have an item for this key.  Update it in place.
176                 if( hash->freeItem ) {
177                         hash->freeItem( node->key, node->item );
178                 }
179                 else
180                         olditem = node->item;
181
182                 node->item = item;
183                 return olditem;
184         }
185         
186         osrfList* bucket;
187         if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
188                 bucket = osrfNewList();
189                 osrfListSet( hash->hash, bucket, bucketkey );
190         }
191
192         node = osrfNewHashNode(VA_BUF, item);
193         osrfListPushFirst( bucket, node );
194
195         hash->size++;
196
197         // Add the new hash node to the end of the linked list
198
199         if( NULL == hash->first_key )
200                 hash->first_key = hash->last_key = node;
201         else {
202                 node->prev = hash->last_key;
203                 hash->last_key->next = node;
204                 hash->last_key = node;
205         }
206         
207         return olditem;
208 }
209
210 /* Delete the entry for a specified key.  If the entry exists,
211    and there is no callback function to destroy the associated
212    item, return a pointer to the formerly associated item.
213    Otherwise return NULL.
214 */
215 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
216         if(!(hash && key )) return NULL;
217
218         VA_LIST_TO_STRING(key);
219
220         osrfHashNode* node = find_item( hash, VA_BUF, NULL );
221         if( !node ) return NULL;
222
223         hash->size--;
224
225         void* item = NULL;  // to be returned
226         if( hash->freeItem )
227                 hash->freeItem( node->key, node->item );
228         else
229                 item = node->item;
230
231         // Mark the node as logically deleted
232         
233         free(node->key);
234         node->key = NULL;
235         node->item = NULL;
236
237         // Make the node unreachable from the rest of the linked list.
238         // We leave the next and prev pointers in place so that an
239         // iterator parked here can find its way to an adjacent node.
240
241         if( node->prev )
242                 node->prev->next = node->next;
243         else
244                 hash->first_key = node->next;
245
246         if( node->next )
247                 node->next->prev = node->prev;
248         else
249                 hash->last_key = node->prev;
250         
251         return item;
252 }
253
254
255 void* osrfHashGet( osrfHash* hash, const char* key ) {
256         if(!(hash && key )) return NULL;
257         osrfHashNode* node = find_item( hash, key, NULL );
258         if( !node ) return NULL;
259         return node->item;
260 }
261
262 void* osrfHashGetFmt( osrfHash* hash, const char* key, ... ) {
263         if(!(hash && key )) return NULL;
264         VA_LIST_TO_STRING(key);
265
266         osrfHashNode* node = find_item( hash, (char*) VA_BUF, NULL );
267         if( !node ) return NULL;
268         return node->item;
269 }
270
271 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
272         if(!hash) return NULL;
273         
274         osrfHashNode* node;
275         osrfStringArray* strings = osrfNewStringArray( hash->size );
276
277         // Add every key on the linked list
278         
279         node = hash->first_key;
280         while( node ) {
281                 if( node->key )  // should always be true
282                         osrfStringArrayAdd( strings, node->key );
283                 node = node->next;
284         }
285         
286         return strings;
287 }
288
289
290 unsigned long osrfHashGetCount( osrfHash* hash ) {
291         if(!hash) return -1;
292         return hash->size;
293 }
294
295 void osrfHashFree( osrfHash* hash ) {
296         if(!hash) return;
297
298         int i, j;
299         osrfList* list;
300         osrfHashNode* node;
301
302         for( i = 0; i != hash->hash->size; i++ ) {
303                 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
304                         for( j = 0; j != list->size; j++ ) {
305                                 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
306                                         OSRF_HASH_NODE_FREE(hash, node);
307                                 }
308                         }
309                         osrfListFree(list);
310                 }
311         }
312
313         osrfListFree(hash->hash);
314         free(hash);
315 }
316
317 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
318         if(!hash) return NULL;
319         osrfHashIterator* itr;
320         OSRF_MALLOC(itr, sizeof(osrfHashIterator));
321         itr->hash = hash;
322         itr->curr_node = NULL;
323         return itr;
324 }
325
326 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
327         if(!(itr && itr->hash)) return NULL;
328
329         // Advance to the next node in the linked list
330         
331         if( NULL == itr->curr_node )
332                 itr->curr_node = itr->hash->first_key;
333         else
334                 itr->curr_node = itr->curr_node->next;
335
336         if( itr->curr_node )
337                 return itr->curr_node->item;
338         else
339                 return NULL;
340 }
341
342 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
343         if( itr && itr->curr_node )
344                 return itr->curr_node->key;
345         else
346                 return NULL;
347 }
348
349 void osrfHashIteratorFree( osrfHashIterator* itr ) {
350         if(itr)
351                 free(itr);
352 }
353
354 void osrfHashIteratorReset( osrfHashIterator* itr ) {
355         if(!itr) return;
356         itr->curr_node = NULL;
357 }
358
359
360 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
361         if( !itr )
362                 return 0;
363         else if( itr->curr_node )
364                 return itr->curr_node->next ? 1 : 0;
365         else
366                 return itr->hash->first_key ? 1 : 0;
367 }