Subject: Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal

From: Junio C Hamano <[email-masked]>
Date: Wed, 11 Sep 2013 21:10:44 -0700

Karsten Blees <[email-masked]> writes:

> +/*
> + * Hashmap entry data structure, intended to be used as first member of user
> + * data structures. Consists of a pointer and an int. Ideally it should be

It is technically correct to say this is "intended to be" used, but
to those who are using this API, it would be more helpful to say "a
user data structure that uses this API *must* have this as its first
member field".

> + * followed by an int-sized member to prevent unused memory on 64-bit systems
> + * due to alignment.
> + */
> +typedef struct hashmap_entry {
> +	struct hashmap_entry *next;
> +	unsigned int hash;
> +} hashmap_entry;
> + ...
> +typedef struct hashmap {
> +	hashmap_entry **table;
> +	hashmap_cmp_fn cmpfn;
> +	unsigned int size, tablesize;
> +} hashmap;

I forgot to mention in my previous message, but we find that the
code tends to be easier to read if we avoid using typedef'ed struct
like these.  E.g. in 2/5 we see something like this:

     static int abbrev = -1; /* unspecified */
     static int max_candidates = 10;
    -static struct hash_table names;
    +static hashmap names;
     static int have_util;
     static const char *pattern;
     static int always;
    @@ -38,7 +38,7 @@ static const char *diff_index_args[] = {

     struct commit_name {
    -	struct commit_name *next;
    +	hashmap_entry entry;
            unsigned char peeled[20];

The version before the patch is preferrable.

Thanks.