]>
Commit | Line | Data |
---|---|---|
da5c8135 AJ |
1 | /* |
2 | * Copyright (C) 2011 STRATO AG | |
3 | * written by Arne Jansen <sensille@gmx.net> | |
4 | * Distributed under the GNU GPL license version 2. | |
5 | */ | |
6 | ||
7 | #include <linux/slab.h> | |
da5c8135 | 8 | #include "ulist.h" |
4c7a6f74 | 9 | #include "ctree.h" |
da5c8135 AJ |
10 | |
11 | /* | |
12 | * ulist is a generic data structure to hold a collection of unique u64 | |
13 | * values. The only operations it supports is adding to the list and | |
14 | * enumerating it. | |
15 | * It is possible to store an auxiliary value along with the key. | |
16 | * | |
da5c8135 AJ |
17 | * A sample usage for ulists is the enumeration of directed graphs without |
18 | * visiting a node twice. The pseudo-code could look like this: | |
19 | * | |
20 | * ulist = ulist_alloc(); | |
21 | * ulist_add(ulist, root); | |
cd1b413c | 22 | * ULIST_ITER_INIT(&uiter); |
da5c8135 | 23 | * |
cd1b413c | 24 | * while ((elem = ulist_next(ulist, &uiter)) { |
da5c8135 AJ |
25 | * for (all child nodes n in elem) |
26 | * ulist_add(ulist, n); | |
27 | * do something useful with the node; | |
28 | * } | |
29 | * ulist_free(ulist); | |
30 | * | |
31 | * This assumes the graph nodes are adressable by u64. This stems from the | |
32 | * usage for tree enumeration in btrfs, where the logical addresses are | |
33 | * 64 bit. | |
34 | * | |
35 | * It is also useful for tree enumeration which could be done elegantly | |
36 | * recursively, but is not possible due to kernel stack limitations. The | |
37 | * loop would be similar to the above. | |
38 | */ | |
39 | ||
40 | /** | |
41 | * ulist_init - freshly initialize a ulist | |
42 | * @ulist: the ulist to initialize | |
43 | * | |
44 | * Note: don't use this function to init an already used ulist, use | |
45 | * ulist_reinit instead. | |
46 | */ | |
47 | void ulist_init(struct ulist *ulist) | |
48 | { | |
4c7a6f74 | 49 | INIT_LIST_HEAD(&ulist->nodes); |
f7f82b81 | 50 | ulist->root = RB_ROOT; |
4c7a6f74 | 51 | ulist->nnodes = 0; |
da5c8135 | 52 | } |
da5c8135 AJ |
53 | |
54 | /** | |
55 | * ulist_fini - free up additionally allocated memory for the ulist | |
56 | * @ulist: the ulist from which to free the additional memory | |
57 | * | |
58 | * This is useful in cases where the base 'struct ulist' has been statically | |
59 | * allocated. | |
60 | */ | |
49fc647a | 61 | static void ulist_fini(struct ulist *ulist) |
da5c8135 | 62 | { |
4c7a6f74 WS |
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 | } | |
f7f82b81 | 69 | ulist->root = RB_ROOT; |
4c7a6f74 | 70 | INIT_LIST_HEAD(&ulist->nodes); |
da5c8135 | 71 | } |
da5c8135 AJ |
72 | |
73 | /** | |
74 | * ulist_reinit - prepare a ulist for reuse | |
75 | * @ulist: ulist to be reused | |
76 | * | |
77 | * Free up all additional memory allocated for the list elements and reinit | |
78 | * the ulist. | |
79 | */ | |
80 | void ulist_reinit(struct ulist *ulist) | |
81 | { | |
82 | ulist_fini(ulist); | |
83 | ulist_init(ulist); | |
84 | } | |
da5c8135 AJ |
85 | |
86 | /** | |
87 | * ulist_alloc - dynamically allocate a ulist | |
88 | * @gfp_mask: allocation flags to for base allocation | |
89 | * | |
90 | * The allocated ulist will be returned in an initialized state. | |
91 | */ | |
2eec6c81 | 92 | struct ulist *ulist_alloc(gfp_t gfp_mask) |
da5c8135 AJ |
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 | } | |
da5c8135 AJ |
103 | |
104 | /** | |
105 | * ulist_free - free dynamically allocated ulist | |
106 | * @ulist: ulist to free | |
107 | * | |
108 | * It is not necessary to call ulist_fini before. | |
109 | */ | |
110 | void ulist_free(struct ulist *ulist) | |
111 | { | |
112 | if (!ulist) | |
113 | return; | |
114 | ulist_fini(ulist); | |
115 | kfree(ulist); | |
116 | } | |
da5c8135 | 117 | |
f7f82b81 WS |
118 | static 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 | ||
135 | static 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 | ||
da5c8135 AJ |
157 | /** |
158 | * ulist_add - add an element to the ulist | |
159 | * @ulist: ulist to add the element to | |
160 | * @val: value to add to ulist | |
161 | * @aux: auxiliary value to store along with val | |
162 | * @gfp_mask: flags to use for allocation | |
163 | * | |
164 | * Note: locking must be provided by the caller. In case of rwlocks write | |
165 | * locking is needed | |
166 | * | |
167 | * Add an element to a ulist. The @val will only be added if it doesn't | |
168 | * already exist. If it is added, the auxiliary value @aux is stored along with | |
169 | * it. In case @val already exists in the ulist, @aux is ignored, even if | |
170 | * it differs from the already stored value. | |
171 | * | |
172 | * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been | |
173 | * inserted. | |
174 | * In case of allocation failure -ENOMEM is returned and the ulist stays | |
175 | * unaltered. | |
176 | */ | |
34d73f54 | 177 | int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask) |
3301958b JS |
178 | { |
179 | return ulist_add_merge(ulist, val, aux, NULL, gfp_mask); | |
180 | } | |
181 | ||
34d73f54 AB |
182 | int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, |
183 | u64 *old_aux, gfp_t gfp_mask) | |
da5c8135 | 184 | { |
4c7a6f74 WS |
185 | int ret; |
186 | struct ulist_node *node; | |
187 | ||
f7f82b81 WS |
188 | node = ulist_rbtree_search(ulist, val); |
189 | if (node) { | |
190 | if (old_aux) | |
191 | *old_aux = node->aux; | |
192 | return 0; | |
da5c8135 | 193 | } |
4c7a6f74 WS |
194 | node = kmalloc(sizeof(*node), gfp_mask); |
195 | if (!node) | |
196 | return -ENOMEM; | |
da5c8135 | 197 | |
4c7a6f74 WS |
198 | node->val = val; |
199 | node->aux = aux; | |
200 | #ifdef CONFIG_BTRFS_DEBUG | |
201 | node->seqnum = ulist->nnodes; | |
202 | #endif | |
da5c8135 | 203 | |
4c7a6f74 WS |
204 | ret = ulist_rbtree_insert(ulist, node); |
205 | ASSERT(!ret); | |
206 | list_add_tail(&node->list, &ulist->nodes); | |
207 | ulist->nnodes++; | |
da5c8135 AJ |
208 | |
209 | return 1; | |
210 | } | |
da5c8135 AJ |
211 | |
212 | /** | |
213 | * ulist_next - iterate ulist | |
214 | * @ulist: ulist to iterate | |
cd1b413c | 215 | * @uiter: iterator variable, initialized with ULIST_ITER_INIT(&iterator) |
da5c8135 AJ |
216 | * |
217 | * Note: locking must be provided by the caller. In case of rwlocks only read | |
218 | * locking is needed | |
219 | * | |
cd1b413c JS |
220 | * This function is used to iterate an ulist. |
221 | * It returns the next element from the ulist or %NULL when the | |
da5c8135 AJ |
222 | * end is reached. No guarantee is made with respect to the order in which |
223 | * the elements are returned. They might neither be returned in order of | |
224 | * addition nor in ascending order. | |
225 | * It is allowed to call ulist_add during an enumeration. Newly added items | |
226 | * are guaranteed to show up in the running enumeration. | |
227 | */ | |
cd1b413c | 228 | struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter) |
da5c8135 | 229 | { |
4c7a6f74 WS |
230 | struct ulist_node *node; |
231 | ||
232 | if (list_empty(&ulist->nodes)) | |
da5c8135 | 233 | return NULL; |
4c7a6f74 | 234 | if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes) |
da5c8135 | 235 | return NULL; |
4c7a6f74 WS |
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; | |
da5c8135 | 251 | } |