+/* Martin Asser Hansen (mail@maasha.dk) Copyright (C) 2008 - All right reserved */
+
#include "common.h"
+#include "mem.h"
#include "hash.h"
#include "list.h"
-struct hash *hash_new( size_t size )
+hash *hash_new( size_t size )
{
/* Martin A. Hansen, June 2008 */
/* Initialize a new generic hash structure. */
- struct hash *new_hash;
- int table_size;
+ hash *new_hash = NULL;
+ size_t table_size = 0;
- MEM_GET( new_hash );
+ new_hash = mem_get( sizeof( new_hash ) );
table_size = 1 << size; /* table_size = ( 2 ** size ) */
new_hash->table_size = table_size;
new_hash->mask = table_size - 1;
- new_hash->table = mem_get( sizeof( struct hash_elem * ) * table_size );
-
- new_hash->elem_count = 0;
+ new_hash->table = mem_get( sizeof( hash_elem * ) * table_size );
+ new_hash->nmemb = 0;
return new_hash;
}
-void hash_add( struct hash *myhash, char *key, void *val )
+hash_elem *hash_elem_new()
+{
+ /* Martin A. Hansen, November 2008. */
+
+ /* Initializes a new hash_elem structure. */
+
+ hash_elem *new_elem = NULL;
+
+ new_elem = mem_get( sizeof( hash_elem ) );
+
+ new_elem->next = NULL;
+ new_elem->key = NULL;
+ new_elem->val = NULL;
+
+ return new_elem;
+}
+
+
+void hash_add( hash *hash_pt, char *key, void *val )
{
/* Martin A. Hansen, June 2008 */
/* Add a new hash element consisting of a key/value pair to an existing hash. */
- struct hash_elem *old_elem;
- struct hash_elem *new_elem;
- int hash_index;
+ hash_elem *old_elem = NULL;
+ hash_elem *new_elem = NULL;
+ size_t hash_index = 0;
- if ( ( old_elem = hash_get_elem( myhash, key ) ) != NULL )
+ if ( ( old_elem = hash_elem_get( hash_pt, key ) ) != NULL )
{
old_elem->val = val;
}
else
{
- MEM_GET( new_elem );
+ new_elem = hash_elem_new();
- hash_index = ( hash_key( key ) & myhash->mask );
+ hash_index = ( hash_key( key ) & hash_pt->mask );
new_elem->key = mem_clone( key, strlen( key ) );
new_elem->val = val;
- new_elem->next = myhash->table[ hash_index ];
+ new_elem->next = hash_pt->table[ hash_index ];
- myhash->table[ hash_index ] = new_elem;
- myhash->elem_count++;
+ hash_pt->table[ hash_index ] = new_elem;
+ hash_pt->nmemb++;
}
}
-void *hash_get( struct hash *myhash, char *key )
+void *hash_get( hash *hash_pt, char *key )
{
/* Martin A. Hansen, June 2008 */
/* Lookup a key in a given hash and return the value - or NULL if not found. */
- struct hash_elem *bucket;
+ hash_elem *bucket;
- bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
+ bucket = hash_pt->table[ ( hash_key( key ) & hash_pt->mask ) ];
while ( bucket != NULL )
{
}
-struct hash_elem *hash_get_elem( struct hash *myhash, char *key )
+hash_elem *hash_elem_get( hash *hash_pt, char *key )
{
/* Martin A. Hansen, June 2008 */
/* Lookup a key in a given hash and return the hash element - or NULL if not found. */
- struct hash_elem *bucket;
+ hash_elem *bucket;
- bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
+ bucket = hash_pt->table[ ( hash_key( key ) & hash_pt->mask ) ];
while ( bucket != NULL )
{
}
-bool hash_del( struct hash *myhash, char *key )
-{
- /* Martin A. Hansen, June 2008 */
-
- /* Remove key/value pair from a given hash. */
- /* Returns true if a remove was successful. */
-
- struct hash_elem *bucket;
-
- bucket = myhash->table[ ( hash_key( key ) & myhash->mask ) ];
-
- while ( bucket != NULL )
- {
- if ( strcmp( bucket->key, key ) == 0 )
- {
- myhash->elem_count--;
- return TRUE;
- }
-
- bucket = bucket->next;
- }
-
- return FALSE;
-}
-
-
-void hash_destroy( struct hash *myhash )
+void hash_destroy( hash *hash_pt )
{
/* Martin A. Hansen, June 2008 */
/* Deallocate memory for hash and all hash elements. */
- int i;
- struct hash_elem *bucket;
+ size_t i;
+ hash_elem *bucket;
- for ( i = 0; i < myhash->table_size; i++ )
+ for ( i = 0; i < hash_pt->table_size; i++ )
{
- for ( bucket = myhash->table[ i ]; bucket != NULL; bucket = bucket->next )
+ for ( bucket = hash_pt->table[ i ]; bucket != NULL; bucket = bucket->next )
{
- mem_free( bucket->key );
+// mem_free( bucket->key );
// mem_free( bucket->val );
mem_free( bucket );
}
}
- mem_free( myhash->table );
- mem_free( myhash );
+ mem_free( hash_pt->table );
+ mem_free( hash_pt );
}
}
-void hash_collision_stats( struct hash *myhash )
+void hash_print( hash *hash_pt )
+{
+ /* Martin A. Hansen, November 2008. */
+
+ /* Debug function that prints hash meta data and
+ * all hash elements. */
+
+ hash_elem *bucket = NULL;
+ size_t i = 0;
+
+ printf( "table_size: %zu mask: %zu elem_count: %zu\n", hash_pt->table_size, hash_pt->mask, hash_pt->nmemb );
+
+ for ( i = 0; i < hash_pt->table_size; i++ )
+ {
+ bucket = hash_pt->table[ i ];
+
+ while ( bucket != NULL )
+ {
+ printf( "i: %zu key: %s val: %s\n", i, bucket->key, ( char * ) bucket->val );
+
+ bucket = bucket->next;
+ }
+ }
+}
+
+
+void hash_collision_stats( hash *hash_pt )
{
/* Martin A. Hansen, June 2008 */
/* Output some collision stats for a given hash. */
- /* Use with biotools: ... | plot_histogram -k Col -x */
+ /* Use with Biopieces: ... | plot_histogram -k Col -x */
- int i;
- int col;
- struct hash_elem *bucket;
+ size_t i = 0;
+ size_t col = 0;
+ hash_elem *bucket = NULL;
- for ( i = 0; i < myhash->table_size; i++ )
+ for ( i = 0; i < hash_pt->table_size; i++ )
{
col = 0;
- for ( bucket = myhash->table[ i ]; bucket != NULL; bucket = bucket->next ) {
+ for ( bucket = hash_pt->table[ i ]; bucket != NULL; bucket = bucket->next ) {
col++;
}
- printf( "Col: %d\n---\n", col );
+ printf( "Col: %zu\n---\n", col );
}
}