2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
5 * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice unmodified, this list of conditions, and the following
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 #include <sys/param.h>
31 #include <sys/systm.h>
32 #include <sys/malloc.h>
33 #include <sys/kernel.h>
34 #include <sys/sysctl.h>
36 #include <linux/slab.h>
37 #include <linux/kernel.h>
38 #include <linux/radix-tree.h>
39 #include <linux/err.h>
41 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
44 radix_max(struct radix_tree_root *root)
46 return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
50 radix_pos(long id, int height)
52 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
56 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
58 struct radix_tree_node *node;
64 height = root->height - 1;
65 if (index > radix_max(root))
67 while (height && node)
68 node = node->slots[radix_pos(index, height--)];
70 item = node->slots[radix_pos(index, 0)];
77 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
79 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
80 struct radix_tree_node *node;
87 height = root->height - 1;
88 if (index > radix_max(root))
91 * Find the node and record the path in stack.
93 while (height && node) {
95 node = node->slots[radix_pos(index, height--)];
97 idx = radix_pos(index, 0);
99 item = node->slots[idx];
101 * If we removed something reduce the height of the tree.
105 node->slots[idx] = NULL;
110 if (node == root->rnode) {
116 node = stack[height];
117 idx = radix_pos(index, height);
124 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
126 struct radix_tree_node *node;
127 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
131 /* bail out upon insertion of a NULL item */
135 /* get root node, if any */
138 /* allocate root node, if any */
140 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
147 /* expand radix tree as needed */
148 while (radix_max(root) < index) {
150 /* check if the radix tree is getting too big */
151 if (root->height == RADIX_TREE_MAX_HEIGHT)
155 * If the root radix level is not empty, we need to
156 * allocate a new radix level:
158 if (node->count != 0) {
159 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
162 node->slots[0] = root->rnode;
169 /* get radix tree height index */
170 height = root->height - 1;
172 /* walk down the tree until the first missing node, if any */
173 for ( ; height != 0; height--) {
174 idx = radix_pos(index, height);
175 if (node->slots[idx] == NULL)
177 node = node->slots[idx];
180 /* allocate the missing radix levels, if any */
181 for (idx = 0; idx != height; idx++) {
182 temp[idx] = malloc(sizeof(*node), M_RADIX,
183 root->gfp_mask | M_ZERO);
184 if (temp[idx] == NULL) {
186 free(temp[idx], M_RADIX);
187 /* check if we should free the root node aswell */
188 if (root->rnode->count == 0) {
189 free(root->rnode, M_RADIX);
197 /* setup new radix levels, if any */
198 for ( ; height != 0; height--) {
199 idx = radix_pos(index, height);
200 node->slots[idx] = temp[height - 1];
202 node = node->slots[idx];
206 * Insert and adjust count if the item does not already exist.
208 idx = radix_pos(index, 0);
209 if (node->slots[idx])
211 node->slots[idx] = item;