lustre/ptlrpc/heap.h

   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  * GPL HEADER END
  17  */
  18 /*
  19  * Copyright (c) 2011 Intel Corporation
  20  */
  21 /*
  22  * libcfs/include/libcfs/heap.h
  23  *
  24  * Author: Eric Barton  <eeb@whamcloud.com>
  25  *         Liang Zhen   <liang@whamcloud.com>
  26  */
  27
  28 #ifndef __LIBCFS_HEAP_H__
  29 #define __LIBCFS_HEAP_H__
  30
  31 /** \defgroup heap Binary heap
  32  *
  33  * The binary heap is a scalable data structure created using a binary tree. It
  34  * is capable of maintaining large sets of elements sorted usually by one or
  35  * more element properties, but really based on anything that can be used as a
  36  * binary predicate in order to determine the relevant ordering of any two nodes
  37  * that belong to the set. There is no search operation, rather the intention is
  38  * for the element of the lowest priority which will always be at the root of
  39  * the tree (as this is an implementation of a min-heap) to be removed by users
  40  * for consumption.
  41  *
  42  * Users of the heap should embed a \e struct binheap_node object instance
  43  * on every object of the set that they wish the binary heap instance to handle,
  44  * and (at a minimum) provide a struct binheap_ops::hop_compare()
  45  * implementation which is used by the heap as the binary predicate during its
  46  * internal sorting operations.
  47  *
  48  * The current implementation enforces no locking scheme, and so assumes the
  49  * user caters for locking between calls to insert, delete and lookup
  50  * operations. Since the only consumer for the data structure at this point
  51  * are NRS policies, and these operate on a per-CPT basis, binary heap instances
  52  * are tied to a specific CPT.
  53  * @{
  54  */
  55
  56 #define CBH_SHIFT       9
  57 #define CBH_SIZE       (1 << CBH_SHIFT)             /* # ptrs per level */
  58 #define CBH_MASK       (CBH_SIZE - 1)
  59 #define CBH_NOB        (CBH_SIZE * sizeof(struct binheap_node *))
  60
  61 #define CBH_POISON      0xdeadbeef
  62
  63 /**
  64  * Binary heap flags.
  65  */
  66 enum {
  67         CBH_FLAG_ATOMIC_GROW    = 1,
  68 };
  69
  70 struct binheap;
  71
  72 /**
  73  * Binary heap operations.
  74  */
  75 struct binheap_ops {
  76         /**
  77          * Called right before inserting a node into the binary heap.
  78          *
  79          * Implementing this operation is optional.
  80          *
  81          * \param[in] h The heap
  82          * \param[in] e The node
  83          *
  84          * \retval 0 success
  85          * \retval != 0 error
  86          */
  87         int             (*hop_enter)(struct binheap *h,
  88                                      struct binheap_node *e);
  89         /**
  90          * Called right after removing a node from the binary heap.
  91          *
  92          * Implementing this operation is optional.
  93          *
  94          * \param[in] h The heap
  95          * \param[in] e The node
  96          */
  97         void            (*hop_exit)(struct binheap *h,
  98                                     struct binheap_node *e);
  99         /**
 100          * A binary predicate which is called during internal heap sorting
 101          * operations, and used in order to determine the relevant ordering of
 102          * two heap nodes.
 103          *
 104          * Implementing this operation is mandatory.
 105          *
 106          * \param[in] a The first heap node
 107          * \param[in] b The second heap node
 108          *
 109          * \retval 0 Node a > node b
 110          * \retval 1 Node a < node b
 111          *
 112          * \see binheap_bubble()
 113          * \see cfs_biheap_sink()
 114          */
 115         int             (*hop_compare)(struct binheap_node *a,
 116                                        struct binheap_node *b);
 117 };
 118
 119 /**
 120  * Binary heap object.
 121  *
 122  * Sorts elements of type \e struct binheap_node
 123  */
 124 struct binheap {
 125         /** Triple indirect */
 126         struct binheap_node  ****cbh_elements3;
 127         /** double indirect */
 128         struct binheap_node   ***cbh_elements2;
 129         /** single indirect */
 130         struct binheap_node    **cbh_elements1;
 131         /** # elements referenced */
 132         unsigned int            cbh_nelements;
 133         /** high water mark */
 134         unsigned int            cbh_hwm;
 135         /** user flags */
 136         unsigned int            cbh_flags;
 137         /** operations table */
 138         struct binheap_ops *cbh_ops;
 139         /** private data */
 140         void                   *cbh_private;
 141         /** associated CPT table */
 142         struct cfs_cpt_table   *cbh_cptab;
 143         /** associated CPT id of this struct binheap::cbh_cptab */
 144         int                     cbh_cptid;
 145 };
 146
 147 void binheap_destroy(struct binheap *h);
 148 struct binheap *
 149 binheap_create(struct binheap_ops *ops, unsigned int flags,
 150                    unsigned int count, void *arg, struct cfs_cpt_table *cptab,
 151                    int cptid);
 152 struct binheap_node *
 153 binheap_find(struct binheap *h, unsigned int idx);
 154 int binheap_insert(struct binheap *h, struct binheap_node *e);
 155 void binheap_remove(struct binheap *h, struct binheap_node *e);
 156 void binheap_relocate(struct binheap *h, struct binheap_node *e);
 157
 158 static inline int
 159 binheap_size(struct binheap *h)
 160 {
 161         return h->cbh_nelements;
 162 }
 163
 164 static inline int
 165 binheap_is_empty(struct binheap *h)
 166 {
 167         return h->cbh_nelements == 0;
 168 }
 169
 170 static inline struct binheap_node *
 171 binheap_root(struct binheap *h)
 172 {
 173         return binheap_find(h, 0);
 174 }
 175
 176 static inline struct binheap_node *
 177 binheap_remove_root(struct binheap *h)
 178 {
 179         struct binheap_node *e = binheap_find(h, 0);
 180
 181         if (e != NULL)
 182                 binheap_remove(h, e);
 183         return e;
 184 }
 185
 186 /** @} heap */
 187
 188 #endif /* __LIBCFS_HEAP_H__ */