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 /* 28 * Embedded Linked Lists 29 * 30 * Simple doubly-linked list implementation. This implementation assumes that 31 * each list element contains an embedded fmd_list_t (previous and next 32 * pointers), which is typically the first member of the element struct. 33 * An additional fmd_list_t is used to store the head (l_next) and tail 34 * (l_prev) pointers. The current head and tail list elements have their 35 * previous and next pointers set to NULL, respectively. 36 * 37 * NOTE: The embeddable list code in this file intentionally provides no 38 * locking of any kind. The implementation of any list in fmd must provide 39 * an appropriate locking strategy to protect the list or to protect access 40 * to the embedded fmd_list_t inside of each list element to avoid corruption. 41 * Refer to comments in the source files that use fmd_list_t for lock details. 42 */ 43 44 #include <fmd_subr.h> 45 #include <fmd_list.h> 46 47 void 48 fmd_list_append(fmd_list_t *lp, void *new) 49 { 50 fmd_list_t *p = lp->l_prev; /* p = tail list element */ 51 fmd_list_t *q = new; /* q = new list element */ 52 53 lp->l_prev = q; 54 q->l_prev = p; 55 q->l_next = NULL; 56 57 if (p != NULL) { 58 ASSERT(p->l_next == NULL); 59 p->l_next = q; 60 } else { 61 ASSERT(lp->l_next == NULL); 62 lp->l_next = q; 63 } 64 } 65 66 void 67 fmd_list_prepend(fmd_list_t *lp, void *new) 68 { 69 fmd_list_t *p = new; /* p = new list element */ 70 fmd_list_t *q = lp->l_next; /* q = head list element */ 71 72 lp->l_next = p; 73 p->l_prev = NULL; 74 p->l_next = q; 75 76 if (q != NULL) { 77 ASSERT(q->l_prev == NULL); 78 q->l_prev = p; 79 } else { 80 ASSERT(lp->l_prev == NULL); 81 lp->l_prev = p; 82 } 83 } 84 85 void 86 fmd_list_insert_before(fmd_list_t *lp, void *before_me, void *new) 87 { 88 fmd_list_t *p = before_me; 89 fmd_list_t *q = new; 90 91 if (p == NULL || p->l_prev == NULL) { 92 fmd_list_prepend(lp, new); 93 return; 94 } 95 96 q->l_prev = p->l_prev; 97 q->l_next = p; 98 p->l_prev = q; 99 q->l_prev->l_next = q; 100 } 101 102 void 103 fmd_list_insert_after(fmd_list_t *lp, void *after_me, void *new) 104 { 105 fmd_list_t *p = after_me; 106 fmd_list_t *q = new; 107 108 if (p == NULL || p->l_next == NULL) { 109 fmd_list_append(lp, new); 110 return; 111 } 112 113 q->l_next = p->l_next; 114 q->l_prev = p; 115 p->l_next = q; 116 q->l_next->l_prev = q; 117 } 118 119 void 120 fmd_list_delete(fmd_list_t *lp, void *existing) 121 { 122 fmd_list_t *p = existing; 123 124 if (p->l_prev != NULL) 125 p->l_prev->l_next = p->l_next; 126 else 127 lp->l_next = p->l_next; 128 129 if (p->l_next != NULL) 130 p->l_next->l_prev = p->l_prev; 131 else 132 lp->l_prev = p->l_prev; 133 } 134