1/**************************************************************************
2 *
3 * Copyright 2008 VMware, Inc.
4 * All Rights Reserved.
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sub license, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice (including the
15 * next paragraph) shall be included in all copies or substantial portions
16 * of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 *
26 **************************************************************************/
27
28/**
29 * @file
30 * General purpose hash table implementation.
31 *
32 * Just uses the util_hash for now, but it might be better switch to a linear
33 * probing hash table implementation at some point -- as it is said they have
34 * better lookup and cache performance and it appears to be possible to write
35 * a lock-free implementation of such hash tables .
36 *
37 * @author José Fonseca <jfonseca@vmware.com>
38 */
39
40
41#ifdef HAVE_CONFIG_H
42#include "config.h"
43#endif
44
45#include "util_hash_table.h"
46#include "util_hash.h"
47
48#include <stdlib.h>
49#include <assert.h>
50
51struct util_hash_table
52{
53	struct util_hash *head;
54
55	/** Hash function */
56	unsigned (*make_hash)(void *key);
57
58	/** Compare two keys */
59	int (*compare)(void *key1, void *key2);
60};
61
62struct util_hash_table_item
63{
64	void *key;
65	void *value;
66};
67
68
69static struct util_hash_table_item *
70util_hash_table_item(struct util_hash_iter iter)
71{
72	return (struct util_hash_table_item *)util_hash_iter_data(iter);
73}
74
75drm_private struct util_hash_table *
76util_hash_table_create(unsigned (*hash)(void *key),
77		       int (*compare)(void *key1, void *key2))
78{
79	struct util_hash_table *ht;
80
81	ht = malloc(sizeof(struct util_hash_table));
82	if(!ht)
83		return NULL;
84
85	ht->head = util_hash_create();
86	if(!ht->head) {
87		free(ht);
88		return NULL;
89	}
90
91	ht->make_hash = hash;
92	ht->compare = compare;
93
94	return ht;
95}
96
97static struct util_hash_iter
98util_hash_table_find_iter(struct util_hash_table *ht,
99			  void *key, unsigned key_hash)
100{
101	struct util_hash_iter iter;
102	struct util_hash_table_item *item;
103
104	iter = util_hash_find(ht->head, key_hash);
105	while (!util_hash_iter_is_null(iter)) {
106		item = (struct util_hash_table_item *)util_hash_iter_data(iter);
107		if (!ht->compare(item->key, key))
108			break;
109		iter = util_hash_iter_next(iter);
110	}
111
112	return iter;
113}
114
115static struct util_hash_table_item *
116util_hash_table_find_item(struct util_hash_table *ht,
117                          void *key, unsigned key_hash)
118{
119	struct util_hash_iter iter;
120	struct util_hash_table_item *item;
121
122	iter = util_hash_find(ht->head, key_hash);
123	while (!util_hash_iter_is_null(iter)) {
124		item = (struct util_hash_table_item *)util_hash_iter_data(iter);
125		if (!ht->compare(item->key, key))
126			return item;
127		iter = util_hash_iter_next(iter);
128	}
129
130	return NULL;
131}
132
133drm_private void
134util_hash_table_set(struct util_hash_table *ht, void *key, void *value)
135{
136	unsigned key_hash;
137	struct util_hash_table_item *item;
138	struct util_hash_iter iter;
139
140	assert(ht);
141	if (!ht)
142		return;
143
144	key_hash = ht->make_hash(key);
145
146	item = util_hash_table_find_item(ht, key, key_hash);
147	if(item) {
148		/* TODO: key/value destruction? */
149		item->value = value;
150		return;
151	}
152
153	item = malloc(sizeof(struct util_hash_table_item));
154	if(!item)
155		return;
156
157	item->key = key;
158	item->value = value;
159
160	iter = util_hash_insert(ht->head, key_hash, item);
161	if(util_hash_iter_is_null(iter)) {
162		free(item);
163		return;
164	}
165}
166
167drm_private void *util_hash_table_get(struct util_hash_table *ht, void *key)
168{
169	unsigned key_hash;
170	struct util_hash_table_item *item;
171
172	assert(ht);
173	if (!ht)
174		return NULL;
175
176	key_hash = ht->make_hash(key);
177
178	item = util_hash_table_find_item(ht, key, key_hash);
179	if(!item)
180		return NULL;
181
182	return item->value;
183}
184
185drm_private void util_hash_table_remove(struct util_hash_table *ht, void *key)
186{
187	unsigned key_hash;
188	struct util_hash_iter iter;
189	struct util_hash_table_item *item;
190
191	assert(ht);
192	if (!ht)
193		return;
194
195	key_hash = ht->make_hash(key);
196
197	iter = util_hash_table_find_iter(ht, key, key_hash);
198	if(util_hash_iter_is_null(iter))
199		return;
200
201	item = util_hash_table_item(iter);
202	assert(item);
203	free(item);
204
205	util_hash_erase(ht->head, iter);
206}
207
208drm_private void util_hash_table_clear(struct util_hash_table *ht)
209{
210	struct util_hash_iter iter;
211	struct util_hash_table_item *item;
212
213	assert(ht);
214	if (!ht)
215		return;
216
217	iter = util_hash_first_node(ht->head);
218	while (!util_hash_iter_is_null(iter)) {
219		item = (struct util_hash_table_item *)util_hash_take(ht->head, util_hash_iter_key(iter));
220		free(item);
221		iter = util_hash_first_node(ht->head);
222	}
223}
224
225drm_private void util_hash_table_foreach(struct util_hash_table *ht,
226			void (*callback)(void *key, void *value, void *data),
227			void *data)
228{
229	struct util_hash_iter iter;
230	struct util_hash_table_item *item;
231
232	assert(ht);
233	if (!ht)
234		return;
235
236	iter = util_hash_first_node(ht->head);
237	while (!util_hash_iter_is_null(iter)) {
238		item = (struct util_hash_table_item *)util_hash_iter_data(iter);
239		callback(item->key, item->value, data);
240		iter = util_hash_iter_next(iter);
241	}
242}
243
244drm_private void util_hash_table_destroy(struct util_hash_table *ht)
245{
246	struct util_hash_iter iter;
247	struct util_hash_table_item *item;
248
249	assert(ht);
250	if (!ht)
251		return;
252
253	iter = util_hash_first_node(ht->head);
254	while (!util_hash_iter_is_null(iter)) {
255		item = (struct util_hash_table_item *)util_hash_iter_data(iter);
256		free(item);
257		iter = util_hash_iter_next(iter);
258	}
259
260	util_hash_delete(ht->head);
261	free(ht);
262}
263