list.h 21.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1
2
3
#ifndef _LINUX_LIST_H
#define _LINUX_LIST_H

4
#include <linux/types.h>
Linus Torvalds's avatar
Linus Torvalds committed
5
#include <linux/stddef.h>
6
#include <linux/poison.h>
Linus Torvalds's avatar
Linus Torvalds committed
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <linux/prefetch.h>

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

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

#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)

24
25
26
27
28
static inline void INIT_LIST_HEAD(struct list_head *list)
{
	list->next = list;
	list->prev = list;
}
Linus Torvalds's avatar
Linus Torvalds committed
29
30
31
32
33
34
35

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
36
#ifndef CONFIG_DEBUG_LIST
Linus Torvalds's avatar
Linus Torvalds committed
37
38
39
40
41
42
43
44
45
static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}
46
47
48
49
50
#else
extern void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next);
#endif
Linus Torvalds's avatar
Linus Torvalds committed
51
52
53
54
55
56
57
58
59
60
61
62
63

/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}
64

Linus Torvalds's avatar
Linus Torvalds committed
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

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	prev->next = next;
}

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
95
 * Note: list_empty() on entry does not return true after this, the entry is
Linus Torvalds's avatar
Linus Torvalds committed
96
97
 * in an undefined state.
 */
98
#ifndef CONFIG_DEBUG_LIST
Linus Torvalds's avatar
Linus Torvalds committed
99
100
101
102
103
104
static inline void list_del(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
105
106
107
#else
extern void list_del(struct list_head *entry);
#endif
Linus Torvalds's avatar
Linus Torvalds committed
108

109
110
111
112
/**
 * list_replace - replace old entry by new one
 * @old : the element to be replaced
 * @new : the new element to insert
113
114
 *
 * If @old was empty, it will be overwritten.
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 */
static inline void list_replace(struct list_head *old,
				struct list_head *new)
{
	new->next = old->next;
	new->next->prev = new;
	new->prev = old->prev;
	new->prev->next = new;
}

static inline void list_replace_init(struct list_head *old,
					struct list_head *new)
{
	list_replace(old, new);
	INIT_LIST_HEAD(old);
}

Linus Torvalds's avatar
Linus Torvalds committed
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	INIT_LIST_HEAD(entry);
}

/**
 * list_move - delete from one list and add as another's head
 * @list: the entry to move
 * @head: the head that will precede our entry
 */
static inline void list_move(struct list_head *list, struct list_head *head)
{
149
150
	__list_del(list->prev, list->next);
	list_add(list, head);
Linus Torvalds's avatar
Linus Torvalds committed
151
152
153
154
155
156
157
158
159
160
}

/**
 * list_move_tail - delete from one list and add as another's tail
 * @list: the entry to move
 * @head: the head that will follow our entry
 */
static inline void list_move_tail(struct list_head *list,
				  struct list_head *head)
{
161
162
	__list_del(list->prev, list->next);
	list_add_tail(list, head);
Linus Torvalds's avatar
Linus Torvalds committed
163
164
}

Shailabh Nagar's avatar
Shailabh Nagar committed
165
166
167
168
169
170
171
172
173
174
175
/**
 * list_is_last - tests whether @list is the last entry in list @head
 * @list: the entry to test
 * @head: the head of the list
 */
static inline int list_is_last(const struct list_head *list,
				const struct list_head *head)
{
	return list->next == head;
}

Linus Torvalds's avatar
Linus Torvalds committed
176
177
178
179
180
181
182
183
184
185
/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)
{
	return head->next == head;
}

/**
Randy Dunlap's avatar
Randy Dunlap committed
186
187
188
189
190
191
 * list_empty_careful - tests whether a list is empty and not being modified
 * @head: the list to test
 *
 * Description:
 * tests whether a list is empty _and_ checks that no other CPU might be
 * in the process of modifying either member (next or prev)
Linus Torvalds's avatar
Linus Torvalds committed
192
193
194
195
196
197
198
199
200
201
 *
 * NOTE: using list_empty_careful() without synchronization
 * can only be safe if the only activity that can happen
 * to the list entry is list_del_init(). Eg. it cannot be used
 * if another CPU could re-list_add() it.
 */
