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 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__ */ 450