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