7 struct hash *hash_new( size_t size )
9 /* Martin A. Hansen, June 2008 */
11 /* Initialize a new generic hash structure. */
13 struct hash *new_hash;
18 table_size = 1 << size; /* table_size = ( 2 ** size ) */
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 );
24 new_hash->elem_count = 0;
30 void hash_add( struct hash *myhash, char *key, void *val )
32 /* Martin A. Hansen, June 2008 */
34 /* Add a new hash element consisting of a key/value pair to an existing hash. */
36 struct hash_elem *old_elem;
37 struct hash_elem *new_elem;
40 if ( ( old_elem = hash_get_elem( myhash, key ) ) != NULL )
48 hash_index = ( hash_key( key ) & myhash->mask );
50 new_elem->key = mem_clone( key, strlen( key ) );
52 new_elem->next = myhash->table[ hash_index ];
54 myhash->table[ hash_index ] = new_elem;
60 void *hash_get( struct hash *myhash, char *key )
62 /* Martin A. Hansen, June 2008 */
64 /* Lookup a key in a given hash and return the value - or NULL if not found. */
66 struct hash_elem *bucket;
68 bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
70 while ( bucket != NULL )
72 if ( strcmp( bucket->key, key ) == 0 ) {
76 bucket = bucket->next;
83 struct hash_elem *hash_get_elem( struct hash *myhash, char *key )
85 /* Martin A. Hansen, June 2008 */
87 /* Lookup a key in a given hash and return the hash element - or NULL if not found. */
89 struct hash_elem *bucket;
91 bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
93 while ( bucket != NULL )
95 if ( strcmp( bucket->key, key ) == 0 ) {
99 bucket = bucket->next;
106 bool hash_del( struct hash *myhash, char *key )
108 /* Martin A. Hansen, June 2008 */
110 /* Remove key/value pair from a given hash. */
111 /* Returns true if a remove was successful. */
113 struct hash_elem *bucket;
115 bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
117 while ( bucket != NULL )
119 if ( strcmp( bucket->key, key ) == 0 )
121 myhash->elem_count--;
125 bucket = bucket->next;
132 void hash_destroy( struct hash *myhash )
134 /* Martin A. Hansen, June 2008 */
136 /* Deallocate memory for hash and all hash elements. */
139 struct hash_elem *bucket;
141 for ( i = 0; i < myhash->table_size; i++ )
143 for ( bucket = myhash->table[ i ]; bucket != NULL; bucket = bucket->next )
145 mem_free( bucket->key );
146 // mem_free( bucket->val );
151 mem_free( myhash->table );
156 uint hash_key( char *string )
158 /* Martin A. Hansen, June 2008 */
160 /* Hash function that generates a hash key, */
161 /* based on the Jim Kent's stuff. */
167 while ( ( c = *key++ ) != '\0' ) {
168 result += ( result << 3 ) + c;
175 void hash_collision_stats( struct hash *myhash )
177 /* Martin A. Hansen, June 2008 */
179 /* Output some collision stats for a given hash. */
181 /* Use with biotools: ... | plot_histogram -k Col -x */
185 struct hash_elem *bucket;
187 for ( i = 0; i < myhash->table_size; i++ )
191 for ( bucket = myhash->table[ i ]; bucket != NULL; bucket = bucket->next ) {
195 printf( "Col: %d\n---\n", col );