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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27 #pragma ident "%Z%%M% %I% %E% SMI" 28 29 /* 30 * Embedded Linked Lists 31 * 32 * Simple doubly-linked list implementation. This implementation assumes that 33 * each list element contains an embedded fmd_list_t (previous and next 34 * pointers), which is typically the first member of the element struct. 35 * An additional fmd_list_t is used to store the head (l_next) and tail 36 * (l_prev) pointers. The current head and tail list elements have their 37 * previous and next pointers set to NULL, respectively. 38 * 39 * NOTE: The embeddable list code in this file intentionally provides no 40 * locking of any kind. The implementation of any list in fmd must provide 41 * an appropriate locking strategy to protect the list or to protect access 42 * to the embedded fmd_list_t inside of each list element to avoid corruption. 43 * Refer to comments in the source files that use fmd_list_t for lock details. 44 */ 45 46 #include <fmd_subr.h> 47 #include <fmd_list.h> 48 49 void 50 fmd_list_append(fmd_list_t *lp, void *new) 51 { 52 fmd_list_t *p = lp->l_prev; /* p = tail list element */ 53 fmd_list_t *q = new; /* q = new list element */ 54 55 lp->l_prev = q; 56 q->l_prev = p; 57 q->l_next = NULL; 58 59 if (p != NULL) { 60 ASSERT(p->l_next == NULL); 61 p->l_next = q; 62 } else { 63 ASSERT(lp->l_next == NULL); 64 lp->l_next = q; 65 } 66 } 67 68 void 69 fmd_list_prepend(fmd_list_t *lp, void *new) 70 { 71 fmd_list_t *p = new; /* p = new list element */ 72 fmd_list_t *q = lp->l_next; /* q = head list element */ 73 74 lp->l_next = p; 75 p->l_prev = NULL; 76 p->l_next = q; 77 78 if (q != NULL) { 79 ASSERT(q->l_prev == NULL); 80 q->l_prev = p; 81 } else { 82 ASSERT(lp->l_prev == NULL); 83 lp->l_prev = p; 84 } 85 } 86 87 void 88 fmd_list_insert_before(fmd_list_t *lp, void *before_me, void *new) 89 { 90 fmd_list_t *p = before_me; 91 fmd_list_t *q = new; 92 93 if (p == NULL || p->l_prev == NULL) { 94 fmd_list_prepend(lp, new); 95 return; 96 } 97 98 q->l_prev = p->l_prev; 99 q->l_next = p; 100 p->l_prev = q; 101 q->l_prev->l_next = q; 102 } 103 104 void 105 fmd_list_insert_after(fmd_list_t *lp, void *after_me, void *new) 106 { 107 fmd_list_t *p = after_me; 108 fmd_list_t *q = new; 109 110 if (p == NULL || p->l_next == NULL) { 111 fmd_list_append(lp, new); 112 return; 113 } 114 115 q->l_next = p->l_next; 116 q->l_prev = p; 117 p->l_next = q; 118 q->l_next->l_prev = q; 119 } 120 121 void 122 fmd_list_delete(fmd_list_t *lp, void *existing) 123 { 124 fmd_list_t *p = existing; 125 126 if (p->l_prev != NULL) 127 p->l_prev->l_next = p->l_next; 128 else 129 lp->l_next = p->l_next; 130 131 if (p->l_next != NULL) 132 p->l_next->l_prev = p->l_prev; 133 else 134 lp->l_prev = p->l_prev; 135 } 136