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

[Karsten Blees <karsten.blees@gmail.com>]

Am 12.09.2013 06:10, schrieb Junio C Hamano:
> Karsten Blees <karsten.blees@gmail.com> 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".
> 

Right. I considered making the position in the user struct configurable via some offsetof() magic, but this would have just complicated things unnecessarily.

>> + * 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.
> 

OK