On Mon, Oct 28, 2013 at 4:48 PM, Junio C Hamano <gits...@pobox.com> wrote:
>> jk/pack-bitmap adds khash.h, which from a first glance looks like yet
>> another hash table implementation. I was just wondering if kb's new
>> hash tables can cover the need of pack-bitmap.c too so we can remove
>> khash.h later..
> Good thinking ;-).

We use the khash tables to map:

    - sha1 (const char *) to (void *)
    - sha1 (const char *) to int

The new `hashmap.c` covers the first case quite well (albeit slightly
more verbosely than I'd like), but in the second case it doesn't quite
work. Since the new hash needs to embed the "struct hashmap_entry" on
all its values (to allow for separate chaining), having it map to
`int` keys requires a struct like this:

    struct sha1_position {
        struct hashmap_entry {
            struct hashmap_entry *next;
            unsigned int hash;
        int position;

khash on the other hand is capable of storing the position values as
part of the hash table itself (i.e. `int **buckets`), and saves us
from thousands of bytes of allocations + indirection.

I am not sure whether the consistency of having a single hash map
warrants the performance and memory hits when operating on the
extended index.

Please advice.

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

Reply via email to