seamlessrdp/ClientDLL/hash.cpp

#include <string.h>
#include <stdlib.h> 
/* #define NDEBUG */
#include <assert.h>

#include "hash.h"


/*
** public domain code by Jerry Coffin.
**
** Tested with Visual C 1.0 and Borland C 3.1.
** Compiles without warnings, and seems like it should be pretty
** portable.
*/

/* HW: HenkJan Wolthuis, 1997, public domain
 
      changed functionnames, all public functions now have a 'hash_' prefix
      minor editing, marked 'm all(?) with a description
      removed a bug in hash_del and one in hash_enumerate
      added some assertions
      added a 'count' member to hold the number of elements
      added hash_sorted_enum, sometimes useful
      changed the testmain
*/

/*
** RBS: Bob Stout, 2003, public domain
**
**  1. Fixed some problems in hash() static function.
**  2. Use unsigned shorts for hash values. This was implicit in the original
**     which was written for PC's using early Microsoft and Borland compilers.
*/

/* HW: #define to allow duplicate keys, they're added before the existing
      key so hash_lookup finds the last one inserted first (LIFO)
      when not defined, hash_insert swaps the datapointers, returning a
      pointer to the old data
*/ 
/* #define DUPLICATE_KEYS */

/*
** These are used in freeing a table.  Perhaps I should code up
** something a little less grungy, but it works, so what the heck.
 */
static void ( *function ) ( void * ) = NULL;
static hash_table *the_table = NULL;


/* Initialize the hash_table to the size asked for.  Allocates space
** for the correct number of pointers and sets them to NULL.  If it
** can't allocate sufficient memory, signals error by setting the size
** of the table to 0.
*/ 
/*HW: changed, now returns NULL on malloc-failure */
hash_table *hash_construct_table( hash_table * table, size_t size )
{
    size_t i;
    bucket **temp;
    
    table->size = size;
    table->count = 0;
    table->table = ( bucket ** ) malloc( sizeof( bucket * ) * size );
    temp = table->table;
    
    if ( NULL == temp ) {
        table->size = 0;
        return NULL;            /*HW: was 'table' */
    }
    
    for ( i = 0; i < size; i++ )
        temp[ i ] = NULL;
        
    return table;
}


/*
** Hashes a string to produce an unsigned short, which should be
** sufficient for most purposes.
** RBS: fixed per user feedback from Steve Greenland
*/

static unsigned short hash( char *string )
{
    unsigned short ret_val = 0;
    int i;
    
    while ( *string ) {
        /*
         ** RBS: Added conditional to account for strings in which the
         ** length is less than an integral multiple of sizeof(int).
         **
         ** Note: This fixes the problem of hasing trailing garbage, but
         ** doesn't fix the problem with some CPU's which can't align on
         ** byte boundries. Any decent C compiler *should* fix this, but
         ** it still might extract a performance hit. Also unaddressed is
         ** what happens when using a CPU which addresses data only on
         ** 4-byte boundries when it tries to work with a pointer to a
         ** 2-byte unsigned short.
         */
        
        if ( strlen( string ) >= sizeof( unsigned short ) )
            i = *( unsigned short * ) string;
        else
            i = ( unsigned short ) ( *string );
        ret_val ^= i;
        ret_val <<= 1;
        string++;
    }
    return ret_val;
}

