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, Haldeneggsteig 4, CH-8092 Zurich. Attn: Systems Group. 12 */ 13 14#ifndef _HASH_TABLE_H_ 15#define _HASH_TABLE_H_ 16 17#include "collections/list.h" 18 19/* 20 * a simple hash table. 21 */ 22 23typedef void (* collections_hash_data_free)(void *); 24 25typedef struct _collections_hash_table { 26 // number of buckets in the table. 27 int num_buckets; 28 29 // pointer to the buckets. 30 collections_listnode **buckets; 31 32 // total number of elements in the table. 33 uint32_t num_elems; 34 35 // function that knows how to free inserted data resources 36 collections_hash_data_free data_free; 37 38 // a pointer to keep track of 39 // traversing the hash table 40 int32_t cur_bucket_num; 41} collections_hash_table; 42 43/* 44 * Structure of a hash table element. 45 */ 46typedef struct _collections_hash_elem { 47 48 uint64_t key; 49 50 void *data; 51} collections_hash_elem; 52 53#define NUM_BUCKETS 1013 54 55#ifdef __cplusplus 56extern "C" { 57#endif // __cplusplus 58 59 60/* 61 * functions ... 62 */ 63void collections_hash_create(collections_hash_table **t, collections_hash_data_free f); 64void collections_hash_create_with_buckets(collections_hash_table **t, int num_buckets, collections_hash_data_free f); 65void collections_hash_release(collections_hash_table *t); 66void collections_hash_insert(collections_hash_table *t, uint64_t key, void *data); 67void* collections_hash_find(collections_hash_table *t, uint64_t key); 68void collections_hash_delete(collections_hash_table *t, uint64_t key); 69uint32_t collections_hash_size(collections_hash_table *t); 70int32_t collections_hash_traverse_start(collections_hash_table* t); 71void* collections_hash_traverse_next(collections_hash_table* t, uint64_t *key); 72int32_t collections_hash_traverse_end(collections_hash_table* t); 73 74/* 75 * Visitor function: returns 0 when visit should be considered finish. 76 */ 77typedef int (*collections_hash_visitor_func)(uint64_t key, void *data, void *arg); 78 79/* 80 * Apply function to all elements in hash table or until function indicates 81 * function application should stop. 82 * 83 * Returns non-zero if all elements in table visited, 0 otherwise. 84 */ 85int collections_hash_visit(collections_hash_table *t, collections_hash_visitor_func collections_hash_visitor, void *arg); 86 87#ifdef __cplusplus 88} 89#endif // __cplusplus 90 91#endif 92