Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
5564 | serge | 1 | /* |
2 | * Copyright © 2009-2012 Intel Corporation |
||
3 | * Copyright © 1988-2004 Keith Packard and Bart Massey. |
||
4 | * |
||
5 | * Permission is hereby granted, free of charge, to any person obtaining a |
||
6 | * copy of this software and associated documentation files (the "Software"), |
||
7 | * to deal in the Software without restriction, including without limitation |
||
8 | * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
||
9 | * and/or sell copies of the Software, and to permit persons to whom the |
||
10 | * Software is furnished to do so, subject to the following conditions: |
||
11 | * |
||
12 | * The above copyright notice and this permission notice (including the next |
||
13 | * paragraph) shall be included in all copies or substantial portions of the |
||
14 | * Software. |
||
15 | * |
||
16 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
||
17 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
||
18 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
||
19 | * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
||
20 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
||
21 | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
||
22 | * IN THE SOFTWARE. |
||
23 | * |
||
24 | * Except as contained in this notice, the names of the authors |
||
25 | * or their institutions shall not be used in advertising or |
||
26 | * otherwise to promote the sale, use or other dealings in this |
||
27 | * Software without prior written authorization from the |
||
28 | * authors. |
||
29 | * |
||
30 | * Authors: |
||
31 | * Eric Anholt |
||
32 | * Keith Packard |
||
33 | */ |
||
34 | |||
35 | #include |
||
36 | #include |
||
37 | |||
38 | #include "macros.h" |
||
39 | #include "ralloc.h" |
||
40 | #include "set.h" |
||
41 | |||
42 | /* |
||
43 | * From Knuth -- a good choice for hash/rehash values is p, p-2 where |
||
44 | * p and p-2 are both prime. These tables are sized to have an extra 10% |
||
45 | * free to avoid exponential performance degradation as the hash table fills |
||
46 | */ |
||
47 | |||
48 | uint32_t deleted_key_value; |
||
49 | const void *deleted_key = &deleted_key_value; |
||
50 | |||
51 | static const struct { |
||
52 | uint32_t max_entries, size, rehash; |
||
53 | } hash_sizes[] = { |
||
54 | { 2, 5, 3 }, |
||
55 | { 4, 7, 5 }, |
||
56 | { 8, 13, 11 }, |
||
57 | { 16, 19, 17 }, |
||
58 | { 32, 43, 41 }, |
||
59 | { 64, 73, 71 }, |
||
60 | { 128, 151, 149 }, |
||
61 | { 256, 283, 281 }, |
||
62 | { 512, 571, 569 }, |
||
63 | { 1024, 1153, 1151 }, |
||
64 | { 2048, 2269, 2267 }, |
||
65 | { 4096, 4519, 4517 }, |
||
66 | { 8192, 9013, 9011 }, |
||
67 | { 16384, 18043, 18041 }, |
||
68 | { 32768, 36109, 36107 }, |
||
69 | { 65536, 72091, 72089 }, |
||
70 | { 131072, 144409, 144407 }, |
||
71 | { 262144, 288361, 288359 }, |
||
72 | { 524288, 576883, 576881 }, |
||
73 | { 1048576, 1153459, 1153457 }, |
||
74 | { 2097152, 2307163, 2307161 }, |
||
75 | { 4194304, 4613893, 4613891 }, |
||
76 | { 8388608, 9227641, 9227639 }, |
||
77 | { 16777216, 18455029, 18455027 }, |
||
78 | { 33554432, 36911011, 36911009 }, |
||
79 | { 67108864, 73819861, 73819859 }, |
||
80 | { 134217728, 147639589, 147639587 }, |
||
81 | { 268435456, 295279081, 295279079 }, |
||
82 | { 536870912, 590559793, 590559791 }, |
||
83 | { 1073741824, 1181116273, 1181116271 }, |
||
84 | { 2147483648ul, 2362232233ul, 2362232231ul } |
||
85 | }; |
||
86 | |||
87 | static int |
||
88 | entry_is_free(struct set_entry *entry) |
||
89 | { |
||
90 | return entry->key == NULL; |
||
91 | } |
||
92 | |||
93 | static int |
||
94 | entry_is_deleted(struct set_entry *entry) |
||
95 | { |
||
96 | return entry->key == deleted_key; |
||
97 | } |
||
98 | |||
99 | static int |
||
100 | entry_is_present(struct set_entry *entry) |
||
101 | { |
||
102 | return entry->key != NULL && entry->key != deleted_key; |
||
103 | } |
||
104 | |||
105 | struct set * |
||
106 | _mesa_set_create(void *mem_ctx, |
||
107 | uint32_t (*key_hash_function)(const void *key), |
||
108 | bool (*key_equals_function)(const void *a, |
||
109 | const void *b)) |
||
110 | { |
||
111 | struct set *ht; |
||
112 | |||
113 | ht = ralloc(mem_ctx, struct set); |
||
114 | if (ht == NULL) |
||
115 | return NULL; |
||
116 | |||
117 | ht->size_index = 0; |
||
118 | ht->size = hash_sizes[ht->size_index].size; |
||
119 | ht->rehash = hash_sizes[ht->size_index].rehash; |
||
120 | ht->max_entries = hash_sizes[ht->size_index].max_entries; |
||
121 | ht->key_hash_function = key_hash_function; |
||
122 | ht->key_equals_function = key_equals_function; |
||
123 | ht->table = rzalloc_array(ht, struct set_entry, ht->size); |
||
124 | ht->entries = 0; |
||
125 | ht->deleted_entries = 0; |
||
126 | |||
127 | if (ht->table == NULL) { |
||
128 | ralloc_free(ht); |
||
129 | return NULL; |
||
130 | } |
||
131 | |||
132 | return ht; |
||
133 | } |
||
134 | |||
135 | /** |
||
136 | * Frees the given set. |
||
137 | * |
||
138 | * If delete_function is passed, it gets called on each entry present before |
||
139 | * freeing. |
||
140 | */ |
||
141 | void |
||
142 | _mesa_set_destroy(struct set *ht, void (*delete_function)(struct set_entry *entry)) |
||
143 | { |
||
144 | if (!ht) |
||
145 | return; |
||
146 | |||
147 | if (delete_function) { |
||
148 | struct set_entry *entry; |
||
149 | |||
150 | set_foreach (ht, entry) { |
||
151 | delete_function(entry); |
||
152 | } |
||
153 | } |
||
154 | ralloc_free(ht->table); |
||
155 | ralloc_free(ht); |
||
156 | } |
||
157 | |||
158 | /** |
||
159 | * Finds a set entry with the given key and hash of that key. |
||
160 | * |
||
161 | * Returns NULL if no entry is found. |
||
162 | */ |
||
163 | static struct set_entry * |
||
164 | set_search(const struct set *ht, uint32_t hash, const void *key) |
||
165 | { |
||
166 | uint32_t hash_address; |
||
167 | |||
168 | hash_address = hash % ht->size; |
||
169 | do { |
||
170 | uint32_t double_hash; |
||
171 | |||
172 | struct set_entry *entry = ht->table + hash_address; |
||
173 | |||
174 | if (entry_is_free(entry)) { |
||
175 | return NULL; |
||
176 | } else if (entry_is_present(entry) && entry->hash == hash) { |
||
177 | if (ht->key_equals_function(key, entry->key)) { |
||
178 | return entry; |
||
179 | } |
||
180 | } |
||
181 | |||
182 | double_hash = 1 + hash % ht->rehash; |
||
183 | |||
184 | hash_address = (hash_address + double_hash) % ht->size; |
||
185 | } while (hash_address != hash % ht->size); |
||
186 | |||
187 | return NULL; |
||
188 | } |
||
189 | |||
190 | struct set_entry * |
||
191 | _mesa_set_search(const struct set *set, const void *key) |
||
192 | { |
||
193 | assert(set->key_hash_function); |
||
194 | return set_search(set, set->key_hash_function(key), key); |
||
195 | } |
||
196 | |||
197 | struct set_entry * |
||
198 | _mesa_set_search_pre_hashed(const struct set *set, uint32_t hash, |
||
199 | const void *key) |
||
200 | { |
||
201 | assert(set->key_hash_function == NULL || |
||
202 | hash == set->key_hash_function(key)); |
||
203 | return set_search(set, hash, key); |
||
204 | } |
||
205 | |||
206 | static struct set_entry * |
||
207 | set_add(struct set *ht, uint32_t hash, const void *key); |
||
208 | |||
209 | static void |
||
210 | set_rehash(struct set *ht, unsigned new_size_index) |
||
211 | { |
||
212 | struct set old_ht; |
||
213 | struct set_entry *table, *entry; |
||
214 | |||
215 | if (new_size_index >= ARRAY_SIZE(hash_sizes)) |
||
216 | return; |
||
217 | |||
218 | table = rzalloc_array(ht, struct set_entry, |
||
219 | hash_sizes[new_size_index].size); |
||
220 | if (table == NULL) |
||
221 | return; |
||
222 | |||
223 | old_ht = *ht; |
||
224 | |||
225 | ht->table = table; |
||
226 | ht->size_index = new_size_index; |
||
227 | ht->size = hash_sizes[ht->size_index].size; |
||
228 | ht->rehash = hash_sizes[ht->size_index].rehash; |
||
229 | ht->max_entries = hash_sizes[ht->size_index].max_entries; |
||
230 | ht->entries = 0; |
||
231 | ht->deleted_entries = 0; |
||
232 | |||
233 | for (entry = old_ht.table; |
||
234 | entry != old_ht.table + old_ht.size; |
||
235 | entry++) { |
||
236 | if (entry_is_present(entry)) { |
||
237 | set_add(ht, entry->hash, entry->key); |
||
238 | } |
||
239 | } |
||
240 | |||
241 | ralloc_free(old_ht.table); |
||
242 | } |
||
243 | |||
244 | /** |
||
245 | * Inserts the key with the given hash into the table. |
||
246 | * |
||
247 | * Note that insertion may rearrange the table on a resize or rehash, |
||
248 | * so previously found hash_entries are no longer valid after this function. |
||
249 | */ |
||
250 | static struct set_entry * |
||
251 | set_add(struct set *ht, uint32_t hash, const void *key) |
||
252 | { |
||
253 | uint32_t hash_address; |
||
254 | struct set_entry *available_entry = NULL; |
||
255 | |||
256 | if (ht->entries >= ht->max_entries) { |
||
257 | set_rehash(ht, ht->size_index + 1); |
||
258 | } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { |
||
259 | set_rehash(ht, ht->size_index); |
||
260 | } |
||
261 | |||
262 | hash_address = hash % ht->size; |
||
263 | do { |
||
264 | struct set_entry *entry = ht->table + hash_address; |
||
265 | uint32_t double_hash; |
||
266 | |||
267 | if (!entry_is_present(entry)) { |
||
268 | /* Stash the first available entry we find */ |
||
269 | if (available_entry == NULL) |
||
270 | available_entry = entry; |
||
271 | if (entry_is_free(entry)) |
||
272 | break; |
||
273 | } |
||
274 | |||
275 | /* Implement replacement when another insert happens |
||
276 | * with a matching key. This is a relatively common |
||
277 | * feature of hash tables, with the alternative |
||
278 | * generally being "insert the new value as well, and |
||
279 | * return it first when the key is searched for". |
||
280 | * |
||
281 | * Note that the hash table doesn't have a delete callback. |
||
282 | * If freeing of old keys is required to avoid memory leaks, |
||
283 | * perform a search before inserting. |
||
284 | */ |
||
285 | if (entry->hash == hash && |
||
286 | ht->key_equals_function(key, entry->key)) { |
||
287 | entry->key = key; |
||
288 | return entry; |
||
289 | } |
||
290 | |||
291 | double_hash = 1 + hash % ht->rehash; |
||
292 | |||
293 | hash_address = (hash_address + double_hash) % ht->size; |
||
294 | } while (hash_address != hash % ht->size); |
||
295 | |||
296 | if (available_entry) { |
||
297 | if (entry_is_deleted(available_entry)) |
||
298 | ht->deleted_entries--; |
||
299 | available_entry->hash = hash; |
||
300 | available_entry->key = key; |
||
301 | ht->entries++; |
||
302 | return available_entry; |
||
303 | } |
||
304 | |||
305 | /* We could hit here if a required resize failed. An unchecked-malloc |
||
306 | * application could ignore this result. |
||
307 | */ |
||
308 | return NULL; |
||
309 | } |
||
310 | |||
311 | struct set_entry * |
||
312 | _mesa_set_add(struct set *set, const void *key) |
||
313 | { |
||
314 | assert(set->key_hash_function); |
||
315 | return set_add(set, set->key_hash_function(key), key); |
||
316 | } |
||
317 | |||
318 | struct set_entry * |
||
319 | _mesa_set_add_pre_hashed(struct set *set, uint32_t hash, const void *key) |
||
320 | { |
||
321 | assert(set->key_hash_function == NULL || |
||
322 | hash == set->key_hash_function(key)); |
||
323 | return set_add(set, hash, key); |
||
324 | } |
||
325 | |||
326 | /** |
||
327 | * This function deletes the given hash table entry. |
||
328 | * |
||
329 | * Note that deletion doesn't otherwise modify the table, so an iteration over |
||
330 | * the table deleting entries is safe. |
||
331 | */ |
||
332 | void |
||
333 | _mesa_set_remove(struct set *ht, struct set_entry *entry) |
||
334 | { |
||
335 | if (!entry) |
||
336 | return; |
||
337 | |||
338 | entry->key = deleted_key; |
||
339 | ht->entries--; |
||
340 | ht->deleted_entries++; |
||
341 | } |
||
342 | |||
343 | /** |
||
344 | * This function is an iterator over the hash table. |
||
345 | * |
||
346 | * Pass in NULL for the first entry, as in the start of a for loop. Note that |
||
347 | * an iteration over the table is O(table_size) not O(entries). |
||
348 | */ |
||
349 | struct set_entry * |
||
350 | _mesa_set_next_entry(const struct set *ht, struct set_entry *entry) |
||
351 | { |
||
352 | if (entry == NULL) |
||
353 | entry = ht->table; |
||
354 | else |
||
355 | entry = entry + 1; |
||
356 | |||
357 | for (; entry != ht->table + ht->size; entry++) { |
||
358 | if (entry_is_present(entry)) { |
||
359 | return entry; |
||
360 | } |
||
361 | } |
||
362 | |||
363 | return NULL; |
||
364 | } |
||
365 | |||
366 | struct set_entry * |
||
367 | _mesa_set_random_entry(struct set *ht, |
||
368 | int (*predicate)(struct set_entry *entry)) |
||
369 | { |
||
370 | struct set_entry *entry; |
||
371 | uint32_t i = rand() % ht->size; |
||
372 | |||
373 | if (ht->entries == 0) |
||
374 | return NULL; |
||
375 | |||
376 | for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { |
||
377 | if (entry_is_present(entry) && |
||
378 | (!predicate || predicate(entry))) { |
||
379 | return entry; |
||
380 | } |
||
381 | } |
||
382 | |||
383 | for (entry = ht->table; entry != ht->table + i; entry++) { |
||
384 | if (entry_is_present(entry) && |
||
385 | (!predicate || predicate(entry))) { |
||
386 | return entry; |
||
387 | } |
||
388 | } |
||
389 | |||
390 | return NULL; |
||
391 | } |