![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to list.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to list.h CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1 root 1: /*
2: * Copyright (c) 2009, 2010 Richard Braun.
3: * All rights reserved.
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: *
14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: *
25: *
26: * Simple doubly-linked list.
27: */
28:
29: #ifndef _KERN_LIST_H
30: #define _KERN_LIST_H
31:
32: #include <stddef.h>
33: #include <sys/types.h>
1.1.1.2 ! root 34: #include <kern/macros.h>
1.1 root 35:
36: /*
37: * Structure used as both head and node.
38: *
39: * This implementation relies on using the same type for both heads and nodes.
40: *
41: * It is recommended to encode the use of struct list variables in their names,
42: * e.g. struct list free_list or struct list free_objects is a good hint for a
43: * list of free objects. A declaration like struct list free_node clearly
44: * indicates it is used as part of a node in the free list.
45: */
46: struct list {
47: struct list *prev;
48: struct list *next;
49: };
50:
51: /*
52: * Static list initializer.
53: */
54: #define LIST_INITIALIZER(list) { &(list), &(list) }
55:
56: /*
57: * Initialize a list.
58: */
59: static inline void list_init(struct list *list)
60: {
61: list->prev = list;
62: list->next = list;
63: }
64:
65: /*
66: * Initialize a list node.
67: *
68: * An entry is in no list when its node members point to NULL.
69: */
70: static inline void list_node_init(struct list *node)
71: {
72: node->prev = NULL;
73: node->next = NULL;
74: }
75:
76: /*
77: * Return true if node is in no list.
78: */
79: static inline int list_node_unlinked(const struct list *node)
80: {
81: return node->prev == NULL;
82: }
83:
84: /*
85: * Macro that evaluates to the address of the structure containing the
86: * given node based on the given type and member.
87: */
88: #define list_entry(node, type, member) structof(node, type, member)
89:
90: /*
91: * Return the first node of a list.
92: */
93: static inline struct list * list_first(const struct list *list)
94: {
95: return list->next;
96: }
97:
98: /*
99: * Return the last node of a list.
100: */
101: static inline struct list * list_last(const struct list *list)
102: {
103: return list->prev;
104: }
105:
106: /*
107: * Return the node next to the given node.
108: */
109: static inline struct list * list_next(const struct list *node)
110: {
111: return node->next;
112: }
113:
114: /*
115: * Return the node previous to the given node.
116: */
117: static inline struct list * list_prev(const struct list *node)
118: {
119: return node->prev;
120: }
121:
122: /*
123: * Get the first entry of a list.
124: */
125: #define list_first_entry(list, type, member) \
126: list_entry(list_first(list), type, member)
127:
128: /*
129: * Get the last entry of a list.
130: */
131: #define list_last_entry(list, type, member) \
132: list_entry(list_last(list), type, member)
133:
134: /*
135: * Return true if node is after the last or before the first node of the list.
136: */
137: static inline int list_end(const struct list *list, const struct list *node)
138: {
139: return list == node;
140: }
141:
142: /*
143: * Return true if list is empty.
144: */
145: static inline int list_empty(const struct list *list)
146: {
147: return list == list->next;
148: }
149:
150: /*
151: * Return true if list contains exactly one node.
152: */
153: static inline int list_singular(const struct list *list)
154: {
155: return (list != list->next) && (list->next == list->prev);
156: }
157:
158: /*
159: * Split list2 by moving its nodes up to (but not including) the given
160: * node into list1 (which can be in a stale state).
161: *
162: * If list2 is empty, or node is list2 or list2->next, nothing is done.
163: */
164: static inline void list_split(struct list *list1, struct list *list2,
165: struct list *node)
166: {
167: if (list_empty(list2) || (list2->next == node) || list_end(list2, node))
168: return;
169:
170: list1->next = list2->next;
171: list1->next->prev = list1;
172:
173: list1->prev = node->prev;
174: node->prev->next = list1;
175:
176: list2->next = node;
177: node->prev = list2;
178: }
179:
180: /*
181: * Append the nodes of list2 at the end of list1.
182: *
183: * After completion, list2 is stale.
184: */
185: static inline void list_concat(struct list *list1, const struct list *list2)
186: {
187: struct list *last1, *first2, *last2;
188:
189: if (list_empty(list2))
190: return;
191:
192: last1 = list1->prev;
193: first2 = list2->next;
194: last2 = list2->prev;
195:
196: last1->next = first2;
197: first2->prev = last1;
198:
199: last2->next = list1;
200: list1->prev = last2;
201: }
202:
203: /*
204: * Set the new head of a list.
205: *
206: * This function is an optimized version of :
207: * list_init(&new_list);
208: * list_concat(&new_list, &old_list);
209: *
210: * After completion, old_head is stale.
211: */
212: static inline void list_set_head(struct list *new_head,
213: const struct list *old_head)
214: {
215: if (list_empty(old_head)) {
216: list_init(new_head);
217: return;
218: }
219:
220: *new_head = *old_head;
221: new_head->next->prev = new_head;
222: new_head->prev->next = new_head;
223: }
224:
225: /*
226: * Add a node between two nodes.
227: */
228: static inline void list_add(struct list *prev, struct list *next,
229: struct list *node)
230: {
231: next->prev = node;
232: node->next = next;
233:
234: prev->next = node;
235: node->prev = prev;
236: }
237:
238: /*
239: * Insert a node at the head of a list.
240: */
241: static inline void list_insert_head(struct list *list, struct list *node)
242: {
243: list_add(list, list->next, node);
244: }
245:
246: /*
247: * Insert a node at the tail of a list.
248: */
249: static inline void list_insert_tail(struct list *list, struct list *node)
250: {
251: list_add(list->prev, list, node);
252: }
253:
254: /*
255: * Insert a node before another node.
256: */
257: static inline void list_insert_before(struct list *next, struct list *node)
258: {
259: list_add(next->prev, next, node);
260: }
261:
262: /*
263: * Insert a node after another node.
264: */
265: static inline void list_insert_after(struct list *prev, struct list *node)
266: {
267: list_add(prev, prev->next, node);
268: }
269:
270: /*
271: * Remove a node from a list.
272: *
273: * After completion, the node is stale.
274: */
275: static inline void list_remove(struct list *node)
276: {
277: node->prev->next = node->next;
278: node->next->prev = node->prev;
279: }
280:
281: /*
282: * Forge a loop to process all nodes of a list.
283: *
284: * The node must not be altered during the loop.
285: */
286: #define list_for_each(list, node) \
287: for (node = list_first(list); \
288: !list_end(list, node); \
289: node = list_next(node))
290:
291: /*
292: * Forge a loop to process all nodes of a list.
293: */
294: #define list_for_each_safe(list, node, tmp) \
295: for (node = list_first(list), tmp = list_next(node); \
296: !list_end(list, node); \
297: node = tmp, tmp = list_next(node))
298:
299: /*
300: * Version of list_for_each() that processes nodes backward.
301: */
302: #define list_for_each_reverse(list, node) \
303: for (node = list_last(list); \
304: !list_end(list, node); \
305: node = list_prev(node))
306:
307: /*
308: * Version of list_for_each_safe() that processes nodes backward.
309: */
310: #define list_for_each_reverse_safe(list, node, tmp) \
311: for (node = list_last(list), tmp = list_prev(node); \
312: !list_end(list, node); \
313: node = tmp, tmp = list_prev(node))
314:
315: /*
316: * Forge a loop to process all entries of a list.
317: *
318: * The entry node must not be altered during the loop.
319: */
320: #define list_for_each_entry(list, entry, member) \
321: for (entry = list_entry(list_first(list), typeof(*entry), member); \
322: !list_end(list, &entry->member); \
323: entry = list_entry(list_next(&entry->member), typeof(*entry), \
324: member))
325:
326: /*
327: * Forge a loop to process all entries of a list.
328: */
329: #define list_for_each_entry_safe(list, entry, tmp, member) \
330: for (entry = list_entry(list_first(list), typeof(*entry), member), \
331: tmp = list_entry(list_next(&entry->member), typeof(*entry), \
332: member); \
333: !list_end(list, &entry->member); \
334: entry = tmp, tmp = list_entry(list_next(&entry->member), \
335: typeof(*entry), member))
336:
337: /*
338: * Version of list_for_each_entry() that processes entries backward.
339: */
340: #define list_for_each_entry_reverse(list, entry, member) \
341: for (entry = list_entry(list_last(list), typeof(*entry), member); \
342: !list_end(list, &entry->member); \
343: entry = list_entry(list_prev(&entry->member), typeof(*entry), \
344: member))
345:
346: /*
347: * Version of list_for_each_entry_safe() that processes entries backward.
348: */
349: #define list_for_each_entry_reverse_safe(list, entry, tmp, member) \
350: for (entry = list_entry(list_last(list), typeof(*entry), member), \
351: tmp = list_entry(list_prev(&entry->member), typeof(*entry), \
352: member); \
353: !list_end(list, &entry->member); \
354: entry = tmp, tmp = list_entry(list_prev(&entry->member), \
355: typeof(*entry), member))
356:
357: #endif /* _KERN_LIST_H */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.