b1eb9d4e217d743d850e0eb3c6fb5f2f0f23f426
[mesa.git] / src / util / hash_table.h
1 /*
2 * Copyright © 2009,2012 Intel Corporation
3 *
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:
10 *
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
13 * Software.
14 *
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 DEALINGS
21 * IN THE SOFTWARE.
22 *
23 * Authors:
24 * Eric Anholt <eric@anholt.net>
25 *
26 */
27
28 #ifndef _HASH_TABLE_H
29 #define _HASH_TABLE_H
30
31 #include <stdlib.h>
32 #include <inttypes.h>
33 #include <stdbool.h>
34 #include "c99_compat.h"
35 #include "fnv1a.h"
36 #include "macros.h"
37
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41
42 struct hash_entry {
43 uint32_t hash;
44 const void *key;
45 void *data;
46 };
47
48 struct hash_table {
49 struct hash_entry *table;
50 uint32_t (*key_hash_function)(const void *key);
51 bool (*key_equals_function)(const void *a, const void *b);
52 const void *deleted_key;
53 uint32_t size;
54 uint32_t rehash;
55 uint64_t size_magic;
56 uint64_t rehash_magic;
57 uint32_t max_entries;
58 uint32_t size_index;
59 uint32_t entries;
60 uint32_t deleted_entries;
61 };
62
63 struct hash_table *
64 _mesa_hash_table_create(void *mem_ctx,
65 uint32_t (*key_hash_function)(const void *key),
66 bool (*key_equals_function)(const void *a,
67 const void *b));
68
69 bool
70 _mesa_hash_table_init(struct hash_table *ht,
71 void *mem_ctx,
72 uint32_t (*key_hash_function)(const void *key),
73 bool (*key_equals_function)(const void *a,
74 const void *b));
75
76 struct hash_table *
77 _mesa_hash_table_clone(struct hash_table *src, void *dst_mem_ctx);
78 void _mesa_hash_table_destroy(struct hash_table *ht,
79 void (*delete_function)(struct hash_entry *entry));
80 void _mesa_hash_table_clear(struct hash_table *ht,
81 void (*delete_function)(struct hash_entry *entry));
82 void _mesa_hash_table_set_deleted_key(struct hash_table *ht,
83 const void *deleted_key);
84
85 static inline uint32_t _mesa_hash_table_num_entries(struct hash_table *ht)
86 {
87 return ht->entries;
88 }
89
90 struct hash_entry *
91 _mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data);
92 struct hash_entry *
93 _mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash,
94 const void *key, void *data);
95 struct hash_entry *
96 _mesa_hash_table_search(struct hash_table *ht, const void *key);
97 struct hash_entry *
98 _mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash,
99 const void *key);
100 void _mesa_hash_table_remove(struct hash_table *ht,
101 struct hash_entry *entry);
102 void _mesa_hash_table_remove_key(struct hash_table *ht,
103 const void *key);
104
105 struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht,
106 struct hash_entry *entry);
107 struct hash_entry *
108 _mesa_hash_table_random_entry(struct hash_table *ht,
109 bool (*predicate)(struct hash_entry *entry));
110
111 uint32_t _mesa_hash_data(const void *data, size_t size);
112
113 uint32_t _mesa_hash_int(const void *key);
114 uint32_t _mesa_hash_uint(const void *key);
115 uint32_t _mesa_hash_u32(const void *key);
116 uint32_t _mesa_hash_string(const void *key);
117 uint32_t _mesa_hash_pointer(const void *pointer);
118
119 bool _mesa_key_int_equal(const void *a, const void *b);
120 bool _mesa_key_uint_equal(const void *a, const void *b);
121 bool _mesa_key_u32_equal(const void *a, const void *b);
122 bool _mesa_key_string_equal(const void *a, const void *b);
123 bool _mesa_key_pointer_equal(const void *a, const void *b);
124
125 struct hash_table *
126 _mesa_pointer_hash_table_create(void *mem_ctx);
127
128 /**
129 * This foreach function is safe against deletion (which just replaces
130 * an entry's data with the deleted marker), but not against insertion
131 * (which may rehash the table, making entry a dangling pointer).
132 */
133 #define hash_table_foreach(ht, entry) \
134 for (struct hash_entry *entry = _mesa_hash_table_next_entry(ht, NULL); \
135 entry != NULL; \
136 entry = _mesa_hash_table_next_entry(ht, entry))
137
138 static inline void
139 hash_table_call_foreach(struct hash_table *ht,
140 void (*callback)(const void *key,
141 void *data,
142 void *closure),
143 void *closure)
144 {
145 hash_table_foreach(ht, entry)
146 callback(entry->key, entry->data, closure);
147 }
148
149 /**
150 * Hash table wrapper which supports 64-bit keys.
151 */
152 struct hash_table_u64 {
153 struct hash_table *table;
154 void *freed_key_data;
155 void *deleted_key_data;
156 };
157
158 struct hash_table_u64 *
159 _mesa_hash_table_u64_create(void *mem_ctx);
160
161 void
162 _mesa_hash_table_u64_destroy(struct hash_table_u64 *ht,
163 void (*delete_function)(struct hash_entry *entry));
164
165 void
166 _mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key,
167 void *data);
168
169 void *
170 _mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key);
171
172 void
173 _mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key);
174
175 void
176 _mesa_hash_table_u64_clear(struct hash_table_u64 *ht,
177 void (*delete_function)(struct hash_entry *entry));
178
179 #ifdef __cplusplus
180 } /* extern C */
181 #endif
182
183 #endif /* _HASH_TABLE_H */