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