4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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.
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
23 * Copyright (c) 2011 Intel Corporation
26 * libcfs/libcfs/heap.c
28 * Author: Eric Barton <eeb@whamcloud.com>
29 * Liang Zhen <liang@whamcloud.com>
36 #define DEBUG_SUBSYSTEM S_LNET
38 #include <libcfs/libcfs.h>
40 #define CBH_ALLOC(ptr, h) \
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); \
46 LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid, \
50 #define CBH_FREE(ptr) LIBCFS_FREE(ptr, CBH_NOB)
53 * Grows the capacity of a binary heap so that it can handle a larger number of
54 * \e cfs_binheap_node_t objects.
56 * \param[in] h The binary heap
58 * \retval 0 Successfully grew the heap
59 * \retval -ENOMEM OOM error
62 cfs_binheap_grow(cfs_binheap_t *h)
64 cfs_binheap_node_t ***frag1 = NULL;
65 cfs_binheap_node_t **frag2;
68 /* need a whole new chunk of pointers */
69 LASSERT((h->cbh_hwm & CBH_MASK) == 0);
72 /* first use of single indirect */
73 CBH_ALLOC(h->cbh_elements1, h);
74 if (h->cbh_elements1 == NULL)
81 if (hwm < CBH_SIZE * CBH_SIZE) {
82 /* not filled double indirect */
88 /* first use of double indirect */
89 CBH_ALLOC(h->cbh_elements2, h);
90 if (h->cbh_elements2 == NULL) {
96 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
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 */
111 if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
112 /* first use of this 2nd level index */
121 /* first use of triple indirect */
122 CBH_ALLOC(h->cbh_elements3, h);
123 if (h->cbh_elements3 == NULL) {
131 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
132 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
134 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
135 LASSERT(frag1 != NULL);
138 frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
141 h->cbh_hwm += CBH_SIZE;
146 * Creates and initializes a binary heap instance.
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
155 * \retval valid-pointer A newly-created and initialized binary heap object
159 cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
160 unsigned count, void *arg, struct cfs_cpt_table *cptab,
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));
171 LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
176 h->cbh_nelements = 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;
183 while (h->cbh_hwm < count) { /* preallocate */
184 if (cfs_binheap_grow(h) != 0) {
185 cfs_binheap_destroy(h);
190 h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
194 EXPORT_SYMBOL(cfs_binheap_create);
197 * Releases all resources associated with a binary heap instance.
199 * Deallocates memory for all indirection levels and the binary heap object
202 * \param[in] h The binary heap object
205 cfs_binheap_destroy(cfs_binheap_t *h)
216 CBH_FREE(h->cbh_elements1);
221 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
222 CBH_FREE(h->cbh_elements2[idx0]);
226 CBH_FREE(h->cbh_elements2);
230 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
232 for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
233 CBH_FREE(h->cbh_elements3[idx0][idx1]);
237 CBH_FREE(h->cbh_elements3[idx0]);
240 CBH_FREE(h->cbh_elements3);
243 LIBCFS_FREE(h, sizeof(*h));
245 EXPORT_SYMBOL(cfs_binheap_destroy);
248 * Obtains a double pointer to a heap element, given its index into the binary
251 * \param[in] h The binary heap instance
252 * \param[in] idx The requested node's index
254 * \retval valid-pointer A double pointer to a heap pointer entry
256 static cfs_binheap_node_t **
257 cfs_binheap_pointer(cfs_binheap_t *h, unsigned int idx)
260 return &(h->cbh_elements1[idx]);
263 if (idx < CBH_SIZE * CBH_SIZE)
264 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
266 idx -= CBH_SIZE * CBH_SIZE;
267 return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
268 [(idx >> CBH_SHIFT) & CBH_MASK]\
273 * Obtains a pointer to a heap element, given its index into the binary tree.
275 * \param[in] h The binary heap
276 * \param[in] idx The requested node's index
278 * \retval valid-pointer The requested heap node
279 * \retval NULL Supplied index is out of bounds
282 cfs_binheap_find(cfs_binheap_t *h, unsigned int idx)
284 if (idx >= h->cbh_nelements)
287 return *cfs_binheap_pointer(h, idx);
289 EXPORT_SYMBOL(cfs_binheap_find);
292 * Moves a node upwards, towards the root of the binary tree.
294 * \param[in] h The heap
295 * \param[in] e The node
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
301 cfs_binheap_bubble(cfs_binheap_t *h, cfs_binheap_node_t *e)
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;
309 cur_ptr = cfs_binheap_pointer(h, cur_idx);
310 LASSERT(*cur_ptr == e);
312 while (cur_idx > 0) {
313 parent_idx = (cur_idx - 1) >> 1;
315 parent_ptr = cfs_binheap_pointer(h, parent_idx);
316 LASSERT((*parent_ptr)->chn_index == parent_idx);
318 if (h->cbh_ops->hop_compare(*parent_ptr, e))
321 (*parent_ptr)->chn_index = cur_idx;
322 *cur_ptr = *parent_ptr;
323 cur_ptr = parent_ptr;
324 cur_idx = parent_idx;
328 e->chn_index = cur_idx;
335 * Moves a node downwards, towards the last level of the binary tree.
337 * \param[in] h The heap
338 * \param[in] e The node
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
344 cfs_binheap_sink(cfs_binheap_t *h, cfs_binheap_node_t *e)
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;
357 cur_idx = e->chn_index;
358 cur_ptr = cfs_binheap_pointer(h, cur_idx);
359 LASSERT(*cur_ptr == e);
361 while (cur_idx < n) {
362 child_idx = (cur_idx << 1) + 1;
366 child_ptr = cfs_binheap_pointer(h, child_idx);
369 child2_idx = child_idx + 1;
370 if (child2_idx < n) {
371 child2_ptr = cfs_binheap_pointer(h, child2_idx);
372 child2 = *child2_ptr;
374 if (h->cbh_ops->hop_compare(child2, child)) {
375 child_idx = child2_idx;
376 child_ptr = child2_ptr;
381 LASSERT(child->chn_index == child_idx);
383 if (h->cbh_ops->hop_compare(e, child))
386 child->chn_index = cur_idx;
393 e->chn_index = cur_idx;
400 * Sort-inserts a node into the binary heap.
402 * \param[in] h The heap
403 * \param[in] e The node
405 * \retval 0 Element inserted successfully
409 cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e)
411 cfs_binheap_node_t **new_ptr;
412 unsigned int new_idx = h->cbh_nelements;
415 if (new_idx == h->cbh_hwm) {
416 rc = cfs_binheap_grow(h);
421 if (h->cbh_ops->hop_enter) {
422 rc = h->cbh_ops->hop_enter(h, e);
427 e->chn_index = new_idx;
428 new_ptr = cfs_binheap_pointer(h, new_idx);
432 cfs_binheap_bubble(h, e);
436 EXPORT_SYMBOL(cfs_binheap_insert);
439 * Removes a node from the binary heap.
441 * \param[in] h The heap
442 * \param[in] e The node
445 cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e)
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;
452 LASSERT(cur_idx != CBH_POISON);
453 LASSERT(cur_idx < n);
455 cur_ptr = cfs_binheap_pointer(h, cur_idx);
456 LASSERT(*cur_ptr == e);
459 last = *cfs_binheap_pointer(h, n);
460 h->cbh_nelements = n;
464 last->chn_index = cur_idx;
466 cfs_binheap_relocate(h, *cur_ptr);
468 e->chn_index = CBH_POISON;
469 if (h->cbh_ops->hop_exit)
470 h->cbh_ops->hop_exit(h, e);
472 EXPORT_SYMBOL(cfs_binheap_remove);
475 * Relocate a node in the binary heap.
476 * Should be called whenever a node's values
477 * which affects its ranking are changed.
479 * \param[in] h The heap
480 * \param[in] e The node
483 cfs_binheap_relocate(cfs_binheap_t *h, cfs_binheap_node_t *e)
485 if (!cfs_binheap_bubble(h, e))
486 cfs_binheap_sink(h, e);
488 EXPORT_SYMBOL(cfs_binheap_relocate);