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 311