Whamcloud - gitweb
LU-398 libcfs: Add libcfs heap, a binary heap implementation
authorNikitas Angelinas <nikitas_angelinas@xyratex.com>
Tue, 30 Oct 2012 15:46:39 +0000 (15:46 +0000)
committerOleg Drokin <green@whamcloud.com>
Mon, 17 Dec 2012 05:12:29 +0000 (00:12 -0500)
The heap can be used to build and maintain sorted arrays and lists,
and prioritized queues of large numbers of elements, with minimal
insertion and removal time. The first user for the data structure are
NRS policies, which use it to maintain prioritized queues of RPCs at
PTLRPC services.

There is no 'search' operation, but the data type aims to be useful
in cases where performing searches on the data set is not required,
and instead the lowest priority element is usually removed from the
data set for consumption.

Original-author: Eric Barton <eeb@whamcloud.com>
Original-author: Liang Zhen <liang@whamcloud.com>
Signed-off-by: James Simmons <uja.ornl@gmail.com>
Signed-off-by: Nikitas Angelinas <nikitas_angelinas@xyratex.com>
Change-Id: Ifd293d0a8201e45bd6030d7a16ce0be691f79cb9
Oracle-bug-id: b=13634
Xyratex-bug-id: MRP-73
Reviewed-on: http://review.whamcloud.com/4412
Tested-by: Hudson
Reviewed-by: Liang Zhen <liang@whamcloud.com>
Tested-by: Maloo <whamcloud.maloo@gmail.com>
Reviewed-by: Oleg Drokin <green@whamcloud.com>
libcfs/include/libcfs/Makefile.am
libcfs/include/libcfs/libcfs.h
libcfs/include/libcfs/libcfs_heap.h [new file with mode: 0644]
libcfs/libcfs/Makefile.in
libcfs/libcfs/autoMakefile.am
libcfs/libcfs/heap.c [new file with mode: 0644]

index 645a02e..8ef76b7 100644 (file)
@@ -11,4 +11,4 @@ EXTRA_DIST = curproc.h libcfs_private.h libcfs.h list.h lltrace.h \
                libcfs_debug.h libcfsutil.h libcfs_ioctl.h \
                libcfs_pack.h libcfs_unpack.h libcfs_string.h \
                libcfs_kernelcomm.h libcfs_workitem.h lucache.h \
                libcfs_debug.h libcfsutil.h libcfs_ioctl.h \
                libcfs_pack.h libcfs_unpack.h libcfs_string.h \
                libcfs_kernelcomm.h libcfs_workitem.h lucache.h \
-               libcfs_fail.h params_tree.h libcfs_crypto.h
+               libcfs_fail.h params_tree.h libcfs_crypto.h libcfs_heap.h
index 37dd2f6..5b6cc66 100644 (file)
@@ -318,6 +318,7 @@ void cfs_get_random_bytes(void *buf, int size);
 #include <libcfs/libcfs_kernelcomm.h>
 #include <libcfs/libcfs_workitem.h>
 #include <libcfs/libcfs_hash.h>
 #include <libcfs/libcfs_kernelcomm.h>
 #include <libcfs/libcfs_workitem.h>
 #include <libcfs/libcfs_hash.h>
+#include <libcfs/libcfs_heap.h>
 #include <libcfs/libcfs_fail.h>
 #include <libcfs/params_tree.h>
 #include <libcfs/libcfs_crypto.h>
 #include <libcfs/libcfs_fail.h>
 #include <libcfs/params_tree.h>
 #include <libcfs/libcfs_crypto.h>
