1 1.7 ad /* $NetBSD: radixtree.h,v 1.7 2020/01/28 16:33:34 ad Exp $ */ 2 1.1 yamt 3 1.1 yamt /*- 4 1.1 yamt * Copyright (c)2011 YAMAMOTO Takashi, 5 1.1 yamt * All rights reserved. 6 1.1 yamt * 7 1.1 yamt * Redistribution and use in source and binary forms, with or without 8 1.1 yamt * modification, are permitted provided that the following conditions 9 1.1 yamt * are met: 10 1.1 yamt * 1. Redistributions of source code must retain the above copyright 11 1.1 yamt * notice, this list of conditions and the following disclaimer. 12 1.1 yamt * 2. Redistributions in binary form must reproduce the above copyright 13 1.1 yamt * notice, this list of conditions and the following disclaimer in the 14 1.1 yamt * documentation and/or other materials provided with the distribution. 15 1.1 yamt * 16 1.1 yamt * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 1.1 yamt * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 1.1 yamt * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 1.1 yamt * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 1.1 yamt * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 1.1 yamt * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 1.1 yamt * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 1.1 yamt * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 1.1 yamt * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 1.1 yamt * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 1.1 yamt * SUCH DAMAGE. 27 1.1 yamt */ 28 1.1 yamt 29 1.1 yamt #if !defined(_SYS_RADIXTREE_H_) 30 1.1 yamt #define _SYS_RADIXTREE_H_ 31 1.1 yamt 32 1.1 yamt struct radix_tree { 33 1.1 yamt void *t_root; 34 1.1 yamt unsigned int t_height; 35 1.1 yamt }; 36 1.1 yamt 37 1.2 yamt #if defined(_KERNEL) || defined(_STANDALONE) 38 1.1 yamt #include <sys/types.h> 39 1.2 yamt #else /* defined(_KERNEL) || defined(_STANDALONE) */ 40 1.1 yamt #include <stdbool.h> 41 1.1 yamt #include <stdint.h> 42 1.2 yamt #endif /* defined(_KERNEL) || defined(_STANDALONE) */ 43 1.1 yamt 44 1.1 yamt /* 45 1.1 yamt * subsystem 46 1.1 yamt */ 47 1.1 yamt 48 1.1 yamt #if defined(_KERNEL) 49 1.1 yamt void radix_tree_init(void); 50 1.7 ad void radix_tree_await_memory(void); 51 1.1 yamt #endif /* defined(_KERNEL) */ 52 1.1 yamt 53 1.1 yamt /* 54 1.1 yamt * tree 55 1.1 yamt */ 56 1.1 yamt 57 1.1 yamt void radix_tree_init_tree(struct radix_tree *); 58 1.1 yamt void radix_tree_fini_tree(struct radix_tree *); 59 1.3 yamt bool radix_tree_empty_tree_p(struct radix_tree *); 60 1.1 yamt 61 1.1 yamt /* 62 1.1 yamt * node 63 1.1 yamt */ 64 1.1 yamt 65 1.1 yamt int radix_tree_insert_node(struct radix_tree *, uint64_t, void *); 66 1.1 yamt void *radix_tree_replace_node(struct radix_tree *, uint64_t, void *); 67 1.1 yamt void *radix_tree_remove_node(struct radix_tree *, uint64_t); 68 1.1 yamt void *radix_tree_lookup_node(struct radix_tree *, uint64_t); 69 1.1 yamt unsigned int radix_tree_gang_lookup_node(struct radix_tree *, uint64_t, 70 1.6 ad void **, unsigned int, bool); 71 1.4 yamt unsigned int radix_tree_gang_lookup_node_reverse(struct radix_tree *, uint64_t, 72 1.6 ad void **, unsigned int, bool); 73 1.1 yamt 74 1.1 yamt /* 75 1.1 yamt * tag 76 1.1 yamt */ 77 1.1 yamt 78 1.6 ad typedef unsigned int radix_tree_tagmask_t; 79 1.1 yamt #define RADIX_TREE_TAG_ID_MAX 2 80 1.6 ad radix_tree_tagmask_t radix_tree_get_tag(struct radix_tree *, uint64_t, 81 1.6 ad radix_tree_tagmask_t); 82 1.6 ad void radix_tree_set_tag(struct radix_tree *, uint64_t, radix_tree_tagmask_t); 83 1.6 ad void radix_tree_clear_tag(struct radix_tree *, uint64_t, radix_tree_tagmask_t); 84 1.1 yamt unsigned int radix_tree_gang_lookup_tagged_node(struct radix_tree *, uint64_t, 85 1.6 ad void **, unsigned int, bool, radix_tree_tagmask_t); 86 1.4 yamt unsigned int radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *, 87 1.6 ad uint64_t, void **, unsigned int, bool, radix_tree_tagmask_t); 88 1.6 ad bool radix_tree_empty_tagged_tree_p(struct radix_tree *, radix_tree_tagmask_t); 89 1.1 yamt 90 1.1 yamt #endif /* !defined(_SYS_RADIXTREE_H_) */ 91
Indexes created Sun Sep 21 18:09:52 GMT 2025