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