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
|
<!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/schedqueue.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/schedqueue.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) 2008 Philippe Gerum <rpm@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_SCHEDQUEUE_H</span>
<a name="l00021"></a>00021 <span class="preprocessor"></span><span class="preprocessor">#define _XENO_NUCLEUS_SCHEDQUEUE_H</span>
<a name="l00022"></a>00022 <span class="preprocessor"></span>
<a name="l00023"></a>00023 <span class="preprocessor">#include <nucleus/queue.h></span>
<a name="l00024"></a>00024
<a name="l00025"></a>00025 <span class="preprocessor">#ifdef CONFIG_XENO_OPT_SCALABLE_SCHED</span>
<a name="l00026"></a>00026 <span class="preprocessor"></span><span class="comment">/*</span>
<a name="l00027"></a>00027 <span class="comment"> * Multi-level priority queue, suitable for handling the runnable</span>
<a name="l00028"></a>00028 <span class="comment"> * thread queue of a scheduling class with O(1) property. We only</span>
<a name="l00029"></a>00029 <span class="comment"> * manage a descending queuing order, i.e. highest numbered priorities</span>
<a name="l00030"></a>00030 <span class="comment"> * come first.</span>
<a name="l00031"></a>00031 <span class="comment"> */</span>
<a name="l00032"></a>00032 <span class="preprocessor">#define XNSCHED_MLQ_LEVELS 264</span>
<a name="l00033"></a>00033 <span class="preprocessor"></span>
<a name="l00034"></a>00034 <span class="preprocessor">#if BITS_PER_LONG * BITS_PER_LONG < XNSCHED_MLQ_LEVELS</span>
<a name="l00035"></a>00035 <span class="preprocessor"></span><span class="preprocessor">#error "Internal bitmap cannot hold so many priority levels"</span>
<a name="l00036"></a>00036 <span class="preprocessor"></span><span class="preprocessor">#endif</span>
<a name="l00037"></a>00037 <span class="preprocessor"></span>
<a name="l00038"></a>00038 <span class="preprocessor">#define __MLQ_LONGS ((XNSCHED_MLQ_LEVELS+BITS_PER_LONG-1)/BITS_PER_LONG)</span>
<a name="l00039"></a>00039 <span class="preprocessor"></span>
<a name="l00040"></a>00040 <span class="keyword">struct </span>xnsched_mlq {
<a name="l00041"></a>00041
<a name="l00042"></a>00042 <span class="keywordtype">int</span> loprio, hiprio, elems;
<a name="l00043"></a>00043 <span class="keywordtype">unsigned</span> <span class="keywordtype">long</span> himap, lomap[__MLQ_LONGS];
<a name="l00044"></a>00044 <span class="keyword">struct </span>xnqueue queue[XNSCHED_MLQ_LEVELS];
<a name="l00045"></a>00045
<a name="l00046"></a>00046 };
<a name="l00047"></a>00047
<a name="l00048"></a>00048 <span class="preprocessor">#undef __MLQ_LONGS</span>
<a name="l00049"></a>00049 <span class="preprocessor"></span>
<a name="l00050"></a>00050 <span class="keywordtype">void</span> initmlq(<span class="keyword">struct</span> xnsched_mlq *q, <span class="keywordtype">int</span> loprio, <span class="keywordtype">int</span> hiprio);
<a name="l00051"></a>00051
<a name="l00052"></a>00052 <span class="keywordtype">void</span> addmlq(<span class="keyword">struct</span> xnsched_mlq *q,
<a name="l00053"></a>00053 <span class="keyword">struct</span> xnpholder *holder, <span class="keywordtype">int</span> idx, <span class="keywordtype">int</span> lifo);
<a name="l00054"></a>00054
<a name="l00055"></a>00055 <span class="keywordtype">void</span> removemlq(<span class="keyword">struct</span> xnsched_mlq *q, <span class="keyword">struct</span> xnpholder *holder);
<a name="l00056"></a>00056
<a name="l00057"></a>00057 <span class="keyword">struct </span>xnpholder *findmlqh(<span class="keyword">struct</span> xnsched_mlq *q, <span class="keywordtype">int</span> prio);
<a name="l00058"></a>00058
<a name="l00059"></a>00059 <span class="keyword">struct </span>xnpholder *getheadmlq(<span class="keyword">struct</span> xnsched_mlq *q);
<a name="l00060"></a>00060
<a name="l00061"></a>00061 <span class="keyword">struct </span>xnpholder *getmlq(<span class="keyword">struct</span> xnsched_mlq *q);
<a name="l00062"></a>00062
<a name="l00063"></a>00063 <span class="keyword">struct </span>xnpholder *nextmlq(<span class="keyword">struct</span> xnsched_mlq *q,
<a name="l00064"></a>00064 <span class="keyword">struct</span> xnpholder *h);
<a name="l00065"></a>00065
<a name="l00066"></a>00066 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> countmlq(<span class="keyword">struct</span> xnsched_mlq *q)
<a name="l00067"></a>00067 {
<a name="l00068"></a>00068 <span class="keywordflow">return</span> q->elems;
<a name="l00069"></a>00069 }
<a name="l00070"></a>00070
<a name="l00071"></a>00071 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> emptymlq_p(<span class="keyword">struct</span> xnsched_mlq *q)
<a name="l00072"></a>00072 {
<a name="l00073"></a>00073 <span class="keywordflow">return</span> q->himap == 0;
<a name="l00074"></a>00074 }
<a name="l00075"></a>00075
<a name="l00076"></a>00076 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> indexmlq(<span class="keyword">struct</span> xnsched_mlq *q, <span class="keywordtype">int</span> prio)
<a name="l00077"></a>00077 {
<a name="l00078"></a>00078 XENO_ASSERT(QUEUES,
<a name="l00079"></a>00079 prio >= q->loprio && prio <= q->hiprio,
<a name="l00080"></a>00080 xnpod_fatal(<span class="stringliteral">"priority level %d is out of range "</span>, prio));
<a name="l00081"></a>00081 <span class="comment">/*</span>
<a name="l00082"></a>00082 <span class="comment"> * BIG FAT WARNING: We need to rescale the priority level to a</span>
<a name="l00083"></a>00083 <span class="comment"> * 0-based range. We use ffnz() to scan the bitmap which MUST</span>
<a name="l00084"></a>00084 <span class="comment"> * be based on a bit scan forward op. Therefore, the lower the</span>
<a name="l00085"></a>00085 <span class="comment"> * index value, the higher the priority (since least</span>
<a name="l00086"></a>00086 <span class="comment"> * significant bits will be found first when scanning the</span>
<a name="l00087"></a>00087 <span class="comment"> * bitmaps).</span>
<a name="l00088"></a>00088 <span class="comment"> */</span>
<a name="l00089"></a>00089 <span class="keywordflow">return</span> q->hiprio - prio;
<a name="l00090"></a>00090 }
<a name="l00091"></a>00091
<a name="l00092"></a>00092 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">int</span> ffsmlq(<span class="keyword">struct</span> xnsched_mlq *q)
<a name="l00093"></a>00093 {
<a name="l00094"></a>00094 <span class="keywordtype">int</span> hi = ffnz(q->himap);
<a name="l00095"></a>00095 <span class="keywordtype">int</span> lo = ffnz(q->lomap[hi]);
<a name="l00096"></a>00096 <span class="keywordflow">return</span> hi * BITS_PER_LONG + lo; <span class="comment">/* Result is undefined if none set. */</span>
<a name="l00097"></a>00097 }
<a name="l00098"></a>00098
<a name="l00099"></a>00099 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> insertmlql(<span class="keyword">struct</span> xnsched_mlq *q,
<a name="l00100"></a>00100 <span class="keyword">struct</span> xnpholder *holder, <span class="keywordtype">int</span> prio)
<a name="l00101"></a>00101 {
<a name="l00102"></a>00102 addmlq(q, holder, indexmlq(q, prio), 1);
<a name="l00103"></a>00103 }
<a name="l00104"></a>00104
<a name="l00105"></a>00105 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> insertmlqf(<span class="keyword">struct</span> xnsched_mlq *q,
<a name="l00106"></a>00106 <span class="keyword">struct</span> xnpholder *holder, <span class="keywordtype">int</span> prio)
<a name="l00107"></a>00107 {
<a name="l00108"></a>00108 addmlq(q, holder, indexmlq(q, prio), 0);
<a name="l00109"></a>00109 }
<a name="l00110"></a>00110
<a name="l00111"></a>00111 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> appendmlq(<span class="keyword">struct</span> xnsched_mlq *q, <span class="keyword">struct</span> xnpholder *holder)
<a name="l00112"></a>00112 {
<a name="l00113"></a>00113 addmlq(q, holder, indexmlq(q, q->hiprio), 0);
<a name="l00114"></a>00114 }
<a name="l00115"></a>00115
<a name="l00116"></a>00116 <span class="keyword">static</span> <span class="keyword">inline</span> <span class="keywordtype">void</span> prependmlq(<span class="keyword">struct</span> xnsched_mlq *q, <span class="keyword">struct</span> xnpholder *holder)
<a name="l00117"></a>00117 {
<a name="l00118"></a>00118 addmlq(q, holder, indexmlq(q, q->loprio), 1);
<a name="l00119"></a>00119 }
<a name="l00120"></a>00120
<a name="l00121"></a>00121 <span class="keyword">typedef</span> <span class="keyword">struct </span>xnsched_mlq xnsched_queue_t;
<a name="l00122"></a>00122
<a name="l00123"></a>00123 <span class="preprocessor">#define sched_initpq initmlq</span>
<a name="l00124"></a>00124 <span class="preprocessor"></span><span class="preprocessor">#define sched_emptypq_p emptymlq_p</span>
<a name="l00125"></a>00125 <span class="preprocessor"></span><span class="preprocessor">#define sched_insertpql insertmlql</span>
<a name="l00126"></a>00126 <span class="preprocessor"></span><span class="preprocessor">#define sched_insertpqf insertmlqf</span>
<a name="l00127"></a>00127 <span class="preprocessor"></span><span class="preprocessor">#define sched_appendpq appendmlq</span>
<a name="l00128"></a>00128 <span class="preprocessor"></span><span class="preprocessor">#define sched_prependpq prependmlq</span>
<a name="l00129"></a>00129 <span class="preprocessor"></span><span class="preprocessor">#define sched_removepq removemlq</span>
<a name="l00130"></a>00130 <span class="preprocessor"></span><span class="preprocessor">#define sched_getheadpq getheadmlq</span>
<a name="l00131"></a>00131 <span class="preprocessor"></span><span class="preprocessor">#define sched_nextpq nextmlq</span>
<a name="l00132"></a>00132 <span class="preprocessor"></span><span class="preprocessor">#define sched_getpq getmlq</span>
<a name="l00133"></a>00133 <span class="preprocessor"></span><span class="preprocessor">#define sched_findpqh findmlqh</span>
<a name="l00134"></a>00134 <span class="preprocessor"></span>
<a name="l00135"></a>00135 <span class="preprocessor">#else </span><span class="comment">/* ! CONFIG_XENO_OPT_SCALABLE_SCHED */</span>
<a name="l00136"></a>00136
<a name="l00137"></a>00137 <span class="keyword">typedef</span> xnpqueue_t xnsched_queue_t;
<a name="l00138"></a>00138
<a name="l00139"></a>00139 <span class="preprocessor">#define sched_initpq(q, minp, maxp) initpq(q)</span>
<a name="l00140"></a>00140 <span class="preprocessor"></span><span class="preprocessor">#define sched_emptypq_p emptypq_p</span>
<a name="l00141"></a>00141 <span class="preprocessor"></span><span class="preprocessor">#define sched_insertpql insertpql</span>
<a name="l00142"></a>00142 <span class="preprocessor"></span><span class="preprocessor">#define sched_insertpqf insertpqf</span>
<a name="l00143"></a>00143 <span class="preprocessor"></span><span class="preprocessor">#define sched_appendpq appendpq</span>
<a name="l00144"></a>00144 <span class="preprocessor"></span><span class="preprocessor">#define sched_prependpq prependpq</span>
<a name="l00145"></a>00145 <span class="preprocessor"></span><span class="preprocessor">#define sched_removepq removepq</span>
<a name="l00146"></a>00146 <span class="preprocessor"></span><span class="preprocessor">#define sched_getheadpq getheadpq</span>
<a name="l00147"></a>00147 <span class="preprocessor"></span><span class="preprocessor">#define sched_nextpq nextpq</span>
<a name="l00148"></a>00148 <span class="preprocessor"></span><span class="preprocessor">#define sched_getpq getpq</span>
<a name="l00149"></a>00149 <span class="preprocessor"></span><span class="preprocessor">#define sched_findpqh findpqh</span>
<a name="l00150"></a>00150 <span class="preprocessor"></span>
<a name="l00151"></a>00151 <span class="preprocessor">#endif </span><span class="comment">/* !CONFIG_XENO_OPT_SCALABLE_SCHED */</span>
<a name="l00152"></a>00152
<a name="l00153"></a>00153 <span class="preprocessor">#endif </span><span class="comment">/* !_XENO_NUCLEUS_SCHEDQUEUE_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>
|
