Home
last modified time | relevance | path

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

12345678910>>...159

/Linux-v5.4/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 …]
/Linux-v5.4/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 …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 fd->tree = tree; in hfs_find_init()
21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
27 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
28 mutex_lock(&tree->tree_lock); in hfs_find_init()
37 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
38 mutex_unlock(&fd->tree->tree_lock); in hfs_find_exit()
39 fd->tree = NULL; in hfs_find_exit()
63 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); in __hfs_brec_find()
[all …]
/Linux-v5.4/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 …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 fd->tree = tree; in hfs_find_init()
21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
27 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
28 switch (tree->cnid) { in hfs_find_init()
30 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); in hfs_find_init()
33 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); in hfs_find_init()
36 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); in hfs_find_init()
49 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
[all …]
/Linux-v5.4/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 …]
/Linux-v5.4/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 …]
/Linux-v5.4/fs/btrfs/
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
231 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) in try_merge_map() argument
250 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
[all …]
Dextent_io.h31 * Redefined bits above which are used only in the device allocation tree,
132 /* Who owns this io tree, should be one of IO_TREE_* */
173 /* >= 0 if eb belongs to a log tree, -1 otherwise */
263 struct extent_io_tree *tree, unsigned int owner,
265 void extent_io_tree_release(struct extent_io_tree *tree);
268 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
271 static inline int lock_extent(struct extent_io_tree *tree, u64 start, u64 end) in lock_extent() argument
273 return lock_extent_bits(tree, start, end, NULL); in lock_extent()
276 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end);
277 int extent_read_full_page(struct extent_io_tree *tree, struct page *page,
[all …]
Dordered-data.c29 * in the tree
60 "Inconsistency in ordered tree at offset %llu", offset); in ordered_data_tree_panic()
64 * look for a given offset in the tree, and if it can't be found return the
141 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree, in tree_search() argument
144 struct rb_root *root = &tree->tree; in tree_search()
149 if (tree->last) { in tree_search()
150 entry = rb_entry(tree->last, struct btrfs_ordered_extent, in tree_search()
153 return tree->last; in tree_search()
159 tree->last = ret; in tree_search()
163 /* allocate and add a new ordered_extent into the per-inode tree.
[all …]
Dextent_io.c70 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", in btrfs_leak_debug_check()
87 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
88 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
90 struct extent_io_tree *tree, u64 start, u64 end) in __btrfs_debug_check_extent_io_range() argument
92 struct inode *inode = tree->private_data; in __btrfs_debug_check_extent_io_range()
120 struct extent_io_tree *tree; member
152 struct extent_io_tree *tree = bio->bi_private; in submit_one_bio() local
156 if (tree->ops) in submit_one_bio()
157 ret = tree->ops->submit_bio_hook(tree->private_data, bio, in submit_one_bio()
251 struct extent_io_tree *tree, unsigned int owner, in extent_io_tree_init() argument
[all …]
/Linux-v5.4/sound/hda/
Dhdac_sysfs.c79 * Widget tree sysfs
81 * This is a tree showing the attributes of each widget. It appears like
322 struct hdac_widget_tree *tree = codec->widgets; in widget_tree_free() local
325 if (!tree) in widget_tree_free()
327 free_widget_node(tree->afg, &widget_afg_group); in widget_tree_free()
328 if (tree->nodes) { in widget_tree_free()
329 for (p = tree->nodes; *p; p++) in widget_tree_free()
331 kfree(tree->nodes); in widget_tree_free()
333 kobject_put(tree->root); in widget_tree_free()
334 kfree(tree); in widget_tree_free()
[all …]
/Linux-v5.4/lib/zlib_deflate/
Ddeftree.c13 * Each code tree is stored in a compressed form which is itself
89 /* The static literal tree. Since the bit lengths are imposed, there is no
91 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init
96 /* The static distance tree. (Actually a trivial tree since all codes use
116 const ct_data *static_tree; /* static tree or NULL */
119 int elems; /* max number of elements in the tree */
138 static void pqdownheap (deflate_state *s, ct_data *tree, int k);
140 static void gen_codes (ct_data *tree, int max_code, ush *bl_count);
142 static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
143 static void send_tree (deflate_state *s, ct_data *tree, int max_code);
[all …]
/Linux-v5.4/scripts/dtc/libfdt/
Dfdt_overlay.c3 * libfdt - Flat Device Tree manipulation
16 * @fdto: pointer to the device tree overlay blob
45 * @fdt: Base device tree blob
46 * @fdto: Device tree overlay blob
51 * device tree of a fragment, no matter how the actual targeting is
55 * the targeted node offset in the base device tree
104 * @fdt: Base device tree blob
105 * @node: Device tree overlay blob
143 * @fdto: Device tree overlay blob
150 * phandles to not conflict with the overlays of the base device tree.
[all …]
/Linux-v5.4/net/sched/
Dematch.c162 static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree, in tcf_em_get_match() argument
165 return &tree->matches[index]; in tcf_em_get_match()
285 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
288 * @nla: ematch tree configuration TLV
289 * @tree: destination ematch tree variable to store the resulting
290 * ematch tree.
293 * ematch tree in @tree. The resulting tree must later be copied into
295 * provide the ematch tree variable of the private classifier data directly,
301 struct tcf_ematch_tree *tree) in tcf_em_tree_validate() argument
309 memset(tree, 0, sizeof(*tree)); in tcf_em_tree_validate()
[all …]
/Linux-v5.4/arch/arm/mach-spear/
DKconfig30 bool "SPEAr1310 Machine support with Device Tree"
34 Supports ST SPEAr1310 machine configured via the device-tree
37 bool "SPEAr1340 Machine support with Device Tree"
41 Supports ST SPEAr1340 machine configured via the device-tree
57 bool "SPEAr300 Machine support with Device Tree"
60 Supports ST SPEAr300 machine configured via the device-tree
63 bool "SPEAr310 Machine support with Device Tree"
66 Supports ST SPEAr310 machine configured via the device-tree
69 bool "SPEAr320 Machine support with Device Tree"
72 Supports ST SPEAr320 machine configured via the device-tree
[all …]
/Linux-v5.4/scripts/tracing/
Ddraw_functrace.py9 The resulted trace is processed into a tree to produce a more human
10 view of the call stack by drawing textual but hierarchical tree of
28 """ This class provides a tree representation of the functions
46 into the tree at the appropriate place.
59 tree = self
60 while tree != CallTree.ROOT and tree._func != func:
61 tree = tree._parent
62 if tree == CallTree.ROOT:
65 return tree
114 tree = CallTree.ROOT
[all …]
/Linux-v5.4/include/linux/
Dradix-tree.h32 * The internal entry may be a pointer to the next level in the tree, a
34 * to another location in the tree and the lookup should be restarted. While
36 * the tree for this index (no matter what level of the tree it is found at).
37 * This means that storing a NULL entry in the tree is the same as deleting
38 * the entry from the tree.
49 /*** radix-tree API starts here ***/
80 * struct radix_tree_iter - radix tree iterator state
87 * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
88 * subinterval of slots contained within one radix tree leaf node. It is
90 * which holds the chunk's position in the tree and its size. For tagged
[all …]
/Linux-v5.4/drivers/of/
DKconfig6 bool "Device Tree and Open Firmware support"
8 This option enables the device tree infrastructure.
16 bool "Device Tree runtime unit tests"
22 This option builds in test cases for the device tree infrastructure
29 bool "Build all Device Tree Blobs"
33 This option builds all possible Device Tree Blobs (DTBs) for the
61 On some platforms, the device tree can be manipulated at runtime.
63 can enable it manually to improve device tree unit test coverage.
93 bool "Device Tree overlays"
99 device tree with dynamically loaded data.
[all …]
/Linux-v5.4/scripts/dtc/
Dfstree.c16 struct node *tree; in read_fstree() local
22 tree = build_node(NULL, NULL, NULL); in read_fstree()
50 add_property(tree, prop); in read_fstree()
58 add_child(tree, newchild); in read_fstree()
65 return tree; in read_fstree()
70 struct node *tree; in dt_from_fs() local
72 tree = read_fstree(dirname); in dt_from_fs()
73 tree = name_node(tree, ""); in dt_from_fs()
75 return build_dt_info(DTSF_V1, NULL, tree, guess_boot_cpuid(tree)); in dt_from_fs()

12345678910>>...159