• Home
  • History
  • Annotate
  • 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