← Back to branch summary

~darkxst/ubuntu/raring/xorg-server/lp1073724

« back to all changes in this revision

Viewing changes to include/list.h

  • Committer: Package Import Robot
  • Author(s): Cyril Brulebois
  • Date: 2011-12-20 11:39:51 UTC
  • mto: (0.10.23) (1.1.48)
  • mto: This revision was merged to the branch mainline in revision 244.
  • Revision ID: package-import@ubuntu.com-20111220113951-cx9svdcnqpcta5wk
Tags: upstream-1.11.99.2
Import upstream version 1.11.99.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/list.h
28
28
 
29
29
/**
30
30
 * @file Classic doubly-link circular list implementation.
 
31
 * For real usage examples of the linked list, see the file test/list.c
31
32
 *
32
33
 * Example:
33
34
 * We need to keep a list of struct foo in the parent struct bar, i.e. what
35
36
 *
36
37
 *     struct bar {
37
38
 *          ...
38
 
 *          struct foo *foos; -----> struct foo {}, struct foo {}, struct foo{}
 
39
 *          struct foo *list_of_foos; -----> struct foo {}, struct foo {}, struct foo{}
39
40
 *          ...
40
41
 *     }
41
42
 *
42
 
 * We need one list head in bar and a list element in all foos (both are of
 
43
 * We need one list head in bar and a list element in all list_of_foos (both are of
43
44
 * data type 'struct list').
44
45
 *
45
46
 *     struct bar {
46
47
 *          ...
47
 
 *          struct list foos;
 
48
 *          struct list list_of_foos;
48
49
 *          ...
49
50
 *     }
50
51
 *
58
59
 *
59
60
 *     struct bar bar;
60
61
 *     ...
61
 
 *     list_init(&bar.foos);
 
62
 *     list_init(&bar.list_of_foos);
62
63
 *
63
64
 * Then we create the first element and add it to this list:
64
65
 *
65
66
 *     struct foo *foo = malloc(...);
66
67
 *     ....
67
 
 *     list_add(&foo->entry, &bar.foos);
 
68
 *     list_add(&foo->entry, &bar.list_of_foos);
68
69
 *
69
70
 * Repeat the above for each element you want to add to the list. Deleting
70
71
 * works with the element itself.
71
72
 *      list_del(&foo->entry);
72
73
 *      free(foo);
73
74
 *
74
 
 * Note: calling list_del(&bar.foos) will set bar.foos to an empty
 
75
 * Note: calling list_del(&bar.list_of_foos) will set bar.list_of_foos to an empty
75
76
 * list again.
76
77
 *
77
78
 * Looping through the list requires a 'struct foo' as iterator and the
78
79
 * name of the field the subnodes use.
79
80
 *
80
81
 * struct foo *iterator;
81
 
 * list_for_each_entry(iterator, &bar.foos, entry) {
 
82
 * list_for_each_entry(iterator, &bar.list_of_foos, entry) {
82
83
 *      if (iterator->something == ...)
83
84
 *             ...
84
85
 * }
87
88
 * loop. You need to run the safe for-each loop instead:
88
89
 *
89
90
 * struct foo *iterator, *next;
90
 
 * list_for_each_entry_safe(iterator, next, &bar.foos, entry) {
 
91
 * list_for_each_entry_safe(iterator, next, &bar.list_of_foos, entry) {
91
92
 *      if (...)
92
93
 *              list_del(&iterator->entry);
93
94
 * }
96
97
 
97
98
/**
98
99
 * The linkage struct for list nodes. This struct must be part of your
99
 
 * to-be-linked struct.
100
 
 *
101
 
 * Example:
102
 
 * struct foo {
103
 
 *      int a;
104
 
 *      void *b;
105
 
 *      struct list *mylist;
106
 
 * }
 
100
 * to-be-linked struct. struct list is required for both the head of the
 
101
 * list and for each list node.
107
102
 *
108
103
 * Position and name of the struct list field is irrelevant.
109
104
 * There are no requirements that elements of a list are of the same type.
118
113
 * Initialize the list as an empty list.
119
114
 *
120
115
 * Example:
121
 
 * list_init(&foo->mylist);
 
116
 * list_init(&bar->list_of_foos);
122
117
 *
123
118
 * @param The list to initialized.
124
119
 */
