sys/dev/ocs_fc/ocs_list.h

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