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/cdefs.h>
31 __FBSDID("$FreeBSD$");
33 #include <sys/param.h>
34 #include <sys/systm.h>
35 #include <sys/malloc.h>
36 #include <sys/kernel.h>
37 #include <sys/sysctl.h>
39 #include <linux/slab.h>
40 #include <linux/kernel.h>
41 #include <linux/radix-tree.h>
42 #include <linux/err.h>
44 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
47 radix_max(struct radix_tree_root *root)
49 return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
53 radix_pos(long id, int height)
55 return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
59 radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
61 struct radix_tree_node *node;
67 height = root->height - 1;
68 if (index > radix_max(root))
70 while (height && node)
71 node = node->slots[radix_pos(index, height--)];
73 item = node->slots[radix_pos(index, 0)];
80 radix_tree_delete(struct radix_tree_root *root, unsigned long index)
82 struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
83 struct radix_tree_node *node;
90 height = root->height - 1;
91 if (index > radix_max(root))
94 * Find the node and record the path in stack.
96 while (height && node) {
98 node = node->slots[radix_pos(index, height--)];
100 idx = radix_pos(index, 0);
102 item = node->slots[idx];
104 * If we removed something reduce the height of the tree.
108 node->slots[idx] = NULL;
113 if (node == root->rnode) {
119 node = stack[height];
120 idx = radix_pos(index, height);
127 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
129 struct radix_tree_node *node;
130 struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
134 /* bail out upon insertion of a NULL item */
138 /* get root node, if any */
141 /* allocate root node, if any */
143 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
150 /* expand radix tree as needed */
151 while (radix_max(root) < index) {
153 /* check if the radix tree is getting too big */
154 if (root->height == RADIX_TREE_MAX_HEIGHT)
158 * If the root radix level is not empty, we need to
159 * allocate a new radix level:
161 if (node->count != 0) {
162 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
165 node->slots[0] = root->rnode;
172 /* get radix tree height index */
173 height = root->height - 1;
175 /* walk down the tree until the first missing node, if any */
176 for ( ; height != 0; height--) {
177 idx = radix_pos(index, height);
178 if (node->slots[idx] == NULL)
180 node = node->slots[idx];
183 /* allocate the missing radix levels, if any */
184 for (idx = 0; idx != height; idx++) {
185 temp[idx] = malloc(sizeof(*node), M_RADIX,
186 root->gfp_mask | M_ZERO);
187 if (temp[idx] == NULL) {
189 free(temp[idx], M_RADIX);
190 /* Check if we should free the root node as well. */
191 if (root->rnode->count == 0) {
192 free(root->rnode, M_RADIX);
200 /* setup new radix levels, if any */
201 for ( ; height != 0; height--) {
202 idx = radix_pos(index, height);
203 node->slots[idx] = temp[height - 1];
205 node = node->slots[idx];
209 * Insert and adjust count if the item does not already exist.
211 idx = radix_pos(index, 0);
212 if (node->slots[idx])
214 node->slots[idx] = item;