Skip to contentSkip to conversation

Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick()

PATCH In review Mathieu Desnoyers 3 participants 4 messages Oct 7, 2010 – Oct 9, 2010 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick()

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.

Cc Paul Menage <[email protected]>
Cc David Rientjes <[email protected]>
Cc Cedric Le Goater <[email protected]>
Cc "Eric W. Biederman" <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Linus Torvalds <[email protected]>
---
 include/linux/prio_heap.h |   44 ++++++++++++++++++++++
 lib/prio_heap.c           |   91 ++++++++++++++++++++++++++++++++++++----------
 2 files changed, 116 insertions(+), 19 deletions(-)
include/linux/prio_heap.h +44 -0
Index: linux.trees.git/include/linux/prio_heap.h
===================================================================
@@ -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 */
lib/prio_heap.c +72 -19

108 lines not on this page · raw message

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
Reviewed-by on v1 1/1
#1 lore raw
Quoted 9 lines · Mathieu Desnoyers

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!

Quoted 9 lines
Cc Paul Menage <[email protected]>
Cc David Rientjes <[email protected]>
Cc Cedric Le Goater <[email protected]>
Cc "Eric W. Biederman" <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Linus Torvalds <[email protected]>
Quoted 4 lines
---
 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?

Quoted 80 lines

Index: linux.trees.git/include/linux/prio_heap.h
===================================================================

include/linux/prio_heap.h +44 -0
@@ -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
===================================================================

lib/prio_heap.c +8 -1
@@ -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;

lib/prio_heap.c void heap_free(struct ptr_heap *heap) · line 43

Quoted 10 lines
lib/prio_heap.c +10 -0
+		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;
	}
}
Quoted 29 lines
lib/prio_heap.c +20 -0
+
+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++;

lib/prio_heap.c void *heap_insert(struct ptr_heap *heap, · line 88

Quoted 8 lines
lib/prio_heap.c +2 -3
@@ -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.

Quoted 41 lines
lib/prio_heap.c +24 -15
-	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:

lib/prio_heap.c void *heap_insert(struct ptr_heap *heap,

Quoted 10 lines
lib/prio_heap.c +8 -0
+	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.

Acked-by on v1 1/1
#2 lore raw
In reply to Mathieu Desnoyers
Quoted 10 lines · Mathieu Desnoyers

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.

Looks fine, other than a couple of suggestions to make the code slightly clearer.

Quoted 79 lines
Cc Paul Menage <[email protected]>
Cc David Rientjes <[email protected]>
Cc Cedric Le Goater <[email protected]>
Cc "Eric W. Biederman" <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Linus Torvalds <[email protected]>

---
 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
===================================================================

include/linux/prio_heap.h   2010-07-07 10:04:33.000000000 -0400 renamed from include/linux/prio_heap.h      2010-07-06 14:25:29.000000000 -0400 +44 -0
@@ -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
===================================================================

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 26

Quoted 5 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +1 -1
@@ -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.

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 31

Quoted 5 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +1 -0
+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()

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 33

Quoted 3 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +2 -0
+       if (!heap->size) {
+               ptrs[heap->size++] = p;

Maybe make this clearer?

  ptrs[0] = p;
  heap->size = 1;

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 42

Quoted 9 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +9 -0
+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];

#3 lore raw
Quoted 100 lines · * Paul Menage ([email protected]) wrote:
Quoted 10 lines · Mathieu Desnoyers

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.

Looks fine, other than a couple of suggestions to make the code slightly clearer.

Quoted 82 lines
Cc Paul Menage <[email protected]>
Cc David Rientjes <[email protected]>
Cc Cedric Le Goater <[email protected]>
Cc "Eric W. Biederman" <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Linus Torvalds <[email protected]>

---
 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
===================================================================

include/linux/prio_heap.h   2010-07-07 10:04:33.000000000 -0400 renamed from include/linux/prio_heap.h      2010-07-06 14:25:29.000000000 -0400 +44 -0
@@ -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
===================================================================

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +0 -0
@@ -23,12 +23,49 @@ void heap_free(struct ptr_heap *heap)
        kfree(heap->ptrs);
  }
 
Quoted 6 lines

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 26

Quoted 2 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +1 -1
-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.

Quoted 8 lines

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 31

Quoted 6 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +1 -0
+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

Quoted 8 lines

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 33

Quoted 3 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +2 -0
+       if (!heap->size) {
+               ptrs[heap->size++] = p;

Maybe make this clearer?

  ptrs[0] = p;
  heap->size = 1;

OK.

Quoted 13 lines

lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 void heap_free(struct ptr_heap *heap) · line 42

Quoted 10 lines
lib/prio_heap.c     2010-07-07 10:18:32.000000000 -0400 renamed from lib/prio_heap.c        2010-07-06 14:25:29.000000000 -0400 +9 -0
+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:

Quoted 2 lines

heap->size = 0;
return ptrs[0];

Yep, I changed the same thing in heap_cherrypick too.

Thanks!

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com