Also here: https://github.com/kblees/git/tree/kb/hashmap
Hi, this is a spin-off of my (very slowly progressing) msysgit fscache project. I needed to remove things from the hash table, which cannot be implemented efficiently in hash.[ch]. So I wrote hasmap.[ch], with these features: - O(1) remove - builtin entry chaining - ready-to-use FNV-1 hash functions - unit test - additions are ~twice as fast - uses less memory Patches 2 and 5 convert existing uses of hash.[ch] to hashmap.[ch]. Patches 3 and 4 are useful optimizations of their own. I haven't found the time to tackle name-hash.c yet, this is where remove() could come into play (to replace the CE_UNHASHED flag). Karsten Karsten Blees (5): add a hashtable implementation that supports O(1) removal buitin/describe.c: use new hash map implementation diffcore-rename.c: move code around to prepare for the next patch diffcore-rename.c: simplify finding exact renames diffcore-rename.c: use new hash map implementation Makefile | 3 + builtin/describe.c | 53 +++++------ diffcore-rename.c | 185 +++++++++++++------------------------- hashmap.c | 210 +++++++++++++++++++++++++++++++++++++++++++ hashmap.h | 200 +++++++++++++++++++++++++++++++++++++++++ t/t0011-hashmap.sh | 236 ++++++++++++++++++++++++++++++++++++++++++++++++ test-hashmap.c | 258 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 995 insertions(+), 150 deletions(-) create mode 100644 hashmap.c create mode 100644 hashmap.h create mode 100755 t/t0011-hashmap.sh create mode 100644 test-hashmap.c -- 1.8.4.8243.gbcbdefd -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
