| /kernel/linux/linux-6.6/tools/testing/radix-tree/ |
| D | tag_check.c | 8 #include <linux/radix-tree.h>
14 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) in __simple_checks() argument
19 item_check_absent(tree, index); in __simple_checks()
20 assert(item_tag_get(tree, index, tag) == 0); in __simple_checks()
22 item_insert(tree, index); in __simple_checks()
23 assert(item_tag_get(tree, index, tag) == 0); in __simple_checks()
24 item_tag_set(tree, index, tag); in __simple_checks()
25 ret = item_tag_get(tree, index, tag); in __simple_checks()
27 ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag); in __simple_checks()
29 ret = item_tag_get(tree, index, !tag); in __simple_checks()
[all …]
|
| D | main.c | 10 #include <linux/radix-tree.h>
18 RADIX_TREE(tree, GFP_KERNEL); in __gang_check()
23 item_insert(&tree, middle + idx); in __gang_check()
25 item_check_absent(&tree, middle - down - 1); in __gang_check()
27 item_check_present(&tree, middle + idx); in __gang_check()
28 item_check_absent(&tree, middle + up); in __gang_check()
31 item_gang_check_present(&tree, middle - down, up + down, in __gang_check()
33 item_full_scan(&tree, middle - down, down + up, chunk); in __gang_check()
35 item_kill_tree(&tree); in __gang_check()
81 RADIX_TREE(tree, GFP_KERNEL); in add_and_check()
[all …]
|
| /kernel/linux/linux-5.10/tools/testing/radix-tree/ |
| D | tag_check.c | 8 #include <linux/radix-tree.h>
14 __simple_checks(struct radix_tree_root *tree, unsigned long index, int tag) in __simple_checks() argument
19 item_check_absent(tree, index); in __simple_checks()
20 assert(item_tag_get(tree, index, tag) == 0); in __simple_checks()
22 item_insert(tree, index); in __simple_checks()
23 assert(item_tag_get(tree, index, tag) == 0); in __simple_checks()
24 item_tag_set(tree, index, tag); in __simple_checks()
25 ret = item_tag_get(tree, index, tag); in __simple_checks()
27 ret = tag_tagged_items(tree, first, ~0UL, 10, tag, !tag); in __simple_checks()
29 ret = item_tag_get(tree, index, !tag); in __simple_checks()
[all …]
|
| D | main.c | 10 #include <linux/radix-tree.h>
18 RADIX_TREE(tree, GFP_KERNEL); in __gang_check()
23 item_insert(&tree, middle + idx); in __gang_check()
25 item_check_absent(&tree, middle - down - 1); in __gang_check()
27 item_check_present(&tree, middle + idx); in __gang_check()
28 item_check_absent(&tree, middle + up); in __gang_check()
31 item_gang_check_present(&tree, middle - down, up + down, in __gang_check()
33 item_full_scan(&tree, middle - down, down + up, chunk); in __gang_check()
35 item_kill_tree(&tree); in __gang_check()
81 RADIX_TREE(tree, GFP_KERNEL); in add_and_check()
[all …]
|
| /kernel/linux/linux-5.10/fs/hfs/ |
| D | btree.c | 18 /* Get a reference to a B*Tree and do some initial checks */
21 struct hfs_btree *tree; in hfs_btree_open() local
27 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
28 if (!tree) in hfs_btree_open()
31 mutex_init(&tree->tree_lock); in hfs_btree_open()
32 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
34 tree->sb = sb; in hfs_btree_open()
35 tree->cnid = id; in hfs_btree_open()
36 tree->keycmp = keycmp; in hfs_btree_open()
38 tree->inode = iget_locked(sb, id); in hfs_btree_open()
[all …]
|
| D | brec.c | 16 static int hfs_btree_inc_height(struct hfs_btree *tree);
24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
45 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
50 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
56 if (retval > node->tree->max_key_len + 1) { in hfs_brec_keylen()
[all …]
|
| D | bnode.c | 31 if (pagenum >= node->tree->pages_per_bnode) in hfs_bnode_read()
63 struct hfs_btree *tree; in hfs_bnode_read_key() local
66 tree = node->tree; in hfs_bnode_read_key()
68 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
71 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
161 off = node->tree->node_size - 2; in hfs_bnode_dump()
168 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
171 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
188 struct hfs_btree *tree; in hfs_bnode_unlink() local
192 tree = node->tree; in hfs_bnode_unlink()
[all …]
|
| /kernel/linux/linux-6.6/fs/hfs/ |
| D | btree.c | 18 /* Get a reference to a B*Tree and do some initial checks */
21 struct hfs_btree *tree; in hfs_btree_open() local
27 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
28 if (!tree) in hfs_btree_open()
31 mutex_init(&tree->tree_lock); in hfs_btree_open()
32 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
34 tree->sb = sb; in hfs_btree_open()
35 tree->cnid = id; in hfs_btree_open()
36 tree->keycmp = keycmp; in hfs_btree_open()
38 tree->inode = iget_locked(sb, id); in hfs_btree_open()
[all …]
|
| D | brec.c | 16 static int hfs_btree_inc_height(struct hfs_btree *tree);
24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
45 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
50 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
56 if (retval > node->tree->max_key_len + 1) { in hfs_brec_keylen()
[all …]
|
| D | bnode.c | 30 if (pagenum >= node->tree->pages_per_bnode) in hfs_bnode_read()
60 struct hfs_btree *tree; in hfs_bnode_read_key() local
63 tree = node->tree; in hfs_bnode_read_key()
65 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
68 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
160 off = node->tree->node_size - 2; in hfs_bnode_dump()
167 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
170 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
187 struct hfs_btree *tree; in hfs_bnode_unlink() local
191 tree = node->tree; in hfs_bnode_unlink()
[all …]
|
| /kernel/linux/linux-6.6/fs/hfsplus/ |
| D | btree.c | 42 * Catalog B-tree Header
47 * Attributes B-tree Header
132 /* Get a reference to a B*Tree and do some initial checks */
135 struct hfs_btree *tree; in hfs_btree_open() local
142 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
143 if (!tree) in hfs_btree_open()
146 mutex_init(&tree->tree_lock); in hfs_btree_open()
147 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
148 tree->sb = sb; in hfs_btree_open()
149 tree->cnid = id; in hfs_btree_open()
[all …]
|
| D | brec.c | 25 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
40 !(node->tree->attributes & HFS_TREE_VARIDXKEYS) && in hfs_brec_keylen()
41 (node->tree->cnid != HFSPLUS_ATTR_CNID)) { in hfs_brec_keylen()
42 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
45 node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (recoff > node->tree->node_size - 2) { in hfs_brec_keylen()
54 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
65 struct hfs_btree *tree; in hfs_brec_insert() local
72 tree = fd->tree; in hfs_brec_insert()
74 if (!tree->root) in hfs_brec_insert()
[all …]
|
| D | bnode.c | 59 struct hfs_btree *tree; in hfs_bnode_read_key() local
62 tree = node->tree; in hfs_bnode_read_key()
64 tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_read_key()
65 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
68 key_len = tree->max_key_len + 2; in hfs_bnode_read_key()
309 off = node->tree->node_size - 2; in hfs_bnode_dump()
316 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
317 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
320 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
336 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
|
| /kernel/linux/linux-5.10/fs/hfsplus/ |
| D | btree.c | 42 * Catalog B-tree Header
47 * Attributes B-tree Header
132 /* Get a reference to a B*Tree and do some initial checks */
135 struct hfs_btree *tree; in hfs_btree_open() local
142 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
143 if (!tree) in hfs_btree_open()
146 mutex_init(&tree->tree_lock); in hfs_btree_open()
147 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
148 tree->sb = sb; in hfs_btree_open()
149 tree->cnid = id; in hfs_btree_open()
[all …]
|
| D | brec.c | 25 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
40 !(node->tree->attributes & HFS_TREE_VARIDXKEYS) && in hfs_brec_keylen()
41 (node->tree->cnid != HFSPLUS_ATTR_CNID)) { in hfs_brec_keylen()
42 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
45 node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (recoff > node->tree->node_size - 2) { in hfs_brec_keylen()
54 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
65 struct hfs_btree *tree; in hfs_brec_insert() local
72 tree = fd->tree; in hfs_brec_insert()
74 if (!tree->root) in hfs_brec_insert()
[all …]
|
| D | bnode.c | 61 struct hfs_btree *tree; in hfs_bnode_read_key() local
64 tree = node->tree; in hfs_bnode_read_key()
66 tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_read_key()
67 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
70 key_len = tree->max_key_len + 2; in hfs_bnode_read_key()
310 off = node->tree->node_size - 2; in hfs_bnode_dump()
317 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
318 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
321 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
337 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
|
| /kernel/linux/linux-5.10/fs/btrfs/ |
| D | extent-io-tree.h | 30 * Redefined bits above which are used only in the device allocation tree,
62 /* Who owns this io tree, should be one of IO_TREE_* */
89 struct extent_io_tree *tree, unsigned int owner,
91 void extent_io_tree_release(struct extent_io_tree *tree);
93 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
96 static inline int lock_extent(struct extent_io_tree *tree, u64 start, u64 end) in lock_extent() argument
98 return lock_extent_bits(tree, start, end, NULL); in lock_extent()
101 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end);
106 u64 count_range_bits(struct extent_io_tree *tree,
111 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
[all …]
|
| /kernel/linux/linux-6.6/fs/btrfs/ |
| D | extent-io-tree.c | 7 #include "extent-io-tree.h"
46 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", in btrfs_extent_state_leak_debug_check()
55 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
56 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
58 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
61 struct btrfs_inode *inode = tree->inode; in __btrfs_debug_check_extent_io_range()
84 * the tree lock and get the inode lock when setting delalloc. These two things
97 struct extent_io_tree *tree, unsigned int owner) in extent_io_tree_init() argument
99 tree->fs_info = fs_info; in extent_io_tree_init()
100 tree->state = RB_ROOT; in extent_io_tree_init()
[all …]
|
| D | extent-io-tree.h | 64 * Redefined bits above which are used only in the device allocation tree,
91 /* Inode associated with this tree, or NULL. */
94 /* Who owns this io tree, should be one of IO_TREE_* */
116 struct extent_io_tree *tree, unsigned int owner);
117 void extent_io_tree_release(struct extent_io_tree *tree);
119 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
122 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
128 u64 count_range_bits(struct extent_io_tree *tree,
134 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
136 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
[all …]
|
| /kernel/linux/linux-5.10/kernel/ |
| D | audit_tree.c | 61 * the same tree.
68 * tree.chunks anchors chunk.owners[].list hash_lock
69 * tree.rules anchors rule.rlist audit_filter_mutex
70 * chunk.trees anchors tree.same_root hash_lock
74 * tree is refcounted; one reference for "some rules on rules_list refer to
95 struct audit_tree *tree; in alloc_tree() local
97 tree = kmalloc(sizeof(struct audit_tree) + strlen(s) + 1, GFP_KERNEL); in alloc_tree()
98 if (tree) { in alloc_tree()
99 refcount_set(&tree->count, 1); in alloc_tree()
100 tree->goner = 0; in alloc_tree()
[all …]
|
| /kernel/linux/linux-6.6/kernel/ |
| D | audit_tree.c | 61 * the same tree.
68 * tree.chunks anchors chunk.owners[].list hash_lock
69 * tree.rules anchors rule.rlist audit_filter_mutex
70 * chunk.trees anchors tree.same_root hash_lock
74 * tree is refcounted; one reference for "some rules on rules_list refer to
95 struct audit_tree *tree; in alloc_tree() local
97 tree = kmalloc(struct_size(tree, pathname, strlen(s) + 1), GFP_KERNEL); in alloc_tree()
98 if (tree) { in alloc_tree()
99 refcount_set(&tree->count, 1); in alloc_tree()
100 tree->goner = 0; in alloc_tree()
[all …]
|
| /kernel/linux/linux-6.6/Documentation/core-api/ |
| D | maple_tree.rst | 5 Maple Tree
13 The Maple Tree is a B-Tree data type which is optimized for storing
14 non-overlapping ranges, including ranges of size 1. The tree was designed to
17 entry in a cache-efficient manner. The tree can also be put into an RCU-safe
22 The Maple Tree maintains a small memory footprint and was designed to use
24 use the normal API. An :ref:`maple-tree-advanced-api` exists for more complex
25 scenarios. The most important usage of the Maple Tree is the tracking of the
28 The Maple Tree can store values between ``0`` and ``ULONG_MAX``. The Maple
29 Tree reserves values with the bottom two bits set to '10' which are below 4096
34 :ref:`maple-tree-advanced-api`, but are blocked by the normal API.
[all …]
|
| /kernel/linux/linux-6.6/include/linux/ |
| D | maple_tree.h | 5 * Maple Tree - An RCU-safe adaptive tree for storing ranges
17 * Allocated nodes are mutable until they have been inserted into the tree,
19 * from the tree and an RCU grace period has passed.
25 * Nodes in the tree point to their parent unless bit 0 is set.
45 * is a pointer to the tree itself. No more bits are available in this pointer
49 * parent pointer is 256B aligned like all other tree nodes. When storing a 32
56 * type is done by examining the immutable tree flag for the MAPLE_ALLOC_RANGE
96 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
97 * indicate that the tree is specifying ranges, Pivots may appear in the
99 * specific position of a B-tree. Pivot values are inclusive of the slot with
[all …]
|
| D | rbtree.h | 43 /* Find logical next and previous nodes in a tree */
97 * rb_erase() may rebalance the tree, causing us to miss some nodes.
157 * rb_add_cached() - insert @node into the leftmost cached tree @tree
159 * @tree: leftmost cached tree to insert @node into
165 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, in rb_add_cached() argument
168 struct rb_node **link = &tree->rb_root.rb_node; in rb_add_cached()
183 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached()
189 * rb_add() - insert @node into @tree
191 * @tree: tree to insert @node into
195 rb_add(struct rb_node *node, struct rb_root *tree, in rb_add() argument
[all …]
|
| /kernel/linux/linux-5.10/Documentation/devicetree/ |
| D | of_unittest.rst | 4 Open Firmware Device Tree Unittest
13 is attached to the live tree dynamically, independent of the machine's
23 from the unflattened device tree data structure. This interface is used by
30 The Device Tree Source file (drivers/of/unittest-data/testcases.dts) contains
32 drivers/of/unittest.c. Currently, following Device Tree Source Include files
62 Un-flattened device tree structure:
64 Un-flattened device tree consists of connected device_node(s) in form of a tree
67 // following struct members are used to construct the tree
76 Figure 1, describes a generic structure of machine's un-flattened device tree
78 ``*parent``, that is used to traverse the tree in the reverse direction. So, at
[all …]
|