diff options
author | Eric Anholt <[email protected]> | 2012-11-06 23:18:41 -0800 |
---|---|---|
committer | Chad Versace <[email protected]> | 2012-11-12 15:52:42 -0800 |
commit | 35fd61bd99c15c2e13d3945b41c4db7df6e64319 (patch) | |
tree | 23771a21726cb11bd292ba51a5e95022032c7af6 /src/mesa/main/hash_table.h | |
parent | 1e8dd15311dab217d74c7c5d5a2dee6f6d7bf95e (diff) |
mesa: Import a copy of the open-addressing hash table code I wrote.
Mesa's chaining hash table for object names is slow, and this should be much
faster. I namespaced the functions under _mesa_*, to avoid visibility
troubles that we may have had before with hash_table_* functions.
v2: Move .c file to main/, const a few things, clean up loop conditions,
add/extend some comments.
Reviewed-by: Brian Paul <[email protected]>
Reviewed-by: Chad Versace <[email protected]>
Acked-by: Kenneth Graunke <[email protected]> (v1)
Diffstat (limited to 'src/mesa/main/hash_table.h')
-rw-r--r-- | src/mesa/main/hash_table.h | 105 |
1 files changed, 105 insertions, 0 deletions
diff --git a/src/mesa/main/hash_table.h b/src/mesa/main/hash_table.h new file mode 100644 index 00000000000..76e05a0856f --- /dev/null +++ b/src/mesa/main/hash_table.h @@ -0,0 +1,105 @@ +/* + * Copyright © 2009,2012 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <[email protected]> + * + */ + +#include <inttypes.h> +#include <stdbool.h> + +#ifndef _HASH_TABLE_H +#define _HASH_TABLE_H + +#ifdef __cplusplus +extern "C" { +#endif + +struct hash_entry { + uint32_t hash; + const void *key; + void *data; +}; + +struct hash_table { + void *mem_ctx; + struct hash_entry *table; + bool (*key_equals_function)(const void *a, const void *b); + const void *deleted_key; + uint32_t size; + uint32_t rehash; + uint32_t max_entries; + uint32_t size_index; + uint32_t entries; + uint32_t deleted_entries; +}; + +struct hash_table * +_mesa_hash_table_create(void *mem_ctx, + bool (*key_equals_function)(const void *a, + const void *b)); +void _mesa_hash_table_destroy(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)); +void _mesa_hash_table_set_deleted_key(struct hash_table *ht, + const void *deleted_key); + +struct hash_entry * +_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash, + const void *key, void *data); +struct hash_entry * +_mesa_hash_table_search(struct hash_table *ht, uint32_t hash, + const void *key); +void _mesa_hash_table_remove(struct hash_table *ht, + struct hash_entry *entry); + +struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht, + struct hash_entry *entry); +struct hash_entry * +_mesa_hash_table_random_entry(struct hash_table *ht, + bool (*predicate)(struct hash_entry *entry)); + +uint32_t _mesa_hash_data(const void *data, size_t size); +uint32_t _mesa_hash_string(const char *key); +bool _mesa_key_string_equal(const void *a, const void *b); +bool _mesa_key_pointer_equal(const void *a, const void *b); + +static inline uint32_t _mesa_hash_pointer(const void *pointer) +{ + return _mesa_hash_data(&pointer, sizeof(pointer)); +} + +/** + * This foreach function is safe against deletion (which just replaces + * an entry's data with the deleted marker), but not against insertion + * (which may rehash the table, making entry a dangling pointer). + */ +#define hash_table_foreach(ht, entry) \ + for (entry = _mesa_hash_table_next_entry(ht, NULL); \ + entry != NULL; \ + entry = _mesa_hash_table_next_entry(ht, entry)) + +#ifdef __cplusplus +} /* extern C */ +#endif + +#endif /* _HASH_TABLE_H */ |