[deliverable/linux.git] / drivers / staging / lustre / lustre / libcfs / heap.c

/*
 * 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 "../../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 */
Commit	Line	Data
d7e09d03 PT	1	/*
	2	* GPL HEADER START
	3	*
	4	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	5	*
	6	* This program is free software; you can redistribute it and/or modify
	7	* it under the terms of the GNU General Public License version 2 only,
	8	* as published by the Free Software Foundation.
	9
	10	* This program is distributed in the hope that it will be useful,
	11	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	13	* GNU General Public License version 2 for more details. A copy is
	14	* included in the COPYING file that accompanied this code.
	15
	16	* You should have received a copy of the GNU General Public License
	17	* along with this program; if not, write to the Free Software
	18	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
	19	*
	20	* GPL HEADER END
	21	*/
	22	/*
	23	* Copyright (c) 2011 Intel Corporation
	24	*/
	25	/*
	26	* libcfs/libcfs/heap.c
	27	*
	28	* Author: Eric Barton <eeb@whamcloud.com>
	29	* Liang Zhen <liang@whamcloud.com>
	30	*/
	31	/** \addtogroup heap
	32	*
	33	* @{
	34	*/
	35
	36	#define DEBUG_SUBSYSTEM S_LNET
	37
9fdaf8c0	38	#include "../../include/linux/libcfs/libcfs.h"
d7e09d03 PT	39
	40	#define CBH_ALLOC(ptr, h) \
	41	do { \
	42	if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
	43	LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, h->cbh_cptid, \
	44	CBH_NOB, GFP_ATOMIC); \
	45	else \
	46	LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid, \
	47	CBH_NOB); \
	48	} while (0)
	49
	50	#define CBH_FREE(ptr) LIBCFS_FREE(ptr, CBH_NOB)
	51
	52	/**
	53	* Grows the capacity of a binary heap so that it can handle a larger number of
	54	* \e cfs_binheap_node_t objects.
	55	*
	56	* \param[in] h The binary heap
	57	*
	58	* \retval 0 Successfully grew the heap
	59	* \retval -ENOMEM OOM error
	60	*/
	61	static int
	62	cfs_binheap_grow(cfs_binheap_t *h)
	63	{
	64	cfs_binheap_node_t ***frag1 = NULL;
	65	cfs_binheap_node_t **frag2;
	66	int hwm = h->cbh_hwm;
	67
	68	/* need a whole new chunk of pointers */
	69	LASSERT((h->cbh_hwm & CBH_MASK) == 0);
	70
	71	if (hwm == 0) {
	72	/* first use of single indirect */
	73	CBH_ALLOC(h->cbh_elements1, h);
	74	if (h->cbh_elements1 == NULL)
	75	return -ENOMEM;
	76
	77	goto out;
	78	}
	79
	80	hwm -= CBH_SIZE;
	81	if (hwm < CBH_SIZE * CBH_SIZE) {
	82	/* not filled double indirect */
	83	CBH_ALLOC(frag2, h);
	84	if (frag2 == NULL)
	85	return -ENOMEM;
	86
	87	if (hwm == 0) {
	88	/* first use of double indirect */
	89	CBH_ALLOC(h->cbh_elements2, h);
	90	if (h->cbh_elements2 == NULL) {
	91	CBH_FREE(frag2);
	92	return -ENOMEM;
	93	}
	94	}
	95
	96	h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
	97	goto out;
	98	}
	99
	100	hwm -= CBH_SIZE * CBH_SIZE;
	101	#if (CBH_SHIFT * 3 < 32)
	102	if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
103	/* filled triple indirect */
104	return -ENOMEM;
105	}
106	#endif
107	CBH_ALLOC(frag2, h);
108	if (frag2 == NULL)
109	return -ENOMEM;
110
111	if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
112	/* first use of this 2nd level index */
113	CBH_ALLOC(frag1, h);
114	if (frag1 == NULL) {
115	CBH_FREE(frag2);
116	return -ENOMEM;
117	}
118	}
119
120	if (hwm == 0) {
121	/* first use of triple indirect */
122	CBH_ALLOC(h->cbh_elements3, h);
123	if (h->cbh_elements3 == NULL) {
124	CBH_FREE(frag2);
125	CBH_FREE(frag1);
126	return -ENOMEM;
127	}
128	}
129
130	if (frag1 != NULL) {
131	LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
132	h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
133	} else {
134	frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
135	LASSERT(frag1 != NULL);
136	}
137
138	frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
139
140	out:
141	h->cbh_hwm += CBH_SIZE;
142	return 0;
143	}
144
145	/**
146	* Creates and initializes a binary heap instance.
147	*
148	* \param[in] ops The operations to be used
149	* \param[in] flags The heap flags
150	* \parm[in] count The initial heap capacity in # of elements
151	* \param[in] arg An optional private argument
152	* \param[in] cptab The CPT table this heap instance will operate over
153	* \param[in] cptid The CPT id of \a cptab this heap instance will operate over
154	*
155	* \retval valid-pointer A newly-created and initialized binary heap object
156	* \retval NULL error
157	*/
158	cfs_binheap_t *
159	cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
160	unsigned count, void arg, struct cfs_cpt_table cptab,
161	int cptid)
162	{
163	cfs_binheap_t *h;
164
165	LASSERT(ops != NULL);
166	LASSERT(ops->hop_compare != NULL);
167	LASSERT(cptab != NULL);
168	LASSERT(cptid == CFS_CPT_ANY \|\|
169	(cptid >= 0 && cptid < cptab->ctb_nparts));
170
171	LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
172	if (h == NULL)
173	return NULL;
174
175	h->cbh_ops = ops;
176	h->cbh_nelements = 0;
177	h->cbh_hwm = 0;
178	h->cbh_private = arg;
179	h->cbh_flags = flags & (~CBH_FLAG_ATOMIC_GROW);
180	h->cbh_cptab = cptab;
181	h->cbh_cptid = cptid;
182
183	while (h->cbh_hwm < count) { /* preallocate */
184	if (cfs_binheap_grow(h) != 0) {
185	cfs_binheap_destroy(h);
186	return NULL;
187	}
188	}
189
190	h->cbh_flags \|= flags & CBH_FLAG_ATOMIC_GROW;
191
192	return h;
193	}
194	EXPORT_SYMBOL(cfs_binheap_create);
195
196	/**
197	* Releases all resources associated with a binary heap instance.
198	*
199	* Deallocates memory for all indirection levels and the binary heap object
200	* itself.
201	*
202	* \param[in] h The binary heap object
203	*/
204	void
205	cfs_binheap_destroy(cfs_binheap_t *h)
206	{
207	int idx0;
208	int idx1;
209	int n;
210
211	LASSERT(h != NULL);
212
213	n = h->cbh_hwm;
214
215	if (n > 0) {
216	CBH_FREE(h->cbh_elements1);
217	n -= CBH_SIZE;
218	}
219
220	if (n > 0) {
221	for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
222	CBH_FREE(h->cbh_elements2[idx0]);
223	n -= CBH_SIZE;
224	}
225
226	CBH_FREE(h->cbh_elements2);
227	}
228
229	if (n > 0) {
230	for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
231
232	for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
233	CBH_FREE(h->cbh_elements3[idx0][idx1]);
234	n -= CBH_SIZE;
235	}
236
237	CBH_FREE(h->cbh_elements3[idx0]);
238	}
239
240	CBH_FREE(h->cbh_elements3);
241	}
242
243	LIBCFS_FREE(h, sizeof(*h));
244	}
245	EXPORT_SYMBOL(cfs_binheap_destroy);
246
247	/**
248	* Obtains a double pointer to a heap element, given its index into the binary
249	* tree.
250	*
251	* \param[in] h The binary heap instance
252	* \param[in] idx The requested node's index
253	*
254	* \retval valid-pointer A double pointer to a heap pointer entry
255	*/
256	static cfs_binheap_node_t **
257	cfs_binheap_pointer(cfs_binheap_t *h, unsigned int idx)
258	{
259	if (idx < CBH_SIZE)
260	return &(h->cbh_elements1[idx]);
261
262	idx -= CBH_SIZE;
263	if (idx < CBH_SIZE * CBH_SIZE)
264	return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
265
266	idx -= CBH_SIZE * CBH_SIZE;
267	return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
268	[(idx >> CBH_SHIFT) & CBH_MASK]\
269	[idx & CBH_MASK]);
270	}
271
272	/**
273	* Obtains a pointer to a heap element, given its index into the binary tree.
274	*
275	* \param[in] h The binary heap
276	* \param[in] idx The requested node's index
277	*
278	* \retval valid-pointer The requested heap node
279	* \retval NULL Supplied index is out of bounds
280	*/
281	cfs_binheap_node_t *
282	cfs_binheap_find(cfs_binheap_t *h, unsigned int idx)
283	{
284	if (idx >= h->cbh_nelements)
285	return NULL;
286
287	return *cfs_binheap_pointer(h, idx);
288	}
289	EXPORT_SYMBOL(cfs_binheap_find);
290
291	/**
292	* Moves a node upwards, towards the root of the binary tree.
293	*
294	* \param[in] h The heap
295	* \param[in] e The node
296	*
297	* \retval 1 The position of \a e in the tree was changed at least once
298	* \retval 0 The position of \a e in the tree was not changed
299	*/
300	static int
301	cfs_binheap_bubble(cfs_binheap_t h, cfs_binheap_node_t e)
302	{
303	unsigned int cur_idx = e->chn_index;
304	cfs_binheap_node_t **cur_ptr;
305	unsigned int parent_idx;
306	cfs_binheap_node_t **parent_ptr;
307	int did_sth = 0;
308
309	cur_ptr = cfs_binheap_pointer(h, cur_idx);
310	LASSERT(*cur_ptr == e);
311
312	while (cur_idx > 0) {
313	parent_idx = (cur_idx - 1) >> 1;
314
315	parent_ptr = cfs_binheap_pointer(h, parent_idx);
316	LASSERT((*parent_ptr)->chn_index == parent_idx);
317
318	if (h->cbh_ops->hop_compare(*parent_ptr, e))
319	break;
320
321	(*parent_ptr)->chn_index = cur_idx;
322	cur_ptr = parent_ptr;
323	cur_ptr = parent_ptr;
324	cur_idx = parent_idx;
325	did_sth = 1;
326	}
327
328	e->chn_index = cur_idx;
329	*cur_ptr = e;
330
331	return did_sth;
332	}
333
334	/**
335	* Moves a node downwards, towards the last level of the binary tree.
336	*
337	* \param[in] h The heap
338	* \param[in] e The node
339	*
340	* \retval 1 The position of \a e in the tree was changed at least once
341	* \retval 0 The position of \a e in the tree was not changed
342	*/
343	static int
344	cfs_binheap_sink(cfs_binheap_t h, cfs_binheap_node_t e)
345	{
346	unsigned int n = h->cbh_nelements;
347	unsigned int child_idx;
348	cfs_binheap_node_t **child_ptr;
349	cfs_binheap_node_t *child;
350	unsigned int child2_idx;
351	cfs_binheap_node_t **child2_ptr;
352	cfs_binheap_node_t *child2;
353	unsigned int cur_idx;
354	cfs_binheap_node_t **cur_ptr;
355	int did_sth = 0;
356
357	cur_idx = e->chn_index;
358	cur_ptr = cfs_binheap_pointer(h, cur_idx);
359	LASSERT(*cur_ptr == e);
360
361	while (cur_idx < n) {
362	child_idx = (cur_idx << 1) + 1;
363	if (child_idx >= n)
364	break;
365
366	child_ptr = cfs_binheap_pointer(h, child_idx);
367	child = *child_ptr;
368
369	child2_idx = child_idx + 1;
370	if (child2_idx < n) {
371	child2_ptr = cfs_binheap_pointer(h, child2_idx);
372	child2 = *child2_ptr;
373
374	if (h->cbh_ops->hop_compare(child2, child)) {
375	child_idx = child2_idx;
376	child_ptr = child2_ptr;
377	child = child2;
378	}
379	}
380
381	LASSERT(child->chn_index == child_idx);
382
383	if (h->cbh_ops->hop_compare(e, child))
384	break;
385
386	child->chn_index = cur_idx;
387	*cur_ptr = child;
388	cur_ptr = child_ptr;
389	cur_idx = child_idx;
390	did_sth = 1;
391	}
392
393	e->chn_index = cur_idx;
394	*cur_ptr = e;
395
396	return did_sth;
397	}
398
399	/**
400	* Sort-inserts a node into the binary heap.
401	*
402	* \param[in] h The heap
403	* \param[in] e The node
404	*
405	* \retval 0 Element inserted successfully
406	* \retval != 0 error
407	*/
408	int
409	cfs_binheap_insert(cfs_binheap_t h, cfs_binheap_node_t e)
410	{
411	cfs_binheap_node_t **new_ptr;
412	unsigned int new_idx = h->cbh_nelements;
413	int rc;
414
415	if (new_idx == h->cbh_hwm) {
416	rc = cfs_binheap_grow(h);
417	if (rc != 0)
418	return rc;
419	}
420
421	if (h->cbh_ops->hop_enter) {
422	rc = h->cbh_ops->hop_enter(h, e);
423	if (rc != 0)
424	return rc;
425	}
426
427	e->chn_index = new_idx;
428	new_ptr = cfs_binheap_pointer(h, new_idx);
429	h->cbh_nelements++;
430	*new_ptr = e;
431
432	cfs_binheap_bubble(h, e);
433
434	return 0;
435	}
436	EXPORT_SYMBOL(cfs_binheap_insert);
437
438	/**
439	* Removes a node from the binary heap.
440	*
441	* \param[in] h The heap
442	* \param[in] e The node
443	*/
444	void
445	cfs_binheap_remove(cfs_binheap_t h, cfs_binheap_node_t e)
446	{
447	unsigned int n = h->cbh_nelements;
448	unsigned int cur_idx = e->chn_index;
449	cfs_binheap_node_t **cur_ptr;
450	cfs_binheap_node_t *last;
451
452	LASSERT(cur_idx != CBH_POISON);
453	LASSERT(cur_idx < n);
454
455	cur_ptr = cfs_binheap_pointer(h, cur_idx);
456	LASSERT(*cur_ptr == e);
457
458	n--;
459	last = *cfs_binheap_pointer(h, n);
460	h->cbh_nelements = n;
461	if (last == e)
462	return;
463
464	last->chn_index = cur_idx;
465	*cur_ptr = last;
466	if (!cfs_binheap_bubble(h, *cur_ptr))
467	cfs_binheap_sink(h, *cur_ptr);
468
469	e->chn_index = CBH_POISON;
470	if (h->cbh_ops->hop_exit)
471	h->cbh_ops->hop_exit(h, e);
472	}
473	EXPORT_SYMBOL(cfs_binheap_remove);
474
475	/** @} heap */