/[rdesktop]/sourceforge.net/trunk/seamlessrdp/ClientDLL/hash.cpp
This is repository of my old source code which isn't updated any more. Go to git.rot13.org for current projects!
ViewVC logotype

Diff of /sourceforge.net/trunk/seamlessrdp/ClientDLL/hash.cpp

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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