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 h->first = (struct hlist_bl_node *)((unsigned long)n | LIST_BL_LOCKMASK); 67 } 68 69 static inline int hlist_bl_empty(const struct hlist_bl_head *h) 70 { 71 return !((unsigned long)h->first & ~LIST_BL_LOCKMASK); 72 } 73 74 static inline void hlist_bl_add_head(struct hlist_bl_node *n, 75 struct hlist_bl_head *h) 76 { 77 struct hlist_bl_node *first = hlist_bl_first(h); 78 79 n->next = first; 80 if (first) 81 first->pprev = &n->next; 82 n->pprev = &h->first; 83 hlist_bl_set_first(h, n); 84 } 85 86 static inline void __hlist_bl_del(struct hlist_bl_node *n) 87 { 88 struct hlist_bl_node *next = n->next; 89 struct hlist_bl_node **pprev = n->pprev; 90 91 LIST_BL_BUG_ON((unsigned long)n & LIST_BL_LOCKMASK); 92 93 /* pprev may be `first`, so be careful not to lose the lock bit */ 94 *pprev = (struct hlist_bl_node *) 95 ((unsigned long)next | 96 ((unsigned long)*pprev & LIST_BL_LOCKMASK)); 97 if (next) 98 next->pprev = pprev; 99 } 100 101 static inline void hlist_bl_del(struct hlist_bl_node *n) 102 { 103 __hlist_bl_del(n); 104 n->next = LIST_POISON1; 105 n->pprev = LIST_POISON2; 106 } 107 108 static inline void hlist_bl_del_init(struct hlist_bl_node *n) 109 { 110 if (!hlist_bl_unhashed(n)) { 111 __hlist_bl_del(n); 112 INIT_HLIST_BL_NODE(n); 113 } 114 } 115 116 /** 117 * hlist_bl_for_each_entry - iterate over list of given type 118 * @tpos: the type * to use as a loop cursor. 119 * @pos: the &struct hlist_node to use as a loop cursor. 120 * @head: the head for your list. 121 * @member: the name of the hlist_node within the struct. 122 * 123 */ 124 #define hlist_bl_for_each_entry(tpos, pos, head, member) \ 125 for (pos = hlist_bl_first(head); \ 126 pos && \ 127 ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \ 128 pos = pos->next) 129 130 /** 131 * hlist_bl_for_each_entry_safe - iterate over list of given type safe against removal of list entry 132 * @tpos: the type * to use as a loop cursor. 133 * @pos: the &struct hlist_node to use as a loop cursor. 134 * @n: another &struct hlist_node to use as temporary storage 135 * @head: the head for your list. 136 * @member: the name of the hlist_node within the struct. 137 */ 138 #define hlist_bl_for_each_entry_safe(tpos, pos, n, head, member) \ 139 for (pos = hlist_bl_first(head); \ 140 pos && ({ n = pos->next; 1; }) && \ 141 ({ tpos = hlist_bl_entry(pos, typeof(*tpos), member); 1;}); \ 142 pos = n) 143 144 #endif 145