lkml.org 
[lkml]   [2008]   [Jun]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [RFC 3/5] Replacement policy on heap overfull
On Fri, Jun 27, 2008 at 8:18 AM, Balbir Singh <balbir@linux.vnet.ibm.com> wrote:
>
>
> This patch adds a policy parameter to heap_insert. While inserting an element
> if the heap is full, the policy determines which element to replace.
> The default earlier is now obtained by passing the policy as HEAP_REP_TOP.
> The new HEAP_REP_LEAF policy, replaces a leaf node (the last element).
>
> Signed-off-by: Balbir Singh <balbir@linux.vnet.ibm.com>
> ---
>
> include/linux/prio_heap.h | 9 ++++++++-
> kernel/cgroup.c | 2 +-
> lib/prio_heap.c | 31 +++++++++++++++++++++++--------
> 3 files changed, 32 insertions(+), 10 deletions(-)
>
> diff -puN include/linux/prio_heap.h~prio_heap_replace_leaf include/linux/prio_heap.h
> --- linux-2.6.26-rc5/include/linux/prio_heap.h~prio_heap_replace_leaf 2008-06-27 20:43:09.000000000 +0530
> +++ linux-2.6.26-rc5-balbir/include/linux/prio_heap.h 2008-06-27 20:43:09.000000000 +0530
> @@ -22,6 +22,11 @@ struct ptr_heap {
> int (*gt)(void *, void *);
> };
>
> +enum heap_replacement_policy {
> + HEAP_REP_LEAF,
> + HEAP_REP_TOP,
> +};

Maybe "drop" rather than "replace"? HEAP_REP_TOP doesn't replace the
top element if you insert a new higher element, it drops the top.

How about HEAP_DROP_LEAF and HEAP_DROP_MAX? You could also provide a
HEAP_DROP_MIN with the caveat that it would take linear time.

Add comments here about what these mean?

> + if (policy == HEAP_REP_TOP)

switch() here?

> + if (heap->gt(p, ptrs[0]))
> + return p;
> +
> + if (policy == HEAP_REP_LEAF) {
> + /* Heap insertion */
> + int pos = heap->size - 1;
> + res = ptrs[pos];
> + heap_insert_at(heap, p, pos);
> + return res;
> + }
>
> /* Replace the current max and heapify */
> res = ptrs[0];

This should probably be in the arm dealing with
HEAP_REP_TOP/HEAP_DROP_MAX since we only get here in that case.

Paul


\
 
 \ /
  Last update: 2008-06-27 17:41    [W:0.237 / U:0.316 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site