u_hash_table.c revision d26139d6a19aaf8b4dbbaa1ee937fed2283923e4 
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 "pipe/p_debug.h"
43#include "pipe/p_util.h"
44
45#include "cso_cache/cso_hash.h"
46#include "u_hash_table.h"
47
48
49struct hash_table
50{
51   struct cso_hash *cso;
52
53   /** Hash function */
54   unsigned (*hash)(void *key);
55
56   /** Compare two keys */
57   int (*compare)(void *key1, void *key2);
58
59   /* TODO: key, value destructors? */
60};
61
62
63struct hash_table_item
64{
65   void *key;
66   void *value;
67};
68
69
70struct hash_table *
71hash_table_create(unsigned (*hash)(void *key),
72                  int (*compare)(void *key1, void *key2))
73{
74   struct hash_table *ht;
75
76   ht = MALLOC_STRUCT(hash_table);
77   if(!ht)
78      return NULL;
79
80   ht->cso = cso_hash_create();
81   if(!ht->cso) {
82      FREE(ht);
83      return NULL;
84   }
85
86   ht->hash = hash;
87   ht->compare = compare;
88
89   return ht;
90}
91
92
93static struct hash_table_item *
94hash_table_find_item(struct hash_table *ht,
95                     void *key,
96                     unsigned key_hash)
97{
98   struct cso_hash_iter iter;
99   struct hash_table_item *item;
100
101   iter = cso_hash_find(ht->cso, key_hash);
102   while (!cso_hash_iter_is_null(iter)) {
103      item = (struct hash_table_item *)cso_hash_iter_data(iter);
104      if (!ht->compare(item->key, key))
105         return item;
106      iter = cso_hash_iter_next(iter);
107   }
108
109   return NULL;
110}
111
112
113enum pipe_error
114hash_table_set(struct hash_table *ht,
115               void *key,
116               void *value)
117{
118   unsigned key_hash;
119   struct hash_table_item *item;
120
121   assert(ht);
122
123   key_hash = ht->hash(key);
124
125   item = hash_table_find_item(ht, key, key_hash);
126   if(item) {
127      /* TODO: key/value destruction? */
128      item->value = value;
129      return PIPE_OK;
130   }
131
132   item = MALLOC_STRUCT(hash_table_item);
133   if(!item)
134      return PIPE_ERROR_OUT_OF_MEMORY;
135
136   item->key = key;
137   item->value = value;
138
139   cso_hash_insert(ht->cso, key_hash, item);
140   /* FIXME: there is no OOM propagation in cso_hash */
141   if(0) {
142      FREE(item);
143      return PIPE_ERROR_OUT_OF_MEMORY;
144   }
145
146   return PIPE_OK;
147}
148
149
150void *
151hash_table_get(struct hash_table *ht,
152               void *key)
153{
154   unsigned key_hash;
155   struct hash_table_item *item;
156
157   assert(ht);
158
159   key_hash = ht->hash(key);
160
161   item = hash_table_find_item(ht, key, key_hash);
162   if(!item)
163      return NULL;
164
165   return item->value;
166}
167
168
169void
170hash_table_remove(struct hash_table *ht,
171                  void *key)
172{
173   unsigned key_hash;
174   struct hash_table_item *item;
175
176   assert(ht);
177
178   key_hash = ht->hash(key);
179
180   item = hash_table_find_item(ht, key, key_hash);
181   if(!item)
182      return;
183
184   /* FIXME: cso_hash_take takes the first element of the collision list
185    * indiscriminately, so we can not take the item down. */
186   item->value = NULL;
187}
188
189
190enum pipe_error
191hash_table_foreach(struct hash_table *ht,
192                   enum pipe_error (*callback)(void *key, void *value, void *data),
193                   void *data)
194{
195   struct cso_hash_iter iter;
196   struct hash_table_item *item;
197   enum pipe_error result;
198
199   iter = cso_hash_first_node(ht->cso);
200   while (!cso_hash_iter_is_null(iter)) {
201      item = (struct hash_table_item *)cso_hash_iter_data(iter);
202      result = callback(item->key, item->value, data);
203      if(result != PIPE_OK)
204	 return result;
205      iter = cso_hash_iter_next(iter);
206   }
207
208   return PIPE_OK;
209}
210
211
212void
213hash_table_destroy(struct hash_table *ht)
214{
215   assert(ht);
216
217   cso_hash_delete(ht->cso);
218
219   FREE(ht);
220}
221