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