list.c

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  * CDDL HEADER START
    3  *
    4  * The contents of this file are subject to the terms of the
    5  * Common Development and Distribution License (the "License").
    6  * You may not use this file except in compliance with the License.
    7  *
    8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
    9  * or https://opensource.org/licenses/CDDL-1.0.
   10  * See the License for the specific language governing permissions
   11  * and limitations under the License.
   12  *
   13  * When distributing Covered Code, include this CDDL HEADER in each
   14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
   15  * If applicable, add the following below this CDDL HEADER, with the
   16  * fields enclosed by brackets "[]" replaced with your own identifying
   17  * information: Portions Copyright [yyyy] [name of copyright owner]
   18  *
   19  * CDDL HEADER END
   20  */
   21 /*
   22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
   23  * Use is subject to license terms.
   24  */
   25 
   26 /*
   27  * Generic doubly-linked list implementation
   28  */
   29 
   30 #include <sys/list.h>
   31 #include <sys/list_impl.h>
   32 #include <sys/types.h>
   33 #include <sys/sysmacros.h>
   34 #include <sys/debug.h>
   35 
   36 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
   37 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
   38 #define list_empty(a) ((a)->list_head.next == &(a)->list_head)
   39 
   40 #define list_insert_after_node(list, node, object) {    \
   41         list_node_t *lnew = list_d2l(list, object);     \
   42         lnew->prev = (node);                    \
   43         lnew->next = (node)->next;              \
   44         (node)->next->prev = lnew;              \
   45         (node)->next = lnew;                    \
   46 }
   47 
   48 #define list_insert_before_node(list, node, object) {   \
   49         list_node_t *lnew = list_d2l(list, object);     \
   50         lnew->next = (node);                    \
   51         lnew->prev = (node)->prev;              \
   52         (node)->prev->next = lnew;              \
   53         (node)->prev = lnew;                    \
   54 }
   55 
   56 #define list_remove_node(node)                                  \
   57         (node)->prev->next = (node)->next;      \
   58         (node)->next->prev = (node)->prev;      \
   59         (node)->next = (node)->prev = NULL
   60 
   61 void
   62 list_create(list_t *list, size_t size, size_t offset)
   63 {
   64         ASSERT(list);
   65         ASSERT(size > 0);
   66         ASSERT(size >= offset + sizeof (list_node_t));
   67 
   68         list->list_size = size;
   69         list->list_offset = offset;
   70         list->list_head.next = list->list_head.prev = &list->list_head;
   71 }
   72 
   73 void
   74 list_destroy(list_t *list)
   75 {
   76         list_node_t *node = &list->list_head;
   77 
   78         ASSERT(list);
   79         ASSERT(list->list_head.next == node);
   80         ASSERT(list->list_head.prev == node);
   81 
   82         node->next = node->prev = NULL;
   83 }
   84 
   85 void
   86 list_insert_after(list_t *list, void *object, void *nobject)
   87 {
   88         if (object == NULL) {
   89                 list_insert_head(list, nobject);
   90         } else {
   91                 list_node_t *lold = list_d2l(list, object);
   92                 list_insert_after_node(list, lold, nobject);
   93         }
   94 }
   95 
   96 void
   97 list_insert_before(list_t *list, void *object, void *nobject)
   98 {
   99         if (object == NULL) {
  100                 list_insert_tail(list, nobject);
  101         } else {
  102                 list_node_t *lold = list_d2l(list, object);
  103                 list_insert_before_node(list, lold, nobject);
  104         }
  105 }
  106 
  107 void
  108 list_insert_head(list_t *list, void *object)
  109 {
  110         list_node_t *lold = &list->list_head;
  111         list_insert_after_node(list, lold, object);
  112 }
  113 
  114 void
  115 list_insert_tail(list_t *list, void *object)
  116 {
  117         list_node_t *lold = &list->list_head;
  118         list_insert_before_node(list, lold, object);
  119 }
  120 
  121 void
  122 list_remove(list_t *list, void *object)
  123 {
  124         list_node_t *lold = list_d2l(list, object);
  125         ASSERT(!list_empty(list));
  126         ASSERT(lold->next != NULL);
  127         list_remove_node(lold);
  128 }
  129 
  130 void *
  131 list_remove_head(list_t *list)
  132 {
  133         list_node_t *head = list->list_head.next;
  134         if (head == &list->list_head)
  135                 return (NULL);
  136         list_remove_node(head);
  137         return (list_object(list, head));
  138 }
  139 
  140 void *
  141 list_remove_tail(list_t *list)
  142 {
  143         list_node_t *tail = list->list_head.prev;
  144         if (tail == &list->list_head)
  145                 return (NULL);
  146         list_remove_node(tail);
  147         return (list_object(list, tail));
  148 }
  149 
  150 void *
  151 list_head(list_t *list)
  152 {
  153         if (list_empty(list))
  154                 return (NULL);
  155         return (list_object(list, list->list_head.next));
  156 }
  157 
  158 void *
  159 list_tail(list_t *list)
  160 {
  161         if (list_empty(list))
  162                 return (NULL);
  163         return (list_object(list, list->list_head.prev));
  164 }
  165 
  166 void *
  167 list_next(list_t *list, void *object)
  168 {
  169         list_node_t *node = list_d2l(list, object);
  170 
  171         if (node->next != &list->list_head)
  172                 return (list_object(list, node->next));
  173 
  174         return (NULL);
  175 }
  176 
  177 void *
  178 list_prev(list_t *list, void *object)
  179 {
  180         list_node_t *node = list_d2l(list, object);
  181 
  182         if (node->prev != &list->list_head)
  183                 return (list_object(list, node->prev));
  184 
  185         return (NULL);
  186 }
  187 
  188 /*
  189  *  Insert src list after dst list. Empty src list thereafter.
  190  */
  191 void
  192 list_move_tail(list_t *dst, list_t *src)
  193 {
  194         list_node_t *dstnode = &dst->list_head;
  195         list_node_t *srcnode = &src->list_head;
  196 
  197         ASSERT(dst->list_size == src->list_size);
  198         ASSERT(dst->list_offset == src->list_offset);
  199 
  200         if (list_empty(src))
  201                 return;
  202 
  203         dstnode->prev->next = srcnode->next;
  204         srcnode->next->prev = dstnode->prev;
  205         dstnode->prev = srcnode->prev;
  206         srcnode->prev->next = dstnode;
  207 
  208         /* empty src list */
  209         srcnode->next = srcnode->prev = srcnode;
  210 }
  211 
  212 void
  213 list_link_replace(list_node_t *lold, list_node_t *lnew)
  214 {
  215         ASSERT(list_link_active(lold));
  216         ASSERT(!list_link_active(lnew));
  217 
  218         lnew->next = lold->next;
  219         lnew->prev = lold->prev;
  220         lold->prev->next = lnew;
  221         lold->next->prev = lnew;
  222         lold->next = lold->prev = NULL;
  223 }
  224 
  225 void
  226 list_link_init(list_node_t *ln)
  227 {
  228         ln->next = NULL;
  229         ln->prev = NULL;
  230 }
  231 
  232 int
  233 list_link_active(list_node_t *ln)
  234 {
  235         EQUIV(ln->next == NULL, ln->prev == NULL);
  236         return (ln->next != NULL);
  237 }
  238 
  239 int
  240 list_is_empty(list_t *list)
  241 {
  242         return (list_empty(list));
  243 }

Cache object: 78e12a75cffd9c2705548895b6218d6a

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

FreeBSD/Linux Kernel Cross Reference sys/contrib/openzfs/lib/libspl/list.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/openzfs/lib/libspl/list.c