diff options
author | Kenneth Graunke <[email protected]> | 2014-02-25 01:08:45 -0800 |
---|---|---|
committer | Jason Ekstrand <[email protected]> | 2014-08-04 11:07:05 -0700 |
commit | 72e55bb6888ff4d6b69b10d9c58573e4c3d492ec (patch) | |
tree | 9084fd3c939f545bbc0d6a214564755bca9745cb /src/util/tests | |
parent | 1e0da6233be6e5fb0143615d5e3d3642ddb7964f (diff) |
util: Move the open-addressing linear-probing hash_table to src/util.
This hash table is used in core Mesa, the GLSL compiler, and the i965
driver, which makes it a good candidate for the new src/util module.
It's much faster than program/hash_table.[ch] (see commit 6991c2922f5
for data), and José's u_hash_table.c has a comment saying Gallium should
probably consider switching to a linear probing hash table at some point.
So this seems like the best candidate for a shared data structure.
Signed-off-by: Kenneth Graunke <[email protected]>
v2 (Jason Ekstrand): Pick up another hash_table use and patch up scons
Signed-off-by: Jason Ekstrand <[email protected]>
Reviewed-by: Marek Olšák <[email protected]>
Diffstat (limited to 'src/util/tests')
-rw-r--r-- | src/util/tests/Makefile.am | 2 | ||||
-rw-r--r-- | src/util/tests/hash_table/.gitignore | 10 | ||||
-rw-r--r-- | src/util/tests/hash_table/Makefile.am | 46 | ||||
-rw-r--r-- | src/util/tests/hash_table/collision.c | 80 | ||||
-rw-r--r-- | src/util/tests/hash_table/delete_and_lookup.c | 74 | ||||
-rw-r--r-- | src/util/tests/hash_table/delete_management.c | 88 | ||||
-rw-r--r-- | src/util/tests/hash_table/destroy_callback.c | 66 | ||||
-rw-r--r-- | src/util/tests/hash_table/insert_and_lookup.c | 57 | ||||
-rw-r--r-- | src/util/tests/hash_table/insert_many.c | 72 | ||||
-rw-r--r-- | src/util/tests/hash_table/null_destroy.c | 37 | ||||
-rw-r--r-- | src/util/tests/hash_table/random_entry.c | 88 | ||||
-rw-r--r-- | src/util/tests/hash_table/remove_null.c | 45 | ||||
-rw-r--r-- | src/util/tests/hash_table/replacement.c | 64 |
13 files changed, 729 insertions, 0 deletions
diff --git a/src/util/tests/Makefile.am b/src/util/tests/Makefile.am index a2b54982ff1..8ec8c3aa55c 100644 --- a/src/util/tests/Makefile.am +++ b/src/util/tests/Makefile.am @@ -19,6 +19,8 @@ # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS # IN THE SOFTWARE. +SUBDIRS = hash_table + AM_CFLAGS = \ $(PTHREAD_CFLAGS) AM_CPPFLAGS = \ diff --git a/src/util/tests/hash_table/.gitignore b/src/util/tests/hash_table/.gitignore new file mode 100644 index 00000000000..1b9aaf4a27e --- /dev/null +++ b/src/util/tests/hash_table/.gitignore @@ -0,0 +1,10 @@ +collision +delete_and_lookup +delete_management +destroy_callback +insert_and_lookup +insert_many +null_destroy +random_entry +remove_null +replacement diff --git a/src/util/tests/hash_table/Makefile.am b/src/util/tests/hash_table/Makefile.am new file mode 100644 index 00000000000..55cc0b72335 --- /dev/null +++ b/src/util/tests/hash_table/Makefile.am @@ -0,0 +1,46 @@ +# Copyright © 2009 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 +# on 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 +# ADAM JACKSON 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. + +AM_CPPFLAGS = \ + -I$(top_srcdir)/include \ + -I$(top_srcdir)/src/util \ + -I$(top_srcdir)/src/mesa \ + -I$(top_srcdir)/src/mesa/main \ + $(DEFINES) $(INCLUDE_DIRS) + +LDADD = \ + $(top_builddir)/src/mesa/libmesa.la \ + $(PTHREAD_LIBS) \ + $(DLOPEN_LIBS) + +TESTS = \ + collision \ + delete_and_lookup \ + delete_management \ + destroy_callback \ + insert_and_lookup \ + insert_many \ + null_destroy \ + random_entry \ + remove_null \ + replacement \ + $() + +EXTRA_PROGRAMS = $(TESTS) diff --git a/src/util/tests/hash_table/collision.c b/src/util/tests/hash_table/collision.c new file mode 100644 index 00000000000..9174c396151 --- /dev/null +++ b/src/util/tests/hash_table/collision.c @@ -0,0 +1,80 @@ +/* + * Copyright © 2012 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + const char *str1 = "test1"; + const char *str2 = "test2"; + struct hash_entry *entry1, *entry2; + uint32_t bad_hash = 5; + int i; + + ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal); + + _mesa_hash_table_insert(ht, bad_hash, str1, NULL); + _mesa_hash_table_insert(ht, bad_hash, str2, NULL); + + entry1 = _mesa_hash_table_search(ht, bad_hash, str1); + assert(entry1->key == str1); + + entry2 = _mesa_hash_table_search(ht, bad_hash, str2); + assert(entry2->key == str2); + + /* Check that we can still find #1 after inserting #2 */ + entry1 = _mesa_hash_table_search(ht, bad_hash, str1); + assert(entry1->key == str1); + + /* Remove the collided entry and look again. */ + _mesa_hash_table_remove(ht, entry1); + entry2 = _mesa_hash_table_search(ht, bad_hash, str2); + assert(entry2->key == str2); + + /* Put str1 back, then spam junk into the table to force a + * resize and make sure we can still find them both. + */ + _mesa_hash_table_insert(ht, bad_hash, str1, NULL); + for (i = 0; i < 100; i++) { + char *key = malloc(10); + sprintf(key, "spam%d", i); + _mesa_hash_table_insert(ht, _mesa_hash_string(key), key, NULL); + } + entry1 = _mesa_hash_table_search(ht, bad_hash, str1); + assert(entry1->key == str1); + entry2 = _mesa_hash_table_search(ht, bad_hash, str2); + assert(entry2->key == str2); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/delete_and_lookup.c b/src/util/tests/hash_table/delete_and_lookup.c new file mode 100644 index 00000000000..fc886ff4f4e --- /dev/null +++ b/src/util/tests/hash_table/delete_and_lookup.c @@ -0,0 +1,74 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +/* Return collisions, so we can test the deletion behavior for chained + * objects. + */ +static uint32_t +badhash(const void *key) +{ + return 1; +} + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + const char *str1 = "test1"; + const char *str2 = "test2"; + uint32_t hash_str1 = badhash(str1); + uint32_t hash_str2 = badhash(str2); + struct hash_entry *entry; + + ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal); + + _mesa_hash_table_insert(ht, hash_str1, str1, NULL); + _mesa_hash_table_insert(ht, hash_str2, str2, NULL); + + entry = _mesa_hash_table_search(ht, hash_str2, str2); + assert(strcmp(entry->key, str2) == 0); + + entry = _mesa_hash_table_search(ht, hash_str1, str1); + assert(strcmp(entry->key, str1) == 0); + + _mesa_hash_table_remove(ht, entry); + + entry = _mesa_hash_table_search(ht, hash_str1, str1); + assert(entry == NULL); + + entry = _mesa_hash_table_search(ht, hash_str2, str2); + assert(strcmp(entry->key, str2) == 0); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/delete_management.c b/src/util/tests/hash_table/delete_management.c new file mode 100644 index 00000000000..b8d764019f4 --- /dev/null +++ b/src/util/tests/hash_table/delete_management.c @@ -0,0 +1,88 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +static uint32_t +key_value(const void *key) +{ + return *(const uint32_t *)key; +} + +static bool +uint32_t_key_equals(const void *a, const void *b) +{ + return key_value(a) == key_value(b); +} + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + struct hash_entry *entry; + int size = 10000; + uint32_t keys[size]; + uint32_t i; + + ht = _mesa_hash_table_create(NULL, uint32_t_key_equals); + + for (i = 0; i < size; i++) { + keys[i] = i; + + _mesa_hash_table_insert(ht, i, keys + i, NULL); + + if (i >= 100) { + uint32_t delete_value = i - 100; + entry = _mesa_hash_table_search(ht, delete_value, + &delete_value); + _mesa_hash_table_remove(ht, entry); + } + } + + /* Make sure that all our entries were present at the end. */ + for (i = size - 100; i < size; i++) { + entry = _mesa_hash_table_search(ht, i, keys + i); + assert(entry); + assert(key_value(entry->key) == i); + } + + /* Make sure that no extra entries got in */ + for (entry = _mesa_hash_table_next_entry(ht, NULL); + entry != NULL; + entry = _mesa_hash_table_next_entry(ht, entry)) { + assert(key_value(entry->key) >= size - 100 && + key_value(entry->key) < size); + } + assert(ht->entries == 100); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/destroy_callback.c b/src/util/tests/hash_table/destroy_callback.c new file mode 100644 index 00000000000..dce2b333234 --- /dev/null +++ b/src/util/tests/hash_table/destroy_callback.c @@ -0,0 +1,66 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +static const char *str1 = "test1"; +static const char *str2 = "test2"; +static int delete_str1 = 0; +static int delete_str2 = 0; + +static void +delete_callback(struct hash_entry *entry) +{ + if (strcmp(entry->key, str1) == 0) + delete_str1 = 1; + else if (strcmp(entry->key, str2) == 0) + delete_str2 = 1; + else + abort(); +} + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + uint32_t hash_str1 = _mesa_hash_string(str1); + uint32_t hash_str2 = _mesa_hash_string(str2); + + ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal); + + _mesa_hash_table_insert(ht, hash_str1, str1, NULL); + _mesa_hash_table_insert(ht, hash_str2, str2, NULL); + + _mesa_hash_table_destroy(ht, delete_callback); + + assert(delete_str1 && delete_str2); + + return 0; +} diff --git a/src/util/tests/hash_table/insert_and_lookup.c b/src/util/tests/hash_table/insert_and_lookup.c new file mode 100644 index 00000000000..402f3fd4002 --- /dev/null +++ b/src/util/tests/hash_table/insert_and_lookup.c @@ -0,0 +1,57 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + const char *str1 = "test1"; + const char *str2 = "test2"; + uint32_t hash_str1 = _mesa_hash_string(str1); + uint32_t hash_str2 = _mesa_hash_string(str2); + struct hash_entry *entry; + + ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal); + + _mesa_hash_table_insert(ht, hash_str1, str1, NULL); + _mesa_hash_table_insert(ht, hash_str2, str2, NULL); + + entry = _mesa_hash_table_search(ht, hash_str1, str1); + assert(strcmp(entry->key, str1) == 0); + + entry = _mesa_hash_table_search(ht, hash_str2, str2); + assert(strcmp(entry->key, str2) == 0); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/insert_many.c b/src/util/tests/hash_table/insert_many.c new file mode 100644 index 00000000000..b2122dcf96c --- /dev/null +++ b/src/util/tests/hash_table/insert_many.c @@ -0,0 +1,72 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +static uint32_t +key_value(const void *key) +{ + return *(const uint32_t *)key; +} + +static bool +uint32_t_key_equals(const void *a, const void *b) +{ + return key_value(a) == key_value(b); +} + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + struct hash_entry *entry; + int size = 10000; + uint32_t keys[size]; + uint32_t i; + + ht = _mesa_hash_table_create(NULL, uint32_t_key_equals); + + for (i = 0; i < size; i++) { + keys[i] = i; + + _mesa_hash_table_insert(ht, i, keys + i, NULL); + } + + for (i = 0; i < size; i++) { + entry = _mesa_hash_table_search(ht, i, keys + i); + assert(entry); + assert(key_value(entry->key) == i); + } + assert(ht->entries == size); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/null_destroy.c b/src/util/tests/hash_table/null_destroy.c new file mode 100644 index 00000000000..3833464f454 --- /dev/null +++ b/src/util/tests/hash_table/null_destroy.c @@ -0,0 +1,37 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include "hash_table.h" + +int +main(int argc, char **argv) +{ + _mesa_hash_table_destroy(NULL, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/random_entry.c b/src/util/tests/hash_table/random_entry.c new file mode 100644 index 00000000000..22cafa7e857 --- /dev/null +++ b/src/util/tests/hash_table/random_entry.c @@ -0,0 +1,88 @@ +/* + * Copyright © 2009 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +static uint32_t +key_value(const void *key) +{ + return *(const uint32_t *)key; +} + +static bool +uint32_t_key_equals(const void *a, const void *b) +{ + return key_value(a) == key_value(b); +} + +static bool +uint32_t_key_is_even(struct hash_entry *entry) +{ + return (key_value(entry->key) & 1) == 0; +} + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + struct hash_entry *entry; + int size = 10000; + uint32_t keys[size]; + uint32_t i, random_value; + + ht = _mesa_hash_table_create(NULL, uint32_t_key_equals); + + for (i = 0; i < size; i++) { + keys[i] = i; + + _mesa_hash_table_insert(ht, i, keys + i, NULL); + } + + /* Test the no-predicate case. */ + entry = _mesa_hash_table_random_entry(ht, NULL); + assert(entry); + + /* Check that we're getting different entries and that the predicate + * works. + */ + for (i = 0; i < 100; i++) { + entry = _mesa_hash_table_random_entry(ht, uint32_t_key_is_even); + assert(entry); + assert((key_value(entry->key) & 1) == 0); + if (i == 0 || key_value(entry->key) != random_value) + break; + random_value = key_value(entry->key); + } + assert(i != 100); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/remove_null.c b/src/util/tests/hash_table/remove_null.c new file mode 100644 index 00000000000..90fb784ac40 --- /dev/null +++ b/src/util/tests/hash_table/remove_null.c @@ -0,0 +1,45 @@ +/* + * Copyright © 2011 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + + ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal); + + _mesa_hash_table_remove(ht, NULL); + + _mesa_hash_table_destroy(ht, NULL); + + return 0; +} diff --git a/src/util/tests/hash_table/replacement.c b/src/util/tests/hash_table/replacement.c new file mode 100644 index 00000000000..387cfc0fd94 --- /dev/null +++ b/src/util/tests/hash_table/replacement.c @@ -0,0 +1,64 @@ +/* + * Copyright © 2011 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. + * + * Authors: + * Eric Anholt <[email protected]> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + char *str1 = strdup("test1"); + char *str2 = strdup("test1"); + uint32_t hash_str1 = _mesa_hash_string(str1); + uint32_t hash_str2 = _mesa_hash_string(str2); + struct hash_entry *entry; + + assert(str1 != str2); + + ht = _mesa_hash_table_create(NULL, _mesa_key_string_equal); + + _mesa_hash_table_insert(ht, hash_str1, str1, str1); + _mesa_hash_table_insert(ht, hash_str2, str2, str2); + + entry = _mesa_hash_table_search(ht, hash_str1, str1); + assert(entry); + assert(entry->data == str2); + + _mesa_hash_table_remove(ht, entry); + + entry = _mesa_hash_table_search(ht, hash_str1, str1); + assert(!entry); + + _mesa_hash_table_destroy(ht, NULL); + free(str1); + free(str2); + + return 0; +} |