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