static inline int list_empty_careful(const struct list_head *head)
{
	struct list_head *next = head->next;
	return (next == head) && (next == head->prev);
202
203
}

204
205
206
207
208
209
210
211
212
213
214
215
216
217
/**
 * list_rotate_left - rotate the list to the left
 * @head: the head of the list
 */
static inline void list_rotate_left(struct list_head *head)
{
	struct list_head *first;

	if (!list_empty(head)) {
		first = head->next;
		list_move_tail(first, head);
	}
}

218
219
220
221
222
223
224
/**
 * list_is_singular - tests whether a list has just one entry.
 * @head: the list to test.
 */
static inline int list_is_singular(const struct list_head *head)
{
	return !list_empty(head) && (head->next == head->prev);
Linus Torvalds's avatar
Linus Torvalds committed
225
226
}

227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
static inline void __list_cut_position(struct list_head *list,
		struct list_head *head, struct list_head *entry)
{
	struct list_head *new_first = entry->next;
	list->next = head->next;
	list->next->prev = list;
	list->prev = entry;
	entry->next = list;
	head->next = new_first;
	new_first->prev = head;
}

/**
 * list_cut_position - cut a list into two
 * @list: a new list to add all removed entries
 * @head: a list with entries
 * @entry: an entry within head, could be the head itself
 *	and if so we won't cut the list
 *
 * This helper moves the initial part of @head, up to and
 * including @entry, from @head to @list. You should
 * pass on @entry an element you know is on @head. @list
 * should be an empty list or a list you do not care about
 * losing its data.
 *
 */
static inline void list_cut_position(struct list_head *list,
		struct list_head *head, struct list_head *entry)
{
	if (list_empty(head))
		return;
	if (list_is_singular(head) &&
		(head->next != entry && head != entry))
		return;
	if (entry == head)
		INIT_LIST_HEAD(list);
	else
		__list_cut_position(list, head, entry);
}

267
static inline void __list_splice(const struct list_head *list,
268
269
				 struct list_head *prev,
				 struct list_head *next)
Linus Torvalds's avatar
Linus Torvalds committed
270
271
272
273
{
	struct list_head *first = list->next;
	struct list_head *last = list->prev;

274
275
	first->prev = prev;
	prev->next = first;
Linus Torvalds's avatar
Linus Torvalds committed
276

277
278
	last->next = next;
	next->prev = last;
Linus Torvalds's avatar
Linus Torvalds committed
279
280
281
}

/**
282
 * list_splice - join two lists, this is designed for stacks
Linus Torvalds's avatar
Linus Torvalds committed
283
284
285
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
286
287
static inline void list_splice(const struct list_head *list,
				struct list_head *head)
Linus Torvalds's avatar
Linus Torvalds committed
288
289
{
	if (!list_empty(list))
290
291
292
293
294
295
296
297
298
299
300
301
302
		__list_splice(list, head, head->next);
}

/**
 * list_splice_tail - join two lists, each list being a queue
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 */
static inline void list_splice_tail(struct list_head *list,
				struct list_head *head)
{
	if (!list_empty(list))
		__list_splice(list, head->prev, head);
Linus Torvalds's avatar
Linus Torvalds committed
303
304
305
306
307
308
309
310
311
312
313
314
315
}

/**
 * list_splice_init - join two lists and reinitialise the emptied list.
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 *
 * The list at @list is reinitialised
 */
static inline void list_splice_init(struct list_head *list,
				    struct list_head *head)
{
	if (!list_empty(list)) {
316
317
318
319
320
321
		__list_splice(list, head, head->next);
		INIT_LIST_HEAD(list);
	}
}

/**
322
 * list_splice_tail_init - join two lists and reinitialise the emptied list
323
324
325
 * @list: the new list to add.
 * @head: the place to add it in the first list.
 *
326
 * Each of the lists is a queue.
327
328
329
330
331
332
333
 * The list at @list is reinitialised
 */
