interpreters/nitfol/hash.c

   1 #include "nitfol.h"
   2
   3
   4 /* Modified and bugfixed for nitfol by Evin Robertson Sept 10, 1999 */
   5
   6
   7 /*
   8 ** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
   9 **
  10 ** Tested with Visual C 1.0 and Borland C 3.1.
  11 ** Compiles without warnings, and seems like it should be pretty
  12 ** portable.
  13 */
  14
  15
  16 #ifdef HEADER
  17 /*
  18 ** A hash table consists of an array of these buckets.  Each bucket
  19 ** holds a copy of the key, a pointer to the data associated with the
  20 ** key, and a pointer to the next bucket that collided with this one,
  21 ** if there was one.
  22 */
  23
  24 typedef struct bucket {
  25     char *key;
  26     void *data;
  27     struct bucket *next;
  28 } bucket;
  29
  30 /*
  31 ** This is what you actually declare an instance of to create a table.
  32 ** You then call 'construct_table' with the address of this structure,
  33 ** and a guess at the size of the table.  Note that more nodes than this
  34 ** can be inserted in the table, but performance degrades as this
  35 ** happens.  Performance should still be quite adequate until 2 or 3
  36 ** times as many nodes have been inserted as the table was created with.
  37 */
  38
  39 typedef struct hash_table {
  40     size_t size;
  41     bucket **table;
  42 } hash_table;
  43 #endif
  44
  45
  46 /*
  47 ** These are used in freeing a table.  Perhaps I should code up
  48 ** something a little less grungy, but it works, so what the heck.
  49 */
  50 typedef void (*my_function)(void *);
  51 static my_function function = NULL;
  52 static hash_table *the_table = NULL;
  53
  54 /* Initialize the hash_table to the size asked for.  Allocates space
  55 ** for the correct number of pointers and sets them to NULL.  If it
  56 ** can't allocate sufficient memory, signals error by setting the size
  57 ** of the table to 0.
  58 */
  59
  60 hash_table *n_hash_construct_table(hash_table *table, size_t size)
  61 {
  62       size_t i;
  63       bucket **temp;
  64
  65       table -> size  = size;
  66       table -> table = (bucket * *)n_malloc(sizeof(bucket *) * size);
  67       temp = table -> table;
  68
  69       if ( temp == NULL )
  70       {
  71             table -> size = 0;
  72             return table;
  73       }
  74
  75       for (i=0;i<size;i++)
  76             temp[i] = NULL;
  77       return table;
  78 }
  79
  80
  81 /*
  82 ** Hashes a string to produce an unsigned short, which should be
  83 ** sufficient for most purposes.
  84 */
  85
  86 static unsigned hash(const char *string)
  87 {
  88       unsigned ret_val = 0;
  89       int i;
  90
  91       while (*string)
  92       {
  93             /* Modified by ecr to fix bug and improve method slightly */
  94             ret_val <<= 1;
  95             i = string[0] + (string[1] << 8);
  96             ret_val ^= i;
  97             string ++;
  98       }
  99       return ret_val;
 100 }
 101
 102 /*
 103 ** Insert 'key' into hash table.
 104 ** Returns pointer to old data associated with the key, if any, or
 105 ** NULL if the key wasn't in the table previously.
 106 */
 107
 108 void *n_hash_insert(const char *key, void *data, hash_table *table)
 109 {
 110       unsigned val = hash(key) % table->size;
 111       bucket *ptr;
 112
 113       /*
 114       ** NULL means this bucket hasn't been used yet.  We'll simply
 115       ** allocate space for our new bucket and put our data there, with
 116       ** the table pointing at it.
 117       */
 118
 119       if (NULL == (table->table)[val])
 120       {
 121             (table->table)[val] = (bucket *)n_malloc(sizeof(bucket));
 122             if (NULL==(table->table)[val])
 123                   return NULL;
 124
 125             (table->table)[val] -> key = n_strdup(key);
 126             (table->table)[val] -> next = NULL;
 127             (table->table)[val] -> data = data;
 128             return (table->table)[val] -> data;
 129       }
 130
 131       /*
 132       ** This spot in the table is already in use.  See if the current string
 133       ** has already been inserted, and if so, increment its count.
 134       */
 135
 136       for (ptr = (table->table)[val];NULL != ptr; ptr = ptr -> next)
 137             if (0 == n_strcmp(key, ptr->key))
 138             {
 139                   void *old_data;
 140
 141                   old_data = ptr->data;
 142                   ptr -> data = data;
 143                   return old_data;
 144             }
 145
 146       /*
 147       ** This key must not be in the table yet.  We'll add it to the head of
 148       ** the list at this spot in the hash table.  Speed would be
 149       ** slightly improved if the list was kept sorted instead.  In this case,
 150       ** this code would be moved into the loop above, and the insertion would
 151       ** take place as soon as it was determined that the present key in the
 152       ** list was larger than this one.
 153       */
 154
 155       ptr = (bucket *)n_malloc(sizeof(bucket));
 156       if (NULL==ptr)
 157             return 0;
 158       ptr -> key = n_strdup(key);
 159       ptr -> data = data;
 160       ptr -> next = (table->table)[val];
 161       (table->table)[val] = ptr;
 162       return data;
 163 }
 164
 165
 166 /*
 167 ** Look up a key and return the associated data.  Returns NULL if
 168 ** the key is not in the table.
 169 */
 170
 171 void *n_hash_lookup(const char *key, hash_table *table)
 172 {
 173       unsigned val = hash(key) % table->size;
 174       bucket *ptr;
 175
 176       if (NULL == (table->table)[val])
 177             return NULL;
 178
 179       for ( ptr = (table->table)[val];NULL != ptr; ptr = ptr->next )
 180       {
 181             if (0 == n_strcmp(key, ptr -> key ) )
 182                   return ptr->data;
 183       }
 184       return NULL;
 185 }
 186
 187 /*
 188 ** Delete a key from the hash table and return associated
 189 ** data, or NULL if not present.
 190 */
 191
 192 void *n_hash_del(const char *key, hash_table *table)
 193 {
 194       unsigned val = hash(key) % table->size;
 195       void *data;
 196       bucket *ptr, *last = NULL;
 197
 198       if (NULL == (table->table)[val])
 199             return NULL;
 200
 201       /*
 202       ** Traverse the list, keeping track of the previous node in the list.
 203       ** When we find the node to delete, we set the previous node's next
 204       ** pointer to point to the node after ourself instead.  We then delete
 205       ** the key from the present node, and return a pointer to the data it
 206       ** contains.
 207       */
 208
 209       for (last = NULL, ptr = (table->table)[val];
 210             NULL != ptr;
 211             last = ptr, ptr = ptr->next)
 212       {
 213             if (0 == n_strcmp(key, ptr -> key))
 214             {
 215                   if (last != NULL )
 216                   {
 217                         data = ptr -> data;
 218                         last -> next = ptr -> next;
 219                         n_free(ptr->key);
 220                         n_free(ptr);
 221                         return data;
 222                   }
 223
 224                   /*
 225                   ** If 'last' still equals NULL, it means that we need to
 226                   ** delete the first node in the list. This simply consists
 227                   ** of putting our own 'next' pointer in the array holding
 228                   ** the head of the list.  We then dispose of the current
 229                   ** node as above.
 230                   */
 231
 232                   else
 233                   {
 234                         data = ptr->data;
 235                         (table->table)[val] = ptr->next;
 236                         n_free(ptr->key);
 237                         n_free(ptr);
 238                         return data;
 239                   }
 240             }
 241       }
 242
 243       /*
 244       ** If we get here, it means we didn't find the item in the table.
 245       ** Signal this by returning NULL.
 246       */
 247
 248       return NULL;
 249 }
 250
 251 /*
 252 ** free_table iterates the table, calling this repeatedly to free
 253 ** each individual node.  This, in turn, calls one or two other
 254 ** functions - one to free the storage used for the key, the other
 255 ** passes a pointer to the data back to a function defined by the user,
 256 ** process the data as needed.
 257 */
 258
 259 static void free_node(const char *key, void *data)
 260 {
 261       (void) data;
 262
 263       if (function)
 264             function(n_hash_del(key,the_table));
 265       else  n_hash_del(key,the_table);
 266 }
 267
 268 /*
 269 ** Frees a complete table by iterating over it and freeing each node.
 270 ** the second parameter is the address of a function it will call with a
 271 ** pointer to the data associated with each node.  This function is
 272 ** responsible for freeing the data, or doing whatever is needed with
 273 ** it.
 274 */
 275
 276 void n_hash_free_table(hash_table *table, void (*func)(void *))
 277 {
 278       function = func;
 279       the_table = table;
 280
 281       n_hash_enumerate( table, free_node);
 282       n_free(table->table);
 283       table->table = NULL;
 284       table->size = 0;
 285
 286       the_table = NULL;
 287       function = (void (*)(void *))NULL;
 288 }
 289
 290 /*
 291 ** Simply invokes the function given as the second parameter for each
 292 ** node in the table, passing it the key and the associated data.
 293 */
 294
 295 void n_hash_enumerate( hash_table *table, void (*func)(const char *, void *))
 296 {
 297       unsigned i;
 298       bucket *temp, *next;
 299
 300       for (i=0; i < table->size; i++)
 301       {
 302             for (temp = (table->table)[i]; temp; temp=next)
 303             {
 304                    next = temp->next; /* ecr - temp may be deleted by func */
 305                    func(temp->key, temp->data);
 306             }
 307       }
 308 }