| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
At least on this developer's MacOSX (Snow Leopard, gcc-4.2.1), GCC
prints a warning that 'hash' may be used uninitialized when
compiling test-hashmap that 'hash' may be used uninitialized (but
GCC 4.6.3 on this developer's Ubuntu server does not report this
problem).
The old compiler is wrong, of course, as the switch (method & 3)
statement already handles all the possible cases, but that does not
help in a scenario where it is hard or impossible to upgrade to a
newer compiler (e.g. being stuck on an older MacOSX and having to
rely on Xcode).
So let's just initialize the variable and be done with it, it is
hardly a crucial part of the code because it is only used by the
test suite and invisible to the end users.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
|
|
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 <blees@dcon.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
|
