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
|
<!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.6 -->
<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@xenomai.org></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="comment">/* Priority queue implementation, using a binary heap. */</span>
<a name="l00029"></a>00029
<a name="l00030"></a>00030 <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="l00031"></a>00031
<a name="l00032"></a>00032 <span class="keyword">typedef</span> <span class="keyword">struct </span>bheaph {
<a name="l00033"></a>00033 bheap_key_t key;
<a name="l00034"></a>00034 <span class="keywordtype">unsigned</span> prio;
<a name="l00035"></a>00035 <span class="keywordtype">unsigned</span> pos;
<a name="l00036"></a>00036 } bheaph_t;
<a name="l00037"></a>00037
<a name="l00038"></a>00038 <span class="preprocessor">#define bheaph_init(holder) do { } while (0)</span>
<a name="l00039"></a>00039 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_key(holder) ((holder)->key)</span>
<a name="l00040"></a>00040 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_prio(holder) ((holder)->prio)</span>
<a name="l00041"></a>00041 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_pos(holder) ((holder)->pos)</span>
<a name="l00042"></a>00042 <span class="preprocessor"></span><span class="preprocessor">#define bheaph_lt(h1, h2) ((long long) ((h1)->key - (h2)->key) < 0 || \</span>
<a name="l00043"></a>00043 <span class="preprocessor"> ((h1)->key == (h2)->key && \</span>
<a name="l00044"></a>00044 <span class="preprocessor"> (h1)->prio > (h2)->prio))</span>
<a name="l00045"></a>00045 <span class="preprocessor"></span>
<a name="l00046"></a>00046 <span class="keyword">typedef</span> <span class="keyword">struct </span>bheap {
<a name="l00047"></a>00047 <span class="keywordtype">unsigned</span> sz;
<a name="l00048"></a>00048 <span class="keywordtype">unsigned</span> last;
<a name="l00049"></a>00049 bheaph_t *elems[1]; <span class="comment">/* only padding, indexing starts at 1 */</span>
<a name="l00050"></a>00050 } bheap_t;
<a name="l00051"></a>00051
<a name="l00052"></a>00052 <span class="preprocessor">#define DECLARE_BHEAP_CONTAINER(name, sz) \</span>
<a name="l00053"></a>00053 <span class="preprocessor"> struct { \</span>
<a name="l00054"></a>00054 <span class="preprocessor"> bheap_t bheap; \</span>
<a name="l00055"></a>00055 <span class="preprocessor"> bheaph_t *elems[sz]; \</span>
<a name="l00056"></a>00056 <span class="preprocessor"> } name</span>
<a name="l00057"></a>00057 <span class="preprocessor"></span>
<a name="l00058"></a>00058 <span class="comment">/* Check the binary heap invariant. */</span>
<a name="l00059"></a>00059 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> bheap_ordered(bheap_t *heap)
<a name="l00060"></a>00060 {
<a name="l00061"></a>00061 <span class="keywordtype">unsigned</span> i;
<a name="l00062"></a>00062 <span class="keywordflow">for</span> (i = 2; i < heap->last; i++)
<a name="l00063"></a>00063 <span class="keywordflow">if</span> (bheaph_lt(heap->elems[i], heap->elems[i / 2]))
<a name="l00064"></a>00064 <span class="keywordflow">return</span> 0;
<a name="l00065"></a>00065 <span class="keywordflow">return</span> 1;
<a name="l00066"></a>00066 }
<a name="l00067"></a>00067
<a name="l00068"></a>00068 <span class="preprocessor">#define BHEAP_CHECK(heap) \</span>
<a name="l00069"></a>00069 <span class="preprocessor"> XENO_BUGON(QUEUES, ((heap)->sz == 0) || !bheap_ordered(heap))</span>
<a name="l00070"></a>00070 <span class="preprocessor"></span>
<a name="l00071"></a>00071 <span class="preprocessor">#define bheap_gethead(heap) \</span>
<a name="l00072"></a>00072 <span class="preprocessor"> ({ \</span>
<a name="l00073"></a>00073 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00074"></a>00074 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00075"></a>00075 <span class="preprocessor"> __internal_bheap_gethead(_bheap); \</span>
<a name="l00076"></a>00076 <span class="preprocessor"> })</span>
<a name="l00077"></a>00077 <span class="preprocessor"></span>
<a name="l00078"></a>00078 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *__internal_bheap_gethead(bheap_t *heap)
<a name="l00079"></a>00079 {
<a name="l00080"></a>00080 <span class="keywordflow">if</span> (heap->last == 1)
<a name="l00081"></a>00081 <span class="keywordflow">return</span> NULL;
<a name="l00082"></a>00082
<a name="l00083"></a>00083 <span class="keywordflow">return</span> heap->elems[1];
<a name="l00084"></a>00084 }
<a name="l00085"></a>00085
<a name="l00086"></a>00086 <span class="preprocessor">#define bheap_next(heap, holder) \</span>
<a name="l00087"></a>00087 <span class="preprocessor"> ({ \</span>
<a name="l00088"></a>00088 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00089"></a>00089 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00090"></a>00090 <span class="preprocessor"> __internal_bheap_next(_bheap, holder); \</span>
<a name="l00091"></a>00091 <span class="preprocessor"> })</span>
<a name="l00092"></a>00092 <span class="preprocessor"></span>
<a name="l00093"></a>00093 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *__internal_bheap_next(bheap_t *heap, bheaph_t *holder)
<a name="l00094"></a>00094 {
<a name="l00095"></a>00095 <span class="keywordtype">unsigned</span> pos;
<a name="l00096"></a>00096
<a name="l00097"></a>00097 <span class="keywordflow">if</span> (unlikely(bheaph_pos(holder) >= heap->last
<a name="l00098"></a>00098 || heap->elems[bheaph_pos(holder)] != holder))
<a name="l00099"></a>00099 <span class="keywordflow">return</span> (bheaph_t *) ERR_PTR(-EINVAL);
<a name="l00100"></a>00100
<a name="l00101"></a>00101 pos = bheaph_pos(holder) + 1;
<a name="l00102"></a>00102
<a name="l00103"></a>00103 <span class="keywordflow">return</span> likely(pos < heap->last) ? heap->elems[pos] : NULL;
<a name="l00104"></a>00104 }
<a name="l00105"></a>00105
<a name="l00106"></a>00106 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *bheaph_parent(bheap_t *heap, bheaph_t *holder)
<a name="l00107"></a>00107 {
<a name="l00108"></a>00108 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> pos = holder->pos;
<a name="l00109"></a>00109
<a name="l00110"></a>00110 <span class="keywordflow">return</span> likely(pos > 1) ? heap->elems[pos / 2] : NULL;
<a name="l00111"></a>00111 }
<a name="l00112"></a>00112
<a name="l00113"></a>00113 <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="l00114"></a>00114 {
<a name="l00115"></a>00115 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> pos = 2 * holder->pos + side;
<a name="l00116"></a>00116
<a name="l00117"></a>00117 <span class="keywordflow">return</span> likely(pos < heap->last) ? heap->elems[pos] : NULL;
<a name="l00118"></a>00118 }
<a name="l00119"></a>00119
<a name="l00120"></a>00120 <span class="preprocessor">#define bheap_init(heap, sz) __internal_bheap_init(&(heap)->bheap, sz)</span>
<a name="l00121"></a>00121 <span class="preprocessor"></span>
<a name="l00122"></a>00122 <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="l00123"></a>00123 {
<a name="l00124"></a>00124 heap->sz = sz;
<a name="l00125"></a>00125 heap->last = 1;
<a name="l00126"></a>00126 }
<a name="l00127"></a>00127
<a name="l00128"></a>00128 <span class="preprocessor">#define bheap_destroy(heap) __internal_bheap_destroy(&(heap)->bheap)</span>
<a name="l00129"></a>00129 <span class="preprocessor"></span>
<a name="l00130"></a>00130 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> __internal_bheap_destroy(bheap_t *heap)
<a name="l00131"></a>00131 {
<a name="l00132"></a>00132 heap->sz = 0;
<a name="l00133"></a>00133 heap->last = 1;
<a name="l00134"></a>00134 }
<a name="l00135"></a>00135
<a name="l00136"></a>00136 <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="l00137"></a>00137 {
<a name="l00138"></a>00138 <span class="keyword">const</span> <span class="keywordtype">unsigned</span> pos2 = bheaph_pos(h2);
<a name="l00139"></a>00139
<a name="l00140"></a>00140 heap->elems[bheaph_pos(h1)] = h2;
<a name="l00141"></a>00141 bheaph_pos(h2) = bheaph_pos(h1);
<a name="l00142"></a>00142 heap->elems[pos2] = h1;
<a name="l00143"></a>00143 bheaph_pos(h1) = pos2;
<a name="l00144"></a>00144 }
<a name="l00145"></a>00145
<a name="l00146"></a>00146 <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="l00147"></a>00147 {
<a name="l00148"></a>00148 bheaph_t *parent;
<a name="l00149"></a>00149
<a name="l00150"></a>00150 <span class="keywordflow">while</span> ((parent = bheaph_parent(heap, holder)) && bheaph_lt(holder, parent))
<a name="l00151"></a>00151 bheap_swap(heap, holder, parent);
<a name="l00152"></a>00152 }
<a name="l00153"></a>00153
<a name="l00154"></a>00154 <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="l00155"></a>00155 {
<a name="l00156"></a>00156 bheaph_t *left, *right, *minchild;
<a name="l00157"></a>00157
<a name="l00158"></a>00158 <span class="keywordflow">for</span> (;;) {
<a name="l00159"></a>00159 left = bheaph_child(heap, holder, 0);
<a name="l00160"></a>00160 right = bheaph_child(heap, holder, 1);
<a name="l00161"></a>00161
<a name="l00162"></a>00162 <span class="keywordflow">if</span> (left && right)
<a name="l00163"></a>00163 minchild = bheaph_lt(left, right) ? left : right;
<a name="l00164"></a>00164 <span class="keywordflow">else</span>
<a name="l00165"></a>00165 minchild = left ?: right;
<a name="l00166"></a>00166
<a name="l00167"></a>00167 <span class="keywordflow">if</span> (!minchild || bheaph_lt(holder, minchild))
<a name="l00168"></a>00168 <span class="keywordflow">break</span>;
<a name="l00169"></a>00169
<a name="l00170"></a>00170 bheap_swap(heap, minchild, holder);
<a name="l00171"></a>00171 }
<a name="l00172"></a>00172 }
<a name="l00173"></a>00173
<a name="l00174"></a>00174 <span class="preprocessor">#define bheap_insert(heap, holder) \</span>
<a name="l00175"></a>00175 <span class="preprocessor"> ({ \</span>
<a name="l00176"></a>00176 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00177"></a>00177 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00178"></a>00178 <span class="preprocessor"> __internal_bheap_insert(_bheap, holder); \</span>
<a name="l00179"></a>00179 <span class="preprocessor"> })</span>
<a name="l00180"></a>00180 <span class="preprocessor"></span>
<a name="l00181"></a>00181 <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="l00182"></a>00182 {
<a name="l00183"></a>00183 <span class="keywordflow">if</span> (heap->last == heap->sz + 1)
<a name="l00184"></a>00184 <span class="keywordflow">return</span> EBUSY;
<a name="l00185"></a>00185
<a name="l00186"></a>00186 heap->elems[heap->last] = holder;
<a name="l00187"></a>00187 bheaph_pos(holder) = heap->last;
<a name="l00188"></a>00188 ++heap->last;
<a name="l00189"></a>00189 bheap_up(heap, holder);
<a name="l00190"></a>00190 <span class="keywordflow">return</span> 0;
<a name="l00191"></a>00191 }
<a name="l00192"></a>00192
<a name="l00193"></a>00193 <span class="preprocessor">#define bheap_delete(heap, holder) \</span>
<a name="l00194"></a>00194 <span class="preprocessor"> ({ \</span>
<a name="l00195"></a>00195 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00196"></a>00196 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00197"></a>00197 <span class="preprocessor"> __internal_bheap_delete(_bheap, holder); \</span>
<a name="l00198"></a>00198 <span class="preprocessor"> })</span>
<a name="l00199"></a>00199 <span class="preprocessor"></span>
<a name="l00200"></a>00200 <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="l00201"></a>00201 {
<a name="l00202"></a>00202 bheaph_t *lasth;
<a name="l00203"></a>00203
<a name="l00204"></a>00204 <span class="keywordflow">if</span> (unlikely(bheaph_pos(holder) >= heap->last
<a name="l00205"></a>00205 || heap->elems[bheaph_pos(holder)] != holder))
<a name="l00206"></a>00206 <span class="keywordflow">return</span> EINVAL;
<a name="l00207"></a>00207
<a name="l00208"></a>00208 --heap->last;
<a name="l00209"></a>00209 <span class="keywordflow">if</span> (heap->last != bheaph_pos(holder)) {
<a name="l00210"></a>00210 bheaph_t *parent;
<a name="l00211"></a>00211 lasth = heap->elems[heap->last];
<a name="l00212"></a>00212 heap->elems[bheaph_pos(holder)] = lasth;
<a name="l00213"></a>00213 bheaph_pos(lasth) = bheaph_pos(holder);
<a name="l00214"></a>00214 <span class="keywordflow">if</span> ((parent = bheaph_parent(heap, lasth)) && bheaph_lt(lasth, parent))
<a name="l00215"></a>00215 bheap_up(heap, lasth);
<a name="l00216"></a>00216 <span class="keywordflow">else</span>
<a name="l00217"></a>00217 bheap_down(heap, lasth);
<a name="l00218"></a>00218 }
<a name="l00219"></a>00219
<a name="l00220"></a>00220 <span class="keywordflow">return</span> 0;
<a name="l00221"></a>00221 }
<a name="l00222"></a>00222
<a name="l00223"></a>00223 <span class="preprocessor">#define bheap_get(heap) \</span>
<a name="l00224"></a>00224 <span class="preprocessor"> ({ \</span>
<a name="l00225"></a>00225 <span class="preprocessor"> bheap_t *_bheap = &(heap)->bheap; \</span>
<a name="l00226"></a>00226 <span class="preprocessor"> BHEAP_CHECK(_bheap); \</span>
<a name="l00227"></a>00227 <span class="preprocessor"> __internal_bheap_get(_bheap, holder); \</span>
<a name="l00228"></a>00228 <span class="preprocessor"> })</span>
<a name="l00229"></a>00229 <span class="preprocessor"></span>
<a name="l00230"></a>00230 <span class="keyword">static</span> <span class="keyword">inline</span> bheaph_t *__internal_bheap_get(bheap_t *heap)
<a name="l00231"></a>00231 {
<a name="l00232"></a>00232 bheaph_t *holder = __internal_bheap_gethead(heap);
<a name="l00233"></a>00233
<a name="l00234"></a>00234 <span class="keywordflow">if</span> (!holder)
<a name="l00235"></a>00235 <span class="keywordflow">return</span> NULL;
<a name="l00236"></a>00236
<a name="l00237"></a>00237 __internal_bheap_delete(heap, holder);
<a name="l00238"></a>00238
<a name="l00239"></a>00239 <span class="keywordflow">return</span> holder;
<a name="l00240"></a>00240 }
<a name="l00241"></a>00241
<a name="l00242"></a>00242 <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 Mon Aug 2 12:48:36 2010 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.6 </small></address>
</body>
</html>
|
