1 /* $NetBSD: radix-tree.h,v 1.8 2021/12/19 11:51:51 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2021 The NetBSD Foundation, 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, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26 * POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29 #ifndef _LINUX_RADIX_TREE_H_ 30 #define _LINUX_RADIX_TREE_H_ 31 32 #include <sys/radixtree.h> 33 #include <sys/lock.h> 34 35 #include <linux/gfp.h> 36 37 #define INIT_RADIX_TREE linux_INIT_RADIX_TREE 38 #define radix_tree_delete linux_radix_tree_delete 39 #define radix_tree_deref_slot linux_radix_tree_deref_slot 40 #define radix_tree_empty linux_radix_tree_empty 41 #define radix_tree_insert linux_radix_tree_insert 42 #define radix_tree_iter_delete linux_radix_tree_iter_delete 43 #define radix_tree_iter_init linux_radix_tree_iter_init 44 #define radix_tree_lookup linux_radix_tree_lookup 45 #define radix_tree_next_chunk linux_radix_tree_next_chunk 46 #define radix_tree_next_slot linux_radix_tree_next_slot 47 48 struct radix_tree_root { 49 struct radix_tree rtr_tree; 50 __cpu_simple_lock_t rtr_lock; /* XXX lame-o */ 51 }; 52 53 struct radix_tree_iter { 54 unsigned long index; 55 const struct radix_tree_root *rti_tree; 56 }; 57 58 void INIT_RADIX_TREE(struct radix_tree_root *, gfp_t); 59 60 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *); 61 void * radix_tree_delete(struct radix_tree_root *, unsigned long); 62 63 bool radix_tree_empty(struct radix_tree_root *); 64 void * radix_tree_lookup(const struct radix_tree_root *, unsigned long); 65 void * radix_tree_deref_slot(void **); 66 67 void ** radix_tree_iter_init(struct radix_tree_iter *, unsigned long); 68 void ** radix_tree_next_chunk(const struct radix_tree_root *, 69 struct radix_tree_iter *, unsigned); 70 void ** radix_tree_next_slot(void **, struct radix_tree_iter *, unsigned); 71 void radix_tree_iter_delete(struct radix_tree_root *, 72 struct radix_tree_iter *, void **); 73 74 #define radix_tree_for_each_slot(N, T, I, S) \ 75 for ((N) = radix_tree_iter_init((I), (S)); \ 76 (N) || ((N) = radix_tree_next_chunk((T), (I), 0)); \ 77 (N) = radix_tree_next_slot((N), (I), 0)) 78 79 #endif /* _LINUX_RADIX_TREE_H_ */ 80