1 /*-
2 * Copyright (c) 2017 Broadcom. All rights reserved.
3 * The term "Broadcom" refers to Broadcom Limited and/or its subsidiaries.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright notice,
9 * this list of conditions and the following disclaimer.
10 *
11 * 2. Redistributions in binary form must reproduce the above copyright notice,
12 * this list of conditions and the following disclaimer in the documentation
13 * and/or other materials provided with the distribution.
14 *
15 * 3. Neither the name of the copyright holder nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /**
33 * @file
34 *
35 * OCS linked list API
36 *
37 */
38
39 #if !defined(__OCS_LIST_H__)
40 #define __OCS_LIST_H__
41
42 #define OCS_LIST_DEBUG
43
44 #if defined(OCS_LIST_DEBUG)
45
46 #define ocs_list_magic_decl uint32_t magic;
47 #define OCS_LIST_LIST_MAGIC 0xcafe0000
48 #define OCS_LIST_LINK_MAGIC 0xcafe0001
49 #define ocs_list_set_list_magic list->magic = OCS_LIST_LIST_MAGIC
50 #define ocs_list_set_link_magic list->magic = OCS_LIST_LINK_MAGIC
51
52 #define ocs_list_assert(cond, ...) \
53 if (!(cond)) { \
54 return __VA_ARGS__; \
55 }
56 #else
57 #define ocs_list_magic_decl
58 #define ocs_list_assert(cond, ...)
59 #define ocs_list_set_list_magic
60 #define ocs_list_set_link_magic
61 #endif
62
63 /**
64 * @brief list/link structure
65 *
66 * used for both the list object, and the link object(s). offset
67 * is specified when the list is initialized; this implies that a list
68 * will always point to objects of the same type. offset is not used
69 * when ocs_list_t is used as a link (ocs_list_link_t).
70 *
71 */
72
73 typedef struct ocs_list_s ocs_list_t;
74 struct ocs_list_s {
75 ocs_list_magic_decl /*<< used if debugging is enabled */
76 ocs_list_t *next; /*<< pointer to head of list (or next if link) */
77 ocs_list_t *prev; /*<< pointer to tail of list (or previous if link) */
78 uint32_t offset; /*<< offset in bytes to the link element of the objects in list */
79 };
80 typedef ocs_list_t ocs_list_link_t;
81
82 /* item2link - return pointer to link given pointer to an item */
83 #define item2link(list, item) ((ocs_list_t*) (((uint8_t*)(item)) + (list)->offset))
84
85 /* link2item - return pointer to item given pointer to a link */
86 #define link2item(list, link) ((void*) (((uint8_t*)(link)) - (list)->offset))
87
88 /**
89 * @brief Initialize a list
90 *
91 * A list object is initialized. Helper define is used to call _ocs_list_init() with
92 * offsetof(type, link)
93 *
94 * @param list Pointer to list
95 * @param offset Offset in bytes in item to the link element
96 *
97 * @return none
98 */
99 static inline void
_ocs_list_init(ocs_list_t * list,uint32_t offset)100 _ocs_list_init(ocs_list_t *list, uint32_t offset)
101 {
102 ocs_list_assert(list);
103 ocs_list_set_list_magic;
104
105 list->next = list;
106 list->prev = list;
107 list->offset = offset;
108 }
109 #define ocs_list_init(head, type, link) _ocs_list_init(head, offsetof(type, link))
110
111 /**
112 * @ingroup os
113 * @brief Test if a list is empty
114 *
115 * @param list Pointer to list head
116 *
117 * @return 1 if empty, 0 otherwise
118 */
119 static inline int32_t
ocs_list_empty(ocs_list_t * list)120 ocs_list_empty(ocs_list_t *list)
121 {
122 ocs_list_assert(list, 1);
123 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, 1);
124 return list->next == list;
125 }
126
127 /**
128 * @ingroup os
129 * @brief Test if a list is valid (ready for use)
130 *
131 * @param list Pointer to list head
132 *
133 * @return true if list is usable, false otherwise
134 */
135 static inline int
ocs_list_valid(ocs_list_t * list)136 ocs_list_valid(ocs_list_t *list)
137 {
138 return (list->magic == OCS_LIST_LIST_MAGIC);
139 }
140
141 /**
142 * @brief Insert link between two other links
143 *
144 * Inserts a link in between two other links
145 *
146 * @param a Pointer to first link
147 * @param b Pointer to next link
148 * @param c Pointer to link to insert between a and b
149 *
150 * @return none
151 */
152 static inline void
_ocs_list_insert_link(ocs_list_t * a,ocs_list_t * b,ocs_list_t * c)153 _ocs_list_insert_link(ocs_list_t *a, ocs_list_t *b, ocs_list_t *c)
154 {
155 ocs_list_assert(a);
156 ocs_list_assert((a->magic == OCS_LIST_LIST_MAGIC) || (a->magic == OCS_LIST_LINK_MAGIC));
157 ocs_list_assert(a->next);
158 ocs_list_assert(a->prev);
159 ocs_list_assert(b);
160 ocs_list_assert((b->magic == OCS_LIST_LIST_MAGIC) || (b->magic == OCS_LIST_LINK_MAGIC));
161 ocs_list_assert(b->next);
162 ocs_list_assert(b->prev);
163 ocs_list_assert(c);
164 ocs_list_assert((c->magic == OCS_LIST_LIST_MAGIC) || (c->magic == OCS_LIST_LINK_MAGIC));
165 ocs_list_assert(!c->next);
166 ocs_list_assert(!c->prev);
167
168 ocs_list_assert(a->offset == b->offset);
169 ocs_list_assert(b->offset == c->offset);
170
171 c->next = a->next;
172 c->prev = b->prev;
173 a->next = c;
174 b->prev = c;
175 }
176
177 #if defined(OCS_LIST_DEBUG)
178 /**
179 * @brief Initialize a list link for debug purposes
180 *
181 * For debugging a linked list link element has a magic number that is initialized,
182 * and the offset value initialized and used for subsequent assertions.
183 *
184 *
185 * @param list Pointer to list head
186 * @param link Pointer to link to be initialized
187 *
188 * @return none
189 */
190 static inline void
ocs_list_init_link(ocs_list_t * list,ocs_list_t * link)191 ocs_list_init_link(ocs_list_t *list, ocs_list_t *link)
192 {
193 ocs_list_assert(list);
194 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC);
195 ocs_list_assert(link);
196
197 if (link->magic == 0) {
198 link->magic = OCS_LIST_LINK_MAGIC;
199 link->offset = list->offset;
200 link->next = NULL;
201 link->prev = NULL;
202 }
203 }
204 #else
205 #define ocs_list_init_link(...)
206 #endif
207
208 /**
209 * @ingroup os
210 * @brief Add an item to the head of the list
211 *
212 * @param list Pointer to list head
213 * @param item Item to add
214 */
215 static inline void
ocs_list_add_head(ocs_list_t * list,void * item)216 ocs_list_add_head(ocs_list_t *list, void *item)
217 {
218 ocs_list_t *link;
219
220 ocs_list_assert(list);
221 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC);
222 ocs_list_assert(item);
223
224 link = item2link(list, item);
225 ocs_list_init_link(list, link);
226
227 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC);
228 ocs_list_assert(link->offset == list->offset);
229 ocs_list_assert(link->next == NULL);
230 ocs_list_assert(link->prev == NULL);
231
232 _ocs_list_insert_link(list, list->next, item2link(list, item));
233 }
234
235 /**
236 * @ingroup os
237 * @brief Add an item to the tail of the list
238 *
239 * @param list Head of the list
240 * @param item Item to add
241 */
242 static inline void
ocs_list_add_tail(ocs_list_t * list,void * item)243 ocs_list_add_tail(ocs_list_t *list, void *item)
244 {
245 ocs_list_t *link;
246
247 ocs_list_assert(list);
248 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC);
249 ocs_list_assert(item);
250
251 link = item2link(list, item);
252 ocs_list_init_link(list, link);
253
254 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC);
255 ocs_list_assert(link->offset == list->offset);
256 ocs_list_assert(link->next == NULL);
257 ocs_list_assert(link->prev == NULL);
258
259 _ocs_list_insert_link(list->prev, list, link);
260 }
261
262 /**
263 * @ingroup os
264 * @brief Return the first item in the list
265 *
266 * @param list Head of the list
267 *
268 * @return pointer to the first item, NULL otherwise
269 */
270 static inline void *
ocs_list_get_head(ocs_list_t * list)271 ocs_list_get_head(ocs_list_t *list)
272 {
273 ocs_list_assert(list, NULL);
274 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
275 return ocs_list_empty(list) ? NULL : link2item(list, list->next);
276 }
277
278 /**
279 * @ingroup os
280 * @brief Return the first item in the list
281 *
282 * @param list head of the list
283 *
284 * @return pointer to the last item, NULL otherwise
285 */
286 static inline void *
ocs_list_get_tail(ocs_list_t * list)287 ocs_list_get_tail(ocs_list_t *list)
288 {
289 ocs_list_assert(list, NULL);
290 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
291 return ocs_list_empty(list) ? NULL : link2item(list, list->prev);
292 }
293
294 /**
295 * @ingroup os
296 * @brief Return the last item in the list
297 *
298 * @param list Pointer to list head
299 *
300 * @return pointer to the last item, NULL otherwise
301 */
ocs_list_tail(ocs_list_t * list)302 static inline void *ocs_list_tail(ocs_list_t *list)
303 {
304 ocs_list_assert(list, NULL);
305 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
306 return ocs_list_empty(list) ? NULL : link2item(list, list->prev);
307 }
308
309 /**
310 * @ingroup os
311 * @brief Get the next item on the list
312 *
313 * @param list head of the list
314 * @param item current item
315 *
316 * @return pointer to the next item, NULL otherwise
317 */
ocs_list_next(ocs_list_t * list,void * item)318 static inline void *ocs_list_next(ocs_list_t *list, void *item)
319 {
320 ocs_list_t *link;
321
322 if (item == NULL) {
323 return NULL;
324 }
325
326 ocs_list_assert(list, NULL);
327 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
328 ocs_list_assert(item, NULL);
329
330 link = item2link(list, item);
331
332 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC, NULL);
333 ocs_list_assert(link->offset == list->offset, NULL);
334 ocs_list_assert(link->next, NULL);
335 ocs_list_assert(link->prev, NULL);
336
337 if ((link->next) == list) {
338 return NULL;
339 }
340
341 return link2item(list, link->next);
342 }
343
344 /**
345 * @ingroup os
346 * @brief Remove and return an item from the head of the list
347 *
348 * @param list head of the list
349 *
350 * @return pointer to returned item, or NULL if list is empty
351 */
352 #define ocs_list_remove_head(list) ocs_list_remove(list, ocs_list_get_head(list))
353
354 /**
355 * @ingroup os
356 * @brief Remove an item from the list
357 *
358 * @param list Head of the list
359 * @param item Item to remove
360 *
361 * @return pointer to item, or NULL if item is not found.
362 */
ocs_list_remove(ocs_list_t * list,void * item)363 static inline void *ocs_list_remove(ocs_list_t *list, void *item)
364 {
365 ocs_list_t *link;
366 ocs_list_t *prev;
367 ocs_list_t *next;
368
369 if (item == NULL) {
370 return NULL;
371 }
372 ocs_list_assert(list, NULL);
373 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
374
375 link = item2link(list, item);
376
377 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC, NULL);
378 ocs_list_assert(link->offset == list->offset, NULL);
379 ocs_list_assert(link->next, NULL);
380 ocs_list_assert(link->prev, NULL);
381
382 prev = link->prev;
383 next = link->next;
384
385 prev->next = next;
386 next->prev = prev;
387
388 link->next = link->prev = NULL;
389
390 return item;
391 }
392
393 /**
394 * @brief Iterate a linked list
395 *
396 * Iterate a linked list.
397 *
398 * @param list Pointer to list
399 * @param item Pointer to iterated item
400 *
401 * note, item is NULL after full list is traversed.
402
403 * @return none
404 */
405
406 #define ocs_list_foreach(list, item) \
407 for (item = ocs_list_get_head((list)); item; item = ocs_list_next((list), item) )
408
409 /**
410 * @brief Iterate a linked list safely
411 *
412 * Iterate a linked list safely, meaning that the iterated item
413 * may be safely removed from the list.
414 *
415 * @param list Pointer to list
416 * @param item Pointer to iterated item
417 * @param nxt Pointer to saveed iterated item
418 *
419 * note, item is NULL after full list is traversed.
420 *
421 * @return none
422 */
423
424 #define ocs_list_foreach_safe(list, item, nxt) \
425 for (item = ocs_list_get_head(list), nxt = item ? ocs_list_next(list, item) : NULL; item; \
426 item = nxt, nxt = ocs_list_next(list, item))
427
428 /**
429 * @brief Test if object is on a list
430 *
431 * Returns True if object is on a list
432 *
433 * @param link Pointer to list link
434 *
435 * @return returns True if object is on a list
436 */
437 static inline int32_t
ocs_list_on_list(ocs_list_link_t * link)438 ocs_list_on_list(ocs_list_link_t *link)
439 {
440 return (link->next != NULL);
441 }
442
443 #endif /* __OCS_LIST_H__ */
444