code_c/Maasha/src/lib/hash.c

   1 /* Martin Asser Hansen (mail@maasha.dk) Copyright (C) 2008 - All right reserved */
   2
   3 #include "common.h"
   4 #include "mem.h"
   5 #include "hash.h"
   6 #include "list.h"
   7
   8
   9 hash *hash_new( size_t size )
  10 {
  11     /* Martin A. Hansen, June 2008 */
  12
  13     /* Initialize a new generic hash structure. */
  14
  15     hash   *new_hash   = NULL;
  16     size_t  table_size = 0;
  17
  18     new_hash = mem_get( sizeof( new_hash ) );
  19
  20     table_size = 1 << size;   /* table_size = ( 2 ** size ) */
  21
  22     new_hash->table_size   = table_size;
  23     new_hash->mask         = table_size - 1;
  24     new_hash->table        = mem_get( sizeof( hash_elem * ) * table_size );
  25     new_hash->nmemb        = 0;
  26     new_hash->index_table  = 0;
  27     new_hash->index_bucket = mem_get( sizeof( hash_elem ) );
  28     new_hash->index_bucket = NULL;
  29
  30     return new_hash;
  31 }
  32
  33
  34 hash_elem *hash_elem_new()
  35 {
  36     /* Martin A. Hansen, November 2008. */
  37
  38     /* Initializes a new hash_elem structure. */
  39
  40     hash_elem *new_elem = NULL;
  41
  42     new_elem = mem_get( sizeof( hash_elem ) );
  43
  44     new_elem->next = NULL;
  45     new_elem->key  = NULL;
  46     new_elem->val  = NULL;
  47
  48     return new_elem;
  49 }
  50
  51
  52 void hash_add( hash *hash_pt, char *key, void *val )
  53 {
  54     /* Martin A. Hansen, June 2008 */
  55
  56     /* Add a new hash element consisting of a key/value pair to an existing hash. */
  57
  58     hash_elem *old_elem   = NULL;
  59     hash_elem *new_elem   = NULL;
  60     size_t     hash_index = 0;
  61
  62     if ( ( old_elem = hash_elem_get( hash_pt, key ) ) != NULL )
  63     {
  64         old_elem->val = val;
  65     }
  66     else
  67     {
  68         new_elem = hash_elem_new();
  69
  70         hash_index = ( hash_key( key ) & hash_pt->mask );
  71
  72         new_elem->key  = mem_clone( key, strlen( key ) );
  73         new_elem->val  = val;
  74         new_elem->next = hash_pt->table[ hash_index ];
  75
  76         hash_pt->table[ hash_index ] = new_elem;
  77         hash_pt->nmemb++;
  78     }
  79 }
  80
  81
  82 void *hash_get( hash *hash_pt, char *key )
  83 {
  84     /* Martin A. Hansen, June 2008 */
  85
  86     /* Lookup a key in a given hash and return the value - or NULL if not found. */
  87
  88     hash_elem *bucket;
  89
  90     bucket = hash_pt->table[ ( hash_key( key ) & hash_pt->mask ) ];
  91
  92     while ( bucket != NULL )
  93     {
  94         if ( strcmp( bucket->key, key ) == 0 ) {
  95             return bucket->val;
  96         }
  97
  98         bucket = bucket->next;
  99     }
 100
 101     return NULL;
 102 }
 103
 104
 105 hash_elem *hash_elem_get( hash *hash_pt, char *key )
 106 {
 107     /* Martin A. Hansen, June 2008 */
 108
 109     /* Lookup a key in a given hash and return the hash element - or NULL if not found. */
 110
 111     hash_elem *bucket;
 112
 113     bucket = hash_pt->table[ ( hash_key( key ) & hash_pt->mask ) ];
 114
 115     while ( bucket != NULL )
 116     {
 117         if ( strcmp( bucket->key, key ) == 0 ) {
 118             return bucket;
 119         }
 120
 121         bucket = bucket->next;
 122     }
 123
 124     return NULL;
 125 }
 126
 127
 128 bool hash_each( hash *hash_pt, char **key_ppt, void *val )
 129 {
 130     /* Martin A. Hansen, December 2008. */
 131
 132     /* Get the next key/value pair from a hash table. */
 133
 134     char *key = *key_ppt;
 135
 136     printf( "\nhash_each INIT   -> i: %zu   he: %p\n", hash_pt->index_table, hash_pt->index_bucket );
 137
 138     if ( hash_pt->index_bucket != NULL )
 139     {
 140         key = hash_pt->index_bucket->key;
 141         val = hash_pt->index_bucket->val;
 142
 143         hash_pt->index_bucket = hash_pt->index_bucket->next;
 144
 145         *key_ppt = key;
 146
 147         printf( "\nhash_each BUCKET -> i: %zu   he: %p\n", hash_pt->index_table, hash_pt->index_bucket );
 148         return TRUE;
 149     }
 150
 151     while ( hash_pt->index_table < hash_pt->table_size )
 152     {
 153         hash_pt->index_bucket = hash_pt->table[ hash_pt->index_table ];
 154
 155         if ( hash_pt->index_bucket != NULL )
 156         {
 157             key = hash_pt->index_bucket->key;
 158             val = hash_pt->index_bucket->val;
 159
 160             hash_pt->index_bucket = hash_pt->index_bucket->next;
 161
 162             *key_ppt = key;
 163
 164             printf( "hash_each TABLE table[ %zu ]\n", hash_pt->index_table );
 165             return TRUE;
 166         }
 167
 168         hash_pt->index_table++;
 169     }
 170
 171     printf( "\nhash_each FALSE -> i: %zu   he: %p\n", hash_pt->index_table, hash_pt->index_bucket );
 172
 173     // RESET ITERATORS!
 174
 175     return FALSE;
 176 }
 177
 178
 179 void hash_destroy( hash *hash_pt )
 180 {
 181     /* Martin A. Hansen, June 2008 */
 182
 183     /* Deallocate memory for hash and all hash elements. */
 184
 185     size_t     i;
 186     hash_elem *bucket;
 187
 188     for ( i = 0; i < hash_pt->table_size; i++ )
 189     {
 190         for ( bucket = hash_pt->table[ i ]; bucket != NULL; bucket = bucket->next )
 191         {
 192 //            mem_free( bucket->key );
 193 //            mem_free( bucket->val );
 194             mem_free( bucket );
 195         }
 196     }
 197
 198     mem_free( hash_pt->table );
 199     mem_free( hash_pt );
 200 }
 201
 202
 203 uint hash_key( char *string )
 204 {
 205     /* Martin A. Hansen, June 2008 */
 206
 207     /* Hash function that generates a hash key, */
 208     /* based on the Jim Kent's stuff. */
 209
 210     char *key    = string;
 211     uint  result = 0;
 212     int   c;
 213
 214     while ( ( c = *key++ ) != '\0' ) {
 215         result += ( result << 3 ) + c;
 216     }
 217
 218     return result;
 219 }
 220
 221
 222 void hash_print( hash *hash_pt )
 223 {
 224     /* Martin A. Hansen, November 2008. */
 225
 226     /* Debug function that prints hash meta data and
 227      * all hash elements. */
 228
 229     hash_elem *bucket = NULL;
 230     size_t     i      = 0;
 231
 232     printf( "table_size: %zu mask: %zu elem_count: %zu\n", hash_pt->table_size, hash_pt->mask, hash_pt->nmemb );
 233
 234     for ( i = 0; i < hash_pt->table_size; i++ )
 235     {
 236         bucket = hash_pt->table[ i ];
 237
 238         while ( bucket != NULL  )
 239         {
 240             printf( "i: %zu   key: %s   val: %s\n", i, bucket->key, ( char * ) bucket->val );
 241
 242             bucket = bucket->next;
 243         }
 244     }
 245 }
 246
 247
 248 void hash_collision_stats( hash *hash_pt )
 249 {
 250     /* Martin A. Hansen, June 2008 */
 251
 252     /* Output some collision stats for a given hash. */
 253
 254     /* Use with Biopieces: ... | plot_histogram -k Col -x */
 255
 256     size_t     i      = 0;
 257     size_t     col    = 0;
 258     hash_elem *bucket = NULL;
 259
 260     for ( i = 0; i < hash_pt->table_size; i++ )
 261     {
 262         col = 0;
 263
 264         for ( bucket = hash_pt->table[ i ]; bucket != NULL; bucket = bucket->next ) {
 265             col++;
 266         }
 267
 268         printf( "Col: %zu\n---\n", col );
 269     }
 270 }