vcs.maemo.org Git - monky/blob - src/hash.c

   1 /* ------------------------------------------------------
   2  * Open-addressed hash using double hash probing
   3  *
   4  * for i in 0 to m-1:
   5  *      h(k, i) = ( h1(k) + i*h2(k) ) mod m
   6  *
   7  * requires: 1) m must be a power of two
   8  *           2) h2(k) must return an odd number
   9  *
  10  * Besed on code published in _Mastering Algorithms in C_
  11  * by Kyle Loudon (O'Reilly 1999).
  12  * Modified by Philip Kovacs (kovacsp3@comcast.net)
  13  *
  14  * $Id$
  15  * ------------------------------------------------------ */
  16
  17 #ifdef HASH_DEBUG
  18 #include <stdio.h>
  19 #endif
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "hash.h"
  23
  24 /* Create and initialize a hash table on the heap.
  25    Returns 0 on success, -1 otherwise. */
  26 int hash_create( hash_table_t *p_hash_table,
  27                  int positions,
  28                  int (*p_hash_fun1)(const void *p_data),
  29                  int (*p_hash_fun2)(const void *p_data),
  30                  int (*p_match_fun)(const void *p_data1, const void *p_data2),
  31                  void (*p_destroy_fun)(void *p_data)
  32         )
  33 {
  34     if ( ( p_hash_table->pp_table = (void **)calloc(positions,  sizeof(void *))) == NULL )
  35         return -1;
  36
  37     p_hash_table->positions = positions;
  38     p_hash_table->size = 0;
  39     p_hash_table->vacated = 0;
  40
  41     /* sentinel address indicating a vacated slot */
  42     p_hash_table->p_vacated = &p_hash_table->sentinel_vacated;
  43
  44     p_hash_table->p_hash_fun1 = p_hash_fun1;
  45     p_hash_table->p_hash_fun2 = p_hash_fun2;
  46
  47     p_hash_table->p_match_fun = p_match_fun;
  48     p_hash_table->p_destroy_fun = p_destroy_fun;
  49
  50     return 0;
  51 }
  52
  53
  54 /* Destroy a hash table */
  55 void hash_destroy( hash_table_t *p_hash_table )
  56 {
  57    int  i;
  58
  59    if ( !p_hash_table )
  60         return;
  61
  62    /* Destroy the elements the hash points to, if a destroy function was provided */
  63    if (p_hash_table->p_destroy_fun != NULL) {
  64
  65         for (i = 0; i < p_hash_table->positions; i++) {
  66
  67                 if ( p_hash_table->pp_table[i] != NULL && p_hash_table->pp_table[i] != p_hash_table->p_vacated )
  68                    p_hash_table->p_destroy_fun( p_hash_table->pp_table[i] );
  69         }
  70    }
  71
  72    free( p_hash_table->pp_table );
  73    memset( p_hash_table, 0, sizeof(hash_table_t) );
  74
  75    return;
  76 }
  77
  78 /* Insert an element into a hash table.
  79    Returns 0 on successful insert, 1 if data already in hash and -1 if unable to insert. */
  80 int hash_insert( hash_table_t *p_hash_table, const void *p_data )
  81 {
  82    void *temp;
  83    int position, i;
  84    int hashed_1, hashed_2;
  85
  86    if ( !p_hash_table )
  87         return -1;
  88
  89    if ( p_hash_table->size == p_hash_table->positions )
  90         return -1;
  91
  92    temp = (void *)p_data;
  93
  94    if ( hash_lookup( p_hash_table, &temp ) == 0 )
  95         return 1;
  96
  97    /* Loudon's original algorithm needlessly repeated running the hash algorithms with each iteration
  98       to find a slot.   Just running the hash algorithms once is enough since they are deterministic. */
  99    hashed_1 = p_hash_table->p_hash_fun1( p_data );
 100    hashed_2 = p_hash_table->p_hash_fun2( p_data );
 101
 102    for ( i = 0; i < p_hash_table->positions; i++ ) {
 103
 104         position = ( hashed_1 + (i * hashed_2) ) % p_hash_table->positions;
 105 #ifdef HASH_DEBUG
 106         printf("--- hash_insert: probe %d, position %d\n",i,position);
 107 #endif
 108
 109         if ( p_hash_table->pp_table[ position ] == NULL ) /* empty slot */
 110         {
 111                 p_hash_table->pp_table[ position ] = (void *)p_data;
 112                 p_hash_table->size++;
 113                 return 0;
 114         }
 115
 116         if ( p_hash_table->pp_table[ position ] == p_hash_table->p_vacated ) /* vacated slot */
 117         {
 118                 p_hash_table->pp_table[ position ] = (void *)p_data;
 119                 p_hash_table->size++;
 120                 p_hash_table->vacated--;
 121                 return 0;
 122         }
 123    }
 124
 125    /* hash functions not selected correctly since the above algorithm should visit all slots in the hash. */
 126    return -1;
 127 }
 128
 129 /* Delete an element from a hash table.
 130    Returns 0 on successful delete, -1 if not found. */
 131 int hash_remove( hash_table_t *p_hash_table, void **pp_data)
 132 {
 133    int position, i;
 134    int hashed_1, hashed_2;
 135
 136    if ( !p_hash_table || !pp_data )
 137         return -1;
 138
 139    hashed_1 = p_hash_table->p_hash_fun1( *pp_data );
 140    hashed_2 = p_hash_table->p_hash_fun2( *pp_data );
 141
 142    for (i = 0; i < p_hash_table->positions; i++) {
 143
 144         position= ( hashed_1 + (i * hashed_2) ) % p_hash_table->positions;
 145 #ifdef HASH_DEBUG
 146         printf("--- hash_remove: probe %d, position %d\n",i,position);
 147 #endif
 148
 149         if ( p_hash_table->pp_table[ position ] == NULL ) {
 150
 151                 return -1;
 152
 153         }
 154
 155         else if ( p_hash_table->pp_table[ position ] == p_hash_table->p_vacated ) {
 156
 157                 continue;
 158
 159         }
 160
 161         else if ( p_hash_table->p_match_fun( p_hash_table->pp_table[ position ], *pp_data)) {
 162
 163                 *pp_data = p_hash_table->pp_table[ position ];
 164                 p_hash_table->pp_table[ position ] = p_hash_table->p_vacated;
 165                 p_hash_table->vacated++;
 166                 p_hash_table->size--;
 167                 return 0;
 168         }
 169    }
 170
 171    return -1;
 172 }
 173
 174 /* Lookup an element in a hash table.
 175    Returns 0 if found (data passed back byref), -1 if not found. */
 176 int hash_lookup(const hash_table_t *p_hash_table, void **pp_data)
 177 {
 178    int position, i;
 179    int hashed_1, hashed_2;
 180
 181    if ( !p_hash_table || !pp_data )
 182         return -1;
 183
 184    hashed_1 = p_hash_table->p_hash_fun1( *pp_data );
 185    hashed_2 = p_hash_table->p_hash_fun2( *pp_data );
 186
 187    for (i = 0; i < p_hash_table->positions; i++) {
 188
 189         position= ( hashed_1 + (i * hashed_2) ) % p_hash_table->positions;
 190 #ifdef HASH_DEBUG
 191         printf("--- hash_lookup: probe %d, position %d\n",i,position);
 192 #endif
 193         if ( p_hash_table->pp_table[ position ] == NULL ) {
 194
 195                 return -1;
 196
 197         }
 198
 199         else if ( p_hash_table->p_match_fun(p_hash_table->pp_table[ position ], *pp_data) ) {
 200
 201                 *pp_data = p_hash_table->pp_table[ position ];
 202                 return 0;
 203
 204         }
 205    }
 206
 207    return -1;
 208 }