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_cptab) {                                             \
  43                 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)              \
  44                         LIBCFS_CPT_ALLOC_GFP((ptr), h->cbh_cptab,       \
  45                                              h->cbh_cptid, CBH_NOB,     \
  46                                              GFP_ATOMIC);               \
  47                 else                                                    \
  48                         LIBCFS_CPT_ALLOC((ptr), h->cbh_cptab,           \
  49                                          h->cbh_cptid, CBH_NOB);        \
  50         } else {                                                        \
  51                 if ((h)->cbh_flags & CBH_FLAG_ATOMIC_GROW)              \
  52                         LIBCFS_ALLOC_ATOMIC((ptr), CBH_NOB);            \
  53                 else                                                    \
  54                         LIBCFS_ALLOC((ptr), CBH_NOB);                   \
  55         }                                                               \
  56 } while (0)
  57
  58 #define CBH_FREE(ptr)   LIBCFS_FREE(ptr, CBH_NOB)
  59
  60 /**
  61  * Grows the capacity of a binary heap so that it can handle a larger number of
  62  * \e struct cfs_binheap_node objects.
  63  *
  64  * \param[in] h The binary heap
  65  *
  66  * \retval 0       Successfully grew the heap
  67  * \retval -ENOMEM OOM error
  68  */
  69 static int
  70 cfs_binheap_grow(struct cfs_binheap *h)
  71 {
  72         struct cfs_binheap_node ***frag1 = NULL;
  73         struct cfs_binheap_node  **frag2;
  74         int hwm = h->cbh_hwm;
  75
  76         /* need a whole new chunk of pointers */
  77         LASSERT((h->cbh_hwm & CBH_MASK) == 0);
  78
  79         if (hwm == 0) {
  80                 /* first use of single indirect */
  81                 CBH_ALLOC(h->cbh_elements1, h);
  82                 if (h->cbh_elements1 == NULL)
  83                         return -ENOMEM;
  84
  85                 goto out;
  86         }
  87
  88         hwm -= CBH_SIZE;
  89         if (hwm < CBH_SIZE * CBH_SIZE) {
  90                 /* not filled double indirect */
  91                 CBH_ALLOC(frag2, h);
  92                 if (frag2 == NULL)
  93                         return -ENOMEM;
  94
  95                 if (hwm == 0) {
  96                         /* first use of double indirect */
  97                         CBH_ALLOC(h->cbh_elements2, h);
  98                         if (h->cbh_elements2 == NULL) {
  99                                 CBH_FREE(frag2);
 100                                 return -ENOMEM;
 101                         }
 102                 }
 103
 104                 h->cbh_elements2[hwm >> CBH_SHIFT] = frag2;
 105                 goto out;
 106         }
 107
 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 */
 112                 return -ENOMEM;
 113         }
 114 #endif
 115         CBH_ALLOC(frag2, h);
 116         if (frag2 == NULL)
 117                 return -ENOMEM;
 118
 119         if (((hwm >> CBH_SHIFT) & CBH_MASK) == 0) {
 120                 /* first use of this 2nd level index */
 121                 CBH_ALLOC(frag1, h);
 122                 if (frag1 == NULL) {
 123                         CBH_FREE(frag2);
 124                         return -ENOMEM;
 125                 }
 126         }
 127
 128         if (hwm == 0) {
 129                 /* first use of triple indirect */
 130                 CBH_ALLOC(h->cbh_elements3, h);
 131                 if (h->cbh_elements3 == NULL) {
 132                         CBH_FREE(frag2);
 133                         CBH_FREE(frag1);
 134                         return -ENOMEM;
 135                 }
 136         }
 137
 138         if (frag1 != NULL) {
 139                 LASSERT(h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] == NULL);
 140                 h->cbh_elements3[hwm >> (2 * CBH_SHIFT)] = frag1;
 141         } else {
 142                 frag1 = h->cbh_elements3[hwm >> (2 * CBH_SHIFT)];
 143                 LASSERT(frag1 != NULL);
 144         }
 145
 146         frag1[(hwm >> CBH_SHIFT) & CBH_MASK] = frag2;
 147
 148  out:
 149         h->cbh_hwm += CBH_SIZE;
 150         return 0;
 151 }
 152
 153 /**
 154  * Creates and initializes a binary heap instance.
 155  *
 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
 162  *
 163  * \retval valid-pointer A newly-created and initialized binary heap object
 164  * \retval NULL          error
 165  */
 166 struct cfs_binheap *
 167 cfs_binheap_create(struct cfs_binheap_ops *ops, unsigned int flags,
 168                    unsigned count, void *arg, struct cfs_cpt_table *cptab,
 169                    int cptid)
 170 {
 171         struct cfs_binheap *h;
 172
 173         LASSERT(ops != NULL);
 174         LASSERT(ops->hop_compare != NULL);
 175         if (cptab) {
 176                 LASSERT(cptid == CFS_CPT_ANY ||
 177                        (cptid >= 0 && cptid < cptab->ctb_nparts));
 178                 LIBCFS_CPT_ALLOC(h, cptab, cptid, sizeof(*h));
 179         } else {
 180                 LIBCFS_ALLOC(h, sizeof(*h));
 181         }
 182         if (!h)
 183                 return NULL;
 184
 185         h->cbh_ops        = ops;
 186         h->cbh_nelements  = 0;
 187         h->cbh_hwm        = 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;
 192
 193         while (h->cbh_hwm < count) { /* preallocate */
 194                 if (cfs_binheap_grow(h) != 0) {
 195                         cfs_binheap_destroy(h);
 196                         return NULL;
 197                 }
 198         }
 199
 200         h->cbh_flags |= flags & CBH_FLAG_ATOMIC_GROW;
 201
 202         return h;
 203 }
 204 EXPORT_SYMBOL(cfs_binheap_create);
 205
 206 /**
 207  * Releases all resources associated with a binary heap instance.
 208  *
 209  * Deallocates memory for all indirection levels and the binary heap object
 210  * itself.
 211  *
 212  * \param[in] h The binary heap object
 213  */
 214 void
 215 cfs_binheap_destroy(struct cfs_binheap *h)
 216 {
 217         int idx0;
 218         int idx1;
 219         int n;
 220
 221         LASSERT(h != NULL);
 222
 223         n = h->cbh_hwm;
 224
 225         if (n > 0) {
 226                 CBH_FREE(h->cbh_elements1);
 227                 n -= CBH_SIZE;
 228         }
 229
 230         if (n > 0) {
 231                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 232                         CBH_FREE(h->cbh_elements2[idx0]);
 233                         n -= CBH_SIZE;
 234                 }
 235
 236                 CBH_FREE(h->cbh_elements2);
 237         }
 238
 239         if (n > 0) {
 240                 for (idx0 = 0; idx0 < CBH_SIZE && n > 0; idx0++) {
 241
 242                         for (idx1 = 0; idx1 < CBH_SIZE && n > 0; idx1++) {
 243                                 CBH_FREE(h->cbh_elements3[idx0][idx1]);
 244                                 n -= CBH_SIZE;
 245                         }
 246
 247                         CBH_FREE(h->cbh_elements3[idx0]);
 248                 }
 249
 250                 CBH_FREE(h->cbh_elements3);
 251         }
 252
 253         LIBCFS_FREE(h, sizeof(*h));
 254 }
 255 EXPORT_SYMBOL(cfs_binheap_destroy);
 256
 257 /**
 258  * Obtains a double pointer to a heap element, given its index into the binary
 259  * tree.
 260  *
 261  * \param[in] h   The binary heap instance
 262  * \param[in] idx The requested node's index
 263  *
 264  * \retval valid-pointer A double pointer to a heap pointer entry
 265  */
 266 static struct cfs_binheap_node **
 267 cfs_binheap_pointer(struct cfs_binheap *h, unsigned int idx)
 268 {
 269         if (idx < CBH_SIZE)
 270                 return &(h->cbh_elements1[idx]);
 271
 272         idx -= CBH_SIZE;
 273         if (idx < CBH_SIZE * CBH_SIZE)
 274                 return &(h->cbh_elements2[idx >> CBH_SHIFT][idx & CBH_MASK]);
 275
 276         idx -= CBH_SIZE * CBH_SIZE;
 277         return &(h->cbh_elements3[idx >> (2 * CBH_SHIFT)]\
 278                                  [(idx >> CBH_SHIFT) & CBH_MASK]\
 279                                  [idx & CBH_MASK]);
 280 }
 281
 282 /**
 283  * Obtains a pointer to a heap element, given its index into the binary tree.
 284  *
 285  * \param[in] h   The binary heap
 286  * \param[in] idx The requested node's index
 287  *
 288  * \retval valid-pointer The requested heap node
 289  * \retval NULL          Supplied index is out of bounds
 290  */
 291 struct cfs_binheap_node *
 292 cfs_binheap_find(struct cfs_binheap *h, unsigned int idx)
 293 {
 294         if (idx >= h->cbh_nelements)
 295                 return NULL;
 296
 297         return *cfs_binheap_pointer(h, idx);
 298 }
 299 EXPORT_SYMBOL(cfs_binheap_find);
 300
 301 /**
 302  * Moves a node upwards, towards the root of the binary tree.
 303  *
 304  * \param[in] h The heap
 305  * \param[in] e The node
 306  *
 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
 309  */
 310 static int
 311 cfs_binheap_bubble(struct cfs_binheap *h, struct cfs_binheap_node *e)
 312 {
 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;
 317         int                  did_sth = 0;
 318
 319         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 320         LASSERT(*cur_ptr == e);
 321
 322         while (cur_idx > 0) {
 323                 parent_idx = (cur_idx - 1) >> 1;
 324
 325                 parent_ptr = cfs_binheap_pointer(h, parent_idx);
 326                 LASSERT((*parent_ptr)->chn_index == parent_idx);
 327
 328                 if (h->cbh_ops->hop_compare(*parent_ptr, e))
 329                         break;
 330
 331                 (*parent_ptr)->chn_index = cur_idx;
 332                 *cur_ptr = *parent_ptr;
 333                 cur_ptr = parent_ptr;
 334                 cur_idx = parent_idx;
 335                 did_sth = 1;
 336         }
 337
 338         e->chn_index = cur_idx;
 339         *cur_ptr = e;
 340
 341         return did_sth;
 342 }
 343
 344 /**
 345  * Moves a node downwards, towards the last level of the binary tree.
 346  *
 347  * \param[in] h The heap
 348  * \param[in] e The node
 349  *
 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
 352  */
 353 static int
 354 cfs_binheap_sink(struct cfs_binheap *h, struct cfs_binheap_node *e)
 355 {
 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;
 365         int                  did_sth = 0;
 366
 367         cur_idx = e->chn_index;
 368         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 369         LASSERT(*cur_ptr == e);
 370
 371         while (cur_idx < n) {
 372                 child_idx = (cur_idx << 1) + 1;
 373                 if (child_idx >= n)
 374                         break;
 375
 376                 child_ptr = cfs_binheap_pointer(h, child_idx);
 377                 child = *child_ptr;
 378
 379                 child2_idx = child_idx + 1;
 380                 if (child2_idx < n) {
 381                         child2_ptr = cfs_binheap_pointer(h, child2_idx);
 382                         child2 = *child2_ptr;
 383
 384                         if (h->cbh_ops->hop_compare(child2, child)) {
 385                                 child_idx = child2_idx;
 386                                 child_ptr = child2_ptr;
 387                                 child = child2;
 388                         }
 389                 }
 390
 391                 LASSERT(child->chn_index == child_idx);
 392
 393                 if (h->cbh_ops->hop_compare(e, child))
 394                         break;
 395
 396                 child->chn_index = cur_idx;
 397                 *cur_ptr = child;
 398                 cur_ptr = child_ptr;
 399                 cur_idx = child_idx;
 400                 did_sth = 1;
 401         }
 402
 403         e->chn_index = cur_idx;
 404         *cur_ptr = e;
 405
 406         return did_sth;
 407 }
 408
 409 /**
 410  * Sort-inserts a node into the binary heap.
 411  *
 412  * \param[in] h The heap
 413  * \param[in] e The node
 414  *
 415  * \retval 0    Element inserted successfully
 416  * \retval != 0 error
 417  */
 418 int
 419 cfs_binheap_insert(struct cfs_binheap *h, struct cfs_binheap_node *e)
 420 {
 421         struct cfs_binheap_node **new_ptr;
 422         unsigned int         new_idx = h->cbh_nelements;
 423         int                  rc;
 424
 425         if (new_idx == h->cbh_hwm) {
 426                 rc = cfs_binheap_grow(h);
 427                 if (rc != 0)
 428                         return rc;
 429         }
 430
 431         if (h->cbh_ops->hop_enter) {
 432                 rc = h->cbh_ops->hop_enter(h, e);
 433                 if (rc != 0)
 434                         return rc;
 435         }
 436
 437         e->chn_index = new_idx;
 438         new_ptr = cfs_binheap_pointer(h, new_idx);
 439         h->cbh_nelements++;
 440         *new_ptr = e;
 441
 442         cfs_binheap_bubble(h, e);
 443
 444         return 0;
 445 }
 446 EXPORT_SYMBOL(cfs_binheap_insert);
 447
 448 /**
 449  * Removes a node from the binary heap.
 450  *
 451  * \param[in] h The heap
 452  * \param[in] e The node
 453  */
 454 void
 455 cfs_binheap_remove(struct cfs_binheap *h, struct cfs_binheap_node *e)
 456 {
 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;
 461
 462         LASSERT(cur_idx != CBH_POISON);
 463         LASSERT(cur_idx < n);
 464
 465         cur_ptr = cfs_binheap_pointer(h, cur_idx);
 466         LASSERT(*cur_ptr == e);
 467
 468         n--;
 469         last = *cfs_binheap_pointer(h, n);
 470         h->cbh_nelements = n;
 471         if (last == e)
 472                 return;
 473
 474         last->chn_index = cur_idx;
 475         *cur_ptr = last;
 476         cfs_binheap_relocate(h, *cur_ptr);
 477
 478         e->chn_index = CBH_POISON;
 479         if (h->cbh_ops->hop_exit)
 480                 h->cbh_ops->hop_exit(h, e);
 481 }
 482 EXPORT_SYMBOL(cfs_binheap_remove);
 483
 484 /**
 485  * Relocate a node in the binary heap.
 486  * Should be called whenever a node's values
 487  * which affects its ranking are changed.
 488  *
 489  * \param[in] h The heap
 490  * \param[in] e The node
 491  */
 492 void
 493 cfs_binheap_relocate(struct cfs_binheap *h, struct cfs_binheap_node *e)
 494 {
 495         if (!cfs_binheap_bubble(h, e))
 496                 cfs_binheap_sink(h, e);
 497 }
 498 EXPORT_SYMBOL(cfs_binheap_relocate);
 499 /** @} heap */