2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
10 * 1. Redistributions of source code must retain the above copyright
11 * notice unmodified, this list of conditions, and the following
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 #include <sys/param.h>
30 #include <sys/systm.h>
31 #include <sys/malloc.h>
32 #include <sys/kernel.h>
33 #include <sys/sysctl.h>
35 #include <linux/slab.h>
36 #include <linux/kernel.h>
37 #include <linux/radix-tree.h>
38 #include <linux/err.h>
40 MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
43 radix_max(struct radix_tree_root *root)
45 return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
49 radix_pos(long id, int height)
51 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
55 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
57 struct radix_tree_node *node;
63 height = root->height - 1;
64 if (index > radix_max(root))
66 while (height && node)
67 node = node->slots[radix_pos(index, height--)];
69 item = node->slots[radix_pos(index, 0)];
76 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
78 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
79 struct radix_tree_node *node;
86 height = root->height - 1;
87 if (index > radix_max(root))
90 * Find the node and record the path in stack.
92 while (height && node) {
94 node = node->slots[radix_pos(index, height--)];
96 idx = radix_pos(index, 0);
98 item = node->slots[idx];
100 * If we removed something reduce the height of the tree.
104 node->slots[idx] = NULL;
109 if (node == root->rnode) {
115 node = stack[height];
116 idx = radix_pos(index, height);
123 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
125 struct radix_tree_node *node;
130 * Expand the tree to fit indexes as big as requested.
132 while (root->rnode == NULL || radix_max(root) < index) {
133 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
136 node->slots[0] = root->rnode;
143 height = root->height - 1;
145 * Walk down the tree finding the correct node and allocating any
146 * missing nodes along the way.
149 idx = radix_pos(index, height);
150 if (node->slots[idx] == NULL) {
151 node->slots[idx] = malloc(sizeof(*node), M_RADIX,
152 root->gfp_mask | M_ZERO);
153 if (node->slots[idx] == NULL)
157 node = node->slots[idx];
161 * Insert and adjust count if the item does not already exist.
163 idx = radix_pos(index, 0);
164 if (node->slots[idx])
166 node->slots[idx] = item;