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) \
43 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
44 LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, \
45 h->cbh_cptid, CBH_NOB, \
48 LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, \
49 h->cbh_cptid, CBH_NOB); \
51 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
52 LIBCFS_ALLOC_ATOMIC((ptr), CBH_NOB); \
54 LIBCFS_ALLOC((ptr), CBH_NOB); \
58 #define CBH_FREE(ptr) LIBCFS_FREE(ptr, CBH_NOB)
61 * Grows the capacity of a binary heap so that it can handle a larger number of
62 * \e struct cfs_binheap_node objects.
64 * \param[in] h The binary heap
66 * \retval 0 Successfully grew the heap
67 * \retval -ENOMEM OOM error
70 cfs_binheap_grow(struct cfs_binheap *h)
72 struct cfs_binheap_node ***frag1 = NULL;
73 struct cfs_binheap_node **frag2;
76 /* need a whole new chunk of pointers */
77 LASSERT((h->cbh_hwm & CBH_MASK) == 0);
80 /* first use of single indirect */
81 CBH_ALLOC(h->cbh_elements1, h);
82 if (h->cbh_elements1 == NULL)
89 if (hwm < CBH_SIZE * CBH_SIZE) {
90 /* not filled double indirect */
96 /* first use of double indirect */
97 CBH_ALLOC(h->cbh_elements2, h);
98 if (h->cbh_elements2 == NULL) {
104 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
108 hwm -= CBH_SIZE * CBH_SIZE;
109 #if (CBH_SHIFT * 3 < 32)
110 if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
111 /* filled triple indirect */
119 if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
120 /* first use of this 2nd level index */
129 /* first use of triple indirect */
130 CBH_ALLOC(h->cbh_elements3, h);
131 if (h->cbh_elements3 == NULL) {
139 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
140 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
142 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
143 LASSERT(frag1 != NULL);
146 frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
149 h->cbh_hwm += CBH_SIZE;
154 * Creates and initializes a binary heap instance.
156 * \param[in] ops The operations to be used
157 * \param[in] flags The heap flags
158 * \parm[in] count The initial heap capacity in # of elements
159 * \param[in] arg An optional private argument
160 * \param[in] cptab The CPT table this heap instance will operate over
161 * \param[in] cptid The CPT id of \a cptab this heap instance will operate over
163 * \retval valid-pointer A newly-created and initialized binary heap object
167 cfs_binheap_create(struct cfs_binheap_ops *ops, unsigned int flags,
168 unsigned count, void *arg, struct cfs_cpt_table *cptab,
171 struct cfs_binheap *h;
173 LASSERT(ops != NULL);
174 LASSERT(ops->hop_compare != NULL);
176 LASSERT(cptid == CFS_CPT_ANY ||
177 (cptid >= 0 && cptid < cptab->ctb_nparts));
178 LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
180 LIBCFS_ALLOC(h, sizeof(*h));
186 h->cbh_nelements = 0;
188 h->cbh_private = arg;
189 h->cbh_flags = flags & (~CBH_FLAG_ATOMIC_GROW);
190 h->cbh_cptab = cptab;
191 h->cbh_cptid = cptid;
193 while (h->cbh_hwm < count) { /* preallocate */
194 if (cfs_binheap_grow(h) != 0) {
195 cfs_binheap_destroy(h);
200 h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
204 EXPORT_SYMBOL(cfs_binheap_create);
207 * Releases all resources associated with a binary heap instance.
209 * Deallocates memory for all indirection levels and the binary heap object
212 * \param[in] h The binary heap object
215 cfs_binheap_destroy(struct cfs_binheap *h)
226 CBH_FREE(h->cbh_elements1);
231 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
232 CBH_FREE(h->cbh_elements2[idx0]);
236 CBH_FREE(h->cbh_elements2);
240 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
242 for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
243 CBH_FREE(h->cbh_elements3[idx0][idx1]);
247 CBH_FREE(h->cbh_elements3[idx0]);
250 CBH_FREE(h->cbh_elements3);
253 LIBCFS_FREE(h, sizeof(*h));
255 EXPORT_SYMBOL(cfs_binheap_destroy);
258 * Obtains a double pointer to a heap element, given its index into the binary
261 * \param[in] h The binary heap instance
262 * \param[in] idx The requested node's index
264 * \retval valid-pointer A double pointer to a heap pointer entry
266 static struct cfs_binheap_node **
267 cfs_binheap_pointer(struct cfs_binheap *h, unsigned int idx)
270 return &(h->cbh_elements1[idx]);
273 if (idx < CBH_SIZE * CBH_SIZE)
274 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
276 idx -= CBH_SIZE * CBH_SIZE;
277 return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
278 [(idx >> CBH_SHIFT) & CBH_MASK]\
283 * Obtains a pointer to a heap element, given its index into the binary tree.
285 * \param[in] h The binary heap
286 * \param[in] idx The requested node's index
288 * \retval valid-pointer The requested heap node
289 * \retval NULL Supplied index is out of bounds
291 struct cfs_binheap_node *
292 cfs_binheap_find(struct cfs_binheap *h, unsigned int idx)
294 if (idx >= h->cbh_nelements)
297 return *cfs_binheap_pointer(h, idx);
299 EXPORT_SYMBOL(cfs_binheap_find);
302 * Moves a node upwards, towards the root of the binary tree.
304 * \param[in] h The heap
305 * \param[in] e The node
307 * \retval 1 The position of \a e in the tree was changed at least once
308 * \retval 0 The position of \a e in the tree was not changed
311 cfs_binheap_bubble(struct cfs_binheap *h, struct cfs_binheap_node *e)
313 unsigned int cur_idx = e->chn_index;
314 struct cfs_binheap_node **cur_ptr;
315 unsigned int parent_idx;
316 struct cfs_binheap_node **parent_ptr;
319 cur_ptr = cfs_binheap_pointer(h, cur_idx);
320 LASSERT(*cur_ptr == e);
322 while (cur_idx > 0) {
323 parent_idx = (cur_idx - 1) >> 1;
325 parent_ptr = cfs_binheap_pointer(h, parent_idx);
326 LASSERT((*parent_ptr)->chn_index == parent_idx);
328 if (h->cbh_ops->hop_compare(*parent_ptr, e))
331 (*parent_ptr)->chn_index = cur_idx;
332 *cur_ptr = *parent_ptr;
333 cur_ptr = parent_ptr;
334 cur_idx = parent_idx;
338 e->chn_index = cur_idx;
345 * Moves a node downwards, towards the last level of the binary tree.
347 * \param[in] h The heap
348 * \param[in] e The node
350 * \retval 1 The position of \a e in the tree was changed at least once
351 * \retval 0 The position of \a e in the tree was not changed
354 cfs_binheap_sink(struct cfs_binheap *h, struct cfs_binheap_node *e)
356 unsigned int n = h->cbh_nelements;
357 unsigned int child_idx;
358 struct cfs_binheap_node **child_ptr;
359 struct cfs_binheap_node *child;
360 unsigned int child2_idx;
361 struct cfs_binheap_node **child2_ptr;
362 struct cfs_binheap_node *child2;
363 unsigned int cur_idx;
364 struct cfs_binheap_node **cur_ptr;
367 cur_idx = e->chn_index;
368 cur_ptr = cfs_binheap_pointer(h, cur_idx);
369 LASSERT(*cur_ptr == e);
371 while (cur_idx < n) {
372 child_idx = (cur_idx << 1) + 1;
376 child_ptr = cfs_binheap_pointer(h, child_idx);
379 child2_idx = child_idx + 1;
380 if (child2_idx < n) {
381 child2_ptr = cfs_binheap_pointer(h, child2_idx);
382 child2 = *child2_ptr;
384 if (h->cbh_ops->hop_compare(child2, child)) {
385 child_idx = child2_idx;
386 child_ptr = child2_ptr;
391 LASSERT(child->chn_index == child_idx);
393 if (h->cbh_ops->hop_compare(e, child))
396 child->chn_index = cur_idx;
403 e->chn_index = cur_idx;
410 * Sort-inserts a node into the binary heap.
412 * \param[in] h The heap
413 * \param[in] e The node
415 * \retval 0 Element inserted successfully
419 cfs_binheap_insert(struct cfs_binheap *h, struct cfs_binheap_node *e)
421 struct cfs_binheap_node **new_ptr;
422 unsigned int new_idx = h->cbh_nelements;
425 if (new_idx == h->cbh_hwm) {
426 rc = cfs_binheap_grow(h);
431 if (h->cbh_ops->hop_enter) {
432 rc = h->cbh_ops->hop_enter(h, e);
437 e->chn_index = new_idx;
438 new_ptr = cfs_binheap_pointer(h, new_idx);
442 cfs_binheap_bubble(h, e);
446 EXPORT_SYMBOL(cfs_binheap_insert);
449 * Removes a node from the binary heap.
451 * \param[in] h The heap
452 * \param[in] e The node
455 cfs_binheap_remove(struct cfs_binheap *h, struct cfs_binheap_node *e)
457 unsigned int n = h->cbh_nelements;
458 unsigned int cur_idx = e->chn_index;
459 struct cfs_binheap_node **cur_ptr;
460 struct cfs_binheap_node *last;
462 LASSERT(cur_idx != CBH_POISON);
463 LASSERT(cur_idx < n);
465 cur_ptr = cfs_binheap_pointer(h, cur_idx);
466 LASSERT(*cur_ptr == e);
469 last = *cfs_binheap_pointer(h, n);
470 h->cbh_nelements = n;
474 last->chn_index = cur_idx;
476 cfs_binheap_relocate(h, *cur_ptr);
478 e->chn_index = CBH_POISON;
479 if (h->cbh_ops->hop_exit)
480 h->cbh_ops->hop_exit(h, e);
482 EXPORT_SYMBOL(cfs_binheap_remove);
485 * Relocate a node in the binary heap.
486 * Should be called whenever a node's values
487 * which affects its ranking are changed.
489 * \param[in] h The heap
490 * \param[in] e The node
493 cfs_binheap_relocate(struct cfs_binheap *h, struct cfs_binheap_node *e)
495 if (!cfs_binheap_bubble(h, e))
496 cfs_binheap_sink(h, e);
498 EXPORT_SYMBOL(cfs_binheap_relocate);