diff --git a/libcfs/include/libcfs/libcfs_heap.h b/libcfs/include/libcfs/libcfs_heap.h
new file mode 100644 (file)
index 0000000..40d4eda
--- /dev/null
@@ -0,0 +1,200 @@
+/*
+ * 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/include/libcfs/heap.h
+ *
+ * Author: Eric Barton <eeb@whamcloud.com>
+ *        Liang Zhen   <liang@whamcloud.com>
+ */
+
+#ifndef __LIBCFS_HEAP_H__
+#define __LIBCFS_HEAP_H__
+
+/** \defgroup heap Binary heap
+ *
+ * The binary heap is a scalable data structure created using a binary tree. It
+ * is capable of maintaining large sets of elements sorted usually by one or
+ * more element properties, but really based on anything that can be used as a
+ * binary predicate in order to determine the relevant ordering of any two nodes
+ * that belong to the set. There is no search operation, rather the intention is
+ * for the element of the lowest priority which will always be at the root of
+ * the tree (as this is an implementation of a min-heap) to be removed by users
+ * for consumption.
+ *
+ * Users of the heap should embed a \e cfs_binheap_node_t object instance on
+ * every object of the set that they wish the binary heap instance to handle,
+ * and (at a minimum) provide a cfs_binheap_ops_t::hop_compare() implementation
+ * which is used by the heap as the binary predicate during its internal sorting
+ * operations.
+ *
+ * The current implementation enforces no locking scheme, and so assumes the
+ * user caters for locking between calls to insert, delete and lookup
+ * operations. Since the only consumer for the data structure at this point
+ * are NRS policies, and these operate on a per-CPT basis, binary heap instances
+ * are tied to a specific CPT.
+ * @{
+ */
+
+/**
+ * Binary heap node.
+ *
+ * Objects of this type are embedded into objects of the ordered set that is to
+ * be maintained by a \e cfs_binheap_t instance.
+ */
+typedef struct {
+       /** Index into the binary tree */
+       unsigned int    chn_index;
+} cfs_binheap_node_t;
+
+#define CBH_SHIFT      9
+#define CBH_SIZE       (1 << CBH_SHIFT)                    /* # ptrs per level */
+#define CBH_MASK       (CBH_SIZE - 1)
+#define CBH_NOB        (CBH_SIZE * sizeof(cfs_binheap_node_t *))
+
+#define CBH_POISON     0xdeadbeef
+
+/**
+ * Binary heap flags.
+ */
+enum {
+       CBH_FLAG_ATOMIC_GROW    = 1,
+};
+
+struct cfs_binheap;
+
+/**
+ * Binary heap operations.
+ */
+typedef struct {
+       /**
+        * Called right before inserting a node into the binary heap.
+        *
+        * Implementing this operation is optional.
+        *
+        * \param[in] h The heap
+        * \param[in] e The node
+        *
+        * \retval 0 success
+        * \retval != 0 error
+        */
+       int             (*hop_enter)(struct cfs_binheap *h,
+                                    cfs_binheap_node_t *e);
+       /**
+        * Called right after removing a node from the binary heap.
+        *
+        * Implementing this operation is optional.
+        *
+        * \param[in] h The heap
+        * \param[in] e The node
+        */
+       void            (*hop_exit)(struct cfs_binheap *h,
+                                   cfs_binheap_node_t *e);
+       /**
+        * A binary predicate which is called during internal heap sorting
+        * operations, and used in order to determine the relevant ordering of
+        * two heap nodes.
+        *
+        * Implementing this operation is mandatory.
+        *
+        * \param[in] a The first heap node
+        * \param[in] b The second heap node
+        *
+        * \retval 0 Node a > node b
+        * \retval 1 Node a < node b
+        *
+        * \see cfs_binheap_bubble()
+        * \see cfs_biheap_sink()
+        */
+       int             (*hop_compare)(cfs_binheap_node_t *a,
+                                      cfs_binheap_node_t *b);
+} cfs_binheap_ops_t;
+
+/**
+ * Binary heap object.
+ *
+ * Sorts elements of type \e cfs_binheap_node_t
+ */
+typedef struct cfs_binheap {
+       /** Triple indirect */
+       cfs_binheap_node_t  ****cbh_elements3;
+       /** double indirect */
+       cfs_binheap_node_t   ***cbh_elements2;
+       /** single indirect */
+       cfs_binheap_node_t    **cbh_elements1;
+       /** # elements referenced */
+       unsigned int            cbh_nelements;
+       /** high water mark */
+       unsigned int            cbh_hwm;
+       /** user flags */
+       unsigned int            cbh_flags;
+       /** operations table */
+       cfs_binheap_ops_t      *cbh_ops;
+       /** private data */
+       void                   *cbh_private;
+       /** associated CPT table */
+       struct cfs_cpt_table   *cbh_cptab;
+       /** associated CPT id of this cfs_binheap_t::cbh_cptab */
+       int                     cbh_cptid;
+} cfs_binheap_t;
+
+void cfs_binheap_destroy(cfs_binheap_t *h);
+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_node_t *cfs_binheap_find(cfs_binheap_t *h, unsigned int idx);
+int cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e);
+void cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e);
+
+static inline int
+cfs_binheap_size(cfs_binheap_t *h)
+{
+       return h->cbh_nelements;
+}
+
+static inline int
+cfs_binheap_is_empty(cfs_binheap_t *h)
+{
+       return h->cbh_nelements == 0;
+}
+
+static inline cfs_binheap_node_t *
+cfs_binheap_root(cfs_binheap_t *h)
+{
+       return cfs_binheap_find(h, 0);
+}
+
+static inline cfs_binheap_node_t *
+cfs_binheap_remove_root(cfs_binheap_t *h)
+{
+       cfs_binheap_node_t *e = cfs_binheap_find(h, 0);
+
+       if (e != NULL)
+               cfs_binheap_remove(h, e);
+       return e;
+}
+
+/** @} heap */
+
+#endif /* __LIBCFS_HEAP_H__ */
index 4ad5b82..71852cc 100644 (file)
@@ -32,7 +32,7 @@ libcfs-linux-objs := $(addprefix linux/,$(libcfs-linux-objs))
 libcfs-all-objs := debug.o fail.o nidstrings.o lwt.o module.o tracefile.o \
                   watchdog.o libcfs_string.o hash.o kernel_user_comm.o \
                   prng.o workitem.o upcall_cache.o libcfs_cpu.o \
 libcfs-all-objs := debug.o fail.o nidstrings.o lwt.o module.o tracefile.o \
                   watchdog.o libcfs_string.o hash.o kernel_user_comm.o \
                   prng.o workitem.o upcall_cache.o libcfs_cpu.o \
