diff options
Diffstat (limited to 'libglusterfs/src/glusterfs/list.h')
-rw-r--r-- | libglusterfs/src/glusterfs/list.h | 273 |
1 files changed, 273 insertions, 0 deletions
diff --git a/libglusterfs/src/glusterfs/list.h b/libglusterfs/src/glusterfs/list.h new file mode 100644 index 00000000000..221a710ca30 --- /dev/null +++ b/libglusterfs/src/glusterfs/list.h @@ -0,0 +1,273 @@ +/* + Copyright (c) 2008-2012 Red Hat, Inc. <http://www.redhat.com> + This file is part of GlusterFS. + + This file is licensed to you under your choice of the GNU Lesser + General Public License, version 3 or any later version (LGPLv3 or + later), or the GNU General Public License, version 2 (GPLv2), in all + cases as published by the Free Software Foundation. +*/ + +#ifndef _LLIST_H +#define _LLIST_H + +struct list_head { + struct list_head *next; + struct list_head *prev; +}; + +#define INIT_LIST_HEAD(head) \ + do { \ + (head)->next = (head)->prev = head; \ + } while (0) + +static inline void +list_add(struct list_head *new, struct list_head *head) +{ + new->prev = head; + new->next = head->next; + + new->prev->next = new; + new->next->prev = new; +} + +static inline void +list_add_tail(struct list_head *new, struct list_head *head) +{ + new->next = head; + new->prev = head->prev; + + new->prev->next = new; + new->next->prev = new; +} + +/* This function will insert the element to the list in a order. + Order will be based on the compare function provided as a input. + If element to be inserted in ascending order compare should return: + 0: if both the arguments are equal + >0: if first argument is greater than second argument + <0: if first argument is less than second argument */ +static inline void +list_add_order(struct list_head *new, struct list_head *head, + int (*compare)(struct list_head *, struct list_head *)) +{ + struct list_head *pos = head->prev; + + while (pos != head) { + if (compare(new, pos) >= 0) + break; + + /* Iterate the list in the reverse order. This will have + better efficiency if the elements are inserted in the + ascending order */ + pos = pos->prev; + } + + list_add(new, pos); +} + +static inline void +list_del(struct list_head *old) +{ + old->prev->next = old->next; + old->next->prev = old->prev; + + old->next = (void *)0xbabebabe; + old->prev = (void *)0xcafecafe; +} + +static inline void +list_del_init(struct list_head *old) +{ + old->prev->next = old->next; + old->next->prev = old->prev; + + old->next = old; + old->prev = old; +} + +static inline void +list_move(struct list_head *list, struct list_head *head) +{ + list_del(list); + list_add(list, head); +} + +static inline void +list_move_tail(struct list_head *list, struct list_head *head) +{ + list_del(list); + list_add_tail(list, head); +} + +static inline int +list_empty(struct list_head *head) +{ + return (head->next == head); +} + +static inline void +__list_splice(struct list_head *list, struct list_head *head) +{ + (list->prev)->next = (head->next); + (head->next)->prev = (list->prev); + + (head)->next = (list->next); + (list->next)->prev = (head); +} + +static inline void +list_splice(struct list_head *list, struct list_head *head) +{ + if (list_empty(list)) + return; + + __list_splice(list, head); +} + +/* Splice moves @list to the head of the list at @head. */ +static inline void +list_splice_init(struct list_head *list, struct list_head *head) +{ + if (list_empty(list)) + return; + + __list_splice(list, head); + INIT_LIST_HEAD(list); +} + +static inline void +__list_append(struct list_head *list, struct list_head *head) +{ + (head->prev)->next = (list->next); + (list->next)->prev = (head->prev); + (head->prev) = (list->prev); + (list->prev)->next = head; +} + +static inline void +list_append(struct list_head *list, struct list_head *head) +{ + if (list_empty(list)) + return; + + __list_append(list, head); +} + +/* Append moves @list to the end of @head */ +static inline void +list_append_init(struct list_head *list, struct list_head *head) +{ + if (list_empty(list)) + return; + + __list_append(list, head); + INIT_LIST_HEAD(list); +} + +static inline int +list_is_last(struct list_head *list, struct list_head *head) +{ + return (list->next == head); +} + +static inline int +list_is_singular(struct list_head *head) +{ + return !list_empty(head) && (head->next == head->prev); +} + +/** + * list_replace - replace old entry by new one + * @old : the element to be replaced + * @new : the new element to insert + * + * If @old was empty, it will be overwritten. + */ +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); +} + +/** + * 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); + } +} + +#define list_entry(ptr, type, member) \ + ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))) + +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +#define list_last_entry(ptr, type, member) list_entry((ptr)->prev, type, member) + +#define list_next_entry(pos, member) \ + list_entry((pos)->member.next, typeof(*(pos)), member) + +#define list_prev_entry(pos, member) \ + list_entry((pos)->member.prev, typeof(*(pos)), member) + +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +#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)) + +#define list_for_each_entry_reverse(pos, head, member) \ + for (pos = list_entry((head)->prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.prev, typeof(*pos), member)) + +#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)) + +/* + * This list implementation has some advantages, but one disadvantage: you + * can't use NULL to check whether you're at the head or tail. Thus, the + * address of the head has to be an argument for these macros. + */ + +#define list_next(ptr, head, type, member) \ + (((ptr)->member.next == head) \ + ? NULL \ + : list_entry((ptr)->member.next, type, member)) + +#define list_prev(ptr, head, type, member) \ + (((ptr)->member.prev == head) \ + ? NULL \ + : list_entry((ptr)->member.prev, type, member)) + +#endif /* _LLIST_H */ |