Messages in this thread | | | Date | Fri, 27 Jun 2008 08:37:34 -0700 | From | "Paul Menage" <> | Subject | Re: [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
| |