drivers/staging/lustre/lustre/libcfs/heap.c - kernel/lockdown - Git at Google

 /*
  * GPL HEADER START
  *
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 only,
  * as published by the Free Software Foundation.

  * This program is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License version 2 for more details.  A copy is
  * included in the COPYING file that accompanied this code.

  * You should have received a copy of the GNU General Public License
  * along with this program; if not, write to the Free Software
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  *
  * GPL HEADER END
  */
 /*
  * Copyright (c) 2011 Intel Corporation
  */
 /*
  * libcfs/libcfs/heap.c
  *
  * Author: Eric Barton	<eeb@whamcloud.com>
  *	   Liang Zhen	<liang@whamcloud.com>
  */
 /** \addtogroup heap
  *
  * @{
  */

 #define DEBUG_SUBSYSTEM S_LNET

 #include <linux/libcfs/libcfs.h>

 #define CBH_ALLOC(ptr, h)						\
 do {									\
 	if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)			\
 		LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, h->cbh_cptid,	\
 				     CBH_NOB, GFP_ATOMIC);	\
 	else								\
 		LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid,	\
 				 CBH_NOB);				\
 } while (0)

 #define CBH_FREE(ptr)	LIBCFS_FREE(ptr, CBH_NOB)

 /**
  * Grows the capacity of a binary heap so that it can handle a larger number of
  * \e cfs_binheap_node_t objects.
  *
  * \param[in] h The binary heap
  *
  * \retval 0	   Successfully grew the heap
  * \retval -ENOMEM OOM error
  */
 static int
 cfs_binheap_grow(cfs_binheap_t *h)
 {
 	cfs_binheap_node_t ***frag1 = NULL;
 	cfs_binheap_node_t  **frag2;
 	int hwm = h->cbh_hwm;

 	/* need a whole new chunk of pointers */
 	LASSERT((h->cbh_hwm & CBH_MASK) == 0);

 	if (hwm == 0) {
 		/* first use of single indirect */
 		CBH_ALLOC(h->cbh_elements1, h);
 		if (h->cbh_elements1 == NULL)
 			return -ENOMEM;

 		goto out;
 	}

 	hwm -= CBH_SIZE;
 	if (hwm < CBH_SIZE * CBH_SIZE) {
 		/* not filled double indirect */
 		CBH_ALLOC(frag2, h);
 		if (frag2 == NULL)
 			return -ENOMEM;

 		if (hwm == 0) {
 			/* first use of double indirect */
 			CBH_ALLOC(h->cbh_elements2, h);
 			if (h->cbh_elements2 == NULL) {
 				CBH_FREE(frag2);
 				return -ENOMEM;
 			}
 		}

 		h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
 		goto out;
 	}

 	hwm -= CBH_SIZE * CBH_SIZE;
 #if (CBH_SHIFT * 3 < 32)
 	if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
 		/* filled triple indirect */
 		return -ENOMEM;
 	}
 #endif
 	CBH_ALLOC(frag2, h);
 	if (frag2 == NULL)
 		return -ENOMEM;

 	if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
 		/* first use of this 2nd level index */
 		CBH_ALLOC(frag1, h);
 		if (frag1 == NULL) {
 			CBH_FREE(frag2);
 			return -ENOMEM;
 		}
 	}

 	if (hwm == 0) {
 		/* first use of triple indirect */
 		CBH_ALLOC(h->cbh_elements3, h);
 		if (h->cbh_elements3 == NULL) {
 			CBH_FREE(frag2);
 			CBH_FREE(frag1);
 			return -ENOMEM;
 		}
 	}

 	if (frag1 != NULL) {
 		LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
 		h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
 	} else {
 		frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
 		LASSERT(frag1 != NULL);
 	}

 	frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;

  out:
 	h->cbh_hwm += CBH_SIZE;
 	return 0;
 }

 /**
  * Creates and initializes a binary heap instance.
  *
  * \param[in] ops   The operations to be used
  * \param[in] flags The heap flags
  * \parm[in]  count The initial heap capacity in # of elements
  * \param[in] arg   An optional private argument
  * \param[in] cptab The CPT table this heap instance will operate over
  * \param[in] cptid The CPT id of \a cptab this heap instance will operate over
  *
  * \retval valid-pointer A newly-created and initialized binary heap object
  * \retval NULL		 error
  */
 cfs_binheap_t *
 cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
 		   unsigned count, void *arg, struct cfs_cpt_table *cptab,
 		   int cptid)
 {
 	cfs_binheap_t *h;

 	LASSERT(ops != NULL);
 	LASSERT(ops->hop_compare != NULL);
 	LASSERT(cptab != NULL);
 	LASSERT(cptid == CFS_CPT_ANY ||
 	       (cptid >= 0 && cptid < cptab->ctb_nparts));

 	LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
 	if (h == NULL)
 		return NULL;

 	h->cbh_ops	  = ops;
 	h->cbh_nelements  = 0;
 	h->cbh_hwm	  = 0;
 	h->cbh_private	  = arg;
 	h->cbh_flags	  = flags & (~CBH_FLAG_ATOMIC_GROW);
 	h->cbh_cptab	  = cptab;
 	h->cbh_cptid	  = cptid;

 	while (h->cbh_hwm < count) { /* preallocate */
 		if (cfs_binheap_grow(h) != 0) {
 			cfs_binheap_destroy(h);
 			return NULL;
 		}
 	}

 	h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;

 	return h;
 }
 EXPORT_SYMBOL(cfs_binheap_create);

 /**
  * Releases all resources associated with a binary heap instance.
  *
  * Deallocates memory for all indirection levels and the binary heap object
  * itself.
  *
  * \param[in] h The binary heap object
  */
 void
 cfs_binheap_destroy(cfs_binheap_t *h)
 {
 	int idx0;
 	int idx1;
 	int n;

 	LASSERT(h != NULL);

 	n = h->cbh_hwm;

 	if (n > 0) {
 		CBH_FREE(h->cbh_elements1);
 		n -= CBH_SIZE;
 	}

 	if (n > 0) {
 		for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 			CBH_FREE(h->cbh_elements2[idx0]);
 			n -= CBH_SIZE;
 		}

 		CBH_FREE(h->cbh_elements2);
 	}

 	if (n > 0) {
 		for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {

 			for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
 				CBH_FREE(h->cbh_elements3[idx0][idx1]);
 				n -= CBH_SIZE;
 			}

 			CBH_FREE(h->cbh_elements3[idx0]);
 		}

 		CBH_FREE(h->cbh_elements3);
 	}

 	LIBCFS_FREE(h, sizeof(*h));
 }
 EXPORT_SYMBOL(cfs_binheap_destroy);

 /**
  * Obtains a double pointer to a heap element, given its index into the binary
  * tree.
  *
  * \param[in] h	  The binary heap instance
  * \param[in] idx The requested node's index
  *
  * \retval valid-pointer A double pointer to a heap pointer entry
  */
 static cfs_binheap_node_t **
 cfs_binheap_pointer(cfs_binheap_t *h, unsigned int idx)
 {
 	if (idx < CBH_SIZE)
 		return &(h->cbh_elements1[idx]);

 	idx -= CBH_SIZE;
 	if (idx < CBH_SIZE * CBH_SIZE)
 		return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);

 	idx -= CBH_SIZE * CBH_SIZE;
 	return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
 				 [(idx >> CBH_SHIFT) & CBH_MASK]\
 				 [idx & CBH_MASK]);
 }

 /**
  * Obtains a pointer to a heap element, given its index into the binary tree.
  *
  * \param[in] h	  The binary heap
  * \param[in] idx The requested node's index
  *
  * \retval valid-pointer The requested heap node
  * \retval NULL		 Supplied index is out of bounds
  */
 cfs_binheap_node_t *
 cfs_binheap_find(cfs_binheap_t *h, unsigned int idx)
 {
 	if (idx >= h->cbh_nelements)
 		return NULL;

 	return *cfs_binheap_pointer(h, idx);
 }
 EXPORT_SYMBOL(cfs_binheap_find);

 /**
  * Moves a node upwards, towards the root of the binary tree.
  *
  * \param[in] h The heap
  * \param[in] e The node
  *
  * \retval 1 The position of \a e in the tree was changed at least once
  * \retval 0 The position of \a e in the tree was not changed
  */
 static int
 cfs_binheap_bubble(cfs_binheap_t *h, cfs_binheap_node_t *e)
 {
 	unsigned int	     cur_idx = e->chn_index;
 	cfs_binheap_node_t **cur_ptr;
 	unsigned int	     parent_idx;
 	cfs_binheap_node_t **parent_ptr;
 	int		     did_sth = 0;

 	cur_ptr = cfs_binheap_pointer(h, cur_idx);
 	LASSERT(*cur_ptr == e);

 	while (cur_idx > 0) {
 		parent_idx = (cur_idx - 1) >> 1;

 		parent_ptr = cfs_binheap_pointer(h, parent_idx);
 		LASSERT((*parent_ptr)->chn_index == parent_idx);

 		if (h->cbh_ops->hop_compare(*parent_ptr, e))
 			break;

 		(*parent_ptr)->chn_index = cur_idx;
 		*cur_ptr = *parent_ptr;
 		cur_ptr = parent_ptr;
 		cur_idx = parent_idx;
 		did_sth = 1;
 	}

 	e->chn_index = cur_idx;
 	*cur_ptr = e;

 	return did_sth;
 }

 /**
  * Moves a node downwards, towards the last level of the binary tree.
  *
  * \param[in] h The heap
  * \param[in] e The node
  *
  * \retval 1 The position of \a e in the tree was changed at least once
  * \retval 0 The position of \a e in the tree was not changed
  */
 static int
 cfs_binheap_sink(cfs_binheap_t *h, cfs_binheap_node_t *e)
 {
 	unsigned int	     n = h->cbh_nelements;
 	unsigned int	     child_idx;
 	cfs_binheap_node_t **child_ptr;
 	cfs_binheap_node_t  *child;
 	unsigned int	     child2_idx;
 	cfs_binheap_node_t **child2_ptr;
 	cfs_binheap_node_t  *child2;
 	unsigned int	     cur_idx;
 	cfs_binheap_node_t **cur_ptr;
 	int		     did_sth = 0;

 	cur_idx = e->chn_index;
 	cur_ptr = cfs_binheap_pointer(h, cur_idx);
 	LASSERT(*cur_ptr == e);

 	while (cur_idx < n) {
 		child_idx = (cur_idx << 1) + 1;
 		if (child_idx >= n)
 			break;

 		child_ptr = cfs_binheap_pointer(h, child_idx);
 		child = *child_ptr;

 		child2_idx = child_idx + 1;
 		if (child2_idx < n) {
 			child2_ptr = cfs_binheap_pointer(h, child2_idx);
 			child2 = *child2_ptr;

 			if (h->cbh_ops->hop_compare(child2, child)) {
 				child_idx = child2_idx;
 				child_ptr = child2_ptr;
 				child = child2;
 			}
 		}

 		LASSERT(child->chn_index == child_idx);

 		if (h->cbh_ops->hop_compare(e, child))
 			break;

 		child->chn_index = cur_idx;
 		*cur_ptr = child;
 		cur_ptr = child_ptr;
 		cur_idx = child_idx;
 		did_sth = 1;
 	}

 	e->chn_index = cur_idx;
 	*cur_ptr = e;

 	return did_sth;
 }

 /**
  * Sort-inserts a node into the binary heap.
  *
  * \param[in] h The heap
  * \param[in] e The node
  *
  * \retval 0	Element inserted successfully
  * \retval != 0 error
  */
 int
 cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e)
 {
 	cfs_binheap_node_t **new_ptr;
 	unsigned int	     new_idx = h->cbh_nelements;
 	int		     rc;

 	if (new_idx == h->cbh_hwm) {
 		rc = cfs_binheap_grow(h);
 		if (rc != 0)
 			return rc;
 	}

 	if (h->cbh_ops->hop_enter) {
 		rc = h->cbh_ops->hop_enter(h, e);
 		if (rc != 0)
 			return rc;
 	}

 	e->chn_index = new_idx;
 	new_ptr = cfs_binheap_pointer(h, new_idx);
 	h->cbh_nelements++;
 	*new_ptr = e;

 	cfs_binheap_bubble(h, e);

 	return 0;
 }
 EXPORT_SYMBOL(cfs_binheap_insert);

 /**
  * Removes a node from the binary heap.
  *
  * \param[in] h The heap
  * \param[in] e The node
  */
 void
 cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e)
 {
 	unsigned int	     n = h->cbh_nelements;
 	unsigned int	     cur_idx = e->chn_index;
 	cfs_binheap_node_t **cur_ptr;
 	cfs_binheap_node_t  *last;

 	LASSERT(cur_idx != CBH_POISON);
 	LASSERT(cur_idx < n);

 	cur_ptr = cfs_binheap_pointer(h, cur_idx);
 	LASSERT(*cur_ptr == e);

 	n--;
 	last = *cfs_binheap_pointer(h, n);
 	h->cbh_nelements = n;
 	if (last == e)
 		return;

 	last->chn_index = cur_idx;
 	*cur_ptr = last;
 	if (!cfs_binheap_bubble(h, *cur_ptr))
 		cfs_binheap_sink(h, *cur_ptr);

 	e->chn_index = CBH_POISON;
 	if (h->cbh_ops->hop_exit)
 		h->cbh_ops->hop_exit(h, e);
 }
 EXPORT_SYMBOL(cfs_binheap_remove);

 /** @} heap */
	/*
	* GPL HEADER START
	*
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This program is free software; you can redistribute it and/or modify
	* it under the terms of the GNU General Public License version 2 only,
	* as published by the Free Software Foundation.

	* This program is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	* GNU General Public License version 2 for more details. A copy is
	* included in the COPYING file that accompanied this code.

	* You should have received a copy of the GNU General Public License
	* along with this program; if not, write to the Free Software
	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	*
	* GPL HEADER END
	*/
	/*
	* Copyright (c) 2011 Intel Corporation
	*/
	/*
	* libcfs/libcfs/heap.c
	*
	* Author: Eric Barton <eeb@whamcloud.com>
	* Liang Zhen <liang@whamcloud.com>
	*/
	/** \addtogroup heap
	*
	* @{
	*/

	#define DEBUG_SUBSYSTEM S_LNET

	#include <linux/libcfs/libcfs.h>

	#define CBH_ALLOC(ptr, h) \
	do { \
	if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
	LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, h->cbh_cptid, \
	CBH_NOB, GFP_ATOMIC); \
	else \
	LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid, \
	CBH_NOB); \
	} while (0)

	#define CBH_FREE(ptr) LIBCFS_FREE(ptr, CBH_NOB)

	/**
	* Grows the capacity of a binary heap so that it can handle a larger number of
	* \e cfs_binheap_node_t objects.
	*
	* \param[in] h The binary heap
	*
	* \retval 0 Successfully grew the heap
	* \retval -ENOMEM OOM error
	*/
	static int
	cfs_binheap_grow(cfs_binheap_t *h)
	{
	cfs_binheap_node_t ***frag1 = NULL;
	cfs_binheap_node_t **frag2;
	int hwm = h->cbh_hwm;

	/* need a whole new chunk of pointers */
	LASSERT((h->cbh_hwm & CBH_MASK) == 0);

	if (hwm == 0) {
	/* first use of single indirect */
	CBH_ALLOC(h->cbh_elements1, h);
	if (h->cbh_elements1 == NULL)
	return -ENOMEM;

	goto out;
	}

	hwm -= CBH_SIZE;
	if (hwm < CBH_SIZE * CBH_SIZE) {
	/* not filled double indirect */
	CBH_ALLOC(frag2, h);
	if (frag2 == NULL)
	return -ENOMEM;

	if (hwm == 0) {
	/* first use of double indirect */
	CBH_ALLOC(h->cbh_elements2, h);
	if (h->cbh_elements2 == NULL) {
	CBH_FREE(frag2);
	return -ENOMEM;
	}
	}

	h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
	goto out;
	}

	hwm -= CBH_SIZE * CBH_SIZE;
	#if (CBH_SHIFT * 3 < 32)
	if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
	/* filled triple indirect */
	return -ENOMEM;
	}
	#endif
	CBH_ALLOC(frag2, h);
	if (frag2 == NULL)
	return -ENOMEM;

	if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
	/* first use of this 2nd level index */
	CBH_ALLOC(frag1, h);
	if (frag1 == NULL) {
	CBH_FREE(frag2);
	return -ENOMEM;
	}
	}

	if (hwm == 0) {
	/* first use of triple indirect */
	CBH_ALLOC(h->cbh_elements3, h);
	if (h->cbh_elements3 == NULL) {
	CBH_FREE(frag2);
	CBH_FREE(frag1);
	return -ENOMEM;
	}
	}

	if (frag1 != NULL) {
	LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
	h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
	} else {
	frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
	LASSERT(frag1 != NULL);
	}

	frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;

	out:
	h->cbh_hwm += CBH_SIZE;
	return 0;
	}

	/**
	* Creates and initializes a binary heap instance.
	*
	* \param[in] ops The operations to be used
	* \param[in] flags The heap flags
	* \parm[in] count The initial heap capacity in # of elements
	* \param[in] arg An optional private argument
	* \param[in] cptab The CPT table this heap instance will operate over
	* \param[in] cptid The CPT id of \a cptab this heap instance will operate over
	*
	* \retval valid-pointer A newly-created and initialized binary heap object
	* \retval NULL error
	*/
	cfs_binheap_t *
	cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
	unsigned count, void arg, struct cfs_cpt_table cptab,
	int cptid)
	{
	cfs_binheap_t *h;

	LASSERT(ops != NULL);
	LASSERT(ops->hop_compare != NULL);
	LASSERT(cptab != NULL);
	LASSERT(cptid == CFS_CPT_ANY \|\|
	(cptid >= 0 && cptid < cptab->ctb_nparts));

	LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
	if (h == NULL)
	return NULL;

	h->cbh_ops = ops;
	h->cbh_nelements = 0;
	h->cbh_hwm = 0;
	h->cbh_private = arg;
	h->cbh_flags = flags & (~CBH_FLAG_ATOMIC_GROW);
	h->cbh_cptab = cptab;
	h->cbh_cptid = cptid;

	while (h->cbh_hwm < count) { /* preallocate */
	if (cfs_binheap_grow(h) != 0) {
	cfs_binheap_destroy(h);
	return NULL;
	}
	}

	h->cbh_flags \|= flags & CBH_FLAG_ATOMIC_GROW;

	return h;
	}
	EXPORT_SYMBOL(cfs_binheap_create);

	/**
	* Releases all resources associated with a binary heap instance.
	*
	* Deallocates memory for all indirection levels and the binary heap object
	* itself.
	*
	* \param[in] h The binary heap object
	*/
	void
	cfs_binheap_destroy(cfs_binheap_t *h)
	{
	int idx0;
	int idx1;
	int n;

	LASSERT(h != NULL);

	n = h->cbh_hwm;

	if (n > 0) {
	CBH_FREE(h->cbh_elements1);
	n -= CBH_SIZE;
	}

	if (n > 0) {
	for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
	CBH_FREE(h->cbh_elements2[idx0]);
	n -= CBH_SIZE;
	}

	CBH_FREE(h->cbh_elements2);
	}

	if (n > 0) {
	for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {

	for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
	CBH_FREE(h->cbh_elements3[idx0][idx1]);
	n -= CBH_SIZE;
	}

	CBH_FREE(h->cbh_elements3[idx0]);
	}

	CBH_FREE(h->cbh_elements3);
	}

	LIBCFS_FREE(h, sizeof(*h));
	}
	EXPORT_SYMBOL(cfs_binheap_destroy);

	/**
	* Obtains a double pointer to a heap element, given its index into the binary
	* tree.
	*
	* \param[in] h The binary heap instance
	* \param[in] idx The requested node's index
	*
	* \retval valid-pointer A double pointer to a heap pointer entry
	*/
	static cfs_binheap_node_t **
	cfs_binheap_pointer(cfs_binheap_t *h, unsigned int idx)
	{
	if (idx < CBH_SIZE)
	return &(h->cbh_elements1[idx]);

	idx -= CBH_SIZE;
	if (idx < CBH_SIZE * CBH_SIZE)
	return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);

	idx -= CBH_SIZE * CBH_SIZE;
	return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
	[(idx >> CBH_SHIFT) & CBH_MASK]\
	[idx & CBH_MASK]);
	}

	/**
	* Obtains a pointer to a heap element, given its index into the binary tree.
	*
	* \param[in] h The binary heap
	* \param[in] idx The requested node's index
	*
	* \retval valid-pointer The requested heap node
	* \retval NULL Supplied index is out of bounds
	*/
	cfs_binheap_node_t *
	cfs_binheap_find(cfs_binheap_t *h, unsigned int idx)
	{
	if (idx >= h->cbh_nelements)
	return NULL;

	return *cfs_binheap_pointer(h, idx);
	}
	EXPORT_SYMBOL(cfs_binheap_find);

	/**
	* Moves a node upwards, towards the root of the binary tree.
	*
	* \param[in] h The heap
	* \param[in] e The node
	*
	* \retval 1 The position of \a e in the tree was changed at least once
	* \retval 0 The position of \a e in the tree was not changed
	*/
	static int
	cfs_binheap_bubble(cfs_binheap_t h, cfs_binheap_node_t e)
	{
	unsigned int cur_idx = e->chn_index;
	cfs_binheap_node_t **cur_ptr;
	unsigned int parent_idx;
	cfs_binheap_node_t **parent_ptr;
	int did_sth = 0;

	cur_ptr = cfs_binheap_pointer(h, cur_idx);
	LASSERT(*cur_ptr == e);

	while (cur_idx > 0) {
	parent_idx = (cur_idx - 1) >> 1;

	parent_ptr = cfs_binheap_pointer(h, parent_idx);
	LASSERT((*parent_ptr)->chn_index == parent_idx);

	if (h->cbh_ops->hop_compare(*parent_ptr, e))
	break;

	(*parent_ptr)->chn_index = cur_idx;
	cur_ptr = parent_ptr;
	cur_ptr = parent_ptr;
	cur_idx = parent_idx;
	did_sth = 1;
	}

	e->chn_index = cur_idx;
	*cur_ptr = e;

	return did_sth;
	}

	/**
	* Moves a node downwards, towards the last level of the binary tree.
	*
	* \param[in] h The heap
	* \param[in] e The node
	*
	* \retval 1 The position of \a e in the tree was changed at least once
	* \retval 0 The position of \a e in the tree was not changed
	*/
	static int
	cfs_binheap_sink(cfs_binheap_t h, cfs_binheap_node_t e)
	{
	unsigned int n = h->cbh_nelements;
	unsigned int child_idx;
	cfs_binheap_node_t **child_ptr;
	cfs_binheap_node_t *child;
	unsigned int child2_idx;
	cfs_binheap_node_t **child2_ptr;
	cfs_binheap_node_t *child2;
	unsigned int cur_idx;
	cfs_binheap_node_t **cur_ptr;
	int did_sth = 0;

	cur_idx = e->chn_index;
	cur_ptr = cfs_binheap_pointer(h, cur_idx);
	LASSERT(*cur_ptr == e);

	while (cur_idx < n) {
	child_idx = (cur_idx << 1) + 1;
	if (child_idx >= n)
	break;

	child_ptr = cfs_binheap_pointer(h, child_idx);
	child = *child_ptr;

	child2_idx = child_idx + 1;
	if (child2_idx < n) {
	child2_ptr = cfs_binheap_pointer(h, child2_idx);
	child2 = *child2_ptr;

	if (h->cbh_ops->hop_compare(child2, child)) {
	child_idx = child2_idx;
	child_ptr = child2_ptr;
	child = child2;
	}
	}

	LASSERT(child->chn_index == child_idx);

	if (h->cbh_ops->hop_compare(e, child))
	break;

	child->chn_index = cur_idx;
	*cur_ptr = child;
	cur_ptr = child_ptr;
	cur_idx = child_idx;
	did_sth = 1;
	}

	e->chn_index = cur_idx;
	*cur_ptr = e;

	return did_sth;
	}

	/**
	* Sort-inserts a node into the binary heap.
	*
	* \param[in] h The heap
	* \param[in] e The node
	*
	* \retval 0 Element inserted successfully
	* \retval != 0 error
	*/
	int
	cfs_binheap_insert(cfs_binheap_t h, cfs_binheap_node_t e)
	{
	cfs_binheap_node_t **new_ptr;
	unsigned int new_idx = h->cbh_nelements;
	int rc;

	if (new_idx == h->cbh_hwm) {
	rc = cfs_binheap_grow(h);
	if (rc != 0)
	return rc;
	}

	if (h->cbh_ops->hop_enter) {
	rc = h->cbh_ops->hop_enter(h, e);
	if (rc != 0)
	return rc;
	}

	e->chn_index = new_idx;
	new_ptr = cfs_binheap_pointer(h, new_idx);
	h->cbh_nelements++;
	*new_ptr = e;

	cfs_binheap_bubble(h, e);

	return 0;
	}
	EXPORT_SYMBOL(cfs_binheap_insert);

	/**
	* Removes a node from the binary heap.
	*
	* \param[in] h The heap
	* \param[in] e The node
	*/
	void
	cfs_binheap_remove(cfs_binheap_t h, cfs_binheap_node_t e)
	{
	unsigned int n = h->cbh_nelements;
	unsigned int cur_idx = e->chn_index;
	cfs_binheap_node_t **cur_ptr;
	cfs_binheap_node_t *last;

	LASSERT(cur_idx != CBH_POISON);
	LASSERT(cur_idx < n);

	cur_ptr = cfs_binheap_pointer(h, cur_idx);
	LASSERT(*cur_ptr == e);

	n--;
	last = *cfs_binheap_pointer(h, n);
	h->cbh_nelements = n;
	if (last == e)
	return;

	last->chn_index = cur_idx;
	*cur_ptr = last;
	if (!cfs_binheap_bubble(h, *cur_ptr))
	cfs_binheap_sink(h, *cur_ptr);

	e->chn_index = CBH_POISON;
	if (h->cbh_ops->hop_exit)
	h->cbh_ops->hop_exit(h, e);
	}
	EXPORT_SYMBOL(cfs_binheap_remove);

	/** @} heap */