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: releng/12.0/sys/dev/ocs_fc/ocs_list.h 331766 2018-03-30 15:28:25Z ken $
   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__ */

Cache object: 2b377d444a9775a3a81c982ac13423f3


[ 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.