Commit | Line | Data |
---|---|---|
4e35e607 NP |
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 | ||
32385c7c | 19 | #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_SPINLOCK) |
4e35e607 NP |
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); | |
2c675598 NP |
65 | LIST_BL_BUG_ON(((unsigned long)h->first & LIST_BL_LOCKMASK) != |
66 | LIST_BL_LOCKMASK); | |
4e35e607 NP |
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 |