ia64/xen-unstable

view xen/common/radix-tree.c @ 19835:edfdeb150f27

Fix buildsystem to detect udev > version 124

udev removed the udevinfo symlink from versions higher than 123 and
xen's build-system could not detect if udev is in place and has the
required version.

Signed-off-by: Marc-A. Dahlhaus <mad@wol.de>
author Keir Fraser <keir.fraser@citrix.com>
date Thu Jun 25 13:02:37 2009 +0100 (2009-06-25)
parents f210a633571c
children
line source
1 /*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
4 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License as
8 * published by the Free Software Foundation; either version 2, or (at
9 * your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful, but
12 * WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 */
21 /*
22 * Copyright (C) 2009 adaption for Xen tmem by Dan Magenheimer, Oracle Corp.
23 * Changed:
24 * o Linux 2.6.18 source used (prior to read-copy-update addition)
25 * o constants and data structures moved out to radix-tree.h header
26 * o tagging code removed
27 * o radix_tree_insert has func parameter for dynamic data struct allocation
28 * o radix_tree_destroy added (including recursive helper function)
29 * o __init functions must be called explicitly
30 * o other include files adapted to Xen
31 */
33 #include <xen/config.h>
34 #include <xen/lib.h>
35 #include <xen/types.h>
36 #include <xen/errno.h>
37 #include <xen/radix-tree.h>
38 #include <asm/cache.h>
40 static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly;
42 /*
43 * Return the maximum key which can be store into a
44 * radix tree with height HEIGHT.
45 */
46 static inline unsigned long radix_tree_maxindex(unsigned int height)
47 {
48 return height_to_maxindex[height];
49 }
51 /*
52 * Extend a radix tree so it can store key @index.
53 */
54 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index,
55 struct radix_tree_node *(*node_alloc)(void *), void *arg)
56 {
57 struct radix_tree_node *node;
58 unsigned int height;
60 /* Figure out what the height should be. */
61 height = root->height + 1;
62 if (index > radix_tree_maxindex(height))
63 while (index > radix_tree_maxindex(height))
64 height++;
66 if (root->rnode == NULL) {
67 root->height = height;
68 goto out;
69 }
71 do {
72 if (!(node = node_alloc(arg)))
73 return -ENOMEM;
75 /* Increase the height. */
76 node->slots[0] = root->rnode;
78 node->count = 1;
79 root->rnode = node;
80 root->height++;
81 } while (height > root->height);
82 out:
83 return 0;
84 }
86 /**
87 * radix_tree_insert - insert into a radix tree
88 * @root: radix tree root
89 * @index: index key
90 * @item: item to insert
91 *
92 * Insert an item into the radix tree at position @index.
93 */
94 int radix_tree_insert(struct radix_tree_root *root, unsigned long index,
95 void *item, struct radix_tree_node *(*node_alloc)(void *), void *arg)
96 {
97 struct radix_tree_node *node = NULL, *slot;
98 unsigned int height, shift;
99 int offset;
100 int error;
102 /* Make sure the tree is high enough. */
103 if (index > radix_tree_maxindex(root->height)) {
104 error = radix_tree_extend(root, index, node_alloc, arg);
105 if (error)
106 return error;
107 }
109 slot = root->rnode;
110 height = root->height;
111 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
113 offset = 0; /* uninitialised var warning */
114 while (height > 0) {
115 if (slot == NULL) {
116 /* Have to add a child node. */
117 if (!(slot = node_alloc(arg)))
118 return -ENOMEM;
119 if (node) {
121 node->slots[offset] = slot;
122 node->count++;
123 } else
124 root->rnode = slot;
125 }
127 /* Go a level down */
128 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
129 node = slot;
130 slot = node->slots[offset];
131 shift -= RADIX_TREE_MAP_SHIFT;
132 height--;
133 }
135 if (slot != NULL)
136 return -EEXIST;
138 if (node) {
139 node->count++;
140 node->slots[offset] = item;
141 } else {
142 root->rnode = item;
143 }
145 return 0;
146 }
147 EXPORT_SYMBOL(radix_tree_insert);
149 static inline void **__lookup_slot(struct radix_tree_root *root,
150 unsigned long index)
151 {
152 unsigned int height, shift;
153 struct radix_tree_node **slot;
155 height = root->height;
157 if (index > radix_tree_maxindex(height))
158 return NULL;
160 if (height == 0 && root->rnode)
161 return (void **)&root->rnode;
163 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
164 slot = &root->rnode;
166 while (height > 0) {
167 if (*slot == NULL)
168 return NULL;
170 slot = (struct radix_tree_node **)
171 ((*slot)->slots +
172 ((index >> shift) & RADIX_TREE_MAP_MASK));
173 shift -= RADIX_TREE_MAP_SHIFT;
174 height--;
175 }
177 return (void **)slot;
178 }
180 /**
181 * radix_tree_lookup_slot - lookup a slot in a radix tree
182 * @root: radix tree root
183 * @index: index key
184 *
185 * Lookup the slot corresponding to the position @index in the radix tree
186 * @root. This is useful for update-if-exists operations.
187 */
188 void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
189 {
190 return __lookup_slot(root, index);
191 }
192 EXPORT_SYMBOL(radix_tree_lookup_slot);
194 /**
195 * radix_tree_lookup - perform lookup operation on a radix tree
196 * @root: radix tree root
197 * @index: index key
198 *
199 * Lookup the item at the position @index in the radix tree @root.
200 */
201 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
202 {
203 void **slot;
205 slot = __lookup_slot(root, index);
206 return slot != NULL ? *slot : NULL;
207 }
208 EXPORT_SYMBOL(radix_tree_lookup);
210 static unsigned int
211 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
212 unsigned int max_items, unsigned long *next_index)
213 {
214 unsigned int nr_found = 0;
215 unsigned int shift, height;
216 struct radix_tree_node *slot;
217 unsigned long i;
219 height = root->height;
220 if (index > radix_tree_maxindex(height))
221 if (height == 0) {
222 if (root->rnode && index == 0)
223 results[nr_found++] = root->rnode;
224 goto out;
225 }
227 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
228 slot = root->rnode;
230 for ( ; height > 1; height--) {
232 for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
233 i < RADIX_TREE_MAP_SIZE; i++) {
234 if (slot->slots[i] != NULL)
235 break;
236 index &= ~((1UL << shift) - 1);
237 index += 1UL << shift;
238 if (index == 0)
239 goto out; /* 32-bit wraparound */
240 }
241 if (i == RADIX_TREE_MAP_SIZE)
242 goto out;
244 shift -= RADIX_TREE_MAP_SHIFT;
245 slot = slot->slots[i];
246 }
248 /* Bottom level: grab some items */
249 for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
250 index++;
251 if (slot->slots[i]) {
252 results[nr_found++] = slot->slots[i];
253 if (nr_found == max_items)
254 goto out;
255 }
256 }
257 out:
258 *next_index = index;
259 return nr_found;
260 }
262 /**
263 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
264 * @root: radix tree root
265 * @results: where the results of the lookup are placed
266 * @first_index: start the lookup from this key
267 * @max_items: place up to this many items at *results
268 *
269 * Performs an index-ascending scan of the tree for present items. Places
270 * them at *@results and returns the number of items which were placed at
271 * *@results.
272 *
273 * The implementation is naive.
274 */
275 unsigned int
276 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
277 unsigned long first_index, unsigned int max_items)
278 {
279 const unsigned long max_index = radix_tree_maxindex(root->height);
280 unsigned long cur_index = first_index;
281 unsigned int ret = 0;
283 while (ret < max_items) {
284 unsigned int nr_found;
285 unsigned long next_index; /* Index of next search */
287 if (cur_index > max_index)
288 break;
289 nr_found = __lookup(root, results + ret, cur_index,
290 max_items - ret, &next_index);
291 ret += nr_found;
292 if (next_index == 0)
293 break;
294 cur_index = next_index;
295 }
296 return ret;
297 }
298 EXPORT_SYMBOL(radix_tree_gang_lookup);
300 /**
301 * radix_tree_shrink - shrink height of a radix tree to minimal
302 * @root radix tree root
303 */
304 static inline void radix_tree_shrink(struct radix_tree_root *root,
305 void (*node_free)(struct radix_tree_node *))
306 {
307 /* try to shrink tree height */
308 while (root->height > 0 &&
309 root->rnode->count == 1 &&
310 root->rnode->slots[0]) {
311 struct radix_tree_node *to_free = root->rnode;
313 root->rnode = to_free->slots[0];
314 root->height--;
315 to_free->slots[0] = NULL;
316 to_free->count = 0;
317 node_free(to_free);
318 }
319 }
321 /**
322 * radix_tree_delete - delete an item from a radix tree
323 * @root: radix tree root
324 * @index: index key
325 *
326 * Remove the item at @index from the radix tree rooted at @root.
327 *
328 * Returns the address of the deleted item, or NULL if it was not present.
329 */
330 void *radix_tree_delete(struct radix_tree_root *root, unsigned long index,
331 void(*node_free)(struct radix_tree_node *))
332 {
333 struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
334 struct radix_tree_node *slot = NULL;
335 unsigned int height, shift;
336 int offset;
338 height = root->height;
339 if (index > radix_tree_maxindex(height))
340 goto out;
342 slot = root->rnode;
343 if (height == 0 && root->rnode) {
344 root->rnode = NULL;
345 goto out;
346 }
348 shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
349 pathp->node = NULL;
351 do {
352 if (slot == NULL)
353 goto out;
355 pathp++;
356 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
357 pathp->offset = offset;
358 pathp->node = slot;
359 slot = slot->slots[offset];
360 shift -= RADIX_TREE_MAP_SHIFT;
361 height--;
362 } while (height > 0);
364 if (slot == NULL)
365 goto out;
367 /* Now free the nodes we do not need anymore */
368 while (pathp->node) {
369 pathp->node->slots[pathp->offset] = NULL;
370 pathp->node->count--;
372 if (pathp->node->count) {
373 if (pathp->node == root->rnode)
374 radix_tree_shrink(root, node_free);
375 goto out;
376 }
378 /* Node with zero slots in use so free it */
379 node_free(pathp->node);
381 pathp--;
382 }
383 root->height = 0;
384 root->rnode = NULL;
386 out:
387 return slot;
388 }
389 EXPORT_SYMBOL(radix_tree_delete);
391 static void
392 radix_tree_node_destroy(struct radix_tree_node *node, unsigned int height,
393 void (*slot_free)(void *), void (*node_free)(struct radix_tree_node *))
394 {
395 int i;
397 if (height == 0)
398 return;
399 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
400 if (node->slots[i]) {
401 if (height == 1) {
402 slot_free(node->slots[i]);
403 node->slots[i] = NULL;
404 continue;
405 }
406 radix_tree_node_destroy(node->slots[i], height-1,
407 slot_free, node_free);
408 node_free(node->slots[i]);
409 node->slots[i] = NULL;
410 }
411 }
412 }
414 void radix_tree_destroy(struct radix_tree_root *root,
415 void (*slot_free)(void *), void (*node_free)(struct radix_tree_node *))
416 {
417 if (root->rnode == NULL)
418 return;
419 if (root->height == 0)
420 slot_free(root->rnode);
421 else {
422 radix_tree_node_destroy(root->rnode, root->height,
423 slot_free, node_free);
424 node_free(root->rnode);
425 root->height = 0;
426 }
427 root->rnode = NULL;
428 /* caller must delete root if desired */
429 }
430 EXPORT_SYMBOL(radix_tree_destroy);
432 static /*__init*/ unsigned long __maxindex(unsigned int height)
433 {
434 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
435 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
437 if (tmp >= RADIX_TREE_INDEX_BITS)
438 index = ~0UL;
439 return index;
440 }
442 /*__init*/ void radix_tree_init(void)
443 {
444 unsigned int i;
446 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
447 height_to_maxindex[i] = __maxindex(i);
448 }