]> git.proxmox.com Git - libgit2.git/commit
Rewrite git_hashtable internals
authorVicent Marti <tanoku@gmail.com>
Tue, 22 Feb 2011 19:59:36 +0000 (21:59 +0200)
committerVicent Marti <tanoku@gmail.com>
Tue, 22 Feb 2011 19:59:36 +0000 (21:59 +0200)
commitfc658755bf980170cf5a497870155a9fc97151cb
tree1e04116b1c9ca8234c4aacbba90d182c470081b7
parent4378e8d470abae5e9e8f32f98869516c8b86b191
Rewrite git_hashtable internals

The old hash table with chained buckets has been replaced by a new one
using Cuckoo hashing, which offers guaranteed constant lookup times.
This should improve speeds on most use cases, since hash tables in
libgit2 are usually used as caches where the objects are stored once and
queried several times.

The Cuckoo hash implementation is based off the one in the Basekit
library [1] for the IO language, but rewritten to support an arbritrary
number of hashes. We currently use 3 to maximize the usage of the nodes pool.

[1]: https://github.com/stevedekorte/basekit/blob/master/source/CHash.c

Signed-off-by: Vicent Marti <tanoku@gmail.com>
src/hashtable.c
src/hashtable.h
src/refs.c
src/repository.c
src/revwalk.c
tests/t07-hashtable.c