Re: [PATCH] Prio_heap: heap_remove(), heap_maximum(), heap_replace() and heap_cherrypick()

[Lai Jiangshan <laijs@cn.fujitsu.com>]

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 <mathieu.desnoyers@efficios.com>
> Acked-by: Balbir Singh <balbir@in.ibm.com>
> Cc: Paul Menage <menage@google.com>
> Cc: David Rientjes <rientjes@google.com>
> Cc: Cedric Le Goater <clg@fr.ibm.com>
> Cc: "Eric W. Biederman" <ebiederm@xmission.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> ---
>  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 <laijs@cn.fujitsu.com>