1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
|
/*
* GPL HEADER START
*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License version 2 only,
* as published by the Free Software Foundation.
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License version 2 for more details. A copy is
* included in the COPYING file that accompanied this code.
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
* GPL HEADER END
*/
/*
* Copyright (c) 2011 Intel Corporation
*/
/*
* libcfs/include/libcfs/heap.h
*
* Author: Eric Barton <eeb@whamcloud.com>
* Liang Zhen <liang@whamcloud.com>
*/
#ifndef __LIBCFS_HEAP_H__
#define __LIBCFS_HEAP_H__
/** \defgroup heap Binary heap
*
* The binary heap is a scalable data structure created using a binary tree. It
* is capable of maintaining large sets of elements sorted usually by one or
* more element properties, but really based on anything that can be used as a
* binary predicate in order to determine the relevant ordering of any two nodes
* that belong to the set. There is no search operation, rather the intention is
* for the element of the lowest priority which will always be at the root of
* the tree (as this is an implementation of a min-heap) to be removed by users
* for consumption.
*
* Users of the heap should embed a \e cfs_binheap_node_t object instance on
* every object of the set that they wish the binary heap instance to handle,
* and (at a minimum) provide a cfs_binheap_ops_t::hop_compare() implementation
* which is used by the heap as the binary predicate during its internal sorting
* operations.
*
* The current implementation enforces no locking scheme, and so assumes the
* user caters for locking between calls to insert, delete and lookup
* operations. Since the only consumer for the data structure at this point
* are NRS policies, and these operate on a per-CPT basis, binary heap instances
* are tied to a specific CPT.
* @{
*/
/**
* Binary heap node.
*
* Objects of this type are embedded into objects of the ordered set that is to
* be maintained by a \e cfs_binheap_t instance.
*/
typedef struct {
/** Index into the binary tree */
unsigned int chn_index;
} cfs_binheap_node_t;
#define CBH_SHIFT 9
#define CBH_SIZE (1 << CBH_SHIFT) /* # ptrs per level */
#define CBH_MASK (CBH_SIZE - 1)
#define CBH_NOB (CBH_SIZE * sizeof(cfs_binheap_node_t *))
#define CBH_POISON 0xdeadbeef
/**
* Binary heap flags.
*/
enum {
CBH_FLAG_ATOMIC_GROW = 1,
};
struct cfs_binheap;
/**
* Binary heap operations.
*/
typedef struct {
/**
* Called right before inserting a node into the binary heap.
*
* Implementing this operation is optional.
*
* \param[in] h The heap
* \param[in] e The node
*
* \retval 0 success
* \retval != 0 error
*/
int (*hop_enter)(struct cfs_binheap *h,
cfs_binheap_node_t *e);
/**
* Called right after removing a node from the binary heap.
*
* Implementing this operation is optional.
*
* \param[in] h The heap
* \param[in] e The node
*/
void (*hop_exit)(struct cfs_binheap *h,
cfs_binheap_node_t *e);
/**
* A binary predicate which is called during internal heap sorting
* operations, and used in order to determine the relevant ordering of
* two heap nodes.
*
* Implementing this operation is mandatory.
*
* \param[in] a The first heap node
* \param[in] b The second heap node
*
* \retval 0 Node a > node b
* \retval 1 Node a < node b
*
* \see cfs_binheap_bubble()
* \see cfs_biheap_sink()
*/
int (*hop_compare)(cfs_binheap_node_t *a,
cfs_binheap_node_t *b);
} cfs_binheap_ops_t;
/**
* Binary heap object.
*
* Sorts elements of type \e cfs_binheap_node_t
*/
typedef struct cfs_binheap {
/** Triple indirect */
cfs_binheap_node_t ****cbh_elements3;
/** double indirect */
cfs_binheap_node_t ***cbh_elements2;
/** single indirect */
cfs_binheap_node_t **cbh_elements1;
/** # elements referenced */
unsigned int cbh_nelements;
/** high water mark */
unsigned int cbh_hwm;
/** user flags */
unsigned int cbh_flags;
/** operations table */
cfs_binheap_ops_t *cbh_ops;
/** private data */
void *cbh_private;
/** associated CPT table */
struct cfs_cpt_table *cbh_cptab;
/** associated CPT id of this cfs_binheap_t::cbh_cptab */
int cbh_cptid;
} cfs_binheap_t;
void cfs_binheap_destroy(cfs_binheap_t *h);
cfs_binheap_t *cfs_binheap_create(cfs_binheap_ops_t *ops, unsigned int flags,
unsigned count, void *arg,
struct cfs_cpt_table *cptab, int cptid);
cfs_binheap_node_t *cfs_binheap_find(cfs_binheap_t *h, unsigned int idx);
int cfs_binheap_insert(cfs_binheap_t *h, cfs_binheap_node_t *e);
void cfs_binheap_remove(cfs_binheap_t *h, cfs_binheap_node_t *e);
static inline int
cfs_binheap_size(cfs_binheap_t *h)
{
return h->cbh_nelements;
}
static inline int
cfs_binheap_is_empty(cfs_binheap_t *h)
{
return h->cbh_nelements == 0;
}
static inline cfs_binheap_node_t *
cfs_binheap_root(cfs_binheap_t *h)
{
return cfs_binheap_find(h, 0);
}
static inline cfs_binheap_node_t *
cfs_binheap_remove_root(cfs_binheap_t *h)
{
cfs_binheap_node_t *e = cfs_binheap_find(h, 0);
if (e != NULL)
cfs_binheap_remove(h, e);
return e;
}
/** @} heap */
#endif /* __LIBCFS_HEAP_H__ */
|
