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/param.h>
   31 #include <sys/list.h>
   32 #include <sys/list_impl.h>
   33 #include <sys/types.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.list_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->list_prev = (node);                       \
   43         lnew->list_next = (node)->list_next;            \
   44         (node)->list_next->list_prev = lnew;            \
   45         (node)->list_next = lnew;                       \
   46 }
   47 
   48 #define list_insert_before_node(list, node, object) {   \
   49         list_node_t *lnew = list_d2l(list, object);     \
   50         lnew->list_next = (node);                       \
   51         lnew->list_prev = (node)->list_prev;            \
   52         (node)->list_prev->list_next = lnew;            \
   53         (node)->list_prev = lnew;                       \
   54 }
   55 
   56 #define list_remove_node(node)                                  \
   57         (node)->list_prev->list_next = (node)->list_next;       \
   58         (node)->list_next->list_prev = (node)->list_prev;       \
   59         (node)->list_next = (node)->list_prev = NULL
   60 
   61 void
   62 list_create(list_t *list, size_t size, size_t offset)
   63 {
   64         ASSERT3P(list, !=, NULL);
   65         ASSERT3U(size, >=, offset + sizeof (list_node_t));
   66 
   67         list->list_size = size;
   68         list->list_offset = offset;
   69         list->list_head.list_next = list->list_head.list_prev =
   70             &list->list_head;
   71 }
   72 
   73 void
   74 list_destroy(list_t *list)
   75 {
   76         list_node_t *node = &list->list_head;
   77 
   78         ASSERT3P(list, !=, NULL);
   79         ASSERT3P(list->list_head.list_next, ==, node);
   80         ASSERT3P(list->list_head.list_prev, ==, node);
   81 
   82         node->list_next = node->list_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         ASSERT3P(lold->list_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.list_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.list_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.list_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.list_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->list_next != &list->list_head)
  172                 return (list_object(list, node->list_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->list_prev != &list->list_head)
  183                 return (list_object(list, node->list_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         ASSERT3U(dst->list_size, ==, src->list_size);
  198         ASSERT3U(dst->list_offset, ==, src->list_offset);
  199 
  200         if (list_empty(src))
  201                 return;
  202 
  203         dstnode->list_prev->list_next = srcnode->list_next;
  204         srcnode->list_next->list_prev = dstnode->list_prev;
  205         dstnode->list_prev = srcnode->list_prev;
  206         srcnode->list_prev->list_next = dstnode;
  207 
  208         /* empty src list */
  209         srcnode->list_next = srcnode->list_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->list_next = lold->list_next;
  219         lnew->list_prev = lold->list_prev;
  220         lold->list_prev->list_next = lnew;
  221         lold->list_next->list_prev = lnew;
  222         lold->list_next = lold->list_prev = NULL;
  223 }
  224 
  225 void
  226 list_link_init(list_node_t *link)
  227 {
  228         link->list_next = NULL;
  229         link->list_prev = NULL;
  230 }
  231 
  232 int
  233 list_link_active(list_node_t *link)
  234 {
  235         EQUIV(link->list_next == NULL, link->list_prev == NULL);
  236         return (link->list_next != NULL);
  237 }
  238 
  239 int
  240 list_is_empty(list_t *list)
  241 {
  242         return (list_empty(list));
  243 }

Cache object: a68fec07e2157cad68b652e38c8a73cd

[ 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/module/os/freebsd/spl/list.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/openzfs/module/os/freebsd/spl/list.c