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>
35 #include "main/imports.h"
36 #include "main/simple_list.h"
37 #include "hash_table.h"
46 hash_compare_func_t compare
;
49 struct node buckets
[1];
61 hash_table_ctor(unsigned num_buckets
, hash_func_t hash
,
62 hash_compare_func_t compare
)
64 struct hash_table
*ht
;
68 if (num_buckets
< 16) {
72 ht
= _mesa_malloc(sizeof(*ht
) + ((num_buckets
- 1)
73 * sizeof(ht
->buckets
[0])));
76 ht
->compare
= compare
;
77 ht
->num_buckets
= num_buckets
;
79 for (i
= 0; i
< num_buckets
; i
++) {
80 make_empty_list(& ht
->buckets
[i
]);
89 hash_table_dtor(struct hash_table
*ht
)
97 hash_table_clear(struct hash_table
*ht
)
104 for (i
= 0; i
< ht
->num_buckets
; i
++) {
105 foreach_s(node
, temp
, & ht
->buckets
[i
]) {
106 remove_from_list(node
);
110 assert(is_empty_list(& ht
->buckets
[i
]));
116 hash_table_find(struct hash_table
*ht
, const void *key
)
118 const unsigned hash_value
= (*ht
->hash
)(key
);
119 const unsigned bucket
= hash_value
% ht
->num_buckets
;
122 foreach(node
, & ht
->buckets
[bucket
]) {
123 struct hash_node
*hn
= (struct hash_node
*) node
;
125 if ((*ht
->compare
)(hn
->key
, key
) == 0) {
135 hash_table_insert(struct hash_table
*ht
, void *data
, const void *key
)
137 const unsigned hash_value
= (*ht
->hash
)(key
);
138 const unsigned bucket
= hash_value
% ht
->num_buckets
;
139 struct hash_node
*node
;
141 node
= _mesa_calloc(sizeof(*node
));
146 insert_at_head(& ht
->buckets
[bucket
], & node
->link
);
151 hash_table_string_hash(const void *key
)
153 const char *str
= (const char *) key
;
154 unsigned hash
= 5381;
157 while (*str
!= '\0') {
158 hash
= (hash
* 33) + *str
;