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