diff options
| -rw-r--r-- | Makefile.am | 4 | ||||
| -rw-r--r-- | README | 6 | ||||
| -rw-r--r-- | configure.ac | 3 | ||||
| -rw-r--r-- | fnv_hash.c | 57 | ||||
| -rw-r--r-- | fnv_hash.h | 34 | ||||
| -rw-r--r-- | tests/Makefile.am | 29 | ||||
| -rw-r--r-- | tests/insert_and_lookup.c | 56 | ||||
| -rw-r--r-- | tests/null_destroy.c | 38 |
8 files changed, 224 insertions, 3 deletions
diff --git a/Makefile.am b/Makefile.am index dde3fc3..b7bd6f2 100644 --- a/Makefile.am +++ b/Makefile.am @@ -20,11 +20,15 @@ AUTOMAKE_OPTIONS = foreign +SUBDIRS = . tests + AM_CFLAGS = $(WARN_CFLAGS) noinst_LTLIBRARIES = libhash_table.la libhash_table_la_SOURCES = \ + fnv_hash.c \ + fnv_hash.h \ hash_table.c \ hash_table.h @@ -40,6 +40,6 @@ Performance considerations: The solution here is to decide when the table is too full of deleted entries and recompute the data into a clean version of the hashtable. -In addition to the core hash_table implementation, a copy of the FNV-1a 32-bit -hash function is included for convenience for those that don't wish to analyze -hash functions on their own. +In addition to the core hash_table implementation, a sample of the FNV-1a +32-bit hash function is included for convenience for those that don't wish +to analyze hash functions on their own. diff --git a/configure.ac b/configure.ac index d6e9123..8b56d4b 100644 --- a/configure.ac +++ b/configure.ac @@ -34,6 +34,8 @@ AM_INIT_AUTOMAKE([dist-bzip2]) AC_PROG_LIBTOOL AC_PROG_CC +# Enable quiet compiles on automake 1.11. +m4_ifdef([AM_SILENT_RULES], [AM_SILENT_RULES([yes])]) WARN_CFLAGS="" @@ -47,4 +49,5 @@ AC_SUBST([WARN_CFLAGS]) AC_OUTPUT([ Makefile + tests/Makefile ]) diff --git a/fnv_hash.c b/fnv_hash.c new file mode 100644 index 0000000..171ec20 --- /dev/null +++ b/fnv_hash.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 <eric@anholt.net> + */ + +/* Quick FNV-1 hash implementation based on: + * http://www.isthe.com/chongo/tech/comp/fnv/ + * + * FNV-1 may not be the best hash out there -- Jenkins's lookup3 is supposed + * to be quite good, and it may beat FNV. But FNV has the advantage that it + * involves almost no code. + */ + +#include <string.h> +#include "fnv_hash.h" + +uint32_t +fnv1_hash_string(const void *key) +{ + uint32_t hash = 0; + const unsigned char *str = key; + + while (*str != 0) { + hash = hash * 0x01000193; + hash ^= *str; + str++; + } + + return hash; +} + +int +string_key_equals(const void *a, const void *b) +{ + return strcmp(a, b) == 0; +} diff --git a/fnv_hash.h b/fnv_hash.h new file mode 100644 index 0000000..08a3b51 --- /dev/null +++ b/fnv_hash.h @@ -0,0 +1,34 @@ +/* + * 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 <eric@anholt.net> + */ + +/* Quick FNV-1 hash implementation based on: + * http://www.isthe.com/chongo/tech/comp/fnv/ + */ + +#include <inttypes.h> + +uint32_t fnv1_hash_string(const void *key); +int string_key_equals(const void *a, const void *b); diff --git a/tests/Makefile.am b/tests/Makefile.am new file mode 100644 index 0000000..b59663a --- /dev/null +++ b/tests/Makefile.am @@ -0,0 +1,29 @@ +# 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_CFLAGS = $(WARN_CFLAGS) -I.. +LDADD = ../libhash_table.la + +TESTS = \ + insert_and_lookup \ + null_destroy \ + $() + +EXTRA_PROGRAMS = $(TESTS) diff --git a/tests/insert_and_lookup.c b/tests/insert_and_lookup.c new file mode 100644 index 0000000..2c287b6 --- /dev/null +++ b/tests/insert_and_lookup.c @@ -0,0 +1,56 @@ +/* + * 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 <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> +#include <assert.h> +#include "hash_table.h" +#include "fnv_hash.h" + +int +main(int argc, char **argv) +{ + struct hash_table *ht; + const char *str1 = "test1"; + const char *str2 = "test2"; + struct hash_entry *entry; + + ht = hash_table_create(fnv1_hash_string, string_key_equals); + + hash_table_insert(ht, str1, NULL); + hash_table_insert(ht, str2, NULL); + + entry = hash_table_search(ht, str1); + assert(strcmp(entry->key, str1) == 0); + + entry = hash_table_search(ht, str2); + assert(strcmp(entry->key, str2) == 0); + + hash_table_destroy(NULL, NULL); + + return 0; +} diff --git a/tests/null_destroy.c b/tests/null_destroy.c new file mode 100644 index 0000000..606d473 --- /dev/null +++ b/tests/null_destroy.c @@ -0,0 +1,38 @@ +/* + * 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 <eric@anholt.net> + */ + +#include <stdlib.h> +#include <stdio.h> +#include "hash_table.h" +#include "fnv_hash.h" + +int +main(int argc, char **argv) +{ + hash_table_destroy(NULL, NULL); + + return 0; +} |