libcfs/libcfs/heap.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   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.
   9
  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.
  15
  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
  19  *
  20  * GPL HEADER END
  21  */
  22 /*
  23  * Copyright (c) 2011 Intel Corporation
  24  */
  25 /*
  26  * libcfs/libcfs/heap.c
  27  *
  28  * Author: Eric Barton  <eeb@whamcloud.com>
  29  *         Liang Zhen   <liang@whamcloud.com>
  30  */
  31 /** \addtogroup heap
  32  *
  33  * @{
  34  */
  35
  36 #define DEBUG_SUBSYSTEM S_LNET
  37
  38 #include <libcfs/libcfs.h>
  39
  40 #define CBH_ALLOC(ptr, h)                                               \
  41 do {                                                                    \
  42         if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)                      \
  43                 LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab, h->cbh_cptid, \
  44                                      CBH_NOB, CFS_ALLOC_ATOMIC);        \
  45         else                                                            \
  46                 LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab, h->cbh_cptid,     \
  47                                  CBH_NOB);                              \
  48 } while (0)
  49
  50 #define CBH_FREE(ptr)   LIBCFS_FREE(ptr, CBH_NOB)
  51
  52 /**
  53  * Grows the capacity of a binary heap so that it can handle a larger number of
  54  * \e cfs_binheap_node_t objects.
  55  *
  56  * \param[in] h The binary heap
  57  *
  58  * \retval 0       Successfully grew the heap
  59  * \retval -ENOMEM OOM error
  60  */
  61 static int
  62 cfs_binheap_grow(cfs_binheap_t *h)
  63 {
  64         cfs_binheap_node_t ***frag1 = NULL;
  65         cfs_binheap_node_t  **frag2;
  66         int hwm = h->cbh_hwm;
  67
  68         /* need a whole new chunk of pointers */
  69         LASSERT((h->cbh_hwm & CBH_MASK) == 0);
  70
  71         if (hwm == 0) {
  72                 /* first use of single indirect */
  73                 CBH_ALLOC(h->cbh_elements1, h);
  74                 if (h->cbh_elements1 == NULL)
  75                         return -ENOMEM;
  76
  77                 goto out;
  78         }
  79
  80         hwm -= CBH_SIZE;
  81         if (hwm < CBH_SIZE * CBH_SIZE) {
  82                 /* not filled double indirect */
  83                 CBH_ALLOC(frag2, h);
  84                 if (frag2 == NULL)
  85                         return -ENOMEM;
  86
  87                 if (hwm == 0) {
  88                         /* first use of double indirect */
  89                         CBH_ALLOC(h->cbh_elements2, h);
  90                         if (h->cbh_elements2 == NULL) {
  91                                 CBH_FREE(frag2);
  92                                 return -ENOMEM;
  93                         }
  94                 }
  95
  96                 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
  97                 goto out;
  98         }
  99
 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 */
 104                 return -ENOMEM;
 105         }
 106 #endif
 107         CBH_ALLOC(frag2, h);
 108         if (frag2 == NULL)
 109                 return -ENOMEM;
 110
 111         if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
 112                 /* first use of this 2nd level index */
 113                 CBH_ALLOC(frag1, h);
 114                 if (frag1 == NULL) {
 115                         CBH_FREE(frag2);
 116                         return -ENOMEM;
 117                 }
 118         }
 119
 120         if (hwm == 0) {
 121                 /* first use of triple indirect */
 122                 CBH_ALLOC(h->cbh_elements3, h);
 123                 if (h->cbh_elements3 == NULL) {
 124                         CBH_FREE(frag2);
 125                         CBH_FREE(frag1);
 126                         return -ENOMEM;
 127                 }
 128         }
 129
 130         if (frag1 != NULL) {
 131                 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
 132                 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
 133         } else {
 134                 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
 135                 LASSERT(frag1 != NULL);
 136         }
 137
 138         frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
 139
 140  out:
 141         h->cbh_hwm += CBH_SIZE;
 142         return 0;
 143 }
 144
 145 /**
 146  * Creates and initializes a binary heap instance.
 147  *
 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
 154  *
 155  * \retval valid-pointer A newly-created and initialized binary heap object
 156  * \retval NULL          error
 157  */
 158 cfs_binheap_t *
 159 cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
 160                    unsigned count, void *arg, struct cfs_cpt_table *cptab,
 161                    int cptid)
 162 {
 163         cfs_binheap_t *h;
 164
 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));
 170
 171         LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
 172         if (h == NULL)
 173                 return NULL;
 174
 175         h->cbh_ops        = ops;
 176         h->cbh_nelements  = 0;
 177         h->cbh_hwm        = 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;
 182
 183         while (h->cbh_hwm < count) { /* preallocate */
 184                 if (cfs_binheap_grow(h) != 0) {
 185                         cfs_binheap_destroy(h);
 186                         return NULL;
 187                 }
 188         }
 189
 190         h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
 191
 192         return h;
 193 }
 194 EXPORT_SYMBOL(cfs_binheap_create);
 195
 196 /**
 197  * Releases all resources associated with a binary heap instance.
 198  *
 199  * Deallocates memory for all indirection levels and the binary heap object
 200  * itself.
 201  *
 202  * \param[in] h The binary heap object
 203  */
 204 void
 205 cfs_binheap_destroy(cfs_binheap_t *h)
 206 {
 207         int idx0;
 208         int idx1;
 209         int n;
 210
 211         LASSERT(h != NULL);
 212
 213         n = h->cbh_hwm;
 214
 215         if (n > 0) {
 216                 CBH_FREE(h->cbh_elements1);
 217                 n -= CBH_SIZE;
 218         }
 219
 220         if (n > 0) {
 221                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 222                         CBH_FREE(h->cbh_elements2[idx0]);
 223                         n -= CBH_SIZE;
 224                 }
 225
 226                 CBH_FREE(h->cbh_elements2);
 227         }
 228
 229         if (n > 0) {
 230                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 231
 232                         for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
 233                                 CBH_FREE(h->cbh_elements3[idx0][idx1]);
 234                                 n -= CBH_SIZE;
 235                         }
 236
 237                         CBH_FREE(h->cbh_elements3[idx0]);
 238                 }
 239
 240                 CBH_FREE(h->cbh_elements3);
 241         }
 242
 243         LIBCFS_FREE(h, sizeof(*h));
 244 }
 245 EXPORT_SYMBOL(cfs_binheap_destroy);
 246
 247 /**
 248  * Obtains a double pointer to a heap element, given its index into the binary
 249  * tree.
 250  *
 251  * \param[in] h   The binary heap instance
 252  * \param[in] idx The requested node's index
 253  *
 254  * \retval valid-pointer A double pointer to a heap pointer entry
 255  */
 256 static cfs_binheap_node_t **
 257 cfs_binheap_pointer(cfs_binheap_t *h, unsigned int idx)
 258 {
 259         if (idx < CBH_SIZE)
 260                 return &(h->cbh_elements1[idx]);
 261
 262         idx -= CBH_SIZE;
 263         if (idx < CBH_SIZE * CBH_SIZE)
 264                 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
 265
 266         idx -= CBH_SIZE * CBH_SIZE;
 267         return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
 268                                  [(idx >> CBH_SHIFT) & CBH_MASK]\
 269                                  [idx & CBH_MASK]);
 270 }
 271
 272 /**
 273  * Obtains a pointer to a heap element, given its index into the binary tree.
 274  *
 275  * \param[in] h   The binary heap
 276  * \param[in] idx The requested node's index
 277  *
 278  * \retval valid-pointer The requested heap node
 279  * \retval NULL          Supplied index is out of bounds
 280  */
 281 cfs_binheap_node_t *
 282 cfs_binheap_find(cfs_binheap_t *h, unsigned int idx)
 283 {
 284         if (idx >= h->cbh_nelements)
 285                 return NULL;
 286
 287         return *cfs_binheap_pointer(h, idx);
 288 }
 289 EXPORT_SYMBOL(cfs_binheap_find);
 290
 291 /**
 292  * Moves a node upwards, towards the root of the binary tree.
 293  *
 294  * \param[in] h The heap
 295  * \param[in] e The node
 296  *
 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
 299  */
 300 static int
 301 cfs_binheap_bubble(cfs_binheap_t *h, cfs_binheap_node_t *e)
 302 {
 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;
 307         int                  did_sth = 0;
 308
 309         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 310         LASSERT(*cur_ptr == e);
 311
 312         while (cur_idx > 0) {
 313                 parent_idx = (cur_idx - 1) >> 1;
 314
 315                 parent_ptr = cfs_binheap_pointer(h, parent_idx);
 316                 LASSERT((*parent_ptr)->chn_index == parent_idx);
 317
 318                 if (h->cbh_ops->hop_compare(*parent_ptr, e))
 319                         break;
 320
 321                 (*parent_ptr)->chn_index = cur_idx;
 322                 *cur_ptr = *parent_ptr;
 323                 cur_ptr = parent_ptr;
 324                 cur_idx = parent_idx;
 325                 did_sth = 1;
 326         }
 327
 328         e->chn_index = cur_idx;
 329         *cur_ptr = e;
 330
 331         return did_sth;
 332 }
 333
 334 /**
 335  * Moves a node downwards, towards the last level of the binary tree.
 336  *
 337  * \param[in] h The heap
 338  * \param[in] e The node
 339  *
 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
 342  */
 343 static int
 344 cfs_binheap_sink(cfs_binheap_t *h, cfs_binheap_node_t *e)
 345 {
 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;
 355         int                  did_sth = 0;
 356
 357         cur_idx = e->chn_index;
 358         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 359         LASSERT(*cur_ptr == e);
 360
 361         while (cur_idx < n) {
 362                 child_idx = (cur_idx << 1) + 1;
 363                 if (child_idx >= n)
 364                         break;
 365
 366                 child_ptr = cfs_binheap_pointer(h, child_idx);
 367                 child = *child_ptr;
 368
 369                 child2_idx = child_idx + 1;
 370                 if (child2_idx < n) {
 371                         child2_ptr = cfs_binheap_pointer(h, child2_idx);
 372                         child2 = *child2_ptr;
 373
 374                         if (h->cbh_ops->hop_compare(child2, child)) {
 375                                 child_idx = child2_idx;
 376                                 child_ptr = child2_ptr;
 377                                 child = child2;
 378                         }
 379                 }
 380
 381                 LASSERT(child->chn_index == child_idx);
 382
 383                 if (h->cbh_ops->hop_compare(e, child))
 384                         break;
 385
 386                 child->chn_index = cur_idx;
 387                 *cur_ptr = child;
 388                 cur_ptr = child_ptr;
 389                 cur_idx = child_idx;
 390                 did_sth = 1;
 391         }
 392
 393         e->chn_index = cur_idx;
 394         *cur_ptr = e;
 395
 396         return did_sth;
 397 }
 398
 399 /**
 400  * Sort-inserts a node into the binary heap.
 401  *
 402  * \param[in] h The heap
 403  * \param[in] e The node
 404  *
 405  * \retval 0    Element inserted successfully
 406  * \retval != 0 error
 407  */
 408 int
 409 cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e)
 410 {
 411         cfs_binheap_node_t **new_ptr;
 412         unsigned int         new_idx = h->cbh_nelements;
 413         int                  rc;
 414
 415         if (new_idx == h->cbh_hwm) {
 416                 rc = cfs_binheap_grow(h);
 417                 if (rc != 0)
 418                         return rc;
 419         }
 420
 421         if (h->cbh_ops->hop_enter) {
 422                 rc = h->cbh_ops->hop_enter(h, e);
 423                 if (rc != 0)
 424                         return rc;
 425         }
 426
 427         e->chn_index = new_idx;
 428         new_ptr = cfs_binheap_pointer(h, new_idx);
 429         h->cbh_nelements++;
 430         *new_ptr = e;
 431
 432         cfs_binheap_bubble(h, e);
 433
 434         return 0;
 435 }
 436 EXPORT_SYMBOL(cfs_binheap_insert);
 437
 438 /**
 439  * Removes a node from the binary heap.
 440  *
 441  * \param[in] h The heap
 442  * \param[in] e The node
 443  */
 444 void
 445 cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e)
 446 {
 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;
 451
 452         LASSERT(cur_idx != CBH_POISON);
 453         LASSERT(cur_idx < n);
 454
 455         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 456         LASSERT(*cur_ptr == e);
 457
 458         n--;
 459         last = *cfs_binheap_pointer(h, n);
 460         h->cbh_nelements = n;
 461         if (last == e)
 462                 return;
 463
 464         last->chn_index = cur_idx;
 465         *cur_ptr = last;
 466         if (!cfs_binheap_bubble(h, *cur_ptr))
 467                 cfs_binheap_sink(h, *cur_ptr);
 468
 469         e->chn_index = CBH_POISON;
 470         if (h->cbh_ops->hop_exit)
 471                 h->cbh_ops->hop_exit(h, e);
 472 }
 473 EXPORT_SYMBOL(cfs_binheap_remove);
 474
 475 /** @} heap */