• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  * Key lookup/associative container.
30  *
31  * Like Jose's util_hash_table, based on CSO cache code for now.
32  *
33  * Author: Brian Paul
34  */
35 
36 
37 #include "pipe/p_compiler.h"
38 #include "util/u_debug.h"
39 
40 #include "cso_cache/cso_hash.h"
41 
42 #include "util/u_memory.h"
43 #include "util/u_keymap.h"
44 
45 
46 struct keymap
47 {
48    struct cso_hash *cso;
49    unsigned key_size;
50    unsigned max_entries; /* XXX not obeyed net */
51    unsigned num_entries;
52    keymap_delete_func delete_func;
53 };
54 
55 
56 struct keymap_item
57 {
58    void *key, *value;
59 };
60 
61 
62 /**
63  * This the default key-delete function used when the client doesn't
64  * provide one.
65  */
66 static void
default_delete_func(const struct keymap * map,const void * key,void * data,void * user)67 default_delete_func(const struct keymap *map,
68                     const void *key, void *data, void *user)
69 {
70    FREE((void*) data);
71 }
72 
73 
74 static INLINE struct keymap_item *
hash_table_item(struct cso_hash_iter iter)75 hash_table_item(struct cso_hash_iter iter)
76 {
77    return (struct keymap_item *) cso_hash_iter_data(iter);
78 }
79 
80 
81 /**
82  * Return 4-byte hash key for a block of bytes.
83  */
84 static unsigned
hash(const void * key,unsigned keySize)85 hash(const void *key, unsigned keySize)
86 {
87    unsigned i, hash;
88 
89    keySize /= 4; /* convert from bytes to uints */
90 
91    hash = 0;
92    for (i = 0; i < keySize; i++) {
93       hash ^= (i + 1) * ((const unsigned *) key)[i];
94    }
95 
96    /*hash = hash ^ (hash >> 11) ^ (hash >> 22);*/
97 
98    return hash;
99 }
100 
101 
102 /**
103  * Create a new map.
104  * \param keySize  size of the keys in bytes
105  * \param maxEntries  max number of entries to allow (~0 = infinity)
106  * \param deleteFunc  optional callback to call when entries
107  *                    are deleted/replaced
108  */
109 struct keymap *
util_new_keymap(unsigned keySize,unsigned maxEntries,keymap_delete_func deleteFunc)110 util_new_keymap(unsigned keySize, unsigned maxEntries,
111                  keymap_delete_func deleteFunc)
112 {
113    struct keymap *map = MALLOC_STRUCT(keymap);
114    if (!map)
115       return NULL;
116 
117    map->cso = cso_hash_create();
118    if (!map->cso) {
119       FREE(map);
120       return NULL;
121    }
122 
123    map->max_entries = maxEntries;
124    map->num_entries = 0;
125    map->key_size = keySize;
126    map->delete_func = deleteFunc ? deleteFunc : default_delete_func;
127 
128    return map;
129 }
130 
131 
132 /**
133  * Delete/free a keymap and all entries.  The deleteFunc that was given at
134  * create time will be called for each entry.
135  * \param user  user-provided pointer passed through to the delete callback
136  */
137 void
util_delete_keymap(struct keymap * map,void * user)138 util_delete_keymap(struct keymap *map, void *user)
139 {
140    util_keymap_remove_all(map, user);
141    cso_hash_delete(map->cso);
142    FREE(map);
143 }
144 
145 
146 static INLINE struct cso_hash_iter
hash_table_find_iter(const struct keymap * map,const void * key,unsigned key_hash)147 hash_table_find_iter(const struct keymap *map, const void *key,
148                      unsigned key_hash)
149 {
150    struct cso_hash_iter iter;
151    struct keymap_item *item;
152 
153    iter = cso_hash_find(map->cso, key_hash);
154    while (!cso_hash_iter_is_null(iter)) {
155       item = (struct keymap_item *) cso_hash_iter_data(iter);
156       if (!memcmp(item->key, key, map->key_size))
157          break;
158       iter = cso_hash_iter_next(iter);
159    }
160 
161    return iter;
162 }
163 
164 
165 static INLINE struct keymap_item *
hash_table_find_item(const struct keymap * map,const void * key,unsigned key_hash)166 hash_table_find_item(const struct keymap *map, const void *key,
167                      unsigned key_hash)
168 {
169    struct cso_hash_iter iter = hash_table_find_iter(map, key, key_hash);
170    if (cso_hash_iter_is_null(iter)) {
171       return NULL;
172    }
173    else {
174       return hash_table_item(iter);
175    }
176 }
177 
178 
179 /**
180  * Insert a new key + data pointer into the table.
181  * Note: we create a copy of the key, but not the data!
182  * If the key is already present in the table, replace the existing
183  * entry (calling the delete callback on the previous entry).
184  * If the maximum capacity of the map is reached an old entry
185  * will be deleted (the delete callback will be called).
186  */
187 boolean
util_keymap_insert(struct keymap * map,const void * key,const void * data,void * user)188 util_keymap_insert(struct keymap *map, const void *key,
189                    const void *data, void *user)
190 {
191    unsigned key_hash;
192    struct keymap_item *item;
193    struct cso_hash_iter iter;
194 
195    assert(map);
196    if (!map)
197       return FALSE;
198 
199    key_hash = hash(key, map->key_size);
200 
201    item = hash_table_find_item(map, key, key_hash);
202    if (item) {
203       /* call delete callback for old entry/item */
204       map->delete_func(map, item->key, item->value, user);
205       item->value = (void *) data;
206       return TRUE;
207    }
208 
209    item = MALLOC_STRUCT(keymap_item);
210    if (!item)
211       return FALSE;
212 
213    item->key = mem_dup(key, map->key_size);
214    item->value = (void *) data;
215 
216    iter = cso_hash_insert(map->cso, key_hash, item);
217    if (cso_hash_iter_is_null(iter)) {
218       FREE(item);
219       return FALSE;
220    }
221 
222    map->num_entries++;
223 
224    return TRUE;
225 }
226 
227 
228 /**
229  * Look up a key in the map and return the associated data pointer.
230  */
231 const void *
util_keymap_lookup(const struct keymap * map,const void * key)232 util_keymap_lookup(const struct keymap *map, const void *key)
233 {
234    unsigned key_hash;
235    struct keymap_item *item;
236 
237    assert(map);
238    if (!map)
239       return NULL;
240 
241    key_hash = hash(key, map->key_size);
242 
243    item = hash_table_find_item(map, key, key_hash);
244    if (!item)
245       return NULL;
246 
247    return item->value;
248 }
249 
250 
251 /**
252  * Remove an entry from the map.
253  * The delete callback will be called if the given key/entry is found.
254  * \param user  passed to the delete callback as the last param.
255  */
256 void
util_keymap_remove(struct keymap * map,const void * key,void * user)257 util_keymap_remove(struct keymap *map, const void *key, void *user)
258 {
259    unsigned key_hash;
260    struct cso_hash_iter iter;
261    struct keymap_item *item;
262 
263    assert(map);
264    if (!map)
265       return;
266 
267    key_hash = hash(key, map->key_size);
268 
269    iter = hash_table_find_iter(map, key, key_hash);
270    if (cso_hash_iter_is_null(iter))
271       return;
272 
273    item = hash_table_item(iter);
274    assert(item);
275    if (!item)
276       return;
277    map->delete_func(map, item->key, item->value, user);
278    FREE(item->key);
279    FREE(item);
280 
281    map->num_entries--;
282 
283    cso_hash_erase(map->cso, iter);
284 }
285 
286 
287 /**
288  * Remove all entries from the map, calling the delete callback for each.
289  * \param user  passed to the delete callback as the last param.
290  */
291 void
util_keymap_remove_all(struct keymap * map,void * user)292 util_keymap_remove_all(struct keymap *map, void *user)
293 {
294    struct cso_hash_iter iter;
295    struct keymap_item *item;
296 
297    assert(map);
298    if (!map)
299       return;
300 
301    iter = cso_hash_first_node(map->cso);
302    while (!cso_hash_iter_is_null(iter)) {
303       item = (struct keymap_item *)
304          cso_hash_take(map->cso, cso_hash_iter_key(iter));
305       map->delete_func(map, item->key, item->value, user);
306       FREE(item->key);
307       FREE(item);
308       iter = cso_hash_first_node(map->cso);
309    }
310 }
311 
312 
313 extern void
util_keymap_info(const struct keymap * map)314 util_keymap_info(const struct keymap *map)
315 {
316    debug_printf("Keymap %p: %u of max %u entries\n",
317                 (void *) map, map->num_entries, map->max_entries);
318 }
319