linux_idr.c revision 1.1.2.3
1 /* $NetBSD: linux_idr.c,v 1.1.2.3 2013/07/24 02:07:09 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2013 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #include <sys/cdefs.h> 33 __KERNEL_RCSID(0, "$NetBSD: linux_idr.c,v 1.1.2.3 2013/07/24 02:07:09 riastradh Exp $"); 34 35 #include <sys/param.h> 36 #include <sys/atomic.h> 37 #include <sys/kmem.h> 38 #include <sys/rbtree.h> 39 40 #include <linux/idr.h> 41 42 struct idr_node { 43 rb_node_t in_rb_node; 44 int in_index; 45 void *in_data; 46 }; 47 48 static signed int idr_tree_compare_nodes(void *, const void *, const void *); 49 static signed int idr_tree_compare_key(void *, const void *, const void *); 50 51 static const rb_tree_ops_t idr_rb_ops = { 52 .rbto_compare_nodes = &idr_tree_compare_nodes, 53 .rbto_compare_key = &idr_tree_compare_key, 54 .rbto_node_offset = offsetof(struct idr_node, in_rb_node), 55 .rbto_context = NULL, 56 }; 57 58 static signed int 59 idr_tree_compare_nodes(void *ctx __unused, const void *na, const void *nb) 60 { 61 const int a = ((const struct idr_node *)na)->in_index; 62 const int b = ((const struct idr_node *)nb)->in_index; 63 64 if (a < b) 65 return -1; 66 else if (b < a) 67 return +1; 68 else 69 return 0; 70 } 71 72 static signed int 73 idr_tree_compare_key(void *ctx __unused, const void *n, const void *key) 74 { 75 const int a = ((const struct idr_node *)n)->in_index; 76 const int b = *(const int *)key; 77 78 if (a < b) 79 return -1; 80 else if (b < a) 81 return +1; 82 else 83 return 0; 84 } 85 86 void 87 idr_init(struct idr *idr) 88 { 89 90 rw_init(&idr->idr_lock); 91 rb_tree_init(&idr->idr_tree, &idr_rb_ops); 92 idr->idr_temp = NULL; 93 } 94 95 void 96 idr_destroy(struct idr *idr) 97 { 98 99 if (idr->idr_temp != NULL) { 100 /* XXX Probably shouldn't happen. */ 101 kmem_free(idr->idr_temp, sizeof(*idr->idr_temp)); 102 idr->idr_temp = NULL; 103 } 104 #if 0 /* XXX No rb_tree_destroy? */ 105 rb_tree_destroy(&idr->idr_tree); 106 #endif 107 rw_destroy(&idr->idr_lock); 108 } 109 110 void * 111 idr_find(struct idr *idr, int id) 112 { 113 const struct idr_node *node; 114 void *data; 115 116 rw_enter(&idr->idr_lock, RW_READER); 117 node = rb_tree_find_node(&idr->idr_tree, &id); 118 data = (node == NULL? NULL : node->in_data); 119 rw_exit(&idr->idr_lock); 120 121 return data; 122 } 123 124 void 125 idr_remove(struct idr *idr, int id) 126 { 127 struct idr_node *node; 128 129 rw_enter(&idr->idr_lock, RW_WRITER); 130 node = rb_tree_find_node(&idr->idr_tree, &id); 131 KASSERT(node != NULL); 132 rb_tree_remove_node(&idr->idr_tree, node); 133 rw_exit(&idr->idr_lock); 134 kmem_free(node, sizeof(*node)); 135 } 136 137 void 138 idr_remove_all(struct idr *idr) 139 { 140 struct idr_node *node; 141 142 rw_enter(&idr->idr_lock, RW_WRITER); 143 while ((node = rb_tree_iterate(&idr->idr_tree, NULL, RB_DIR_RIGHT)) != 144 NULL) { 145 rb_tree_remove_node(&idr->idr_tree, node); 146 rw_exit(&idr->idr_lock); 147 kmem_free(node, sizeof(*node)); 148 rw_enter(&idr->idr_lock, RW_WRITER); 149 } 150 rw_exit(&idr->idr_lock); 151 } 152 153 int 154 idr_pre_get(struct idr *idr, int flags __unused /* XXX */) 155 { 156 struct idr_node *const temp = kmem_alloc(sizeof(*temp), KM_SLEEP); 157 158 if (temp == NULL) 159 return 0; 160 161 rw_enter(&idr->idr_lock, RW_WRITER); 162 if (idr->idr_temp == NULL) 163 idr->idr_temp = temp; 164 else 165 kmem_free(temp, sizeof(*temp)); 166 rw_exit(&idr->idr_lock); 167 168 return 1; 169 } 170 171 int 172 idr_get_new_above(struct idr *idr, void *data, int min_id, int *id) 173 { 174 struct idr_node *node, *search, *collision __unused; 175 int want_id = min_id; 176 177 rw_enter(&idr->idr_lock, RW_WRITER); 178 179 node = idr->idr_temp; 180 if (node == NULL) { 181 rw_exit(&idr->idr_lock); 182 return -EAGAIN; 183 } 184 idr->idr_temp = NULL; 185 186 search = rb_tree_find_node_geq(&idr->idr_tree, &min_id); 187 while ((search != NULL) && (search->in_index == want_id)) { 188 search = rb_tree_iterate(&idr->idr_tree, search, RB_DIR_RIGHT); 189 want_id++; 190 } 191 192 node->in_index = want_id; 193 node->in_data = data; 194 195 collision = rb_tree_insert_node(&idr->idr_tree, node); 196 KASSERT(collision == node); 197 198 rw_exit(&idr->idr_lock); 199 200 return 0; 201 } 202
Indexes created Tue Sep 30 06:09:59 GMT 2025