1178825Sdfr/* 2178825Sdfr * CDDL HEADER START 3233294Sstas * 4233294Sstas * The contents of this file are subject to the terms of the 5233294Sstas * Common Development and Distribution License (the "License"). 6178825Sdfr * You may not use this file except in compliance with the License. 7233294Sstas * 8233294Sstas * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9233294Sstas * or http://www.opensolaris.org/os/licensing. 10178825Sdfr * See the License for the specific language governing permissions 11233294Sstas * and limitations under the License. 12233294Sstas * 13178825Sdfr * When distributing Covered Code, include this CDDL HEADER in each 14233294Sstas * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15233294Sstas * If applicable, add the following below this CDDL HEADER, with the 16233294Sstas * fields enclosed by brackets "[]" replaced with your own identifying 17178825Sdfr * information: Portions Copyright [yyyy] [name of copyright owner] 18233294Sstas * 19233294Sstas * CDDL HEADER END 20233294Sstas */ 21178825Sdfr/* 22233294Sstas * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 23233294Sstas * Use is subject to license terms. 24233294Sstas */ 25233294Sstas 26233294Sstas#pragma ident "%Z%%M% %I% %E% SMI" 27233294Sstas 28233294Sstas/* 29233294Sstas * Generic doubly-linked list implementation 30233294Sstas */ 31233294Sstas 32233294Sstas#include <sys/list.h> 33178825Sdfr#include <sys/list_impl.h> 34178825Sdfr#include <sys/types.h> 35178825Sdfr#include <sys/sysmacros.h> 36178825Sdfr#include <sys/debug.h> 37178825Sdfr 38178825Sdfr#define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset)) 39178825Sdfr#define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset)) 40178825Sdfr#define list_empty(a) ((a)->list_head.list_next == &(a)->list_head) 41178825Sdfr 42178825Sdfr#define list_insert_after_node(list, node, object) { \ 43178825Sdfr list_node_t *lnew = list_d2l(list, object); \ 44178825Sdfr lnew->list_prev = (node); \ 45178825Sdfr lnew->list_next = (node)->list_next; \ 46178825Sdfr (node)->list_next->list_prev = lnew; \ 47178825Sdfr (node)->list_next = lnew; \ 48178825Sdfr} 49222081Sbenl 50233294Sstas#define list_insert_before_node(list, node, object) { \ 51233294Sstas list_node_t *lnew = list_d2l(list, object); \ 52233294Sstas lnew->list_next = (node); \ 53233294Sstas lnew->list_prev = (node)->list_prev; \ 54233294Sstas (node)->list_prev->list_next = lnew; \ 55233294Sstas (node)->list_prev = lnew; \ 56178825Sdfr} 57178825Sdfr 58178825Sdfr#define list_remove_node(node) \ 59178825Sdfr (node)->list_prev->list_next = (node)->list_next; \ 60178825Sdfr (node)->list_next->list_prev = (node)->list_prev; \ 61178825Sdfr (node)->list_next = (node)->list_prev = NULL 62178825Sdfr 63178825Sdfrvoid 64178825Sdfrlist_create(list_t *list, size_t size, size_t offset) 65178825Sdfr{ 66178825Sdfr ASSERT(list); 67178825Sdfr ASSERT(size > 0); 68178825Sdfr ASSERT(size >= offset + sizeof (list_node_t)); 69178825Sdfr 70178825Sdfr list->list_size = size; 71178825Sdfr list->list_offset = offset; 72178825Sdfr list->list_head.list_next = list->list_head.list_prev = 73178825Sdfr &list->list_head; 74178825Sdfr} 75178825Sdfr 76178825Sdfrvoid 77178825Sdfrlist_destroy(list_t *list) 78178825Sdfr{ 79178825Sdfr list_node_t *node = &list->list_head; 80178825Sdfr 81178825Sdfr ASSERT(list); 82178825Sdfr ASSERT(list->list_head.list_next == node); 83178825Sdfr ASSERT(list->list_head.list_prev == node); 84178825Sdfr 85178825Sdfr node->list_next = node->list_prev = NULL; 86178825Sdfr} 87178825Sdfr 88178825Sdfrvoid 89178825Sdfrlist_insert_after(list_t *list, void *object, void *nobject) 90178825Sdfr{ 91178825Sdfr if (object == NULL) { 92178825Sdfr list_insert_head(list, nobject); 93178825Sdfr } else { 94178825Sdfr list_node_t *lold = list_d2l(list, object); 95178825Sdfr list_insert_after_node(list, lold, nobject); 96178825Sdfr } 97178825Sdfr} 98178825Sdfr 99178825Sdfrvoid 100178825Sdfrlist_insert_before(list_t *list, void *object, void *nobject) 101178825Sdfr{ 102178825Sdfr if (object == NULL) { 103178825Sdfr list_insert_tail(list, nobject); 104178825Sdfr } else { 105178825Sdfr list_node_t *lold = list_d2l(list, object); 106178825Sdfr list_insert_before_node(list, lold, nobject); 107178825Sdfr } 108178825Sdfr} 109178825Sdfr 110178825Sdfrvoid 111178825Sdfrlist_insert_head(list_t *list, void *object) 112178825Sdfr{ 113178825Sdfr list_node_t *lold = &list->list_head; 114178825Sdfr list_insert_after_node(list, lold, object); 115178825Sdfr} 116178825Sdfr 117178825Sdfrvoid 118178825Sdfrlist_insert_tail(list_t *list, void *object) 119178825Sdfr{ 120178825Sdfr list_node_t *lold = &list->list_head; 121178825Sdfr list_insert_before_node(list, lold, object); 122178825Sdfr} 123178825Sdfr 124178825Sdfrvoid 125178825Sdfrlist_remove(list_t *list, void *object) 126178825Sdfr{ 127178825Sdfr list_node_t *lold = list_d2l(list, object); 128178825Sdfr ASSERT(!list_empty(list)); 129178825Sdfr ASSERT(lold->list_next != NULL); 130233294Sstas list_remove_node(lold); 131178825Sdfr} 132178825Sdfr 133178825Sdfrvoid * 134178825Sdfrlist_remove_head(list_t *list) 135178825Sdfr{ 136178825Sdfr list_node_t *head = list->list_head.list_next; 137178825Sdfr if (head == &list->list_head) 138178825Sdfr return (NULL); 139178825Sdfr list_remove_node(head); 140178825Sdfr return (list_object(list, head)); 141178825Sdfr} 142178825Sdfr 143233294Sstasvoid * 144233294Sstaslist_remove_tail(list_t *list) 145178825Sdfr{ 146178825Sdfr list_node_t *tail = list->list_head.list_prev; 147178825Sdfr if (tail == &list->list_head) 148178825Sdfr return (NULL); 149178825Sdfr list_remove_node(tail); 150178825Sdfr return (list_object(list, tail)); 151178825Sdfr} 152178825Sdfr 153178825Sdfrvoid * 154233294Sstaslist_head(list_t *list) 155178825Sdfr{ 156178825Sdfr if (list_empty(list)) 157178825Sdfr return (NULL); 158178825Sdfr return (list_object(list, list->list_head.list_next)); 159178825Sdfr} 160178825Sdfr 161178825Sdfrvoid * 162233294Sstaslist_tail(list_t *list) 163233294Sstas{ 164233294Sstas if (list_empty(list)) 165233294Sstas return (NULL); 166178825Sdfr return (list_object(list, list->list_head.list_prev)); 167178825Sdfr} 168178825Sdfr 169178825Sdfrvoid * 170178825Sdfrlist_next(list_t *list, void *object) 171178825Sdfr{ 172178825Sdfr list_node_t *node = list_d2l(list, object); 173178825Sdfr 174178825Sdfr if (node->list_next != &list->list_head) 175178825Sdfr return (list_object(list, node->list_next)); 176178825Sdfr 177178825Sdfr return (NULL); 178178825Sdfr} 179178825Sdfr 180178825Sdfrvoid * 181178825Sdfrlist_prev(list_t *list, void *object) 182178825Sdfr{ 183178825Sdfr list_node_t *node = list_d2l(list, object); 184178825Sdfr 185178825Sdfr if (node->list_prev != &list->list_head) 186178825Sdfr return (list_object(list, node->list_prev)); 187178825Sdfr 188178825Sdfr return (NULL); 189178825Sdfr} 190178825Sdfr 191178825Sdfr/* 192178825Sdfr * Insert src list after dst list. Empty src list thereafter. 193178825Sdfr */ 194178825Sdfrvoid 195178825Sdfrlist_move_tail(list_t *dst, list_t *src) 196178825Sdfr{ 197178825Sdfr list_node_t *dstnode = &dst->list_head; 198178825Sdfr list_node_t *srcnode = &src->list_head; 199178825Sdfr 200178825Sdfr ASSERT(dst->list_size == src->list_size); 201178825Sdfr ASSERT(dst->list_offset == src->list_offset); 202178825Sdfr 203178825Sdfr if (list_empty(src)) 204178825Sdfr return; 205178825Sdfr 206178825Sdfr dstnode->list_prev->list_next = srcnode->list_next; 207178825Sdfr srcnode->list_next->list_prev = dstnode->list_prev; 208178825Sdfr dstnode->list_prev = srcnode->list_prev; 209178825Sdfr srcnode->list_prev->list_next = dstnode; 210178825Sdfr 211178825Sdfr /* empty src list */ 212178825Sdfr srcnode->list_next = srcnode->list_prev = srcnode; 213178825Sdfr} 214178825Sdfr 215178825Sdfrvoid 216178825Sdfrlist_link_replace(list_node_t *lold, list_node_t *lnew) 217178825Sdfr{ 218178825Sdfr ASSERT(list_link_active(lold)); 219178825Sdfr ASSERT(!list_link_active(lnew)); 220233294Sstas 221178825Sdfr lnew->list_next = lold->list_next; 222178825Sdfr lnew->list_prev = lold->list_prev; 223178825Sdfr lold->list_prev->list_next = lnew; 224178825Sdfr lold->list_next->list_prev = lnew; 225178825Sdfr lold->list_next = lold->list_prev = NULL; 226178825Sdfr} 227178825Sdfr 228178825Sdfrvoid 229178825Sdfrlist_link_init(list_node_t *link) 230178825Sdfr{ 231178825Sdfr link->list_next = NULL; 232178825Sdfr link->list_prev = NULL; 233178825Sdfr} 234178825Sdfr 235178825Sdfrint 236178825Sdfrlist_link_active(list_node_t *link) 237178825Sdfr{ 238178825Sdfr return (link->list_next != NULL); 239178825Sdfr} 240178825Sdfr 241178825Sdfrint 242178825Sdfrlist_is_empty(list_t *list) 243178825Sdfr{ 244178825Sdfr return (list_empty(list)); 245178825Sdfr} 246178825Sdfr