Branch data 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 : 0 : INIT_LIST_HEAD(&ulist->nodes);
50 : 0 : ulist->root = RB_ROOT;
51 : 0 : 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 : 0 : static void ulist_fini(struct ulist *ulist)
62 : : {
63 : : struct ulist_node *node;
64 : : struct ulist_node *next;
65 : :
66 [ # # ]: 0 : list_for_each_entry_safe(node, next, &ulist->nodes, list) {
67 : 0 : kfree(node);
68 : : }
69 : 0 : ulist->root = RB_ROOT;
70 : : INIT_LIST_HEAD(&ulist->nodes);
71 : 0 : }
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 : 0 : void ulist_reinit(struct ulist *ulist)
81 : : {
82 : 0 : ulist_fini(ulist);
83 : : ulist_init(ulist);
84 : 0 : }
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 : 0 : struct ulist *ulist_alloc(gfp_t gfp_mask)
93 : : {
94 : : struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
95 : :
96 [ # # ]: 0 : if (!ulist)
97 : : return NULL;
98 : :
99 : : ulist_init(ulist);
100 : :
101 : 0 : 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 : 0 : void ulist_free(struct ulist *ulist)
111 : : {
112 [ # # ]: 0 : if (!ulist)
113 : 0 : return;
114 : 0 : ulist_fini(ulist);
115 : 0 : 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 [ # # ]: 0 : while (n) {
124 : 0 : u = rb_entry(n, struct ulist_node, rb_node);
125 [ # # ]: 0 : if (u->val < val)
126 : 0 : n = n->rb_right;
127 [ # # ]: 0 : else if (u->val > val)
128 : 0 : n = n->rb_left;
129 : : else
130 : : return u;
131 : : }
132 : : return NULL;
133 : : }
134 : :
135 : 0 : static int ulist_rbtree_insert(struct ulist *ulist, struct ulist_node *ins)
136 : : {
137 : 0 : struct rb_node **p = &ulist->root.rb_node;
138 : : struct rb_node *parent = NULL;
139 : : struct ulist_node *cur = NULL;
140 : :
141 [ # # ]: 0 : while (*p) {
142 : : parent = *p;
143 : : cur = rb_entry(parent, struct ulist_node, rb_node);
144 : :
145 [ # # ]: 0 : if (cur->val < ins->val)
146 : 0 : p = &(*p)->rb_right;
147 [ # # ]: 0 : else if (cur->val > ins->val)
148 : 0 : p = &(*p)->rb_left;
149 : : else
150 : : return -EEXIST;
151 : : }
152 : 0 : rb_link_node(&ins->rb_node, parent, p);
153 : 0 : rb_insert_color(&ins->rb_node, &ulist->root);
154 : 0 : 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 : 0 : int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
178 : : {
179 : 0 : return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
180 : : }
181 : :
182 : 0 : 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 [ # # ]: 0 : if (node) {
190 [ # # ]: 0 : if (old_aux)
191 : 0 : *old_aux = node->aux;
192 : : return 0;
193 : : }
194 : : node = kmalloc(sizeof(*node), gfp_mask);
195 [ # # ]: 0 : if (!node)
196 : : return -ENOMEM;
197 : :
198 : 0 : node->val = val;
199 : 0 : node->aux = aux;
200 : : #ifdef CONFIG_BTRFS_DEBUG
201 : : node->seqnum = ulist->nnodes;
202 : : #endif
203 : :
204 : 0 : ret = ulist_rbtree_insert(ulist, node);
205 : : ASSERT(!ret);
206 : 0 : list_add_tail(&node->list, &ulist->nodes);
207 : 0 : ulist->nnodes++;
208 : :
209 : 0 : 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 : 0 : struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
229 : : {
230 : : struct ulist_node *node;
231 : :
232 [ # # ]: 0 : if (list_empty(&ulist->nodes))
233 : : return NULL;
234 [ # # ][ # # ]: 0 : if (uiter->cur_list && uiter->cur_list->next == &ulist->nodes)
235 : : return NULL;
236 [ # # ]: 0 : if (uiter->cur_list) {
237 : 0 : uiter->cur_list = uiter->cur_list->next;
238 : : } else {
239 : 0 : uiter->cur_list = ulist->nodes.next;
240 : : #ifdef CONFIG_BTRFS_DEBUG
241 : : uiter->i = 0;
242 : : #endif
243 : : }
244 : 0 : 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 : 0 : return node;
251 : : }
|
