X-Git-Url: https://git.whamcloud.com/?a=blobdiff_plain;f=libcfs%2Finclude%2Flibcfs%2Flist.h;h=f73ce9841084be1c18178d80c32d1aa6d1d8b77e;hb=c64a87cede3b070573ed0062d98fc33be34111b8;hp=548bdf5cd15693f4574317be0730f2d672ead933;hpb=c8616363809a73b3d4b6c736e6b55a84d7f137b4;p=fs%2Flustre-release.git diff --git a/libcfs/include/libcfs/list.h b/libcfs/include/libcfs/list.h index 548bdf5..f73ce98 100644 --- a/libcfs/include/libcfs/list.h +++ b/libcfs/include/libcfs/list.h @@ -1,22 +1,31 @@ +/* + * GPL HEADER START + * + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 only, + * as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License version 2 for more details. A copy is + * included in the COPYING file that accompanied this code. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + * GPL HEADER END + */ + #ifndef __LIBCFS_LIST_H__ #define __LIBCFS_LIST_H__ -#if defined (__linux__) && defined(__KERNEL__) - -#include - -#define CFS_LIST_HEAD_INIT(n) LIST_HEAD_INIT(n) -#define CFS_LIST_HEAD(n) LIST_HEAD(n) -#define CFS_INIT_LIST_HEAD(p) INIT_LIST_HEAD(p) - -#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,0) -#define CFS_HLIST_HEAD_INIT HLIST_HEAD_INIT -#define CFS_HLIST_HEAD(n) HLIST_HEAD(n) -#define CFS_INIT_HLIST_HEAD(p) INIT_HLIST_HEAD(p) -#define CFS_INIT_HLIST_NODE(p) INIT_HLIST_NODE(p) -#endif - -#else /* !defined (__linux__) || !defined(__KERNEL__) */ +#ifdef __KERNEL__ +# include +#else /* __KERNEL__ */ /* * Simple doubly linked list implementation. @@ -34,26 +43,21 @@ struct list_head { struct list_head *next, *prev; }; -typedef struct list_head list_t; - -#define CFS_LIST_HEAD_INIT(name) { &(name), &(name) } +#define LIST_HEAD_INIT(name) { &(name), &(name) } -#define CFS_LIST_HEAD(name) \ - struct list_head name = CFS_LIST_HEAD_INIT(name) - -#define CFS_INIT_LIST_HEAD(ptr) do { \ +#define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0) -/* +/** * Insert a new entry between two known consecutive entries. * * This is only for internal list manipulation where we know * the prev/next entries already! */ static inline void __list_add(struct list_head * new, - struct list_head * prev, - struct list_head * next) + struct list_head * prev, + struct list_head * next) { next->prev = new; new->next = next; @@ -62,27 +66,29 @@ static inline void __list_add(struct list_head * new, } /** - * list_add - add a new entry - * @new: new entry to be added - * @head: list head to add it after + * Insert an entry at the start of a list. + * \param new new entry to be inserted + * \param head list to add it to * * 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) +static inline void list_add(struct list_head *new, + struct list_head *head) { __list_add(new, head, head->next); } /** - * list_add_tail - add a new entry - * @new: new entry to be added - * @head: list head to add it before + * Insert an entry at the end of a list. + * \param new new entry to be inserted + * \param head list to add it to * * 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) +static inline void list_add_tail(struct list_head *new, + struct list_head *head) { __list_add(new, head->prev, head); } @@ -94,16 +100,18 @@ static inline void list_add_tail(struct list_head *new, struct list_head *head) * 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) +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. - * Note: list_empty on entry does not return true after this, the entry is in an undefined state. + * Remove an entry from the list it is currently in. + * \param entry the entry to remove + * Note: list_empty(entry) does not return true after this, the entry is in an + * undefined state. */ static inline void list_del(struct list_head *entry) { @@ -111,53 +119,70 @@ static inline void list_del(struct list_head *entry) } /** - * list_del_init - deletes entry from list and reinitialize it. - * @entry: the element to delete from the list. + * Remove an entry from the list it is currently in and reinitialize it. + * \param entry the entry to remove. */ static inline void list_del_init(struct list_head *entry) { __list_del(entry->prev, entry->next); - CFS_INIT_LIST_HEAD(entry); + 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 - * - * This is not safe to use if @list is already on the same list as @head. + * Remove an entry from the list it is currently in and insert it at the start + * of another list. + * \param list the entry to move + * \param head the list to move it to */ -static inline void list_move(struct list_head *list, struct list_head *head) +static inline void list_move(struct list_head *list, + struct list_head *head) { __list_del(list->prev, list->next); list_add(list, head); } /** - * 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 - * - * This is not safe to use if @list is already on the same list as @head. + * Remove an entry from the list it is currently in and insert it at the end of + * another list. + * \param list the entry to move + * \param head the list to move it to */ static inline void list_move_tail(struct list_head *list, - struct list_head *head) + struct list_head *head) { __list_del(list->prev, list->next); list_add_tail(list, head); } /** - * list_empty - tests whether a list is empty - * @head: the list to test. + * Test whether a list is empty + * \param head the list to test. */ static inline int list_empty(struct list_head *head) { return head->next == head; } +/** + * Test whether a list is empty and not being modified + * \param head the list to test + * + * Tests whether a list is empty _and_ checks that no other CPU might be + * in the process of modifying either member (next or prev) + * + * 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); +} + static inline void __list_splice(struct list_head *list, - struct list_head *head) + struct list_head *head) { struct list_head *first = list->next; struct list_head *last = list->prev; @@ -171,74 +196,105 @@ static inline void __list_splice(struct list_head *list, } /** - * list_splice - join two lists - * @list: the new list to add. - * @head: the place to add it in the first list. + * Join two lists + * \param list the new list to add. + * \param head the place to add it in the first list. + * + * The contents of \a list are added at the start of \a head. \a list is in an + * undefined state on return. */ -static inline void list_splice(struct list_head *list, struct list_head *head) +static inline void list_splice(struct list_head *list, + struct list_head *head) { if (!list_empty(list)) __list_splice(list, head); } +static inline void list_splice_tail(struct list_head *list, struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head->prev); +} + /** - * 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. + * Join two lists and reinitialise the emptied list. + * \param list the new list to add. + * \param head the place to add it in the first list. * - * The list at @list is reinitialised + * The contents of \a list are added at the start of \a head. \a list is empty + * on return. */ static inline void list_splice_init(struct list_head *list, - struct list_head *head) + struct list_head *head) { if (!list_empty(list)) { __list_splice(list, head); - CFS_INIT_LIST_HEAD(list); + 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. + * Get the container of a list + * \param ptr the embedded list. + * \param type the type of the struct this is embedded in. + * \param member the member name of the list within the struct. */ #define list_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(char *)(&((type *)0)->member))) /** - * list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. + * Iterate over a list + * \param pos the iterator + * \param head the list to iterate over + * + * Behaviour is undefined if \a pos is removed from the list in the body of the + * loop. */ #define list_for_each(pos, head) \ for (pos = (head)->next, prefetch(pos->next); pos != (head); \ pos = pos->next, prefetch(pos->next)) /** - * list_for_each_safe - iterate over a list safe against removal of list entry - * @pos: the &struct list_head to use as a loop counter. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. + * Iterate over a list safely + * \param pos the iterator + * \param n temporary storage + * \param head the list to iterate over + * + * This is safe to use if \a pos could be removed from the list in the body of + * the loop. */ #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) -/* +/** + * Iterate over a list continuing after existing point + * \param pos the type * to use as a loop counter + * \param head the list head + * \param member the name of the list_struct within the struct + */ +#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)) + +/** + * \defgroup hlist Hash List * 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). + * 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). + * @{ */ +struct hlist_node { + struct hlist_node *next, **pprev; +}; + struct hlist_head { struct hlist_node *first; }; -struct hlist_node { - struct hlist_node *next, **pprev; -}; +/* @} */ /* * "NULL" might not be defined at this point @@ -249,15 +305,15 @@ struct hlist_node { #define NULL_P ((void *)0) #endif -#define CFS_HLIST_HEAD_INIT { NULL_P } -#define CFS_HLIST_HEAD(name) struct hlist_head name = { NULL_P } -#define CFS_INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P) -#define CFS_INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P) +/** + * \addtogroup hlist + * @{ + */ -#define HLIST_HEAD_INIT CFS_HLIST_HEAD_INIT -#define HLIST_HEAD(n) CFS_HLIST_HEAD(n) -#define INIT_HLIST_HEAD(p) CFS_INIT_HLIST_HEAD(p) -#define INIT_HLIST_NODE(p) CFS_INIT_HLIST_NODE(p) +#define HLIST_HEAD_INIT { NULL_P } +#define HLIST_HEAD(name) struct hlist_head name = { NULL_P } +#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL_P) +#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL_P, (ptr)->pprev = NULL_P) static inline int hlist_unhashed(const struct hlist_node *h) { @@ -291,7 +347,8 @@ static inline void hlist_del_init(struct hlist_node *n) } } -static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) +static inline void hlist_add_head(struct hlist_node *n, + struct hlist_head *h) { struct hlist_node *first = h->first; n->next = first; @@ -312,7 +369,7 @@ static inline void hlist_add_before(struct hlist_node *n, } static inline void hlist_add_after(struct hlist_node *n, - struct hlist_node *next) + struct hlist_node *next) { next->next = n->next; n->next = next; @@ -333,162 +390,123 @@ static inline void hlist_add_after(struct hlist_node *n, pos = n) /** - * hlist_for_each_entry - iterate over list of given type - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @head: the head for your list. - * @member: the name of the hlist_node within the struct. + * Iterate over an hlist of given type + * \param tpos the type * to use as a loop counter. + * \param pos the &struct hlist_node to use as a loop counter. + * \param head the head for your list. + * \param 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;}) && \ +#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) /** - * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @member: the name of the hlist_node within the struct. + * Iterate over an hlist continuing after existing point + * \param tpos the type * to use as a loop counter. + * \param pos the &struct hlist_node to use as a loop counter. + * \param 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;}) && \ +#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) /** - * hlist_for_each_entry_from - iterate over a hlist continuing from existing point - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @member: the name of the hlist_node within the struct. + * Iterate over an hlist continuing from an existing point + * \param tpos the type * to use as a loop counter. + * \param pos the &struct hlist_node to use as a loop counter. + * \param 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;}) && \ + 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 - * @tpos: the type * to use as a loop counter. - * @pos: the &struct hlist_node to use as a loop counter. - * @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. + * Iterate over an hlist of given type safe against removal of list entry + * \param tpos the type * to use as a loop counter. + * \param pos the &struct hlist_node to use as a loop counter. + * \param n another &struct hlist_node to use as temporary storage + * \param head the head for your list. + * \param 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; }) && \ +#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 /* __linux__ && __KERNEL__ */ +/* @} */ -#ifndef list_for_each_prev /** - * list_for_each_prev - iterate over a list in reverse order - * @pos: the &struct list_head to use as a loop counter. - * @head: the head for your list. + * Iterate over a list in reverse order + * \param pos the &struct list_head to use as a loop counter. + * \param 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, prefetch(pos->prev)) -#endif /* list_for_each_prev */ - -#ifndef list_for_each_entry /** - * list_for_each_entry - iterate over list of given type - * @pos: the type * to use as a loop counter. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. + * Iterate over a list of given type + * \param pos the type * to use as a loop counter. + * \param head the head for your list. + * \param 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), \ +#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), \ prefetch(pos->member.next)) -#endif /* list_for_each_entry */ -#ifndef list_for_each_entry_reverse /** - * list_for_each_entry_reverse - iterate backwards over list of given type. - * @pos: the type * to use as a loop counter. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. + * Iterate backwards over a list of given type. + * \param pos the type * to use as a loop counter. + * \param head the head for your list. + * \param 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); \ + prefetch(pos->member.prev), &pos->member != (head); \ pos = list_entry(pos->member.prev, typeof(*pos), member)) -#endif /* list_for_each_entry_reverse */ -#ifndef list_for_each_entry_safe /** - * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry - * @pos: the type * to use as a loop counter. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. + * Iterate over a list of given type safe against removal of list entry + * \param pos the type * to use as a loop counter. + * \param n another type * to use as temporary storage + * \param head the head for your list. + * \param 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); \ +#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)) -#endif /* list_for_each_entry_safe */ - -#ifndef list_for_each_entry_safe_from -/** - * list_for_each_entry_safe_from - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type from current point, safe against - * removal of list entry. - */ -#define list_for_each_entry_safe_from(pos, n, head, member) \ - for (n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) -#endif /* list_for_each_entry_safe_from */ - -#define cfs_list_for_each_entry_typed(pos, head, type, member) \ - for (pos = list_entry((head)->next, type, member), \ - prefetch(pos->member.next); \ - &pos->member != (head); \ - pos = list_entry(pos->member.next, type, member), \ - prefetch(pos->member.next)) - -#define cfs_list_for_each_entry_reverse_typed(pos, head, type, member) \ - for (pos = list_entry((head)->prev, type, member); \ - prefetch(pos->member.prev), &pos->member != (head); \ - pos = list_entry(pos->member.prev, type, member)) - -#define cfs_list_for_each_entry_safe_typed(pos, n, head, type, member) \ - for (pos = list_entry((head)->next, type, member), \ - n = list_entry(pos->member.next, type, member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, type, member)) - -#define cfs_list_for_each_entry_safe_from_typed(pos, n, head, type, member) \ - for (n = list_entry(pos->member.next, type, member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, type, member)) -#define cfs_hlist_for_each_entry_typed(tpos, pos, head, type, member) \ - for (pos = (head)->first; \ - pos && (prefetch(pos->next), 1) && \ - (tpos = hlist_entry(pos, type, member), 1); \ - pos = pos->next) - -#define cfs_hlist_for_each_entry_safe_typed(tpos, pos, n, head, type, member)\ - for (pos = (head)->first; \ - pos && (n = pos->next, 1) && \ - (tpos = hlist_entry(pos, type, member), 1); \ - pos = n) +#endif /* __KERNEL__ */ + +#ifdef HAVE_HLIST_FOR_EACH_3ARG +#define cfs_hlist_for_each_entry(tpos, pos, head, member) \ + hlist_for_each_entry(tpos, head, member) +#define cfs_hlist_for_each_entry_safe(tpos, pos, n, head, member) \ + hlist_for_each_entry_safe(tpos, n, head, member) +#define cfs_hlist_for_each_entry_continue(tpos, pos, member) \ + hlist_for_each_entry_continue(tpos, member) +#define cfs_hlist_for_each_entry_from(tpos, pos, member) \ + hlist_for_each_entry_from(tpos, member) +#else +#define cfs_hlist_for_each_entry(tpos, pos, head, member) \ + hlist_for_each_entry(tpos, pos, head, member) +#define cfs_hlist_for_each_entry_safe(tpos, pos, n, head, member) \ + hlist_for_each_entry_safe(tpos, pos, n, head, member) +#define cfs_hlist_for_each_entry_continue(tpos, pos, member) \ + hlist_for_each_entry_continue(tpos, pos, member) +#define cfs_hlist_for_each_entry_from(tpos, pos, member) \ + hlist_for_each_entry_from(tpos, pos, member) +#endif #endif /* __LIBCFS_LUSTRE_LIST_H__ */