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