Re: [PATCH/RFC 1/5] add a hashtable implementation that supports O(1) removal
Am 12.09.2013 06:10, schrieb Junio C Hamano:
Show 11 quoted lines
> 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.
Show 35 quoted lines
>> + * 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.
> Karsten Blees <karsten.blees@gmail.com>