|
1 #ifndef _LINUX_LIST_NULLS_H |
|
2 #define _LINUX_LIST_NULLS_H |
|
3 |
|
4 /* |
|
5 * Special version of lists, where end of list is not a NULL pointer, |
|
6 * but a 'nulls' marker, which can have many different values. |
|
7 * (up to 2^31 different values guaranteed on all platforms) |
|
8 * |
|
9 * In the standard hlist, termination of a list is the NULL pointer. |
|
10 * In this special 'nulls' variant, we use the fact that objects stored in |
|
11 * a list are aligned on a word (4 or 8 bytes alignment). |
|
12 * We therefore use the last significant bit of 'ptr' : |
|
13 * Set to 1 : This is a 'nulls' end-of-list marker (ptr >> 1) |
|
14 * Set to 0 : This is a pointer to some object (ptr) |
|
15 */ |
|
16 |
|
17 struct hlist_nulls_head { |
|
18 struct hlist_nulls_node *first; |
|
19 }; |
|
20 |
|
21 struct hlist_nulls_node { |
|
22 struct hlist_nulls_node *next, **pprev; |
|
23 }; |
|
24 #define INIT_HLIST_NULLS_HEAD(ptr, nulls) \ |
|
25 ((ptr)->first = (struct hlist_nulls_node *) (1UL | (((long)nulls) << 1))) |
|
26 |
|
27 #define hlist_nulls_entry(ptr, type, member) container_of(ptr,type,member) |
|
28 /** |
|
29 * ptr_is_a_nulls - Test if a ptr is a nulls |
|
30 * @ptr: ptr to be tested |
|
31 * |
|
32 */ |
|
33 static inline int is_a_nulls(const struct hlist_nulls_node *ptr) |
|
34 { |
|
35 return ((unsigned long)ptr & 1); |
|
36 } |
|
37 |
|
38 /** |
|
39 * get_nulls_value - Get the 'nulls' value of the end of chain |
|
40 * @ptr: end of chain |
|
41 * |
|
42 * Should be called only if is_a_nulls(ptr); |
|
43 */ |
|
44 static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr) |
|
45 { |
|
46 return ((unsigned long)ptr) >> 1; |
|
47 } |
|
48 |
|
49 static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h) |
|
50 { |
|
51 return !h->pprev; |
|
52 } |
|
53 |
|
54 static inline int hlist_nulls_empty(const struct hlist_nulls_head *h) |
|
55 { |
|
56 return is_a_nulls(h->first); |
|
57 } |
|
58 |
|
59 static inline void __hlist_nulls_del(struct hlist_nulls_node *n) |
|
60 { |
|
61 struct hlist_nulls_node *next = n->next; |
|
62 struct hlist_nulls_node **pprev = n->pprev; |
|
63 *pprev = next; |
|
64 if (!is_a_nulls(next)) |
|
65 next->pprev = pprev; |
|
66 } |
|
67 |
|
68 /** |
|
69 * hlist_nulls_for_each_entry - iterate over list of given type |
|
70 * @tpos: the type * to use as a loop cursor. |
|
71 * @pos: the &struct hlist_node to use as a loop cursor. |
|
72 * @head: the head for your list. |
|
73 * @member: the name of the hlist_node within the struct. |
|
74 * |
|
75 */ |
|
76 #define hlist_nulls_for_each_entry(tpos, pos, head, member) \ |
|
77 for (pos = (head)->first; \ |
|
78 (!is_a_nulls(pos)) && \ |
|
79 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \ |
|
80 pos = pos->next) |
|
81 |
|
82 /** |
|
83 * hlist_nulls_for_each_entry_from - iterate over a hlist continuing from current point |
|
84 * @tpos: the type * to use as a loop cursor. |
|
85 * @pos: the &struct hlist_node to use as a loop cursor. |
|
86 * @member: the name of the hlist_node within the struct. |
|
87 * |
|
88 */ |
|
89 #define hlist_nulls_for_each_entry_from(tpos, pos, member) \ |
|
90 for (; (!is_a_nulls(pos)) && \ |
|
91 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \ |
|
92 pos = pos->next) |
|
93 |
|
94 #endif |