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
  27     return new_hash;
  28 }
  29
  30
  31 hash_elem *hash_elem_new()
  32 {
  33     /* Martin A. Hansen, November 2008. */
  34
  35     /* Initializes a new hash_elem structure. */
  36
  37     hash_elem *new_elem = NULL;
  38
  39     new_elem = mem_get( sizeof( hash_elem ) );
  40
  41     new_elem->next = NULL;
  42     new_elem->key  = NULL;
  43     new_elem->val  = NULL;
  44
  45     return new_elem;
  46 }
  47
  48
  49 void hash_add( hash *hash_pt, char *key, void *val )
  50 {
  51     /* Martin A. Hansen, June 2008 */
  52
  53     /* Add a new hash element consisting of a key/value pair to an existing hash. */
  54
  55     hash_elem *old_elem   = NULL;
  56     hash_elem *new_elem   = NULL;
  57     size_t     hash_index = 0;
  58
  59     if ( ( old_elem = hash_elem_get( hash_pt, key ) ) != NULL )
  60     {
  61         old_elem->val = val;
  62     }
  63     else
  64     {
  65         new_elem = hash_elem_new();
  66
  67         hash_index = ( hash_key( key ) & hash_pt->mask );
  68
  69         new_elem->key  = mem_clone( key, strlen( key ) );
  70         new_elem->val  = val;
  71         new_elem->next = hash_pt->table[ hash_index ];
  72
  73         hash_pt->table[ hash_index ] = new_elem;
  74         hash_pt->nmemb++;
  75     }
  76 }
  77
  78
  79 void *hash_get( hash *hash_pt, char *key )
  80 {
  81     /* Martin A. Hansen, June 2008 */
  82
  83     /* Lookup a key in a given hash and return the value - or NULL if not found. */
  84
  85     hash_elem *bucket;
  86
  87     bucket = hash_pt->table[ ( hash_key( key ) & hash_pt->mask ) ];
  88
  89     while ( bucket != NULL )
  90     {
  91         if ( strcmp( bucket->key, key ) == 0 ) {
  92             return bucket->val;
  93         }
  94
  95         bucket = bucket->next;
  96     }
  97
  98     return NULL;
  99 }
 100
 101
 102 hash_elem *hash_elem_get( hash *hash_pt, char *key )
 103 {
 104     /* Martin A. Hansen, June 2008 */
 105
 106     /* Lookup a key in a given hash and return the hash element - or NULL if not found. */
 107
 108     hash_elem *bucket;
 109
 110     bucket = hash_pt->table[ ( hash_key( key ) & hash_pt->mask ) ];
 111
 112     while ( bucket != NULL )
 113     {
 114         if ( strcmp( bucket->key, key ) == 0 ) {
 115             return bucket;
 116         }
 117
 118         bucket = bucket->next;
 119     }
 120
 121     return NULL;
 122 }
 123
 124
 125 void hash_destroy( hash *hash_pt )
 126 {
 127     /* Martin A. Hansen, June 2008 */
 128
 129     /* Deallocate memory for hash and all hash elements. */
 130
 131     size_t     i;
 132     hash_elem *bucket;
 133
 134     for ( i = 0; i < hash_pt->table_size; i++ )
 135     {
 136         for ( bucket = hash_pt->table[ i ]; bucket != NULL; bucket = bucket->next )
 137         {
 138 //            mem_free( bucket->key );
 139 //            mem_free( bucket->val );
 140             mem_free( bucket );
 141         }
 142     }
 143
 144     mem_free( hash_pt->table );
 145     mem_free( hash_pt );
 146 }
 147
 148
 149 uint hash_key( char *string )
 150 {
 151     /* Martin A. Hansen, June 2008 */
 152
 153     /* Hash function that generates a hash key, */
 154     /* based on the Jim Kent's stuff. */
 155
 156     char *key    = string;
 157     uint  result = 0;
 158     int   c;
 159
 160     while ( ( c = *key++ ) != '\0' ) {
 161         result += ( result << 3 ) + c;
 162     }
 163
 164     return result;
 165 }
 166
 167
 168 void hash_print( hash *hash_pt )
 169 {
 170     /* Martin A. Hansen, November 2008. */
 171
 172     /* Debug function that prints hash meta data and
 173      * all hash elements. */
 174
 175     hash_elem *bucket = NULL;
 176     size_t     i      = 0;
 177
 178     printf( "table_size: %zu mask: %zu elem_count: %zu\n", hash_pt->table_size, hash_pt->mask, hash_pt->nmemb );
 179
 180     for ( i = 0; i < hash_pt->table_size; i++ )
 181     {
 182         bucket = hash_pt->table[ i ];
 183
 184         while ( bucket != NULL  )
 185         {
 186             printf( "i: %zu   key: %s   val: %s\n", i, bucket->key, ( char * ) bucket->val );
 187
 188             bucket = bucket->next;
 189         }
 190     }
 191 }
 192
 193
 194 void hash_collision_stats( hash *hash_pt )
 195 {
 196     /* Martin A. Hansen, June 2008 */
 197
 198     /* Output some collision stats for a given hash. */
 199
 200     /* Use with Biopieces: ... | plot_histogram -k Col -x */
 201
 202     size_t     i      = 0;
 203     size_t     col    = 0;
 204     hash_elem *bucket = NULL;
 205
 206     for ( i = 0; i < hash_pt->table_size; i++ )
 207     {
 208         col = 0;
 209
 210         for ( bucket = hash_pt->table[ i ]; bucket != NULL; bucket = bucket->next ) {
 211             col++;
 212         }
 213
 214         printf( "Col: %zu\n---\n", col );
 215     }
 216 }