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 VA_LIST_TO_STRING(key);
259 osrfHashNode* node = find_item( hash, (char*) VA_BUF, NULL );
260 if( !node ) return NULL;
264 osrfStringArray* osrfHashKeys( osrfHash* hash ) {
265 if(!hash) return NULL;
268 osrfStringArray* strings = osrfNewStringArray( hash->size );
270 // Add every key on the linked list
272 node = hash->first_key;
274 if( node->key ) // should always be true
275 osrfStringArrayAdd( strings, node->key );
283 unsigned long osrfHashGetCount( osrfHash* hash ) {
288 void osrfHashFree( osrfHash* hash ) {
295 for( i = 0; i != hash->hash->size; i++ ) {
296 if( ( list = OSRF_LIST_GET_INDEX( hash->hash, i )) ) {
297 for( j = 0; j != list->size; j++ ) {
298 if( (node = OSRF_LIST_GET_INDEX( list, j )) ) {
299 OSRF_HASH_NODE_FREE(hash, node);
306 osrfListFree(hash->hash);
310 osrfHashIterator* osrfNewHashIterator( osrfHash* hash ) {
311 if(!hash) return NULL;
312 osrfHashIterator* itr;
313 OSRF_MALLOC(itr, sizeof(osrfHashIterator));
315 itr->curr_node = NULL;
319 void* osrfHashIteratorNext( osrfHashIterator* itr ) {
320 if(!(itr && itr->hash)) return NULL;
322 // Advance to the next node in the linked list
324 if( NULL == itr->curr_node )
325 itr->curr_node = itr->hash->first_key;
327 itr->curr_node = itr->curr_node->next;
330 return itr->curr_node->item;
335 const char* osrfHashIteratorKey( const osrfHashIterator* itr ) {
336 if( itr && itr->curr_node )
337 return itr->curr_node->key;
342 void osrfHashIteratorFree( osrfHashIterator* itr ) {
347 void osrfHashIteratorReset( osrfHashIterator* itr ) {
349 itr->curr_node = NULL;
353 int osrfHashIteratorHasNext( osrfHashIterator* itr ) {
356 else if( itr->curr_node )
357 return itr->curr_node->next ? 1 : 0;
359 return itr->hash->first_key ? 1 : 0;