2 * Copyright © 2008 Intel Corporation
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
26 * \brief Implementation of a generic, opaque hash table data type.
28 * \author Ian Romanick <ian.d.romanick@intel.com>
31 #include "main/imports.h"
32 #include "util/simple_list.h"
33 #include "hash_table.h"
42 hash_compare_func_t compare
;
45 struct node buckets
[1];
57 hash_table_ctor(unsigned num_buckets
, hash_func_t hash
,
58 hash_compare_func_t compare
)
60 struct hash_table
*ht
;
64 if (num_buckets
< 16) {
68 ht
= malloc(sizeof(*ht
) + ((num_buckets
- 1)
69 * sizeof(ht
->buckets
[0])));
72 ht
->compare
= compare
;
73 ht
->num_buckets
= num_buckets
;
75 for (i
= 0; i
< num_buckets
; i
++) {
76 make_empty_list(& ht
->buckets
[i
]);
85 hash_table_dtor(struct hash_table
*ht
)
93 hash_table_clear(struct hash_table
*ht
)
100 for (i
= 0; i
< ht
->num_buckets
; i
++) {
101 foreach_s(node
, temp
, & ht
->buckets
[i
]) {
102 remove_from_list(node
);
106 assert(is_empty_list(& ht
->buckets
[i
]));
111 static struct hash_node
*
112 get_node(struct hash_table
*ht
, const void *key
)
114 const unsigned hash_value
= (*ht
->hash
)(key
);
115 const unsigned bucket
= hash_value
% ht
->num_buckets
;
118 foreach(node
, & ht
->buckets
[bucket
]) {
119 struct hash_node
*hn
= (struct hash_node
*) node
;
121 if ((*ht
->compare
)(hn
->key
, key
) == 0) {
130 hash_table_find(struct hash_table
*ht
, const void *key
)
132 struct hash_node
*hn
= get_node(ht
, key
);
134 return (hn
== NULL
) ? NULL
: hn
->data
;
138 hash_table_insert(struct hash_table
*ht
, void *data
, const void *key
)
140 const unsigned hash_value
= (*ht
->hash
)(key
);
141 const unsigned bucket
= hash_value
% ht
->num_buckets
;
142 struct hash_node
*node
;
144 node
= calloc(1, sizeof(*node
));
146 _mesa_error_no_memory(__func__
);
153 insert_at_head(& ht
->buckets
[bucket
], & node
->link
);
157 hash_table_replace(struct hash_table
*ht
, void *data
, const void *key
)
159 const unsigned hash_value
= (*ht
->hash
)(key
);
160 const unsigned bucket
= hash_value
% ht
->num_buckets
;
162 struct hash_node
*hn
;
164 foreach(node
, & ht
->buckets
[bucket
]) {
165 hn
= (struct hash_node
*) node
;
167 if ((*ht
->compare
)(hn
->key
, key
) == 0) {
173 hn
= calloc(1, sizeof(*hn
));
175 _mesa_error_no_memory(__func__
);
182 insert_at_head(& ht
->buckets
[bucket
], & hn
->link
);
187 hash_table_remove(struct hash_table
*ht
, const void *key
)
189 struct node
*node
= (struct node
*) get_node(ht
, key
);
191 remove_from_list(node
);
198 hash_table_call_foreach(struct hash_table
*ht
,
199 void (*callback
)(const void *key
,
206 for (bucket
= 0; bucket
< ht
->num_buckets
; bucket
++) {
207 struct node
*node
, *temp
;
208 foreach_s(node
, temp
, &ht
->buckets
[bucket
]) {
209 struct hash_node
*hn
= (struct hash_node
*) node
;
211 callback(hn
->key
, hn
->data
, closure
);
217 hash_table_string_hash(const void *key
)
219 const char *str
= (const char *) key
;
220 unsigned hash
= 5381;
223 while (*str
!= '\0') {
224 hash
= (hash
* 33) + *str
;
233 hash_table_pointer_hash(const void *key
)
235 return (unsigned)((uintptr_t) key
/ sizeof(void *));
240 hash_table_pointer_compare(const void *key1
, const void *key2
)
242 return key1
== key2
? 0 : 1;