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.
19 * Copyright (c) 2011 Intel Corporation
22 * libcfs/include/libcfs/heap.h
24 * Author: Eric Barton <eeb@whamcloud.com>
25 * Liang Zhen <liang@whamcloud.com>
28 #ifndef __LIBCFS_HEAP_H__
29 #define __LIBCFS_HEAP_H__
31 /** \defgroup heap Binary heap
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
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.
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.
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 *))
61 #define CBH_POISON 0xdeadbeef
67 CBH_FLAG_ATOMIC_GROW = 1,
73 * Binary heap operations.
77 * Called right before inserting a node into the binary heap.
79 * Implementing this operation is optional.
81 * \param[in] h The heap
82 * \param[in] e The node
87 int (*hop_enter)(struct binheap *h,
88 struct binheap_node *e);
90 * Called right after removing a node from the binary heap.
92 * Implementing this operation is optional.
94 * \param[in] h The heap
95 * \param[in] e The node
97 void (*hop_exit)(struct binheap *h,
98 struct binheap_node *e);
100 * A binary predicate which is called during internal heap sorting
101 * operations, and used in order to determine the relevant ordering of
104 * Implementing this operation is mandatory.
106 * \param[in] a The first heap node
107 * \param[in] b The second heap node
109 * \retval 0 Node a > node b
110 * \retval 1 Node a < node b
112 * \see binheap_bubble()
113 * \see cfs_biheap_sink()
115 int (*hop_compare)(struct binheap_node *a,
116 struct binheap_node *b);
120 * Binary heap object.
122 * Sorts elements of type \e struct binheap_node
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;
136 unsigned int cbh_flags;
137 /** operations table */
138 struct binheap_ops *cbh_ops;
141 /** associated CPT table */
142 struct cfs_cpt_table *cbh_cptab;
143 /** associated CPT id of this struct binheap::cbh_cptab */
147 void binheap_destroy(struct binheap *h);
149 binheap_create(struct binheap_ops *ops, unsigned int flags,
150 unsigned int count, void *arg, struct cfs_cpt_table *cptab,
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);
159 binheap_size(struct binheap *h)
161 return h->cbh_nelements;
165 binheap_is_empty(struct binheap *h)
167 return h->cbh_nelements == 0;
170 static inline struct binheap_node *
171 binheap_root(struct binheap *h)
173 return binheap_find(h, 0);
176 static inline struct binheap_node *
177 binheap_remove_root(struct binheap *h)
179 struct binheap_node *e = binheap_find(h, 0);
182 binheap_remove(h, e);
188 #endif /* __LIBCFS_HEAP_H__ */