Home
last modified time | relevance | path

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

12345678910>>...168

/linux/tools/testing/radix-tree/
H A 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 …]
H A 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/fs/hfs/
H A 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 …]
H A 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 …]
H A Dbnode.c30 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()
154 off = node->tree->node_size - 2; in hfs_bnode_dump()
161 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
164 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
181 struct hfs_btree *tree; in hfs_bnode_unlink() local
185 tree = node->tree; in hfs_bnode_unlink()
[all …]
H A 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/fs/hfsplus/
H A 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 …]
H A 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 …]
H A Dbnode.c59 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()
303 off = node->tree->node_size - 2; in hfs_bnode_dump()
310 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
311 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
314 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
330 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
H A 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_nested(&tree->tree_lock, in hfs_find_init()
29 hfsplus_btree_lock_class(tree)); in hfs_find_init()
38 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
39 mutex_unlock(&fd->tree->tree_lock); in hfs_find_exit()
40 fd->tree = NULL; in hfs_find_exit()
[all …]
/linux/fs/btrfs/
H A Dextent-io-tree.c8 #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()
56 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
57 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
59 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
65 if (tree->owner != IO_TREE_INODE_IO) in __btrfs_debug_check_extent_io_range()
68 inode = extent_io_tree_to_inode_const(tree); in __btrfs_debug_check_extent_io_range()
85 * The only tree allowed to set the inode is IO_TREE_INODE_IO.
87 static bool is_inode_io_tree(const struct extent_io_tree *tree) in is_inode_io_tree() argument
89 return tree->owner == IO_TREE_INODE_IO; in is_inode_io_tree()
[all …]
H A Dextent-io-tree.h74 * Redefined bits above which are used only in the device allocation tree,
101 * The fs_info is needed for trace points, a tree attached to an inode
112 /* Who owns this io tree, should be one of IO_TREE_* */
133 struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree);
134 const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree);
135 const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree);
138 struct extent_io_tree *tree, unsigned int owner);
139 void extent_io_tree_release(struct extent_io_tree *tree);
140 int __lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
142 bool __try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
[all …]
/linux/kernel/
H A 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(struct_size(tree, pathname, strlen(s) + 1), GFP_KERNEL); in alloc_tree()
98 if (tree) { in alloc_tree()
99 refcount_set(&tree in alloc_tree()
111 get_tree(struct audit_tree * tree) get_tree() argument
116 put_tree(struct audit_tree * tree) put_tree() argument
123 audit_tree_path(struct audit_tree * tree) audit_tree_path() argument
261 audit_tree_match(struct audit_chunk * chunk,struct audit_tree * tree) audit_tree_match() argument
397 create_chunk(struct inode * inode,struct audit_tree * tree) create_chunk() argument
458 tag_chunk(struct inode * inode,struct audit_tree * tree) tag_chunk() argument
542 kill_rules(struct audit_context * context,struct audit_tree * tree) kill_rules() argument
609 trim_marked(struct audit_tree * tree) trim_marked() argument
649 struct audit_tree *tree; audit_remove_tree_rule() local
684 struct audit_tree *tree; audit_trim_trees() local
740 audit_put_tree(struct audit_tree * tree) audit_put_tree() argument
802 struct audit_tree *seed = rule->tree, *tree; audit_add_tree_rule() local
897 struct audit_tree *tree; audit_tag_tree() local
934 struct audit_tree *tree; audit_tag_tree() local
[all...]
/linux/drivers/gpu/drm/xe/
H A Dxe_range_fence.c24 struct xe_range_fence_tree *tree = rfence->tree; in xe_range_fence_signal_notify() local
26 llist_add(&rfence->link, &tree->list); in xe_range_fence_signal_notify()
29 static bool __xe_range_fence_tree_cleanup(struct xe_range_fence_tree *tree) in __xe_range_fence_tree_cleanup() argument
31 struct llist_node *node = llist_del_all(&tree->list); in __xe_range_fence_tree_cleanup()
35 xe_range_fence_tree_remove(rfence, &tree->root); in __xe_range_fence_tree_cleanup()
45 * @tree: range fence tree to insert intoi
54 int xe_range_fence_insert(struct xe_range_fence_tree *tree, in xe_range_fence_insert() argument
61 __xe_range_fence_tree_cleanup(tree); in xe_range_fence_insert()
69 rfence->tree = tree; in xe_range_fence_insert()
78 xe_range_fence_tree_insert(rfence, &tree->root); in xe_range_fence_insert()
[all …]
H A Dxe_range_fence.h24 /** @rb: RB tree node inserted into interval tree */
26 /** @start: start address of range fence is interval tree */
28 /** @last: last address (inclusive) of range fence is interval tree */
30 /** @__subtree_last: interval tree internal usage */
36 /** @tree: interval tree which range fence belongs to */
37 struct xe_range_fence_tree *tree; member
39 * @cb: callback when fence signals to remove range fence free from interval tree
48 /** struct xe_range_fence_tree - interval tree to store range fences */
50 /** @root: interval tree root */
59 xe_range_fence_tree_first(struct xe_range_fence_tree *tree, u64 start,
[all …]
/linux/Documentation/core-api/
H A Dmaple_tree.rst5 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 …]
/linux/include/linux/
H A Dmaple_tree.h5 * 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 * range type is done by examining the immutable tree flag for the
96 * In regular B-Tree terms, pivots are called keys. The term pivot is used to
97 * indicate that the tree i
427 struct maple_tree *tree; /* The tree we're operating in */ global() member
489 MA_TOPIARY(name,tree) global() argument
530 mas_init(struct ma_state * mas,struct maple_tree * tree,unsigned long addr) mas_init() argument
[all...]
H A Drbtree.h43 /* 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
195 rb_add(struct rb_node * node,struct rb_root * tree,bool (* less)(struct rb_node *,const struct rb_node *)) rb_add() argument
223 rb_find_add(struct rb_node * node,struct rb_root * tree,int (* cmp)(struct rb_node *,const struct rb_node *)) rb_find_add() argument
256 rb_find(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find() argument
284 rb_find_first(const void * key,const struct rb_root * tree,int (* cmp)(const void * key,const struct rb_node *)) rb_find_first() argument
330 rb_for_each(node,key,tree,cmp) global() argument
[all...]
/linux/tools/include/linux/
H A Drbtree.h52 /* Find logical next and previous nodes in a tree */
95 * rb_erase() may rebalance the tree, causing us to miss some nodes.
172 * rb_add_cached() - insert @node into the leftmost cached tree @tree
174 * @tree: leftmost cached tree to insert @node into
178 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, in rb_add_cached() argument
181 struct rb_node **link = &tree->rb_root.rb_node; in rb_add_cached()
196 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached()
200 * rb_add() - insert @node into @tree
202 * @tree: tree to insert @node into
206 rb_add(struct rb_node *node, struct rb_root *tree, in rb_add() argument
[all …]
/linux/rust/kernel/
H A Drbtree.rs18 /// A red-black tree with owned nodes.
24 /// In the example below we do several operations on a tree. We note that insertions may fail if
30 /// // Create a new tree.
31 /// let mut tree = RBTree::new();
34 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
35 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
36 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
40 /// assert_eq!(tree.get(&10).unwrap(), &100);
41 /// assert_eq!(tree.get(&20).unwrap(), &200);
42 /// assert_eq!(tree.get(&30).unwrap(), &300);
[all …]
/linux/Documentation/devicetree/
H A Dof_unittest.rst13 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
51 The Device Tree Source file (drivers/of/unittest-data/testcases.dts) contains
53 drivers/of/unittest.c. Currently, following Device Tree Source Include files
83 Un-flattened device tree structure:
85 Un-flattened device tree consists of connected device_node(s) in form of a tree
88 // following struct members are used to construct the tree
97 Figure 1, describes a generic structure of machine's un-flattened device tree
99 ``*parent``, that is used to traverse the tree in the reverse direction. So, at
126 Figure 1: Generic structure of un-flattened device tree
[all …]
/linux/sound/hda/
H A 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/lib/zlib_deflate/
H A Ddeftree.c13 * Each code tree is stored in a compressed form which is itself
84 /* The static literal tree. Since the bit lengths are imposed, there is no
86 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init
91 /* The static distance tree. (Actually a trivial tree since all codes use
111 const ct_data *static_tree; /* static tree or NULL */
114 int elems; /* max number of elements in the tree */
133 static void pqdownheap (deflate_state *s, ct_data *tree, int k);
135 static void gen_codes (ct_data *tree, int max_code, ush *bl_count);
137 static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
138 static void send_tree (deflate_state *s, ct_data *tree, int max_code);
[all …]
/linux/net/sched/
H A 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()
290 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
293 * @nla: ematch tree configuration TLV
294 * @tree: destination ematch tree variable to store the resulting
295 * ematch tree.
298 * ematch tree in @tree. The resulting tree must later be copied into
300 * provide the ematch tree variable of the private classifier data directly,
306 struct tcf_ematch_tree *tree) in tcf_em_tree_validate() argument
314 memset(tree, 0, sizeof(*tree)); in tcf_em_tree_validate()
[all …]
/linux/scripts/dtc/libfdt/
H A Dfdt_overlay.c3 * libfdt - Flat Device Tree manipulation
16 * @fdto: pointer to the device tree overlay blob
89 * @fdt: Base device tree blob
90 * @node: Device tree overlay blob
124 * @fdto: Device tree overlay blob
131 * phandles to not conflict with the overlays of the base device tree.
162 * @fdto: Device tree overlay blob
168 * phandles to not conflict with the overlays of the base device tree.
184 * @fdto: Device tree overlay blob
190 * pointing to a node within the device tree overlay by adding a
[all …]

12345678910>>...168