Statistics
| Branch: | Revision:

peerstreamer-src / src / list.h @ 58fb2cdc

History | View | Annotate | Download (6.57 KB)

1
#ifndef __LIST_H
2
#define __LIST_H
3

    
4
/* This file is from Linux Kernel (include/linux/list.h) 
5
 * and modified by simply removing hardware prefetching of list items. 
6
 * Here by copyright, credits attributed to wherever they belong.
7
 * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu)
8
 */
9

    
10
/*
11
 * Simple doubly linked list implementation.
12
 *
13
 * Some of the internal functions ("__xxx") are useful when
14
 * manipulating whole lists rather than single entries, as
15
 * sometimes we already know the next/prev entries and we can
16
 * generate better code by using them directly rather than
17
 * using the generic single-entry routines.
18
 */
19

    
20
struct list_head {
21
        struct list_head *next, *prev;
22
};
23

    
24
#define LIST_HEAD_INIT(name) { &(name), &(name) }
25

    
26
#define LIST_HEAD(name) \
27
        struct list_head name = LIST_HEAD_INIT(name)
28

    
29
#define INIT_LIST_HEAD(ptr) do { \
30
        (ptr)->next = (ptr); (ptr)->prev = (ptr); \
31
} while (0)
32

    
33
/*
34
 * Insert a new entry between two known consecutive entries. 
35
 *
36
 * This is only for internal list manipulation where we know
37
 * the prev/next entries already!
38
 */
39
static inline void __list_add(struct list_head *new,
40
                              struct list_head *prev,
41
                              struct list_head *next)
42
{
43
        next->prev = new;
44
        new->next = next;
45
        new->prev = prev;
46
        prev->next = new;
47
}
48

    
49
/**
50
 * list_add - add a new entry
51
 * @new: new entry to be added
52
 * @head: list head to add it after
53
 *
54
 * Insert a new entry after the specified head.
55
 * This is good for implementing stacks.
56
 */
57
static inline void list_add(struct list_head *new, struct list_head *head)
58
{
59
        __list_add(new, head, head->next);
60
}
61

    
62
/**
63
 * list_add_tail - add a new entry
64
 * @new: new entry to be added
65
 * @head: list head to add it before
66
 *
67
 * Insert a new entry before the specified head.
68
 * This is useful for implementing queues.
69
 */
70
static inline void list_add_tail(struct list_head *new, struct list_head *head)
71
{
72
        __list_add(new, head->prev, head);
73
}
74

    
75
/*
76
 * Delete a list entry by making the prev/next entries
77
 * point to each other.
78
 *
79
 * This is only for internal list manipulation where we know
80
 * the prev/next entries already!
81
 */
82
static inline void __list_del(struct list_head *prev, struct list_head *next)
83
{
84
        next->prev = prev;
85
        prev->next = next;
86
}
87

    
88
/**
89
 * list_del - deletes entry from list.
90
 * @entry: the element to delete from the list.
91
 * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
92
 */
93
static inline void list_del(struct list_head *entry)
94
{
95
        __list_del(entry->prev, entry->next);
96
        entry->next = (void *) 0;
97
        entry->prev = (void *) 0;
98
}
99

    
100
/**
101
 * list_del_init - deletes entry from list and reinitialize it.
102
 * @entry: the element to delete from the list.
103
 */
104
static inline void list_del_init(struct list_head *entry)
105
{
106
        __list_del(entry->prev, entry->next);
107
        INIT_LIST_HEAD(entry); 
108
}
109

    
110
/**
111
 * list_move - delete from one list and add as another's head
112
 * @list: the entry to move
113
 * @head: the head that will precede our entry
114
 */
115
static inline void list_move(struct list_head *list, struct list_head *head)
116
{
117
        __list_del(list->prev, list->next);
118
        list_add(list, head);
119
}
120

    
121
/**
122
 * list_move_tail - delete from one list and add as another's tail
123
 * @list: the entry to move
124
 * @head: the head that will follow our entry
125
 */
126
static inline void list_move_tail(struct list_head *list,
127
                                  struct list_head *head)
