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