Whamcloud - gitweb
LU-3494 libcfs: Add relocation function to libcfs heap
[fs/lustre-release.git] / 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 cfs_binheap_node_t object instance on
47  * every object of the set that they wish the binary heap instance to handle,
48  * and (at a minimum) provide a cfs_binheap_ops_t::hop_compare() implementation
49  * which is used by the heap as the binary predicate during its internal sorting
50  * 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 cfs_binheap_t instance.
65  */
66 typedef struct {
67         /** Index into the binary tree */
68         unsigned int    chn_index;
69 } cfs_binheap_node_t;
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(cfs_binheap_node_t *))
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 typedef struct {
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                                      cfs_binheap_node_t *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                                     cfs_binheap_node_t *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)(cfs_binheap_node_t *a,
131                                        cfs_binheap_node_t *b);
132 } cfs_binheap_ops_t;
133
134 /**
135  * Binary heap object.
136  *
137  * Sorts elements of type \e cfs_binheap_node_t
138  */
139 typedef struct cfs_binheap {
140         /** Triple indirect */
141         cfs_binheap_node_t  ****cbh_elements3;
142         /** double indirect */
143         cfs_binheap_node_t   ***cbh_elements2;
144         /** single indirect */
145         cfs_binheap_node_t    **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         cfs_binheap_ops_t      *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 cfs_binheap_t::cbh_cptab */
159         int                     cbh_cptid;
160 } cfs_binheap_t;
161
162 void cfs_binheap_destroy(cfs_binheap_t *h);
163 cfs_binheap_t *cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
164                                   unsigned count, void *arg,
165                                   struct cfs_cpt_table *cptab, int cptid);
166 cfs_binheap_node_t *cfs_binheap_find(cfs_binheap_t *h, unsigned int idx);
167 int cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e);
168 void cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e);
169 void cfs_binheap_relocate(cfs_binheap_t *h, cfs_binheap_node_t *e);
170
171 static inline int
172 cfs_binheap_size(cfs_binheap_t *h)
173 {
174         return h->cbh_nelements;
175 }
176
177 static inline int
178 cfs_binheap_is_empty(cfs_binheap_t *h)
179 {
180         return h->cbh_nelements == 0;
181 }
182
183 static inline cfs_binheap_node_t *
184 cfs_binheap_root(cfs_binheap_t *h)
185 {
186         return cfs_binheap_find(h, 0);
187 }
188
189 static inline cfs_binheap_node_t *
190 cfs_binheap_remove_root(cfs_binheap_t *h)
191 {
192         cfs_binheap_node_t *e = cfs_binheap_find(h, 0);
193
194         if (e != NULL)
195                 cfs_binheap_remove(h, e);
196         return e;
197 }
198
199 /** @} heap */
200
201 #endif /* __LIBCFS_HEAP_H__ */