Line data Source code
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>
8 : #include "ulist.h"
9 : #include "ctree.h"
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 : *
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);
22 : * ULIST_ITER_INIT(&uiter);
23 : *
24 : * while ((elem = ulist_next(ulist, &uiter)) {
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 0 : void ulist_init(struct ulist *ulist)
48 : {
49 1978321 : INIT_LIST_HEAD(&ulist->nodes);
50 1978321 : ulist->root = RB_ROOT;
51 1978321 : ulist->nnodes = 0;
52 0 : }
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 : */
61 1978318 : static void ulist_fini(struct ulist *ulist)
62 : {
63 : struct ulist_node *node;
64 : struct ulist_node *next;
65 :
66 3833529 : list_for_each_entry_safe(node, next, &ulist->nodes, list) {
67 1855219 : kfree(node);
68 : }
69 1978310 : ulist->root = RB_ROOT;
70 : INIT_LIST_HEAD(&ulist->nodes);
71 1978310 : }
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 1222424 : void ulist_reinit(struct ulist *ulist)
81 : {
82 1222424 : ulist_fini(ulist);
83 : ulist_init(ulist);
84 1222430 : }
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 : */
92 755891 : struct ulist *ulist_alloc(gfp_t gfp_mask)
93 : {
94 : struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
95 :
96 755891 : if (!ulist)
97 : return NULL;
98 :
99 : ulist_init(ulist);
100 :
101 755891 : return ulist;
102 : }
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 756103 : void ulist_free(struct ulist *ulist)
111 : {
112 756103 : if (!ulist)
113 756103 : return;
114 755891 : ulist_fini(ulist);
115 755891 : kfree(ulist);
116 : }
117 :
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 8675402 : while (n) {
124 6820195 : u = rb_entry(n, struct ulist_node, rb_node);
125 6820195 : if (u->val < val)
126 86146 : n = n->rb_right;
127 6734049 : else if (u->val > val)
128 6733736 : n = n->rb_left;
129 : else
130 : return u;
131 : }
132 : return NULL;
133 : }
134 :
135 1855211 : static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
136 : {
137 1855211 : struct rb_node **p = &ulist->root.rb_node;
138 : struct rb_node *parent = NULL;
139 : struct ulist_node *cur = NULL;
140 :
141 10530302 : while (*p) {
142 : parent = *p;
143 : cur = rb_entry(parent, struct ulist_node, rb_node);
144 :
145 6819880 : if (cur->val < ins->val)
146 86146 : p = &(*p)->rb_right;
147 6733734 : else if (cur->val > ins->val)
148 6733734 : p = &(*p)->rb_left;
149 : else
150 : return -EEXIST;
151 : }
152 1855211 : rb_link_node(&ins->rb_node, parent, p);
153 1855211 : rb_insert_color(&ins->rb_node, &ulist->root);
154 1855209 : return 0;
155 : }
156 :
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 : */
177 1212203 : int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
178 : {
179 1212203 : return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
180 : }
181 :
182 1855520 : int 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 1855520 : if (node) {
190 313 : if (old_aux)
191 313 : *old_aux = node->aux;
192 : return 0;
193 : }
194 : node = kmalloc(sizeof(*node), gfp_mask);
195 1855211 : if (!node)
196 : return -ENOMEM;
197 :
198 1855211 : node->val = val;
199 1855211 : node->aux = aux;
200 : #ifdef CONFIG_BTRFS_DEBUG
201 : node->seqnum = ulist->nnodes;
202 : #endif
203 :
204 1855211 : ret = ulist_rbtree_insert(ulist, node);
205 : ASSERT(!ret);
206 1855208 : list_add_tail(&node->list, &ulist->nodes);
207 1855208 : ulist->nnodes++;
208 :
209 1855208 : return 1;
210 : }
211 :
212 : /**
213 : * ulist_next - iterate ulist
214 : * @ulist: ulist to iterate
215 : * @uiter: iterator variable, initialized with ULIST_ITER_INIT(&iterator)
216 : *
217 : * Note: locking must be provided by the caller. In case of rwlocks only read
218 : * locking is needed
219 : *
220 : * This function is used to iterate an ulist.
221 : * It returns the next element from the ulist or %NULL when the
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 : */
228 3844348 : struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
229 : {
230 : struct ulist_node *node;
231 :
232 7688696 : if (list_empty(&ulist->nodes))
233 : return NULL;
234 2673823 : if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes)
235 : return NULL;
236 1900692 : if (uiter->cur_list) {
237 1126558 : uiter->cur_list = uiter->cur_list->next;
238 : } else {
239 774134 : uiter->cur_list = ulist->nodes.next;
240 : #ifdef CONFIG_BTRFS_DEBUG
241 : uiter->i = 0;
242 : #endif
243 : }
244 1900692 : 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 1900692 : return node;
251 : }
|