static inline void list_splice_tail_init(struct list_head *list,
					 struct list_head *head)
{
	if (!list_empty(list)) {
		__list_splice(list, head->prev, head);
Linus Torvalds's avatar
Linus Torvalds committed
334
335
336
337
338
339
340
341
342
343
344
345
346
		INIT_LIST_HEAD(list);
	}
}

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

347
348
349
350
351
352
353
354
355
356
357
/**
 * list_first_entry - get the first element from a list
 * @ptr:	the list head to take the element from.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_struct within the struct.
 *
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
	list_entry((ptr)->next, type, member)

Linus Torvalds's avatar
Linus Torvalds committed
358
359
/**
 * list_for_each	-	iterate over a list
360
 * @pos:	the &struct list_head to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
361
362
363
364
365
366
367
368
 * @head:	the head for your list.
 */
#define list_for_each(pos, head) \
	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
        	pos = pos->next)

/**
 * __list_for_each	-	iterate over a list
369
 * @pos:	the &struct list_head to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
370
371
372
373
374
375
376
377
378
379
380
381
 * @head:	the head for your list.
 *
 * This variant differs from list_for_each() in that it's the
 * simplest possible list iteration code, no prefetching is done.
 * Use this for code that knows the list to be very short (empty
 * or 1 entry) most of the time.
 */
#define __list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

/**
 * list_for_each_prev	-	iterate over a list backwards
382
 * @pos:	the &struct list_head to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
383
384
385
386
387
388
389
 * @head:	the head for your list.
 */
#define list_for_each_prev(pos, head) \
	for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
        	pos = pos->prev)

/**
Randy Dunlap's avatar
Randy Dunlap committed
390
 * list_for_each_safe - iterate over a list safe against removal of list entry
391
 * @pos:	the &struct list_head to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
392
393
394
395
396
397
398
 * @n:		another &struct list_head to use as temporary storage
 * @head:	the head for your list.
 */
#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

Denis V. Lunev's avatar
Denis V. Lunev committed
399
/**
400
 * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
Denis V. Lunev's avatar
Denis V. Lunev committed
401
402
403
404
405
406
407
408
409
 * @pos:	the &struct list_head to use as a loop cursor.
 * @n:		another &struct list_head to use as temporary storage
 * @head:	the head for your list.
 */
#define list_for_each_prev_safe(pos, n, head) \
	for (pos = (head)->prev, n = pos->prev; \
	     prefetch(pos->prev), pos != (head); \
	     pos = n, n = pos->prev)

Linus Torvalds's avatar
Linus Torvalds committed
410
411
/**
 * list_for_each_entry	-	iterate over list of given type
412
 * @pos:	the type * to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
413
414
415
416
417
418
419
420
421
422
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)				\
	for (pos = list_entry((head)->next, typeof(*pos), member);	\
	     prefetch(pos->member.next), &pos->member != (head); 	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_reverse - iterate backwards over list of given type.
423
 * @pos:	the type * to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
424
425
426
427
428
429
430
431
432
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#define list_for_each_entry_reverse(pos, head, member)			\
	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
	     prefetch(pos->member.prev), &pos->member != (head); 	\
	     pos = list_entry(pos->member.prev, typeof(*pos), member))

/**
433
 * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
Linus Torvalds's avatar
Linus Torvalds committed
434
435
436
 * @pos:	the type * to use as a start point
 * @head:	the head of the list
 * @member:	the name of the list_struct within the struct.
Randy Dunlap's avatar
Randy Dunlap committed
437
 *
438
 * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
Linus Torvalds's avatar
Linus Torvalds committed
439
440
441
442
443
 */
#define list_prepare_entry(pos, head, member) \
	((pos) ? : list_entry(head, typeof(*pos), member))

/**
Randy Dunlap's avatar
Randy Dunlap committed
444
 * list_for_each_entry_continue - continue iteration over list of given type
445
 * @pos:	the type * to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
446
447
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
Randy Dunlap's avatar
Randy Dunlap committed
448
449
450
 *
 * Continue to iterate over list of given type, continuing after
 * the current position.
Linus Torvalds's avatar
Linus Torvalds committed
451
452
453
454
455
456
 */
