4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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.
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
23 * Copyright (c) 2011 Intel Corporation
26 * libcfs/include/libcfs/heap.h
28 * Author: Eric Barton <eeb@whamcloud.com>
29 * Liang Zhen <liang@whamcloud.com>
32 #ifndef __LIBCFS_HEAP_H__
33 #define __LIBCFS_HEAP_H__
35 /** \defgroup heap Binary heap
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
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
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.
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.
67 /** Index into the binary tree */
68 unsigned int chn_index;
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 *))
76 #define CBH_POISON 0xdeadbeef
82 CBH_FLAG_ATOMIC_GROW = 1,
88 * Binary heap operations.
92 * Called right before inserting a node into the binary heap.
94 * Implementing this operation is optional.
96 * \param[in] h The heap
97 * \param[in] e The node
102 int (*hop_enter)(struct cfs_binheap *h,
103 cfs_binheap_node_t *e);
105 * Called right after removing a node from the binary heap.
107 * Implementing this operation is optional.
109 * \param[in] h The heap
110 * \param[in] e The node
112 void (*hop_exit)(struct cfs_binheap *h,
113 cfs_binheap_node_t *e);
115 * A binary predicate which is called during internal heap sorting
116 * operations, and used in order to determine the relevant ordering of
119 * Implementing this operation is mandatory.
121 * \param[in] a The first heap node
122 * \param[in] b The second heap node
124 * \retval 0 Node a > node b
125 * \retval 1 Node a < node b
127 * \see cfs_binheap_bubble()
128 * \see cfs_biheap_sink()
130 int (*hop_compare)(cfs_binheap_node_t *a,
131 cfs_binheap_node_t *b);
135 * Binary heap object.
137 * Sorts elements of type \e cfs_binheap_node_t
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;
151 unsigned int cbh_flags;
152 /** operations table */
153 cfs_binheap_ops_t *cbh_ops;
156 /** associated CPT table */
157 struct cfs_cpt_table *cbh_cptab;
158 /** associated CPT id of this cfs_binheap_t::cbh_cptab */
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);
171 cfs_binheap_size(cfs_binheap_t *h)
173 return h->cbh_nelements;
177 cfs_binheap_is_empty(cfs_binheap_t *h)
179 return h->cbh_nelements == 0;
182 static inline cfs_binheap_node_t *
183 cfs_binheap_root(cfs_binheap_t *h)
185 return cfs_binheap_find(h, 0);
188 static inline cfs_binheap_node_t *
189 cfs_binheap_remove_root(cfs_binheap_t *h)
191 cfs_binheap_node_t *e = cfs_binheap_find(h, 0);
194 cfs_binheap_remove(h, e);
200 #endif /* __LIBCFS_HEAP_H__ */