/*
** Insert 'key' into hash table.
** Returns pointer to old data associated with the key, if any, or
** NULL if the key wasn't in the table previously.
*/ 
/* HW: returns NULL if malloc failed */
void *hash_insert( char *key, void *data, hash_table * table )
{
    unsigned short val = hash( key ) % table->size;
    bucket *ptr;
    
    assert( NULL != key );
    
    /*
     ** NULL means this bucket hasn't been used yet.  We'll simply
     ** allocate space for our new bucket and put our data there, with
     ** the table pointing at it.
     */
    
    if ( NULL == ( table->table ) [ val ] ) {
        ( table->table ) [ val ] = ( bucket * ) malloc( sizeof( bucket ) );
        if ( NULL == ( table->table ) [ val ] )
            return NULL;
            
        if ( NULL ==
                ( ( table->table ) [ val ] ->key = ( char * ) malloc( strlen( key ) + 1 ) ) ) {
            free( ( table->table ) [ val ] );
            ( table->table ) [ val ] = NULL;
            return NULL;
        }
        strcpy( ( table->table ) [ val ] ->key, key );
        ( table->table ) [ val ] ->next = NULL;
        ( table->table ) [ val ] ->data = data;
        table->count++;         /* HW */
        return ( table->table ) [ val ] ->data;
    }
    
    /* HW: added a #define so the hashtable can accept duplicate keys */
#ifndef DUPLICATE_KEYS
    /*
     ** This spot in the table is already in use.  See if the current string
     ** has already been inserted, and if so, increment its count.
     */ /* HW: ^^^^^^^^ ?? */
    for ( ptr = ( table->table ) [ val ]; NULL != ptr; ptr = ptr->next )
        if ( 0 == strcmp( key, ptr->key ) ) {
            void * old_data;
            
            old_data = ptr->data;
            ptr->data = data;
            return old_data;
        }
#endif
    /*
     ** This key must not be in the table yet.  We'll add it to the head of
     ** the list at this spot in the hash table.  Speed would be
     ** slightly improved if the list was kept sorted instead.  In this case,
     ** this code would be moved into the loop above, and the insertion would
     ** take place as soon as it was determined that the present key in the
     ** list was larger than this one.
     */
    
    ptr = ( bucket * ) malloc( sizeof( bucket ) );
    if ( NULL == ptr )
        return NULL;            /*HW: was 0 */
        
    if ( NULL == ( ptr->key = ( char * ) malloc( strlen( key ) + 1 ) ) ) {
        free( ptr );
        return NULL;
    }
    strcpy( ptr->key, key );
    ptr->data = data;
    ptr->next = ( table->table ) [ val ];
    ( table->table ) [ val ] = ptr;
    table->count++;             /* HW */
    
    return data;
}


/*
** Look up a key and return the associated data.  Returns NULL if
** the key is not in the table.
*/
void *hash_lookup( char *key, hash_table * table )
{
    unsigned short val = hash( key ) % table->size;
    bucket *ptr;
    
    assert( NULL != key );
    
    if ( NULL == ( table->table ) [ val ] )
        return NULL;
        
    for ( ptr = ( table->table ) [ val ]; NULL != ptr; ptr = ptr->next ) {
        if ( 0 == strcmp( key, ptr->key ) )
            return ptr->data;
    }
    
    return NULL;
}

/*
** Delete a key from the hash table and return associated
** data, or NULL if not present.
*/

void *hash_del( char *key, hash_table * table )
{
    unsigned short val = hash( key ) % table->size;
    void *data;
    bucket *ptr, *last = NULL;
    
    assert( NULL != key );
    
    if ( NULL == ( table->table ) [ val ] )
        return NULL;            /* HW: was 'return 0' */
        
    /*
     ** Traverse the list, keeping track of the previous node in the list.
     ** When we find the node to delete, we set the previous node's next
     ** pointer to point to the node after ourself instead.      We then delete
     ** the key from the present node, and return a pointer to the data it
     ** contains.
     */
    for ( last = NULL, ptr = ( table->table ) [ val ];
            NULL != ptr; last = ptr, ptr = ptr->next ) {
        if ( 0 == strcmp( key, ptr->key ) ) {
            if ( last != NULL ) {
                data = ptr->data;
                last->next = ptr->next;
                free( ptr->key );
                free( ptr );
                table->count--; /* HW */
                return data;
            }
            
            /* If 'last' still equals NULL, it means that we need to
             ** delete the first node in the list. This simply consists
             ** of putting our own 'next' pointer in the array holding
             ** the head of the list. We then dispose of the current
             ** node as above.
             */
            else {
                /* HW: changed this bit to match the comments above */
                data = ptr->data;
                ( table->table ) [ val ] = ptr->next;
                free( ptr->key );
                free( ptr );
                table->count--; /* HW */
                return data;
            }
        }
    }
    
    /*
     ** If we get here, it means we didn't find the item in the table.
     ** Signal this by returning NULL.
     */
    
    return NULL;
}

