]>
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> | |
180e001c | 8 | #include <linux/export.h> |
da5c8135 AJ |
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); | |
cd1b413c | 26 | * ULIST_ITER_INIT(&uiter); |
da5c8135 | 27 | * |
cd1b413c | 28 | * while ((elem = ulist_next(ulist, &uiter)) { |
da5c8135 AJ |
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 | */ | |
2eec6c81 | 98 | struct ulist *ulist_alloc(gfp_t gfp_mask) |
da5c8135 AJ |
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 | */ | |
34d73f54 | 146 | int ulist_add(struct ulist *ulist, u64 val, u64 aux, gfp_t gfp_mask) |
3301958b JS |
147 | { |
148 | return ulist_add_merge(ulist, val, aux, NULL, gfp_mask); | |
149 | } | |
150 | ||
34d73f54 AB |
151 | int ulist_add_merge(struct ulist *ulist, u64 val, u64 aux, |
152 | u64 *old_aux, gfp_t gfp_mask) | |
da5c8135 AJ |
153 | { |
154 | int i; | |
155 | ||
156 | for (i = 0; i < ulist->nnodes; ++i) { | |
3301958b JS |
157 | if (ulist->nodes[i].val == val) { |
158 | if (old_aux) | |
159 | *old_aux = ulist->nodes[i].aux; | |
da5c8135 | 160 | return 0; |
3301958b | 161 | } |
da5c8135 AJ |
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 | |
cd1b413c | 199 | * @uiter: iterator variable, initialized with ULIST_ITER_INIT(&iterator) |
da5c8135 AJ |
200 | * |
201 | * Note: locking must be provided by the caller. In case of rwlocks only read | |
202 | * locking is needed | |
203 | * | |
cd1b413c JS |
204 | * This function is used to iterate an ulist. |
205 | * It returns the next element from the ulist or %NULL when the | |
da5c8135 AJ |
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 | */ | |
cd1b413c | 212 | struct ulist_node *ulist_next(struct ulist *ulist, struct ulist_iterator *uiter) |
da5c8135 | 213 | { |
da5c8135 AJ |
214 | if (ulist->nnodes == 0) |
215 | return NULL; | |
cd1b413c | 216 | if (uiter->i < 0 || uiter->i >= ulist->nnodes) |
da5c8135 AJ |
217 | return NULL; |
218 | ||
cd1b413c | 219 | return &ulist->nodes[uiter->i++]; |
da5c8135 AJ |
220 | } |
221 | EXPORT_SYMBOL(ulist_next); |