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 Void elemClear(Elem *elem);
174
175 instance:
176
177 /*!
178 * ======== metaList ========
179 * @_nodoc 180 * Used to store elem before the object is initialized.
181 */
182 metaonlyconfig any metaList[];
183
184 /*!
185 * ======== create ========
186 * Create a List object
187 */
188 create();
189
190 /*!
191 * ======== empty ========
192 * Test for an empty List (atomic)
193 *
194 * @b(returns) TRUE if this List is empty
195 */
196 Bool empty();
197
198 /*!
199 * ======== get ========
200 * Get element from front of List (atomic)
201 *
202 * This function atomically removes the element from the front of a
203 * List and returns a pointer to it.
204 *
205 * @b(returns) pointer to former first element or NULL if empty
206 */
207 Ptr get();
208
209 /*!
210 * ======== put ========
211 * Put element at end of List (atomic)
212 *
213 * This function atomically places the element at the end of
214 * List.
215 *
216 * @param(elem) pointer to new List element
217 */
218 Void put(Elem *elem);
219
220 /*!
221 * ======== putHead ========
222 * Put element at head of List (atomic)
223 *
224 * This function atomically places the element at the front of
225 * List.
226 *
227 * @param(elem) pointer to new List element
228 */
229 Void putHead(Elem *elem);
230
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);
244
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 Ptr next(Elem *elem);
276
277 /*!
278 * ======== prev ========
279 * Return previous element in List (non-atomic)
280 *
281 * This function returns the previous element on a list. It does not
282 * remove any items from the list. The caller should protect the
283 * list from being changed while using this call since it is non-atomic.
284 *
285 * To look at the last elem on the list, use NULL as the elem argument.
286 *
287 * This function is useful in searching a list in reverse order. The
288 * following code shows an example. The scanning of a list should be
289 * protected against other threads that modify the list.
290 *
291 * @p(code) 292 * List_Elem *elem = NULL;
293 *
294 * // Begin protection against modification of the list.
295 *
296 * while ((elem = List_prev(listHandle, elem)) != NULL) {
297 * //act elem as needed. For example call List_remove().
298 * }
299 *
300 * // End protection against modification of the list.
301 * @p 302 *
303 * @param(elem) element in list or NULL to start at the end (i.e. tail)
304 *
305 * @b(returns) previous element in list or NULL to denote
306 * no previous elem
307 */
308 Ptr prev(Elem *elem);
309
310 /*!
311 * ======== insert ========
312 * Insert element at into a List (non-atomic)
313 *
314 * This function inserts `newElem` in the queue in
315 * front of `curElem`. The caller should protect the
316 * list from being changed while using this call since it is non-atomic.
317 *
318 * To place an elem at the end of the list, use {@link #put}.
319 * To place a elem at the front of the list, use {@link #putHead}.
320 *
321 * @param(newElem) element to insert
322 *
323 * @param(curElem) element to insert in front of
324 */
325 Void insert(Elem *newElem, Elem *curElem);
326
327 /*!
328 * ======== remove ========
329 * Remove elem from middle of list (non-atomic)
330 *
331 * This function removes an elem from a list.
332 * The `elem` parameter is a pointer to an existing element to be removed
333 * from the List. The caller should protect the
334 * list from being changed while using this call since it is non-atomic.
335 *
336 * @param(elem) element in list
337 */
338 Void remove(Elem *elem);
339
340 /*!
341 * ======== dequeue ========
342 * Get element from front of List (non-atomic)
343 *
344 * This function atomically removes the element from the front of a
345 * List and returns a pointer to it.
346 *
347 * @b(returns) pointer to former first element or NULL if empty
348 */
349 Ptr dequeue();
350
351 /*!
352 * ======== enqueue ========
353 * Put element at end of List (non-atomic)
354 *
355 * This function atomically places the element at the end of
356 * List.
357 *
358 * @param(elem) pointer to new List element
359 */
360 Void enqueue(Elem *elem);
361
362 /*!
363 * ======== enqueueHead ========
364 * Put element at head of List (non-atomic)
365 *
366 * This function atomically places the element at the front of
367 * List.
368 *
369 * @param(elem) pointer to new List element
370 */
371 Void enqueueHead(Elem *elem);
372
373 internal:
374
375 /* instance object */
376 struct Instance_State {
377 Elem elem;
378 };
379 }