128
{
129
        __list_del(list->prev, list->next);
130
        list_add_tail(list, head);
131
}
132

    
133
/**
134
 * list_empty - tests whether a list is empty
135
 * @head: the list to test.
136
 */
137
static inline int list_empty(struct list_head *head)
138
{
139
        return head->next == head;
140
}
141

    
142
static inline void __list_splice(struct list_head *list,
143
                                 struct list_head *head)
144
{
145
        struct list_head *first = list->next;
146
        struct list_head *last = list->prev;
147
        struct list_head *at = head->next;
148

    
149
        first->prev = head;
150
        head->next = first;
151

    
152
        last->next = at;
153
        at->prev = last;
154
}
155

    
156
/**
157
 * list_splice - join two lists
158
 * @list: the new list to add.
159
 * @head: the place to add it in the first list.
160
 */
161
static inline void list_splice(struct list_head *list, struct list_head *head)
162
{
163
        if (!list_empty(list))
164
                __list_splice(list, head);
165
}
166

    
167
/**
168
 * list_splice_init - join two lists and reinitialise the emptied list.
169
 * @list: the new list to add.
170
 * @head: the place to add it in the first list.
171
 *
172
 * The list at @list is reinitialised
173
 */
174
static inline void list_splice_init(struct list_head *list,
175
                                    struct list_head *head)
176
{
177
        if (!list_empty(list)) {
178
                __list_splice(list, head);
179
                INIT_LIST_HEAD(list);
180
        }
181
}
182

    
183
/**
184
 * list_entry - get the struct for this entry
185
 * @ptr:        the &struct list_head pointer.
186
 * @type:        the type of the struct this is embedded in.
187
 * @member:        the name of the list_struct within the struct.
188
 */
189
#define list_entry(ptr, type, member) \
190
        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
191

    
192
/**
193
 * list_for_each        -        iterate over a list
194
 * @pos:        the &struct list_head to use as a loop counter.
195
 * @head:        the head for your list.
196
 */
197
#define list_for_each(pos, head) \
198
        for (pos = (head)->next; pos != (head); \
199
                pos = pos->next)
200
/**
201
 * list_for_each_prev        -        iterate over a list backwards
202
 * @pos:        the &struct list_head to use as a loop counter.
203
 * @head:        the head for your list.
204
 */
205
#define list_for_each_prev(pos, head) \
206
        for (pos = (head)->prev; pos != (head); \
207
                pos = pos->prev)
208
                
209
/**
210
 * list_for_each_safe        -        iterate over a list safe against removal of list entry
211
 * @pos:        the &struct list_head to use as a loop counter.
212
 * @n:                another &struct list_head to use as temporary storage
213
 * @head:        the head for your list.
214
 */
215
#define list_for_each_safe(pos, n, head) \
216
        for (pos = (head)->next, n = pos->next; pos != (head); \
217
                pos = n, n = pos->next)
218

    
219
/**
220
 * list_for_each_entry        -        iterate over list of given type
221
 * @pos:        the type * to use as a loop counter.
222
 * @head:        the head for your list.
223
 * @member:        the name of the list_struct within the struct.
224
 */
225
#define list_for_each_entry(pos, head, member)                                \
226
        for (pos = list_entry((head)->next, typeof(*pos), member);        \
227
             &pos->member != (head);                                         \
228
             pos = list_entry(pos->member.next, typeof(*pos), member))
229

    
230
/**
231
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
232
 * @pos:        the type * to use as a loop counter.
233
 * @n:                another type * to use as temporary storage
234
 * @head:        the head for your list.
235
 * @member:        the name of the list_struct within the struct.
236
 */
237
#define list_for_each_entry_safe(pos, n, head, member)                        \
238
        for (pos = list_entry((head)->next, typeof(*pos), member),        \
239
                n = list_entry(pos->member.next, typeof(*pos), member);        \
240
             &pos->member != (head);                                         \
241
             pos = n, n = list_entry(n->member.next, typeof(*n), member))
242

    
243

    
244
#endif