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 "macros.h" 35 36#ifdef __cplusplus 37extern "C" { 38#endif 39 40struct hash_entry { 41 uint32_t hash; 42 const void *key; 43 void *data; 44}; 45 46struct hash_table { 47 struct hash_entry *table; 48 uint32_t (*key_hash_function)(const void *key); 49 bool (*key_equals_function)(const void *a, const void *b); 50 const void *deleted_key; 51 uint32_t size; 52 uint32_t rehash; 53 uint64_t size_magic; 54 uint64_t rehash_magic; 55 uint32_t max_entries; 56 uint32_t size_index; 57 uint32_t entries; 58 uint32_t deleted_entries; 59}; 60 61struct hash_table * 62_mesa_hash_table_create(void *mem_ctx, 63 uint32_t (*key_hash_function)(const void *key), 64 bool (*key_equals_function)(const void *a, 65 const void *b)); 66 67bool 68_mesa_hash_table_init(struct hash_table *ht, 69 void *mem_ctx, 70 uint32_t (*key_hash_function)(const void *key), 71 bool (*key_equals_function)(const void *a, 72 const void *b)); 73 74struct hash_table * 75_mesa_hash_table_create_u32_keys(void *mem_ctx); 76 77struct hash_table * 78_mesa_hash_table_clone(struct hash_table *src, void *dst_mem_ctx); 79void _mesa_hash_table_destroy(struct hash_table *ht, 80 void (*delete_function)(struct hash_entry *entry)); 81void _mesa_hash_table_clear(struct hash_table *ht, 82 void (*delete_function)(struct hash_entry *entry)); 83void _mesa_hash_table_set_deleted_key(struct hash_table *ht, 84 const void *deleted_key); 85 86static inline uint32_t _mesa_hash_table_num_entries(struct hash_table *ht) 87{ 88 return ht->entries; 89} 90 91struct hash_entry * 92_mesa_hash_table_insert(struct hash_table *ht, const void *key, void *data); 93struct hash_entry * 94_mesa_hash_table_insert_pre_hashed(struct hash_table *ht, uint32_t hash, 95 const void *key, void *data); 96struct hash_entry * 97_mesa_hash_table_search(struct hash_table *ht, const void *key); 98struct hash_entry * 99_mesa_hash_table_search_pre_hashed(struct hash_table *ht, uint32_t hash, 100 const void *key); 101void _mesa_hash_table_remove(struct hash_table *ht, 102 struct hash_entry *entry); 103void _mesa_hash_table_remove_key(struct hash_table *ht, 104 const void *key); 105 106struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht, 107 struct hash_entry *entry); 108struct hash_entry *_mesa_hash_table_next_entry_unsafe(const struct hash_table *ht, 109 struct hash_entry *entry); 110struct hash_entry * 111_mesa_hash_table_random_entry(struct hash_table *ht, 112 bool (*predicate)(struct hash_entry *entry)); 113 114uint32_t _mesa_hash_data(const void *data, size_t size); 115uint32_t _mesa_hash_data_with_seed(const void *data, size_t size, uint32_t seed); 116 117uint32_t _mesa_hash_int(const void *key); 118uint32_t _mesa_hash_uint(const void *key); 119uint32_t _mesa_hash_u32(const void *key); 120uint32_t _mesa_hash_string(const void *key); 121uint32_t _mesa_hash_string_with_length(const void *_key, unsigned length); 122uint32_t _mesa_hash_pointer(const void *pointer); 123 124bool _mesa_key_int_equal(const void *a, const void *b); 125bool _mesa_key_uint_equal(const void *a, const void *b); 126bool _mesa_key_u32_equal(const void *a, const void *b); 127bool _mesa_key_string_equal(const void *a, const void *b); 128bool _mesa_key_pointer_equal(const void *a, const void *b); 129 130struct hash_table * 131_mesa_pointer_hash_table_create(void *mem_ctx); 132 133bool 134_mesa_hash_table_reserve(struct hash_table *ht, unsigned size); 135/** 136 * This foreach function is safe against deletion (which just replaces 137 * an entry's data with the deleted marker), but not against insertion 138 * (which may rehash the table, making entry a dangling pointer). 139 */ 140#define hash_table_foreach(ht, entry) \ 141 for (struct hash_entry *entry = _mesa_hash_table_next_entry(ht, NULL); \ 142 entry != NULL; \ 143 entry = _mesa_hash_table_next_entry(ht, entry)) 144/** 145 * This foreach function destroys the table as it iterates. 146 * It is not safe to use when inserting or removing entries. 147 */ 148#define hash_table_foreach_remove(ht, entry) \ 149 for (struct hash_entry *entry = _mesa_hash_table_next_entry_unsafe(ht, NULL); \ 150 (ht)->entries; \ 151 entry->hash = 0, entry->key = (void*)NULL, entry->data = NULL, \ 152 (ht)->entries--, entry = _mesa_hash_table_next_entry_unsafe(ht, entry)) 153 154static inline void 155hash_table_call_foreach(struct hash_table *ht, 156 void (*callback)(const void *key, 157 void *data, 158 void *closure), 159 void *closure) 160{ 161 hash_table_foreach(ht, entry) 162 callback(entry->key, entry->data, closure); 163} 164 165/** 166 * Hash table wrapper which supports 64-bit keys. 167 */ 168struct hash_table_u64 { 169 struct hash_table *table; 170 void *freed_key_data; 171 void *deleted_key_data; 172}; 173 174struct hash_table_u64 * 175_mesa_hash_table_u64_create(void *mem_ctx); 176 177void 178_mesa_hash_table_u64_destroy(struct hash_table_u64 *ht); 179 180void 181_mesa_hash_table_u64_insert(struct hash_table_u64 *ht, uint64_t key, 182 void *data); 183 184void * 185_mesa_hash_table_u64_search(struct hash_table_u64 *ht, uint64_t key); 186 187void 188_mesa_hash_table_u64_remove(struct hash_table_u64 *ht, uint64_t key); 189 190void 191_mesa_hash_table_u64_clear(struct hash_table_u64 *ht); 192 193#ifdef __cplusplus 194} /* extern C */ 195#endif 196 197#endif /* _HASH_TABLE_H */ 198