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