From mboxrd@z Thu Jan 1 00:00:00 1970 From: Sasha Levin Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable Date: Thu, 06 Sep 2012 17:49:41 +0200 Message-ID: <5048C615.4070204@gmail.com> References: <503C95E4.3010000@gmail.com> <20120828101148.GA21683@Krystal> <503CAB1E.5010408@gmail.com> <20120828115638.GC23818@Krystal> <20120828230050.GA3337@Krystal> <1346772948.27919.9.camel@gandalf.local.home> <50462C99.5000007@redhat.com> <50462EE8.1090903@redhat.com> <20120904170138.GB31934@Krystal> <5048AAF6.5090101@gmail.com> <20120906145545.GA17332@leaf> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Cc: snitzer-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, neilb-l3A5Bk7waGM@public.gmane.org, fweisbec-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org, Trond.Myklebust-HgOvQuBEEgTQT0dZR+AlfA@public.gmane.org, bfields-uC3wQj2KruNg9hUCZPvPmw@public.gmane.org, paul.gortmaker-CWA4WttNNZF54TAoqtyWWQ@public.gmane.org, dm-devel-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, agk-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, aarcange-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, rds-devel-N0ozoZBvEnrZJqsBc5GL+g@public.gmane.org, eric.dumazet-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org, venkat.x.venkatsubra-QHcLZuEGTsvQT0dZR+AlfA@public.gmane.org, ccaulfie-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, mingo-X9Un+BFzKDI@public.gmane.org, dev-yBygre7rU0TnMu66kgdUjQ@public.gmane.org, ericvh-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org, Steven Rostedt , lw-BthXqXjhjHXQFUHtdCDX3A@public.gmane.org, Mathieu Desnoyers , axboe-tSWWG44O7X1aa/9Udqfwiw@public.gmane.org, linux-nfs-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, edumazet-hpIqsD4AKlfQT0dZR+AlfA@public.gmane.org, linux-mm-Bw31MaZKKs3YtjvyW6yDsg@public.gmane.org, Pedro Alves , linux-kernel-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, ejt-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, ebiederm-aS9lmoZGLiVWk0Htik3J/w@public.gmane.org, netdev-u79uwXL29TY76Z2rM5mHXA@public.gmane.org, Tejun Heo , teigland-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org, akpm-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org, torvalds-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org, davem-fT/PcQaiUtIeIZ0/mPfg9Q@public.gmane.org To: Josh Triplett Return-path: In-Reply-To: <20120906145545.GA17332@leaf> List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: dev-bounces-yBygre7rU0TnMu66kgdUjQ@public.gmane.org Errors-To: dev-bounces-yBygre7rU0TnMu66kgdUjQ@public.gmane.org List-Id: netdev.vger.kernel.org On 09/06/2012 04:55 PM, Josh Triplett wrote: > On Thu, Sep 06, 2012 at 03:53:58PM +0200, Sasha Levin wrote: >> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote: >>>> #define do_for_each_ftrace_rec(pg, rec) \ >>>>> for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \ >>>>> pg && rec == &pg->records[pg->index]; \ >>>>> pg = pg->next) \ >>>>> for (rec = pg->records; rec < &pg->records[pg->index]; rec++) >>> Maybe in some cases there might be ways to combine the two loops into >>> one ? I'm not seeing exactly how to do it for this one, but it should >>> not be impossible. If the inner loop condition can be moved to the outer >>> loop, and if we use (blah ? loop1_conf : loop2_cond) to test for >>> different conditions depending on the context, and do the same for the >>> 3rd argument of the for() loop. The details elude me for now though, so >>> maybe it's complete non-sense ;) >>> >>> It might not be that useful for do_for_each_ftrace_rec, but if we can do >>> it for the hash table iterator, it might be worth it. >> >> So I think that for the hash iterator it might actually be simpler. >> >> My solution to making 'break' work in the iterator is:A code like that doesn >> >> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++) >> hlist_for_each_entry(obj, node, &name[bkt], member) >> >> We initialize our node loop cursor with NULL in the external loop, and the >> external loop will have a new condition to loop while that cursor is NULL. >> >> My logic is that we can only 'break' when we are iterating over an object in the >> internal loop. If we're iterating over an object in that loop then 'node != NULL'. >> >> This way, if we broke from within the internal loop, the external loop will see >> node as not NULL, and so it will stop looping itself. On the other hand, if the >> internal loop has actually ended, then node will be NULL, and the outer loop >> will keep running. >> >> Is there anything I've missed? > > Looks reasonable. However, it would break (or rather, not break) on > code like this: > > hash_for_each_entry(...) { > if (...) { > foo(node); > node = NULL; > break; > } > } > > Hiding the double loop still seems error-prone. I think that that code doesn't make sense. The users of hlist_for_each_* aren't supposed to be changing the loop cursor. We have three options here: 1. Stuff everything into a single for(). While not too difficult, it will make the readability of the code difficult as it will force us to abandon using hlist_for_each_* macros. 2. Over-complicate everything, and check for 'node == NULL && obj && obj->member.next == NULL' instead. That one will fail only if the user has specifically set the object as the last object in the list and the node as NULL. 3. Use 2 loops which might not work properly if the user does something odd, with a big fat warning above them. To sum it up, I'd rather go with 3 and let anyone who does things he shouldn't be doing break. Thanks, Sasha