140
135
}
141
136
 
142
137
/**
143
 
 * Insert a new element after the given list head.
 
138
 * Insert a new element after the given list head. The new element does not
 
139
 * need to be initialised as empty list.
144
140
 * The list changes from:
145
141
 *      head → some element → ...
146
142
 * to
148
144
 *
149
145
 * Example:
150
146
 * struct foo *newfoo = malloc(...);
151
 
 * list_add(&newfoo->mylist, &foo->mylist);
 
147
 * list_add(&newfoo->entry, &bar->list_of_foos);
152
148
 *
153
149
 * @param entry The new element to prepend to the list.
154
150
 * @param head The existing list.
159
155
    __list_add(entry, head, head->next);
160
156
}
161
157
 
 
158
/**
 
159
 * Append a new element to the end of the list given with this list head.
 
160
 *
 
161
 * The list changes from:
 
162
 *      head → some element → ... → lastelement
 
163
 * to
 
164
 *      head → some element → ... → lastelement → new element
 
165
 *
 
166
 * Example:
 
167
 * struct foo *newfoo = malloc(...);
 
168
 * list_append(&newfoo->entry, &bar->list_of_foos);
 
169
 *
 
170
 * @param entry The new element to prepend to the list.
 
171
 * @param head The existing list.
 
172
 */
 
173
static inline void
 
174
list_append(struct list *entry, struct list *head)
 
175
{
 
176
    __list_add(entry, head->prev, head);
 
177
}
 
178
 
 
179
 
162
180
static inline void
163
181
__list_del(struct list *prev, struct list *next)
164
182
{
176
194
 * the list but rather reset the list as empty list.
177
195
 *
178
196
 * Example:
179
 
 * list_del(&newfoo->mylist);
 
197
 * list_del(&foo->entry);
180
198
 *
181
199
 * @param entry The element to remove.
182
200
 */
191
209
 * Check if the list is empty.
192
210
 *
193
211
 * Example:
194
 
 * list_is_empty(&foo->mylist);
 
212
 * list_is_empty(&bar->list_of_foos);
195
213
 *
196
214
 * @return True if the list contains one or more elements or False otherwise.
197
215
 */
206
224
 *
207
225
 * Example:
208
226
 * struct foo* f;
209
 
 * f = container_of(&foo->mylist, struct foo, mylist);
 
227
 * f = container_of(&foo->entry, struct foo, entry);
210
228
 * assert(f == foo);
211
229
 *
212
230
 * @param ptr Pointer to the struct list.
230
248
 *
231
249
 * Example:
232
250
 * struct foo *first;
233
 
 * first = list_first_entry(&foo->mylist, struct foo, mylist);
 
251
 * first = list_first_entry(&bar->list_of_foos, struct foo, list_of_foos);
234
252
 *
235
253
 * @param ptr The list head
236
254
 * @param type Data type of the list element to retrieve
240
258
#define list_first_entry(ptr, type, member) \
241
259
    list_entry((ptr)->next, type, member)
242
260
 
 
261
/**
 
262
 * Retrieve the last list entry for the given listpointer.
 
263
 *
 
264
 * Example:
 
265
 * struct foo *first;
 
266
 * first = list_last_entry(&bar->list_of_foos, struct foo, list_of_foos);
 
267
 *
 
268
 * @param ptr The list head
 
269
 * @param type Data type of the list element to retrieve
 
270
 * @param member Member name of the struct list field in the list element.
 
271
 * @return A pointer to the last list element.
 
272
 */
 
273
#define list_last_entry(ptr, type, member) \
 
274
    list_entry((ptr)->prev, type, member)
 
275
 
243
276
#define __container_of(ptr, sample, member)                             \
244
277
    (void *)((char *)(ptr)                                              \
245
278
             - ((char *)&(sample)->member - (char *)(sample)))
248
281
 *
249
282
 * Example:
250
283
 * struct foo *iterator;
251
 
 * list_for_each_entry(iterator, &foo->mylist, mylist) {
 
284
 * list_for_each_entry(iterator, &bar->list_of_foos, entry) {
252
285
 *      [modify iterator]
253
286
 * }
254
287
 *