1/**************************************************************************
2 *
3 * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas.
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 TUNGSTEN GRAPHICS 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 cso_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 <jrfonseca@tungstengraphics.com>
38 */
39
40
41#include "pipe/p_compiler.h"
42#include "util/u_debug.h"
43
44#include "cso_cache/cso_hash.h"
45
46#include "util/u_memory.h"
47#include "util/u_hash_table.h"
48
49
50struct util_hash_table
51{
52   struct cso_hash *cso;
53
54   /** Hash function */
55   unsigned (*hash)(void *key);
56
57   /** Compare two keys */
58   int (*compare)(void *key1, void *key2);
59
60   /* TODO: key, value destructors? */
61};
62
63
64struct util_hash_table_item
65{
66   void *key;
67   void *value;
68};
69
70
71static INLINE struct util_hash_table_item *
72util_hash_table_item(struct cso_hash_iter iter)
73{
74   return (struct util_hash_table_item *)cso_hash_iter_data(iter);
75}
76
77
78struct util_hash_table *
79util_hash_table_create(unsigned (*hash)(void *key),
80                       int (*compare)(void *key1, void *key2))
81{
82   struct util_hash_table *ht;
83
84   ht = MALLOC_STRUCT(util_hash_table);
85   if(!ht)
86      return NULL;
87
88   ht->cso = cso_hash_create();
89   if(!ht->cso) {
90      FREE(ht);
91      return NULL;
92   }
93
94   ht->hash = hash;
95   ht->compare = compare;
96
97   return ht;
98}
99
100
101static INLINE struct cso_hash_iter
102util_hash_table_find_iter(struct util_hash_table *ht,
103                          void *key,
104                          unsigned key_hash)
105{
106   struct cso_hash_iter iter;
107   struct util_hash_table_item *item;
108
109   iter = cso_hash_find(ht->cso, key_hash);
110   while (!cso_hash_iter_is_null(iter)) {
111      item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
112      if (!ht->compare(item->key, key))
113         break;
114      iter = cso_hash_iter_next(iter);
115   }
116
117   return iter;
118}
119
120
121static INLINE struct util_hash_table_item *
122util_hash_table_find_item(struct util_hash_table *ht,
123                          void *key,
124                          unsigned key_hash)
125{
126   struct cso_hash_iter iter;
127   struct util_hash_table_item *item;
128
129   iter = cso_hash_find(ht->cso, key_hash);
130   while (!cso_hash_iter_is_null(iter)) {
131      item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
132      if (!ht->compare(item->key, key))
133         return item;
134      iter = cso_hash_iter_next(iter);
135   }
136
137   return NULL;
138}
139
140
141enum pipe_error
142util_hash_table_set(struct util_hash_table *ht,
143                    void *key,
144                    void *value)
145{
146   unsigned key_hash;
147   struct util_hash_table_item *item;
148   struct cso_hash_iter iter;
149
150   assert(ht);
151   if (!ht)
152      return PIPE_ERROR_BAD_INPUT;
153
154   key_hash = ht->hash(key);
155
156   item = util_hash_table_find_item(ht, key, key_hash);
157   if(item) {
158      /* TODO: key/value destruction? */
159      item->value = value;
160      return PIPE_OK;
161   }
162
163   item = MALLOC_STRUCT(util_hash_table_item);
164   if(!item)
165      return PIPE_ERROR_OUT_OF_MEMORY;
166
167   item->key = key;
168   item->value = value;
169
170   iter = cso_hash_insert(ht->cso, key_hash, item);
171   if(cso_hash_iter_is_null(iter)) {
172      FREE(item);
173      return PIPE_ERROR_OUT_OF_MEMORY;
174   }
175
176   return PIPE_OK;
177}
178
179
180void *
181util_hash_table_get(struct util_hash_table *ht,
182                    void *key)
183{
184   unsigned key_hash;
185   struct util_hash_table_item *item;
186
187   assert(ht);
188   if (!ht)
189      return NULL;
190
191   key_hash = ht->hash(key);
192
193   item = util_hash_table_find_item(ht, key, key_hash);
194   if(!item)
195      return NULL;
196
197   return item->value;
198}
199
200
201void
202util_hash_table_remove(struct util_hash_table *ht,
203                       void *key)
204{
205   unsigned key_hash;
206   struct cso_hash_iter iter;
207   struct util_hash_table_item *item;
208
209   assert(ht);
210   if (!ht)
211      return;
212
213   key_hash = ht->hash(key);
214
215   iter = util_hash_table_find_iter(ht, key, key_hash);
216   if(cso_hash_iter_is_null(iter))
217      return;
218
219   item = util_hash_table_item(iter);
220   assert(item);
221   FREE(item);
222
223   cso_hash_erase(ht->cso, iter);
224}
225
226
227void
228util_hash_table_clear(struct util_hash_table *ht)
229{
230   struct cso_hash_iter iter;
231   struct util_hash_table_item *item;
232
233   assert(ht);
234   if (!ht)
235      return;
236
237   iter = cso_hash_first_node(ht->cso);
238   while (!cso_hash_iter_is_null(iter)) {
239      item = (struct util_hash_table_item *)cso_hash_take(ht->cso, cso_hash_iter_key(iter));
240      FREE(item);
241      iter = cso_hash_first_node(ht->cso);
242   }
243}
244
245
246enum pipe_error
247util_hash_table_foreach(struct util_hash_table *ht,
248                     enum pipe_error (*callback)
249                        (void *key, void *value, void *data),
250                     void *data)
251{
252   struct cso_hash_iter iter;
253   struct util_hash_table_item *item;
254   enum pipe_error result;
255
256   assert(ht);
257   if (!ht)
258      return PIPE_ERROR_BAD_INPUT;
259
260   iter = cso_hash_first_node(ht->cso);
261   while (!cso_hash_iter_is_null(iter)) {
262      item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
263      result = callback(item->key, item->value, data);
264      if(result != PIPE_OK)
265	 return result;
266      iter = cso_hash_iter_next(iter);
267   }
268
269   return PIPE_OK;
270}
271
272
273void
274util_hash_table_destroy(struct util_hash_table *ht)
275{
276   struct cso_hash_iter iter;
277   struct util_hash_table_item *item;
278
279   assert(ht);
280   if (!ht)
281      return;
282
283   iter = cso_hash_first_node(ht->cso);
284   while (!cso_hash_iter_is_null(iter)) {
285      item = (struct util_hash_table_item *)cso_hash_iter_data(iter);
286      FREE(item);
287      iter = cso_hash_iter_next(iter);
288   }
289
290   cso_hash_delete(ht->cso);
291
292   FREE(ht);
293}
294