Home
last modified time | relevance | path

Searched full:tree (Results 1 – 25 of 6409) sorted by relevance

12345678910>>...257

/kernel/linux/linux-4.19/tools/testing/radix-tree/
Dtag_check.c8 #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, NULL, first, ~0UL, 10, tag, !tag); in __simple_checks()
29 ret = item_tag_get(tree, index, !tag); in __simple_checks()
[all …]
Dmultiorder.c2 * multiorder.c: Multi-order radix tree entry testing
16 #include <linux/radix-tree.h>
28 RADIX_TREE(tree, GFP_KERNEL); in __multiorder_tag_test()
37 err = item_insert_order(&tree, index, order); in __multiorder_tag_test()
46 err = __radix_tree_insert(&tree, i, order, in __multiorder_tag_test()
52 assert(!radix_tree_tag_get(&tree, i, 0)); in __multiorder_tag_test()
53 assert(!radix_tree_tag_get(&tree, i, 1)); in __multiorder_tag_test()
56 assert(radix_tree_tag_set(&tree, index, 0)); in __multiorder_tag_test()
59 assert(radix_tree_tag_get(&tree, i, 0)); in __multiorder_tag_test()
60 assert(!radix_tree_tag_get(&tree, i, 1)); in __multiorder_tag_test()
[all …]
Dmain.c10 #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/
Dtag_check.c8 #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 …]
Dmain.c10 #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-4.19/fs/hfs/
Dbtree.c18 /* 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 …]
Dbrec.c16 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 …]
Dbnode.c48 struct hfs_btree *tree; in hfs_bnode_read_key() local
51 tree = node->tree; in hfs_bnode_read_key()
53 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
56 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
146 off = node->tree->node_size - 2; in hfs_bnode_dump()
153 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
156 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
173 struct hfs_btree *tree; in hfs_bnode_unlink() local
177 tree = node->tree; in hfs_bnode_unlink()
179 tmp = hfs_bnode_find(tree, node->prev); in hfs_bnode_unlink()
[all …]
/kernel/linux/linux-5.10/fs/hfs/
Dbtree.c18 /* 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 …]
Dbrec.c16 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 …]
Dbnode.c31 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 …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 if (!tree) in hfs_find_init()
21 fd->tree = tree; in hfs_find_init()
23 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
27 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
29 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
30 switch (tree->cnid) { in hfs_find_init()
32 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); in hfs_find_init()
35 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); in hfs_find_init()
38 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); in hfs_find_init()
[all …]
/kernel/linux/linux-4.19/fs/hfsplus/
Dbtree.c42 * 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 …]
Dbrec.c25 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 …]
Dbnode.c61 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/hfsplus/
Dbtree.c42 * 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 …]
Dbrec.c25 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 …]
Dbnode.c61 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/
Dextent-io-tree.h30 * 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 …]
Dextent_map.c30 * extent_map_tree_init - initialize extent map tree
31 * @tree: tree to initialize
33 * Initialize the extent tree @tree. Should be called for each new inode
36 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
38 tree->map = RB_ROOT_CACHED; in extent_map_tree_init()
39 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
40 rwlock_init(&tree->lock); in extent_map_tree_init()
142 * search through the tree for an extent_map with a given offset. If
235 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) in try_merge_map() argument
241 * We can't modify an extent map that is in the tree and that is being in try_merge_map()
[all …]
/kernel/linux/linux-4.19/kernel/
Daudit_tree.c50 * the same tree.
57 * tree.chunks anchors chunk.owners[].list hash_lock
58 * tree.rules anchors rule.rlist audit_filter_mutex
59 * chunk.trees anchors tree.same_root hash_lock
63 * tree is refcounted; one reference for "some rules on rules_list refer to
79 struct audit_tree *tree; in alloc_tree() local
81 tree = kmalloc(sizeof(struct audit_tree) + strlen(s) + 1, GFP_KERNEL); in alloc_tree()
82 if (tree) { in alloc_tree()
83 refcount_set(&tree->count, 1); in alloc_tree()
84 tree->goner = 0; in alloc_tree()
[all …]
/kernel/linux/linux-5.10/kernel/
Daudit_tree.c61 * 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-4.19/Documentation/devicetree/
Dof_unittest.txt1 Open Firmware Device Tree Unittest
9 is attached to the live tree dynamically, independent of the machine's
19 from the unflattened device tree data structure. This interface is used by
25 The Device Tree Source file (drivers/of/unittest-data/testcases.dts) contains
27 drivers/of/unittest.c. Currently, following Device Tree Source Include files
55 Un-flattened device tree structure:
57 Un-flattened device tree consists of connected device_node(s) in form of a tree
60 // following struct members are used to construct the tree
69 Figure 1, describes a generic structure of machine's un-flattened device tree
71 *parent, that is used to traverse the tree in the reverse direction. So, at
[all …]
/kernel/linux/linux-5.10/Documentation/devicetree/
Dof_unittest.rst4 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 …]
/kernel/linux/linux-4.19/fs/btrfs/
Dextent_map.c29 * extent_map_tree_init - initialize extent map tree
30 * @tree: tree to initialize
32 * Initialize the extent tree @tree. Should be called for each new inode
35 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
37 tree->map = RB_ROOT; in extent_map_tree_init()
38 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
39 rwlock_init(&tree->lock); in extent_map_tree_init()
138 * search through the tree for an extent_map with a given offset. If
226 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) in try_merge_map() argument
232 * We can't modify an extent map that is in the tree and that is being in try_merge_map()
[all …]

12345678910>>...257