usr/src/common/list/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 http://www.opensolaris.org/os/licensing.
  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 (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
  23  */
  24
  25 /*
  26  * Generic doubly-linked list implementation
  27  */
  28
  29 #include <sys/list.h>
  30 #include <sys/list_impl.h>
  31 #include <sys/types.h>
  32 #include <sys/sysmacros.h>
  33 #ifdef _KERNEL
  34 #include <sys/debug.h>
  35 #else
  36 #include <assert.h>
  37 #define ASSERT(a)       assert(a)
  38 #endif
  39
  40 #ifdef lint
  41 extern list_node_t *list_d2l(list_t *list, void *obj);
  42 #else
  43 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
  44 #endif
  45 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
  46 #define list_empty(a) ((a)->list_head.list_next == &(a)->list_head)
  47
  48 #define list_insert_after_node(list, node, object) {    \
  49         list_node_t *lnew = list_d2l(list, object);     \
  50         lnew->list_prev = (node);                       \
  51         lnew->list_next = (node)->list_next;            \
  52         (node)->list_next->list_prev = lnew;            \
  53         (node)->list_next = lnew;                       \
  54 }
  55
  56 #define list_insert_before_node(list, node, object) {   \
  57         list_node_t *lnew = list_d2l(list, object);     \
  58         lnew->list_next = (node);                       \
  59         lnew->list_prev = (node)->list_prev;            \
  60         (node)->list_prev->list_next = lnew;            \
  61         (node)->list_prev = lnew;                       \
  62 }
  63
  64 #define list_remove_node(node)                                  \
  65         (node)->list_prev->list_next = (node)->list_next;       \
  66         (node)->list_next->list_prev = (node)->list_prev;       \
  67         (node)->list_next = (node)->list_prev = NULL
  68
  69 void
  70 list_create(list_t *list, size_t size, size_t offset)
  71 {
  72         ASSERT(list);
  73         ASSERT(size > 0);
  74         ASSERT(size >= offset + sizeof (list_node_t));
  75
  76         list->list_size = size;
  77         list->list_offset = offset;
  78         list->list_head.list_next = list->list_head.list_prev =
  79             &list->list_head;
  80 }
  81
  82 void
  83 list_destroy(list_t *list)
  84 {
  85         list_node_t *node = &list->list_head;
  86
  87         ASSERT(list);
  88         ASSERT(list->list_head.list_next == node);
  89         ASSERT(list->list_head.list_prev == node);
  90
  91         node->list_next = node->list_prev = NULL;
  92 }
  93
  94 void
  95 list_insert_after(list_t *list, void *object, void *nobject)
  96 {
  97         if (object == NULL) {
  98                 list_insert_head(list, nobject);
  99         } else {
 100                 list_node_t *lold = list_d2l(list, object);
 101                 list_insert_after_node(list, lold, nobject);
 102         }
 103 }
 104
 105 void
 106 list_insert_before(list_t *list, void *object, void *nobject)
 107 {
 108         if (object == NULL) {
 109                 list_insert_tail(list, nobject);
 110         } else {
 111                 list_node_t *lold = list_d2l(list, object);
 112                 list_insert_before_node(list, lold, nobject);
 113         }
 114 }
 115
 116 void
 117 list_insert_head(list_t *list, void *object)
 118 {
 119         list_node_t *lold = &list->list_head;
 120         list_insert_after_node(list, lold, object);
 121 }
 122
 123 void
 124 list_insert_tail(list_t *list, void *object)
 125 {
 126         list_node_t *lold = &list->list_head;
 127         list_insert_before_node(list, lold, object);
 128 }
 129
 130 void
 131 list_remove(list_t *list, void *object)
 132 {
 133         list_node_t *lold = list_d2l(list, object);
 134         ASSERT(!list_empty(list));
 135         ASSERT(lold->list_next != NULL);
 136         list_remove_node(lold);
 137 }
 138
 139 void *
 140 list_remove_head(list_t *list)
 141 {
 142         list_node_t *head = list->list_head.list_next;
 143         if (head == &list->list_head)
 144                 return (NULL);
 145         list_remove_node(head);
 146         return (list_object(list, head));
 147 }
 148
 149 void *
 150 list_remove_tail(list_t *list)
 151 {
 152         list_node_t *tail = list->list_head.list_prev;
 153         if (tail == &list->list_head)
 154                 return (NULL);
 155         list_remove_node(tail);
 156         return (list_object(list, tail));
 157 }
 158
 159 void *
 160 list_head(list_t *list)
 161 {
 162         if (list_empty(list))
 163                 return (NULL);
 164         return (list_object(list, list->list_head.list_next));
 165 }
 166
 167 void *
 168 list_tail(list_t *list)
 169 {
 170         if (list_empty(list))
 171                 return (NULL);
 172         return (list_object(list, list->list_head.list_prev));
 173 }
 174
 175 void *
 176 list_next(list_t *list, void *object)
 177 {
 178         list_node_t *node = list_d2l(list, object);
 179
 180         if (node->list_next != &list->list_head)
 181                 return (list_object(list, node->list_next));
 182
 183         return (NULL);
 184 }
 185
 186 void *
 187 list_prev(list_t *list, void *object)
 188 {
 189         list_node_t *node = list_d2l(list, object);
 190
 191         if (node->list_prev != &list->list_head)
 192                 return (list_object(list, node->list_prev));
 193
 194         return (NULL);
 195 }
 196
 197 /*
 198  *  Insert src list after dst list. Empty src list thereafter.
 199  */
 200 void
 201 list_move_tail(list_t *dst, list_t *src)
 202 {
 203         list_node_t *dstnode = &dst->list_head;
 204         list_node_t *srcnode = &src->list_head;
 205
 206         ASSERT(dst->list_size == src->list_size);
 207         ASSERT(dst->list_offset == src->list_offset);
 208
 209         if (list_empty(src))
 210                 return;
 211
 212         dstnode->list_prev->list_next = srcnode->list_next;
 213         srcnode->list_next->list_prev = dstnode->list_prev;
 214         dstnode->list_prev = srcnode->list_prev;
 215         srcnode->list_prev->list_next = dstnode;
 216
 217         /* empty src list */
 218         srcnode->list_next = srcnode->list_prev = srcnode;
 219 }
 220
 221 void
 222 list_link_replace(list_node_t *lold, list_node_t *lnew)
 223 {
 224         ASSERT(list_link_active(lold));
 225         ASSERT(!list_link_active(lnew));
 226
 227         lnew->list_next = lold->list_next;
 228         lnew->list_prev = lold->list_prev;
 229         lold->list_prev->list_next = lnew;
 230         lold->list_next->list_prev = lnew;
 231         lold->list_next = lold->list_prev = NULL;
 232 }
 233
 234 void
 235 list_link_init(list_node_t *link)
 236 {
 237         link->list_next = NULL;
 238         link->list_prev = NULL;
 239 }
 240
 241 int
 242 list_link_active(list_node_t *link)
 243 {
 244         return (link->list_next != NULL);
 245 }
 246
 247 int
 248 list_is_empty(list_t *list)
 249 {
 250         return (list_empty(list));
 251 }