linux_radix.c revision 270166 
1/*-
2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice unmodified, this list of conditions, and the following
12 *    disclaimer.
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.
16 *
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.
27 */
28
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>
34
35#include <linux/slab.h>
36#include <linux/kernel.h>
37#include <linux/radix-tree.h>
38#include <linux/err.h>
39
40static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
41
42static inline int
43radix_max(struct radix_tree_root *root)
44{
45	return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
46}
47
48static inline int
49radix_pos(long id, int height)
50{
51	return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
52}
53
54void *
55radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
56{
57	struct radix_tree_node *node;
58	void *item;
59	int height;
60
61	item = NULL;
62	node = root->rnode;
63	height = root->height - 1;
64	if (index > radix_max(root))
65		goto out;
66	while (height && node)
67		node = node->slots[radix_pos(index, height--)];
68	if (node)
69		item = node->slots[radix_pos(index, 0)];
70
71out:
72	return (item);
73}
74
75void *
76radix_tree_delete(struct radix_tree_root *root, unsigned long index)
77{
78	struct radix_tree_node *stack[RADIX_TREE_MAX_HEIGHT];
79	struct radix_tree_node *node;
80	void *item;
81	int height;
82	int idx;
83
84	item = NULL;
85	node = root->rnode;
86	height = root->height - 1;
87	if (index > radix_max(root))
88		goto out;
89	/*
90	 * Find the node and record the path in stack.
91	 */
92	while (height && node) {
93		stack[height] = node;
94		node = node->slots[radix_pos(index, height--)];
95	}
96	idx = radix_pos(index, 0);
97	if (node)
98		item = node->slots[idx];
99	/*
100	 * If we removed something reduce the height of the tree.
101	 */
102	if (item)
103		for (;;) {
104			node->slots[idx] = NULL;
105			node->count--;
106			if (node->count > 0)
107				break;
108			free(node, M_RADIX);
109			if (node == root->rnode) {
110				root->rnode = NULL;
111				root->height = 0;
112				break;
113			}
114			height++;
115			node = stack[height];
116			idx = radix_pos(index, height);
117		}
118out:
119	return (item);
120}
121
122int
123radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
124{
125	struct radix_tree_node *node;
126	struct radix_tree_node *temp[RADIX_TREE_MAX_HEIGHT - 1];
127	int height;
128	int idx;
129
130	/* bail out upon insertion of a NULL item */
131	if (item == NULL)
132		return (-EINVAL);
133
134	/* get root node, if any */
135	node = root->rnode;
136
137	/* allocate root node, if any */
138	if (node == NULL) {
139		node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
140		if (node == NULL)
141			return (-ENOMEM);
142		root->rnode = node;
143		root->height++;
144	}
145
146	/* expand radix tree as needed */
147	while (radix_max(root) < index) {
148
149		/* check if the radix tree is getting too big */
150		if (root->height == RADIX_TREE_MAX_HEIGHT)
151			return (-E2BIG);
152
153		/*
154		 * If the root radix level is not empty, we need to
155		 * allocate a new radix level:
156		 */
157		if (node->count != 0) {
158			node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
159			if (node == NULL)
160				return (-ENOMEM);
161			node->slots[0] = root->rnode;
162			node->count++;
163			root->rnode = node;
164		}
165		root->height++;
166	}
167
168	/* get radix tree height index */
169	height = root->height - 1;
170
171	/* walk down the tree until the first missing node, if any */
172	for ( ; height != 0; height--) {
173		idx = radix_pos(index, height);
174		if (node->slots[idx] == NULL)
175			break;
176		node = node->slots[idx];
177	}
178
179	/* allocate the missing radix levels, if any */
180	for (idx = 0; idx != height; idx++) {
181		temp[idx] = malloc(sizeof(*node), M_RADIX,
182		    root->gfp_mask | M_ZERO);
183		if (temp[idx] == NULL) {
184			while(idx--)
185				free(temp[idx], M_RADIX);
186			/* check if we should free the root node aswell */
187			if (root->rnode->count == 0) {
188				free(root->rnode, M_RADIX);
189				root->rnode = NULL;
190				root->height = 0;
191			}
192			return (-ENOMEM);
193		}
194	}
195
196	/* setup new radix levels, if any */
197	for ( ; height != 0; height--) {
198		idx = radix_pos(index, height);
199		node->slots[idx] = temp[height - 1];
200		node->count++;
201		node = node->slots[idx];
202	}
203
204	/*
205	 * Insert and adjust count if the item does not already exist.
206	 */
207	idx = radix_pos(index, 0);
208	if (node->slots[idx])
209		return (-EEXIST);
210	node->slots[idx] = item;
211	node->count++;
212
213	return (0);
214}
215