1/** 2 * \file 3 * \brief Barrelfish collections library hash table 4 */ 5/* 6 * Copyright (c) 2010, ETH Zurich. 7 * All rights reserved. 8 * 9 * This file is distributed under the terms in the attached LICENSE file. 10 * If you do not find this file, copies can be found by writing to: 11 * ETH Zurich D-INFK, Universitaetstrasse 6, CH-8092 Zurich. Attn: Systems Group. 12 */ 13 14#include "collections/hash_table.h" 15#include "inttypes.h" 16 17/****************************************************** 18 * a simple hash table implementation 19 ******************************************************/ 20 21/* 22 * Function to identify the right element from the 23 * linked list. 24 */ 25static int32_t match_key(void *data, void *arg) 26{ 27 collections_hash_elem *elem = (collections_hash_elem *) data; 28 uint64_t key = *((uint64_t *)arg); 29 30 return (elem->key == key); 31} 32 33/* 34 * Create a hash table. 35 */ 36static void collections_hash_create_core(collections_hash_table **t, int num_buckets, collections_hash_data_free data_free) 37{ 38 int i; 39 40 *t = (collections_hash_table *) malloc (sizeof(collections_hash_table)); 41 memset(*t, 0, sizeof(collections_hash_table)); 42 43 (*t)->num_buckets = num_buckets; 44 45 // create a linked list node for each bucket 46 (*t)->buckets = (collections_listnode **) malloc(sizeof(collections_listnode *) * num_buckets); 47 for (i = 0; i < num_buckets; i ++) { 48 collections_list_create(&(*t)->buckets[i], NULL); 49 } 50 51 (*t)->num_elems = 0; 52 (*t)->data_free = data_free; 53 54 // to keep track of traversing the hash table 55 (*t)->cur_bucket_num = -1; 56 return; 57} 58 59void collections_hash_create(collections_hash_table **t, collections_hash_data_free elem_free) 60{ 61 collections_hash_create_core(t, NUM_BUCKETS, elem_free); 62} 63 64void collections_hash_create_with_buckets(collections_hash_table **t, int num_buckets, collections_hash_data_free elem_free) 65{ 66 collections_hash_create_core(t, num_buckets, elem_free); 67} 68 69static int collections_hash_release_elem(void* elem, void * arg) 70{ 71 collections_hash_table *t = (collections_hash_table *)arg; 72 collections_hash_elem *he = (collections_hash_elem *)elem; 73 if (t->data_free) 74 { 75 t->data_free(he->data); 76 } 77 free(he); 78 79 t->num_elems--; 80 81 return 1; 82} 83 84// delete the entire hash table 85void collections_hash_release(collections_hash_table *t) 86{ 87 int bucket_num; 88 int bucket_size; 89 collections_listnode *bucket; 90 91 for (bucket_num = 0; bucket_num < t->num_buckets; bucket_num ++) { 92 uint32_t before, after; 93 bucket = t->buckets[bucket_num]; 94 bucket_size = collections_list_size(bucket); 95 96 before = t->num_elems; 97 collections_list_visit(bucket, collections_hash_release_elem, t); 98 after = t->num_elems; 99 assert(before - after == bucket_size); 100 101 collections_list_release(bucket); 102 } 103 assert(t->num_elems == 0); 104 105 free(t->buckets); 106 free(t); 107} 108 109static collections_hash_elem* collections_hash_find_elem(collections_hash_table *t, uint64_t key) 110{ 111 uint32_t bucket_num; 112 collections_listnode *bucket; 113 collections_hash_elem *elem; 114 115 bucket_num = key % t->num_buckets; 116 bucket = t->buckets[bucket_num]; 117 elem = (collections_hash_elem*) collections_list_find_if(bucket, match_key, &key); 118 return elem; 119} 120 121/* 122 * Inserts an element into the hash table. 123 */ 124void collections_hash_insert(collections_hash_table *t, uint64_t key, void *data) 125{ 126 uint32_t bucket_num; 127 collections_listnode *bucket; 128 collections_hash_elem *elem; 129 130 elem = collections_hash_find_elem(t, key); 131 if (elem != NULL) { 132 printf("Error: key %" PRIu64 " already present in hash table %" PRIu64 "\n", 133 key, elem->key); 134 assert(0); 135 return; 136 } 137 138 bucket_num = key % t->num_buckets; 139 bucket = t->buckets[bucket_num]; 140 elem = (collections_hash_elem *) malloc(sizeof(collections_hash_elem)); 141 elem->key = key; 142 elem->data = data; 143 collections_list_insert(bucket, (void *)elem); 144 t->num_elems ++; 145} 146 147/* 148 * Retrieves an element from the hash table. 149 */ 150void *collections_hash_find(collections_hash_table *t, uint64_t key) 151{ 152 collections_hash_elem *he = collections_hash_find_elem(t, key); 153 return (he) ? he->data : NULL; 154} 155 156/* 157 * Removes a specific element from the table. 158 */ 159void collections_hash_delete(collections_hash_table *t, uint64_t key) 160{ 161 uint32_t bucket_num; 162 collections_listnode *bucket; 163 collections_hash_elem *elem; 164 165 bucket_num = key % t->num_buckets; 166 bucket = t->buckets[bucket_num]; 167 elem = (collections_hash_elem*) collections_list_remove_if(bucket, match_key, &key); 168 if (elem) { 169 uint32_t n = t->num_elems; 170 collections_hash_release_elem(elem, t); 171 assert(1 == n - t->num_elems); 172 } 173 else 174 { 175 printf("Error: cannot find the node with key %" PRIu64 " in collections_hash_release\n", key); 176 } 177} 178 179/* 180 * Returns the number of elements in the hash table. 181 */ 182uint32_t collections_hash_size(collections_hash_table *t) 183{ 184 return (t->num_elems); 185} 186 187static collections_listnode* collections_hash_get_next_valid_bucket(collections_hash_table* t) 188{ 189 collections_listnode* bucket; 190 191 do { 192 t->cur_bucket_num ++; 193 if (t->cur_bucket_num < t->num_buckets) { 194 if (!t->buckets[t->cur_bucket_num]) { 195 continue; 196 } 197 } else { 198 return NULL; 199 } 200 } while (collections_list_size(t->buckets[t->cur_bucket_num]) <= 0); 201 202 bucket = t->buckets[t->cur_bucket_num]; 203 collections_list_traverse_start(bucket); 204 205 return bucket; 206} 207 208int32_t collections_hash_traverse_start(collections_hash_table *t) 209{ 210 if (t->cur_bucket_num != -1) { 211 // if the cur_bucket_num is valid, a 212 // traversal is already in progress. 213 printf("Error: collections_hash_table is already opened for traversal.\n"); 214 return -1; 215 } 216 217 collections_hash_get_next_valid_bucket(t); 218 219 return 1; 220} 221 222/* 223 * Returns the next element in the hash table. If 224 * a valid element is found, the key is set to the 225 * key of the element. If there is no valid element, 226 * returns null and key is not modified. 227 */ 228void* collections_hash_traverse_next(collections_hash_table* t, uint64_t *key) 229{ 230 if (t->cur_bucket_num == -1) { 231 // if the cur_bucket_num is invalid, 232 // hash traversal has not been started. 233 printf("Error: collections_hash_table must be opened for traversal first.\n"); 234 return NULL; 235 } 236 237 if (t->cur_bucket_num >= t->num_buckets) { 238 // all the buckets have been traversed. 239 return NULL; 240 } else { 241 collections_listnode* bucket; 242 collections_hash_elem* ret; 243 244 if (t->buckets[t->cur_bucket_num]) { 245 bucket = t->buckets[t->cur_bucket_num]; 246 ret = (collections_hash_elem*) collections_list_traverse_next(bucket); 247 248 if (ret) { 249 *key = ret->key; 250 return ret->data; 251 } else { 252 // this list traversal is over. 253 // let's close it. 254 collections_list_traverse_end(bucket); 255 } 256 } 257 258 bucket = collections_hash_get_next_valid_bucket(t); 259 if (!bucket) { 260 return NULL; 261 } else { 262 ret = (collections_hash_elem*) collections_list_traverse_next(bucket); 263 assert(ret != NULL); 264 } 265 266 *key = ret->key; 267 return ret->data; 268 } 269} 270 271int32_t collections_hash_traverse_end(collections_hash_table* t) 272{ 273 if (t->cur_bucket_num == -1) { 274 // if the cur_bucket_num is invalid, 275 // hash traversal has not been started. 276 printf("Error: collections_hash_table must be opened for traversal first.\n"); 277 return -1; 278 } 279 280 // XXX The bucktes (list) are not reset here which may cause errors when the 281 // hash table is only traversed half way. 282 283 t->cur_bucket_num = -1; 284 return 1; 285} 286 287struct collections_hash_visitor_tuple 288{ 289 collections_hash_visitor_func func; 290 void *arg; 291}; 292 293static int collections_hash_visit0(void* list_data, void* arg) 294{ 295 struct collections_hash_visitor_tuple *t = (struct collections_hash_visitor_tuple *)arg; 296 collections_hash_elem *he = (collections_hash_elem*)list_data; 297 return t->func(he->key, he->data, t->arg); 298} 299 300int collections_hash_visit(collections_hash_table* t, collections_hash_visitor_func func, void* arg) 301{ 302 struct collections_hash_visitor_tuple tuple = { func, arg }; 303 int i = 0; 304 while (i < t->num_buckets) 305 { 306 if (collections_list_visit(t->buckets[i], collections_hash_visit0, &tuple) == 0) { 307 break; 308 } 309 i++; 310 } 311 312 return (i == t->num_buckets); 313} 314