diff options
Diffstat (limited to 'src/gallium/auxiliary/util')
| -rw-r--r-- | src/gallium/auxiliary/util/Makefile | 1 | ||||
| -rw-r--r-- | src/gallium/auxiliary/util/SConscript | 1 | ||||
| -rw-r--r-- | src/gallium/auxiliary/util/p_debug.c | 30 | ||||
| -rw-r--r-- | src/gallium/auxiliary/util/u_handle_table.c | 89 | ||||
| -rw-r--r-- | src/gallium/auxiliary/util/u_handle_table.h | 11 | ||||
| -rw-r--r-- | src/gallium/auxiliary/util/u_hash_table.c | 199 | ||||
| -rw-r--r-- | src/gallium/auxiliary/util/u_hash_table.h | 86 |
7 files changed, 386 insertions, 31 deletions
diff --git a/src/gallium/auxiliary/util/Makefile b/src/gallium/auxiliary/util/Makefile index 2abbe9500e..2016c6fb1f 100644 --- a/src/gallium/auxiliary/util/Makefile +++ b/src/gallium/auxiliary/util/Makefile @@ -8,6 +8,7 @@ C_SOURCES = \ p_tile.c \ p_util.c \ u_handle_table.c \ + u_hash_table.c \ u_mm.c \ u_snprintf.c diff --git a/src/gallium/auxiliary/util/SConscript b/src/gallium/auxiliary/util/SConscript index 2030214aa7..154a3eca8c 100644 --- a/src/gallium/auxiliary/util/SConscript +++ b/src/gallium/auxiliary/util/SConscript @@ -7,6 +7,7 @@ util = env.ConvenienceLibrary( 'p_tile.c', 'p_util.c', 'u_handle_table.c', + 'u_hash_table.c', 'u_mm.c', 'u_snprintf.c', ]) diff --git a/src/gallium/auxiliary/util/p_debug.c b/src/gallium/auxiliary/util/p_debug.c index 09cabdae25..bb84e8096d 100644 --- a/src/gallium/auxiliary/util/p_debug.c +++ b/src/gallium/auxiliary/util/p_debug.c @@ -109,20 +109,30 @@ enum { /* Check for aborts enabled. */ static unsigned abort_en() { - if (!mapped_config_file) - { - /* Open an 8 byte file for configuration data. */ - mapped_config_file = EngMapFile(L"\\??\\c:\\gaDebug.cfg", 8, &debug_config_file); - } - /* An value of "0" (ascii) in the configuration file will clear the first 8 bits in the test byte. */ - /* An value of "1" (ascii) in the configuration file will set the first bit in the test byte. */ - /* An value of "2" (ascii) in the configuration file will set the second bit in the test byte. */ - return ((((char *)mapped_config_file)[0]) - 0x30) & eAssertAbortEn; + if (!mapped_config_file) + { + /* Open an 8 byte file for configuration data. */ + mapped_config_file = EngMapFile(L"\\??\\c:\\gaDebug.cfg", 8, &debug_config_file); + } + + /* A value of "0" (ascii) in the configuration file will clear the + * first 8 bits in the test byte. + * + * A value of "1" (ascii) in the configuration file will set the + * first bit in the test byte. + * + * A value of "2" (ascii) in the configuration file will set the + * second bit in the test byte. + * + * Currently the only interesting values are 0 and 1, which clear + * and set abort-on-assert behaviour respectively. + */ + return ((((char *)mapped_config_file)[0]) - 0x30) & eAssertAbortEn; } #else /* WIN32 */ static unsigned abort_en() { - return !GETENV("GALLIUM_ABORT_ON_ASSERT"); + return !GETENV("GALLIUM_ABORT_ON_ASSERT"); } #endif diff --git a/src/gallium/auxiliary/util/u_handle_table.c b/src/gallium/auxiliary/util/u_handle_table.c index 8a298f7c41..d25872972a 100644 --- a/src/gallium/auxiliary/util/u_handle_table.c +++ b/src/gallium/auxiliary/util/u_handle_table.c @@ -26,6 +26,7 @@ **************************************************************************/ /** + * @file * Generic handle table implementation. * * @author José Fonseca <jrfonseca@tungstengraphics.com> @@ -90,6 +91,39 @@ handle_table_set_destroy(struct handle_table *ht, } +/** + * Resize the table if necessary + */ +static INLINE int +handle_table_resize(struct handle_table *ht, + unsigned minimum_size) +{ + unsigned new_size; + void **new_objects; + + if(ht->size > minimum_size) + return ht->size; + + new_size = ht->size; + while(!(new_size > minimum_size)) + new_size *= 2; + assert(new_size); + + new_objects = (void **)REALLOC((void *)ht->objects, + ht->size*sizeof(void *), + new_size*sizeof(void *)); + if(!new_objects) + return 0; + + memset(new_objects + ht->size, 0, (new_size - ht->size)*sizeof(void *)); + + ht->size = new_size; + ht->objects = new_objects; + + return ht->size; +} + + unsigned handle_table_add(struct handle_table *ht, void *object) @@ -109,34 +143,17 @@ handle_table_add(struct handle_table *ht, ++ht->filled; } - /* grow the table */ - if(ht->filled == ht->size) { - unsigned new_size; - void **new_objects; - - new_size = ht->size*2; - assert(new_size); - - new_objects = (void **)REALLOC((void *)ht->objects, - ht->size*sizeof(void *), - new_size*sizeof(void *)); - if(!new_objects) - return 0; - - memset(new_objects + ht->size, 0, (new_size - ht->size)*sizeof(void *)); - - ht->size = new_size; - ht->objects = new_objects; - } - index = ht->filled; - handle = index + 1; /* check integer overflow */ if(!handle) return 0; + /* grow the table if necessary */ + if(!handle_table_resize(ht, index)) + return 0; + assert(!ht->objects[index]); ht->objects[index] = object; ++ht->filled; @@ -145,6 +162,36 @@ handle_table_add(struct handle_table *ht, } +unsigned +handle_table_set(struct handle_table *ht, + unsigned handle, + void *object) +{ + unsigned index; + + assert(ht); + assert(handle > 0); + assert(handle <= ht->size); + if(!handle || handle > ht->size) + return 0; + + assert(object); + if(!object) + return 0; + + index = handle - 1; + + /* grow the table if necessary */ + if(!handle_table_resize(ht, index)) + return 0; + + assert(!ht->objects[index]); + ht->objects[index] = object; + + return handle; +} + + void * handle_table_get(struct handle_table *ht, unsigned handle) diff --git a/src/gallium/auxiliary/util/u_handle_table.h b/src/gallium/auxiliary/util/u_handle_table.h index 51fc273865..a2f1f604ad 100644 --- a/src/gallium/auxiliary/util/u_handle_table.h +++ b/src/gallium/auxiliary/util/u_handle_table.h @@ -26,6 +26,7 @@ **************************************************************************/ /** + * @file * Generic handle table. * * @author José Fonseca <jrfonseca@tungstengraphics.com> @@ -42,6 +43,8 @@ extern "C" { /** * Abstract data type to map integer handles to objects. + * + * Also referred as "pointer array". */ struct handle_table; @@ -71,6 +74,14 @@ handle_table_add(struct handle_table *ht, void *object); /** + * Returns zero on failure (out of memory). + */ +unsigned +handle_table_set(struct handle_table *ht, + unsigned handle, + void *object); + +/** * Fetch an existing object. * * Returns NULL for an invalid handle. diff --git a/src/gallium/auxiliary/util/u_hash_table.c b/src/gallium/auxiliary/util/u_hash_table.c new file mode 100644 index 0000000000..ac2cb1b540 --- /dev/null +++ b/src/gallium/auxiliary/util/u_hash_table.c @@ -0,0 +1,199 @@ +/************************************************************************** + * + * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas. + * All Rights Reserved. + * + * 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, sub license, 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 NON-INFRINGEMENT. + * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS 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 + * General purpose hash table implementation. + * + * Just uses the cso_hash for now, but it might be better switch to a linear + * probing hash table implementation at some point -- as it is said they have + * better lookup and cache performance and it appears to be possible to write + * a lock-free implementation of such hash tables . + * + * @author José Fonseca <jrfonseca@tungstengraphics.com> + */ + + +#include "pipe/p_compiler.h" +#include "pipe/p_debug.h" +#include "pipe/p_util.h" + +#include "cso_cache/cso_hash.h" +#include "u_hash_table.h" + + +struct hash_table +{ + struct cso_hash *cso; + + /** Hash function */ + unsigned (*hash)(void *key); + + /** Compare two keys */ + int (*compare)(void *key1, void *key2); + + /* TODO: key, value destructors? */ +}; + + +struct hash_table_item +{ + void *key; + void *value; +}; + + +struct hash_table * +hash_table_create(unsigned (*hash)(void *key), + int (*compare)(void *key1, void *key2)) +{ + struct hash_table *ht; + + ht = MALLOC_STRUCT(hash_table); + if(!ht) + return NULL; + + ht->cso = cso_hash_create(); + if(!ht->cso) { + FREE(ht); + return NULL; + } + + ht->hash = hash; + ht->compare = compare; + + return ht; +} + + +static struct hash_table_item * +hash_table_find_item(struct hash_table *ht, + void *key, + unsigned key_hash) +{ + struct cso_hash_iter iter; + struct hash_table_item *item; + + iter = cso_hash_find(ht->cso, key_hash); + while (!cso_hash_iter_is_null(iter)) { + item = (struct hash_table_item *)cso_hash_iter_data(iter); + if (!ht->compare(item->key, key)) + return item; + iter = cso_hash_iter_next(iter); + } + + return NULL; +} + + +enum pipe_error +hash_table_set(struct hash_table *ht, + void *key, + void *value) +{ + unsigned key_hash; + struct hash_table_item *item; + + assert(ht); + + key_hash = ht->hash(key); + + item = hash_table_find_item(ht, key, key_hash); + if(item) { + /* TODO: key/value destruction? */ + item->value = value; + return PIPE_OK; + } + + item = MALLOC_STRUCT(hash_table_item); + if(!item) + return PIPE_ERROR_OUT_OF_MEMORY; + + item->key = key; + item->value = value; + + cso_hash_insert(ht->cso, key_hash, item); + /* FIXME: there is no OOM propagation in cso_hash */ + if(0) { + FREE(item); + return PIPE_ERROR_OUT_OF_MEMORY; + } + + return PIPE_OK; +} + + +void * +hash_table_get(struct hash_table *ht, + void *key) +{ + unsigned key_hash; + struct hash_table_item *item; + + assert(ht); + + key_hash = ht->hash(key); + + item = hash_table_find_item(ht, key, key_hash); + if(!item) + return NULL; + + return item->value; +} + + +void +hash_table_remove(struct hash_table *ht, + void *key) +{ + unsigned key_hash; + struct hash_table_item *item; + + assert(ht); + + key_hash = ht->hash(key); + + item = hash_table_find_item(ht, key, key_hash); + if(!item) + return; + + /* FIXME: cso_hash_take takes the first element of the collision list + * indiscriminately, so we can not take the item down. */ + item->value = NULL; +} + + +void +hash_table_destroy(struct hash_table *ht) +{ + assert(ht); + + cso_hash_delete(ht->cso); + + FREE(ht); +} + diff --git a/src/gallium/auxiliary/util/u_hash_table.h b/src/gallium/auxiliary/util/u_hash_table.h new file mode 100644 index 0000000000..d941f2c6b1 --- /dev/null +++ b/src/gallium/auxiliary/util/u_hash_table.h @@ -0,0 +1,86 @@ +/************************************************************************** + * + * Copyright 2008 Tungsten Graphics, Inc., Cedar Park, Texas. + * All Rights Reserved. + * + * 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, sub license, 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 NON-INFRINGEMENT. + * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS 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. + * + **************************************************************************/ + +/** + * General purpose hash table. + * + * @author José Fonseca <jrfonseca@tungstengraphics.com> + */ + +#ifndef U_HASH_TABLE_H_ +#define U_HASH_TABLE_H_ + + +#include "pipe/p_error.h" + + +#ifdef __cplusplus +extern "C" { +#endif + + +/** + * Generic purpose hash table. + */ +struct hash_table; + + +/** + * Create an hash table. + * + * @param hash hash function + * @param compare should return 0 for two equal keys. + */ +struct hash_table * +hash_table_create(unsigned (*hash)(void *key), + int (*compare)(void *key1, void *key2)); + + +enum pipe_error +hash_table_set(struct hash_table *ht, + void *key, + void *value); + +void * +hash_table_get(struct hash_table *ht, + void *key); + + +void +hash_table_remove(struct hash_table *ht, + void *key); + + +void +hash_table_destroy(struct hash_table *ht); + + +#ifdef __cplusplus +} +#endif + +#endif /* U_HASH_TABLE_H_ */ |