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