From 770cebbc29863ae944a31463ee4bdeb789105aba Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Mon, 20 Jul 2009 17:44:36 -0700 Subject: ARB_fp/vp: Initial import of new ARB vp/fp assembler This still needs quite a bit of work, but a bunch of the programs in progs/vp produce correct results. --- src/mesa/shader/hash_table.h | 108 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 108 insertions(+) create mode 100644 src/mesa/shader/hash_table.h (limited to 'src/mesa/shader/hash_table.h') diff --git a/src/mesa/shader/hash_table.h b/src/mesa/shader/hash_table.h new file mode 100644 index 0000000000..83ae7f07c7 --- /dev/null +++ b/src/mesa/shader/hash_table.h @@ -0,0 +1,108 @@ +/* + * Copyright © 2008 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. + */ + +/** + * \file hash_table.h + * \brief Implementation of a generic, opaque hash table data type. + * + * \author Ian Romanick + */ + +#ifndef HASH_TABLE_H +#define HASH_TABLE_H + +#include + +struct hash_table; + +typedef unsigned (*hash_func_t)(const void *key); +typedef int (*hash_compare_func_t)(const void *key1, const void *key2); + +/** + * Hash table constructor + * + * Creates a hash table with the specified number of buckets. The supplied + * \c hash and \c compare routines are used when adding elements to the table + * and when searching for elements in the table. + * + * \param num_buckets Number of buckets (bins) in the hash table. + * \param hash Function used to compute hash value of input keys. + * \param compare Function used to compare keys. + */ +extern struct hash_table *hash_table_ctor(unsigned num_buckets, + hash_func_t hash, hash_compare_func_t compare); + + +/** + * Flush all entries from a hash table + * + * \param ht Table to be cleared of its entries. + */ +extern void hash_table_clear(struct hash_table *ht); + + +/** + * Search a hash table for a specific element + * + * \param ht Table to be searched + * \param key Key of the desired element + * + * \return + * The \c data value supplied to \c hash_table_insert when the element with + * the matching key was added. If no matching key exists in the table, + * \c NULL is returned. + */ +extern void *hash_table_find(struct hash_table *ht, const void *key); + + +/** + * Add an element to a hash table + */ +extern void hash_table_insert(struct hash_table *ht, void *data, + const void *key); + + +/** + * Compute hash value of a string + * + * Computes the hash value of a string using the DJB2 algorithm developed by + * Professor Daniel J. Bernstein. It was published on comp.lang.c once upon + * a time. I was unable to find the original posting in the archives. + * + * \param key Pointer to a NUL terminated string to be hashed. + * + * \sa hash_table_string_compare + */ +extern unsigned hash_table_string_hash(const void *key); + + +/** + * Compare two strings used as keys + * + * This is just a macro wrapper around \c strcmp. + * + * \sa hash_table_string_hash + */ +#define hash_table_string_compare ((hash_compare_func_t) strcmp) + +#endif /* HASH_TABLE_H */ -- cgit v1.2.3 From 0044d3ba94f9041492ea90cf8961fd8b55daefda Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Mon, 27 Jul 2009 12:17:06 -0700 Subject: Add destructor for hash_table --- src/mesa/shader/hash_table.c | 15 ++++++++++++--- src/mesa/shader/hash_table.h | 9 +++++++++ 2 files changed, 21 insertions(+), 3 deletions(-) (limited to 'src/mesa/shader/hash_table.h') diff --git a/src/mesa/shader/hash_table.c b/src/mesa/shader/hash_table.c index 9b8f251bcc..3ff603b368 100644 --- a/src/mesa/shader/hash_table.c +++ b/src/mesa/shader/hash_table.c @@ -68,7 +68,8 @@ hash_table_ctor(unsigned num_buckets, hash_func_t hash, num_buckets = 16; } - ht = malloc(sizeof(*ht) + ((num_buckets - 1) * sizeof(ht->buckets[0]))); + ht = _mesa_malloc(sizeof(*ht) + ((num_buckets - 1) + * sizeof(ht->buckets[0]))); if (ht != NULL) { ht->hash = hash; ht->compare = compare; @@ -83,6 +84,14 @@ hash_table_ctor(unsigned num_buckets, hash_func_t hash, } +void +hash_table_dtor(struct hash_table *ht) +{ + hash_table_clear(ht); + _mesa_free(ht); +} + + void hash_table_clear(struct hash_table *ht) { @@ -94,7 +103,7 @@ hash_table_clear(struct hash_table *ht) for (i = 0; i < ht->num_buckets; i++) { foreach_s(node, temp, & ht->buckets[i]) { remove_from_list(node); - free(node); + _mesa_free(node); } assert(is_empty_list(& ht->buckets[i])); @@ -128,7 +137,7 @@ hash_table_insert(struct hash_table *ht, void *data, const void *key) const unsigned bucket = hash_value % ht->num_buckets; struct hash_node *node; - node = calloc(1, sizeof(*node)); + node = _mesa_calloc(1, sizeof(*node)); node->data = data; node->key = key; diff --git a/src/mesa/shader/hash_table.h b/src/mesa/shader/hash_table.h index 83ae7f07c7..7b302f5dbe 100644 --- a/src/mesa/shader/hash_table.h +++ b/src/mesa/shader/hash_table.h @@ -53,6 +53,15 @@ extern struct hash_table *hash_table_ctor(unsigned num_buckets, hash_func_t hash, hash_compare_func_t compare); +/** + * Release all memory associated with a hash table + * + * \warning + * This function cannot release memory occupied either by keys or data. + */ +extern void hash_table_dtor(struct hash_table *ht); + + /** * Flush all entries from a hash table * -- cgit v1.2.3