/*
** free_table iterates the table, calling this repeatedly to free
** each individual node.  This, in turn, calls one or two other
** functions - one to free the storage used for the key, the other
** passes a pointer to the data back to a function defined by the user,
** process the data as needed.
*/

static void free_node( char *key, void *data )
{
    ( void ) data;
    
    assert( NULL != key );
    
    if ( NULL != function ) {
        function( hash_del( key, the_table ) );
    } else
        hash_del( key, the_table );
}

/*
** Frees a complete table by iterating over it and freeing each node.
** the second parameter is the address of a function it will call with a
** pointer to the data associated with each node.  This function is
** responsible for freeing the data, or doing whatever is needed with
** it.
*/

void hash_free_table( hash_table * table, void ( *func ) ( void * ) )
{
    function = func;
    the_table = table;
    
    hash_enumerate( table, free_node );
    free( table->table );
    table->table = NULL;
    table->size = 0;
    table->count = 0;           /* HW */
    
    the_table = NULL;
    function = NULL;
}

/*
** Simply invokes the function given as the second parameter for each
** node in the table, passing it the key and the associated data.
*/

void hash_enumerate( hash_table * table, void ( *func ) ( char *, void * ) )
{
    unsigned i;
    bucket *temp;
    bucket *swap;
    
    for ( i = 0; i < table->size; i++ ) {
        if ( NULL != ( table->table ) [ i ] ) {
            /* HW: changed this loop */
            temp = ( table->table ) [ i ];
            while ( NULL != temp ) {
                /* HW: swap trick, in case temp is freed by 'func' */
                swap = temp->next;
                func( temp->key, temp->data );
                temp = swap;
            }
        }
    }
}

/*      HW: added hash_sorted_enum()
 
      hash_sorted_enum is like hash_enumerate but gives
      sorted output. This is much slower than hash_enumerate, but
      sometimes nice for printing to a file...
*/

typedef struct sort_struct
{
    char *key;
    void *data;
}
sort_struct;
static sort_struct *sortmap = NULL;

static int counter = 0;

/* HW: used as 'func' for hash_enumerate */
static void key_get( char *key, void *data )
{
    sortmap[ counter ].key = key;
    sortmap[ counter ].data = data;
    counter++;
}

/* HW: used for comparing the keys in qsort */
static int key_comp( const void *a, const void *b )
{
    return strcmp( ( *( sort_struct * ) a ).key, ( *( sort_struct * ) b ).key );
}

/*    HW: it's a compromise between speed and space. this one needs
      table->count * sizeof( sort_struct) memory.
      Another approach only takes count*sizeof(char*), but needs
      to hash_lookup the data of every key after sorting the key.
      returns 0 on malloc failure, 1 on success
*/
int hash_sorted_enum( hash_table * table, void ( *func ) ( char *, void * ) )
{
    int i;
    
    /* nothing to do ! */
    if ( NULL == table || 0 == table->count || NULL == func )
        return 0;
        
    /* malloc an pointerarray for all hashkey's and datapointers */
    if ( NULL ==
            ( sortmap =
                  ( sort_struct * ) malloc( sizeof( sort_struct ) * table->count ) ) )
        return 0;
        
    /* copy the pointers to the hashkey's */
    counter = 0;
    hash_enumerate( table, key_get );
    
    /* sort the pointers to the keys */
    qsort( sortmap, table->count, sizeof( sort_struct ), key_comp );
    
    /* call the function for each node */
    for ( i = 0; i < abs( ( table->count ) ); i++ ) {
        func( sortmap[ i ].key, sortmap[ i ].data );
    }
    
    /* free the pointerarray */
    free( sortmap );
    sortmap = NULL;
    
    return 1;
}

/* HW: changed testmain */
#define TEST
#ifdef TEST

#include <stdio.h> 
//#include "snip_str.h" /* for strdup() */

FILE *o;

void fprinter( char *string, void *data )
{
    fprintf( o, "%s:    %s\n", string, ( char * ) data );
}

void printer( char *string, void *data )
{
    printf( "%s:    %s\n", string, ( char * ) data );
}

/* function to pass to hash_free_table */
void strfree( void *d )
{
    /* any additional processing goes here (if you use structures as data) */
    /* free the datapointer */
    free( d );
}


