Home | History | Annotate | Line # | Download | only in sys 
      1 /*	$NetBSD: radixtree.h,v 1.7 2020/01/28 16:33:34 ad Exp $	*/
      2 
      3 /*-
      4  * Copyright (c)2011 YAMAMOTO Takashi,
      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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND
     17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
     20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     26  * SUCH DAMAGE.
     27  */
     28 
     29 #if !defined(_SYS_RADIXTREE_H_)
     30 #define	_SYS_RADIXTREE_H_
     31 
     32 struct radix_tree {
     33 	void *t_root;
     34 	unsigned int t_height;
     35 };
     36 
     37 #if defined(_KERNEL) || defined(_STANDALONE)
     38 #include <sys/types.h>
     39 #else /* defined(_KERNEL) || defined(_STANDALONE) */
     40 #include <stdbool.h>
     41 #include <stdint.h>
     42 #endif /* defined(_KERNEL) || defined(_STANDALONE) */
     43 
     44 /*
     45  * subsystem
     46  */
     47 
     48 #if defined(_KERNEL)
     49 void radix_tree_init(void);
     50 void radix_tree_await_memory(void);
     51 #endif /* defined(_KERNEL) */
     52 
     53 /*
     54  * tree
     55  */
     56 
     57 void radix_tree_init_tree(struct radix_tree *);
     58 void radix_tree_fini_tree(struct radix_tree *);
     59 bool radix_tree_empty_tree_p(struct radix_tree *);
     60 
     61 /*
     62  * node
     63  */
     64 
     65 int radix_tree_insert_node(struct radix_tree *, uint64_t, void *);
     66 void *radix_tree_replace_node(struct radix_tree *, uint64_t, void *);
     67 void *radix_tree_remove_node(struct radix_tree *, uint64_t);
     68 void *radix_tree_lookup_node(struct radix_tree *, uint64_t);
     69 unsigned int radix_tree_gang_lookup_node(struct radix_tree *, uint64_t,
     70     void **, unsigned int, bool);
     71 unsigned int radix_tree_gang_lookup_node_reverse(struct radix_tree *, uint64_t,
     72     void **, unsigned int, bool);
     73 
     74 /*
     75  * tag
     76  */
     77 
     78 typedef unsigned int radix_tree_tagmask_t;
     79 #define	RADIX_TREE_TAG_ID_MAX	2
     80 radix_tree_tagmask_t radix_tree_get_tag(struct radix_tree *, uint64_t,
     81     radix_tree_tagmask_t);
     82 void radix_tree_set_tag(struct radix_tree *, uint64_t, radix_tree_tagmask_t);
     83 void radix_tree_clear_tag(struct radix_tree *, uint64_t, radix_tree_tagmask_t);
     84 unsigned int radix_tree_gang_lookup_tagged_node(struct radix_tree *, uint64_t,
     85     void **, unsigned int, bool, radix_tree_tagmask_t);
     86 unsigned int radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *,
     87     uint64_t, void **, unsigned int, bool, radix_tree_tagmask_t);
     88 bool radix_tree_empty_tagged_tree_p(struct radix_tree *, radix_tree_tagmask_t);
     89 
     90 #endif /* !defined(_SYS_RADIXTREE_H_) */
     91