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