From 6a364ced497e407ab3ffb2554d4ef2c78f801832 Mon Sep 17 00:00:00 2001 From: Karsten Blees Date: Thu, 14 Nov 2013 20:17:54 +0100 Subject: add a hashtable implementation that supports O(1) removal The existing hashtable implementation (in hash.[ch]) uses open addressing (i.e. resolve hash collisions by distributing entries across the table). Thus, removal is difficult to implement with less than O(n) complexity. Resolving collisions of entries with identical hashes (e.g. via chaining) is left to the client code. Add a hashtable implementation that supports O(1) removal and is slightly easier to use due to builtin entry chaining. Supports all basic operations init, free, get, add, remove and iteration. Also includes ready-to-use hash functions based on the public domain FNV-1 algorithm (http://www.isthe.com/chongo/tech/comp/fnv). The per-entry data structure (hashmap_entry) is piggybacked in front of the client's data structure to save memory. See test-hashmap.c for usage examples. The hashtable is resized by a factor of four when 80% full. With these settings, average memory consumption is about 2/3 of hash.[ch], and insertion is about twice as fast due to less frequent resizing. Lookups are also slightly faster, because entries are strictly confined to their bucket (i.e. no data of other buckets needs to be traversed). Signed-off-by: Karsten Blees Signed-off-by: Junio C Hamano --- Makefile | 3 +++ 1 file changed, 3 insertions(+) (limited to 'Makefile') diff --git a/Makefile b/Makefile index 4fde227f1..d8d3d6705 100644 --- a/Makefile +++ b/Makefile @@ -557,6 +557,7 @@ TEST_PROGRAMS_NEED_X += test-date TEST_PROGRAMS_NEED_X += test-delta TEST_PROGRAMS_NEED_X += test-dump-cache-tree TEST_PROGRAMS_NEED_X += test-genrandom +TEST_PROGRAMS_NEED_X += test-hashmap TEST_PROGRAMS_NEED_X += test-index-version TEST_PROGRAMS_NEED_X += test-line-buffer TEST_PROGRAMS_NEED_X += test-match-trees @@ -677,6 +678,7 @@ LIB_H += gpg-interface.h LIB_H += graph.h LIB_H += grep.h LIB_H += hash.h +LIB_H += hashmap.h LIB_H += help.h LIB_H += http.h LIB_H += kwset.h @@ -808,6 +810,7 @@ LIB_OBJS += gpg-interface.o LIB_OBJS += graph.o LIB_OBJS += grep.o LIB_OBJS += hash.o +LIB_OBJS += hashmap.o LIB_OBJS += help.o LIB_OBJS += hex.o LIB_OBJS += ident.o -- cgit v1.2.1 From efc684245b81ae0fb8f0afbd06dc1c3101c4e5a0 Mon Sep 17 00:00:00 2001 From: Karsten Blees Date: Thu, 14 Nov 2013 20:23:12 +0100 Subject: remove old hash.[ch] implementation Signed-off-by: Karsten Blees Signed-off-by: Junio C Hamano --- Makefile | 2 -- 1 file changed, 2 deletions(-) (limited to 'Makefile') diff --git a/Makefile b/Makefile index d8d3d6705..f495dd4c1 100644 --- a/Makefile +++ b/Makefile @@ -677,7 +677,6 @@ LIB_H += git-compat-util.h LIB_H += gpg-interface.h LIB_H += graph.h LIB_H += grep.h -LIB_H += hash.h LIB_H += hashmap.h LIB_H += help.h LIB_H += http.h @@ -809,7 +808,6 @@ LIB_OBJS += gettext.o LIB_OBJS += gpg-interface.o LIB_OBJS += graph.o LIB_OBJS += grep.o -LIB_OBJS += hash.o LIB_OBJS += hashmap.o LIB_OBJS += help.o LIB_OBJS += hex.o -- cgit v1.2.1