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