-                  libcfs_mem.o libcfs_lock.o
+                  libcfs_mem.o libcfs_lock.o heap.o
 
 libcfs-objs := $(libcfs-linux-objs) $(libcfs-all-objs) $(libcfs-pclmul-obj)
 
 
 libcfs-objs := $(libcfs-linux-objs) $(libcfs-all-objs) $(libcfs-pclmul-obj)
 
index b7a41eb..989d47d 100644 (file)
@@ -47,7 +47,7 @@ libcfs_a_SOURCES= posix/posix-debug.c user-prim.c user-lock.c user-tcpip.c  \
                  prng.c user-bitops.c user-mem.c hash.c kernel_user_comm.c \
                  workitem.c fail.c libcfs_cpu.c libcfs_mem.c libcfs_lock.c \
                  posix/rbtree.c user-crypto.c posix/posix-crc32.c          \
                  prng.c user-bitops.c user-mem.c hash.c kernel_user_comm.c \
                  workitem.c fail.c libcfs_cpu.c libcfs_mem.c libcfs_lock.c \
                  posix/rbtree.c user-crypto.c posix/posix-crc32.c          \
-                 posix/posix-adler.c
+                 posix/posix-adler.c heap.c
 
 if ARCH_x86
 libcfs_a_SOURCES += user-crc32pclmul.c crc32-pclmul_asm.S
 
 if ARCH_x86
 libcfs_a_SOURCES += user-crc32pclmul.c crc32-pclmul_asm.S
@@ -77,7 +77,7 @@ nodist_libcfs_SOURCES = darwin/darwin-sync.c darwin/darwin-mem.c      \
        darwin/darwin-debug.c darwin/darwin-proc.c                      \
        darwin/darwin-tracefile.c darwin/darwin-module.c                \
        posix/posix-debug.c module.c tracefile.c nidstrings.c watchdog.c \
        darwin/darwin-debug.c darwin/darwin-proc.c                      \
        darwin/darwin-tracefile.c darwin/darwin-module.c                \
        posix/posix-debug.c module.c tracefile.c nidstrings.c watchdog.c \
-       kernel_user_comm.c hash.c posix/rbtree.c
+       kernel_user_comm.c hash.c posix/rbtree.c heap.c
 
 libcfs_CFLAGS := $(EXTRA_KCFLAGS)
 libcfs_LDFLAGS := $(EXTRA_KLDFLAGS)
 
 libcfs_CFLAGS := $(EXTRA_KCFLAGS)
 libcfs_LDFLAGS := $(EXTRA_KLDFLAGS)
@@ -96,5 +96,5 @@ install-data-hook: $(install_data_hook)
 MOSTLYCLEANFILES := @MOSTLYCLEANFILES@ linux-*.c linux/*.o darwin/*.o libcfs
 EXTRA_DIST := $(libcfs-all-objs:%.o=%.c) Info.plist tracefile.h prng.c \
              user-lock.c user-tcpip.c user-bitops.c user-prim.c workitem.c \
 MOSTLYCLEANFILES := @MOSTLYCLEANFILES@ linux-*.c linux/*.o darwin/*.o libcfs
 EXTRA_DIST := $(libcfs-all-objs:%.o=%.c) Info.plist tracefile.h prng.c \
              user-lock.c user-tcpip.c user-bitops.c user-prim.c workitem.c \
-             user-mem.c kernel_user_comm.c fail.c libcfs_cpu.c \
+             user-mem.c kernel_user_comm.c fail.c libcfs_cpu.c heap.c \
              libcfs_mem.c libcfs_lock.c linux/linux-tracefile.h
              libcfs_mem.c libcfs_lock.c linux/linux-tracefile.h
diff --git a/libcfs/libcfs/heap.c b/libcfs/libcfs/heap.c
new file mode 100644 (file)
index 0000000..3a4f168
--- /dev/null
@@ -0,0 +1,475 @@
+/*
+ * 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 <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, CFS_ALLOC_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 */