Home | History | Annotate | Line # | Download | only in linux
linux_radixtree.c revision 1.1 
      1 /*	$NetBSD: linux_radixtree.c,v 1.1 2021/12/19 11:51:43 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 #include <sys/cdefs.h>
     30 __KERNEL_RCSID(0, "$NetBSD: linux_radixtree.c,v 1.1 2021/12/19 11:51:43 riastradh Exp $");
     31 
     32 #include <sys/radixtree.h>
     33 
     34 #include <linux/gfp.h>
     35 #include <linux/radix-tree.h>
     36 
     37 struct kludge {
     38 	uint64_t	k_key;
     39 	void		*k_datum;
     40 };
     41 
     42 void
     43 INIT_RADIX_TREE(struct radix_tree_root *root, gfp_t gfp)
     44 {
     45 
     46 	radix_tree_init_tree(&root->rtr_tree);
     47 }
     48 
     49 int
     50 radix_tree_insert(struct radix_tree_root *root, unsigned long key, void *datum)
     51 {
     52 	struct kludge *kludge;
     53 
     54 	if ((kludge = kmem_zalloc(sizeof(*kludge), KM_NOSLEEP)) == NULL)
     55 		return -ENOMEM;
     56 
     57 	kludge->k_key = key;
     58 	kludge->k_datum = datum;
     59 
     60 	/* XXX errno NetBSD->Linux */
     61 	return -radix_tree_insert_node(&root->rtr_tree, key, kludge);
     62 }
     63 
     64 void *
     65 radix_tree_delete(struct radix_tree_root *root, unsigned long key)
     66 {
     67 	struct kludge *kludge;
     68 	void *datum = NULL;
     69 
     70 	if ((kludge = radix_tree_remove_node(&root->rtr_tree, key)) == NULL)
     71 		return NULL;
     72 
     73 	/* XXX RCU defer */
     74 	datum = kludge->k_datum;
     75 	kmem_free(kludge, sizeof(*kludge));
     76 
     77 	return datum;
     78 }
     79 
     80 bool
     81 radix_tree_empty(struct radix_tree_root *root)
     82 {
     83 
     84 	return radix_tree_empty_tree_p(&root->rtr_tree);
     85 }
     86 
     87 void *
     88 radix_tree_lookup(const struct radix_tree_root *root, unsigned long key)
     89 {
     90 	struct kludge *kludge;
     91 
     92 	kludge = radix_tree_lookup_node(&root->rtr_tree, key);
     93 	if (kludge == NULL)
     94 		NULL;
     95 
     96 	return kludge->k_datum;
     97 }
     98 
     99 void *
    100 radix_tree_deref_slot(void **slot)
    101 {
    102 
    103 	return atomic_load_consume(slot);
    104 }
    105 
    106 void **
    107 radix_tree_iter_init(struct radix_tree_iter *I, unsigned long start)
    108 {
    109 
    110 	I->index = start;
    111 	I->rti_tree = NULL;
    112 	return NULL;
    113 }
    114 
    115 void **
    116 radix_tree_next_chunk(const struct radix_tree_root *root,
    117     struct radix_tree_iter *I, unsigned flags)
    118 {
    119 	void *result;
    120 	struct kludge *kludge;
    121 
    122 	KASSERT(flags == 0);
    123 	if (radix_tree_gang_lookup_node(&root->rtr_tree, I->index,
    124 		&result, /*maxresults*/1, /*dense*/false) == 0)
    125 		return NULL;
    126 
    127 	kludge = result;
    128 
    129 	I->index = kludge->k_key;
    130 	I->rti_tree = &root->rtr_tree;
    131 	return &kludge->k_datum;
    132 }
    133 
    134 void **
    135 radix_tree_next_slot(void **slot, struct radix_tree_iter *I, unsigned flags)
    136 {
    137 	struct kludge *kludge;
    138 	void *result;
    139 
    140 	KASSERT(flags == 0);
    141 	kludge = container_of(slot, struct kludge, k_datum);
    142 	if (radix_tree_gang_lookup_node(I->rtr_tree, kludge->k_key,
    143 		&result, /*maxresults*/1, /*dense*/true) == 0)
    144 		return NULL;
    145 
    146 	kludge = result;
    147 
    148 	I->index = kludge->k_key;
    149 	I->rti_tree = &root->rtr_tree;
    150 	return &kludge->k_datum;
    151 }
    152 
    153 void
    154 radix_tree_iter_delete(struct radix_tree_root *root, struct radix_tree_iter *I,
    155     void **slot)
    156 {
    157 	struct kludge *kludge = container_of(slot, struct kludge, k_datum);
    158 	struct kludge *kludge0 __diagused;
    159 
    160 	kludge0 = radix_tree_remove_node(&root->rtr_tree, kludge->k_key);
    161 	KASSERT(kludge0 == kludge);
    162 }
    163