2 Copyright (C) 2007, 2008 Georgia Public Library Service
3 Bill Erickson <erickson@esilibrary.com>
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.
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.
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.
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.
30 #include <opensrf/osrf_hash.h>
32 struct _osrfHashNodeStruct {
35 struct _osrfHashNodeStruct* prev;
36 struct _osrfHashNodeStruct* next;
38 typedef struct _osrfHashNodeStruct osrfHashNode;
40 struct _osrfHashStruct {
41 osrfList* hash; /* this hash */
42 void (*freeItem) (char* key, void* item); /* callback for freeing stored items */
44 osrfHashNode* first_key;
45 osrfHashNode* last_key;
48 struct _osrfHashIteratorStruct {
50 osrfHashNode* curr_node;
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 */
59 #define OSRF_HASH_NODE_FREE(h, n) \
61 if(h->freeItem && n->key) h->freeItem(n->key, n->item);\
62 free(n->key); free(n); \
65 osrfHash* osrfNewHash() {
67 OSRF_MALLOC(hash, sizeof(osrfHash));
68 hash->hash = osrfNewList();
69 hash->first_key = NULL;
70 hash->last_key = NULL;
74 static osrfHashNode* osrfNewHashNode(char* key, void* item);
76 /* algorithm proposed by Donald E. Knuth
77 * in The Art Of Computer Programming Volume 3 (more or less..)*/
79 static unsigned int osrfHashMakeKey(char* str) {
81 unsigned int len = strlen(str);
84 for(i = 0; i < len; str++, i++)
85 h = ((h << 5) ^ (h >> 27)) ^ (*str);
86 return (h & (OSRF_HASH_LIST_SIZE-1));
90 /* macro version of the above function */
91 #define OSRF_HASH_MAKE_KEY(str,num) \
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));\
102 /* Installs a callback function for freeing stored items */
103 void osrfHashSetCallback( osrfHash* hash, void (*callback) (char* key, void* item) )
105 if( hash ) hash->freeItem = callback;
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 ) {
112 // Find the sub-list in the hash table
114 if( hash->size < 6 && !bucketkey )
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
120 osrfHashNode* currnode = hash->first_key;
121 while( currnode && strcmp( currnode->key, key ) )
122 currnode = currnode->next;
128 OSRF_HASH_MAKE_KEY(key,i);
130 // If asked, report which slot the key hashes to
131 if( bucketkey ) *bucketkey = i;
133 osrfList* list = OSRF_LIST_GET_INDEX( hash->hash, i );
134 if( !list ) { return NULL; }
136 // Search the sub-list
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) )
149 static osrfHashNode* osrfNewHashNode(char* key, void* item) {
150 if(!(key && item)) return NULL;
152 OSRF_MALLOC(n, sizeof(osrfHashNode));
153 n->key = strdup(key);
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.
165 void* osrfHashSet( osrfHash* hash, void* item, const char* key, ... ) {
166 if(!(hash && item && key )) return NULL;
168 void* olditem = NULL;
169 unsigned int bucketkey;
171 VA_LIST_TO_STRING(key);
172 osrfHashNode* node = find_item( hash, VA_BUF, &bucketkey );
175 // We already have an item for this key. Update it in place.
176 if( hash->freeItem ) {
177 hash->freeItem( node->key, node->item );
180 olditem = node->item;
187 if( !(bucket = OSRF_LIST_GET_INDEX(hash->hash, bucketkey)) ) {
188 bucket = osrfNewList();
189 osrfListSet( hash->hash, bucket, bucketkey );
192 node = osrfNewHashNode(VA_BUF, item);
193 osrfListPushFirst( bucket, node );
197 // Add the new hash node to the end of the linked list
199 if( NULL == hash->first_key )
200 hash->first_key = hash->last_key = node;
202 node->prev = hash->last_key;
203 hash->last_key->next = node;
204 hash->last_key = node;
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.
215 void* osrfHashRemove( osrfHash* hash, const char* key, ... ) {
216 if(!(hash && key )) return NULL;
218 VA_LIST_TO_STRING(key);
220 osrfHashNode* node = find_item( hash, VA_BUF, NULL );
221 if( !node ) return NULL;
225 void* item = NULL; // to be returned
227 hash->freeItem( node->key, node->item );
231 // Mark the node as logically deleted
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.
242 node->prev->next = node->next;
244 hash->first_key = node->next;
247 node->next->prev = node->prev;
249 hash->last_key = node->prev;
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;
262 void* osrfHashGetFmt( osrfHash* hash, const char* key, ... ) {
263 if(!(hash && key )) return NULL;
264 VA_LIST_TO_STRING(key);
266 osrfHashNode* node = find_item( hash, (char*) VA_BUF, NULL );
267 if( !node ) return NULL;
271 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
272 if(!hash) return NULL;
275 osrfStringArray* strings = osrfNewStringArray( hash->size );
277 // Add every key on the linked list
279 node = hash->first_key;
281 if( node->key ) // should always be true
282 osrfStringArrayAdd( strings, node->key );
290 unsigned long osrfHashGetCount( osrfHash* hash ) {
295 void osrfHashFree( osrfHash* hash ) {
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);
313 osrfListFree(hash->hash);
317 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
318 if(!hash) return NULL;
319 osrfHashIterator* itr;
320 OSRF_MALLOC(itr, sizeof(osrfHashIterator));
322 itr->curr_node = NULL;
326 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
327 if(!(itr && itr->hash)) return NULL;
329 // Advance to the next node in the linked list
331 if( NULL == itr->curr_node )
332 itr->curr_node = itr->hash->first_key;
334 itr->curr_node = itr->curr_node->next;
337 return itr->curr_node->item;
342 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
343 if( itr && itr->curr_node )
344 return itr->curr_node->key;
349 void osrfHashIteratorFree( osrfHashIterator* itr ) {
354 void osrfHashIteratorReset( osrfHashIterator* itr ) {
356 itr->curr_node = NULL;
360 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
363 else if( itr->curr_node )
364 return itr->curr_node->next ? 1 : 0;
366 return itr->hash->first_key ? 1 : 0;