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