code_c/Maasha/src/lib/hash.c

   1 #include "common.h"
   2 #include "mem.h"
   3 #include "hash.h"
   4 #include "list.h"
   5
   6
   7 struct hash *hash_new( size_t size )
   8 {
   9     /* Martin A. Hansen, June 2008 */
  10
  11     /* Initialize a new generic hash structure. */
  12
  13     struct hash *new_hash;
  14     int         table_size;
  15
  16     new_hash = mem_get( sizeof( new_hash ) );
  17
  18     table_size = 1 << size;   /* table_size = ( 2 ** size ) */
  19
  20     new_hash->table_size = table_size;
  21     new_hash->mask       = table_size - 1;
  22     new_hash->table      = mem_get( sizeof( struct hash_elem * ) * table_size );
  23
  24     new_hash->elem_count = 0;
  25
  26     return new_hash;
  27 }
  28
  29
  30 void hash_add( struct hash *myhash, char *key, void *val )
  31 {
  32     /* Martin A. Hansen, June 2008 */
  33
  34     /* Add a new hash element consisting of a key/value pair to an existing hash. */
  35
  36     struct hash_elem *old_elem;
  37     struct hash_elem *new_elem;
  38     int              hash_index;
  39
  40     if ( ( old_elem = hash_get_elem( myhash, key ) ) != NULL )
  41     {
  42         old_elem->val = val;
  43     }
  44     else
  45     {
  46         new_elem = mem_get( sizeof( new_elem ) );
  47
  48         hash_index = ( hash_key( key ) & myhash->mask );
  49
  50         new_elem->key  = mem_clone( key, strlen( key ) );
  51         new_elem->val  = val;
  52         new_elem->next = myhash->table[ hash_index ];
  53
  54         myhash->table[ hash_index ] = new_elem;
  55         myhash->elem_count++;
  56     }
  57 }
  58
  59
  60 void *hash_get( struct hash *myhash, char *key )
  61 {
  62     /* Martin A. Hansen, June 2008 */
  63
  64     /* Lookup a key in a given hash and return the value - or NULL if not found. */
  65
  66     struct hash_elem *bucket;
  67
  68     bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
  69
  70     while ( bucket != NULL )
  71     {
  72         if ( strcmp( bucket->key, key ) == 0 ) {
  73             return bucket->val;
  74         }
  75
  76         bucket = bucket->next;
  77     }
  78
  79     return NULL;
  80 }
  81
  82
  83 struct hash_elem *hash_get_elem( struct hash *myhash, char *key )
  84 {
  85     /* Martin A. Hansen, June 2008 */
  86
  87     /* Lookup a key in a given hash and return the hash element - or NULL if not found. */
  88
  89     struct hash_elem *bucket;
  90
  91     bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
  92
  93     while ( bucket != NULL )
  94     {
  95         if ( strcmp( bucket->key, key ) == 0 ) {
  96             return bucket;
  97         }
  98
  99         bucket = bucket->next;
 100     }
 101
 102     return NULL;
 103 }
 104
 105
 106 bool hash_del( struct hash *myhash, char *key )
 107 {
 108     /* Martin A. Hansen, June 2008 */
 109
 110     /* Remove key/value pair from a given hash. */
 111     /* Returns true if a remove was successful. */
 112
 113     struct hash_elem *bucket;
 114
 115     bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
 116
 117     while ( bucket != NULL )
 118     {
 119         if ( strcmp( bucket->key, key ) == 0 )
 120         {
 121             myhash->elem_count--;
 122             return TRUE;
 123         }
 124
 125         bucket = bucket->next;
 126     }
 127
 128     return FALSE;
 129 }
 130
 131
 132 void hash_destroy( struct hash *myhash )
 133 {
 134     /* Martin A. Hansen, June 2008 */
 135
 136     /* Deallocate memory for hash and all hash elements. */
 137
 138     int              i;
 139     struct hash_elem *bucket;
 140
 141     for ( i = 0; i < myhash->table_size; i++ )
 142     {
 143         for ( bucket = myhash->table[ i ]; bucket != NULL; bucket = bucket->next )
 144         {
 145             mem_free( ( void * ) &bucket->key );
 146 //            mem_free( bucket->val );
 147             mem_free( ( void * ) &bucket );
 148         }
 149     }
 150
 151     mem_free( ( void * ) &myhash->table );
 152     mem_free( ( void * ) &myhash );
 153 }
 154
 155
 156 uint hash_key( char *string )
 157 {
 158     /* Martin A. Hansen, June 2008 */
 159
 160     /* Hash function that generates a hash key, */
 161     /* based on the Jim Kent's stuff. */
 162
 163     char *key    = string;
 164     uint  result = 0;
 165     int   c;
 166
 167     while ( ( c = *key++ ) != '\0' ) {
 168         result += ( result << 3 ) + c;
 169     }
 170
 171     return result;
 172 }
 173
 174
 175 void hash_collision_stats( struct hash *myhash )
 176 {
 177     /* Martin A. Hansen, June 2008 */
 178
 179     /* Output some collision stats for a given hash. */
 180
 181     /* Use with biotools: ... | plot_histogram -k Col -x */
 182
 183     int               i;
 184     int               col;
 185     struct hash_elem *bucket;
 186
 187     for ( i = 0; i < myhash->table_size; i++ )
 188     {
 189         col = 0;
 190
 191         for ( bucket = myhash->table[ i ]; bucket != NULL; bucket = bucket->next ) {
 192             col++;
 193         }
 194
 195         printf( "Col: %d\n---\n", col );
 196     }
 197 }