1
2
3
4
5
6
7#include <linux/slab.h>
8#include "ulist.h"
9#include "ctree.h"
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47void ulist_init(struct ulist *ulist)
48{
49 INIT_LIST_HEAD(&ulist->nodes);
50 ulist->root = RB_ROOT;
51 ulist->nnodes = 0;
52}
53
54
55
56
57
58
59
60
61static void ulist_fini(struct ulist *ulist)
62{
63 struct ulist_node *node;
64 struct ulist_node *next;
65
66 list_for_each_entry_safe(node, next, &ulist->nodes, list) {
67 kfree(node);
68 }
69 ulist->root = RB_ROOT;
70 INIT_LIST_HEAD(&ulist->nodes);
71}
72
73
74
75
76
77
78
79
80void ulist_reinit(struct ulist *ulist)
81{
82 ulist_fini(ulist);
83 ulist_init(ulist);
84}
85
86
87
88
89
90
91
92struct ulist *ulist_alloc(gfp_t gfp_mask)
93{
94 struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
95
96 if (!ulist)
97 return NULL;
98
99 ulist_init(ulist);
100
101 return ulist;
102}
103
104
105
106
107
108
109
110void ulist_free(struct ulist *ulist)
111{
112 if (!ulist)
113 return;
114 ulist_fini(ulist);
115 kfree(ulist);
116}
117
118static struct ulist_node *ulist_rbtree_search(struct ulist *ulist, u64 val)
119{
120 struct rb_node *n = ulist->root.rb_node;
121 struct ulist_node *u = NULL;
122
123 while (n) {
124 u = rb_entry(n, struct ulist_node, rb_node);
125 if (u->val < val)
126 n = n->rb_right;
127 else if (u->val > val)
128 n = n->rb_left;
129 else
130 return u;
131 }
132 return NULL;
133}
134
135static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
136{
137 struct rb_node **p = &ulist->root.rb_node;
138 struct rb_node *parent = NULL;
139 struct ulist_node *cur = NULL;
140
141 while (*p) {
142 parent = *p;
143 cur = rb_entry(parent, struct ulist_node, rb_node);
144
145 if (cur->val < ins->val)
146 p = &(*p)->rb_right;
147 else if (cur->val > ins->val)
148 p = &(*p)->rb_left;
149 else
150 return -EEXIST;
151 }
152 rb_link_node(&ins->rb_node, parent, p);
153 rb_insert_color(&ins->rb_node, &ulist->root);
154 return 0;
155}
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
178{
179 return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
180}
181
182int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
183 u64 *old_aux, gfp_t gfp_mask)
184{
185 int ret;
186 struct ulist_node *node;
187
188 node = ulist_rbtree_search(ulist, val);
189 if (node) {
190 if (old_aux)
191 *old_aux = node->aux;
192 return 0;
193 }
194 node = kmalloc(sizeof(*node), gfp_mask);
195 if (!node)
196 return -ENOMEM;
197
198 node->val = val;
199 node->aux = aux;
200#ifdef CONFIG_BTRFS_DEBUG
201 node->seqnum = ulist->nnodes;
202#endif
203
204 ret = ulist_rbtree_insert(ulist, node);
205 ASSERT(!ret);
206 list_add_tail(&node->list, &ulist->nodes);
207 ulist->nnodes++;
208
209 return 1;
210}
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
229{
230 struct ulist_node *node;
231
232 if (list_empty(&ulist->nodes))
233 return NULL;
234 if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes)
235 return NULL;
236 if (uiter->cur_list) {
237 uiter->cur_list = uiter->cur_list->next;
238 } else {
239 uiter->cur_list = ulist->nodes.next;
240#ifdef CONFIG_BTRFS_DEBUG
241 uiter->i = 0;
242#endif
243 }
244 node = list_entry(uiter->cur_list, struct ulist_node, list);
245#ifdef CONFIG_BTRFS_DEBUG
246 ASSERT(node->seqnum == uiter->i);
247 ASSERT(uiter->i >= 0 && uiter->i < ulist->nnodes);
248 uiter->i++;
249#endif
250 return node;
251}
252