From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753542Ab2HCVTf (ORCPT ); Fri, 3 Aug 2012 17:19:35 -0400 Received: from mail-we0-f174.google.com ([74.125.82.174]:36161 "EHLO mail-we0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752377Ab2HCVTb (ORCPT ); Fri, 3 Aug 2012 17:19:31 -0400 Message-ID: <501C407D.9080900@gmail.com> Date: Fri, 03 Aug 2012 23:19:57 +0200 From: Sasha Levin User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:14.0) Gecko/20120730 Thunderbird/14.0 MIME-Version: 1.0 To: Tejun Heo CC: torvalds@linux-foundation.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, linux-mm@kvack.org, paul.gortmaker@windriver.com, davem@davemloft.net, rostedt@goodmis.org, mingo@elte.hu, ebiederm@xmission.com, aarcange@redhat.com, ericvh@gmail.com, netdev@vger.kernel.org Subject: Re: [RFC v2 1/7] hashtable: introduce a small and naive hashtable References: <1344003788-1417-1-git-send-email-levinsasha928@gmail.com> <1344003788-1417-2-git-send-email-levinsasha928@gmail.com> <20120803171515.GH15477@google.com> In-Reply-To: <20120803171515.GH15477@google.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 08/03/2012 07:15 PM, Tejun Heo wrote: > Hello, Sasha. > > On Fri, Aug 03, 2012 at 04:23:02PM +0200, Sasha Levin wrote: >> +#define DEFINE_STATIC_HASHTABLE(n, b) \ >> + static struct hash_table n = { .bits = (b), \ >> + .buckets = { [0 ... ((1 << (b)) - 1)] = HLIST_HEAD_INIT } } > > What does this "static" mean? > >> +#define DEFINE_HASHTABLE(n, b) \ >> + union { \ >> + struct hash_table n; \ >> + struct { \ >> + size_t bits; \ >> + struct hlist_head buckets[1 << (b)]; \ >> + } __##n ; \ >> + }; > > Is this supposed to be embedded in struct definition? If so, the name > is rather misleading as DEFINE_* is supposed to define and initialize > stand-alone constructs. Also, for struct members, simply putting hash > entries after struct hash_table should work. It would work, but I didn't want to just put them in the union since I feel it's safer to keep them in a separate struct so they won't be used by mistake, > Wouldn't using DEFINE_HASHTABLE() for the first macro and > DEFINE_HASHTABLE_MEMBER() for the latter be better? Indeed that sounds better, will fix. >> +#define HASH_BITS(name) ((name)->bits) >> +#define HASH_SIZE(name) (1 << (HASH_BITS(name))) >> + >> +__attribute__ ((unused)) > > Are we using __attribute__((unused)) for functions defined in headers > instead of static inline now? If so, why? > >> +static void hash_init(struct hash_table *ht, size_t bits) >> +{ >> + size_t i; > > I would prefer int here but no biggie. Just wondering, is there a particular reason behind it? >> + ht->bits = bits; >> + for (i = 0; i < (1 << bits); i++) >> + INIT_HLIST_HEAD(&ht->buckets[i]); >> +} >> + >> +static void hash_add(struct hash_table *ht, struct hlist_node *node, long key) >> +{ >> + hlist_add_head(node, >> + &ht->buckets[hash_long((unsigned long)key, HASH_BITS(ht))]); >> +} >> + >> + >> +#define hash_get(name, key, type, member, cmp_fn) \ >> +({ \ >> + struct hlist_node *__node; \ >> + typeof(key) __key = key; \ >> + type *__obj = NULL; \ >> + hlist_for_each_entry(__obj, __node, &(name)->buckets[ \ >> + hash_long((unsigned long) __key, \ >> + HASH_BITS(name))], member) \ >> + if (cmp_fn(__obj, __key)) \ >> + break; \ >> + __obj; \ >> +}) > > As opposed to using hash_for_each_possible(), how much difference does > this make? Is it really worthwhile? Most of the places I've switched to using this hashtable so far (4 out of 6) are using hash_get(). I think that the code looks cleaner when you an just provide a comparison function instead of implementing the iteration itself. I think hash_for_for_each_possible() is useful if the comparison condition is more complex than a simple comparison of one of the object members with the key - there's no need to force it on all the users. > > Thanks. >