[Mesa-dev] [PATCH 3/5] mesa: Import a copy of the open-addressing hash table code I wrote.
Brian Paul
brianp at vmware.com
Sun Nov 4 15:38:57 PST 2012
On 10/25/2012 10:13 AM, Eric Anholt 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. The
> hash_table.c file unfortunately lives in program/ still to avoid confusion
> with automake's dependency files that would otherwise require a make distclean
> across this change.
> ---
> configure.ac | 1 +
> src/mesa/main/hash_table.h | 105 +++++
> src/mesa/main/tests/Makefile.am | 2 +
> src/mesa/main/tests/hash_table/.gitignore | 10 +
> src/mesa/main/tests/hash_table/Makefile.am | 42 ++
> src/mesa/main/tests/hash_table/delete_and_lookup.c | 74 ++++
> src/mesa/main/tests/hash_table/delete_management.c | 88 ++++
> src/mesa/main/tests/hash_table/destroy_callback.c | 66 +++
> src/mesa/main/tests/hash_table/insert_and_lookup.c | 57 +++
> src/mesa/main/tests/hash_table/insert_many.c | 72 ++++
> src/mesa/main/tests/hash_table/null_destroy.c | 37 ++
> src/mesa/main/tests/hash_table/random_entry.c | 88 ++++
> src/mesa/main/tests/hash_table/remove_null.c | 45 ++
> src/mesa/main/tests/hash_table/replacement.c | 64 +++
> src/mesa/program/hash_table.c | 431 ++++++++++++++++++++
> src/mesa/sources.mak | 1 +
[I only skimmed the test programs]
> diff --git a/src/mesa/program/hash_table.c b/src/mesa/program/hash_table.c
> new file mode 100644
> index 0000000..ba49437
> --- /dev/null
> +++ b/src/mesa/program/hash_table.c
> @@ -0,0 +1,431 @@
> +/*
> + * Copyright © 2009,2012 Intel Corporation
> + * Copyright © 1988-2004 Keith Packard and Bart Massey.
> + *
> + * 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.
> + *
> + * Except as contained in this notice, the names of the authors
> + * or their institutions shall not be used in advertising or
> + * otherwise to promote the sale, use or other dealings in this
> + * Software without prior written authorization from the
> + * authors.
> + *
> + * Authors:
> + * Eric Anholt<eric at anholt.net>
> + * Keith Packard<keithp at keithp.com>
> + */
> +
> +/**
> + * Implements an open-addressing, linear-reprobing hash table.
> + *
> + * For more information, see:
> + *
> + * http://cgit.freedesktop.org/~anholt/hash_table/tree/README
> + */
> +
> +#include<stdlib.h>
> +#include<string.h>
> +
> +#include "main/hash_table.h"
> +#include "ralloc.h"
> +
> +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0]))
> +
> +uint32_t deleted_key_value;
> +
> +/**
> + * From Knuth -- a good choice for hash/rehash values is p, p-2 where
> + * p and p-2 are both prime. These tables are sized to have an extra 10%
> + * free to avoid exponential performance degradation as the hash table fills
> + */
> +static const struct {
> + uint32_t max_entries, size, rehash;
> +} hash_sizes[] = {
> + { 2, 5, 3 },
> + { 4, 7, 5 },
> + { 8, 13, 11 },
> + { 16, 19, 17 },
> + { 32, 43, 41 },
> + { 64, 73, 71 },
> + { 128, 151, 149 },
> + { 256, 283, 281 },
> + { 512, 571, 569 },
> + { 1024, 1153, 1151 },
> + { 2048, 2269, 2267 },
> + { 4096, 4519, 4517 },
> + { 8192, 9013, 9011 },
> + { 16384, 18043, 18041 },
> + { 32768, 36109, 36107 },
> + { 65536, 72091, 72089 },
> + { 131072, 144409, 144407 },
> + { 262144, 288361, 288359 },
> + { 524288, 576883, 576881 },
> + { 1048576, 1153459, 1153457 },
> + { 2097152, 2307163, 2307161 },
> + { 4194304, 4613893, 4613891 },
> + { 8388608, 9227641, 9227639 },
> + { 16777216, 18455029, 18455027 },
> + { 33554432, 36911011, 36911009 },
> + { 67108864, 73819861, 73819859 },
> + { 134217728, 147639589, 147639587 },
> + { 268435456, 295279081, 295279079 },
> + { 536870912, 590559793, 590559791 },
> + { 1073741824, 1181116273, 1181116271},
> + { 2147483648ul, 2362232233ul, 2362232231ul}
> +};
> +
> +static int
> +entry_is_free(struct hash_entry *entry)
I'd const-qualify the parameter here (and several below) but it's not
a huge deal.
> +{
> + return entry->key == NULL;
> +}
> +
> +static int
> +entry_is_deleted(struct hash_table *ht, struct hash_entry *entry)
> +{
> + return entry->key == ht->deleted_key;
> +}
> +
> +static int
> +entry_is_present(struct hash_table *ht, struct hash_entry *entry)
> +{
> + return entry->key != NULL&& entry->key != ht->deleted_key;
> +}
> +
[...]
> +struct hash_entry *
> +_mesa_hash_table_random_entry(struct hash_table *ht,
> + bool (*predicate)(struct hash_entry *entry))
Just curious, what is this function used for? Just testing?
[...]
> diff --git a/src/mesa/sources.mak b/src/mesa/sources.mak
> index d51adf5..13ba16a 100644
> --- a/src/mesa/sources.mak
> +++ b/src/mesa/sources.mak
> @@ -249,6 +249,7 @@ STATETRACKER_FILES = \
> PROGRAM_FILES = \
> $(SRCDIR)program/arbprogparse.c \
> $(SRCDIR)program/chaining_hash_table.c \
> + $(SRCDIR)program/hash_table.c \
> $(SRCDIR)program/program.c \
> $(SRCDIR)program/program_parse_extra.c \
> $(SRCDIR)program/prog_cache.c \
Update the SConscript file too?
More information about the mesa-dev
mailing list