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