18d59ecb2SHans Petter Selasky /*-
28d59ecb2SHans Petter Selasky * Copyright (c) 2010 Isilon Systems, Inc.
38d59ecb2SHans Petter Selasky * Copyright (c) 2010 iX Systems, Inc.
48d59ecb2SHans Petter Selasky * Copyright (c) 2010 Panasas, Inc.
5ead15282SHans Petter Selasky * Copyright (c) 2013-2018 Mellanox Technologies, Ltd.
68d59ecb2SHans Petter Selasky * All rights reserved.
78d59ecb2SHans Petter Selasky *
88d59ecb2SHans Petter Selasky * Redistribution and use in source and binary forms, with or without
98d59ecb2SHans Petter Selasky * modification, are permitted provided that the following conditions
108d59ecb2SHans Petter Selasky * are met:
118d59ecb2SHans Petter Selasky * 1. Redistributions of source code must retain the above copyright
128d59ecb2SHans Petter Selasky * notice unmodified, this list of conditions, and the following
138d59ecb2SHans Petter Selasky * disclaimer.
148d59ecb2SHans Petter Selasky * 2. Redistributions in binary form must reproduce the above copyright
158d59ecb2SHans Petter Selasky * notice, this list of conditions and the following disclaimer in the
168d59ecb2SHans Petter Selasky * documentation and/or other materials provided with the distribution.
178d59ecb2SHans Petter Selasky *
188d59ecb2SHans Petter Selasky * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
198d59ecb2SHans Petter Selasky * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
208d59ecb2SHans Petter Selasky * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
218d59ecb2SHans Petter Selasky * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
228d59ecb2SHans Petter Selasky * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
238d59ecb2SHans Petter Selasky * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
248d59ecb2SHans Petter Selasky * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
258d59ecb2SHans Petter Selasky * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
268d59ecb2SHans Petter Selasky * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
278d59ecb2SHans Petter Selasky * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
288d59ecb2SHans Petter Selasky */
29307f78f3SVladimir Kondratyev #ifndef _LINUXKPI_LINUX_RADIX_TREE_H_
30307f78f3SVladimir Kondratyev #define _LINUXKPI_LINUX_RADIX_TREE_H_
318d59ecb2SHans Petter Selasky
328e7baabcSHans Petter Selasky #include <linux/types.h>
338e7baabcSHans Petter Selasky
348d59ecb2SHans Petter Selasky #define RADIX_TREE_MAP_SHIFT 6
35ead15282SHans Petter Selasky #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
36ead15282SHans Petter Selasky #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE - 1UL)
378d59ecb2SHans Petter Selasky #define RADIX_TREE_MAX_HEIGHT \
38ead15282SHans Petter Selasky howmany(sizeof(long) * NBBY, RADIX_TREE_MAP_SHIFT)
39ead15282SHans Petter Selasky
40ead15282SHans Petter Selasky #define RADIX_TREE_ENTRY_MASK 3UL
41ead15282SHans Petter Selasky #define RADIX_TREE_EXCEPTIONAL_ENTRY 2UL
42ead15282SHans Petter Selasky #define RADIX_TREE_EXCEPTIONAL_SHIFT 2
438d59ecb2SHans Petter Selasky
448d59ecb2SHans Petter Selasky struct radix_tree_node {
458d59ecb2SHans Petter Selasky void *slots[RADIX_TREE_MAP_SIZE];
468d59ecb2SHans Petter Selasky int count;
478d59ecb2SHans Petter Selasky };
488d59ecb2SHans Petter Selasky
498d59ecb2SHans Petter Selasky struct radix_tree_root {
508d59ecb2SHans Petter Selasky struct radix_tree_node *rnode;
518d59ecb2SHans Petter Selasky gfp_t gfp_mask;
528d59ecb2SHans Petter Selasky int height;
538d59ecb2SHans Petter Selasky };
548d59ecb2SHans Petter Selasky
55ead15282SHans Petter Selasky struct radix_tree_iter {
56ead15282SHans Petter Selasky unsigned long index;
57ead15282SHans Petter Selasky };
58ead15282SHans Petter Selasky
598d59ecb2SHans Petter Selasky #define RADIX_TREE_INIT(mask) \
608d59ecb2SHans Petter Selasky { .rnode = NULL, .gfp_mask = mask, .height = 0 };
618d59ecb2SHans Petter Selasky #define INIT_RADIX_TREE(root, mask) \
628d59ecb2SHans Petter Selasky { (root)->rnode = NULL; (root)->gfp_mask = mask; (root)->height = 0; }
638d59ecb2SHans Petter Selasky #define RADIX_TREE(name, mask) \
648d59ecb2SHans Petter Selasky struct radix_tree_root name = RADIX_TREE_INIT(mask)
658d59ecb2SHans Petter Selasky
66ead15282SHans Petter Selasky #define radix_tree_for_each_slot(slot, root, iter, start) \
67ead15282SHans Petter Selasky for ((iter)->index = (start); \
68ead15282SHans Petter Selasky radix_tree_iter_find(root, iter, &(slot)); (iter)->index++)
69ead15282SHans Petter Selasky
70ead15282SHans Petter Selasky static inline int
radix_tree_exception(void * arg)71ead15282SHans Petter Selasky radix_tree_exception(void *arg)
72ead15282SHans Petter Selasky {
73ead15282SHans Petter Selasky return ((uintptr_t)arg & RADIX_TREE_ENTRY_MASK);
74ead15282SHans Petter Selasky }
75ead15282SHans Petter Selasky
768d59ecb2SHans Petter Selasky void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
778d59ecb2SHans Petter Selasky void *radix_tree_delete(struct radix_tree_root *, unsigned long);
788d59ecb2SHans Petter Selasky int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
796b839ff4SHans Petter Selasky int radix_tree_store(struct radix_tree_root *, unsigned long, void **);
80ead15282SHans Petter Selasky bool radix_tree_iter_find(struct radix_tree_root *, struct radix_tree_iter *, void ***);
816fad8d17SHans Petter Selasky void radix_tree_iter_delete(struct radix_tree_root *, struct radix_tree_iter *, void **);
828d59ecb2SHans Petter Selasky
83307f78f3SVladimir Kondratyev #endif /* _LINUXKPI_LINUX_RADIX_TREE_H_ */
84