The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/dev/ocs_fc/ocs_list.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

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

Cache object: 250a51a5d59e99030e577191cfa7846b


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.