2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License as
7 * published by the Free Software Foundation; either version 2, or (at
8 * your option) any later version.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 #include <linux/errno.h>
21 #include <linux/init.h>
22 #include <linux/kernel.h>
23 #include <linux/mempool.h>
24 #include <linux/module.h>
25 #include <linux/radix-tree.h>
26 #include <linux/slab.h>
27 #include <linux/string.h>
30 * Radix tree node definition.
32 #define RADIX_TREE_MAP_SHIFT 6
33 #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
34 #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
36 struct radix_tree_node {
38 void *slots[RADIX_TREE_MAP_SIZE];
41 struct radix_tree_path {
42 struct radix_tree_node *node, **slot;
45 #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
46 #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
49 * Radix tree node cache.
51 static kmem_cache_t *radix_tree_node_cachep;
52 static mempool_t *radix_tree_node_pool;
54 static inline struct radix_tree_node *
55 radix_tree_node_alloc(struct radix_tree_root *root)
57 return mempool_alloc(radix_tree_node_pool, root->gfp_mask);
61 radix_tree_node_free(struct radix_tree_node *node)
63 mempool_free(node, radix_tree_node_pool);
67 * Return the maximum key which can be store into a
68 * radix tree with height HEIGHT.
70 static inline unsigned long radix_tree_maxindex(unsigned int height)
72 unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
73 unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
75 if (tmp >= RADIX_TREE_INDEX_BITS)
81 * Extend a radix tree so it can store key @index.
83 static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
85 struct radix_tree_node *node;
88 /* Figure out what the height should be. */
89 height = root->height + 1;
90 while (index > radix_tree_maxindex(height))
95 if (!(node = radix_tree_node_alloc(root)))
98 /* Increase the height. */
99 node->slots[0] = root->rnode;
104 } while (height > root->height);
106 root->height = height;
112 * radix_tree_insert - insert into a radix tree
113 * @root: radix tree root
115 * @item: item to insert
117 * Insert an item into the radix tree at position @index.
119 int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
121 struct radix_tree_node *node = NULL, *tmp, **slot;
122 unsigned int height, shift;
125 /* Make sure the tree is high enough. */
126 if (index > radix_tree_maxindex(root->height)) {
127 error = radix_tree_extend(root, index);
133 height = root->height;
134 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
138 /* Have to add a child node. */
139 if (!(tmp = radix_tree_node_alloc(root)))
146 /* Go a level down. */
148 slot = (struct radix_tree_node **)
149 (node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
150 shift -= RADIX_TREE_MAP_SHIFT;
162 EXPORT_SYMBOL(radix_tree_insert);
165 * radix_tree_lookup - perform lookup operation on a radix tree
166 * @root: radix tree root
169 * Lookup them item at the position @index in the radix tree @root.
171 void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
173 unsigned int height, shift;
174 struct radix_tree_node **slot;
176 height = root->height;
177 if (index > radix_tree_maxindex(height))
180 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
187 slot = (struct radix_tree_node **)
188 ((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
189 shift -= RADIX_TREE_MAP_SHIFT;
193 return (void *) *slot;
195 EXPORT_SYMBOL(radix_tree_lookup);
197 static /* inline */ unsigned int
198 __lookup(struct radix_tree_root *root, void **results, unsigned long index,
199 unsigned int max_items, unsigned long *next_index,
200 unsigned long max_index)
202 unsigned int nr_found = 0;
204 unsigned int height = root->height;
205 struct radix_tree_node *slot;
207 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
211 unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
212 for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
213 if (slot->slots[i] != NULL)
215 index &= ~((1 << shift) - 1);
218 if (i == RADIX_TREE_MAP_SIZE)
221 shift -= RADIX_TREE_MAP_SHIFT;
223 /* Bottom level: grab some items */
226 BUG_ON((shift + RADIX_TREE_MAP_SHIFT) != 0);
228 j = index & RADIX_TREE_MAP_MASK;
229 for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
231 if (slot->slots[j]) {
232 results[nr_found++] = slot->slots[j];
233 if (nr_found == max_items)
238 slot = slot->slots[i];
246 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
247 * @root: radix tree root
248 * @results: where the results of the lookup are placed
249 * @first_index: start the lookup from this key
250 * @max_items: place up to this many items at *results
252 * Performs an index-ascending scan of the tree for present items. Places
253 * them at *@results and returns the number of items which were placed at
256 * The implementation is naive.
259 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
260 unsigned long first_index, unsigned int max_items)
262 const unsigned long max_index = radix_tree_maxindex(root->height);
263 unsigned long cur_index = first_index;
264 unsigned int ret = 0;
266 if (root->rnode == NULL)
268 if (max_index == 0) { /* Bah. Special case */
269 if (first_index == 0) {
271 *results = root->rnode;
277 while (ret < max_items) {
278 unsigned int nr_found;
279 unsigned long next_index; /* Index of next search */
281 if (cur_index > max_index)
283 nr_found = __lookup(root, results + ret, cur_index,
284 max_items - ret, &next_index, max_index);
286 if (next_index == max_index)
288 cur_index = next_index;
293 EXPORT_SYMBOL(radix_tree_gang_lookup);
296 * radix_tree_delete - delete an item from a radix tree
297 * @root: radix tree root
300 * Remove the item at @index from the radix tree rooted at @root.
302 int radix_tree_delete(struct radix_tree_root *root, unsigned long index)
304 struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
305 unsigned int height, shift;
307 height = root->height;
308 if (index > radix_tree_maxindex(height))
311 shift = (height-1) * RADIX_TREE_MAP_SHIFT;
313 pathp->slot = &root->rnode;
316 if (*pathp->slot == NULL)
319 pathp[1].node = *pathp[0].slot;
320 pathp[1].slot = (struct radix_tree_node **)
321 (pathp[1].node->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
323 shift -= RADIX_TREE_MAP_SHIFT;
327 if (*pathp[0].slot == NULL)
330 *pathp[0].slot = NULL;
331 while (pathp[0].node && --pathp[0].node->count == 0) {
333 *pathp[0].slot = NULL;
334 radix_tree_node_free(pathp[1].node);
337 if (root->rnode == NULL)
338 root->height = 0; /* Empty tree, we can reset the height */
342 EXPORT_SYMBOL(radix_tree_delete);
344 static void radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags)
346 memset(node, 0, sizeof(struct radix_tree_node));
349 static void *radix_tree_node_pool_alloc(int gfp_mask, void *data)
351 return kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
354 static void radix_tree_node_pool_free(void *node, void *data)
356 kmem_cache_free(radix_tree_node_cachep, node);
360 * FIXME! 512 nodes is 200-300k of memory. This needs to be
361 * scaled by the amount of available memory, and hopefully
364 void __init radix_tree_init(void)
366 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
367 sizeof(struct radix_tree_node), 0,
368 SLAB_HWCACHE_ALIGN, radix_tree_node_ctor, NULL);
369 if (!radix_tree_node_cachep)
370 panic ("Failed to create radix_tree_node cache\n");
371 radix_tree_node_pool = mempool_create(512, radix_tree_node_pool_alloc,
372 radix_tree_node_pool_free, NULL);
373 if (!radix_tree_node_pool)
374 panic ("Failed to create radix_tree_node pool\n");