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 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 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 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 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 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 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 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 * 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 * 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 */ 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 */ 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 */ 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 438 ocs_list_on_list(ocs_list_link_t *link) 439 { 440 return (link->next != NULL); 441 } 442 443 #endif /* __OCS_LIST_H__ */ 444