Also here:


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 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/ | 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/
 create mode 100644 test-hashmap.c


To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to
More majordomo info at

Reply via email to