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 * Iterate over a list
243 * \param pos the iterator
244 * \param head the list to iterate over
246 * Behaviour is undefined if \a pos is removed from the list in the body of the
249 #define list_for_each(pos, head) \
250 for (pos = (head)->next, prefetch(pos->next); pos != (head); \
251 pos = pos->next, prefetch(pos->next))
254 * Iterate over a list safely
255 * \param pos the iterator
256 * \param n temporary storage
257 * \param head the list to iterate over
259 * This is safe to use if \a pos could be removed from the list in the body of
262 #define list_for_each_safe(pos, n, head) \
263 for (pos = (head)->next, n = pos->next; pos != (head); \
264 pos = n, n = pos->next)
267 * Iterate over a list continuing after existing point
268 * \param pos the type * to use as a loop counter
269 * \param head the list head
270 * \param member the name of the list_struct within the struct
272 #define list_for_each_entry_continue(pos, head, member) \
273 for (pos = list_entry(pos->member.next, typeof(*pos), member); \
274 prefetch(pos->member.next), &pos->member != (head); \
275 pos = list_entry(pos->member.next, typeof(*pos), member))
278 * \defgroup hlist Hash List
279 * Double linked lists with a single pointer list head.
280 * Mostly useful for hash tables where the two pointer list head is too
281 * wasteful. You lose the ability to access the tail in O(1).
286 struct hlist_node *next, **pprev;
290 struct hlist_node *first;
296 * "NULL" might not be defined at this point
301 #define NULL_P ((void *)0)
309 #define HLIST_HEAD_INIT { NULL_P }
310 #define HLIST_HEAD(name) struct hlist_head name = { NULL_P }
311 #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P)
312 #define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P)
314 static inline int hlist_unhashed(const struct hlist_node *h)
319 static inline int hlist_empty(const struct hlist_head *h)
324 static inline void __hlist_del(struct hlist_node *n)
326 struct hlist_node *next = n->next;
327 struct hlist_node **pprev = n->pprev;
333 static inline void hlist_del(struct hlist_node *n)
338 static inline void hlist_del_init(struct hlist_node *n)
346 static inline void hlist_add_head(struct hlist_node *n,
347 struct hlist_head *h)
349 struct hlist_node *first = h->first;
352 first->pprev = &n->next;
354 n->pprev = &h->first;
357 /* next must be != NULL */
358 static inline void hlist_add_before(struct hlist_node *n,
359 struct hlist_node *next)
361 n->pprev = next->pprev;
363 next->pprev = &n->next;
367 static inline void hlist_add_after(struct hlist_node *n,
368 struct hlist_node *next)
370 next->next = n->next;
372 next->pprev = &n->next;
375 next->next->pprev = &next->next;
378 #define hlist_entry(ptr, type, member) container_of(ptr,type,member)
380 #define hlist_for_each(pos, head) \
381 for (pos = (head)->first; pos && (prefetch(pos->next), 1); \
384 #define hlist_for_each_safe(pos, n, head) \
385 for (pos = (head)->first; pos && (n = pos->next, 1); \
389 * Iterate over an hlist of given type
390 * \param tpos the type * to use as a loop counter.
391 * \param pos the &struct hlist_node to use as a loop counter.
392 * \param head the head for your list.
393 * \param member the name of the hlist_node within the struct.
395 #define hlist_for_each_entry(tpos, pos, head, member) \
396 for (pos = (head)->first; \
397 pos && ({ prefetch(pos->next); 1;}) && \
398 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
402 * Iterate over an hlist continuing after existing point
403 * \param tpos the type * to use as a loop counter.
404 * \param pos the &struct hlist_node to use as a loop counter.
405 * \param member the name of the hlist_node within the struct.
407 #define hlist_for_each_entry_continue(tpos, pos, member) \
408 for (pos = (pos)->next; \
409 pos && ({ prefetch(pos->next); 1;}) && \
410 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
414 * Iterate over an hlist continuing from an existing point
415 * \param tpos the type * to use as a loop counter.
416 * \param pos the &struct hlist_node to use as a loop counter.
417 * \param member the name of the hlist_node within the struct.
419 #define hlist_for_each_entry_from(tpos, pos, member) \
420 for (; pos && ({ prefetch(pos->next); 1;}) && \
421 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
425 * Iterate over an hlist of given type safe against removal of list entry
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 n another &struct hlist_node to use as temporary storage
429 * \param head the head for your list.
430 * \param member the name of the hlist_node within the struct.
432 #define hlist_for_each_entry_safe(tpos, pos, n, head, member) \
433 for (pos = (head)->first; \
434 pos && ({ n = pos->next; 1; }) && \
435 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
441 * Iterate over a list in reverse order
442 * \param pos the &struct list_head to use as a loop counter.
443 * \param head the head for your list.
445 #define list_for_each_prev(pos, head) \
446 for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
447 pos = pos->prev, prefetch(pos->prev))
450 * Iterate over a list of given type
451 * \param pos the type * to use as a loop counter.
452 * \param head the head for your list.
453 * \param member the name of the list_struct within the struct.
455 #define list_for_each_entry(pos, head, member) \
456 for (pos = list_entry((head)->next, typeof(*pos), member), \
457 prefetch(pos->member.next); \
458 &pos->member != (head); \
459 pos = list_entry(pos->member.next, typeof(*pos), member), \
460 prefetch(pos->member.next))
463 * Iterate backwards over a list of given type.
464 * \param pos the type * to use as a loop counter.
465 * \param head the head for your list.
466 * \param member the name of the list_struct within the struct.
468 #define list_for_each_entry_reverse(pos, head, member) \
469 for (pos = list_entry((head)->prev, typeof(*pos), member); \
470 prefetch(pos->member.prev), &pos->member != (head); \
471 pos = list_entry(pos->member.prev, typeof(*pos), member))
474 * Iterate over a list of given type safe against removal of list entry
475 * \param pos the type * to use as a loop counter.
476 * \param n another type * to use as temporary storage
477 * \param head the head for your list.
478 * \param member the name of the list_struct within the struct.
480 #define list_for_each_entry_safe(pos, n, head, member) \
481 for (pos = list_entry((head)->next, typeof(*pos), member), \
482 n = list_entry(pos->member.next, typeof(*pos), member); \
483 &pos->member != (head); \
484 pos = n, n = list_entry(n->member.next, typeof(*n), member))
487 * Iterate backwards over a list of given type safely against removal of entry
488 * \param pos the type * to use as a loop counter.
489 * \param n another type * to use as temporary storage
490 * \param head the head for your list.
491 * \param member the name of the list_struct within the struct.
493 #define list_for_each_entry_safe_reverse(pos, n, head, member) \
494 for (pos = list_entry((head)->prev, typeof(*pos), member), \
495 n = list_entry(pos->member.prev, typeof(*pos), member); \
496 &pos->member != (head); \
497 pos = n, n = list_entry(n->member.prev, typeof(*n), member))
499 #endif /* __LIBCFS_UTIL_LIST_H__ */