78c302fa322fe6bc2dae2926e95e58189c10c944
[paraslash.git] / list.h
1 /*
2 * Copied from the Linux kernel source tree, version 2.6.13.
3 *
4 * Licensed under the GPL v2 as per the whole kernel source tree.
5 */
6
7 /** \file list.h Doubly linked list implementation. */
8
9 #include <stddef.h> /* offsetof */
10
11 /** Get the struct this entry is embedded in. */
12 #define container_of(ptr, type, member) ({ \
13 const typeof( ((type *)0)->member ) *__mptr = (ptr); \
14 (type *)( (char *)__mptr - offsetof(type,member) );})
15
16 /** A list head is just a pair of pointers. */
17 struct list_head {
18 /** Pointer to the next list entry. */
19 struct list_head *next;
20 /** Pointer to the previous list entry. */
21 struct list_head *prev;
22 };
23
24 /** Define an initialized list head. */
25 #define INITIALIZED_LIST_HEAD(name) struct list_head name = {&(name), &(name)}
26
27 /** This must be called before using any other list functions. */
28 static inline void init_list_head(struct list_head *head)
29 {
30 head->next = head;
31 head->prev = head;
32 }
33
34 /**
35 * Insert a new entry after the specified head.
36 *
37 * \param entry The new entry to add.
38 * \param head The list head to add it after.
39 *
40 * This is good for implementing stacks.
41 */
42 static inline void para_list_add(struct list_head *entry, struct list_head *head)
43 {
44 entry->prev = head;
45 entry->next = head->next;
46 head->next->prev = entry;
47 head->next = entry;
48 }
49
50 /**
51 * Insert a new entry before the specified head.
52 *
53 * \param entry The new entry to add.
54 * \param head list head to add it before.
55 *
56 * This is useful for implementing queues.
57 */
58 static inline void list_add_tail(struct list_head *entry, struct list_head *head)
59 {
60 entry->prev = head->prev;
61 entry->next = head;
62 head->prev->next = entry;
63 head->prev = entry;
64 }
65
66 /**
67 * Delete an entry from a list.
68 *
69 * \param entry The element to delete.
70 *
71 * The list entry is in an undefined state after this and \ref list_empty()
72 * does not return true.
73 */
74 static inline void list_del(struct list_head *entry)
75 {
76 entry->prev->next = entry->next;
77 entry->next->prev = entry->prev;
78 /*
79 * These non-NULL pointers result in page faults when dereferenced.
80 * This helps to catch bugs resulting from using deleted list heads.
81 */
82 entry->next = (void *)0x00100100;
83 entry->prev = (void *)0x00200200;
84 }
85
86 /**
87 * Delete an entry from one list and add it as another list's head.
88 *
89 * \param entry The entry to move.
90 * \param head The head that will precede our entry.
91 */
92 static inline void list_move(struct list_head *entry, struct list_head *head)
93 {
94 list_del(entry);
95 para_list_add(entry, head);
96 }
97
98 /**
99 * Test whether a list contains no entries.
100 *
101 * \param head The list to test.
102 */
103 static inline int list_empty(const struct list_head *head)
104 {
105 return head->next == head;
106 }
107
108 /**
109 * Test whether a list has just one entry.
110 *
111 * \param head The list to test.
112 */
113 static inline int list_is_singular(const struct list_head *head)
114 {
115 return !list_empty(head) && (head->next == head->prev);
116 }
117
118 /**
119 * Get the struct in which this entry is embedded in.
120 *
121 * \param ptr The list head pointer.
122 * \param type The type of containing structure.
123 * \param member The name of the list head member within the structure.
124 */
125 #define list_entry(ptr, type, member) container_of(ptr, type, member)
126
127 /**
128 * Iterate over a list.
129 *
130 * \param pos A struct pointer which serves as the iterator.
131 * \param head The head of the list.
132 * \param member The name of the list head member within the structure.
133 */
134 #define list_for_each_entry(pos, head, member) \
135 for (pos = list_entry((head)->next, typeof(*pos), member); \
136 &pos->member != (head); \
137 pos = list_entry(pos->member.next, typeof(*pos), member))
138
139 /**
140 * Iterate over list, safe against removal of list entry.
141 *
142 * \param pos The iterator struct pointer.
143 * \param n A second struct pointer which is used as temporary storage.
144 * \param head The head of the list.
145 * \param member The name of the list head member within the structure.
146 */
147 #define list_for_each_entry_safe(pos, n, head, member) \
148 for (pos = list_entry((head)->next, typeof(*pos), member), \
149 n = list_entry(pos->member.next, typeof(*pos), member); \
150 &pos->member != (head); \
151 pos = n, n = list_entry(n->member.next, typeof(*n), member))
152
153 /**
154 * Get the first element of a list.
155 *
156 * \param ptr The list head to take the element from.
157 * \param type The type of the struct this is embedded in.
158 * \param member The name of the list_struct within the struct.
159 *
160 * Note that the list is expected to be non-empty.
161 */
162 #define list_first_entry(ptr, type, member) \
163 list_entry((ptr)->next, type, member)