lib/libspl/list.c

   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 }