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.c | 153 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) create mode 100644 src/mesa/shader/hash_table.c (limited to 'src/mesa/shader/hash_table.c') diff --git a/src/mesa/shader/hash_table.c b/src/mesa/shader/hash_table.c new file mode 100644 index 0000000000..9b8f251bcc --- /dev/null +++ b/src/mesa/shader/hash_table.c @@ -0,0 +1,153 @@ +/* + * 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.c + * \brief Implementation of a generic, opaque hash table data type. + * + * \author Ian Romanick + */ +#include +#include + +#include + +#include "main/simple_list.h" +#include "hash_table.h" + +struct node { + struct node *next; + struct node *prev; +}; + +struct hash_table { + hash_func_t hash; + hash_compare_func_t compare; + + unsigned num_buckets; + struct node buckets[1]; +}; + + +struct hash_node { + struct node link; + const void *key; + void *data; +}; + + +struct hash_table * +hash_table_ctor(unsigned num_buckets, hash_func_t hash, + hash_compare_func_t compare) +{ + struct hash_table *ht; + unsigned i; + + + if (num_buckets < 16) { + num_buckets = 16; + } + + ht = malloc(sizeof(*ht) + ((num_buckets - 1) * sizeof(ht->buckets[0]))); + if (ht != NULL) { + ht->hash = hash; + ht->compare = compare; + ht->num_buckets = num_buckets; + + for (i = 0; i < num_buckets; i++) { + make_empty_list(& ht->buckets[i]); + } + } + + return ht; +} + + +void +hash_table_clear(struct hash_table *ht) +{ + struct node *node; + struct node *temp; + unsigned i; + + + for (i = 0; i < ht->num_buckets; i++) { + foreach_s(node, temp, & ht->buckets[i]) { + remove_from_list(node); + free(node); + } + + assert(is_empty_list(& ht->buckets[i])); + } +} + + +void * +hash_table_find(struct hash_table *ht, const void *key) +{ + const unsigned hash_value = (*ht->hash)(key); + const unsigned bucket = hash_value % ht->num_buckets; + struct node *node; + + foreach(node, & ht->buckets[bucket]) { + struct hash_node *hn = (struct hash_node *) node; + + if ((*ht->compare)(hn->key, key) == 0) { + return hn->data; + } + } + + return NULL; +} + + +void +hash_table_insert(struct hash_table *ht, void *data, const void *key) +{ + const unsigned hash_value = (*ht->hash)(key); + const unsigned bucket = hash_value % ht->num_buckets; + struct hash_node *node; + + node = calloc(1, sizeof(*node)); + + node->data = data; + node->key = key; + + insert_at_head(& ht->buckets[bucket], & node->link); +} + + +unsigned +hash_table_string_hash(const void *key) +{ + const char *str = (const char *) key; + unsigned hash = 5381; + + + while (*str != '\0') { + hash = (hash * 33) + *str; + str++; + } + + return hash; +} -- 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.c') 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 From 4821099429ec059dc00a28f448bc3c537296ab55 Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Mon, 27 Jul 2009 15:46:07 -0700 Subject: ARB prog: Fix parameters to _mesa_calloc So totally awesome that _mesa_calloc has a different parameter signature than calloc. Why do these libc wrappers still exist?!? --- src/mesa/shader/hash_table.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/mesa/shader/hash_table.c') diff --git a/src/mesa/shader/hash_table.c b/src/mesa/shader/hash_table.c index 3ff603b368..a28a53ce02 100644 --- a/src/mesa/shader/hash_table.c +++ b/src/mesa/shader/hash_table.c @@ -137,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 = _mesa_calloc(1, sizeof(*node)); + node = _mesa_calloc(sizeof(*node)); node->data = data; node->key = key; -- cgit v1.2.3 From 523cb80d0f28d8dbb7b53b4d798e63baacc0ca35 Mon Sep 17 00:00:00 2001 From: Luo Jinghua Date: Sat, 22 Aug 2009 13:52:46 +0800 Subject: ARB prog parser: include imports.h to kill some compiler warnings --- src/mesa/shader/hash_table.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/mesa/shader/hash_table.c') diff --git a/src/mesa/shader/hash_table.c b/src/mesa/shader/hash_table.c index a28a53ce02..881179f9d8 100644 --- a/src/mesa/shader/hash_table.c +++ b/src/mesa/shader/hash_table.c @@ -32,6 +32,7 @@ #include +#include "main/imports.h" #include "main/simple_list.h" #include "hash_table.h" -- cgit v1.2.3