1 #ifndef _LINUX_LIST_BL_H 2 #define _LINUX_LIST_BL_H 3 4 #include <linux/list.h> 5 6 /* 7 * Special version of lists, where head of the list has a lock in the lowest 8 * bit. This is useful for scalable hash tables without increasing memory 9 * footprint overhead. 10 * 11 * For modification operations, the 0 bit of hlist_bl_head->first 12 * pointer must be set. 13 * 14 * With some small modifications, this can easily be adapted to store several 15 * arbitrary bits (not just a single lock bit), if the need arises to store 16 * some fast and compact auxiliary data. 17 */ 18 19 #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) 20 #define LIST_BL_LOCKMASK 1UL 21 #else 22 #define LIST_BL_LOCKMASK 0UL 23 #endif 24 25 #ifdef CONFIG_DEBUG_LIST 26 #define LIST_BL_BUG_ON(x) BUG_ON(x) 27 #else 28 #define LIST_BL_BUG_ON(x) 29 #endif 30 31 32 struct hlist_bl_head { 33 struct hlist_bl_node *first; 34 }; 35 36 struct hlist_bl_node { 37 struct hlist_bl_node *next, **pprev; 38 }; 39 #define INIT_HLIST_BL_HEAD(ptr) \ 40 ((ptr)->first = NULL) 41 42 static inline void INIT_HLIST_BL_NODE(struct hlist_bl_node *h) 43 { 44 h->next = NULL; 45 h->pprev = NULL; 46 } 47 48 #define hlist_bl_entry(ptr, type, member) container_of(ptr,type,member) 49 50 static inline int hlist_bl_unhashed(const struct hlist_bl_node *h) 51 { 52 return !h->pprev; 53 } 54 55 static inline struct hlist_bl_node *hlist_bl_first(struct hlist_bl_head *h) 56 { 57 return (struct hlist_bl_node *) 58 ((unsigned long)h->first & ~LIST_BL_LOCKMASK); 59 } 60 61 static inline void hlist_bl_set_first(struct hlist_bl_head *h, 62 struct hlist_bl_node *n) 63 { 64 LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK); 65 LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) != 66 LIST_BL_LOCKMASK); 67 h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK); 68 } 69 70 static inline int hlist_bl_empty(const struct hlist_bl_head *h) 71 { 72 return !((unsigned long)h->first & ~LIST_BL_LOCKMASK); 73 } 74 75 static inline void hlist_bl_add_head(struct hlist_bl_node *n, 76 struct hlist_bl_head *h) 77 { 78 struct hlist_bl_node *first = hlist_bl_first(h); 79 80 n->next = first; 81 if (first) 82 first->pprev = &n->next; 83 n->pprev = &h->first; 84 hlist_bl_set_first(h, n); 85 } 86 87 static inline void __hlist_bl_del(struct hlist_bl_node *n) 88 { 89 struct hlist_bl_node *next = n->next; 90 struct hlist_bl_node **pprev = n->pprev; 91 92 LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK); 93 94 /* pprev may be `first`, so be careful not to lose the lock bit */ 95 *pprev = (struct hlist_bl_node *) 96 ((unsigned long)next | 97 ((unsigned long)*pprev & LIST_BL_LOCKMASK)); 98 if (next) 99 next->pprev = pprev; 100 } 101 102 static inline void hlist_bl_del(struct hlist_bl_node *n) 103 { 104 __hlist_bl_del(n); 105 n->next = LIST_POISON1; 106 n->pprev = LIST_POISON2; 107 } 108 109 static inline void hlist_bl_del_init(struct hlist_bl_node *n) 110 { 111 if (!hlist_bl_unhashed(n)) { 112 __hlist_bl_del(n); 113 INIT_HLIST_BL_NODE(n); 114 } 115 } 116 117 /** 118 * hlist_bl_for_each_entry - iterate over list of given type 119 * @tpos: the type * to use as a loop cursor. 120 * @pos: the &struct hlist_node to use as a loop cursor. 121 * @head: the head for your list. 122 * @member: the name of the hlist_node within the struct. 123 * 124 */ 125 #define hlist_bl_for_each_entry(tpos, pos, head, member) \ 126 for (pos = hlist_bl_first(head); \ 127 pos && \ 128 ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \ 129 pos = pos->next) 130 131 /** 132 * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry 133 * @tpos: the type * to use as a loop cursor. 134 * @pos: the &struct hlist_node to use as a loop cursor. 135 * @n: another &struct hlist_node to use as temporary storage 136 * @head: the head for your list. 137 * @member: the name of the hlist_node within the struct. 138 */ 139 #define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member) \ 140 for (pos = hlist_bl_first(head); \ 141 pos && ({ n = pos->next; 1; }) && \ 142 ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \ 143 pos = n) 144 145 #endif 146