![[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>
34:
35: #define structof(ptr, type, member) \
36: ((type *)((char *)ptr - offsetof(type, member)))
37:
38: /*
39: * Structure used as both head and node.
40: *
41: * This implementation relies on using the same type for both heads and nodes.
42: *
43: * It is recommended to encode the use of struct list variables in their names,
44: * e.g. struct list free_list or struct list free_objects is a good hint for a
45: * list of free objects. A declaration like struct list free_node clearly
46: * indicates it is used as part of a node in the free list.
47: */
48: struct list {
49: struct list *prev;
50: struct list *next;
51: };
52:
53: /*
54: * Static list initializer.
55: */
56: #define LIST_INITIALIZER(list) { &(list), &(list) }
57:
58: /*
59: * Initialize a list.
60: */
61: static inline void list_init(struct list *list)
62: {
63: list->prev = list;
64: list->next = list;
65: }
66:
67: /*
68: * Initialize a list node.
69: *
70: * An entry is in no list when its node members point to NULL.
71: */
72: static inline void list_node_init(struct list *node)
73: {
74: node->prev = NULL;
75: node->next = NULL;
76: }
77:
78: /*
79: * Return true if node is in no list.
80: */
81: static inline int list_node_unlinked(const struct list *node)
82: {
83: return node->prev == NULL;
84: }
85:
86: /*
87: * Macro that evaluates to the address of the structure containing the
88: * given node based on the given type and member.
89: */
90: #define list_entry(node, type, member) structof(node, type, member)
91:
92: /*
93: * Return the first node of a list.
94: */
95: static inline struct list * list_first(const struct list *list)
96: {
97: return list->next;
98: }
99:
100: /*
101: * Return the last node of a list.
102: */
103: static inline struct list * list_last(const struct list *list)
104: {
105: return list->prev;
106: }
107:
108: /*
109: * Return the node next to the given node.
110: */
111: static inline struct list * list_next(const struct list *node)
112: {
113: return node->next;
114: }
115:
116: /*
117: * Return the node previous to the given node.
118: */
119: static inline struct list * list_prev(const struct list *node)
120: {
121: return node->prev;
122: }
123:
124: /*
125: * Get the first entry of a list.
126: */
127: #define list_first_entry(list, type, member) \
128: list_entry(list_first(list), type, member)
129:
130: /*
131: * Get the last entry of a list.
132: */
133: #define list_last_entry(list, type, member) \
134: list_entry(list_last(list), type, member)
135:
136: /*
137: * Return true if node is after the last or before the first node of the list.
138: */
139: static inline int list_end(const struct list *list, const struct list *node)
140: {
141: return list == node;
142: }
143:
144: /*
145: * Return true if list is empty.
146: */
147: static inline int list_empty(const struct list *list)
148: {
149: return list == list->next;
150: }
151:
152: /*
153: * Return true if list contains exactly one node.
154: */
155: static inline int list_singular(const struct list *list)
156: {
157: return (list != list->next) && (list->next == list->prev);
158: }
159:
160: /*
161: * Split list2 by moving its nodes up to (but not including) the given
162: * node into list1 (which can be in a stale state).
163: *
164: * If list2 is empty, or node is list2 or list2->next, nothing is done.
165: */
166: static inline void list_split(struct list *list1, struct list *list2,
167: struct list *node)
168: {
169: if (list_empty(list2) || (list2->next == node) || list_end(list2, node))
170: return;
171:
172: list1->next = list2->next;
173: list1->next->prev = list1;
174:
175: list1->prev = node->prev;
176: node->prev->next = list1;
177:
178: list2->next = node;
179: node->prev = list2;
180: }
181:
182: /*
183: * Append the nodes of list2 at the end of list1.
184: *
185: * After completion, list2 is stale.
186: */
187: static inline void list_concat(struct list *list1, const struct list *list2)
188: {
189: struct list *last1, *first2, *last2;
190:
191: if (list_empty(list2))
192: return;
193:
194: last1 = list1->prev;
195: first2 = list2->next;
196: last2 = list2->prev;
197:
198: last1->next = first2;
199: first2->prev = last1;
200:
201: last2->next = list1;
202: list1->prev = last2;
203: }
204:
205: /*
206: * Set the new head of a list.
207: *
208: * This function is an optimized version of :
209: * list_init(&new_list);
210: * list_concat(&new_list, &old_list);
211: *
212: * After completion, old_head is stale.
213: */
214: static inline void list_set_head(struct list *new_head,
215: const struct list *old_head)
216: {
217: if (list_empty(old_head)) {
218: list_init(new_head);
219: return;
220: }
221:
222: *new_head = *old_head;
223: new_head->next->prev = new_head;
224: new_head->prev->next = new_head;
225: }
226:
227: /*
228: * Add a node between two nodes.
229: */
230: static inline void list_add(struct list *prev, struct list *next,
231: struct list *node)
232: {
233: next->prev = node;
234: node->next = next;
235:
236: prev->next = node;
237: node->prev = prev;
238: }
239:
240: /*
241: * Insert a node at the head of a list.
242: */
243: static inline void list_insert_head(struct list *list, struct list *node)
244: {
245: list_add(list, list->next, node);
246: }
247:
248: /*
249: * Insert a node at the tail of a list.
250: */
251: static inline void list_insert_tail(struct list *list, struct list *node)
252: {
253: list_add(list->prev, list, node);
254: }
255:
256: /*
257: * Insert a node before another node.
258: */
259: static inline void list_insert_before(struct list *next, struct list *node)
260: {
261: list_add(next->prev, next, node);
262: }
263:
264: /*
265: * Insert a node after another node.
266: */
267: static inline void list_insert_after(struct list *prev, struct list *node)
268: {
269: list_add(prev, prev->next, node);
270: }
271:
272: /*
273: * Remove a node from a list.
274: *
275: * After completion, the node is stale.
276: */
277: static inline void list_remove(struct list *node)
278: {
279: node->prev->next = node->next;
280: node->next->prev = node->prev;
281: }
282:
283: /*
284: * Forge a loop to process all nodes of a list.
285: *
286: * The node must not be altered during the loop.
287: */
288: #define list_for_each(list, node) \
289: for (node = list_first(list); \
290: !list_end(list, node); \
291: node = list_next(node))
292:
293: /*
294: * Forge a loop to process all nodes of a list.
295: */
296: #define list_for_each_safe(list, node, tmp) \
297: for (node = list_first(list), tmp = list_next(node); \
298: !list_end(list, node); \
299: node = tmp, tmp = list_next(node))
300:
301: /*
302: * Version of list_for_each() that processes nodes backward.
303: */
304: #define list_for_each_reverse(list, node) \
305: for (node = list_last(list); \
306: !list_end(list, node); \
307: node = list_prev(node))
308:
309: /*
310: * Version of list_for_each_safe() that processes nodes backward.
311: */
312: #define list_for_each_reverse_safe(list, node, tmp) \
313: for (node = list_last(list), tmp = list_prev(node); \
314: !list_end(list, node); \
315: node = tmp, tmp = list_prev(node))
316:
317: /*
318: * Forge a loop to process all entries of a list.
319: *
320: * The entry node must not be altered during the loop.
321: */
322: #define list_for_each_entry(list, entry, member) \
323: for (entry = list_entry(list_first(list), typeof(*entry), member); \
324: !list_end(list, &entry->member); \
325: entry = list_entry(list_next(&entry->member), typeof(*entry), \
326: member))
327:
328: /*
329: * Forge a loop to process all entries of a list.
330: */
331: #define list_for_each_entry_safe(list, entry, tmp, member) \
332: for (entry = list_entry(list_first(list), typeof(*entry), member), \
333: tmp = list_entry(list_next(&entry->member), typeof(*entry), \
334: member); \
335: !list_end(list, &entry->member); \
336: entry = tmp, tmp = list_entry(list_next(&entry->member), \
337: typeof(*entry), member))
338:
339: /*
340: * Version of list_for_each_entry() that processes entries backward.
341: */
342: #define list_for_each_entry_reverse(list, entry, member) \
343: for (entry = list_entry(list_last(list), typeof(*entry), member); \
344: !list_end(list, &entry->member); \
345: entry = list_entry(list_prev(&entry->member), typeof(*entry), \
346: member))
347:
348: /*
349: * Version of list_for_each_entry_safe() that processes entries backward.
350: */
351: #define list_for_each_entry_reverse_safe(list, entry, tmp, member) \
352: for (entry = list_entry(list_last(list), typeof(*entry), member), \
353: tmp = list_entry(list_prev(&entry->member), typeof(*entry), \
354: member); \
355: !list_end(list, &entry->member); \
356: entry = tmp, tmp = list_entry(list_prev(&entry->member), \
357: typeof(*entry), member))
358:
359: #endif /* _KERN_LIST_H */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.