1168404Spjd/* 2168404Spjd * CDDL HEADER START 3168404Spjd * 4168404Spjd * The contents of this file are subject to the terms of the 5168404Spjd * Common Development and Distribution License (the "License"). 6168404Spjd * You may not use this file except in compliance with the License. 7168404Spjd * 8168404Spjd * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9168404Spjd * or http://www.opensolaris.org/os/licensing. 10168404Spjd * See the License for the specific language governing permissions 11168404Spjd * and limitations under the License. 12168404Spjd * 13168404Spjd * When distributing Covered Code, include this CDDL HEADER in each 14168404Spjd * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15168404Spjd * If applicable, add the following below this CDDL HEADER, with the 16168404Spjd * fields enclosed by brackets "[]" replaced with your own identifying 17168404Spjd * information: Portions Copyright [yyyy] [name of copyright owner] 18168404Spjd * 19168404Spjd * CDDL HEADER END 20168404Spjd */ 21168404Spjd/* 22185029Spjd * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 23168404Spjd * Use is subject to license terms. 24168404Spjd */ 25168404Spjd 26168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 27168404Spjd 28168404Spjd/* 29168404Spjd * Generic doubly-linked list implementation 30168404Spjd */ 31168404Spjd 32168404Spjd#include <sys/list.h> 33168404Spjd#include <sys/list_impl.h> 34168404Spjd#include <sys/types.h> 35168404Spjd#include <sys/sysmacros.h> 36168404Spjd#include <sys/debug.h> 37168404Spjd 38168404Spjd#define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset)) 39168404Spjd#define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset)) 40168404Spjd#define list_empty(a) ((a)->list_head.list_next == &(a)->list_head) 41168404Spjd 42168404Spjd#define list_insert_after_node(list, node, object) { \ 43168404Spjd list_node_t *lnew = list_d2l(list, object); \ 44185029Spjd lnew->list_prev = (node); \ 45185029Spjd lnew->list_next = (node)->list_next; \ 46185029Spjd (node)->list_next->list_prev = lnew; \ 47185029Spjd (node)->list_next = lnew; \ 48168404Spjd} 49168404Spjd 50168404Spjd#define list_insert_before_node(list, node, object) { \ 51168404Spjd list_node_t *lnew = list_d2l(list, object); \ 52185029Spjd lnew->list_next = (node); \ 53185029Spjd lnew->list_prev = (node)->list_prev; \ 54185029Spjd (node)->list_prev->list_next = lnew; \ 55185029Spjd (node)->list_prev = lnew; \ 56168404Spjd} 57168404Spjd 58185029Spjd#define list_remove_node(node) \ 59185029Spjd (node)->list_prev->list_next = (node)->list_next; \ 60185029Spjd (node)->list_next->list_prev = (node)->list_prev; \ 61185029Spjd (node)->list_next = (node)->list_prev = NULL 62185029Spjd 63168404Spjdvoid 64168404Spjdlist_create(list_t *list, size_t size, size_t offset) 65168404Spjd{ 66168404Spjd ASSERT(list); 67168404Spjd ASSERT(size > 0); 68168404Spjd ASSERT(size >= offset + sizeof (list_node_t)); 69168404Spjd 70168404Spjd list->list_size = size; 71168404Spjd list->list_offset = offset; 72168404Spjd list->list_head.list_next = list->list_head.list_prev = 73168404Spjd &list->list_head; 74168404Spjd} 75168404Spjd 76168404Spjdvoid 77168404Spjdlist_destroy(list_t *list) 78168404Spjd{ 79168404Spjd list_node_t *node = &list->list_head; 80168404Spjd 81168404Spjd ASSERT(list); 82168404Spjd ASSERT(list->list_head.list_next == node); 83168404Spjd ASSERT(list->list_head.list_prev == node); 84168404Spjd 85168404Spjd node->list_next = node->list_prev = NULL; 86168404Spjd} 87168404Spjd 88168404Spjdvoid 89168404Spjdlist_insert_after(list_t *list, void *object, void *nobject) 90168404Spjd{ 91185029Spjd if (object == NULL) { 92185029Spjd list_insert_head(list, nobject); 93185029Spjd } else { 94185029Spjd list_node_t *lold = list_d2l(list, object); 95185029Spjd list_insert_after_node(list, lold, nobject); 96185029Spjd } 97168404Spjd} 98168404Spjd 99168404Spjdvoid 100168404Spjdlist_insert_before(list_t *list, void *object, void *nobject) 101168404Spjd{ 102185029Spjd if (object == NULL) { 103185029Spjd list_insert_tail(list, nobject); 104185029Spjd } else { 105185029Spjd list_node_t *lold = list_d2l(list, object); 106185029Spjd list_insert_before_node(list, lold, nobject); 107185029Spjd } 108168404Spjd} 109168404Spjd 110168404Spjdvoid 111168404Spjdlist_insert_head(list_t *list, void *object) 112168404Spjd{ 113168404Spjd list_node_t *lold = &list->list_head; 114168404Spjd list_insert_after_node(list, lold, object); 115168404Spjd} 116168404Spjd 117168404Spjdvoid 118168404Spjdlist_insert_tail(list_t *list, void *object) 119168404Spjd{ 120168404Spjd list_node_t *lold = &list->list_head; 121168404Spjd list_insert_before_node(list, lold, object); 122168404Spjd} 123168404Spjd 124168404Spjdvoid 125168404Spjdlist_remove(list_t *list, void *object) 126168404Spjd{ 127168404Spjd list_node_t *lold = list_d2l(list, object); 128168404Spjd ASSERT(!list_empty(list)); 129185029Spjd ASSERT(lold->list_next != NULL); 130185029Spjd list_remove_node(lold); 131168404Spjd} 132168404Spjd 133168404Spjdvoid * 134185029Spjdlist_remove_head(list_t *list) 135185029Spjd{ 136185029Spjd list_node_t *head = list->list_head.list_next; 137185029Spjd if (head == &list->list_head) 138185029Spjd return (NULL); 139185029Spjd list_remove_node(head); 140185029Spjd return (list_object(list, head)); 141185029Spjd} 142185029Spjd 143185029Spjdvoid * 144185029Spjdlist_remove_tail(list_t *list) 145185029Spjd{ 146185029Spjd list_node_t *tail = list->list_head.list_prev; 147185029Spjd if (tail == &list->list_head) 148185029Spjd return (NULL); 149185029Spjd list_remove_node(tail); 150185029Spjd return (list_object(list, tail)); 151185029Spjd} 152185029Spjd 153185029Spjdvoid * 154168404Spjdlist_head(list_t *list) 155168404Spjd{ 156168404Spjd if (list_empty(list)) 157168404Spjd return (NULL); 158168404Spjd return (list_object(list, list->list_head.list_next)); 159168404Spjd} 160168404Spjd 161168404Spjdvoid * 162168404Spjdlist_tail(list_t *list) 163168404Spjd{ 164168404Spjd if (list_empty(list)) 165168404Spjd return (NULL); 166168404Spjd return (list_object(list, list->list_head.list_prev)); 167168404Spjd} 168168404Spjd 169168404Spjdvoid * 170168404Spjdlist_next(list_t *list, void *object) 171168404Spjd{ 172168404Spjd list_node_t *node = list_d2l(list, object); 173168404Spjd 174168404Spjd if (node->list_next != &list->list_head) 175168404Spjd return (list_object(list, node->list_next)); 176168404Spjd 177168404Spjd return (NULL); 178168404Spjd} 179168404Spjd 180168404Spjdvoid * 181168404Spjdlist_prev(list_t *list, void *object) 182168404Spjd{ 183168404Spjd list_node_t *node = list_d2l(list, object); 184168404Spjd 185168404Spjd if (node->list_prev != &list->list_head) 186168404Spjd return (list_object(list, node->list_prev)); 187168404Spjd 188168404Spjd return (NULL); 189168404Spjd} 190168404Spjd 191168404Spjd/* 192168404Spjd * Insert src list after dst list. Empty src list thereafter. 193168404Spjd */ 194168404Spjdvoid 195168404Spjdlist_move_tail(list_t *dst, list_t *src) 196168404Spjd{ 197168404Spjd list_node_t *dstnode = &dst->list_head; 198168404Spjd list_node_t *srcnode = &src->list_head; 199168404Spjd 200168404Spjd ASSERT(dst->list_size == src->list_size); 201168404Spjd ASSERT(dst->list_offset == src->list_offset); 202168404Spjd 203168404Spjd if (list_empty(src)) 204168404Spjd return; 205168404Spjd 206168404Spjd dstnode->list_prev->list_next = srcnode->list_next; 207168404Spjd srcnode->list_next->list_prev = dstnode->list_prev; 208168404Spjd dstnode->list_prev = srcnode->list_prev; 209168404Spjd srcnode->list_prev->list_next = dstnode; 210168404Spjd 211168404Spjd /* empty src list */ 212168404Spjd srcnode->list_next = srcnode->list_prev = srcnode; 213168404Spjd} 214168404Spjd 215185029Spjdvoid 216185029Spjdlist_link_replace(list_node_t *lold, list_node_t *lnew) 217185029Spjd{ 218185029Spjd ASSERT(list_link_active(lold)); 219185029Spjd ASSERT(!list_link_active(lnew)); 220185029Spjd 221185029Spjd lnew->list_next = lold->list_next; 222185029Spjd lnew->list_prev = lold->list_prev; 223185029Spjd lold->list_prev->list_next = lnew; 224185029Spjd lold->list_next->list_prev = lnew; 225185029Spjd lold->list_next = lold->list_prev = NULL; 226185029Spjd} 227185029Spjd 228185029Spjdvoid 229185029Spjdlist_link_init(list_node_t *link) 230185029Spjd{ 231185029Spjd link->list_next = NULL; 232185029Spjd link->list_prev = NULL; 233185029Spjd} 234185029Spjd 235168404Spjdint 236168404Spjdlist_link_active(list_node_t *link) 237168404Spjd{ 238168404Spjd return (link->list_next != NULL); 239168404Spjd} 240168404Spjd 241168404Spjdint 242168404Spjdlist_is_empty(list_t *list) 243168404Spjd{ 244168404Spjd return (list_empty(list)); 245168404Spjd} 246