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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>Xenomai API: include/nucleus/bheap.h Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.5 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="main.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
<li><a href="examples.html"><span>Examples</span></a></li>
<li>
<form action="search.php" method="get">
<table cellspacing="0" cellpadding="0" border="0">
<tr>
<td><label> <u>S</u>earch for </label></td>
<td><input type="text" name="query" value="" size="20" accesskey="s"/></td>
</tr>
</table>
</form>
</li>
</ul>
</div>
<h1>include/nucleus/bheap.h</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/*</span>
<a name="l00002"></a>00002 <span class="comment"> * Copyright (C) 2006 Gilles Chanteperdrix <gilles.chanteperdrix@laposte.net></span>
<a name="l00003"></a>00003 <span class="comment"> *</span>
<a name="l00004"></a>00004 <span class="comment"> * Xenomai is free software; you can redistribute it and/or modify</span>
<a name="l00005"></a>00005 <span class="comment"> * it under the terms of the GNU General Public License as published</span>
<a name="l00006"></a>00006 <span class="comment"> * by the Free Software Foundation; either version 2 of the License,</span>
<a name="l00007"></a>00007 <span class="comment"> * or (at your option) any later version.</span>
<a name="l00008"></a>00008 <span class="comment"> *</span>
<a name="l00009"></a>00009 <span class="comment"> * Xenomai is distributed in the hope that it will be useful, but</span>
<a name="l00010"></a>00010 <span class="comment"> * WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00011"></a>00011 <span class="comment"> * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU</span>
<a name="l00012"></a>00012 <span class="comment"> * General Public License for more details.</span>
<a name="l00013"></a>00013 <span class="comment"> *</span>
<a name="l00014"></a>00014 <span class="comment"> * You should have received a copy of the GNU General Public License</span>
<a name="l00015"></a>00015 <span class="comment"> * along with Xenomai; if not, write to the Free Software</span>
<a name="l00016"></a>00016 <span class="comment"> * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA</span>
<a name="l00017"></a>00017 <span class="comment"> * 02111-1307, USA.</span>
<a name="l00018"></a>00018 <span class="comment"> */</span>
<a name="l00019"></a>00019
<a name="l00020"></a>00020 <span class="preprocessor">#ifndef _XENO_NUCLEUS_BHEAP_H</span>
<a name="l00021"></a>00021 <span class="preprocessor"></span><span class="preprocessor">#define _XENO_NUCLEUS_BHEAP_H</span>
<a name="l00022"></a>00022 <span class="preprocessor"></span>
<a name="l00023"></a>00023 <span class="preprocessor">#include <nucleus/compiler.h></span>
<a name="l00024"></a>00024
<a name="l00025"></a>00025 <span class="comment">/* debug support */</span>
<a name="l00026"></a>00026 <span class="preprocessor">#include <nucleus/assert.h></span>
<a name="l00027"></a>00027
<a name="l00028"></a>00028 <span class="preprocessor">#ifndef CONFIG_XENO_OPT_DEBUG_QUEUES</span>
<a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">#define CONFIG_XENO_OPT_DEBUG_QUEUES 0</span>
<a name="l00030"></a>00030 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00031"></a>00031 <span class="preprocessor"></span>
<a name="l00032"></a>00032 <span class="comment">/* Priority queue implementation, using a binary heap. */</span>
<a name="l00033"></a>00033
<a name="l00034"></a>00034 <span class="keyword">typedef</span> <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> <span class="keywordtype">long</span> bheap_key_t;
<a name="l00035"></a>00035
<a name="l00036"></a>00036 <span class="keyword">typedef</span> <span class="keyword">struct </span>bheaph {
<a name="l00037"></a>00037 bheap_key_t key;
<a name="l00038"></a>00038 <span class="keywordtype">unsigned</span> prio;
<a name="l00039"></a>00039 <span class="keywordtype">unsigned</span> pos;
<a name="l00040"></a>00040 } bheaph_t;
<a name="l00041"></a>00041
<a name="l00042"></a>00042 <span class="preprocessor">#define bheaph_init(holder) do { } while (0)</span>
<a name="l00043"></a>00043 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_key(holder) ((holder)->key)</span>
<a name="l00044"></a>00044 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_prio(holder) ((holder)->prio)</span>
<a name="l00045"></a>00045 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_pos(holder) ((holder)->pos)</span>
<a name="l00046"></a>00046 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_lt(h1, h2) ((long long) ((h1)->key - (h2)->key) < 0 || \</span>
<a name="l00047"></a>00047 <span class="preprocessor"> ((h1)->key == (h2)->key && \</span>
<a name="l00048"></a>00048 <span class="preprocessor"> (h1)->prio > (h2)->prio))</span>
<a name="l00049"></a>00049 <span class="preprocessor"></span>
<a name="l00050"></a>00050 <span class="keyword">typedef</span> <span class="keyword">struct </span>bheap {
<a name="l00051"></a>00051 <span class="keywordtype">unsigned</span> sz;
<a name="l00052"></a>00052 <span class="keywordtype">unsigned</span> last;
<a name="l00053"></a>00053 bheaph_t *elems[1]; <span class="comment">/* only padding, indexing starts at 1 */</span>
<a name="l00054"></a>00054 } bheap_t;
<a name="l00055"></a>00055
<a name="l00056"></a>00056 <span class="preprocessor">#define DECLARE_BHEAP_CONTAINER(name, sz) \</span>
<a name="l00057"></a>00057 <span class="preprocessor"> struct { \</span>
<a name="l00058"></a>00058 <span class="preprocessor"> bheap_t bheap; \</span>
<a name="l00059"></a>00059 <span class="preprocessor"> bheaph_t *elems[sz]; \</span>
<a name="l00060"></a>00060 <span class="preprocessor"> } name</span>
<a name="l00061"></a>00061 <span class="preprocessor"></span>
<a name="l00062"></a>00062 <span class="comment">/* Check the binary heap invariant. */</span>
<a name="l00063"></a>00063 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> bheap_ordered(bheap_t *heap)
<a name="l00064"></a>00064 {
<a name="l00065"></a>00065 <span class="keywordtype">unsigned</span> i;
<a name="l00066"></a>00066 <span class="keywordflow">for</span> (i = 2; i < heap->last; i++)
<a name="l00067"></a>00067 <span class="keywordflow">if</span> (bheaph_lt(heap->elems[i], heap->elems[i / 2]))
<a name="l00068"></a>00068 <span class="keywordflow">return</span> 0;
<a name="l00069"></a>00069 <span class="keywordflow">return</span> 1;
<a name="l00070"></a>00070 }
<a name="l00071"></a>00071
<a name="l00072"></a>00072 <span class="preprocessor">#define BHEAP_CHECK(heap) \</span>
<a name="l00073"></a>00073 <span class="preprocessor"> XENO_BUGON(QUEUES, ((heap)->sz == 0) || !bheap_ordered(heap))</span>
<a name="l00074"></a>00074 <span class="preprocessor"></span>
<a name="l00075"></a>00075 <span class="preprocessor">#define bheap_gethead(heap) \</span>
<a name="l00076"></a>00076 <span class="preprocessor"> ({ \</span>
<a name="l00077"></a>00077 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00078"></a>00078 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00079"></a>00079 <span class="preprocessor"> __internal_bheap_gethead(_bheap); \</span>
<a name="l00080"></a>00080 <span class="preprocessor"> })</span>
<a name="l00081"></a>00081 <span class="preprocessor"></span>
<a name="l00082"></a>00082 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *__internal_bheap_gethead(bheap_t *heap)
<a name="l00083"></a>00083 {
<a name="l00084"></a>00084 <span class="keywordflow">if</span> (heap->last == 1)
<a name="l00085"></a>00085 <span class="keywordflow">return</span> NULL;
<a name="l00086"></a>00086
<a name="l00087"></a>00087 <span class="keywordflow">return</span> heap->elems[1];
<a name="l00088"></a>00088 }
<a name="l00089"></a>00089
<a name="l00090"></a>00090 <span class="preprocessor">#define bheap_next(heap, holder) \</span>
<a name="l00091"></a>00091 <span class="preprocessor"> ({ \</span>
<a name="l00092"></a>00092 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00093"></a>00093 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00094"></a>00094 <span class="preprocessor"> __internal_bheap_next(_bheap, holder); \</span>
<a name="l00095"></a>00095 <span class="preprocessor"> })</span>
<a name="l00096"></a>00096 <span class="preprocessor"></span>
<a name="l00097"></a>00097 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *__internal_bheap_next(bheap_t *heap, bheaph_t *holder)
<a name="l00098"></a>00098 {
<a name="l00099"></a>00099 <span class="keywordtype">unsigned</span> pos;
<a name="l00100"></a>00100
<a name="l00101"></a>00101 <span class="keywordflow">if</span> (unlikely(bheaph_pos(holder) >= heap->last
<a name="l00102"></a>00102 || heap->elems[bheaph_pos(holder)] != holder))
<a name="l00103"></a>00103 <span class="keywordflow">return</span> (bheaph_t *) ERR_PTR(-EINVAL);
<a name="l00104"></a>00104
<a name="l00105"></a>00105 pos = bheaph_pos(holder) + 1;
<a name="l00106"></a>00106
<a name="l00107"></a>00107 <span class="keywordflow">return</span> likely(pos < heap->last) ? heap->elems[pos] : NULL;
<a name="l00108"></a>00108 }
<a name="l00109"></a>00109
<a name="l00110"></a>00110 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *bheaph_parent(bheap_t *heap, bheaph_t *holder)
<a name="l00111"></a>00111 {
<a name="l00112"></a>00112 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> pos = holder->pos;
<a name="l00113"></a>00113
<a name="l00114"></a>00114 <span class="keywordflow">return</span> likely(pos > 1) ? heap->elems[pos / 2] : NULL;
<a name="l00115"></a>00115 }
<a name="l00116"></a>00116
<a name="l00117"></a>00117 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *bheaph_child(bheap_t *heap, bheaph_t *holder, <span class="keywordtype">int</span> side)
<a name="l00118"></a>00118 {
<a name="l00119"></a>00119 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> pos = 2 * holder->pos + side;
<a name="l00120"></a>00120
<a name="l00121"></a>00121 <span class="keywordflow">return</span> likely(pos < heap->last) ? heap->elems[pos] : NULL;
<a name="l00122"></a>00122 }
<a name="l00123"></a>00123
<a name="l00124"></a>00124 <span class="preprocessor">#define bheap_init(heap, sz) __internal_bheap_init(&(heap)->bheap, sz)</span>
<a name="l00125"></a>00125 <span class="preprocessor"></span>
<a name="l00126"></a>00126 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> __internal_bheap_init(bheap_t *heap, <span class="keywordtype">unsigned</span> sz)
<a name="l00127"></a>00127 {
<a name="l00128"></a>00128 heap->sz = sz;
<a name="l00129"></a>00129 heap->last = 1;
<a name="l00130"></a>00130 }
<a name="l00131"></a>00131
<a name="l00132"></a>00132 <span class="preprocessor">#define bheap_destroy(heap) __internal_bheap_destroy(&(heap)->bheap)</span>
<a name="l00133"></a>00133 <span class="preprocessor"></span>
<a name="l00134"></a>00134 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> __internal_bheap_destroy(bheap_t *heap)
<a name="l00135"></a>00135 {
<a name="l00136"></a>00136 heap->sz = 0;
<a name="l00137"></a>00137 heap->last = 1;
<a name="l00138"></a>00138 }
<a name="l00139"></a>00139
<a name="l00140"></a>00140 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
<a name="l00141"></a>00141 {
<a name="l00142"></a>00142 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> pos2 = bheaph_pos(h2);
<a name="l00143"></a>00143
<a name="l00144"></a>00144 heap->elems[bheaph_pos(h1)] = h2;
<a name="l00145"></a>00145 bheaph_pos(h2) = bheaph_pos(h1);
<a name="l00146"></a>00146 heap->elems[pos2] = h1;
<a name="l00147"></a>00147 bheaph_pos(h1) = pos2;
<a name="l00148"></a>00148 }
<a name="l00149"></a>00149
<a name="l00150"></a>00150 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> bheap_up(bheap_t *heap, bheaph_t *holder)
<a name="l00151"></a>00151 {
<a name="l00152"></a>00152 bheaph_t *parent;
<a name="l00153"></a>00153
<a name="l00154"></a>00154 <span class="keywordflow">while</span> ((parent = bheaph_parent(heap, holder)) && bheaph_lt(holder, parent))
<a name="l00155"></a>00155 bheap_swap(heap, holder, parent);
<a name="l00156"></a>00156 }
<a name="l00157"></a>00157
<a name="l00158"></a>00158 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> bheap_down(bheap_t *heap, bheaph_t *holder)
<a name="l00159"></a>00159 {
<a name="l00160"></a>00160 bheaph_t *left, *right, *minchild;
<a name="l00161"></a>00161
<a name="l00162"></a>00162 <span class="keywordflow">for</span> (;;) {
<a name="l00163"></a>00163 left = bheaph_child(heap, holder, 0);
<a name="l00164"></a>00164 right = bheaph_child(heap, holder, 1);
<a name="l00165"></a>00165
<a name="l00166"></a>00166 <span class="keywordflow">if</span> (left && right)
<a name="l00167"></a>00167 minchild = bheaph_lt(left, right) ? left : right;
<a name="l00168"></a>00168 <span class="keywordflow">else</span>
<a name="l00169"></a>00169 minchild = left ?: right;
<a name="l00170"></a>00170
<a name="l00171"></a>00171 <span class="keywordflow">if</span> (!minchild || bheaph_lt(holder, minchild))
<a name="l00172"></a>00172 <span class="keywordflow">break</span>;
<a name="l00173"></a>00173
<a name="l00174"></a>00174 bheap_swap(heap, minchild, holder);
<a name="l00175"></a>00175 }
<a name="l00176"></a>00176 }
<a name="l00177"></a>00177
<a name="l00178"></a>00178 <span class="preprocessor">#define bheap_insert(heap, holder) \</span>
<a name="l00179"></a>00179 <span class="preprocessor"> ({ \</span>
<a name="l00180"></a>00180 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00181"></a>00181 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00182"></a>00182 <span class="preprocessor"> __internal_bheap_insert(_bheap, holder); \</span>
<a name="l00183"></a>00183 <span class="preprocessor"> })</span>
<a name="l00184"></a>00184 <span class="preprocessor"></span>
<a name="l00185"></a>00185 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> __internal_bheap_insert(bheap_t *heap, bheaph_t *holder)
<a name="l00186"></a>00186 {
<a name="l00187"></a>00187 <span class="keywordflow">if</span> (heap->last == heap->sz + 1)
<a name="l00188"></a>00188 <span class="keywordflow">return</span> EBUSY;
<a name="l00189"></a>00189
<a name="l00190"></a>00190 heap->elems[heap->last] = holder;
<a name="l00191"></a>00191 bheaph_pos(holder) = heap->last;
<a name="l00192"></a>00192 ++heap->last;
<a name="l00193"></a>00193 bheap_up(heap, holder);
<a name="l00194"></a>00194 <span class="keywordflow">return</span> 0;
<a name="l00195"></a>00195 }
<a name="l00196"></a>00196
<a name="l00197"></a>00197 <span class="preprocessor">#define bheap_delete(heap, holder) \</span>
<a name="l00198"></a>00198 <span class="preprocessor"> ({ \</span>
<a name="l00199"></a>00199 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00200"></a>00200 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00201"></a>00201 <span class="preprocessor"> __internal_bheap_delete(_bheap, holder); \</span>
<a name="l00202"></a>00202 <span class="preprocessor"> })</span>
<a name="l00203"></a>00203 <span class="preprocessor"></span>
<a name="l00204"></a>00204 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> __internal_bheap_delete(bheap_t *heap, bheaph_t *holder)
<a name="l00205"></a>00205 {
<a name="l00206"></a>00206 bheaph_t *lasth;
<a name="l00207"></a>00207
<a name="l00208"></a>00208 <span class="keywordflow">if</span> (unlikely(bheaph_pos(holder) >= heap->last
<a name="l00209"></a>00209 || heap->elems[bheaph_pos(holder)] != holder))
<a name="l00210"></a>00210 <span class="keywordflow">return</span> EINVAL;
<a name="l00211"></a>00211
<a name="l00212"></a>00212 --heap->last;
<a name="l00213"></a>00213 <span class="keywordflow">if</span> (heap->last != bheaph_pos(holder)) {
<a name="l00214"></a>00214 bheaph_t *parent;
<a name="l00215"></a>00215 lasth = heap->elems[heap->last];
<a name="l00216"></a>00216 heap->elems[bheaph_pos(holder)] = lasth;
<a name="l00217"></a>00217 bheaph_pos(lasth) = bheaph_pos(holder);
<a name="l00218"></a>00218 <span class="keywordflow">if</span> ((parent = bheaph_parent(heap, lasth)) && bheaph_lt(lasth, parent))
<a name="l00219"></a>00219 bheap_up(heap, lasth);
<a name="l00220"></a>00220 <span class="keywordflow">else</span>
<a name="l00221"></a>00221 bheap_down(heap, lasth);
<a name="l00222"></a>00222 }
<a name="l00223"></a>00223
<a name="l00224"></a>00224 <span class="keywordflow">return</span> 0;
<a name="l00225"></a>00225 }
<a name="l00226"></a>00226
<a name="l00227"></a>00227 <span class="preprocessor">#define bheap_get(heap) \</span>
<a name="l00228"></a>00228 <span class="preprocessor"> ({ \</span>
<a name="l00229"></a>00229 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00230"></a>00230 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00231"></a>00231 <span class="preprocessor"> __internal_bheap_get(_bheap, holder); \</span>
<a name="l00232"></a>00232 <span class="preprocessor"> })</span>
<a name="l00233"></a>00233 <span class="preprocessor"></span>
<a name="l00234"></a>00234 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *__internal_bheap_get(bheap_t *heap)
<a name="l00235"></a>00235 {
<a name="l00236"></a>00236 bheaph_t *holder = __internal_bheap_gethead(heap);
<a name="l00237"></a>00237
<a name="l00238"></a>00238 <span class="keywordflow">if</span> (!holder)
<a name="l00239"></a>00239 <span class="keywordflow">return</span> NULL;
<a name="l00240"></a>00240
<a name="l00241"></a>00241 __internal_bheap_delete(heap, holder);
<a name="l00242"></a>00242
<a name="l00243"></a>00243 <span class="keywordflow">return</span> holder;
<a name="l00244"></a>00244 }
<a name="l00245"></a>00245
<a name="l00246"></a>00246 <span class="preprocessor">#endif </span><span class="comment">/* _XENO_NUCLEUS_BHEAP_H */</span>
</pre></div></div>
<hr size="1"><address style="text-align: right;"><small>Generated on Sun Jun 8 18:08:49 2008 for Xenomai API by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.5 </small></address>
</body>
</html>
|
