4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 only,
8 * as published by the Free Software Foundation.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License version 2 for more details. A copy is
14 * included in the COPYING file that accompanied this code.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 #ifndef __LIBCFS_UTIL_LIST_H__
24 #define __LIBCFS_UTIL_LIST_H__
27 * Simple doubly linked list implementation.
29 * Some of the internal functions ("__xxx") are useful when
30 * manipulating whole lists rather than single entries, as
31 * sometimes we already know the next/prev entries and we can
32 * generate better code by using them directly rather than
33 * using the generic single-entry routines.
36 #define prefetch(a) ((void)a)
39 struct list_head *next, *prev;
42 #define LIST_HEAD_INIT(name) { &(name), &(name) }
44 #define INIT_LIST_HEAD(ptr) do { \
45 (ptr)->next = (ptr); (ptr)->prev = (ptr); \
49 * Insert a new entry between two known consecutive entries.
51 * This is only for internal list manipulation where we know
52 * the prev/next entries already!
54 static inline void __list_add(struct list_head * new,
55 struct list_head * prev,
56 struct list_head * next)
65 * Insert an entry at the start of a list.
66 * \param new new entry to be inserted
67 * \param head list to add it to
69 * Insert a new entry after the specified head.
70 * This is good for implementing stacks.
72 static inline void list_add(struct list_head *new,
73 struct list_head *head)
75 __list_add(new, head, head->next);
79 * Insert an entry at the end of a list.
80 * \param new new entry to be inserted
81 * \param head list to add it to
83 * Insert a new entry before the specified head.
84 * This is useful for implementing queues.
86 static inline void list_add_tail(struct list_head *new,
87 struct list_head *head)
89 __list_add(new, head->prev, head);
93 * Delete a list entry by making the prev/next entries
94 * point to each other.
96 * This is only for internal list manipulation where we know
97 * the prev/next entries already!
99 static inline void __list_del(struct list_head *prev,
100 struct list_head *next)
107 * Remove an entry from the list it is currently in.
108 * \param entry the entry to remove
109 * Note: list_empty(entry) does not return true after this, the entry is in an
112 static inline void list_del(struct list_head *entry)
114 __list_del(entry->prev, entry->next);
118 * Remove an entry from the list it is currently in and reinitialize it.
119 * \param entry the entry to remove.
121 static inline void list_del_init(struct list_head *entry)
123 __list_del(entry->prev, entry->next);
124 INIT_LIST_HEAD(entry);
128 * Remove an entry from the list it is currently in and insert it at the start
130 * \param list the entry to move
131 * \param head the list to move it to
133 static inline void list_move(struct list_head *list,
134 struct list_head *head)
136 __list_del(list->prev, list->next);
137 list_add(list, head);
141 * Remove an entry from the list it is currently in and insert it at the end of
143 * \param list the entry to move
144 * \param head the list to move it to
146 static inline void list_move_tail(struct list_head *list,
147 struct list_head *head)
149 __list_del(list->prev, list->next);
150 list_add_tail(list, head);
154 * Test whether a list is empty
155 * \param head the list to test.
157 static inline int list_empty(struct list_head *head)
159 return head->next == head;
163 * Test whether a list is empty and not being modified
164 * \param head the list to test
166 * Tests whether a list is empty _and_ checks that no other CPU might be
167 * in the process of modifying either member (next or prev)
169 * NOTE: using list_empty_careful() without synchronization
170 * can only be safe if the only activity that can happen
171 * to the list entry is list_del_init(). Eg. it cannot be used
172 * if another CPU could re-list_add() it.
174 static inline int list_empty_careful(const struct list_head *head)
176 struct list_head *next = head->next;
177 return (next == head) && (next == head->prev);
180 static inline void __list_splice(struct list_head *list,
181 struct list_head *head)
183 struct list_head *first = list->next;
184 struct list_head *last = list->prev;
185 struct list_head *at = head->next;
196 * \param list the new list to add.
197 * \param head the place to add it in the first list.
199 * The contents of \a list are added at the start of \a head. \a list is in an
200 * undefined state on return.
202 static inline void list_splice(struct list_head *list,
203 struct list_head *head)
205 if (!list_empty(list))
206 __list_splice(list, head);
209 static inline void list_splice_tail(struct list_head *list, struct list_head *head)
211 if (!list_empty(list))
212 __list_splice(list, head->prev);
216 * Join two lists and reinitialise the emptied list.
217 * \param list the new list to add.
218 * \param head the place to add it in the first list.
220 * The contents of \a list are added at the start of \a head. \a list is empty
223 static inline void list_splice_init(struct list_head *list,
224 struct list_head *head)
226 if (!list_empty(list)) {
227 __list_splice(list, head);
228 INIT_LIST_HEAD(list);
233 * Get the container of a list
234 * \param ptr the embedded list.
235 * \param type the type of the struct this is embedded in.
236 * \param member the member name of the list within the struct.
238 #define list_entry(ptr, type, member) \
239 ((type *)((char *)(ptr)-(char *)(&((type *)0)->member)))
242 * list_first_entry - get the first element from a list
243 * \param ptr the list head to take the element from.
244 * \param type the type of the struct this is embedded in.
245 * \param member the name of the list_head within the struct.
247 * Note, that list is expected to be not empty.
249 #define list_first_entry(ptr, type, member) \
250 list_entry((ptr)->next, type, member)
253 * Iterate over a list
254 * \param pos the iterator
255 * \param head the list to iterate over
257 * Behaviour is undefined if \a pos is removed from the list in the body of the
260 #define list_for_each(pos, head) \
261 for (pos = (head)->next, prefetch(pos->next); pos != (head); \
262 pos = pos->next, prefetch(pos->next))
265 * Iterate over a list safely
266 * \param pos the iterator
267 * \param n temporary storage
268 * \param head the list to iterate over
270 * This is safe to use if \a pos could be removed from the list in the body of
273 #define list_for_each_safe(pos, n, head) \
274 for (pos = (head)->next, n = pos->next; pos != (head); \
275 pos = n, n = pos->next)
278 * Iterate over a list continuing after existing point
279 * \param pos the type * to use as a loop counter
280 * \param head the list head
281 * \param member the name of the list_struct within the struct
283 #define list_for_each_entry_continue(pos, head, member) \
284 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
285 prefetch(pos->member.next), &pos->member != (head); \
286 pos = list_entry(pos->member.next, typeof(*pos), member))
289 * \defgroup hlist Hash List
290 * Double linked lists with a single pointer list head.
291 * Mostly useful for hash tables where the two pointer list head is too
292 * wasteful. You lose the ability to access the tail in O(1).
297 struct hlist_node *next, **pprev;
301 struct hlist_node *first;
307 * "NULL" might not be defined at this point
312 #define NULL_P ((void *)0)
320 #define HLIST_HEAD_INIT { NULL_P }
321 #define HLIST_HEAD(name) struct hlist_head name = { NULL_P }
322 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
323 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
325 static inline int hlist_unhashed(const struct hlist_node *h)
330 static inline int hlist_empty(const struct hlist_head *h)
335 static inline void __hlist_del(struct hlist_node *n)
337 struct hlist_node *next = n->next;
338 struct hlist_node **pprev = n->pprev;
344 static inline void hlist_del(struct hlist_node *n)
349 static inline void hlist_del_init(struct hlist_node *n)
357 static inline void hlist_add_head(struct hlist_node *n,
358 struct hlist_head *h)
360 struct hlist_node *first = h->first;
363 first->pprev = &n->next;
365 n->pprev = &h->first;
368 /* next must be != NULL */
369 static inline void hlist_add_before(struct hlist_node *n,
370 struct hlist_node *next)
372 n->pprev = next->pprev;
374 next->pprev = &n->next;
378 static inline void hlist_add_after(struct hlist_node *n,
379 struct hlist_node *next)
381 next->next = n->next;
383 next->pprev = &n->next;
386 next->next->pprev = &next->next;
389 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
391 #define hlist_for_each(pos, head) \
392 for (pos = (head)->first; pos && (prefetch(pos->next), 1); \
395 #define hlist_for_each_safe(pos, n, head) \
396 for (pos = (head)->first; pos && (n = pos->next, 1); \
400 * Iterate over an hlist of given type
401 * \param tpos the type * to use as a loop counter.
402 * \param pos the &struct hlist_node to use as a loop counter.
403 * \param head the head for your list.
404 * \param member the name of the hlist_node within the struct.
406 #define hlist_for_each_entry(tpos, pos, head, member) \
407 for (pos = (head)->first; \
408 pos && ({ prefetch(pos->next); 1;}) && \
409 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
413 * Iterate over an hlist continuing after existing point
414 * \param tpos the type * to use as a loop counter.
415 * \param pos the &struct hlist_node to use as a loop counter.
416 * \param member the name of the hlist_node within the struct.
418 #define hlist_for_each_entry_continue(tpos, pos, member) \
419 for (pos = (pos)->next; \
420 pos && ({ prefetch(pos->next); 1;}) && \
421 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
425 * Iterate over an hlist continuing from an existing point
426 * \param tpos the type * to use as a loop counter.
427 * \param pos the &struct hlist_node to use as a loop counter.
428 * \param member the name of the hlist_node within the struct.
430 #define hlist_for_each_entry_from(tpos, pos, member) \
431 for (; pos && ({ prefetch(pos->next); 1;}) && \
432 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
436 * Iterate over an hlist of given type safe against removal of list entry
437 * \param tpos the type * to use as a loop counter.
438 * \param pos the &struct hlist_node to use as a loop counter.
439 * \param n another &struct hlist_node to use as temporary storage
440 * \param head the head for your list.
441 * \param member the name of the hlist_node within the struct.
443 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
444 for (pos = (head)->first; \
445 pos && ({ n = pos->next; 1; }) && \
446 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
452 * Iterate over a list in reverse order
453 * \param pos the &struct list_head to use as a loop counter.
454 * \param head the head for your list.
456 #define list_for_each_prev(pos, head) \
457 for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
458 pos = pos->prev, prefetch(pos->prev))
461 * Iterate over a list of given type
462 * \param pos the type * to use as a loop counter.
463 * \param head the head for your list.
464 * \param member the name of the list_struct within the struct.
466 #define list_for_each_entry(pos, head, member) \
467 for (pos = list_first_entry((head), typeof(*pos), member), \
468 prefetch(pos->member.next); \
469 &pos->member != (head); \
470 pos = list_entry(pos->member.next, typeof(*pos), member), \
471 prefetch(pos->member.next))
474 * Iterate backwards over a list of given type.
475 * \param pos the type * to use as a loop counter.
476 * \param head the head for your list.
477 * \param member the name of the list_struct within the struct.
479 #define list_for_each_entry_reverse(pos, head, member) \
480 for (pos = list_entry((head)->prev, typeof(*pos), member); \
481 prefetch(pos->member.prev), &pos->member != (head); \
482 pos = list_entry(pos->member.prev, typeof(*pos), member))
485 * Iterate over a list of given type safe against removal of list entry
486 * \param pos the type * to use as a loop counter.
487 * \param n another type * to use as temporary storage
488 * \param head the head for your list.
489 * \param member the name of the list_struct within the struct.
491 #define list_for_each_entry_safe(pos, n, head, member) \
492 for (pos = list_first_entry((head), typeof(*pos), member), \
493 n = list_entry(pos->member.next, typeof(*pos), member); \
494 &pos->member != (head); \
495 pos = n, n = list_entry(n->member.next, typeof(*n), member))
498 * Iterate backwards over a list of given type safely against removal of entry
499 * \param pos the type * to use as a loop counter.
500 * \param n another type * to use as temporary storage
501 * \param head the head for your list.
502 * \param member the name of the list_struct within the struct.
504 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
505 for (pos = list_entry((head)->prev, typeof(*pos), member), \
506 n = list_entry(pos->member.prev, typeof(*pos), member); \
507 &pos->member != (head); \
508 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
510 #endif /* __LIBCFS_UTIL_LIST_H__ */