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