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 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 <[email protected]>
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_pointer.h"
48 #include "util/u_hash_table.h"
49 #include "util/hash_table.h"
50 #include "ralloc.h"
51
52
53 struct util_hash_table
54 {
55 struct hash_table table;
56
57 /** free value */
58 void (*destroy)(void *value);
59 };
60
61 struct util_hash_table *
util_hash_table_create(uint32_t (* hash)(const void * key),bool (* equal)(const void * key1,const void * key2),void (* destroy)(void * value))62 util_hash_table_create(uint32_t (*hash)(const void *key),
63 bool (*equal)(const void *key1, const void *key2),
64 void (*destroy)(void *value))
65 {
66 struct util_hash_table *ht;
67
68 ht = ralloc(NULL, struct util_hash_table);
69 if(!ht)
70 return NULL;
71
72 if (!_mesa_hash_table_init(&ht->table, ht, hash, equal)) {
73 ralloc_free(ht);
74 return NULL;
75 }
76
77 ht->destroy = destroy;
78
79 return ht;
80 }
81
82 enum pipe_error
util_hash_table_set(struct util_hash_table * ht,void * key,void * value)83 util_hash_table_set(struct util_hash_table *ht,
84 void *key,
85 void *value)
86 {
87 uint32_t key_hash;
88 struct hash_entry *item;
89
90 assert(ht);
91 if (!ht)
92 return PIPE_ERROR_BAD_INPUT;
93
94 if (!key)
95 return PIPE_ERROR_BAD_INPUT;
96
97 key_hash = ht->table.key_hash_function(key);
98
99 item = _mesa_hash_table_search_pre_hashed(&ht->table, key_hash, key);
100 if(item) {
101 ht->destroy(item->data);
102 item->data = value;
103 return PIPE_OK;
104 }
105
106 item = _mesa_hash_table_insert_pre_hashed(&ht->table, key_hash, key, value);
107 if(!item)
108 return PIPE_ERROR_OUT_OF_MEMORY;
109
110 return PIPE_OK;
111 }
112
113
114 void *
util_hash_table_get(struct util_hash_table * ht,void * key)115 util_hash_table_get(struct util_hash_table *ht,
116 void *key)
117 {
118 struct hash_entry *item;
119
120 assert(ht);
121 if (!ht)
122 return NULL;
123
124 if (!key)
125 return NULL;
126
127 item = _mesa_hash_table_search(&ht->table, key);
128 if(!item)
129 return NULL;
130
131 return item->data;
132 }
133
134
135 void
util_hash_table_remove(struct util_hash_table * ht,void * key)136 util_hash_table_remove(struct util_hash_table *ht,
137 void *key)
138 {
139 struct hash_entry *item;
140
141 assert(ht);
142 if (!ht)
143 return;
144
145 if (!key)
146 return;
147
148 item = _mesa_hash_table_search(&ht->table, key);
149 if (!item)
150 return;
151
152 ht->destroy(item->data);
153 _mesa_hash_table_remove(&ht->table, item);
154 }
155
156
157 void
util_hash_table_clear(struct util_hash_table * ht)158 util_hash_table_clear(struct util_hash_table *ht)
159 {
160 assert(ht);
161 if (!ht)
162 return;
163
164 hash_table_foreach(&ht->table, item) {
165 ht->destroy(item->data);
166 }
167
168 _mesa_hash_table_clear(&ht->table, NULL);
169 }
170
171
172 enum pipe_error
util_hash_table_foreach(struct util_hash_table * ht,enum pipe_error (* callback)(void * key,void * value,void * data),void * data)173 util_hash_table_foreach(struct util_hash_table *ht,
174 enum pipe_error (*callback)
175 (void *key, void *value, void *data),
176 void *data)
177 {
178 assert(ht);
179 if (!ht)
180 return PIPE_ERROR_BAD_INPUT;
181
182 hash_table_foreach(&ht->table, item) {
183 enum pipe_error result = callback((void *)item->key, item->data, data);
184 if (result != PIPE_OK)
185 return result;
186 }
187
188 return PIPE_OK;
189 }
190
191
192 void
util_hash_table_destroy(struct util_hash_table * ht)193 util_hash_table_destroy(struct util_hash_table *ht)
194 {
195 assert(ht);
196 if (!ht)
197 return;
198
199 hash_table_foreach(&ht->table, item) {
200 ht->destroy(item->data);
201 }
202
203 ralloc_free(ht);
204 }
205