/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- threadlistnode_init
- threadlistnode_cleanup
- threadlist_init
- threadlist_cleanup
- threadlist_isempty
- threadlist_insertafternode
- threadlist_insertbeforenode
- threadlist_removenode
- threadlist_addhead
- threadlist_addtail
- threadlist_remhead
- threadlist_remtail
- threadlist_insertafter
- threadlist_insertbefore
- threadlist_remove
1 /*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2008, 2009
3 * The President and Fellows of Harvard College.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * Thread list functions, rather dull.
32 */
33
34 #include <types.h>
35 #include <lib.h>
36 #include <thread.h>
37 #include <threadlist.h>
38
39 void
40 threadlistnode_init(struct threadlistnode *tln, struct thread *t)
41 {
42 DEBUGASSERT(tln != NULL);
43 KASSERT(t != NULL);
44
45 tln->tln_next = NULL;
46 tln->tln_prev = NULL;
47 tln->tln_self = t;
48 }
49
50 void
51 threadlistnode_cleanup(struct threadlistnode *tln)
52 {
53 DEBUGASSERT(tln != NULL);
54
55 KASSERT(tln->tln_next == NULL);
56 KASSERT(tln->tln_prev == NULL);
57 KASSERT(tln->tln_self != NULL);
58 }
59
60 void
61 threadlist_init(struct threadlist *tl)
62 {
63 DEBUGASSERT(tl != NULL);
64
65 tl->tl_head.tln_next = &tl->tl_tail;
66 tl->tl_head.tln_prev = NULL;
67 tl->tl_tail.tln_next = NULL;
68 tl->tl_tail.tln_prev = &tl->tl_head;
69 tl->tl_head.tln_self = NULL;
70 tl->tl_tail.tln_self = NULL;
71 tl->tl_count = 0;
72 }
73
74 void
75 threadlist_cleanup(struct threadlist *tl)
76 {
77 DEBUGASSERT(tl != NULL);
78 DEBUGASSERT(tl->tl_head.tln_next == &tl->tl_tail);
79 DEBUGASSERT(tl->tl_head.tln_prev == NULL);
80 DEBUGASSERT(tl->tl_tail.tln_next == NULL);
81 DEBUGASSERT(tl->tl_tail.tln_prev == &tl->tl_head);
82 DEBUGASSERT(tl->tl_head.tln_self == NULL);
83 DEBUGASSERT(tl->tl_tail.tln_self == NULL);
84
85 KASSERT(threadlist_isempty(tl));
86 KASSERT(tl->tl_count == 0);
87
88 /* nothing (else) to do */
89 }
90
91 bool
92 threadlist_isempty(struct threadlist *tl)
93 {
94 DEBUGASSERT(tl != NULL);
95
96 return (tl->tl_count == 0);
97 }
98
99 ////////////////////////////////////////////////////////////
100 // internal
101
102 /*
103 * Do insertion. Doesn't update tl_count.
104 */
105 static
106 void
107 threadlist_insertafternode(struct threadlistnode *onlist, struct thread *t)
108 {
109 struct threadlistnode *addee;
110
111 addee = &t->t_listnode;
112
113 DEBUGASSERT(addee->tln_prev == NULL);
114 DEBUGASSERT(addee->tln_next == NULL);
115
116 addee->tln_prev = onlist;
117 addee->tln_next = onlist->tln_next;
118 addee->tln_prev->tln_next = addee;
119 addee->tln_next->tln_prev = addee;
120 }
121
122 /*
123 * Do insertion. Doesn't update tl_count.
124 */
125 static
126 void
127 threadlist_insertbeforenode(struct thread *t, struct threadlistnode *onlist)
128 {
129 struct threadlistnode *addee;
130
131 addee = &t->t_listnode;
132
133 DEBUGASSERT(addee->tln_prev == NULL);
134 DEBUGASSERT(addee->tln_next == NULL);
135
136 addee->tln_prev = onlist->tln_prev;
137 addee->tln_next = onlist;
138 addee->tln_prev->tln_next = addee;
139 addee->tln_next->tln_prev = addee;
140 }
141
142 /*
143 * Do removal. Doesn't update tl_count.
144 */
145 static
146 void
147 threadlist_removenode(struct threadlistnode *tln)
148 {
149 DEBUGASSERT(tln != NULL);
150 DEBUGASSERT(tln->tln_prev != NULL);
151 DEBUGASSERT(tln->tln_next != NULL);
152
153 tln->tln_prev->tln_next = tln->tln_next;
154 tln->tln_next->tln_prev = tln->tln_prev;
155 tln->tln_prev = NULL;
156 tln->tln_next = NULL;
157 }
158
159 ////////////////////////////////////////////////////////////
160 // public
161
162 void
163 threadlist_addhead(struct threadlist *tl, struct thread *t)
164 {
165 DEBUGASSERT(tl != NULL);
166 DEBUGASSERT(t != NULL);
167
168 threadlist_insertafternode(&tl->tl_head, t);
169 tl->tl_count++;
170 }
171
172 void
173 threadlist_addtail(struct threadlist *tl, struct thread *t)
174 {
175 DEBUGASSERT(tl != NULL);
176 DEBUGASSERT(t != NULL);
177
178 threadlist_insertbeforenode(t, &tl->tl_tail);
179 tl->tl_count++;
180 }
181
182 struct thread *
183 threadlist_remhead(struct threadlist *tl)
184 {
185 struct threadlistnode *tln;
186
187 DEBUGASSERT(tl != NULL);
188
189 tln = tl->tl_head.tln_next;
190 if (tln->tln_next == NULL) {
191 /* list was empty */
192 return NULL;
193 }
194 threadlist_removenode(tln);
195 DEBUGASSERT(tl->tl_count > 0);
196 tl->tl_count--;
197 return tln->tln_self;
198 }
199
200 struct thread *
201 threadlist_remtail(struct threadlist *tl)
202 {
203 struct threadlistnode *tln;
204
205 DEBUGASSERT(tl != NULL);
206
207 tln = tl->tl_tail.tln_prev;
208 if (tln->tln_prev == NULL) {
209 /* list was empty */
210 return NULL;
211 }
212 threadlist_removenode(tln);
213 DEBUGASSERT(tl->tl_count > 0);
214 tl->tl_count--;
215 return tln->tln_self;
216 }
217
218 void
219 threadlist_insertafter(struct threadlist *tl,
220 struct thread *onlist, struct thread *addee)
221 {
222 threadlist_insertafternode(&onlist->t_listnode, addee);
223 tl->tl_count++;
224 }
225
226 void
227 threadlist_insertbefore(struct threadlist *tl,
228 struct thread *addee, struct thread *onlist)
229 {
230 threadlist_insertbeforenode(addee, &onlist->t_listnode);
231 tl->tl_count++;
232 }
233
234 void
235 threadlist_remove(struct threadlist *tl, struct thread *t)
236 {
237 threadlist_removenode(&t->t_listnode);
238 DEBUGASSERT(tl->tl_count > 0);
239 tl->tl_count--;
240 }