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