/[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 932 by astrand, Thu Jun 30 14:14:56 2005 UTC revision 933 by astrand, Thu Jun 30 14:46:14 2005 UTC
# Line 44  Line 44 
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    
# Line 54  static hash_table *the_table = NULL; Line 54  static hash_table *the_table = NULL;
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;
   
       if( NULL == temp )  
       {  
             table->size = 0;  
             return NULL;      /*HW: was 'table' */  
       }  
66    
67        for( i=0; i<size; i++ )      if (NULL == temp) {
68              temp[i] = NULL;          table->size = 0;
69            return NULL;            /*HW: was 'table' */
70        }
71    
72        return table;      for (i = 0; i < size; i++)
73            temp[i] = NULL;
74    
75        return table;
76  }  }
77    
78    
# Line 85  hash_table *hash_construct_table( hash_t Line 84  hash_table *hash_construct_table( hash_t
84    
85  static unsigned short hash(char *string)  static unsigned short hash(char *string)
86  {  {
87        unsigned short ret_val = 0;      unsigned short ret_val = 0;
88        int i;      int i;
89    
90        while (*string)      while (*string) {
91        {          /*
92              /*           ** RBS: Added conditional to account for strings in which the
93              ** RBS: Added conditional to account for strings in which the           ** length is less than an integral multiple of sizeof(int).
94              ** length is less than an integral multiple of sizeof(int).           **
95              **           ** Note: This fixes the problem of hasing trailing garbage, but
96              ** Note: This fixes the problem of hasing trailing garbage, but           ** doesn't fix the problem with some CPU's which can't align on
97              ** doesn't fix the problem with some CPU's which can't align on           ** byte boundries. Any decent C compiler *should* fix this, but
98              ** byte boundries. Any decent C compiler *should* fix this, but           ** it still might extract a performance hit. Also unaddressed is
99              ** it still might extract a performance hit. Also unaddressed is           ** what happens when using a CPU which addresses data only on
100              ** what happens when using a CPU which addresses data only on           ** 4-byte boundries when it tries to work with a pointer to a
101              ** 4-byte boundries when it tries to work with a pointer to a           ** 2-byte unsigned short.
102              ** 2-byte unsigned short.           */
103              */  
104            if (strlen(string) >= sizeof(unsigned short))
105              if (strlen(string) >= sizeof(unsigned short))              i = *(unsigned short *) string;
106                    i = *(unsigned short *)string;          else
107              else  i = (unsigned short)(*string);              i = (unsigned short) (*string);
108              ret_val ^= i;          ret_val ^= i;
109              ret_val <<= 1;          ret_val <<= 1;
110              string ++;          string++;
111        }      }
112        return ret_val;      return ret_val;
113  }  }
114    
115  /*  /*
# Line 119  static unsigned short hash(char *string) Line 118  static unsigned short hash(char *string)
118  ** NULL if the key wasn't in the table previously.  ** NULL if the key wasn't in the table previously.
119  */  */
120  /* HW: returns NULL if malloc failed */  /* HW: returns NULL if malloc failed */
121  void *hash_insert( char *key, void *data, hash_table *table )  void *hash_insert(char *key, void *data, hash_table * table)
122  {  {
123        unsigned short val = hash(key) % table->size;      unsigned short val = hash(key) % table->size;
124        bucket *ptr;      bucket *ptr;
125    
126        assert( NULL != key );      assert(NULL != key);
127    
128        /*      /*
129        ** NULL means this bucket hasn't been used yet.  We'll simply       ** 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       ** allocate space for our new bucket and put our data there, with
131        ** the table pointing at it.       ** the table pointing at it.
132        */       */
133    
134        if( NULL == (table->table)[val] )      if (NULL == (table->table)[val]) {
135        {          (table->table)[val] = (bucket *) malloc(sizeof(bucket));
136              (table->table)[val] = (bucket *)malloc(sizeof(bucket));          if (NULL == (table->table)[val])
137              if( NULL == (table->table)[val] )              return NULL;
138                    return NULL;  
139            if (NULL ==
140              if( NULL ==  ((table->table)[val]->key = (char*) malloc(strlen(key)+1)) )              ((table->table)[val]->key = (char *) malloc(strlen(key) + 1))) {
141              {              free((table->table)[val]);
142                    free( (table->table)[val] );              (table->table)[val] = NULL;
143                    (table->table)[val] = NULL;              return NULL;
144                    return NULL;          }
145              }          strcpy((table->table)[val]->key, key);
146              strcpy( (table->table)[val]->key, key);          (table->table)[val]->next = NULL;
147              (table->table)[val] -> next = NULL;          (table->table)[val]->data = data;
148              (table->table)[val] -> data = data;          table->count++;         /* HW */
149              table->count++; /* HW */          return (table->table)[val]->data;
150              return (table->table)[val] -> data;      }
       }  
151    
152  /* HW: added a #define so the hashtable can accept duplicate keys */  /* HW: added a #define so the hashtable can accept duplicate keys */
153  #ifndef DUPLICATE_KEYS  #ifndef DUPLICATE_KEYS
154          /*      /*
155          ** This spot in the table is already in use.  See if the current string       ** 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.       ** has already been inserted, and if so, increment its count.
157          */                                             /* HW: ^^^^^^^^ ?? */       *//* HW: ^^^^^^^^ ?? */
158        for( ptr = (table->table)[val]; NULL != ptr; ptr = ptr->next )      for (ptr = (table->table)[val]; NULL != ptr; ptr = ptr->next)
159              if( 0 == strcmp(key, ptr->key) )          if (0 == strcmp(key, ptr->key)) {
160              {              void *old_data;
161                    void *old_data;  
162                old_data = ptr->data;
163                    old_data = ptr->data;              ptr->data = data;
164                    ptr->data = data;              return old_data;
165                    return old_data;          }
             }  
166  #endif  #endif
167        /*      /*
168        ** This key must not be in the table yet.  We'll add it to the head of       ** 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       ** 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,       ** 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       ** 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       ** take place as soon as it was determined that the present key in the
173        ** list was larger than this one.       ** list was larger than this one.
174        */       */
175    
176        ptr = (bucket *)malloc(sizeof(bucket));      ptr = (bucket *) malloc(sizeof(bucket));
177        if( NULL == ptr )      if (NULL == ptr)
178              return NULL;      /*HW: was 0 */          return NULL;            /*HW: was 0 */
179    
180        if( NULL == (ptr -> key = (char*) malloc(strlen(key)+1)) )      if (NULL == (ptr->key = (char *) malloc(strlen(key) + 1))) {
181              {          free(ptr);
182              free(ptr);          return NULL;
183              return NULL;      }
184              }      strcpy(ptr->key, key);
185        strcpy( ptr->key, key );      ptr->data = data;
186        ptr -> data = data;      ptr->next = (table->table)[val];
187        ptr -> next = (table->table)[val];      (table->table)[val] = ptr;
188        (table->table)[val] = ptr;      table->count++;             /* HW */
       table->count++; /* HW */  
189    
190        return data;      return data;
191  }  }
192    
193    
# Line 199  void *hash_insert( char *key, void *data Line 195  void *hash_insert( char *key, void *data
195  ** Look up a key and return the associated data.  Returns NULL if  ** Look up a key and return the associated data.  Returns NULL if
196  ** the key is not in the table.  ** the key is not in the table.
197  */  */
198  void *hash_lookup( char *key, hash_table *table )  void *hash_lookup(char *key, hash_table * table)
199  {  {
200        unsigned short val = hash(key) % table->size;      unsigned short val = hash(key) % table->size;
201        bucket *ptr;      bucket *ptr;
202    
203        assert( NULL != key );      assert(NULL != key);
204    
205        if(NULL == (table->table)[val])      if (NULL == (table->table)[val])
206              return NULL;          return NULL;
207    
208        for( ptr = (table->table)[val]; NULL != ptr; ptr = ptr->next )      for (ptr = (table->table)[val]; NULL != ptr; ptr = ptr->next) {
209        {          if (0 == strcmp(key, ptr->key))
210              if(0 == strcmp( key, ptr -> key ) )              return ptr->data;
211                    return ptr->data;      }
       }  
212    
213        return NULL;      return NULL;
214  }  }
215    
216  /*  /*
# Line 223  void *hash_lookup( char *key, hash_table Line 218  void *hash_lookup( char *key, hash_table
218  ** data, or NULL if not present.  ** data, or NULL if not present.
219  */  */
220    
221  void *hash_del(char *key, hash_table *table)  void *hash_del(char *key, hash_table * table)
222  {  {
223        unsigned short val = hash(key) % table->size;      unsigned short val = hash(key) % table->size;
224        void *data;      void *data;
225        bucket *ptr, *last = NULL;      bucket *ptr, *last = NULL;
226    
227        assert( NULL != key );      assert(NULL != key);
228    
229        if( NULL == (table->table)[val] )      if (NULL == (table->table)[val])
230              return NULL;      /* HW: was 'return 0' */          return NULL;            /* HW: was 'return 0' */
231    
232        /*      /*
233        ** Traverse the list, keeping track of the previous node in the list.       ** 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       ** 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       ** 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       ** the key from the present node, and return a pointer to the data it
237        ** contains.       ** contains.
238        */       */
239        for( last = NULL, ptr = (table->table)[val];      for (last = NULL, ptr = (table->table)[val];
240                    NULL != ptr;           NULL != ptr; last = ptr, ptr = ptr->next) {
241                    last = ptr, ptr = ptr->next )          if (0 == strcmp(key, ptr->key)) {
242        {              if (last != NULL) {
243              if( 0 == strcmp( key, ptr -> key) )                  data = ptr->data;
244              {                  last->next = ptr->next;
245                    if( last != NULL )                  free(ptr->key);
246                    {                  free(ptr);
247                          data = ptr -> data;                  table->count--; /* HW */
248                          last -> next = ptr -> next;                  return data;
                         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;  
                   }  
249              }              }
       }  
250    
251        /*              /* If 'last' still equals NULL, it means that we need to
252        ** If we get here, it means we didn't find the item in the table.               ** delete the first node in the list. This simply consists
253        ** Signal this by returning NULL.               ** 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                    (table->table)[val] = ptr->next;
261                    free(ptr->key);
262                    free(ptr);
263                    table->count--; /* HW */
264                    return data;
265                }
266            }
267        }
268    
269        /*
270         ** If we get here, it means we didn't find the item in the table.
271         ** Signal this by returning NULL.
272         */
273    
274        return NULL;      return NULL;
275  }  }
276    
277  /*  /*
# Line 292  void *hash_del(char *key, hash_table *ta Line 282  void *hash_del(char *key, hash_table *ta
282  ** process the data as needed.  ** process the data as needed.
283  */  */
284    
285  static void free_node( char *key, void *data )  static void free_node(char *key, void *data)
286  {  {
287        (void) data;      (void) data;
288    
289        assert( NULL != key );      assert(NULL != key);
290    
291        if( NULL != function )      if (NULL != function) {
292        {          function(hash_del(key, the_table));
293              function( hash_del( key, the_table ) );      }
294        }      else
295        else          hash_del(key, the_table);
             hash_del( key, the_table );  
296  }  }
297    
298  /*  /*
# Line 314  static void free_node( char *key, void * Line 303  static void free_node( char *key, void *
303  ** it.  ** it.
304  */  */
305    
306  void hash_free_table( hash_table *table, void (*func)(void *) )  void hash_free_table(hash_table * table, void (*func) (void *))
307  {  {
308        function = func;      function = func;
309        the_table = table;      the_table = table;
310    
311        hash_enumerate( table, free_node );      hash_enumerate(table, free_node);
312        free( table->table );      free(table->table);
313        table->table = NULL;      table->table = NULL;
314        table->size = 0;      table->size = 0;
315        table->count = 0; /* HW */      table->count = 0;           /* HW */
316    
317        the_table = NULL;      the_table = NULL;
318        function = NULL;      function = NULL;
319  }  }
320    
321  /*  /*
# Line 334  void hash_free_table( hash_table *table, Line 323  void hash_free_table( hash_table *table,
323  ** node in the table, passing it the key and the associated data.  ** node in the table, passing it the key and the associated data.
324  */  */
325    
326  void hash_enumerate( hash_table *table, void (*func)(char *, void *) )  void hash_enumerate(hash_table * table, void (*func) (char *, void *))
327  {  {
328        unsigned i;      unsigned i;
329        bucket *temp;      bucket *temp;
330        bucket *swap;      bucket *swap;
331    
332        for( i=0; i<table->size; i++ )      for (i = 0; i < table->size; i++) {
333        {          if (NULL != (table->table)[i]) {
334              if( NULL != (table->table)[i] )              /* HW: changed this loop */
335              {              temp = (table->table)[i];
336                    /* HW: changed this loop */              while (NULL != temp) {
337                    temp = (table->table)[i];                  /* HW: swap trick, in case temp is freed by 'func' */
338                    while( NULL != temp )                  swap = temp->next;
339                    {                  func(temp->key, temp->data);
340                          /* HW: swap trick, in case temp is freed by 'func' */                  temp = swap;
                         swap = temp->next;  
                         func( temp -> key, temp->data );  
                         temp = swap;  
                   }  
341              }              }
342        }          }
343        }
344  }  }
345    
346  /*      HW: added hash_sorted_enum()  /*      HW: added hash_sorted_enum()
# Line 365  void hash_enumerate( hash_table *table, Line 351  void hash_enumerate( hash_table *table,
351  */  */
352    
353  typedef struct sort_struct  typedef struct sort_struct
354        {  {
355        char *key;      char *key;
356        void *data;      void *data;
357        } sort_struct;  } sort_struct;
358  static sort_struct *sortmap = NULL;  static sort_struct *sortmap = NULL;
359    
360  static int counter = 0;  static int counter = 0;
361    
362  /* HW: used as 'func' for hash_enumerate */  /* HW: used as 'func' for hash_enumerate */
363  static void key_get( char *key, void *data )  static void key_get(char *key, void *data)
364  {  {
365        sortmap[ counter ].key = key;      sortmap[counter].key = key;
366        sortmap[ counter ].data = data;      sortmap[counter].data = data;
367        counter++;      counter++;
368  }  }
369    
370  /* HW: used for comparing the keys in qsort */  /* HW: used for comparing the keys in qsort */
371  static int key_comp( const void* a, const void *b )  static int key_comp(const void *a, const void *b)
372  {  {
373        return strcmp( (*(sort_struct*)a).key, (*(sort_struct*)b).key );      return strcmp((*(sort_struct *) a).key, (*(sort_struct *) b).key);
374  }  }
375    
376  /*    HW: it's a compromise between speed and space. this one needs  /*    HW: it's a compromise between speed and space. this one needs
# Line 393  static int key_comp( const void* a, cons Line 379  static int key_comp( const void* a, cons
379        to hash_lookup the data of every key after sorting the key.        to hash_lookup the data of every key after sorting the key.
380        returns 0 on malloc failure, 1 on success        returns 0 on malloc failure, 1 on success
381  */  */
382  int hash_sorted_enum( hash_table *table, void (*func)( char *, void *) )  int hash_sorted_enum(hash_table * table, void (*func) (char *, void *))
383  {  {
384        int i;      int i;
385    
386        /* nothing to do ! */      /* nothing to do ! */
387        if( NULL == table || 0 == table->count || NULL == func )      if (NULL == table || 0 == table->count || NULL == func)
388              return 0;          return 0;
389    
390        /* malloc an pointerarray for all hashkey's and datapointers */      /* malloc an pointerarray for all hashkey's and datapointers */
391        if( NULL == ( sortmap = (sort_struct*) malloc( sizeof( sort_struct ) * table->count)) )      if (NULL ==
392              return 0;          (sortmap =
393             (sort_struct *) malloc(sizeof(sort_struct) * table->count)))
394            return 0;
395    
396        /* copy the pointers to the hashkey's */      /* copy the pointers to the hashkey's */
397        counter = 0;      counter = 0;
398        hash_enumerate( table, key_get );      hash_enumerate(table, key_get);
399    
400        /* sort the pointers to the keys */      /* sort the pointers to the keys */
401        qsort( sortmap, table->count, sizeof(sort_struct), key_comp );      qsort(sortmap, table->count, sizeof(sort_struct), key_comp);
402    
403        /* call the function for each node */      /* call the function for each node */
404        for( i=0; i <abs( (table->count)); i++ )      for (i = 0; i < abs((table->count)); i++) {
405        {          func(sortmap[i].key, sortmap[i].data);
406              func( sortmap[i].key, sortmap[i].data );      }
       }  
407    
408        /* free the pointerarray */      /* free the pointerarray */
409        free( sortmap );      free(sortmap);
410        sortmap = NULL;      sortmap = NULL;
411    
412        return 1;      return 1;
413  }  }
414    
415  /* HW: changed testmain */  /* HW: changed testmain */
# Line 436  FILE *o; Line 423  FILE *o;
423    
424  void fprinter(char *string, void *data)  void fprinter(char *string, void *data)
425  {  {
426        fprintf(o,"%s:    %s\n", string, (char *)data);      fprintf(o, "%s:    %s\n", string, (char *) data);
427  }  }
428    
429  void printer(char *string, void *data)  void printer(char *string, void *data)
430  {  {
431        printf("%s:    %s\n", string, (char *)data);      printf("%s:    %s\n", string, (char *) data);
432  }  }
433    
434  /* function to pass to hash_free_table */  /* function to pass to hash_free_table */
435  void strfree( void *d )  void strfree(void *d)
436  {  {
437        /* any additional processing goes here (if you use structures as data) */      /* any additional processing goes here (if you use structures as data) */
438        /* free the datapointer */      /* free the datapointer */
439        free(d);      free(d);
440  }  }
441    
442    
443  int main(void)  int main(void)
444  {  {
445        hash_table table;      hash_table table;
446    
447        char *strings[] = {      char *strings[] = {
448              "The first string",          "The first string",
449              "The second string",          "The second string",
450              "The third string",          "The third string",
451              "The fourth string",          "The fourth string",
452              "A much longer string than the rest in this example.",          "A much longer string than the rest in this example.",
453              "The last string",          "The last string",
454              NULL          NULL
455              };      };
456    
457        char *junk[] = {      char *junk[] = {
458              "The first data",          "The first data",
459              "The second data",          "The second data",
460              "The third data",          "The third data",
461              "The fourth data",          "The fourth data",
462              "The fifth datum",          "The fifth datum",
463              "The sixth piece of data"          "The sixth piece of data"
464              };      };
465    
466        int i;      int i;
467        void *j;      void *j;
468    
469        hash_construct_table(&table,211);      hash_construct_table(&table, 211);
470    
471        /* I know, no checking on strdup ;-)), but using strdup      /* I know, no checking on strdup ;-)), but using strdup
472              to demonstrate hash_table_free with a functionpointer */         to demonstrate hash_table_free with a functionpointer */
473        for (i = 0; NULL != strings[i]; i++ )      for (i = 0; NULL != strings[i]; i++)
474              hash_insert( strings[i], strdup(junk[i]), &table );          hash_insert(strings[i], strdup(junk[i]), &table);
475    
476        /* enumerating to a file */      /* enumerating to a file */
477        if( NULL != (o = fopen("HASH.HSH","wb")) )      if (NULL != (o = fopen("HASH.HSH", "wb"))) {
478        {          fprintf(o, "%d strings in the table:\n\n", table.count);
479              fprintf( o, "%d strings in the table:\n\n", table.count );          hash_enumerate(&table, fprinter);
480              hash_enumerate( &table, fprinter );          fprintf(o, "\nsorted by key:\n");
481              fprintf( o, "\nsorted by key:\n");          hash_sorted_enum(&table, fprinter);
482              hash_sorted_enum( &table, fprinter );          fclose(o);
483              fclose( o );      }
484        }  
485        /* enumerating to screen */
486        /* enumerating to screen */      hash_sorted_enum(&table, printer);
487        hash_sorted_enum( &table, printer );      printf("\n");
488        printf("\n");  
489        /* delete 3 strings, should be 3 left */
490        /* delete 3 strings, should be 3 left */      for (i = 0; i < 3; i++) {
491        for( i=0; i<3; i++ )          /* hash_del returns a pointer to the data */
492        {          strfree(hash_del(strings[i], &table));
493              /* hash_del returns a pointer to the data */      }
494              strfree( hash_del( strings[i], &table) );      hash_enumerate(&table, printer);
495        }  
496        hash_enumerate( &table, printer);      for (i = 0; NULL != strings[i]; i++) {
497            j = hash_lookup(strings[i], &table);
498        for (i=0;NULL != strings[i];i++)          if (NULL == j)
499        {              printf("\n'%s' is not in the table", strings[i]);
500              j = hash_lookup(strings[i], &table);          else
501              if (NULL == j)              printf("\n%s is still in the table.", strings[i]);
502                    printf("\n'%s' is not in the table", strings[i]);      }
             else  
                   printf("\n%s is still in the table.", strings[i]);  
       }  
503    
504        hash_free_table( &table, strfree );      hash_free_table(&table, strfree);
505    
506        return 0;      return 0;
507  }  }
508  #endif /* TEST */  #endif /* TEST */
Legend:
Removed from v.932  
changed lines
  Added in v.933
  ViewVC Help
Powered by ViewVC 1.1.26