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
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
76typedef struct ocs_list_s ocs_list_t;
77struct 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};
83typedef 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 */
102static 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 */
123static inline int32_t
124ocs_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 */
139static inline int
140ocs_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 */
156static 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 */
194static inline void
195ocs_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 */
219static inline void
220ocs_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 */
247static inline void
248ocs_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 */
276static inline void *
277ocs_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 */
292static inline void *
293ocs_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 */
308static 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 */
324static 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 */
369static 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 */
443static inline int32_t
444ocs_list_on_list(ocs_list_link_t *link)
445{
446	return (link->next != NULL);
447}
448
449#endif /* __OCS_LIST_H__ */
450