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