]>
Commit | Line | Data |
---|---|---|
6fa70da6 CM |
1 | #ifndef _LINUX_XLIST_H |
2 | #define _LINUX_XLIST_H | |
3 | ||
4 | #include <linux/stddef.h> | |
5 | #include <linux/poison.h> | |
6 | #include <linux/prefetch.h> | |
7 | #include <asm/system.h> | |
8 | ||
9 | struct xlist_head { | |
10 | struct xlist_head *next; | |
11 | }; | |
12 | ||
13 | /* | |
14 | * XLIST_PTR_TAIL can be used to prevent double insertion. See | |
15 | * xlist_protect() | |
16 | */ | |
17 | #define XLIST_PTR_TAIL ((struct xlist_head *)0x1) | |
18 | ||
19 | static inline void xlist_add(struct xlist_head *new, struct xlist_head *tail, struct xlist_head *head) | |
20 | { | |
21 | struct xlist_head *cur; | |
22 | struct xlist_head *check; | |
23 | ||
24 | while (1) { | |
25 | cur = head->next; | |
26 | tail->next = cur; | |
27 | check = cmpxchg(&head->next, cur, new); | |
28 | if (check == cur) | |
29 | break; | |
30 | } | |
31 | } | |
32 | ||
33 | /* | |
34 | * To avoid duplicate insertion by two CPUs of the same xlist item | |
35 | * you can call xlist_protect. It will stuff XLIST_PTR_TAIL | |
36 | * into the entry->next pointer with xchg, and only return 1 | |
37 | * if there was a NULL there before. | |
38 | * | |
39 | * if xlist_protect returns zero, someone else is busy working | |
40 | * on this entry. Getting a NULL into the entry in a race | |
41 | * free manner is the caller's job. | |
42 | */ | |
43 | static inline int xlist_protect(struct xlist_head *entry) | |
44 | { | |
45 | struct xlist_head *val; | |
46 | ||
47 | val = xchg(&entry->next, XLIST_PTR_TAIL); | |
48 | if (val == NULL) | |
49 | return 1; | |
50 | return 0; | |
51 | } | |
52 | ||
53 | static inline struct xlist_head *xlist_del_head(struct xlist_head *head) | |
54 | { | |
55 | struct xlist_head *cur; | |
56 | struct xlist_head *check; | |
57 | struct xlist_head *next; | |
58 | ||
59 | while (1) { | |
60 | cur = head->next; | |
61 | if (!cur) | |
62 | goto out; | |
63 | ||
64 | if (cur == XLIST_PTR_TAIL) { | |
65 | cur = NULL; | |
66 | goto out; | |
67 | } | |
68 | ||
69 | next = cur->next; | |
70 | check = cmpxchg(&head->next, cur, next); | |
71 | if (check == cur) | |
72 | goto out; | |
73 | } | |
74 | out: | |
75 | return cur; | |
76 | } | |
77 | ||
78 | static inline struct xlist_head *xlist_del_head_fast(struct xlist_head *head) | |
79 | { | |
80 | struct xlist_head *cur; | |
81 | ||
82 | cur = head->next; | |
83 | if (!cur || cur == XLIST_PTR_TAIL) | |
84 | return NULL; | |
85 | ||
86 | head->next = cur->next; | |
87 | return cur; | |
88 | } | |
89 | ||
90 | static inline void xlist_splice(struct xlist_head *list, | |
91 | struct xlist_head *head) | |
92 | { | |
93 | struct xlist_head *cur; | |
94 | ||
95 | WARN_ON(head->next); | |
96 | cur = xchg(&list->next, NULL); | |
97 | head->next = cur; | |
98 | } | |
99 | ||
100 | static inline void INIT_XLIST_HEAD(struct xlist_head *list) | |
101 | { | |
102 | list->next = NULL; | |
103 | } | |
104 | ||
105 | static inline int xlist_empty(struct xlist_head *head) | |
106 | { | |
107 | return head->next == NULL || head->next == XLIST_PTR_TAIL; | |
108 | } | |
109 | ||
110 | #endif |