[PATCH/RFC 0/5] New hash table implementation

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