#define list_for_each_entry_continue(pos, head, member) 		\
	for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
	     prefetch(pos->member.next), &pos->member != (head);	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

457
458
459
460
461
462
463
464
465
466
467
468
469
470
/**
 * list_for_each_entry_continue_reverse - iterate backwards from the given point
 * @pos:	the type * to use as a loop cursor.
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 *
 * Start to iterate over list of given type backwards, continuing after
 * the current position.
 */
#define list_for_each_entry_continue_reverse(pos, head, member)		\
	for (pos = list_entry(pos->member.prev, typeof(*pos), member);	\
	     prefetch(pos->member.prev), &pos->member != (head);	\
	     pos = list_entry(pos->member.prev, typeof(*pos), member))

471
/**
Randy Dunlap's avatar
Randy Dunlap committed
472
 * list_for_each_entry_from - iterate over list of given type from the current point
473
 * @pos:	the type * to use as a loop cursor.
474
475
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
Randy Dunlap's avatar
Randy Dunlap committed
476
477
 *
 * Iterate over list of given type, continuing from current position.
478
479
480
481
482
 */
#define list_for_each_entry_from(pos, head, member) 			\
	for (; prefetch(pos->member.next), &pos->member != (head);	\
	     pos = list_entry(pos->member.next, typeof(*pos), member))

Linus Torvalds's avatar
Linus Torvalds committed
483
484
/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
485
 * @pos:	the type * to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
486
487
488
489
490
491
492
493
494
495
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
 */
#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))

496
/**
497
 * list_for_each_entry_safe_continue - continue list iteration safe against removal
498
 * @pos:	the type * to use as a loop cursor.
499
500
501
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
Randy Dunlap's avatar
Randy Dunlap committed
502
503
504
 *
 * Iterate over list of given type, continuing after current point,
 * safe against removal of list entry.
505
506
 */
#define list_for_each_entry_safe_continue(pos, n, head, member) 		\
507
508
	for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
		n = list_entry(pos->member.next, typeof(*pos), member);		\
509
510
511
512
	     &pos->member != (head);						\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
513
 * list_for_each_entry_safe_from - iterate over list from current point safe against removal
514
 * @pos:	the type * to use as a loop cursor.
515
516
517
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
Randy Dunlap's avatar
Randy Dunlap committed
518
519
520
 *
 * Iterate over list of given type from current point, safe against
 * removal of list entry.
521
522
523
 */
#define list_for_each_entry_safe_from(pos, n, head, member) 			\
	for (n = list_entry(pos->member.next, typeof(*pos), member);		\
524
525
526
	     &pos->member != (head);						\
	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

527
/**
528
 * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
529
 * @pos:	the type * to use as a loop cursor.
530
531
532
 * @n:		another type * to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the list_struct within the struct.
Randy Dunlap's avatar
Randy Dunlap committed
533
534
535
 *
 * Iterate backwards over list of given type, safe against removal
 * of list entry.
536
537
538
539
540
541
542
 */
#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
		n = list_entry(pos->member.prev, typeof(*pos), member);	\
	     &pos->member != (head); 					\
	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))

543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
/**
 * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
 * @pos:	the loop cursor used in the list_for_each_entry_safe loop
 * @n:		temporary storage used in list_for_each_entry_safe
 * @member:	the name of the list_struct within the struct.
 *
 * list_safe_reset_next is not safe to use in general if the list may be
 * modified concurrently (eg. the lock is dropped in the loop body). An
 * exception to this is if the cursor element (pos) is pinned in the list,
 * and list_safe_reset_next is called after re-taking the lock and before
 * completing the current iteration of the loop body.
 */
#define list_safe_reset_next(pos, n, member)				\
	n = list_entry(pos->member.next, typeof(*pos), member)

