1 /* x-hash.c - basic hash tables
3 * Copyright (c) 2002-2012 Apple Inc. All rights reserved.
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation files
7 * (the "Software"), to deal in the Software without restriction,
8 * including without limitation the rights to use, copy, modify, merge,
9 * publish, distribute, sublicense, and/or sell copies of the Software,
10 * and to permit persons to whom the Software is furnished to do so,
11 * subject to the following conditions:
13 * The above copyright notice and this permission notice shall be
14 * included in all copies or substantial portions of the Software.
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE ABOVE LISTED COPYRIGHT
20 * HOLDER(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
21 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
23 * DEALINGS IN THE SOFTWARE.
25 * Except as contained in this notice, the name(s) of the above
26 * copyright holders shall not be used in advertising or otherwise to
27 * promote the sale, use or other dealings in this Software without
28 * prior written authorization.
31 #ifdef HAVE_DIX_CONFIG_H
32 #include <dix-config.h>
40 struct x_hash_table_struct
{
41 unsigned int bucket_index
;
42 unsigned int total_keys
;
46 x_compare_fun
*compare_keys
;
47 x_destroy_fun
*destroy_key
;
48 x_destroy_fun
*destroy_value
;
51 #define ITEM_NEW(k, v) X_PFX(list_prepend) ((x_list *)(k), v)
52 #define ITEM_FREE(i) X_PFX(list_free_1) (i)
53 #define ITEM_KEY(i) ((void *)(i)->next)
54 #define ITEM_VALUE(i) ((i)->data)
56 #define SPLIT_THRESHOLD_FACTOR 2
58 /* http://planetmath.org/?op=getobj&from=objects&name=GoodHashTablePrimes */
59 static const unsigned int bucket_sizes
[] = {
60 29, 53, 97, 193, 389, 769, 1543,
61 3079, 6151, 12289, 24593, 49157,
62 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
64 25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
68 #define N_BUCKET_SIZES (sizeof(bucket_sizes) / sizeof(bucket_sizes[0]))
70 static inline unsigned int
71 hash_table_total_buckets(x_hash_table
*h
)
73 return bucket_sizes
[h
->bucket_index
];
77 hash_table_destroy_item(x_hash_table
*h
, void *k
, void *v
)
79 if (h
->destroy_key
!= 0)
82 if (h
->destroy_value
!= 0)
83 (*h
->destroy_value
)(v
);
87 hash_table_hash_key(x_hash_table
*h
, void *k
)
90 return (*h
->hash_key
)(k
);
96 hash_table_compare_keys(x_hash_table
*h
, void *k1
, void *k2
)
98 if (h
->compare_keys
== 0)
101 return (*h
->compare_keys
)(k1
, k2
) == 0;
105 hash_table_split(x_hash_table
*h
)
108 x_list
*node
, *item
, *next
;
109 int new_size
, old_size
;
113 if (h
->bucket_index
== N_BUCKET_SIZES
- 1)
116 old_size
= hash_table_total_buckets(h
);
121 new_size
= hash_table_total_buckets(h
);
122 new = calloc(new_size
, sizeof(x_list
*));
129 for (i
= 0; i
< old_size
; i
++) {
130 for (node
= old
[i
]; node
!= 0; node
= next
) {
134 b
= hash_table_hash_key(h
, ITEM_KEY(item
)) % new_size
;
145 X_EXTERN x_hash_table
*
146 X_PFX(hash_table_new
) (x_hash_fun
* hash
,
147 x_compare_fun
* compare
,
148 x_destroy_fun
* key_destroy
,
149 x_destroy_fun
* value_destroy
) {
152 h
= calloc(1, sizeof(x_hash_table
));
157 h
->buckets
= calloc(hash_table_total_buckets(h
), sizeof(x_list
*));
159 if (h
->buckets
== 0) {
165 h
->compare_keys
= compare
;
166 h
->destroy_key
= key_destroy
;
167 h
->destroy_value
= value_destroy
;
173 X_PFX(hash_table_free
) (x_hash_table
* h
) {
179 n
= hash_table_total_buckets(h
);
181 for (i
= 0; i
< n
; i
++) {
182 for (node
= h
->buckets
[i
]; node
!= 0; node
= node
->next
) {
184 hash_table_destroy_item(h
, ITEM_KEY(item
), ITEM_VALUE(item
));
187 X_PFX(list_free
) (h
->buckets
[i
]);
194 X_EXTERN
unsigned int
195 X_PFX(hash_table_size
) (x_hash_table
* h
) {
198 return h
->total_keys
;
202 hash_table_modify(x_hash_table
*h
, void *k
, void *v
, int replace
)
209 hash_value
= hash_table_hash_key(h
, k
);
211 for (node
= h
->buckets
[hash_value
% hash_table_total_buckets(h
)];
212 node
!= 0; node
= node
->next
) {
215 if (hash_table_compare_keys(h
, ITEM_KEY(item
), k
)) {
217 hash_table_destroy_item(h
, ITEM_KEY(item
),
220 ITEM_VALUE(item
) = v
;
223 hash_table_destroy_item(h
, k
, ITEM_VALUE(item
));
224 ITEM_VALUE(item
) = v
;
230 /* Key isn't already in the table. Insert it. */
232 if (h
->total_keys
+ 1
233 > hash_table_total_buckets(h
) * SPLIT_THRESHOLD_FACTOR
) {
237 hash_value
= hash_value
% hash_table_total_buckets(h
);
238 h
->buckets
[hash_value
] = X_PFX(list_prepend
) (h
->buckets
[hash_value
],
244 X_PFX(hash_table_insert
) (x_hash_table
* h
, void *k
, void *v
) {
245 hash_table_modify(h
, k
, v
, 0);
249 X_PFX(hash_table_replace
) (x_hash_table
* h
, void *k
, void *v
) {
250 hash_table_modify(h
, k
, v
, 1);
254 X_PFX(hash_table_remove
) (x_hash_table
* h
, void *k
) {
260 hash_value
= hash_table_hash_key(h
, k
);
262 for (ptr
= &h
->buckets
[hash_value
% hash_table_total_buckets(h
)];
263 *ptr
!= 0; ptr
= &((*ptr
)->next
)) {
266 if (hash_table_compare_keys(h
, ITEM_KEY(item
), k
)) {
267 hash_table_destroy_item(h
, ITEM_KEY(item
), ITEM_VALUE(item
));
271 X_PFX(list_free_1
) (item
);
279 X_PFX(hash_table_lookup
) (x_hash_table
* h
, void *k
, void **k_ret
) {
285 hash_value
= hash_table_hash_key(h
, k
);
287 for (node
= h
->buckets
[hash_value
% hash_table_total_buckets(h
)];
288 node
!= 0; node
= node
->next
) {
291 if (hash_table_compare_keys(h
, ITEM_KEY(item
), k
)) {
293 *k_ret
= ITEM_KEY(item
);
295 return ITEM_VALUE(item
);
306 X_PFX(hash_table_foreach
) (x_hash_table
* h
,
307 x_hash_foreach_fun
* fun
, void *data
) {
313 n
= hash_table_total_buckets(h
);
315 for (i
= 0; i
< n
; i
++) {
316 for (node
= h
->buckets
[i
]; node
!= 0; node
= node
->next
) {
318 (*fun
)(ITEM_KEY(item
), ITEM_VALUE(item
), data
);