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 package ti.sysbios.knl;
37
38 import xdc.rov.ViewInfo;
39
40 /*!
41 * ======== Queue ========
42 * Queue manager.
43 *
44 * The Queue module makes available a set of functions that manipulate
45 * queue objects accessed through handles of type Queue_Handle.
46 * Each queue contains a linked sequence of zero or more elements
47 * referenced through variables of type Queue_Elem, which are
48 * embedded as the first field within a structure.
49 *
50 * In the Queue API descriptions, the APIs which disable interrupts before
51 * modifying the Queue are noted as "atomic", while APIs that do not disable
52 * interrupts are "non-atomic".
53 *
54 * Queues are represented as doubly-linked lists, so calls to Queue_next
55 * or Queue_prev can loop continuously over the Queue. The following code
56 * demonstrates one way to iterate over a Queue once from beginning to end.
57 * In this example, 'myQ' is a Queue_Handle.
58 *
59 * @p(code)
60 * Queue_Elem *elem;
61 *
62 * for (elem = Queue_head(myQ);
63 * elem != (Queue_Elem *)myQ;
64 * elem = Queue_next(elem)) {
65 * ...
66 * }
67 * @p
68 *
69 * Below is a simple example of how to create a Queue, enqueue two elements,
70 * and dequeue the elements until the queue is empty:
71 *
72 * @p(code)
73 * #include <xdc/std.h>
74 * #include <xdc/runtime/System.h>
75 *
76 * #include <ti/sysbios/knl/Queue.h>
77 *
78 * typedef struct Rec {
79 * Queue_Elem _elem;
80 * Int data;
81 * } Rec;
82 *
83 * Int main(Int argc, Char *argv[])
84 * {
85 * Queue_Handle q;
86 * Rec r1, r2;
87 * Rec* rp;
88 *
89 * r1.data = 100;
90 * r2.data = 200;
91 *
92 *
93 * // create a Queue instance 'q'
94 * q = Queue_create(NULL, NULL);
95 *
96 *
97 * // enQ a couple of records
98 * Queue_enqueue(q, &r1._elem);
99 * Queue_enqueue(q, &r2._elem);
100 *
101 *
102 * // deQ the records and print their data values until Q is empty
103 * while (!Queue_empty(q)) {
104 * rp = Queue_dequeue(q);
105 * System_printf("rec: %d\n", rp->data);
106 * }
107 *
108 * System_exit(0);
109 * return (0);
110 * }
111 * @p
112 *
113 *
114 *
115 * Unconstrained Functions
116 * All functions are unconstrained
117 *
118 * @p(html)
119 * <h3> Calling Context </h3>
120 * <table border="1" cellpadding="3">
121 * <colgroup span="1"></colgroup> <colgroup span="5" align="center">
122 * </colgroup>
123 *
124 * <tr><th> Function </th><th> Hwi </th><th> Swi </th>
125 * <th> Task </th><th> Main </th><th> Startup </th></tr>
126 * <!-- -->
127 * <tr><td> {@link #create} </td><td> N </td><td> N </td>
128 * <td> Y </td><td> Y </td><td> N </td></tr>
129 * <tr><td> {@link #insert} </td><td> Y </td><td> Y </td>
130 * <td> Y </td><td> Y </td><td> N </td></tr>
131 * <tr><td> {@link #next} </td><td> Y </td><td> Y </td>
132 * <td> Y </td><td> Y </td><td> N </td></tr>
133 * <tr><td> {@link #Params_init} </td><td> Y </td><td> Y </td>
134 * <td> Y </td><td> Y </td><td> N </td></tr>
135 * <tr><td> {@link #prev} </td><td> Y </td><td> Y </td>
136 * <td> Y </td><td> Y </td><td> N </td></tr>
137 * <tr><td> {@link #remove} </td><td> Y </td><td> Y </td>
138 * <td> Y </td><td> Y </td><td> N </td></tr>
139 * <tr><td> {@link #construct} </td><td> Y </td><td> Y </td>
140 * <td> Y </td><td> Y </td><td> N </td></tr>
141 * <tr><td> {@link #delete} </td><td> N </td><td> N </td>
142 * <td> Y </td><td> Y </td><td> N </td></tr>
143 * <tr><td> {@link #dequeue} </td><td> Y </td><td> Y </td>
144 * <td> Y </td><td> Y </td><td> N </td></tr>
145 * <tr><td> {@link #destruct} </td><td> Y </td><td> Y </td>
146 * <td> Y </td><td> Y </td><td> N </td></tr>
147 * <tr><td> {@link #empty} </td><td> Y </td><td> Y </td>
148 * <td> Y </td><td> Y </td><td> N </td></tr>
149 * <tr><td> {@link #enqueue} </td><td> Y </td><td> Y </td>
150 * <td> Y </td><td> Y </td><td> N </td></tr>
151 * <tr><td> {@link #get} </td><td> Y </td><td> Y </td>
152 * <td> Y </td><td> Y </td><td> N </td></tr>
153 * <tr><td> {@link #head} </td><td> Y </td><td> Y </td>
154 * <td> Y </td><td> Y </td><td> N </td></tr>
155 * <tr><td> {@link #put} </td><td> Y </td><td> Y </td>
156 * <td> Y </td><td> Y </td><td> N </td></tr>
157 * <tr><td colspan="6"> Definitions: <br />
158 * <ul>
159 * <li> <b>Hwi</b>: API is callable from a Hwi thread. </li>
160 * <li> <b>Swi</b>: API is callable from a Swi thread. </li>
161 * <li> <b>Task</b>: API is callable from a Task thread. </li>
162 * <li> <b>Main</b>: API is callable during any of these phases: </li>
163 * <ul>
164 * <li> In your module startup after this module is started
165 * (e.g. Queue_Module_startupDone() returns TRUE). </li>
166 * <li> During xdc.runtime.Startup.lastFxns. </li>
167 * <li> During main().</li>
168 * <li> During BIOS.startupFxns.</li>
169 * </ul>
170 * <li> <b>Startup</b>: API is callable during any of these phases:</li>
171 * <ul>
172 * <li> During xdc.runtime.Startup.firstFxns.</li>
173 * <li> In your module startup before this module is started
174 * (e.g. Queue_Module_startupDone() returns FALSE).</li>
175 * </ul>
176 * </ul>
177 * </td></tr>
178 *
179 * </table>
180 * @p
181 */
182
183 @DirectCall
184 @InstanceInitStatic
185 module Queue
186 {
187
188 /*!
189 * ======== BasicView ========
190 * @_nodoc
191 */
192 metaonly struct BasicView {
193 String label;
194 Ptr elems[];
195 }
196
197 /*!
198 * ======== rovViewInfo ========
199 * @_nodoc
200 */
201 @Facet
202 metaonly config ViewInfo.Instance rovViewInfo =
203 ViewInfo.create({
204 viewMap: [
205 ['Basic', {type: ViewInfo.INSTANCE, viewInitFxn: 'viewInitInstance', structName: 'BasicView'}]
206 ]
207 });
208
209 /*!
210 * ======== Elem ========
211 * Opaque queue element.
212 *
213 * A field of this type is placed at the head of client structs.
214 */
215 struct Elem {
216 Elem *volatile next;
217 Elem *volatile prev;
218 };
219
220 /*!
221 * @_nodoc
222 * ======== elemClear ========
223 * Clears a Queue element's pointers so that if isQueued() is called on
224 * the element it will return FALSE. When a Queue element is dequeued or
225 * removed from a Queue, this API must be called on the element for
226 * isQueued() to return FALSE.
227 *
228 * To be clear, this API is not for removing elements from a queue, and
229 * should never be called on an element in a queue--only on dequeued
230 * elements.
231 *
232 * @param(qelem) element to be cleared
233 */
234 Void elemClear(Elem *qelem);
235
236 /*!
237 * ======== elemClearMeta ========
238 * @_nodoc
239 * Clears a Queue element's pointers so that if isQueued() is called on
240 * the element it will return FALSE. When a Queue element is dequeued or
241 * removed from a Queue, this API must be called on the element for
242 * isQueued() to return FALSE.
243 *
244 * To be clear, this API is not for removing elements from a queue, and
245 * should never be called on an element in a queue--only on dequeued
246 * elements.
247 *
248 * @param(qelem) element to be cleared
249 */
250 metaonly Void elemClearMeta(Elem *qelem);
251
252 /*!
253 * ======== insert ========
254 * Insert `elem` in the queue in front of `qelem`.
255 *
256 * @param(qelem) element already in queue
257 *
258 * @param(elem) element to be inserted in queue
259 */
260 Void insert(Elem *qelem, Elem *elem);
261
262 /*!
263 * ======== insertMeta ========
264 * @_nodoc
265 * Insert `elem` in the queue in front of `qelem`.
266 *
267 * @param(qelem) element already in queue
268 *
269 * @param(elem) element to be inserted in queue
270 */
271 metaonly Void insertMeta(Elem *qelem, Elem *elem);
272
273 /*!
274 * ======== next ========
275 * Return next element in queue (non-atomically).
276 *
277 * This function returns a pointer to an Elem object in the queue
278 * after `qelem`. A Queue is represented internally as a doubly-linked
279 * list, so 'next' can be called in a continuous loop over the queue.
280 * See the module description for an example of iterating once over a
281 * Queue.
282 *
283 * @param(qelem) element in queue
284 *
285 * @b(returns) next element in queue
286 */
287 Ptr next(Elem *qelem);
288
289 /*!
290 * ======== prev ========
291 * Return previous element in queue (non-atomically).
292 *
293 * This function returns a pointer to an Elem object in the queue
294 * before `qelem`. A Queue is represented internally as a doubly-linked
295 * list, so 'prev' can be called in a continuous loop over the queue.
296 * See the module description for an example of iterating once over a
297 * Queue.
298 *
299 * @param(qelem) element in queue
300 *
301 * @b(returns) previous element in queue
302 */
303 Ptr prev(Elem *qelem);
304
305 /*!
306 * ======== remove ========
307 * Remove qelem from middle of queue (non-atomically).
308 *
309 * The `qelem` parameter is a pointer to an existing element to be removed
310 * from the Queue.
311 *
312 * @param(qelem) element in queue
313 */
314 Void remove (Elem *qelem);
315
316 /*!
317 * @_nodoc
318 * ======== isQueued ========
319 * Check if the elem is on any queue.
320 *
321 * In order for this API to return false on an element that has been
322 * dequeued or removed from a Queue, elemClear must have been called on
323 * the element.
324 *
325 * @param(qelem) element in queue
326 */
327 Bool isQueued (Elem *qelem);
328
329 instance:
330
331 /*!
332 * @_nodoc
333 * Added to get the Grace instance view to work.
334 */
335 metaonly config UInt dummy = 0;
336
337 /*!
338 * ======== create ========
339 * Create a Queue object
340 */
341 create();
342
343 /*!
344 * ======== dequeue ========
345 * Remove the element from the front of queue and return elem
346 * (non-atomically).
347 *
348 * This function removes an element from the front of a queue and returns
349 * it.
350 *
351 * If called with an empty queue, this function will return a pointer to
352 * the queue itself.
353 *
354 * @a(note) As this function is non-atomic, the method for detecting an
355 * empty Queue as shown in {@link #get Queue_get()} isn't reliable in
356 * a multi-threaded system. Thread safety can be achieved as shown below:
357 *
358 * @p(code)
359 * key = Hwi_disable();
360 *
361 * if ((Queue_Handle)(elem = Queue_dequeue(q)) != q) {
362 * ` process elem `
363 * }
364 *
365 * Hwi_restore(key);
366 * @p
367 *
368 * @b(returns) pointer to former first element
369 */
370 Ptr dequeue();
371
372 /*!
373 * ======== empty ========
374 * Test for an empty queue.
375 *
376 * @b(returns) TRUE if this queue is empty
377 */
378 Bool empty();
379
380 /*!
381 * ======== enqueue ========
382 * Insert at end of queue (non-atomically).
383 *
384 * @param(elem) pointer to an element
385 */
386 Void enqueue(Elem *elem);
387
388 /*!
389 * ======== get ========
390 * Get element from front of queue (atomically).
391 *
392 * This function removes an element from the front of a queue and returns
393 * it.
394 *
395 * If called with an empty queue, this function will return a pointer to
396 * the queue itself.
397 * This provides a means for using a single atomic action to check if a
398 * queue is empty, and to remove and return the first element if it is
399 * not empty:
400 *
401 * @p(code)
402 * if ((Queue_Handle)(elem = Queue_get(q)) != q) {
403 * ` process elem `
404 * }
405 * @p
406 *
407 * @b(returns) pointer to former first element
408 */
409 Ptr get();
410
411 /*!
412 * ======== getTail ========
413 * Get the element at the end of the queue (atomically).
414 *
415 * This function removes the element at the end of a queue and returns
416 * a pointer to it.
417 * If called with an empty queue, this function will return a pointer to
418 * the queue itself.
419 * This provides a means for using a single atomic action to check if a
420 * queue is empty, and to remove and return the last element if it is
421 * not empty:
422 *
423 * @p(code)
424 * if ((Queue_Handle)(elem = Queue_getTail(q)) != q) {
425 * `process elem`
426 * }
427 * @p
428 *
429 * @b(returns) pointer to former end element
430 */
431 Ptr getTail();
432
433 /*!
434 * ======== head ========
435 * Return element at front of queue. (atomically)
436 *
437 * This function returns a pointer to the element at the front of a queue.
438 * The element is not removed from the queue.
439 * If called with an empty queue, this function will return a pointer to
440 * the queue itself.
441 * This provides a means for using a single atomic action to check if a queue
442 * is empty, and to return a pointer to the first element if it is not empty:
443 *
444 * @p(code)
445 * if ((Queue_Handle)(elem = Queue_head(q)) != q) {
446 * `process elem`
447 * @p
448 *
449 * @b(returns) pointer to first element
450 */
451 Ptr head();
452
453 /*!
454 * ======== headMeta ========
455 * @_nodoc
456 * Return element at front of queue. Returns null if queue is empty.
457 *
458 * This function returns a pointer to the element at the front of queue.
459 * The element is not removed from the queue.
460 *
461 * @b(returns) pointer to first element
462 */
463 metaonly Ptr headMeta();
464
465 /*!
466 * ======== put ========
467 * Put element at end of queue (atomically).
468 *
469 * @param(elem) pointer to new queue element
470 */
471 Void put(Elem *elem);
472
473 /*!
474 * ======== putMeta ========
475 * @_nodoc
476 * Put element at end of queue.
477 *
478 * @param(elem) pointer to new queue element
479 */
480 metaonly Void putMeta(Elem* elem);
481
482 /*!
483 * ======== putHead ========
484 * Put element at the front of the queue (atomically).
485 *
486 * @param(elem) pointer to new queue element
487 */
488 Void putHead(Elem *elem);
489
490 /*!
491 * ======== nextMeta ========
492 * @_nodoc
493 * Return next element in queue. Returns null if end of queue.
494 *
495 * This function returns a pointer to an Elem object in the queue
496 * after `qelem`.
497 *
498 * @param(qelem) element in queue
499 *
500 * @b(returns) next element in queue
501 */
502 metaonly Ptr nextMeta(Elem *qelem);
503
504 internal:
505
506
507 struct Instance_State {
508 Elem elem;
509 };
510 }