src/tools/fs_shell/hash.cpp

   1 /* Generic hash table
   2 **
   3 ** Copyright 2001, Travis Geiselbrecht. All rights reserved.
   4 ** Distributed under the terms of the NewOS License.
   5 */
   6
   7 #include "hash.h"
   8
   9 #include <stdlib.h>
  10
  11 #include "fssh_errors.h"
  12 #include "fssh_kernel_export.h"
  13
  14
  15 #undef TRACE
  16 #define TRACE_HASH 0
  17 #if TRACE_HASH
  18 #       define TRACE(x) fssh_dprintf x
  19 #else
  20 #       define TRACE(x) ;
  21 #endif
  22
  23 #undef ASSERT
  24 #define ASSERT(x)
  25
  26
  27 namespace FSShell {
  28
  29
  30 // TODO: the hashtable is not expanded when necessary (no load factor, nothing)
  31 //              resizing should be optional, though, in case the hash is used at times
  32 //              that forbid resizing.
  33
  34 struct hash_table {
  35         struct          hash_element **table;
  36         int                     next_ptr_offset;
  37         uint32_t        table_size;
  38         int                     num_elements;
  39         int                     flags;
  40         int                     (*compare_func)(void *e, const void *key);
  41         uint32_t        (*hash_func)(void *e, const void *key, uint32_t range);
  42 };
  43
  44 // XXX gross hack
  45 #define NEXT_ADDR(t, e) ((void *)(((unsigned long)(e)) + (t)->next_ptr_offset))
  46 #define NEXT(t, e) ((void *)(*(unsigned long *)NEXT_ADDR(t, e)))
  47 #define PUT_IN_NEXT(t, e, val) (*(unsigned long *)NEXT_ADDR(t, e) = (long)(val))
  48
  49
  50 static inline void *
  51 next_element(hash_table *table, void *element)
  52 {
  53         // ToDo: should we use this instead of the NEXT() macro?
  54         return (void *)(*(unsigned long *)NEXT_ADDR(table, element));
  55 }
  56
  57
  58 struct hash_table *
  59 hash_init(uint32_t table_size, int next_ptr_offset,
  60         int compare_func(void *e, const void *key),
  61         uint32_t hash_func(void *e, const void *key, uint32_t range))
  62 {
  63         struct hash_table *t;
  64         unsigned int i;
  65
  66         if (compare_func == NULL || hash_func == NULL) {
  67                 fssh_dprintf("hash_init() called with NULL function pointer\n");
  68                 return NULL;
  69         }
  70
  71         t = (struct hash_table *)malloc(sizeof(struct hash_table));
  72         if (t == NULL)
  73                 return NULL;
  74
  75         t->table = (struct hash_element **)malloc(sizeof(void *) * table_size);
  76         if (t->table == NULL) {
  77                 free(t);
  78                 return NULL;
  79         }
  80
  81         for (i = 0; i < table_size; i++)
  82                 t->table[i] = NULL;
  83
  84         t->table_size = table_size;
  85         t->next_ptr_offset = next_ptr_offset;
  86         t->flags = 0;
  87         t->num_elements = 0;
  88         t->compare_func = compare_func;
  89         t->hash_func = hash_func;
  90
  91         TRACE(("hash_init: created table %p, next_ptr_offset %d, compare_func %p, hash_func %p\n",
  92                 t, next_ptr_offset, compare_func, hash_func));
  93
  94         return t;
  95 }
  96
  97
  98 int
  99 hash_uninit(struct hash_table *table)
 100 {
 101         ASSERT(table->num_elements == 0);
 102
 103         free(table->table);
 104         free(table);
 105
 106         return 0;
 107 }
 108
 109
 110 fssh_status_t
 111 hash_insert(struct hash_table *table, void *element)
 112 {
 113         uint32_t hash;
 114
 115         ASSERT(table != NULL && element != NULL);
 116         TRACE(("hash_insert: table 0x%x, element 0x%x\n", table, element));
 117
 118         hash = table->hash_func(element, NULL, table->table_size);
 119         PUT_IN_NEXT(table, element, table->table[hash]);
 120         table->table[hash] = (struct hash_element *)element;
 121         table->num_elements++;
 122
 123         // ToDo: resize hash table if it's grown too much!
 124
 125         return FSSH_B_OK;
 126 }
 127
 128
 129 fssh_status_t
 130 hash_remove(struct hash_table *table, void *_element)
 131 {
 132         uint32_t hash = table->hash_func(_element, NULL, table->table_size);
 133         void *element, *lastElement = NULL;
 134
 135         for (element = table->table[hash]; element != NULL;
 136                         lastElement = element, element = NEXT(table, element)) {
 137                 if (element == _element) {
 138                         if (lastElement != NULL) {
 139                                 // connect the previous entry with the next one
 140                                 PUT_IN_NEXT(table, lastElement, NEXT(table, element));
 141                         } else
 142                                 table->table[hash] = (struct hash_element *)NEXT(table, element);
 143                         table->num_elements--;
 144
 145                         return FSSH_B_OK;
 146                 }
 147         }
 148
 149         return FSSH_B_ERROR;
 150 }
 151
 152
 153 void
 154 hash_remove_current(struct hash_table *table, struct hash_iterator *iterator)
 155 {
 156         uint32_t index = iterator->bucket;
 157         void *element;
 158
 159         if (iterator->current == NULL)
 160                 fssh_panic("hash_remove_current() called too early.");
 161
 162         for (element = table->table[index]; index < table->table_size; index++) {
 163                 void *lastElement = NULL;
 164
 165                 while (element != NULL) {
 166                         if (element == iterator->current) {
 167                                 iterator->current = lastElement;
 168
 169                                 if (lastElement != NULL) {
 170                                         // connect the previous entry with the next one
 171                                         PUT_IN_NEXT(table, lastElement, NEXT(table, element));
 172                                 } else {
 173                                         table->table[index] = (struct hash_element *)NEXT(table,
 174                                                 element);
 175                                 }
 176
 177                                 table->num_elements--;
 178                                 return;
 179                         }
 180
 181                         element = NEXT(table, element);
 182                 }
 183         }
 184 }
 185
 186
 187 void *
 188 hash_remove_first(struct hash_table *table, uint32_t *_cookie)
 189 {
 190         uint32_t index;
 191
 192         for (index = _cookie ? *_cookie : 0; index < table->table_size; index++) {
 193                 void *element = table->table[index];
 194                 if (element != NULL) {
 195                         // remove the first element we find
 196                         table->table[index] = (struct hash_element *)NEXT(table, element);
 197                         table->num_elements--;
 198                         if (_cookie)
 199                                 *_cookie = index;
 200                         return element;
 201                 }
 202         }
 203
 204         return NULL;
 205 }
 206
 207
 208 void *
 209 hash_find(struct hash_table *table, void *searchedElement)
 210 {
 211         uint32_t hash = table->hash_func(searchedElement, NULL, table->table_size);
 212         void *element;
 213
 214         for (element = table->table[hash]; element != NULL; element = NEXT(table, element)) {
 215                 if (element == searchedElement)
 216                         return element;
 217         }
 218
 219         return NULL;
 220 }
 221
 222
 223 void *
 224 hash_lookup(struct hash_table *table, const void *key)
 225 {
 226         uint32_t hash = table->hash_func(NULL, key, table->table_size);
 227         void *element;
 228
 229         for (element = table->table[hash]; element != NULL; element = NEXT(table, element)) {
 230                 if (table->compare_func(element, key) == 0)
 231                         return element;
 232         }
 233
 234         return NULL;
 235 }
 236
 237
 238 struct hash_iterator *
 239 hash_open(struct hash_table *table, struct hash_iterator *iterator)
 240 {
 241         if (iterator == NULL) {
 242                 iterator = (struct hash_iterator *)malloc(sizeof(struct hash_iterator));
 243                 if (iterator == NULL)
 244                         return NULL;
 245         }
 246
 247         hash_rewind(table, iterator);
 248
 249         return iterator;
 250 }
 251
 252
 253 void
 254 hash_close(struct hash_table *table, struct hash_iterator *iterator, bool freeIterator)
 255 {
 256         if (freeIterator)
 257                 free(iterator);
 258 }
 259
 260
 261 void
 262 hash_rewind(struct hash_table *table, struct hash_iterator *iterator)
 263 {
 264         iterator->current = NULL;
 265         iterator->bucket = -1;
 266 }
 267
 268
 269 void *
 270 hash_next(struct hash_table *table, struct hash_iterator *iterator)
 271 {
 272         uint32_t index;
 273
 274 restart:
 275         if (iterator->current == NULL) {
 276                 // get next bucket
 277                 for (index = (uint32_t)(iterator->bucket + 1); index < table->table_size; index++) {
 278                         if (table->table[index]) {
 279                                 iterator->bucket = index;
 280                                 iterator->current = table->table[index];
 281                                 break;
 282                         }
 283                 }
 284         } else {
 285                 iterator->current = NEXT(table, iterator->current);
 286                 if (!iterator->current)
 287                         goto restart;
 288         }
 289
 290         return iterator->current;
 291 }
 292
 293
 294 uint32_t
 295 hash_hash_string(const char *string)
 296 {
 297         uint32_t hash = 0;
 298         char c;
 299
 300         // we assume hash to be at least 32 bits
 301         while ((c = *string++) != 0) {
 302                 hash ^= hash >> 28;
 303                 hash <<= 4;
 304                 hash ^= c;
 305         }
 306
 307         return hash;
 308 }
 309
 310 }       // namespace FSShell