From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751961Ab0JHDcs (ORCPT ); Thu, 7 Oct 2010 23:32:48 -0400 Received: from cn.fujitsu.com ([222.73.24.84]:51816 "EHLO song.cn.fujitsu.com" rhost-flags-OK-FAIL-OK-OK) by vger.kernel.org with ESMTP id S1751531Ab0JHDcq (ORCPT ); Thu, 7 Oct 2010 23:32:46 -0400 Message-ID: <4CAE91BE.6070703@cn.fujitsu.com> Date: Fri, 08 Oct 2010 11:36:30 +0800 From: Lai Jiangshan User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.1.9) Gecko/20100423 Thunderbird/3.0.4 MIME-Version: 1.0 To: Mathieu Desnoyers CC: Steven Rostedt , LKML , Linus Torvalds , Andrew Morton , Peter Zijlstra , Ingo Molnar , Frederic Weisbecker , Thomas Gleixner , Christoph Hellwig , Li Zefan , Johannes Berg , Masami Hiramatsu , Arnaldo Carvalho de Melo , Tom Zanussi , KOSAKI Motohiro , Andi Kleen , "Paul E. McKenney" , Paul Menage , 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() References: <20101007190322.GA27054@Krystal> In-Reply-To: <20101007190322.GA27054@Krystal> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 10/08/2010 03:03 AM, 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. Good! > > Signed-off-by: Mathieu Desnoyers > 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(-) Comments in the top of prio_heap.h and prio_heap.c. /* * Simple insertion-only static-sized priority heap containing * pointers, based on CLR, chapter 7 */ remove it? > > 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) > +{ > + while (1) { > + int left = 2 * pos + 1; > + int right = 2 * pos + 2; > + int largest = pos; > + if (left < heap->size && heap->gt(ptrs[left], p)) > + largest = left; > + if (right < heap->size && heap->gt(ptrs[right], ptrs[largest])) > + largest = right; > + if (largest == pos) > + break; > + /* Push p down the heap one level and bump one up */ > + ptrs[pos] = ptrs[largest]; > + ptrs[largest] = p; > + pos = largest; > + } > +} This is "static", no one use it, but someone will read it and be confused. because it haves/(is required) a precondition: "ptrs[pos] == p", and no comments for it. PS: the code is exactly the same as the book CLRS, but in practice, I think we can save a half assignments and the precondition(and save a line of code which provides this precondition before call heapify()). /* just type it in this email, compare the children at first */ /* ptrs[pos] is a hole */ static void heapify(struct ptr_heap *heap, void **ptrs, void *p, int pos) { while (1) { int left = 2 * pos + 1; int right = 2 * pos + 2; int largest = left; /* compare the children at first */ if (right < heap->size && heap->gt(ptrs[right], ptrs[left])) largest = right; if (!(largest < heap->size) || heap->gt(p, ptrs[largest])) { ptrs[pos] = p; break; } /* Push p down the heap one level and bump one up */ ptrs[pos] = ptrs[largest]; pos = largest; } } > + > +void *heap_replace_max(struct ptr_heap *heap, void *p) > { > void *res; > void **ptrs = heap->ptrs; > int pos; > > + if (!heap->size) { > + ptrs[heap->size++] = p; > + return NULL; > + } > + > + /* Replace the current max and heapify */ > + res = ptrs[0]; > + ptrs[0] = p; > + pos = 0; > + heapify(heap, ptrs, p, pos); > + return res; > +} > + > +void *heap_insert(struct ptr_heap *heap, void *p) > +{ > + void **ptrs = heap->ptrs; > + int pos; > + > if (heap->size < heap->max) { > /* Heap insertion */ > pos = heap->size++; > @@ -47,24 +84,40 @@ void *heap_insert(struct ptr_heap *heap, > return p; > > /* Replace the current max and heapify */ > - res = ptrs[0]; > - ptrs[0] = p; > - pos = 0; > + return heap_replace_max(heap, p); > +} Since we have heap_replace_max(), I think we can change the semantic of heap_insert() to origin: insert a new element and maintain the heap or return fail when some errors occur(example: the the heap is full). currently only cgroup use heap_insert(), we can covert it to new heap_insert() + heap_replace_max(). Or add a new API for it. Just my think. > > - while (1) { > - int left = 2 * pos + 1; > - int right = 2 * pos + 2; > - int largest = pos; > - if (left < heap->size && heap->gt(ptrs[left], p)) > - largest = left; > - if (right < heap->size && heap->gt(ptrs[right], ptrs[largest])) > - largest = right; > - if (largest == pos) > - break; > - /* Push p down the heap one level and bump one up */ > - ptrs[pos] = ptrs[largest]; > - ptrs[largest] = p; > - pos = largest; > +void *heap_remove(struct ptr_heap *heap) > +{ > + void **ptrs = heap->ptrs; > + > + switch (heap->size) { > + case 0: > + return NULL; > + case 1: > + return ptrs[--heap->size]; > } > - return res; > + > + /* Shrink, replace the current max by previous last entry and heapify */ > + return heap_replace_max(heap, ptrs[--heap->size]); > +} > + > +void *heap_cherrypick(struct ptr_heap *heap, void *p) > +{ > + void **ptrs = heap->ptrs; > + size_t pos, size = heap->size; > + > + for (pos = 0; pos < size; pos++) > + if (ptrs[pos] == p) > + goto found; > + return NULL; > +found: > + if (heap->size == 1) > + return ptrs[--heap->size]; > + /* > + * Replace p with previous last entry and heapify. > + */ > + ptrs[pos] = ptrs[--heap->size]; > + heapify(heap, ptrs, ptrs[pos], pos); > + return p; > } > Thanks. Reviewed-by: Lai Jiangshan