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 37 38 39 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 metaonly struct BasicView {
128 String label;
129 Ptr elems[];
130 }
131
132 @Facet
133 metaonly config 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;
148 Elem *volatile prev;
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 metaonly config 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.
355 *
356 * @b(returns) pointer to former first element or NULL if empty
357 */
358 @DirectCall
359 Ptr dequeue();
360
361 /*!
362 * ======== enqueue ========
363 * Put element at end of List (non-atomic)
364 *
365 * This function atomically places the element at the end of
366 * List.
367 *
368 * @param(elem) pointer to new List element
369 */
370 @DirectCall
371 Void enqueue(Elem *elem);
372
373 /*!
374 * ======== enqueueHead ========
375 * Put element at head of List (non-atomic)
376 *
377 * This function atomically places the element at the front of
378 * List.
379 *
380 * @param(elem) pointer to new List element
381 */
382 @DirectCall
383 Void enqueueHead(Elem *elem);
384
385 internal:
386
387
388 struct Instance_State {
389 Elem elem;
390 };
391 }