1aae69bed019826ddec93f761514652a93d871e49Harald Welte#ifndef _LINUX_LIST_H 2aae69bed019826ddec93f761514652a93d871e49Harald Welte#define _LINUX_LIST_H 3aae69bed019826ddec93f761514652a93d871e49Harald Welte 4aae69bed019826ddec93f761514652a93d871e49Harald Welte#undef offsetof 5aae69bed019826ddec93f761514652a93d871e49Harald Welte#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 6aae69bed019826ddec93f761514652a93d871e49Harald Welte 7aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 8aae69bed019826ddec93f761514652a93d871e49Harald Welte * container_of - cast a member of a structure out to the containing structure 9aae69bed019826ddec93f761514652a93d871e49Harald Welte * 10aae69bed019826ddec93f761514652a93d871e49Harald Welte * @ptr: the pointer to the member. 11aae69bed019826ddec93f761514652a93d871e49Harald Welte * @type: the type of the container struct this is embedded in. 12aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the member within the struct. 13aae69bed019826ddec93f761514652a93d871e49Harald Welte * 14aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 15aae69bed019826ddec93f761514652a93d871e49Harald Welte#define container_of(ptr, type, member) ({ \ 16aae69bed019826ddec93f761514652a93d871e49Harald Welte const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 17aae69bed019826ddec93f761514652a93d871e49Harald Welte (type *)( (char *)__mptr - offsetof(type,member) );}) 18aae69bed019826ddec93f761514652a93d871e49Harald Welte 19aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 20aae69bed019826ddec93f761514652a93d871e49Harald Welte * Check at compile time that something is of a particular type. 21aae69bed019826ddec93f761514652a93d871e49Harald Welte * Always evaluates to 1 so you may use it easily in comparisons. 22aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 23aae69bed019826ddec93f761514652a93d871e49Harald Welte#define typecheck(type,x) \ 24aae69bed019826ddec93f761514652a93d871e49Harald Welte({ type __dummy; \ 25aae69bed019826ddec93f761514652a93d871e49Harald Welte typeof(x) __dummy2; \ 26aae69bed019826ddec93f761514652a93d871e49Harald Welte (void)(&__dummy == &__dummy2); \ 27aae69bed019826ddec93f761514652a93d871e49Harald Welte 1; \ 28aae69bed019826ddec93f761514652a93d871e49Harald Welte}) 29aae69bed019826ddec93f761514652a93d871e49Harald Welte 30aae69bed019826ddec93f761514652a93d871e49Harald Welte#define prefetch(x) 1 31aae69bed019826ddec93f761514652a93d871e49Harald Welte 32aae69bed019826ddec93f761514652a93d871e49Harald Welte/* empty define to make this work in userspace -HW */ 33aae69bed019826ddec93f761514652a93d871e49Harald Welte#define smp_wmb() 34aae69bed019826ddec93f761514652a93d871e49Harald Welte 35aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 36aae69bed019826ddec93f761514652a93d871e49Harald Welte * These are non-NULL pointers that will result in page faults 37aae69bed019826ddec93f761514652a93d871e49Harald Welte * under normal circumstances, used to verify that nobody uses 38aae69bed019826ddec93f761514652a93d871e49Harald Welte * non-initialized list entries. 39aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 40aae69bed019826ddec93f761514652a93d871e49Harald Welte#define LIST_POISON1 ((void *) 0x00100100) 41aae69bed019826ddec93f761514652a93d871e49Harald Welte#define LIST_POISON2 ((void *) 0x00200200) 42aae69bed019826ddec93f761514652a93d871e49Harald Welte 43aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 44aae69bed019826ddec93f761514652a93d871e49Harald Welte * Simple doubly linked list implementation. 45aae69bed019826ddec93f761514652a93d871e49Harald Welte * 46aae69bed019826ddec93f761514652a93d871e49Harald Welte * Some of the internal functions ("__xxx") are useful when 47aae69bed019826ddec93f761514652a93d871e49Harald Welte * manipulating whole lists rather than single entries, as 48aae69bed019826ddec93f761514652a93d871e49Harald Welte * sometimes we already know the next/prev entries and we can 49aae69bed019826ddec93f761514652a93d871e49Harald Welte * generate better code by using them directly rather than 50aae69bed019826ddec93f761514652a93d871e49Harald Welte * using the generic single-entry routines. 51aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 52aae69bed019826ddec93f761514652a93d871e49Harald Welte 53aae69bed019826ddec93f761514652a93d871e49Harald Weltestruct list_head { 54aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *next, *prev; 55aae69bed019826ddec93f761514652a93d871e49Harald Welte}; 56aae69bed019826ddec93f761514652a93d871e49Harald Welte 57aae69bed019826ddec93f761514652a93d871e49Harald Welte#define LIST_HEAD_INIT(name) { &(name), &(name) } 58aae69bed019826ddec93f761514652a93d871e49Harald Welte 59aae69bed019826ddec93f761514652a93d871e49Harald Welte#define LIST_HEAD(name) \ 60aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head name = LIST_HEAD_INIT(name) 61aae69bed019826ddec93f761514652a93d871e49Harald Welte 62aae69bed019826ddec93f761514652a93d871e49Harald Welte#define INIT_LIST_HEAD(ptr) do { \ 63aae69bed019826ddec93f761514652a93d871e49Harald Welte (ptr)->next = (ptr); (ptr)->prev = (ptr); \ 64aae69bed019826ddec93f761514652a93d871e49Harald Welte} while (0) 65aae69bed019826ddec93f761514652a93d871e49Harald Welte 66aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 67aae69bed019826ddec93f761514652a93d871e49Harald Welte * Insert a new entry between two known consecutive entries. 68aae69bed019826ddec93f761514652a93d871e49Harald Welte * 69aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is only for internal list manipulation where we know 70aae69bed019826ddec93f761514652a93d871e49Harald Welte * the prev/next entries already! 71aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 72aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void __list_add(struct list_head *new, 73aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *prev, 74aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *next) 75aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 76aae69bed019826ddec93f761514652a93d871e49Harald Welte next->prev = new; 77aae69bed019826ddec93f761514652a93d871e49Harald Welte new->next = next; 78aae69bed019826ddec93f761514652a93d871e49Harald Welte new->prev = prev; 79aae69bed019826ddec93f761514652a93d871e49Harald Welte prev->next = new; 80aae69bed019826ddec93f761514652a93d871e49Harald Welte} 81aae69bed019826ddec93f761514652a93d871e49Harald Welte 82aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 83aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_add - add a new entry 84aae69bed019826ddec93f761514652a93d871e49Harald Welte * @new: new entry to be added 85aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: list head to add it after 86aae69bed019826ddec93f761514652a93d871e49Harald Welte * 87aae69bed019826ddec93f761514652a93d871e49Harald Welte * Insert a new entry after the specified head. 88aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is good for implementing stacks. 89aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 90aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_add(struct list_head *new, struct list_head *head) 91aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 92aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_add(new, head, head->next); 93aae69bed019826ddec93f761514652a93d871e49Harald Welte} 94aae69bed019826ddec93f761514652a93d871e49Harald Welte 95aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 96aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_add_tail - add a new entry 97aae69bed019826ddec93f761514652a93d871e49Harald Welte * @new: new entry to be added 98aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: list head to add it before 99aae69bed019826ddec93f761514652a93d871e49Harald Welte * 100aae69bed019826ddec93f761514652a93d871e49Harald Welte * Insert a new entry before the specified head. 101aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is useful for implementing queues. 102aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 103aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_add_tail(struct list_head *new, struct list_head *head) 104aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 105aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_add(new, head->prev, head); 106aae69bed019826ddec93f761514652a93d871e49Harald Welte} 107aae69bed019826ddec93f761514652a93d871e49Harald Welte 108aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 109aae69bed019826ddec93f761514652a93d871e49Harald Welte * Insert a new entry between two known consecutive entries. 110aae69bed019826ddec93f761514652a93d871e49Harald Welte * 111aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is only for internal list manipulation where we know 112aae69bed019826ddec93f761514652a93d871e49Harald Welte * the prev/next entries already! 113aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 114aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void __list_add_rcu(struct list_head * new, 115aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head * prev, struct list_head * next) 116aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 117aae69bed019826ddec93f761514652a93d871e49Harald Welte new->next = next; 118aae69bed019826ddec93f761514652a93d871e49Harald Welte new->prev = prev; 119aae69bed019826ddec93f761514652a93d871e49Harald Welte smp_wmb(); 120aae69bed019826ddec93f761514652a93d871e49Harald Welte next->prev = new; 121aae69bed019826ddec93f761514652a93d871e49Harald Welte prev->next = new; 122aae69bed019826ddec93f761514652a93d871e49Harald Welte} 123aae69bed019826ddec93f761514652a93d871e49Harald Welte 124aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 125aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_add_rcu - add a new entry to rcu-protected list 126aae69bed019826ddec93f761514652a93d871e49Harald Welte * @new: new entry to be added 127aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: list head to add it after 128aae69bed019826ddec93f761514652a93d871e49Harald Welte * 129aae69bed019826ddec93f761514652a93d871e49Harald Welte * Insert a new entry after the specified head. 130aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is good for implementing stacks. 131aae69bed019826ddec93f761514652a93d871e49Harald Welte * 132aae69bed019826ddec93f761514652a93d871e49Harald Welte * The caller must take whatever precautions are necessary 133aae69bed019826ddec93f761514652a93d871e49Harald Welte * (such as holding appropriate locks) to avoid racing 134aae69bed019826ddec93f761514652a93d871e49Harald Welte * with another list-mutation primitive, such as list_add_rcu() 135aae69bed019826ddec93f761514652a93d871e49Harald Welte * or list_del_rcu(), running on this same list. 136aae69bed019826ddec93f761514652a93d871e49Harald Welte * However, it is perfectly legal to run concurrently with 137aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-traversal primitives, such as 138aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_rcu(). 139aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 140aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_add_rcu(struct list_head *new, struct list_head *head) 141aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 142aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_add_rcu(new, head, head->next); 143aae69bed019826ddec93f761514652a93d871e49Harald Welte} 144aae69bed019826ddec93f761514652a93d871e49Harald Welte 145aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 146aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_add_tail_rcu - add a new entry to rcu-protected list 147aae69bed019826ddec93f761514652a93d871e49Harald Welte * @new: new entry to be added 148aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: list head to add it before 149aae69bed019826ddec93f761514652a93d871e49Harald Welte * 150aae69bed019826ddec93f761514652a93d871e49Harald Welte * Insert a new entry before the specified head. 151aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is useful for implementing queues. 152aae69bed019826ddec93f761514652a93d871e49Harald Welte * 153aae69bed019826ddec93f761514652a93d871e49Harald Welte * The caller must take whatever precautions are necessary 154aae69bed019826ddec93f761514652a93d871e49Harald Welte * (such as holding appropriate locks) to avoid racing 155aae69bed019826ddec93f761514652a93d871e49Harald Welte * with another list-mutation primitive, such as list_add_tail_rcu() 156aae69bed019826ddec93f761514652a93d871e49Harald Welte * or list_del_rcu(), running on this same list. 157aae69bed019826ddec93f761514652a93d871e49Harald Welte * However, it is perfectly legal to run concurrently with 158aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-traversal primitives, such as 159aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_rcu(). 160aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 161aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_add_tail_rcu(struct list_head *new, 162aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *head) 163aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 164aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_add_rcu(new, head->prev, head); 165aae69bed019826ddec93f761514652a93d871e49Harald Welte} 166aae69bed019826ddec93f761514652a93d871e49Harald Welte 167aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 168aae69bed019826ddec93f761514652a93d871e49Harald Welte * Delete a list entry by making the prev/next entries 169aae69bed019826ddec93f761514652a93d871e49Harald Welte * point to each other. 170aae69bed019826ddec93f761514652a93d871e49Harald Welte * 171aae69bed019826ddec93f761514652a93d871e49Harald Welte * This is only for internal list manipulation where we know 172aae69bed019826ddec93f761514652a93d871e49Harald Welte * the prev/next entries already! 173aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 174aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void __list_del(struct list_head * prev, struct list_head * next) 175aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 176aae69bed019826ddec93f761514652a93d871e49Harald Welte next->prev = prev; 177aae69bed019826ddec93f761514652a93d871e49Harald Welte prev->next = next; 178aae69bed019826ddec93f761514652a93d871e49Harald Welte} 179aae69bed019826ddec93f761514652a93d871e49Harald Welte 180aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 181aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_del - deletes entry from list. 182aae69bed019826ddec93f761514652a93d871e49Harald Welte * @entry: the element to delete from the list. 183aae69bed019826ddec93f761514652a93d871e49Harald Welte * Note: list_empty on entry does not return true after this, the entry is 184aae69bed019826ddec93f761514652a93d871e49Harald Welte * in an undefined state. 185aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 186aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_del(struct list_head *entry) 187aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 188aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_del(entry->prev, entry->next); 189aae69bed019826ddec93f761514652a93d871e49Harald Welte entry->next = LIST_POISON1; 190aae69bed019826ddec93f761514652a93d871e49Harald Welte entry->prev = LIST_POISON2; 191aae69bed019826ddec93f761514652a93d871e49Harald Welte} 192aae69bed019826ddec93f761514652a93d871e49Harald Welte 193aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 194aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_del_rcu - deletes entry from list without re-initialization 195aae69bed019826ddec93f761514652a93d871e49Harald Welte * @entry: the element to delete from the list. 196aae69bed019826ddec93f761514652a93d871e49Harald Welte * 197aae69bed019826ddec93f761514652a93d871e49Harald Welte * Note: list_empty on entry does not return true after this, 198aae69bed019826ddec93f761514652a93d871e49Harald Welte * the entry is in an undefined state. It is useful for RCU based 199aae69bed019826ddec93f761514652a93d871e49Harald Welte * lockfree traversal. 200aae69bed019826ddec93f761514652a93d871e49Harald Welte * 201aae69bed019826ddec93f761514652a93d871e49Harald Welte * In particular, it means that we can not poison the forward 202aae69bed019826ddec93f761514652a93d871e49Harald Welte * pointers that may still be used for walking the list. 203aae69bed019826ddec93f761514652a93d871e49Harald Welte * 204aae69bed019826ddec93f761514652a93d871e49Harald Welte * The caller must take whatever precautions are necessary 205aae69bed019826ddec93f761514652a93d871e49Harald Welte * (such as holding appropriate locks) to avoid racing 206aae69bed019826ddec93f761514652a93d871e49Harald Welte * with another list-mutation primitive, such as list_del_rcu() 207aae69bed019826ddec93f761514652a93d871e49Harald Welte * or list_add_rcu(), running on this same list. 208aae69bed019826ddec93f761514652a93d871e49Harald Welte * However, it is perfectly legal to run concurrently with 209aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-traversal primitives, such as 210aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_rcu(). 211aae69bed019826ddec93f761514652a93d871e49Harald Welte * 212aae69bed019826ddec93f761514652a93d871e49Harald Welte * Note that the caller is not permitted to immediately free 213aae69bed019826ddec93f761514652a93d871e49Harald Welte * the newly deleted entry. Instead, either synchronize_kernel() 214aae69bed019826ddec93f761514652a93d871e49Harald Welte * or call_rcu() must be used to defer freeing until an RCU 215aae69bed019826ddec93f761514652a93d871e49Harald Welte * grace period has elapsed. 216aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 217aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_del_rcu(struct list_head *entry) 218aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 219aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_del(entry->prev, entry->next); 220aae69bed019826ddec93f761514652a93d871e49Harald Welte entry->prev = LIST_POISON2; 221aae69bed019826ddec93f761514652a93d871e49Harald Welte} 222aae69bed019826ddec93f761514652a93d871e49Harald Welte 223aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 224aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_del_init - deletes entry from list and reinitialize it. 225aae69bed019826ddec93f761514652a93d871e49Harald Welte * @entry: the element to delete from the list. 226aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 227aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_del_init(struct list_head *entry) 228aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 229aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_del(entry->prev, entry->next); 230aae69bed019826ddec93f761514652a93d871e49Harald Welte INIT_LIST_HEAD(entry); 231aae69bed019826ddec93f761514652a93d871e49Harald Welte} 232aae69bed019826ddec93f761514652a93d871e49Harald Welte 233aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 234aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_move - delete from one list and add as another's head 235aae69bed019826ddec93f761514652a93d871e49Harald Welte * @list: the entry to move 236aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head that will precede our entry 237aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 238aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_move(struct list_head *list, struct list_head *head) 239aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 240aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_del(list->prev, list->next); 241aae69bed019826ddec93f761514652a93d871e49Harald Welte list_add(list, head); 242aae69bed019826ddec93f761514652a93d871e49Harald Welte} 243aae69bed019826ddec93f761514652a93d871e49Harald Welte 244aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 245aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_move_tail - delete from one list and add as another's tail 246aae69bed019826ddec93f761514652a93d871e49Harald Welte * @list: the entry to move 247aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head that will follow our entry 248aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 249aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_move_tail(struct list_head *list, 250aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *head) 251aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 252aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_del(list->prev, list->next); 253aae69bed019826ddec93f761514652a93d871e49Harald Welte list_add_tail(list, head); 254aae69bed019826ddec93f761514652a93d871e49Harald Welte} 255aae69bed019826ddec93f761514652a93d871e49Harald Welte 256aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 257aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_empty - tests whether a list is empty 258aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the list to test. 259aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 260aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline int list_empty(const struct list_head *head) 261aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 262aae69bed019826ddec93f761514652a93d871e49Harald Welte return head->next == head; 263aae69bed019826ddec93f761514652a93d871e49Harald Welte} 264aae69bed019826ddec93f761514652a93d871e49Harald Welte 265aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 266aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_empty_careful - tests whether a list is 267aae69bed019826ddec93f761514652a93d871e49Harald Welte * empty _and_ checks that no other CPU might be 268aae69bed019826ddec93f761514652a93d871e49Harald Welte * in the process of still modifying either member 269aae69bed019826ddec93f761514652a93d871e49Harald Welte * 270aae69bed019826ddec93f761514652a93d871e49Harald Welte * NOTE: using list_empty_careful() without synchronization 271aae69bed019826ddec93f761514652a93d871e49Harald Welte * can only be safe if the only activity that can happen 272aae69bed019826ddec93f761514652a93d871e49Harald Welte * to the list entry is list_del_init(). Eg. it cannot be used 273aae69bed019826ddec93f761514652a93d871e49Harald Welte * if another CPU could re-list_add() it. 274aae69bed019826ddec93f761514652a93d871e49Harald Welte * 275aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the list to test. 276aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 277aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline int list_empty_careful(const struct list_head *head) 278aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 279aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *next = head->next; 280aae69bed019826ddec93f761514652a93d871e49Harald Welte return (next == head) && (next == head->prev); 281aae69bed019826ddec93f761514652a93d871e49Harald Welte} 282aae69bed019826ddec93f761514652a93d871e49Harald Welte 283aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void __list_splice(struct list_head *list, 284aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *head) 285aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 286aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *first = list->next; 287aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *last = list->prev; 288aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *at = head->next; 289aae69bed019826ddec93f761514652a93d871e49Harald Welte 290aae69bed019826ddec93f761514652a93d871e49Harald Welte first->prev = head; 291aae69bed019826ddec93f761514652a93d871e49Harald Welte head->next = first; 292aae69bed019826ddec93f761514652a93d871e49Harald Welte 293aae69bed019826ddec93f761514652a93d871e49Harald Welte last->next = at; 294aae69bed019826ddec93f761514652a93d871e49Harald Welte at->prev = last; 295aae69bed019826ddec93f761514652a93d871e49Harald Welte} 296aae69bed019826ddec93f761514652a93d871e49Harald Welte 297aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 298aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_splice - join two lists 299aae69bed019826ddec93f761514652a93d871e49Harald Welte * @list: the new list to add. 300aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the place to add it in the first list. 301aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 302aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_splice(struct list_head *list, struct list_head *head) 303aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 304aae69bed019826ddec93f761514652a93d871e49Harald Welte if (!list_empty(list)) 305aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_splice(list, head); 306aae69bed019826ddec93f761514652a93d871e49Harald Welte} 307aae69bed019826ddec93f761514652a93d871e49Harald Welte 308aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 309aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_splice_init - join two lists and reinitialise the emptied list. 310aae69bed019826ddec93f761514652a93d871e49Harald Welte * @list: the new list to add. 311aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the place to add it in the first list. 312aae69bed019826ddec93f761514652a93d871e49Harald Welte * 313aae69bed019826ddec93f761514652a93d871e49Harald Welte * The list at @list is reinitialised 314aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 315aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void list_splice_init(struct list_head *list, 316aae69bed019826ddec93f761514652a93d871e49Harald Welte struct list_head *head) 317aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 318aae69bed019826ddec93f761514652a93d871e49Harald Welte if (!list_empty(list)) { 319aae69bed019826ddec93f761514652a93d871e49Harald Welte __list_splice(list, head); 320aae69bed019826ddec93f761514652a93d871e49Harald Welte INIT_LIST_HEAD(list); 321aae69bed019826ddec93f761514652a93d871e49Harald Welte } 322aae69bed019826ddec93f761514652a93d871e49Harald Welte} 323aae69bed019826ddec93f761514652a93d871e49Harald Welte 324aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 325aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_entry - get the struct for this entry 326aae69bed019826ddec93f761514652a93d871e49Harald Welte * @ptr: the &struct list_head pointer. 327aae69bed019826ddec93f761514652a93d871e49Harald Welte * @type: the type of the struct this is embedded in. 328aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 329aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 330aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_entry(ptr, type, member) \ 331aae69bed019826ddec93f761514652a93d871e49Harald Welte container_of(ptr, type, member) 332aae69bed019826ddec93f761514652a93d871e49Harald Welte 333aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 334aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each - iterate over a list 335aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 336aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 337aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 338aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each(pos, head) \ 339aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->next, prefetch(pos->next); pos != (head); \ 340aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next, prefetch(pos->next)) 341aae69bed019826ddec93f761514652a93d871e49Harald Welte 342aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 343aae69bed019826ddec93f761514652a93d871e49Harald Welte * __list_for_each - iterate over a list 344aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 345aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 346aae69bed019826ddec93f761514652a93d871e49Harald Welte * 347aae69bed019826ddec93f761514652a93d871e49Harald Welte * This variant differs from list_for_each() in that it's the 348aae69bed019826ddec93f761514652a93d871e49Harald Welte * simplest possible list iteration code, no prefetching is done. 349aae69bed019826ddec93f761514652a93d871e49Harald Welte * Use this for code that knows the list to be very short (empty 350aae69bed019826ddec93f761514652a93d871e49Harald Welte * or 1 entry) most of the time. 351aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 352aae69bed019826ddec93f761514652a93d871e49Harald Welte#define __list_for_each(pos, head) \ 353aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->next; pos != (head); pos = pos->next) 354aae69bed019826ddec93f761514652a93d871e49Harald Welte 355aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 356aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_prev - iterate over a list backwards 357aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 358aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 359aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 360aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_prev(pos, head) \ 361aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \ 362aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->prev, prefetch(pos->prev)) 363aae69bed019826ddec93f761514652a93d871e49Harald Welte 364aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 365aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_safe - iterate over a list safe against removal of list entry 366aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 367aae69bed019826ddec93f761514652a93d871e49Harald Welte * @n: another &struct list_head to use as temporary storage 368aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 369aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 370aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_safe(pos, n, head) \ 371aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->next, n = pos->next; pos != (head); \ 372aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = n, n = pos->next) 373aae69bed019826ddec93f761514652a93d871e49Harald Welte 374aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 375aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry - iterate over list of given type 376aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a loop counter. 377aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 378aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 379aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 380aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_entry(pos, head, member) \ 381aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = list_entry((head)->next, typeof(*pos), member), \ 382aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.next); \ 383aae69bed019826ddec93f761514652a93d871e49Harald Welte &pos->member != (head); \ 384aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = list_entry(pos->member.next, typeof(*pos), member), \ 385aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.next)) 386aae69bed019826ddec93f761514652a93d871e49Harald Welte 387aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 388aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_reverse - iterate backwards over list of given type. 389aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a loop counter. 390aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 391aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 392aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 393aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_entry_reverse(pos, head, member) \ 394aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = list_entry((head)->prev, typeof(*pos), member), \ 395aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.prev); \ 396aae69bed019826ddec93f761514652a93d871e49Harald Welte &pos->member != (head); \ 397aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = list_entry(pos->member.prev, typeof(*pos), member), \ 398aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.prev)) 399aae69bed019826ddec93f761514652a93d871e49Harald Welte 400aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 401aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_prepare_entry - prepare a pos entry for use as a start point in 402aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_continue 403aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a start point 404aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head of the list 405aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 406aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 407aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_prepare_entry(pos, head, member) \ 408aae69bed019826ddec93f761514652a93d871e49Harald Welte ((pos) ? : list_entry(head, typeof(*pos), member)) 409aae69bed019826ddec93f761514652a93d871e49Harald Welte 410aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 411aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_continue - iterate over list of given type 412aae69bed019826ddec93f761514652a93d871e49Harald Welte * continuing after existing point 413aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a loop counter. 414aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 415aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 416aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 417aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_entry_continue(pos, head, member) \ 418aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = list_entry(pos->member.next, typeof(*pos), member), \ 419aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.next); \ 420aae69bed019826ddec93f761514652a93d871e49Harald Welte &pos->member != (head); \ 421aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = list_entry(pos->member.next, typeof(*pos), member), \ 422aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.next)) 423aae69bed019826ddec93f761514652a93d871e49Harald Welte 424aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 425aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry 426aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a loop counter. 427aae69bed019826ddec93f761514652a93d871e49Harald Welte * @n: another type * to use as temporary storage 428aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 429aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 430aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 431aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_entry_safe(pos, n, head, member) \ 432aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = list_entry((head)->next, typeof(*pos), member), \ 433aae69bed019826ddec93f761514652a93d871e49Harald Welte n = list_entry(pos->member.next, typeof(*pos), member); \ 434aae69bed019826ddec93f761514652a93d871e49Harald Welte &pos->member != (head); \ 435aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = n, n = list_entry(n->member.next, typeof(*n), member)) 436aae69bed019826ddec93f761514652a93d871e49Harald Welte 437aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 438aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_rcu - iterate over an rcu-protected list 439aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 440aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 441aae69bed019826ddec93f761514652a93d871e49Harald Welte * 442aae69bed019826ddec93f761514652a93d871e49Harald Welte * This list-traversal primitive may safely run concurrently with 443aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-mutation primitives such as list_add_rcu() 444aae69bed019826ddec93f761514652a93d871e49Harald Welte * as long as the traversal is guarded by rcu_read_lock(). 445aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 446aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_rcu(pos, head) \ 447aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->next, prefetch(pos->next); pos != (head); \ 448aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next, ({ smp_read_barrier_depends(); 0;}), prefetch(pos->next)) 449aae69bed019826ddec93f761514652a93d871e49Harald Welte 450aae69bed019826ddec93f761514652a93d871e49Harald Welte#define __list_for_each_rcu(pos, head) \ 451aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->next; pos != (head); \ 452aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next, ({ smp_read_barrier_depends(); 0;})) 453aae69bed019826ddec93f761514652a93d871e49Harald Welte 454aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 455aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_safe_rcu - iterate over an rcu-protected list safe 456aae69bed019826ddec93f761514652a93d871e49Harald Welte * against removal of list entry 457aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 458aae69bed019826ddec93f761514652a93d871e49Harald Welte * @n: another &struct list_head to use as temporary storage 459aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 460aae69bed019826ddec93f761514652a93d871e49Harald Welte * 461aae69bed019826ddec93f761514652a93d871e49Harald Welte * This list-traversal primitive may safely run concurrently with 462aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-mutation primitives such as list_add_rcu() 463aae69bed019826ddec93f761514652a93d871e49Harald Welte * as long as the traversal is guarded by rcu_read_lock(). 464aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 465aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_safe_rcu(pos, n, head) \ 466aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->next, n = pos->next; pos != (head); \ 467aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = n, ({ smp_read_barrier_depends(); 0;}), n = pos->next) 468aae69bed019826ddec93f761514652a93d871e49Harald Welte 469aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 470aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_entry_rcu - iterate over rcu list of given type 471aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a loop counter. 472aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 473aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the list_struct within the struct. 474aae69bed019826ddec93f761514652a93d871e49Harald Welte * 475aae69bed019826ddec93f761514652a93d871e49Harald Welte * This list-traversal primitive may safely run concurrently with 476aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-mutation primitives such as list_add_rcu() 477aae69bed019826ddec93f761514652a93d871e49Harald Welte * as long as the traversal is guarded by rcu_read_lock(). 478aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 479aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_entry_rcu(pos, head, member) \ 480aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = list_entry((head)->next, typeof(*pos), member), \ 481aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.next); \ 482aae69bed019826ddec93f761514652a93d871e49Harald Welte &pos->member != (head); \ 483aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = list_entry(pos->member.next, typeof(*pos), member), \ 484aae69bed019826ddec93f761514652a93d871e49Harald Welte ({ smp_read_barrier_depends(); 0;}), \ 485aae69bed019826ddec93f761514652a93d871e49Harald Welte prefetch(pos->member.next)) 486aae69bed019826ddec93f761514652a93d871e49Harald Welte 487aae69bed019826ddec93f761514652a93d871e49Harald Welte 488aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 489aae69bed019826ddec93f761514652a93d871e49Harald Welte * list_for_each_continue_rcu - iterate over an rcu-protected list 490aae69bed019826ddec93f761514652a93d871e49Harald Welte * continuing after existing point. 491aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct list_head to use as a loop counter. 492aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 493aae69bed019826ddec93f761514652a93d871e49Harald Welte * 494aae69bed019826ddec93f761514652a93d871e49Harald Welte * This list-traversal primitive may safely run concurrently with 495aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-mutation primitives such as list_add_rcu() 496aae69bed019826ddec93f761514652a93d871e49Harald Welte * as long as the traversal is guarded by rcu_read_lock(). 497aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 498aae69bed019826ddec93f761514652a93d871e49Harald Welte#define list_for_each_continue_rcu(pos, head) \ 499aae69bed019826ddec93f761514652a93d871e49Harald Welte for ((pos) = (pos)->next, prefetch((pos)->next); (pos) != (head); \ 500aae69bed019826ddec93f761514652a93d871e49Harald Welte (pos) = (pos)->next, ({ smp_read_barrier_depends(); 0;}), prefetch((pos)->next)) 501aae69bed019826ddec93f761514652a93d871e49Harald Welte 502aae69bed019826ddec93f761514652a93d871e49Harald Welte/* 503aae69bed019826ddec93f761514652a93d871e49Harald Welte * Double linked lists with a single pointer list head. 504aae69bed019826ddec93f761514652a93d871e49Harald Welte * Mostly useful for hash tables where the two pointer list head is 505aae69bed019826ddec93f761514652a93d871e49Harald Welte * too wasteful. 506aae69bed019826ddec93f761514652a93d871e49Harald Welte * You lose the ability to access the tail in O(1). 507aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 508aae69bed019826ddec93f761514652a93d871e49Harald Welte 509aae69bed019826ddec93f761514652a93d871e49Harald Weltestruct hlist_head { 510aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *first; 511aae69bed019826ddec93f761514652a93d871e49Harald Welte}; 512aae69bed019826ddec93f761514652a93d871e49Harald Welte 513aae69bed019826ddec93f761514652a93d871e49Harald Weltestruct hlist_node { 514aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *next, **pprev; 515aae69bed019826ddec93f761514652a93d871e49Harald Welte}; 516aae69bed019826ddec93f761514652a93d871e49Harald Welte 517aae69bed019826ddec93f761514652a93d871e49Harald Welte#define HLIST_HEAD_INIT { .first = NULL } 518aae69bed019826ddec93f761514652a93d871e49Harald Welte#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } 519aae69bed019826ddec93f761514652a93d871e49Harald Welte#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 520aae69bed019826ddec93f761514652a93d871e49Harald Welte#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL) 521aae69bed019826ddec93f761514652a93d871e49Harald Welte 522aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline int hlist_unhashed(const struct hlist_node *h) 523aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 524aae69bed019826ddec93f761514652a93d871e49Harald Welte return !h->pprev; 525aae69bed019826ddec93f761514652a93d871e49Harald Welte} 526aae69bed019826ddec93f761514652a93d871e49Harald Welte 527aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline int hlist_empty(const struct hlist_head *h) 528aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 529aae69bed019826ddec93f761514652a93d871e49Harald Welte return !h->first; 530aae69bed019826ddec93f761514652a93d871e49Harald Welte} 531aae69bed019826ddec93f761514652a93d871e49Harald Welte 532aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void __hlist_del(struct hlist_node *n) 533aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 534aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *next = n->next; 535aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node **pprev = n->pprev; 536aae69bed019826ddec93f761514652a93d871e49Harald Welte *pprev = next; 537aae69bed019826ddec93f761514652a93d871e49Harald Welte if (next) 538aae69bed019826ddec93f761514652a93d871e49Harald Welte next->pprev = pprev; 539aae69bed019826ddec93f761514652a93d871e49Harald Welte} 540aae69bed019826ddec93f761514652a93d871e49Harald Welte 541aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_del(struct hlist_node *n) 542aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 543aae69bed019826ddec93f761514652a93d871e49Harald Welte __hlist_del(n); 544aae69bed019826ddec93f761514652a93d871e49Harald Welte n->next = LIST_POISON1; 545aae69bed019826ddec93f761514652a93d871e49Harald Welte n->pprev = LIST_POISON2; 546aae69bed019826ddec93f761514652a93d871e49Harald Welte} 547aae69bed019826ddec93f761514652a93d871e49Harald Welte 548aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 549aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_del_rcu - deletes entry from hash list without re-initialization 550aae69bed019826ddec93f761514652a93d871e49Harald Welte * @n: the element to delete from the hash list. 551aae69bed019826ddec93f761514652a93d871e49Harald Welte * 552aae69bed019826ddec93f761514652a93d871e49Harald Welte * Note: list_unhashed() on entry does not return true after this, 553aae69bed019826ddec93f761514652a93d871e49Harald Welte * the entry is in an undefined state. It is useful for RCU based 554aae69bed019826ddec93f761514652a93d871e49Harald Welte * lockfree traversal. 555aae69bed019826ddec93f761514652a93d871e49Harald Welte * 556aae69bed019826ddec93f761514652a93d871e49Harald Welte * In particular, it means that we can not poison the forward 557aae69bed019826ddec93f761514652a93d871e49Harald Welte * pointers that may still be used for walking the hash list. 558aae69bed019826ddec93f761514652a93d871e49Harald Welte * 559aae69bed019826ddec93f761514652a93d871e49Harald Welte * The caller must take whatever precautions are necessary 560aae69bed019826ddec93f761514652a93d871e49Harald Welte * (such as holding appropriate locks) to avoid racing 561aae69bed019826ddec93f761514652a93d871e49Harald Welte * with another list-mutation primitive, such as hlist_add_head_rcu() 562aae69bed019826ddec93f761514652a93d871e49Harald Welte * or hlist_del_rcu(), running on this same list. 563aae69bed019826ddec93f761514652a93d871e49Harald Welte * However, it is perfectly legal to run concurrently with 564aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-traversal primitives, such as 565aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry(). 566aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 567aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_del_rcu(struct hlist_node *n) 568aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 569aae69bed019826ddec93f761514652a93d871e49Harald Welte __hlist_del(n); 570aae69bed019826ddec93f761514652a93d871e49Harald Welte n->pprev = LIST_POISON2; 571aae69bed019826ddec93f761514652a93d871e49Harald Welte} 572aae69bed019826ddec93f761514652a93d871e49Harald Welte 573aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_del_init(struct hlist_node *n) 574aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 575aae69bed019826ddec93f761514652a93d871e49Harald Welte if (n->pprev) { 576aae69bed019826ddec93f761514652a93d871e49Harald Welte __hlist_del(n); 577aae69bed019826ddec93f761514652a93d871e49Harald Welte INIT_HLIST_NODE(n); 578aae69bed019826ddec93f761514652a93d871e49Harald Welte } 579aae69bed019826ddec93f761514652a93d871e49Harald Welte} 580aae69bed019826ddec93f761514652a93d871e49Harald Welte 581aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_del_rcu_init hlist_del_init 582aae69bed019826ddec93f761514652a93d871e49Harald Welte 583aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 584aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 585aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *first = h->first; 586aae69bed019826ddec93f761514652a93d871e49Harald Welte n->next = first; 587aae69bed019826ddec93f761514652a93d871e49Harald Welte if (first) 588aae69bed019826ddec93f761514652a93d871e49Harald Welte first->pprev = &n->next; 589aae69bed019826ddec93f761514652a93d871e49Harald Welte h->first = n; 590aae69bed019826ddec93f761514652a93d871e49Harald Welte n->pprev = &h->first; 591aae69bed019826ddec93f761514652a93d871e49Harald Welte} 592aae69bed019826ddec93f761514652a93d871e49Harald Welte 593aae69bed019826ddec93f761514652a93d871e49Harald Welte 594aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 595aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_add_head_rcu - adds the specified element to the specified hlist, 596aae69bed019826ddec93f761514652a93d871e49Harald Welte * while permitting racing traversals. 597aae69bed019826ddec93f761514652a93d871e49Harald Welte * @n: the element to add to the hash list. 598aae69bed019826ddec93f761514652a93d871e49Harald Welte * @h: the list to add to. 599aae69bed019826ddec93f761514652a93d871e49Harald Welte * 600aae69bed019826ddec93f761514652a93d871e49Harald Welte * The caller must take whatever precautions are necessary 601aae69bed019826ddec93f761514652a93d871e49Harald Welte * (such as holding appropriate locks) to avoid racing 602aae69bed019826ddec93f761514652a93d871e49Harald Welte * with another list-mutation primitive, such as hlist_add_head_rcu() 603aae69bed019826ddec93f761514652a93d871e49Harald Welte * or hlist_del_rcu(), running on this same list. 604aae69bed019826ddec93f761514652a93d871e49Harald Welte * However, it is perfectly legal to run concurrently with 605aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-traversal primitives, such as 606aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry(), but only if smp_read_barrier_depends() 607aae69bed019826ddec93f761514652a93d871e49Harald Welte * is used to prevent memory-consistency problems on Alpha CPUs. 608aae69bed019826ddec93f761514652a93d871e49Harald Welte * Regardless of the type of CPU, the list-traversal primitive 609aae69bed019826ddec93f761514652a93d871e49Harald Welte * must be guarded by rcu_read_lock(). 610aae69bed019826ddec93f761514652a93d871e49Harald Welte * 611aae69bed019826ddec93f761514652a93d871e49Harald Welte * OK, so why don't we have an hlist_for_each_entry_rcu()??? 612aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 613aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_add_head_rcu(struct hlist_node *n, 614aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_head *h) 615aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 616aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *first = h->first; 617aae69bed019826ddec93f761514652a93d871e49Harald Welte n->next = first; 618aae69bed019826ddec93f761514652a93d871e49Harald Welte n->pprev = &h->first; 619aae69bed019826ddec93f761514652a93d871e49Harald Welte smp_wmb(); 620aae69bed019826ddec93f761514652a93d871e49Harald Welte if (first) 621aae69bed019826ddec93f761514652a93d871e49Harald Welte first->pprev = &n->next; 622aae69bed019826ddec93f761514652a93d871e49Harald Welte h->first = n; 623aae69bed019826ddec93f761514652a93d871e49Harald Welte} 624aae69bed019826ddec93f761514652a93d871e49Harald Welte 625aae69bed019826ddec93f761514652a93d871e49Harald Welte/* next must be != NULL */ 626aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_add_before(struct hlist_node *n, 627aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *next) 628aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 629aae69bed019826ddec93f761514652a93d871e49Harald Welte n->pprev = next->pprev; 630aae69bed019826ddec93f761514652a93d871e49Harald Welte n->next = next; 631aae69bed019826ddec93f761514652a93d871e49Harald Welte next->pprev = &n->next; 632aae69bed019826ddec93f761514652a93d871e49Harald Welte *(n->pprev) = n; 633aae69bed019826ddec93f761514652a93d871e49Harald Welte} 634aae69bed019826ddec93f761514652a93d871e49Harald Welte 635aae69bed019826ddec93f761514652a93d871e49Harald Weltestatic inline void hlist_add_after(struct hlist_node *n, 636aae69bed019826ddec93f761514652a93d871e49Harald Welte struct hlist_node *next) 637aae69bed019826ddec93f761514652a93d871e49Harald Welte{ 638aae69bed019826ddec93f761514652a93d871e49Harald Welte next->next = n->next; 639aae69bed019826ddec93f761514652a93d871e49Harald Welte n->next = next; 640aae69bed019826ddec93f761514652a93d871e49Harald Welte next->pprev = &n->next; 641aae69bed019826ddec93f761514652a93d871e49Harald Welte 642aae69bed019826ddec93f761514652a93d871e49Harald Welte if(next->next) 643aae69bed019826ddec93f761514652a93d871e49Harald Welte next->next->pprev = &next->next; 644aae69bed019826ddec93f761514652a93d871e49Harald Welte} 645aae69bed019826ddec93f761514652a93d871e49Harald Welte 646aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_entry(ptr, type, member) container_of(ptr,type,member) 647aae69bed019826ddec93f761514652a93d871e49Harald Welte 648aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each(pos, head) \ 649aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \ 650aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next) 651aae69bed019826ddec93f761514652a93d871e49Harald Welte 652aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each_safe(pos, n, head) \ 653aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \ 654aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = n) 655aae69bed019826ddec93f761514652a93d871e49Harald Welte 656aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 657aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry - iterate over list of given type 658aae69bed019826ddec93f761514652a93d871e49Harald Welte * @tpos: the type * to use as a loop counter. 659aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct hlist_node to use as a loop counter. 660aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 661aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the hlist_node within the struct. 662aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 663aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each_entry(tpos, pos, head, member) \ 664aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->first; \ 665aae69bed019826ddec93f761514652a93d871e49Harald Welte pos && ({ prefetch(pos->next); 1;}) && \ 666aae69bed019826ddec93f761514652a93d871e49Harald Welte ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 667aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next) 668aae69bed019826ddec93f761514652a93d871e49Harald Welte 669aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 670aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point 671aae69bed019826ddec93f761514652a93d871e49Harald Welte * @tpos: the type * to use as a loop counter. 672aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct hlist_node to use as a loop counter. 673aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the hlist_node within the struct. 674aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 675aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each_entry_continue(tpos, pos, member) \ 676aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (pos)->next; \ 677aae69bed019826ddec93f761514652a93d871e49Harald Welte pos && ({ prefetch(pos->next); 1;}) && \ 678aae69bed019826ddec93f761514652a93d871e49Harald Welte ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 679aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next) 680aae69bed019826ddec93f761514652a93d871e49Harald Welte 681aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 682aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry_from - iterate over a hlist continuing from existing point 683aae69bed019826ddec93f761514652a93d871e49Harald Welte * @tpos: the type * to use as a loop counter. 684aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct hlist_node to use as a loop counter. 685aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the hlist_node within the struct. 686aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 687aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each_entry_from(tpos, pos, member) \ 688aae69bed019826ddec93f761514652a93d871e49Harald Welte for (; pos && ({ prefetch(pos->next); 1;}) && \ 689aae69bed019826ddec93f761514652a93d871e49Harald Welte ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 690aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next) 691aae69bed019826ddec93f761514652a93d871e49Harald Welte 692aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 693aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry 694aae69bed019826ddec93f761514652a93d871e49Harald Welte * @tpos: the type * to use as a loop counter. 695aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct hlist_node to use as a loop counter. 696aae69bed019826ddec93f761514652a93d871e49Harald Welte * @n: another &struct hlist_node to use as temporary storage 697aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 698aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the hlist_node within the struct. 699aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 700aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each_entry_safe(tpos, pos, n, head, member) \ 701aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->first; \ 702aae69bed019826ddec93f761514652a93d871e49Harald Welte pos && ({ n = pos->next; 1; }) && \ 703aae69bed019826ddec93f761514652a93d871e49Harald Welte ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 704aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = n) 705aae69bed019826ddec93f761514652a93d871e49Harald Welte 706aae69bed019826ddec93f761514652a93d871e49Harald Welte/** 707aae69bed019826ddec93f761514652a93d871e49Harald Welte * hlist_for_each_entry_rcu - iterate over rcu list of given type 708aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the type * to use as a loop counter. 709aae69bed019826ddec93f761514652a93d871e49Harald Welte * @pos: the &struct hlist_node to use as a loop counter. 710aae69bed019826ddec93f761514652a93d871e49Harald Welte * @head: the head for your list. 711aae69bed019826ddec93f761514652a93d871e49Harald Welte * @member: the name of the hlist_node within the struct. 712aae69bed019826ddec93f761514652a93d871e49Harald Welte * 713aae69bed019826ddec93f761514652a93d871e49Harald Welte * This list-traversal primitive may safely run concurrently with 714aae69bed019826ddec93f761514652a93d871e49Harald Welte * the _rcu list-mutation primitives such as hlist_add_rcu() 715aae69bed019826ddec93f761514652a93d871e49Harald Welte * as long as the traversal is guarded by rcu_read_lock(). 716aae69bed019826ddec93f761514652a93d871e49Harald Welte */ 717aae69bed019826ddec93f761514652a93d871e49Harald Welte#define hlist_for_each_entry_rcu(tpos, pos, head, member) \ 718aae69bed019826ddec93f761514652a93d871e49Harald Welte for (pos = (head)->first; \ 719aae69bed019826ddec93f761514652a93d871e49Harald Welte pos && ({ prefetch(pos->next); 1;}) && \ 720aae69bed019826ddec93f761514652a93d871e49Harald Welte ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \ 721aae69bed019826ddec93f761514652a93d871e49Harald Welte pos = pos->next, ({ smp_read_barrier_depends(); 0; }) ) 722aae69bed019826ddec93f761514652a93d871e49Harald Welte 723aae69bed019826ddec93f761514652a93d871e49Harald Welte#endif 724