1 /*
2 * Copyright (c) 2012-2013, 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 */
32 /*
33 * ======== List.xdc ========
34 *
35 */
37 import xdc.rov.ViewInfo;
39 /*!
40 * ======== List ========
41 * Doubly Linked List Manager
42 *
43 * The List module makes available a set of functions that manipulate
44 * List objects accessed through handles of type List_Handle.
45 * Each List contains a linked sequence of zero or more elements
46 * referenced through variables of type List_Elem, which are typically
47 * embedded as the first field within a structure.
48 *
49 * All List function are atomic unless noted otherwise in the API
50 * descriptions. An atomic API means that the API completes in core
51 * functionality without being interrupted. Therefore, atomic APIs are
52 * thread-safe. An example is {@link #put}. Multiple threads can call
53 * {@link #put} at the same time. The threads do not have to manage the
54 * synchronization.
55 *
56 * The {@link xdc.runtime.Gate#enterSystem}/{@link xdc.runtime.Gate#leaveSystem}
57 * calls are used to make the APIs atomic. This Gate calls internally use
58 * {@link xdc.runtime.System}'s gate.
59 *
60 * The List module can be used both as a queue (i.e. First In First Out),
61 * as a stack (i.e. Last In First Out), or as a general purpose linked list.
62 *
63 * Lists are represented as doubly-linked lists, so calls to {@link #next}
64 * or {@link #prev} can loop continuously over the List.
65 * Refer to {@link #next} and {@link #prev} for examples.
66 *
67 * @a(List as a Queue)
68 *
69 * To treat the list object as a queue:
70 * @p(blist)
71 * -Use {@link #put} to put at the tail of the queue
72 * -Use {@link #get} to get from the head of the queue
73 * @p
74 *
75 * Here is sample code that acts on a List instance (listHandle) as a queue
76 * in a FIFO manner.
77 *
78 * @p(code)
79 * List_Elem elem[4];
80 * List_Elem *tmpElem;
81 *
82 * // place at the tail of the queue
83 * for (i = 0; i < 4; i++) {
84 * List_put(listHandle, &(elem[i]));
85 * }
86 *
87 * // remove the buffers from the head
88 * while((tmpElem = List_get(listHandle)) != NULL) {
89 * // process tmpElem
90 * }
91 * @p
92 *
93 * @a(List as a Stack)
94 *
95 * To treat the list object as a stack:
96 * @p(blist)
97 * -Use {@link #putHead} to put at the top of the stack
98 * -Use {@link #get} to get from the top of the stack
99 * @p
100 *
101 * Here is sample code that acts on a List instance (listHandle) as a stack
102 * in a LIFO manner.
103 *
104 * @p(code)
105 * List_Elem elem[4];
106 * List_Elem *tmpElem;
107 *
108 * // push onto the top (i.e. head)
109 * for (i = 0; i < 4; i++) {
110 * List_putHead(listHandle, &(elem[i]));
111 * }
112 *
113 * // remove the buffers in FIFO order.
114 * while((tmpElem = List_get(listHandle)) != NULL) {
115 * // process tmpElem
116 * }
117 * @p
118 */
120 module List
121 {
122 metaonly struct BasicView {
123 String label;
124 Ptr elems[];
125 }
127 @Facet
128 metaonly config ViewInfo.Instance rovViewInfo =
129 ViewInfo.create({
130 viewMap: [
131 ['Basic', {type: ViewInfo.INSTANCE, viewInitFxn: 'viewInitInstance', structName: 'BasicView'}]
132 ]
133 });
135 /*!
136 * ======== Elem ========
137 * Opaque List element
138 *
139 * A field of this type is placed at the head of client structs.
140 */
141 @Opaque struct Elem {
142 Elem *volatile next; /* must be volatile for whole_program */
143 Elem *volatile prev; /* must be volatile for whole_program */
144 };
146 /*!
147 * ======== elemClearMeta ========
148 * Clears a List element's pointers
149 *
150 * This API is not for removing elements from a List, and
151 * should never be called on an element in a List--only on deListed
152 * elements.
153 *
154 * @param(elem) element to be cleared
155 */
156 metaonly Void elemClearMeta(Elem *elem);
158 /*!
159 * ======== elemClear ========
160 * Clears a List element's pointers
161 *
162 * This API does not removing elements from a List, and
163 * should never be called on an element in a List--only on deListed
164 * elements.
165 *
166 * @param(elem) element to be cleared
167 */
168 @DirectCall
169 Void elemClear(Elem *elem);
171 instance:
173 /*!
174 * ======== metaList ========
175 * @_nodoc
176 * Used to store elem before the object is initialized.
177 */
178 metaonly config any metaList[];
180 /*!
181 * ======== create ========
182 * Create a List object
183 */
184 create();
186 /*!
187 * ======== empty ========
188 * Test for an empty List (atomic)
189 *
190 * @b(returns) TRUE if this List is empty
191 */
192 @DirectCall
193 Bool empty();
195 /*!
196 * ======== get ========
197 * Get element from front of List (atomic)
198 *
199 * This function atomically removes the element from the front of a
200 * List and returns a pointer to it.
201 *
202 * @b(returns) pointer to former first element or NULL if empty
203 */
204 @DirectCall
205 Ptr get();
207 /*!
208 * ======== put ========
209 * Put element at end of List (atomic)
210 *
211 * This function atomically places the element at the end of
212 * List.
213 *
214 * @param(elem) pointer to new List element
215 */
216 @DirectCall
217 Void put(Elem *elem);
219 /*!
220 * ======== putHead ========
221 * Put element at head of List (atomic)
222 *
223 * This function atomically places the element at the front of
224 * List.
225 *
226 * @param(elem) pointer to new List element
227 */
228 @DirectCall
229 Void putHead(Elem *elem);
231 /*!
232 * ======== putMeta ========
233 * @_nodoc
234 * Put element at end of List.
235 *
236 * This meta function can be used to place an element onto
237 * the end of a list during configuration. There currently
238 * is no meta API to place the elem at the head of the list
239 * during configuration.
240 *
241 * @param(elem) pointer to new List element
242 */
243 metaonly Void putMeta(Elem* elem);
245 /*!
246 * ======== next ========
247 * Return next element in List (non-atomic)
248 *
249 * This function returns the next element on a list. It does not
250 * remove any items from the list. The caller should protect the
251 * list from being changed while using this call since it is non-atomic.
252 *
253 * To look at the first elem on the list, use NULL as the elem argument.
254 *
255 * This function is useful in searching a list. The following code shows
256 * an example. The scanning of a list should be protected against other
257 * threads that modify the list.
258 *
259 * @p(code)
260 * List_Elem *elem = NULL;
261 *
262 * // Begin protection against modification of the list.
263 *
264 * while ((elem = List_next(listHandle, elem)) != NULL) {
265 * //act elem as needed. For example call List_remove().
266 * }
267 *
268 * // End protection against modification of the list.
269 * @p
270 *
271 * @param(elem) element in list or NULL to start at the head
272 *
273 * @b(returns) next element in list or NULL to denote end
274 */
275 @DirectCall
276 Ptr next(Elem *elem);
278 /*!
279 * ======== prev ========
280 * Return previous element in List (non-atomic)
281 *
282 * This function returns the previous element on a list. It does not
283 * remove any items from the list. The caller should protect the
284 * list from being changed while using this call since it is non-atomic.
285 *
286 * To look at the last elem on the list, use NULL as the elem argument.
287 *
288 * This function is useful in searching a list in reverse order. The
289 * following code shows an example. The scanning of a list should be
290 * protected against other threads that modify the list.
291 *
292 * @p(code)
293 * List_Elem *elem = NULL;
294 *
295 * // Begin protection against modification of the list.
296 *
297 * while ((elem = List_prev(listHandle, elem)) != NULL) {
298 * //act elem as needed. For example call List_remove().
299 * }
300 *
301 * // End protection against modification of the list.
302 * @p
303 *
304 * @param(elem) element in list or NULL to start at the end (i.e. tail)
305 *
306 * @b(returns) previous element in list or NULL to denote
307 * no previous elem
308 */
309 @DirectCall
310 Ptr prev(Elem *elem);
312 /*!
313 * ======== insert ========
314 * Insert element at into a List (non-atomic)
315 *
316 * This function inserts `newElem` in the queue in
317 * front of `curElem`. The caller should protect the
318 * list from being changed while using this call since it is non-atomic.
319 *
320 * To place an elem at the end of the list, use {@link #put}.
321 * To place a elem at the front of the list, use {@link #putHead}.
322 *
323 * @param(newElem) element to insert
324 *
325 * @param(curElem) element to insert in front of
326 */
327 @DirectCall
328 Void insert(Elem *newElem, Elem *curElem);
330 /*!
331 * ======== remove ========
332 * Remove elem from middle of list (non-atomic)
333 *
334 * This function removes an elem from a list.
335 * The `elem` parameter is a pointer to an existing element to be removed
336 * from the List. The caller should protect the
337 * list from being changed while using this call since it is non-atomic.
338 *
339 * @param(elem) element in list
340 */
341 @DirectCall
342 Void remove(Elem *elem);
344 /*!
345 * ======== dequeue ========
346 * Get element from front of List (non-atomic)
347 *
348 * This function atomically removes the element from the front of a
349 * List and returns a pointer to it. This API is not thread safe.
350 * Use {@link #put} and {@link #get} if multiple calling contexts
351 * share the same list.
352 *
353 * @b(returns) pointer to former first element or NULL if empty
354 */
355 @DirectCall
356 Ptr dequeue();
358 /*!
359 * ======== enqueue ========
360 * Put element at end of List (non-atomic)
361 *
362 * This function places the element at the end of a List.
363 * This API is not thread safe. Use {@link #put} and {@link #get}
364 * if multiple calling contexts share the same list.
365 *
366 * @param(elem) pointer to new List element
367 */
368 @DirectCall
369 Void enqueue(Elem *elem);
371 /*!
372 * ======== enqueueHead ========
373 * Put element at head of List (non-atomic)
374 *
375 * This function places the element at the front of the List.
376 * This API is not thread safe. Use {@link #putHead}
377 * if multiple calling contexts share the same list.
378 *
379 * @param(elem) pointer to new List element
380 */
381 @DirectCall
382 Void enqueueHead(Elem *elem);
384 internal:
386 /* instance object */
387 struct Instance_State {
388 Elem elem;
389 };
390 }