From 633a692225fcdad15ce84776a7a18d7d008d52b3 Mon Sep 17 00:00:00 2001 From: Carl Worth Date: Mon, 10 May 2010 13:36:26 -0700 Subject: [PATCH] Add hash table implementation from glsl2 project. The preprocessor here is intended to become part of the glsl2 codebase eventually anyway. --- Makefile | 2 +- hash_table.c | 159 ++++++++++++++++++++++++++++++ hash_table.h | 125 ++++++++++++++++++++++++ main/imports.h | 6 ++ main/simple_list.h | 235 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 526 insertions(+), 1 deletion(-) create mode 100644 hash_table.c create mode 100644 hash_table.h create mode 100644 main/imports.h create mode 100644 main/simple_list.h diff --git a/Makefile b/Makefile index d0ca78de74c..0af7e05d1b2 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ override CFLAGS += -Wall -Wextra -Wwrite-strings -Wswitch-enum -Wno-unused -glcpp: glcpp.o glcpp-lex.o glcpp-parse.o +glcpp: glcpp.o glcpp-lex.o glcpp-parse.o hash_table.o %.c %.h: %.y bison --defines=$*.h --output=$*.c $^ diff --git a/hash_table.c b/hash_table.c new file mode 100644 index 00000000000..e89a2564d76 --- /dev/null +++ b/hash_table.c @@ -0,0 +1,159 @@ +/* + * 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 "main/imports.h" +#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 = _mesa_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_dtor(struct hash_table *ht) +{ + hash_table_clear(ht); + _mesa_free(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); + _mesa_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 = _mesa_calloc(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; +} diff --git a/hash_table.h b/hash_table.h new file mode 100644 index 00000000000..b9dd343dee9 --- /dev/null +++ b/hash_table.h @@ -0,0 +1,125 @@ +/* + * 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 + +#ifdef __cplusplus +extern "C" { +#endif + +#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); + + +/** + * 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 + * + * \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) + +#ifdef __cplusplus +}; +#endif + +#endif /* HASH_TABLE_H */ diff --git a/main/imports.h b/main/imports.h new file mode 100644 index 00000000000..d2197342c04 --- /dev/null +++ b/main/imports.h @@ -0,0 +1,6 @@ +#include +#include + +#define _mesa_malloc(x) malloc(x) +#define _mesa_free(x) free(x) +#define _mesa_calloc(x) calloc(1,x) diff --git a/main/simple_list.h b/main/simple_list.h new file mode 100644 index 00000000000..5ef39e14cc6 --- /dev/null +++ b/main/simple_list.h @@ -0,0 +1,235 @@ +/** + * \file simple_list.h + * Simple macros for type-safe, intrusive lists. + * + * Intended to work with a list sentinal which is created as an empty + * list. Insert & delete are O(1). + * + * \author + * (C) 1997, Keith Whitwell + */ + +/* + * Mesa 3-D graphics library + * Version: 3.5 + * + * Copyright (C) 1999-2001 Brian Paul 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, 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 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 + * BRIAN PAUL 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. + */ + + +#ifndef _SIMPLE_LIST_H +#define _SIMPLE_LIST_H + +struct simple_node { + struct simple_node *next; + struct simple_node *prev; +}; + +/** + * Remove an element from list. + * + * \param elem element to remove. + */ +#define remove_from_list(elem) \ +do { \ + (elem)->next->prev = (elem)->prev; \ + (elem)->prev->next = (elem)->next; \ +} while (0) + +/** + * Insert an element to the list head. + * + * \param list list. + * \param elem element to insert. + */ +#define insert_at_head(list, elem) \ +do { \ + (elem)->prev = list; \ + (elem)->next = (list)->next; \ + (list)->next->prev = elem; \ + (list)->next = elem; \ +} while(0) + +/** + * Insert an element to the list tail. + * + * \param list list. + * \param elem element to insert. + */ +#define insert_at_tail(list, elem) \ +do { \ + (elem)->next = list; \ + (elem)->prev = (list)->prev; \ + (list)->prev->next = elem; \ + (list)->prev = elem; \ +} while(0) + +/** + * Move an element to the list head. + * + * \param list list. + * \param elem element to move. + */ +#define move_to_head(list, elem) \ +do { \ + remove_from_list(elem); \ + insert_at_head(list, elem); \ +} while (0) + +/** + * Move an element to the list tail. + * + * \param list list. + * \param elem element to move. + */ +#define move_to_tail(list, elem) \ +do { \ + remove_from_list(elem); \ + insert_at_tail(list, elem); \ +} while (0) + +/** + * Consatinate a cyclic list to a list + * + * Appends the sequence of nodes starting with \c tail to the list \c head. + * A "cyclic list" is a list that does not have a sentinal node. This means + * that the data pointed to by \c tail is an actual node, not a dataless + * sentinal. Note that if \c tail constist of a single node, this macro + * behaves identically to \c insert_at_tail + * + * \param head Head of the list to be appended to. This may or may not + * be a cyclic list. + * \param tail Head of the cyclic list to be appended to \c head. + * \param temp Temporary \c simple_list used by the macro + * + * \sa insert_at_tail + */ +#define concat_list_and_cycle(head, tail, temp) \ +do { \ + (head)->prev->next = (tail); \ + (tail)->prev->next = (head); \ + (temp) = (head)->prev; \ + (head)->prev = (tail)->prev; \ + (tail)->prev = (temp); \ +} while (0) + +#define concat_list(head, next_list) \ +do { \ + (next_list)->next->prev = (head)->prev; \ + (next_list)->prev->next = (head); \ + (head)->prev->next = (next_list)->next; \ + (head)->prev = (next_list)->prev; \ +} while (0) + +/** + * Make a empty list empty. + * + * \param sentinal list (sentinal element). + */ +#define make_empty_list(sentinal) \ +do { \ + (sentinal)->next = sentinal; \ + (sentinal)->prev = sentinal; \ +} while (0) + +/** + * Get list first element. + * + * \param list list. + * + * \return pointer to first element. + */ +#define first_elem(list) ((list)->next) + +/** + * Get list last element. + * + * \param list list. + * + * \return pointer to last element. + */ +#define last_elem(list) ((list)->prev) + +/** + * Get next element. + * + * \param elem element. + * + * \return pointer to next element. + */ +#define next_elem(elem) ((elem)->next) + +/** + * Get previous element. + * + * \param elem element. + * + * \return pointer to previous element. + */ +#define prev_elem(elem) ((elem)->prev) + +/** + * Test whether element is at end of the list. + * + * \param list list. + * \param elem element. + * + * \return non-zero if element is at end of list, or zero otherwise. + */ +#define at_end(list, elem) ((elem) == (list)) + +/** + * Test if a list is empty. + * + * \param list list. + * + * \return non-zero if list empty, or zero otherwise. + */ +#define is_empty_list(list) ((list)->next == (list)) + +/** + * Walk through the elements of a list. + * + * \param ptr pointer to the current element. + * \param list list. + * + * \note It should be followed by a { } block or a single statement, as in a \c + * for loop. + */ +#define foreach(ptr, list) \ + for( ptr=(list)->next ; ptr!=list ; ptr=(ptr)->next ) + +/** + * Walk through the elements of a list. + * + * Same as #foreach but lets you unlink the current value during a list + * traversal. Useful for freeing a list, element by element. + * + * \param ptr pointer to the current element. + * \param t temporary pointer. + * \param list list. + * + * \note It should be followed by a { } block or a single statement, as in a \c + * for loop. + */ +#define foreach_s(ptr, t, list) \ + for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next) + +#endif -- 2.30.2