diff options
Diffstat (limited to 'drivers/staging/lustre/lustre/libcfs/heap.c')
-rw-r--r-- | drivers/staging/lustre/lustre/libcfs/heap.c | 475 |
1 files changed, 0 insertions, 475 deletions
diff --git a/drivers/staging/lustre/lustre/libcfs/heap.c b/drivers/staging/lustre/lustre/libcfs/heap.c deleted file mode 100644 index bf6d0b91c35f..000000000000 --- a/drivers/staging/lustre/lustre/libcfs/heap.c +++ /dev/null @@ -1,475 +0,0 @@ -/* - * 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 */ |