From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1757250Ab0JIUha (ORCPT ); Sat, 9 Oct 2010 16:37:30 -0400 Received: from mail.openrapids.net ([64.15.138.104]:52575 "EHLO blackscsi.openrapids.net" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1757119Ab0JIUh1 convert rfc822-to-8bit (ORCPT ); Sat, 9 Oct 2010 16:37:27 -0400 Date: Sat, 9 Oct 2010 16:37:24 -0400 From: Mathieu Desnoyers To: Paul Menage Cc: Steven Rostedt , LKML , Linus Torvalds , Andrew Morton , Peter Zijlstra , Ingo Molnar , Frederic Weisbecker , Thomas Gleixner , Christoph Hellwig , Li Zefan , Lai Jiangshan , Johannes Berg , Masami Hiramatsu , Arnaldo Carvalho de Melo , Tom Zanussi , KOSAKI Motohiro , Andi Kleen , "Paul E. McKenney" , David Rientjes , Nick Piggin , Balbir Singh , Cedric Le Goater , "Eric W. Biederman" Subject: Re: [PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick() Message-ID: <20101009203724.GB23472@Krystal> References: <20101007190322.GA27054@Krystal> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8BIT In-Reply-To: X-Editor: vi X-Info: http://www.efficios.com X-Operating-System: Linux/2.6.26-2-686 (i686) X-Uptime: 16:30:46 up 17 days, 32 min, 1 user, load average: 0.44, 0.18, 0.11 User-Agent: Mutt/1.5.18 (2008-05-17) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org * Paul Menage (menage@google.com) wrote: > On Thu, Oct 7, 2010 at 12:03 PM, Mathieu Desnoyers > wrote: > > These added interfaces lets prio_heap users lookup the top of heap item without > > performing any insertion, perform removal of the topmost heap entry, and also > > replacement of topmost heap entry. This is useful if one need to use the result > > of the lookup to determine if the current maximum should simply be removed or if > > it should be replaced. > > > > This is used by the Generic Ring Buffer to perform timestamp-based fusion-merge > > of per-cpu buffer records into a single stream. > > > > Signed-off-by: Mathieu Desnoyers > > Looks fine, other than a couple of suggestions to make the code > slightly clearer. > > Acked-by: Paul Menage > > > Acked-by: Balbir Singh > > Cc: Paul Menage > > Cc: David Rientjes > > Cc: Cedric Le Goater > > Cc: "Eric W. Biederman" > > Cc: Andrew Morton > > Cc: Linus Torvalds > > --- > >  include/linux/prio_heap.h |   44 ++++++++++++++++++++++ > >  lib/prio_heap.c           |   91 ++++++++++++++++++++++++++++++++++++---------- > >  2 files changed, 116 insertions(+), 19 deletions(-) > > > > Index: linux.trees.git/include/linux/prio_heap.h > > =================================================================== > > --- linux.trees.git.orig/include/linux/prio_heap.h      2010-07-06 14:25:29.000000000 -0400 > > +++ linux.trees.git/include/linux/prio_heap.h   2010-07-07 10:04:33.000000000 -0400 > > @@ -23,6 +23,18 @@ struct ptr_heap { > >  }; > > > >  /** > > + * heap_maximum - return the largest element in the heap > > + * @heap: the heap to be operated on > > + * > > + * Returns the largest element in the heap, without performing any modification > > + * to the heap structure. Returns NULL if the heap is empty. > > + */ > > +static inline void *heap_maximum(const struct ptr_heap *heap) > > +{ > > +       return heap->size ? heap->ptrs[0] : NULL; > > +} > > + > > +/** > >  * heap_init - initialize an empty heap with a given memory size > >  * @heap: the heap structure to be initialized > >  * @size: amount of memory to use in bytes > > @@ -53,6 +65,38 @@ void heap_free(struct ptr_heap *heap); > >  */ > >  extern void *heap_insert(struct ptr_heap *heap, void *p); > > > > +/** > > + * heap_remove - remove the largest element from the heap > > + * @heap: the heap to be operated on > > + * > > + * Returns the largest element in the heap. It removes this element from the > > + * heap. Returns NULL if the heap is empty. > > + */ > > +extern void *heap_remove(struct ptr_heap *heap); > > > > +/** > > + * heap_cherrypick - remove a given element from the heap > > + * @heap: the heap to be operated on > > + * @p: the element > > + * > > + * Remove the given element from the heap. Return the element if present, else > > + * return NULL. This algorithm has a complexity of O(n), which is higher than > > + * O(log(n)) provided by the rest of this API. > > + */ > > +extern void *heap_cherrypick(struct ptr_heap *heap, void *p); > > + > > +/** > > + * heap_replace_max - replace the the largest element from the heap > > + * @heap: the heap to be operated on > > + * @p: the pointer to be inserted as topmost element replacement > > + * > > + * Returns the largest element in the heap. It removes this element from the > > + * heap. The heap is rebalanced only once after the insertion. Returns NULL if > > + * the heap is empty. > > + * > > + * This is the equivalent of calling heap_remove() and then heap_insert(), but > > + * it only rebalances the heap once. > > + */ > > +extern void *heap_replace_max(struct ptr_heap *heap, void *p); > > > >  #endif /* _LINUX_PRIO_HEAP_H */ > > Index: linux.trees.git/lib/prio_heap.c > > =================================================================== > > --- linux.trees.git.orig/lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 > > +++ linux.trees.git/lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 > > @@ -23,12 +23,49 @@ void heap_free(struct ptr_heap *heap) > >        kfree(heap->ptrs); > >  } > > > > -void *heap_insert(struct ptr_heap *heap, void *p) > > +static void heapify(struct ptr_heap *heap, void **ptrs, void *p, int pos) > > I'd be inclined to not pass "ptrs" or "p" as an argument, and instead > get ptrs from heap->ptrs and p from ptrs[pos]. It makes it clearer > what heapify() is doing. OK. > > > +void *heap_replace_max(struct ptr_heap *heap, void *p) > >  { > >        void *res; > >        void **ptrs = heap->ptrs; > >        int pos; > > No need for "pos" - just pass a constant 0 to heapify() OK > > > > +       if (!heap->size) { > > +               ptrs[heap->size++] = p; > > Maybe make this clearer? > > ptrs[0] = p; > heap->size = 1; OK. > > > +void *heap_remove(struct ptr_heap *heap) > > +{ > > +       void **ptrs = heap->ptrs; > > + > > +       switch (heap->size) { > > +       case 0: > > +               return NULL; > > +       case 1: > > +               return ptrs[--heap->size]; > > Maybe clearer: > > heap->size = 0; > return ptrs[0]; Yep, I changed the same thing in heap_cherrypick too. Thanks! Mathieu -- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com