ARM: tegra: make device can run on UP
[linux-3.10.git] / fs / btrfs / ulist.c
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 <linux/module.h>
9 #include "ulist.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  * The implementation is preliminary and can probably be sped up
18  * significantly. A first step would be to store the values in an rbtree
19  * as soon as ULIST_SIZE is exceeded.
20  *
21  * A sample usage for ulists is the enumeration of directed graphs without
22  * visiting a node twice. The pseudo-code could look like this:
23  *
24  * ulist = ulist_alloc();
25  * ulist_add(ulist, root);
26  * ULIST_ITER_INIT(&uiter);
27  *
28  * while ((elem = ulist_next(ulist, &uiter)) {
29  *      for (all child nodes n in elem)
30  *              ulist_add(ulist, n);
31  *      do something useful with the node;
32  * }
33  * ulist_free(ulist);
34  *
35  * This assumes the graph nodes are adressable by u64. This stems from the
36  * usage for tree enumeration in btrfs, where the logical addresses are
37  * 64 bit.
38  *
39  * It is also useful for tree enumeration which could be done elegantly
40  * recursively, but is not possible due to kernel stack limitations. The
41  * loop would be similar to the above.
42  */
43
44 /**
45  * ulist_init - freshly initialize a ulist
46  * @ulist:      the ulist to initialize
47  *
48  * Note: don't use this function to init an already used ulist, use
49  * ulist_reinit instead.
50  */
51 void ulist_init(struct ulist *ulist)
52 {
53         ulist->nnodes = 0;
54         ulist->nodes = ulist->int_nodes;
55         ulist->nodes_alloced = ULIST_SIZE;
56 }
57 EXPORT_SYMBOL(ulist_init);
58
59 /**
60  * ulist_fini - free up additionally allocated memory for the ulist
61  * @ulist:      the ulist from which to free the additional memory
62  *
63  * This is useful in cases where the base 'struct ulist' has been statically
64  * allocated.
65  */
66 void ulist_fini(struct ulist *ulist)
67 {
68         /*
69          * The first ULIST_SIZE elements are stored inline in struct ulist.
70          * Only if more elements are alocated they need to be freed.
71          */
72         if (ulist->nodes_alloced > ULIST_SIZE)
73                 kfree(ulist->nodes);
74         ulist->nodes_alloced = 0;       /* in case ulist_fini is called twice */
75 }
76 EXPORT_SYMBOL(ulist_fini);
77
78 /**
79  * ulist_reinit - prepare a ulist for reuse
80  * @ulist:      ulist to be reused
81  *
82  * Free up all additional memory allocated for the list elements and reinit
83  * the ulist.
84  */
85 void ulist_reinit(struct ulist *ulist)
86 {
87         ulist_fini(ulist);
88         ulist_init(ulist);
89 }
90 EXPORT_SYMBOL(ulist_reinit);
91
92 /**
93  * ulist_alloc - dynamically allocate a ulist
94  * @gfp_mask:   allocation flags to for base allocation
95  *
96  * The allocated ulist will be returned in an initialized state.
97  */
98 struct ulist *ulist_alloc(gfp_t gfp_mask)
99 {
100         struct ulist *ulist = kmalloc(sizeof(*ulist), gfp_mask);
101
102         if (!ulist)
103                 return NULL;
104
105         ulist_init(ulist);
106
107         return ulist;
108 }
109 EXPORT_SYMBOL(ulist_alloc);
110
111 /**
112  * ulist_free - free dynamically allocated ulist
113  * @ulist:      ulist to free
114  *
115  * It is not necessary to call ulist_fini before.
116  */
117 void ulist_free(struct ulist *ulist)
118 {
119         if (!ulist)
120                 return;
121         ulist_fini(ulist);
122         kfree(ulist);
123 }
124 EXPORT_SYMBOL(ulist_free);
125
126 /**
127  * ulist_add - add an element to the ulist
128  * @ulist:      ulist to add the element to
129  * @val:        value to add to ulist
130  * @aux:        auxiliary value to store along with val
131  * @gfp_mask:   flags to use for allocation
132  *
133  * Note: locking must be provided by the caller. In case of rwlocks write
134  *       locking is needed
135  *
136  * Add an element to a ulist. The @val will only be added if it doesn't
137  * already exist. If it is added, the auxiliary value @aux is stored along with
138  * it. In case @val already exists in the ulist, @aux is ignored, even if
139  * it differs from the already stored value.
140  *
141  * ulist_add returns 0 if @val already exists in ulist and 1 if @val has been
142  * inserted.
143  * In case of allocation failure -ENOMEM is returned and the ulist stays
144  * unaltered.
145  */
146 int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask)
147 {
148         return ulist_add_merge(ulist, val, aux, NULL, gfp_mask);
149 }
150
151 int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux,
152                     u64 *old_aux, gfp_t gfp_mask)
153 {
154         int i;
155
156         for (i = 0; i < ulist->nnodes; ++i) {
157                 if (ulist->nodes[i].val == val) {
158                         if (old_aux)
159                                 *old_aux = ulist->nodes[i].aux;
160                         return 0;
161                 }
162         }
163
164         if (ulist->nnodes >= ulist->nodes_alloced) {
165                 u64 new_alloced = ulist->nodes_alloced + 128;
166                 struct ulist_node *new_nodes;
167                 void *old = NULL;
168
169                 /*
170                  * if nodes_alloced == ULIST_SIZE no memory has been allocated
171                  * yet, so pass NULL to krealloc
172                  */
173                 if (ulist->nodes_alloced > ULIST_SIZE)
174                         old = ulist->nodes;
175
176                 new_nodes = krealloc(old, sizeof(*new_nodes) * new_alloced,
177                                      gfp_mask);
178                 if (!new_nodes)
179                         return -ENOMEM;
180
181                 if (!old)
182                         memcpy(new_nodes, ulist->int_nodes,
183                                sizeof(ulist->int_nodes));
184
185                 ulist->nodes = new_nodes;
186                 ulist->nodes_alloced = new_alloced;
187         }
188         ulist->nodes[ulist->nnodes].val = val;
189         ulist->nodes[ulist->nnodes].aux = aux;
190         ++ulist->nnodes;
191
192         return 1;
193 }
194 EXPORT_SYMBOL(ulist_add);
195
196 /**
197  * ulist_next - iterate ulist
198  * @ulist:      ulist to iterate
199  * @uiter:      iterator variable, initialized with ULIST_ITER_INIT(&iterator)
200  *
201  * Note: locking must be provided by the caller. In case of rwlocks only read
202  *       locking is needed
203  *
204  * This function is used to iterate an ulist.
205  * It returns the next element from the ulist or %NULL when the
206  * end is reached. No guarantee is made with respect to the order in which
207  * the elements are returned. They might neither be returned in order of
208  * addition nor in ascending order.
209  * It is allowed to call ulist_add during an enumeration. Newly added items
210  * are guaranteed to show up in the running enumeration.
211  */
212 struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter)
213 {
214         if (ulist->nnodes == 0)
215                 return NULL;
216         if (uiter->i < 0 || uiter->i >= ulist->nnodes)
217                 return NULL;
218
219         return &ulist->nodes[uiter->i++];
220 }
221 EXPORT_SYMBOL(ulist_next);