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