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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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

--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html




[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]