int main( void )
{
    hash_table table;
    
    char *strings[] = {
                          "The first string",
                          "The second string",
                          "The third string",
                          "The fourth string",
                          "A much longer string than the rest in this example.",
                          "The last string",
                          NULL
                      };
                      
    char *junk[] = {
                       "The first data",
                       "The second data",
                       "The third data",
                       "The fourth data",
                       "The fifth datum",
                       "The sixth piece of data"
                   };
                   
    int i;
    void *j;
    
    hash_construct_table( &table, 211 );
    
    /* I know, no checking on strdup ;-)), but using strdup
       to demonstrate hash_table_free with a functionpointer */
    for ( i = 0; NULL != strings[ i ]; i++ )
        hash_insert( strings[ i ], strdup( junk[ i ] ), &table );
        
    /* enumerating to a file */
    if ( NULL != ( o = fopen( "HASH.HSH", "wb" ) ) ) {
        fprintf( o, "%d strings in the table:\n\n", table.count );
        hash_enumerate( &table, fprinter );
        fprintf( o, "\nsorted by key:\n" );
        hash_sorted_enum( &table, fprinter );
        fclose( o );
    }
    
    /* enumerating to screen */
    hash_sorted_enum( &table, printer );
    printf( "\n" );
    
    /* delete 3 strings, should be 3 left */
    for ( i = 0; i < 3; i++ ) {
        /* hash_del returns a pointer to the data */
        strfree( hash_del( strings[ i ], &table ) );
    }
    hash_enumerate( &table, printer );
    
    for ( i = 0; NULL != strings[ i ]; i++ ) {
        j = hash_lookup( strings[ i ], &table );
        if ( NULL == j )
            printf( "\n'%s' is not in the table", strings[ i ] );
        else
            printf( "\n%s is still in the table.", strings[ i ] );
    }
    
    hash_free_table( &table, strfree );
    
    return 0;
}
#endif /* TEST */
1	astrand	930	#include <string.h>
2	astrand	992	#include <stdlib.h>
3	astrand	930	/* #define NDEBUG */
4			#include <assert.h>
5	astrand	918
6	astrand	930	#include "hash.h"
7
8
9	astrand	918	/*
10	astrand	930	** public domain code by Jerry Coffin.
11			**
12			** Tested with Visual C 1.0 and Borland C 3.1.
13			** Compiles without warnings, and seems like it should be pretty
14			** portable.
15			*/
16
17			/* HW: HenkJan Wolthuis, 1997, public domain
18	astrand	937
19	astrand	930	changed functionnames, all public functions now have a 'hash_' prefix
20			minor editing, marked 'm all(?) with a description
21			removed a bug in hash_del and one in hash_enumerate
22			added some assertions
23			added a 'count' member to hold the number of elements
24			added hash_sorted_enum, sometimes useful
25			changed the testmain
26			*/
27
28			/*
29	astrand	918	** RBS: Bob Stout, 2003, public domain
30			**
31			** 1. Fixed some problems in hash() static function.
32			** 2. Use unsigned shorts for hash values. This was implicit in the original
33			** which was written for PC's using early Microsoft and Borland compilers.
34			*/
35
36	astrand	930	/* HW: #define to allow duplicate keys, they're added before the existing
37			key so hash_lookup finds the last one inserted first (LIFO)
38			when not defined, hash_insert swaps the datapointers, returning a
39			pointer to the old data
40	astrand	992	*/
41	astrand	930	/* #define DUPLICATE_KEYS */
42
43			/*
44			** These are used in freeing a table. Perhaps I should code up
45			** something a little less grungy, but it works, so what the heck.
46			*/
47	astrand	992	static void ( function ) ( void ) = NULL;
48	astrand	930	static hash_table *the_table = NULL;
49
50
51			/* Initialize the hash_table to the size asked for. Allocates space
52			** for the correct number of pointers and sets them to NULL. If it
53			** can't allocate sufficient memory, signals error by setting the size
54			** of the table to 0.
55	astrand	992	*/
56	astrand	930	/HW: changed, now returns NULL on malloc-failure /
57	astrand	992	hash_table hash_construct_table( hash_table table, size_t size )
58	astrand	930	{
59	astrand	933	size_t i;
60			bucket **temp;
61	astrand	992
62	astrand	933	table->size = size;
63			table->count = 0;
64	astrand	992	table->table = ( bucket ** ) malloc( sizeof( bucket * ) * size );
65	astrand	933	temp = table->table;
66	astrand	992
67			if ( NULL == temp ) {
68	astrand	933	table->size = 0;
69			return NULL; /HW: was 'table' /
70			}
71	astrand	992
72			for ( i = 0; i < size; i++ )
73			temp[ i ] = NULL;
74
75	astrand	933	return table;
76	astrand	930	}
77
78
79			/*
80			** Hashes a string to produce an unsigned short, which should be
81			** sufficient for most purposes.
82			** RBS: fixed per user feedback from Steve Greenland
83			*/
84
85	astrand	992	static unsigned short hash( char *string )
86	astrand	930	{
87	astrand	933	unsigned short ret_val = 0;
88			int i;
89	astrand	992
90			while ( *string ) {
91	astrand	933	/*
92			** RBS: Added conditional to account for strings in which the
93			** length is less than an integral multiple of sizeof(int).
94			**
95			** Note: This fixes the problem of hasing trailing garbage, but
96			** doesn't fix the problem with some CPU's which can't align on
97			** byte boundries. Any decent C compiler should fix this, but
98			** it still might extract a performance hit. Also unaddressed is
99			** what happens when using a CPU which addresses data only on
100			** 4-byte boundries when it tries to work with a pointer to a
101			** 2-byte unsigned short.
102			*/
103	astrand	992
104			if ( strlen( string ) >= sizeof( unsigned short ) )
105			i = ( unsigned short ) string;
106	astrand	933	else
107	astrand	992	i = ( unsigned short ) ( *string );
108	astrand	933	ret_val ^= i;
109			ret_val <<= 1;
110			string++;
111			}
112			return ret_val;
113	astrand	930	}
114
115			/*
116			** Insert 'key' into hash table.
117			** Returns pointer to old data associated with the key, if any, or
118			** NULL if the key wasn't in the table previously.
119	astrand	992	*/
120	astrand	930	/* HW: returns NULL if malloc failed */
121	astrand	992	void hash_insert( char key, void data, hash_table table )
122	astrand	930	{
123	astrand	992	unsigned short val = hash( key ) % table->size;
124	astrand	933	bucket *ptr;
125	astrand	992
126			assert( NULL != key );
127
128	astrand	933	/*
129			** NULL means this bucket hasn't been used yet. We'll simply
130			** allocate space for our new bucket and put our data there, with
131			** the table pointing at it.
132			*/
133	astrand	992
134			if ( NULL == ( table->table ) [ val ] ) {
135			( table->table ) [ val ] = ( bucket * ) malloc( sizeof( bucket ) );
136			if ( NULL == ( table->table ) [ val ] )
137	astrand	933	return NULL;
138	astrand	992
139			if ( NULL ==
140			( ( table->table ) [ val ] ->key = ( char * ) malloc( strlen( key ) + 1 ) ) ) {
141			free( ( table->table ) [ val ] );
142			( table->table ) [ val ] = NULL;
143	astrand	933	return NULL;
144			}
145	astrand	992	strcpy( ( table->table ) [ val ] ->key, key );
146			( table->table ) [ val ] ->next = NULL;
147			( table->table ) [ val ] ->data = data;
148	astrand	933	table->count++; /* HW */
149	astrand	992	return ( table->table ) [ val ] ->data;
150	astrand	933	}
151	astrand	992
152	astrand	937	/* HW: added a #define so the hashtable can accept duplicate keys */
153	astrand	930	#ifndef DUPLICATE_KEYS
154	astrand	933	/*
155			** This spot in the table is already in use. See if the current string
156			** has already been inserted, and if so, increment its count.
157	astrand	992	/ / HW: ^^^^^^^^ ?? */
158			for ( ptr = ( table->table ) [ val ]; NULL != ptr; ptr = ptr->next )
159			if ( 0 == strcmp( key, ptr->key ) ) {
160			void * old_data;
161
162	astrand	933	old_data = ptr->data;
163			ptr->data = data;
164			return old_data;
165			}
166	astrand	930	#endif
167	astrand	933	/*
168			** This key must not be in the table yet. We'll add it to the head of
169			** the list at this spot in the hash table. Speed would be
170			** slightly improved if the list was kept sorted instead. In this case,
171			** this code would be moved into the loop above, and the insertion would
172			** take place as soon as it was determined that the present key in the
173			** list was larger than this one.
174			*/
175	astrand	992
176			ptr = ( bucket * ) malloc( sizeof( bucket ) );
177			if ( NULL == ptr )
178	astrand	933	return NULL; /HW: was 0 /
179	astrand	992
180			if ( NULL == ( ptr->key = ( char * ) malloc( strlen( key ) + 1 ) ) ) {
181			free( ptr );
182	astrand	933	return NULL;
183			}
184	astrand	992	strcpy( ptr->key, key );
185	astrand	933	ptr->data = data;
186	astrand	992	ptr->next = ( table->table ) [ val ];
187			( table->table ) [ val ] = ptr;
188	astrand	933	table->count++; /* HW */
189	astrand	992
190	astrand	933	return data;
191	astrand	930	}
192
193
194			/*
195			** Look up a key and return the associated data. Returns NULL if
196			** the key is not in the table.
197			*/
198	astrand	992	void hash_lookup( char key, hash_table * table )
199	astrand	930	{
200	astrand	992	unsigned short val = hash( key ) % table->size;
201	astrand	933	bucket *ptr;
202	astrand	992
203			assert( NULL != key );
204
205			if ( NULL == ( table->table ) [ val ] )
206	astrand	933	return NULL;
207	astrand	992
208			for ( ptr = ( table->table ) [ val ]; NULL != ptr; ptr = ptr->next ) {
209			if ( 0 == strcmp( key, ptr->key ) )
210	astrand	933	return ptr->data;
211			}
212	astrand	992
213	astrand	933	return NULL;
214	astrand	930	}
215
216			/*
217			** Delete a key from the hash table and return associated
218			** data, or NULL if not present.
219			*/
220
221	astrand	992	void hash_del( char key, hash_table * table )
222	astrand	930	{
223	astrand	992	unsigned short val = hash( key ) % table->size;
224	astrand	933	void *data;
225			bucket ptr, last = NULL;
226	astrand	992
227			assert( NULL != key );
228
229			if ( NULL == ( table->table ) [ val ] )
230	astrand	933	return NULL; /* HW: was 'return 0' */
231	astrand	992
232	astrand	933	/*
233			** Traverse the list, keeping track of the previous node in the list.
234			** When we find the node to delete, we set the previous node's next
235			** pointer to point to the node after ourself instead. We then delete
236			** the key from the present node, and return a pointer to the data it
237			** contains.
238			*/
239	astrand	992	for ( last = NULL, ptr = ( table->table ) [ val ];
240			NULL != ptr; last = ptr, ptr = ptr->next ) {
241			if ( 0 == strcmp( key, ptr->key ) ) {
242			if ( last != NULL ) {
243	astrand	933	data = ptr->data;
244			last->next = ptr->next;
245	astrand	992	free( ptr->key );
246			free( ptr );
247	astrand	933	table->count--; /* HW */
248			return data;
249			}
250	astrand	992
251	astrand	933	/* If 'last' still equals NULL, it means that we need to
252			** delete the first node in the list. This simply consists
253			** of putting our own 'next' pointer in the array holding
254			** the head of the list. We then dispose of the current
255			** node as above.
256			*/
257			else {
258			/* HW: changed this bit to match the comments above */
259			data = ptr->data;
260	astrand	992	( table->table ) [ val ] = ptr->next;
261			free( ptr->key );
262			free( ptr );
263	astrand	933	table->count--; /* HW */
264			return data;
265	astrand	930	}
266	astrand	933	}
267			}
268	astrand	992
269	astrand	933	/*
270			** If we get here, it means we didn't find the item in the table.
271			** Signal this by returning NULL.
272			*/
273	astrand	992
274	astrand	933	return NULL;
275	astrand	930	}
276
277			/*
278			** free_table iterates the table, calling this repeatedly to free
279			** each individual node. This, in turn, calls one or two other
280			** functions - one to free the storage used for the key, the other
281			** passes a pointer to the data back to a function defined by the user,
282			** process the data as needed.
283			*/
284
285	astrand	992	static void free_node( char key, void data )
286	astrand	930	{
287	astrand	992	( void ) data;
288
289			assert( NULL != key );
290
291			if ( NULL != function ) {
292			function( hash_del( key, the_table ) );
293	astrand	937	} else
294	astrand	992	hash_del( key, the_table );
295	astrand	930	}
296
297			/*
298			** Frees a complete table by iterating over it and freeing each node.
299			** the second parameter is the address of a function it will call with a
300			** pointer to the data associated with each node. This function is
301			** responsible for freeing the data, or doing whatever is needed with
302			** it.
303			*/
304
305	astrand	992	void hash_free_table( hash_table * table, void ( func ) ( void ) )
306	astrand	930	{
307	astrand	933	function = func;
308			the_table = table;
309	astrand	992
310			hash_enumerate( table, free_node );
311			free( table->table );
312	astrand	933	table->table = NULL;
313			table->size = 0;
314			table->count = 0; /* HW */
315	astrand	992
316	astrand	933	the_table = NULL;
317			function = NULL;
318	astrand	930	}
319
320			/*
321			** Simply invokes the function given as the second parameter for each
322			** node in the table, passing it the key and the associated data.
323			*/
324
325	astrand	992	void hash_enumerate( hash_table * table, void ( func ) ( char , void * ) )
326	astrand	930	{
327	astrand	933	unsigned i;
328			bucket *temp;
329			bucket *swap;
330	astrand	992
331			for ( i = 0; i < table->size; i++ ) {
332			if ( NULL != ( table->table ) [ i ] ) {
333	astrand	933	/* HW: changed this loop */
334	astrand	992	temp = ( table->table ) [ i ];
335			while ( NULL != temp ) {
336	astrand	933	/* HW: swap trick, in case temp is freed by 'func' */
337			swap = temp->next;
338	astrand	992	func( temp->key, temp->data );
339	astrand	933	temp = swap;
340	astrand	930	}
341	astrand	933	}
342			}
343	astrand	930	}
344
345			/* HW: added hash_sorted_enum()
346	astrand	937
347	astrand	930	hash_sorted_enum is like hash_enumerate but gives
348			sorted output. This is much slower than hash_enumerate, but
349			sometimes nice for printing to a file...
350			*/
351
352			typedef struct sort_struct
353	astrand	933	{
354			char *key;
355			void *data;
356	astrand	937	}
357			sort_struct;
358	astrand	930	static sort_struct *sortmap = NULL;
359
360			static int counter = 0;
361
362			/* HW: used as 'func' for hash_enumerate */
363	astrand	992	static void key_get( char key, void data )
364	astrand	930	{
365	astrand	992	sortmap[ counter ].key = key;
366			sortmap[ counter ].data = data;
367	astrand	933	counter++;
368	astrand	930	}
369
370			/* HW: used for comparing the keys in qsort */
371	astrand	992	static int key_comp( const void a, const void b )
372	astrand	930	{
373	astrand	992	return strcmp( ( ( sort_struct ) a ).key, ( ( sort_struct ) b ).key );
374	astrand	930	}
375
376			/* HW: it's a compromise between speed and space. this one needs
377			table->count * sizeof( sort_struct) memory.
378			Another approach only takes countsizeof(char), but needs
379			to hash_lookup the data of every key after sorting the key.
380			returns 0 on malloc failure, 1 on success
381			*/
382	astrand	992	int hash_sorted_enum( hash_table * table, void ( func ) ( char , void * ) )
383	astrand	930	{
384	astrand	933	int i;
385	astrand	992
386	astrand	933	/* nothing to do ! */
387	astrand	992	if ( NULL == table \|\| 0 == table->count \|\| NULL == func )
388	astrand	933	return 0;
389	astrand	992
390	astrand	933	/* malloc an pointerarray for all hashkey's and datapointers */
391	astrand	992	if ( NULL ==
392			( sortmap =
393			( sort_struct * ) malloc( sizeof( sort_struct ) * table->count ) ) )
394	astrand	933	return 0;
395	astrand	992
396	astrand	933	/* copy the pointers to the hashkey's */
397			counter = 0;
398	astrand	992	hash_enumerate( table, key_get );
399
400	astrand	933	/* sort the pointers to the keys */
401	astrand	992	qsort( sortmap, table->count, sizeof( sort_struct ), key_comp );
402
403	astrand	933	/* call the function for each node */
404	astrand	992	for ( i = 0; i < abs( ( table->count ) ); i++ ) {
405			func( sortmap[ i ].key, sortmap[ i ].data );
406	astrand	933	}
407	astrand	992
408	astrand	933	/* free the pointerarray */
409	astrand	992	free( sortmap );
410	astrand	933	sortmap = NULL;
411	astrand	992
412	astrand	933	return 1;
413	astrand	930	}
414
415			/* HW: changed testmain */
416			#define TEST
417			#ifdef TEST
418
419	astrand	992	#include <stdio.h>
420	astrand	930	//#include "snip_str.h" /* for strdup() */
421
422			FILE *o;
423
424	astrand	992	void fprinter( char string, void data )
425	astrand	930	{
426	astrand	992	fprintf( o, "%s: %s\n", string, ( char * ) data );
427	astrand	930	}
428
429	astrand	992	void printer( char string, void data )
430	astrand	930	{
431	astrand	992	printf( "%s: %s\n", string, ( char * ) data );
432	astrand	930	}
433
434			/* function to pass to hash_free_table */
435	astrand	992	void strfree( void *d )
436	astrand	930	{
437	astrand	933	/* any additional processing goes here (if you use structures as data) */
438			/* free the datapointer */
439	astrand	992	free( d );
440	astrand	930	}
441
442
443	astrand	992	int main( void )
444	astrand	930	{
445	astrand	933	hash_table table;
446	astrand	992
447	astrand	933	char *strings[] = {
448	astrand	937	"The first string",
449			"The second string",
450			"The third string",
451			"The fourth string",
452			"A much longer string than the rest in this example.",
453			"The last string",
454			NULL
455			};
456	astrand	992
457	astrand	933	char *junk[] = {
458	astrand	937	"The first data",
459			"The second data",
460			"The third data",
461			"The fourth data",
462			"The fifth datum",
463			"The sixth piece of data"
464			};
465	astrand	992
466	astrand	933	int i;
467			void *j;
468	astrand	992
469			hash_construct_table( &table, 211 );
470
471	astrand	933	/* I know, no checking on strdup ;-)), but using strdup
472			to demonstrate hash_table_free with a functionpointer */
473	astrand	992	for ( i = 0; NULL != strings[ i ]; i++ )
474			hash_insert( strings[ i ], strdup( junk[ i ] ), &table );
475
476	astrand	933	/* enumerating to a file */
477	astrand	992	if ( NULL != ( o = fopen( "HASH.HSH", "wb" ) ) ) {
478			fprintf( o, "%d strings in the table:\n\n", table.count );
479			hash_enumerate( &table, fprinter );
480			fprintf( o, "\nsorted by key:\n" );
481			hash_sorted_enum( &table, fprinter );
482			fclose( o );
483	astrand	933	}
484	astrand	992
485	astrand	933	/* enumerating to screen */
486	astrand	992	hash_sorted_enum( &table, printer );
487			printf( "\n" );
488
489	astrand	933	/* delete 3 strings, should be 3 left */
490	astrand	992	for ( i = 0; i < 3; i++ ) {
491	astrand	933	/* hash_del returns a pointer to the data */
492	astrand	992	strfree( hash_del( strings[ i ], &table ) );
493	astrand	933	}
494	astrand	992	hash_enumerate( &table, printer );
495
496			for ( i = 0; NULL != strings[ i ]; i++ ) {
497			j = hash_lookup( strings[ i ], &table );
498			if ( NULL == j )
499			printf( "\n'%s' is not in the table", strings[ i ] );
500	astrand	933	else
501	astrand	992	printf( "\n%s is still in the table.", strings[ i ] );
502	astrand	933	}
503	astrand	992
504			hash_free_table( &table, strfree );
505
506	astrand	933	return 0;
507	astrand	930	}
508			#endif /* TEST */