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 2006 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 void
  59 list_create(list_t *list, size_t size, size_t offset)
  60 {
  61         ASSERT(list);
  62         ASSERT(size > 0);
  63         ASSERT(size >= offset + sizeof (list_node_t));
  64
  65         list->list_size = size;
  66         list->list_offset = offset;
  67         list->list_head.list_next = list->list_head.list_prev =
  68             &list->list_head;
  69 }
  70
  71 void
  72 list_destroy(list_t *list)
  73 {
  74         list_node_t *node = &list->list_head;
  75
  76         ASSERT(list);
  77         ASSERT(list->list_head.list_next == node);
  78         ASSERT(list->list_head.list_prev == node);
  79
  80         node->list_next = node->list_prev = NULL;
  81 }
  82
  83 void
  84 list_insert_after(list_t *list, void *object, void *nobject)
  85 {
  86         list_node_t *lold = list_d2l(list, object);
  87         list_insert_after_node(list, lold, nobject);
  88 }
  89
  90 void
  91 list_insert_before(list_t *list, void *object, void *nobject)
  92 {
  93         list_node_t *lold = list_d2l(list, object);
  94         list_insert_before_node(list, lold, nobject)
  95 }
  96
  97 void
  98 list_insert_head(list_t *list, void *object)
  99 {
 100         list_node_t *lold = &list->list_head;
 101         list_insert_after_node(list, lold, object);
 102 }
 103
 104 void
 105 list_insert_tail(list_t *list, void *object)
 106 {
 107         list_node_t *lold = &list->list_head;
 108         list_insert_before_node(list, lold, object);
 109 }
 110
 111 void
 112 list_remove(list_t *list, void *object)
 113 {
 114         list_node_t *lold = list_d2l(list, object);
 115         ASSERT(!list_empty(list));
 116         lold->list_prev->list_next = lold->list_next;
 117         lold->list_next->list_prev = lold->list_prev;
 118         lold->list_next = lold->list_prev = NULL;
 119 }
 120
 121 void *
 122 list_head(list_t *list)
 123 {
 124         if (list_empty(list))
 125                 return (NULL);
 126         return (list_object(list, list->list_head.list_next));
 127 }
 128
 129 void *
 130 list_tail(list_t *list)
 131 {
 132         if (list_empty(list))
 133                 return (NULL);
 134         return (list_object(list, list->list_head.list_prev));
 135 }
 136
 137 void *
 138 list_next(list_t *list, void *object)
 139 {
 140         list_node_t *node = list_d2l(list, object);
 141
 142         if (node->list_next != &list->list_head)
 143                 return (list_object(list, node->list_next));
 144
 145         return (NULL);
 146 }
 147
 148 void *
 149 list_prev(list_t *list, void *object)
 150 {
 151         list_node_t *node = list_d2l(list, object);
 152
 153         if (node->list_prev != &list->list_head)
 154                 return (list_object(list, node->list_prev));
 155
 156         return (NULL);
 157 }
 158
 159 /*
 160  *  Insert src list after dst list. Empty src list thereafter.
 161  */
 162 void
 163 list_move_tail(list_t *dst, list_t *src)
 164 {
 165         list_node_t *dstnode = &dst->list_head;
 166         list_node_t *srcnode = &src->list_head;
 167
 168         ASSERT(dst->list_size == src->list_size);
 169         ASSERT(dst->list_offset == src->list_offset);
 170
 171         if (list_empty(src))
 172                 return;
 173
 174         dstnode->list_prev->list_next = srcnode->list_next;
 175         srcnode->list_next->list_prev = dstnode->list_prev;
 176         dstnode->list_prev = srcnode->list_prev;
 177         srcnode->list_prev->list_next = dstnode;
 178
 179         /* empty src list */
 180         srcnode->list_next = srcnode->list_prev = srcnode;
 181 }
 182
 183 int
 184 list_link_active(list_node_t *link)
 185 {
 186         return (link->list_next != NULL);
 187 }
 188
 189 int
 190 list_is_empty(list_t *list)
 191 {
 192         return (list_empty(list));
 193 }