sys/ofed/include/linux/linux_radix.c

   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
  40 static MALLOC_DEFINE(M_RADIX, "radix", "Linux radix compat");
  41
  42 static inline int
  43 radix_max(struct radix_tree_root *root)
  44 {
  45         return (1 << (root->height * RADIX_TREE_MAP_SHIFT)) - 1;
  46 }
  47
  48 static inline int
  49 radix_pos(long id, int height)
  50 {
  51         return (id >> (RADIX_TREE_MAP_SHIFT * height)) & RADIX_TREE_MAP_MASK;
  52 }
  53
  54 void *
  55 radix_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
  71 out:
  72         return (item);
  73 }
  74
  75 void *
  76 radix_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                 }
 118 out:
 119         return (item);
 120 }
 121
 122 int
 123 radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
 124 {
 125         struct radix_tree_node *node;
 126         int height;
 127         int idx;
 128
 129         /*
 130          * Expand the tree to fit indexes as big as requested.
 131          */
 132         while (root->rnode == NULL || radix_max(root) < index) {
 133                 node = malloc(sizeof(*node), M_RADIX, root->gfp_mask | M_ZERO);
 134                 if (node == NULL)
 135                         return (-ENOMEM);
 136                 node->slots[0] = root->rnode;
 137                 if (root->rnode)
 138                         node->count++;
 139                 root->rnode = node;
 140                 root->height++;
 141         }
 142         node = root->rnode;
 143         height = root->height - 1;
 144         /*
 145          * Walk down the tree finding the correct node and allocating any
 146          * missing nodes along the way.
 147          */
 148         while (height) {
 149                 idx = radix_pos(index, height);
 150                 if (node->slots[idx] == NULL) {
 151                         node->slots[idx] = malloc(sizeof(*node), M_RADIX,
 152                             root->gfp_mask | M_ZERO);
 153                         if (node->slots[idx] == NULL)
 154                                 return (-ENOMEM);
 155                         node->count++;
 156                 }
 157                 node = node->slots[idx];
 158                 height--;
 159         }
 160         /*
 161          * Insert and adjust count if the item does not already exist.
 162          */
 163         idx = radix_pos(index, 0);
 164         if (node->slots[idx])
 165                 return (-EEXIST);
 166         node->slots[idx] = item;
 167         node->count++;
 168
 169         return (0);
 170 }