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.
19 * Copyright (c) 2011 Intel Corporation
22 * libcfs/libcfs/heap.c
24 * Author: Eric Barton <eeb@whamcloud.com>
25 * Liang Zhen <liang@whamcloud.com>
32 #define DEBUG_SUBSYSTEM S_LNET
34 #include <libcfs/libcfs.h>
35 #include <lustre_net.h>
38 #define CBH_ALLOC(ptr, h) \
41 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
42 LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, \
43 h->cbh_cptid, CBH_NOB, \
46 LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, \
47 h->cbh_cptid, CBH_NOB); \
49 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW) \
50 LIBCFS_ALLOC_ATOMIC((ptr), CBH_NOB); \
52 LIBCFS_ALLOC((ptr), CBH_NOB); \
56 #define CBH_FREE(ptr) LIBCFS_FREE(ptr, CBH_NOB)
59 * Grows the capacity of a binary heap so that it can handle a larger number of
60 * \e struct binheap_node objects.
62 * \param[in] h The binary heap
64 * \retval 0 Successfully grew the heap
65 * \retval -ENOMEM OOM error
68 binheap_grow(struct binheap *h)
70 struct binheap_node ***frag1 = NULL;
71 struct binheap_node **frag2;
74 /* need a whole new chunk of pointers */
75 LASSERT((h->cbh_hwm & CBH_MASK) == 0);
78 /* first use of single indirect */
79 CBH_ALLOC(h->cbh_elements1, h);
80 if (h->cbh_elements1 == NULL)
87 if (hwm < CBH_SIZE * CBH_SIZE) {
88 /* not filled double indirect */
94 /* first use of double indirect */
95 CBH_ALLOC(h->cbh_elements2, h);
96 if (h->cbh_elements2 == NULL) {
102 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
106 hwm -= CBH_SIZE * CBH_SIZE;
107 #if (CBH_SHIFT * 3 < 32)
108 if (hwm >= CBH_SIZE * CBH_SIZE * CBH_SIZE) {
109 /* filled triple indirect */
117 if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
118 /* first use of this 2nd level index */
127 /* first use of triple indirect */
128 CBH_ALLOC(h->cbh_elements3, h);
129 if (h->cbh_elements3 == NULL) {
137 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
138 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
140 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
141 LASSERT(frag1 != NULL);
144 frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
147 h->cbh_hwm += CBH_SIZE;
152 * Creates and initializes a binary heap instance.
154 * \param[in] ops The operations to be used
155 * \param[in] flags The heap flags
156 * \parm[in] count The initial heap capacity in # of elements
157 * \param[in] arg An optional private argument
158 * \param[in] cptab The CPT table this heap instance will operate over
159 * \param[in] cptid The CPT id of \a cptab this heap instance will operate over
161 * \retval valid-pointer A newly-created and initialized binary heap object
165 binheap_create(struct binheap_ops *ops, unsigned int flags,
166 unsigned int count, void *arg, struct cfs_cpt_table *cptab,
171 LASSERT(ops != NULL);
172 LASSERT(ops->hop_compare != NULL);
174 LASSERT(cptid == CFS_CPT_ANY ||
175 (cptid >= 0 && cptid < cfs_cpt_number(cptab)));
176 LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
178 LIBCFS_ALLOC(h, sizeof(*h));
184 h->cbh_nelements = 0;
186 h->cbh_private = arg;
187 h->cbh_flags = flags & (~CBH_FLAG_ATOMIC_GROW);
188 h->cbh_cptab = cptab;
189 h->cbh_cptid = cptid;
191 while (h->cbh_hwm < count) { /* preallocate */
192 if (binheap_grow(h) != 0) {
198 h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
202 EXPORT_SYMBOL(binheap_create);
205 * Releases all resources associated with a binary heap instance.
207 * Deallocates memory for all indirection levels and the binary heap object
210 * \param[in] h The binary heap object
213 binheap_destroy(struct binheap *h)
224 CBH_FREE(h->cbh_elements1);
229 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
230 CBH_FREE(h->cbh_elements2[idx0]);
234 CBH_FREE(h->cbh_elements2);
238 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
240 for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
241 CBH_FREE(h->cbh_elements3[idx0][idx1]);
245 CBH_FREE(h->cbh_elements3[idx0]);
248 CBH_FREE(h->cbh_elements3);
251 LIBCFS_FREE(h, sizeof(*h));
253 EXPORT_SYMBOL(binheap_destroy);
256 * Obtains a double pointer to a heap element, given its index into the binary
259 * \param[in] h The binary heap instance
260 * \param[in] idx The requested node's index
262 * \retval valid-pointer A double pointer to a heap pointer entry
264 static struct binheap_node **
265 binheap_pointer(struct binheap *h, unsigned int idx)
268 return &(h->cbh_elements1[idx]);
271 if (idx < CBH_SIZE * CBH_SIZE)
272 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
274 idx -= CBH_SIZE * CBH_SIZE;
275 return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]
276 [(idx >> CBH_SHIFT) & CBH_MASK]
281 * Obtains a pointer to a heap element, given its index into the binary tree.
283 * \param[in] h The binary heap
284 * \param[in] idx The requested node's index
286 * \retval valid-pointer The requested heap node
287 * \retval NULL Supplied index is out of bounds
289 struct binheap_node *
290 binheap_find(struct binheap *h, unsigned int idx)
292 if (idx >= h->cbh_nelements)
295 return *binheap_pointer(h, idx);
297 EXPORT_SYMBOL(binheap_find);
300 * Moves a node upwards, towards the root of the binary tree.
302 * \param[in] h The heap
303 * \param[in] e The node
305 * \retval 1 The position of \a e in the tree was changed at least once
306 * \retval 0 The position of \a e in the tree was not changed
309 binheap_bubble(struct binheap *h, struct binheap_node *e)
311 unsigned int cur_idx = e->chn_index;
312 struct binheap_node **cur_ptr;
313 unsigned int parent_idx;
314 struct binheap_node **parent_ptr;
317 cur_ptr = binheap_pointer(h, cur_idx);
318 LASSERT(*cur_ptr == e);
320 while (cur_idx > 0) {
321 parent_idx = (cur_idx - 1) >> 1;
323 parent_ptr = binheap_pointer(h, parent_idx);
324 LASSERT((*parent_ptr)->chn_index == parent_idx);
326 if (h->cbh_ops->hop_compare(*parent_ptr, e))
329 (*parent_ptr)->chn_index = cur_idx;
330 *cur_ptr = *parent_ptr;
331 cur_ptr = parent_ptr;
332 cur_idx = parent_idx;
336 e->chn_index = cur_idx;
343 * Moves a node downwards, towards the last level of the binary tree.
345 * \param[in] h The heap
346 * \param[in] e The node
348 * \retval 1 The position of \a e in the tree was changed at least once
349 * \retval 0 The position of \a e in the tree was not changed
352 binheap_sink(struct binheap *h, struct binheap_node *e)
354 unsigned int n = h->cbh_nelements;
355 unsigned int child_idx;
356 struct binheap_node **child_ptr;
357 struct binheap_node *child;
358 unsigned int child2_idx;
359 struct binheap_node **child2_ptr;
360 struct binheap_node *child2;
361 unsigned int cur_idx;
362 struct binheap_node **cur_ptr;
365 cur_idx = e->chn_index;
366 cur_ptr = binheap_pointer(h, cur_idx);
367 LASSERT(*cur_ptr == e);
369 while (cur_idx < n) {
370 child_idx = (cur_idx << 1) + 1;
374 child_ptr = binheap_pointer(h, child_idx);
377 child2_idx = child_idx + 1;
378 if (child2_idx < n) {
379 child2_ptr = binheap_pointer(h, child2_idx);
380 child2 = *child2_ptr;
382 if (h->cbh_ops->hop_compare(child2, child)) {
383 child_idx = child2_idx;
384 child_ptr = child2_ptr;
389 LASSERT(child->chn_index == child_idx);
391 if (h->cbh_ops->hop_compare(e, child))
394 child->chn_index = cur_idx;
401 e->chn_index = cur_idx;
408 * Sort-inserts a node into the binary heap.
410 * \param[in] h The heap
411 * \param[in] e The node
413 * \retval 0 Element inserted successfully
417 binheap_insert(struct binheap *h, struct binheap_node *e)
419 struct binheap_node **new_ptr;
420 unsigned int new_idx = h->cbh_nelements;
423 if (new_idx == h->cbh_hwm) {
424 rc = binheap_grow(h);
429 if (h->cbh_ops->hop_enter) {
430 rc = h->cbh_ops->hop_enter(h, e);
435 e->chn_index = new_idx;
436 new_ptr = binheap_pointer(h, new_idx);
440 binheap_bubble(h, e);
444 EXPORT_SYMBOL(binheap_insert);
447 * Removes a node from the binary heap.
449 * \param[in] h The heap
450 * \param[in] e The node
453 binheap_remove(struct binheap *h, struct binheap_node *e)
455 unsigned int n = h->cbh_nelements;
456 unsigned int cur_idx = e->chn_index;
457 struct binheap_node **cur_ptr;
458 struct binheap_node *last;
460 LASSERT(cur_idx != CBH_POISON);
461 LASSERT(cur_idx < n);
463 cur_ptr = binheap_pointer(h, cur_idx);
464 LASSERT(*cur_ptr == e);
467 last = *binheap_pointer(h, n);
468 h->cbh_nelements = n;
472 last->chn_index = cur_idx;
474 binheap_relocate(h, *cur_ptr);
476 e->chn_index = CBH_POISON;
477 if (h->cbh_ops->hop_exit)
478 h->cbh_ops->hop_exit(h, e);
480 EXPORT_SYMBOL(binheap_remove);
483 * Relocate a node in the binary heap.
484 * Should be called whenever a node's values
485 * which affects its ranking are changed.
487 * \param[in] h The heap
488 * \param[in] e The node
491 binheap_relocate(struct binheap *h, struct binheap_node *e)
493 if (!binheap_bubble(h, e))
496 EXPORT_SYMBOL(binheap_relocate);