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 * $FreeBSD$
32 */
33
34 /**
35 * @file
36 *
37 * OCS linked list API
38 *
39 */
40
41 #if !defined(__OCS_LIST_H__)
42 #define __OCS_LIST_H__
43
44 #define OCS_LIST_DEBUG
45
46 #if defined(OCS_LIST_DEBUG)
47
48 #define ocs_list_magic_decl uint32_t magic;
49 #define OCS_LIST_LIST_MAGIC 0xcafe0000
50 #define OCS_LIST_LINK_MAGIC 0xcafe0001
51 #define ocs_list_set_list_magic list->magic = OCS_LIST_LIST_MAGIC
52 #define ocs_list_set_link_magic list->magic = OCS_LIST_LINK_MAGIC
53
54 #define ocs_list_assert(cond, ...) \
55 if (!(cond)) { \
56 return __VA_ARGS__; \
57 }
58 #else
59 #define ocs_list_magic_decl
60 #define ocs_list_assert(cond, ...)
61 #define ocs_list_set_list_magic
62 #define ocs_list_set_link_magic
63 #endif
64
65 /**
66 * @brief list/link structure
67 *
68 * used for both the list object, and the link object(s). offset
69 * is specified when the list is initialized; this implies that a list
70 * will always point to objects of the same type. offset is not used
71 * when ocs_list_t is used as a link (ocs_list_link_t).
72 *
73 */
74
75 typedef struct ocs_list_s ocs_list_t;
76 struct ocs_list_s {
77 ocs_list_magic_decl /*<< used if debugging is enabled */
78 ocs_list_t *next; /*<< pointer to head of list (or next if link) */
79 ocs_list_t *prev; /*<< pointer to tail of list (or previous if link) */
80 uint32_t offset; /*<< offset in bytes to the link element of the objects in list */
81 };
82 typedef ocs_list_t ocs_list_link_t;
83
84 /* item2link - return pointer to link given pointer to an item */
85 #define item2link(list, item) ((ocs_list_t*) (((uint8_t*)(item)) + (list)->offset))
86
87 /* link2item - return pointer to item given pointer to a link */
88 #define link2item(list, link) ((void*) (((uint8_t*)(link)) - (list)->offset))
89
90 /**
91 * @brief Initialize a list
92 *
93 * A list object is initialized. Helper define is used to call _ocs_list_init() with
94 * offsetof(type, link)
95 *
96 * @param list Pointer to list
97 * @param offset Offset in bytes in item to the link element
98 *
99 * @return none
100 */
101 static inline void
102 _ocs_list_init(ocs_list_t *list, uint32_t offset)
103 {
104 ocs_list_assert(list);
105 ocs_list_set_list_magic;
106
107 list->next = list;
108 list->prev = list;
109 list->offset = offset;
110 }
111 #define ocs_list_init(head, type, link) _ocs_list_init(head, offsetof(type, link))
112
113 /**
114 * @ingroup os
115 * @brief Test if a list is empty
116 *
117 * @param list Pointer to list head
118 *
119 * @return 1 if empty, 0 otherwise
120 */
121 static inline int32_t
122 ocs_list_empty(ocs_list_t *list)
123 {
124 ocs_list_assert(list, 1);
125 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, 1);
126 return list->next == list;
127 }
128
129 /**
130 * @ingroup os
131 * @brief Test if a list is valid (ready for use)
132 *
133 * @param list Pointer to list head
134 *
135 * @return true if list is usable, false otherwise
136 */
137 static inline int
138 ocs_list_valid(ocs_list_t *list)
139 {
140 return (list->magic == OCS_LIST_LIST_MAGIC);
141 }
142
143 /**
144 * @brief Insert link between two other links
145 *
146 * Inserts a link in between two other links
147 *
148 * @param a Pointer to first link
149 * @param b Pointer to next link
150 * @param c Pointer to link to insert between a and b
151 *
152 * @return none
153 */
154 static inline void
155 _ocs_list_insert_link(ocs_list_t *a, ocs_list_t *b, ocs_list_t *c)
156 {
157 ocs_list_assert(a);
158 ocs_list_assert((a->magic == OCS_LIST_LIST_MAGIC) || (a->magic == OCS_LIST_LINK_MAGIC));
159 ocs_list_assert(a->next);
160 ocs_list_assert(a->prev);
161 ocs_list_assert(b);
162 ocs_list_assert((b->magic == OCS_LIST_LIST_MAGIC) || (b->magic == OCS_LIST_LINK_MAGIC));
163 ocs_list_assert(b->next);
164 ocs_list_assert(b->prev);
165 ocs_list_assert(c);
166 ocs_list_assert((c->magic == OCS_LIST_LIST_MAGIC) || (c->magic == OCS_LIST_LINK_MAGIC));
167 ocs_list_assert(!c->next);
168 ocs_list_assert(!c->prev);
169
170 ocs_list_assert(a->offset == b->offset);
171 ocs_list_assert(b->offset == c->offset);
172
173 c->next = a->next;
174 c->prev = b->prev;
175 a->next = c;
176 b->prev = c;
177 }
178
179 #if defined(OCS_LIST_DEBUG)
180 /**
181 * @brief Initialize a list link for debug purposes
182 *
183 * For debugging a linked list link element has a magic number that is initialized,
184 * and the offset value initialized and used for subsequent assertions.
185 *
186 *
187 * @param list Pointer to list head
188 * @param link Pointer to link to be initialized
189 *
190 * @return none
191 */
192 static inline void
193 ocs_list_init_link(ocs_list_t *list, ocs_list_t *link)
194 {
195 ocs_list_assert(list);
196 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC);
197 ocs_list_assert(link);
198
199 if (link->magic == 0) {
200 link->magic = OCS_LIST_LINK_MAGIC;
201 link->offset = list->offset;
202 link->next = NULL;
203 link->prev = NULL;
204 }
205 }
206 #else
207 #define ocs_list_init_link(...)
208 #endif
209
210 /**
211 * @ingroup os
212 * @brief Add an item to the head of the list
213 *
214 * @param list Pointer to list head
215 * @param item Item to add
216 */
217 static inline void
218 ocs_list_add_head(ocs_list_t *list, void *item)
219 {
220 ocs_list_t *link;
221
222 ocs_list_assert(list);
223 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC);
224 ocs_list_assert(item);
225
226 link = item2link(list, item);
227 ocs_list_init_link(list, link);
228
229 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC);
230 ocs_list_assert(link->offset == list->offset);
231 ocs_list_assert(link->next == NULL);
232 ocs_list_assert(link->prev == NULL);
233
234 _ocs_list_insert_link(list, list->next, item2link(list, item));
235 }
236
237 /**
238 * @ingroup os
239 * @brief Add an item to the tail of the list
240 *
241 * @param list Head of the list
242 * @param item Item to add
243 */
244 static inline void
245 ocs_list_add_tail(ocs_list_t *list, void *item)
246 {
247 ocs_list_t *link;
248
249 ocs_list_assert(list);
250 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC);
251 ocs_list_assert(item);
252
253 link = item2link(list, item);
254 ocs_list_init_link(list, link);
255
256 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC);
257 ocs_list_assert(link->offset == list->offset);
258 ocs_list_assert(link->next == NULL);
259 ocs_list_assert(link->prev == NULL);
260
261 _ocs_list_insert_link(list->prev, list, link);
262 }
263
264 /**
265 * @ingroup os
266 * @brief Return the first item in the list
267 *
268 * @param list Head of the list
269 *
270 * @return pointer to the first item, NULL otherwise
271 */
272 static inline void *
273 ocs_list_get_head(ocs_list_t *list)
274 {
275 ocs_list_assert(list, NULL);
276 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
277 return ocs_list_empty(list) ? NULL : link2item(list, list->next);
278 }
279
280 /**
281 * @ingroup os
282 * @brief Return the first item in the list
283 *
284 * @param list head of the list
285 *
286 * @return pointer to the last item, NULL otherwise
287 */
288 static inline void *
289 ocs_list_get_tail(ocs_list_t *list)
290 {
291 ocs_list_assert(list, NULL);
292 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
293 return ocs_list_empty(list) ? NULL : link2item(list, list->prev);
294 }
295
296 /**
297 * @ingroup os
298 * @brief Return the last item in the list
299 *
300 * @param list Pointer to list head
301 *
302 * @return pointer to the last item, NULL otherwise
303 */
304 static inline void *ocs_list_tail(ocs_list_t *list)
305 {
306 ocs_list_assert(list, NULL);
307 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
308 return ocs_list_empty(list) ? NULL : link2item(list, list->prev);
309 }
310
311 /**
312 * @ingroup os
313 * @brief Get the next item on the list
314 *
315 * @param list head of the list
316 * @param item current item
317 *
318 * @return pointer to the next item, NULL otherwise
319 */
320 static inline void *ocs_list_next(ocs_list_t *list, void *item)
321 {
322 ocs_list_t *link;
323
324 if (item == NULL) {
325 return NULL;
326 }
327
328 ocs_list_assert(list, NULL);
329 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
330 ocs_list_assert(item, NULL);
331
332 link = item2link(list, item);
333
334 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC, NULL);
335 ocs_list_assert(link->offset == list->offset, NULL);
336 ocs_list_assert(link->next, NULL);
337 ocs_list_assert(link->prev, NULL);
338
339 if ((link->next) == list) {
340 return NULL;
341 }
342
343 return link2item(list, link->next);
344 }
345
346 /**
347 * @ingroup os
348 * @brief Remove and return an item from the head of the list
349 *
350 * @param list head of the list
351 *
352 * @return pointer to returned item, or NULL if list is empty
353 */
354 #define ocs_list_remove_head(list) ocs_list_remove(list, ocs_list_get_head(list))
355
356 /**
357 * @ingroup os
358 * @brief Remove an item from the list
359 *
360 * @param list Head of the list
361 * @param item Item to remove
362 *
363 * @return pointer to item, or NULL if item is not found.
364 */
365 static inline void *ocs_list_remove(ocs_list_t *list, void *item)
366 {
367 ocs_list_t *link;
368 ocs_list_t *prev;
369 ocs_list_t *next;
370
371 if (item == NULL) {
372 return NULL;
373 }
374 ocs_list_assert(list, NULL);
375 ocs_list_assert(list->magic == OCS_LIST_LIST_MAGIC, NULL);
376
377 link = item2link(list, item);
378
379 ocs_list_assert(link->magic == OCS_LIST_LINK_MAGIC, NULL);
380 ocs_list_assert(link->offset == list->offset, NULL);
381 ocs_list_assert(link->next, NULL);
382 ocs_list_assert(link->prev, NULL);
383
384 prev = link->prev;
385 next = link->next;
386
387 prev->next = next;
388 next->prev = prev;
389
390 link->next = link->prev = NULL;
391
392 return item;
393 }
394
395 /**
396 * @brief Iterate a linked list
397 *
398 * Iterate a linked list.
399 *
400 * @param list Pointer to list
401 * @param item Pointer to iterated item
402 *
403 * note, item is NULL after full list is traversed.
404
405 * @return none
406 */
407
408 #define ocs_list_foreach(list, item) \
409 for (item = ocs_list_get_head((list)); item; item = ocs_list_next((list), item) )
410
411 /**
412 * @brief Iterate a linked list safely
413 *
414 * Iterate a linked list safely, meaning that the iterated item
415 * may be safely removed from the list.
416 *
417 * @param list Pointer to list
418 * @param item Pointer to iterated item
419 * @param nxt Pointer to saveed iterated item
420 *
421 * note, item is NULL after full list is traversed.
422 *
423 * @return none
424 */
425
426 #define ocs_list_foreach_safe(list, item, nxt) \
427 for (item = ocs_list_get_head(list), nxt = item ? ocs_list_next(list, item) : NULL; item; \
428 item = nxt, nxt = ocs_list_next(list, item))
429
430 /**
431 * @brief Test if object is on a list
432 *
433 * Returns True if object is on a list
434 *
435 * @param link Pointer to list link
436 *
437 * @return returns True if object is on a list
438 */
439 static inline int32_t
440 ocs_list_on_list(ocs_list_link_t *link)
441 {
442 return (link->next != NULL);
443 }
444
445 #endif /* __OCS_LIST_H__ */
Cache object: 72dfdf844e6a2ab756d2541ac6b744b5
|