| /* |
| * 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 */ |