1 /* --COPYRIGHT--,BSD
2 * Copyright (c) $(CPYYEAR), Texas Instruments Incorporated
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * * Neither the name of Texas Instruments Incorporated nor the names of
17 * its contributors may be used to endorse or promote products derived
18 * from this software without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
22 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
27 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
28 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
29 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
30 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 * --/COPYRIGHT--*/
32 /*
33 * ======== List.xdc ========
34 *
35 *! Revision History
36 *! ================
37 *! 07-Aug-2009 toddm Added enqueue and dequeue
38 *! 16-Apr-2009 toddm Code review comments
39 *! 02-May-2008 nitya created
40 */
41
42 import xdc.rov.ViewInfo;
43
44 /*!
45 * ======== List ========
46 * Doubly Linked List Manager
47 *
48 * The List module makes available a set of functions that manipulate
49 * List objects accessed through handles of type List_Handle.
50 * Each List contains a linked sequence of zero or more elements
51 * referenced through variables of type List_Elem, which are typically
52 * embedded as the first field within a structure.
53 *
54 * All List function are atomic unless noted otherwise in the API
55 * descriptions. An atomic API means that the API completes in core
56 * functionality without being interrupted. Therefore, atomic APIs are
57 * thread-safe. An example is {@link #put}. Multiple threads can call
58 * {@link #put} at the same time. The threads do not have to manage the
59 * synchronization.
60 *
61 * The {@link xdc.runtime.Gate#enterSystem}/{@link xdc.runtime.Gate#leaveSystem}
62 * calls are used to make the APIs atomic. This Gate calls internally use
63 * {@link xdc.runtime.System}'s gate.
64 *
65 * The List module can be used both as a queue (i.e. First In First Out),
66 * as a stack (i.e. Last In First Out), or as a general purpose linked list.
67 *
68 * Lists are represented as doubly-linked lists, so calls to {@link #next}
69 * or {@link #prev} can loop continuously over the List.
70 * Refer to {@link #next} and {@link #prev} for examples.
71 *
72 * @a(List as a Queue) 73 *
74 * To treat the list object as a queue:
75 * @p(blist) 76 * -Use {@link #put} to put at the tail of the queue
77 * -Use {@link #get} to get from the head of the queue
78 * @p 79 *
80 * Here is sample code that acts on a List instance (listHandle) as a queue
81 * in a FIFO manner.
82 *
83 * @p(code) 84 * List_Elem elem[4];
85 * List_Elem *tmpElem;
86 *
87 * // place at the tail of the queue
88 * for (i = 0; i < 4; i++) {
89 * List_put(listHandle, &(elem[i]));
90 * }
91 *
92 * // remove the buffers from the head
93 * while((tmpElem = List_get(listHandle)) != NULL) {
94 * // process tmpElem
95 * }
96 * @p 97 *
98 * @a(List as a Stack) 99 *
100 * To treat the list object as a stack:
101 * @p(blist) 102 * -Use {@link #putHead} to put at the top of the stack
103 * -Use {@link #get} to get from the top of the stack
104 * @p 105 *
106 * Here is sample code that acts on a List instance (listHandle) as a stack
107 * in a LIFO manner.
108 *
109 * @p(code) 110 * List_Elem elem[4];
111 * List_Elem *tmpElem;
112 *
113 * // push onto the top (i.e. head)
114 * for (i = 0; i < 4; i++) {
115 * List_putHead(listHandle, &(elem[i]));
116 * }
117 *
118 * // remove the buffers in FIFO order.
119 * while((tmpElem = List_get(listHandle)) != NULL) {
120 * // process tmpElem
121 * }
122 * @p 123 */
124
125 module List
126 {
127 metaonlystruct BasicView {
128 String label;
129 Ptr elems[];
130 }
131
132 @Facet
133 metaonlyconfig ViewInfo.Instance rovViewInfo =
134 ViewInfo.create({
135 viewMap: [
136 ['Basic', {type: ViewInfo.INSTANCE, viewInitFxn: 'viewInitInstance', structName: 'BasicView'}]
137 ]
138 });
139
140 /*!
141 * ======== Elem ========
142 * Opaque List element
143 *
144 * A field of this type is placed at the head of client structs.
145 */
146 @Opaque struct Elem {
147 Elem *volatile next; /* must be volatile for whole_program */
148 Elem *volatile prev; /* must be volatile for whole_program */
149 };
150
151 /*!
152 * ======== elemClearMeta ========
153 * Clears a List element's pointers
154 *
155 * This API is not for removing elements from a List, and
156 * should never be called on an element in a List--only on deListed
157 * elements.
158 *
159 * @param(elem) element to be cleared
160 */
161 metaonly Void elemClearMeta(Elem *elem);
162
163 /*!
164 * ======== elemClear ========
165 * Clears a List element's pointers
166 *
167 * This API does not removing elements from a List, and
168 * should never be called on an element in a List--only on deListed
169 * elements.
170 *
171 * @param(elem) element to be cleared
172 */
173 @DirectCall
174 Void elemClear(Elem *elem);
175
176 instance:
177
178 /*!
179 * ======== metaList ========
180 * @_nodoc 181 * Used to store elem before the object is initialized.
182 */
183 metaonlyconfig any metaList[];
184
185 /*!
186 * ======== create ========
187 * Create a List object
188 */
189 create();
190
191 /*!
192 * ======== empty ========
193 * Test for an empty List (atomic)
194 *
195 * @b(returns) TRUE if this List is empty
196 */
197 @DirectCall
198 Bool empty();
199
200 /*!
201 * ======== get ========
202 * Get element from front of List (atomic)
203 *
204 * This function atomically removes the element from the front of a
205 * List and returns a pointer to it.
206 *
207 * @b(returns) pointer to former first element or NULL if empty
208 */
209 @DirectCall
210 Ptr get();
211
212 /*!
213 * ======== put ========
214 * Put element at end of List (atomic)
215 *
216 * This function atomically places the element at the end of
217 * List.
218 *
219 * @param(elem) pointer to new List element
220 */
221 @DirectCall
222 Void put(Elem *elem);
223
224 /*!
225 * ======== putHead ========
226 * Put element at head of List (atomic)
227 *
228 * This function atomically places the element at the front of
229 * List.
230 *
231 * @param(elem) pointer to new List element
232 */
233 @DirectCall
234 Void putHead(Elem *elem);
235
236 /*!
237 * ======== putMeta ========
238 * @_nodoc 239 * Put element at end of List.
240 *
241 * This meta function can be used to place an element onto
242 * the end of a list during configuration. There currently
243 * is no meta API to place the elem at the head of the list
244 * during configuration.
245 *
246 * @param(elem) pointer to new List element
247 */
248 metaonly Void putMeta(Elem* elem);
249
250 /*!
251 * ======== next ========
252 * Return next element in List (non-atomic)
253 *
254 * This function returns the next element on a list. It does not
255 * remove any items from the list. The caller should protect the
256 * list from being changed while using this call since it is non-atomic.
257 *
258 * To look at the first elem on the list, use NULL as the elem argument.
259 *
260 * This function is useful in searching a list. The following code shows
261 * an example. The scanning of a list should be protected against other
262 * threads that modify the list.
263 *
264 * @p(code) 265 * List_Elem *elem = NULL;
266 *
267 * // Begin protection against modification of the list.
268 *
269 * while ((elem = List_next(listHandle, elem)) != NULL) {
270 * //act elem as needed. For example call List_remove().
271 * }
272 *
273 * // End protection against modification of the list.
274 * @p 275 *
276 * @param(elem) element in list or NULL to start at the head
277 *
278 * @b(returns) next element in list or NULL to denote end
279 */
280 @DirectCall
281 Ptr next(Elem *elem);
282
283 /*!
284 * ======== prev ========
285 * Return previous element in List (non-atomic)
286 *
287 * This function returns the previous element on a list. It does not
288 * remove any items from the list. The caller should protect the
289 * list from being changed while using this call since it is non-atomic.
290 *
291 * To look at the last elem on the list, use NULL as the elem argument.
292 *
293 * This function is useful in searching a list in reverse order. The
294 * following code shows an example. The scanning of a list should be
295 * protected against other threads that modify the list.
296 *
297 * @p(code) 298 * List_Elem *elem = NULL;
299 *
300 * // Begin protection against modification of the list.
301 *
302 * while ((elem = List_prev(listHandle, elem)) != NULL) {
303 * //act elem as needed. For example call List_remove().
304 * }
305 *
306 * // End protection against modification of the list.
307 * @p 308 *
309 * @param(elem) element in list or NULL to start at the end (i.e. tail)
310 *
311 * @b(returns) previous element in list or NULL to denote
312 * no previous elem
313 */
314 @DirectCall
315 Ptr prev(Elem *elem);
316
317 /*!
318 * ======== insert ========
319 * Insert element at into a List (non-atomic)
320 *
321 * This function inserts `newElem` in the queue in
322 * front of `curElem`. The caller should protect the
323 * list from being changed while using this call since it is non-atomic.
324 *
325 * To place an elem at the end of the list, use {@link #put}.
326 * To place a elem at the front of the list, use {@link #putHead}.
327 *
328 * @param(newElem) element to insert
329 *
330 * @param(curElem) element to insert in front of
331 */
332 @DirectCall
333 Void insert(Elem *newElem, Elem *curElem);
334
335 /*!
336 * ======== remove ========
337 * Remove elem from middle of list (non-atomic)
338 *
339 * This function removes an elem from a list.
340 * The `elem` parameter is a pointer to an existing element to be removed
341 * from the List. The caller should protect the
342 * list from being changed while using this call since it is non-atomic.
343 *
344 * @param(elem) element in list
345 */
346 @DirectCall
347 Void remove(Elem *elem);
348
349 /*!
350 * ======== dequeue ========
351 * Get element from front of List (non-atomic)
352 *
353 * This function atomically removes the element from the front of a
354 * List and returns a pointer to it. This API is not thread safe.
355 * Use {@link #put} and {@link #get} if multiple calling contexts
356 * share the same list.
357 *
358 * @b(returns) pointer to former first element or NULL if empty
359 */
360 @DirectCall
361 Ptr dequeue();
362
363 /*!
364 * ======== enqueue ========
365 * Put element at end of List (non-atomic)
366 *
367 * This function places the element at the end of a List.
368 * This API is not thread safe. Use {@link #put} and {@link #get}
369 * if multiple calling contexts share the same list.
370 *
371 * @param(elem) pointer to new List element
372 */
373 @DirectCall
374 Void enqueue(Elem *elem);
375
376 /*!
377 * ======== enqueueHead ========
378 * Put element at head of List (non-atomic)
379 *
380 * This function places the element at the front of the List.
381 * This API is not thread safe. Use {@link #putHead}
382 * if multiple calling contexts share the same list.
383 *
384 * @param(elem) pointer to new List element
385 */
386 @DirectCall
387 Void enqueueHead(Elem *elem);
388
389 internal:
390
391 /* instance object */
392 struct Instance_State {
393 Elem elem;
394 };
395 }