Linus Torvalds's avatar
Linus Torvalds committed
558
559
560
561
562
563
564
565
566
567
/*
 * Double linked lists with a single pointer list head.
 * Mostly useful for hash tables where the two pointer list head is
 * too wasteful.
 * You lose the ability to access the tail in O(1).
 */

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
568
569
570
571
572
static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
	h->next = NULL;
	h->pprev = NULL;
}
Linus Torvalds's avatar
Linus Torvalds committed
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601

static inline int hlist_unhashed(const struct hlist_node *h)
{
	return !h->pprev;
}

static inline int hlist_empty(const struct hlist_head *h)
{
	return !h->first;
}

static inline void __hlist_del(struct hlist_node *n)
{
	struct hlist_node *next = n->next;
	struct hlist_node **pprev = n->pprev;
	*pprev = next;
	if (next)
		next->pprev = pprev;
}

static inline void hlist_del(struct hlist_node *n)
{
	__hlist_del(n);
	n->next = LIST_POISON1;
	n->pprev = LIST_POISON2;
}

static inline void hlist_del_init(struct hlist_node *n)
{
Akinobu Mita's avatar
Akinobu Mita committed
602
	if (!hlist_unhashed(n)) {
Linus Torvalds's avatar
Linus Torvalds committed
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
		__hlist_del(n);
		INIT_HLIST_NODE(n);
	}
}

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
	struct hlist_node *first = h->first;
	n->next = first;
	if (first)
		first->pprev = &n->next;
	h->first = n;
	n->pprev = &h->first;
}

/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
					struct hlist_node *next)
{
	n->pprev = next->pprev;
	n->next = next;
	next->pprev = &n->next;
	*(n->pprev) = n;
}

static inline void hlist_add_after(struct hlist_node *n,
					struct hlist_node *next)
{
	next->next = n->next;
	n->next = next;
	next->pprev = &n->next;

	if(next->next)
		next->next->pprev  = &next->next;
}

639
640
641
642
643
644
/* after that we'll appear to be on some hlist and hlist_del will work */
static inline void hlist_add_fake(struct hlist_node *n)
{
	n->pprev = &n->next;
}

645
646
647
648
649
650
651
652
653
654
655
656
657
/*
 * Move a list from one list head to another. Fixup the pprev
 * reference of the first entry if it exists.
 */
static inline void hlist_move_list(struct hlist_head *old,
				   struct hlist_head *new)
{
	new->first = old->first;
	if (new->first)
		new->first->pprev = &new->first;
	old->first = NULL;
}

Linus Torvalds's avatar
Linus Torvalds committed
658
659
660
661
662
663
664
665
666
667
668
669
#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

#define hlist_for_each(pos, head) \
	for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
	     pos = pos->next)

#define hlist_for_each_safe(pos, n, head) \
	for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
	     pos = n)

/**
 * hlist_for_each_entry	- iterate over list of given type
670
671
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
672
673
674
675
676
677
678
679
680
681
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(tpos, pos, head, member)			 \
	for (pos = (head)->first;					 \
	     pos && ({ prefetch(pos->next); 1;}) &&			 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
Randy Dunlap's avatar
Randy Dunlap committed
682
 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
683
684
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
685
686
687
688
689
690
691
692
693
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_continue(tpos, pos, member)		 \
	for (pos = (pos)->next;						 \
	     pos && ({ prefetch(pos->next); 1;}) &&			 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
Randy Dunlap's avatar
Randy Dunlap committed
694
 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
695
696
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
697
698
699
700
701
702
703
704
705
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_from(tpos, pos, member)			 \
	for (; pos && ({ prefetch(pos->next); 1;}) &&			 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = pos->next)

/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
706
707
 * @tpos:	the type * to use as a loop cursor.
 * @pos:	the &struct hlist_node to use as a loop cursor.
Linus Torvalds's avatar
Linus Torvalds committed
708
709
710
711
712
713
714
715
716
717
718
 * @n:		another &struct hlist_node to use as temporary storage
 * @head:	the head for your list.
 * @member:	the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_safe(tpos, pos, n, head, member) 		 \
	for (pos = (head)->first;					 \
	     pos && ({ n = pos->next; 1; }) && 				 \
		({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
	     pos = n)

#endif