| /linux/tools/testing/radix-tree/ |
| H A 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 …]
|
| H A 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 …]
|
| /linux/fs/btrfs/ |
| H A D | extent-io-tree.c | 8 #include "extent-io-tree.h"
47 "state leak: start %llu end %llu state %u in tree %d refs %d", in btrfs_extent_state_leak_debug_check()
57 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
58 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
60 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
63 const struct btrfs_inode *inode = tree->inode; in __btrfs_debug_check_extent_io_range()
66 if (tree->owner != IO_TREE_INODE_IO) in __btrfs_debug_check_extent_io_range()
84 const struct btrfs_inode *btrfs_extent_io_tree_to_inode(const struct extent_io_tree *tree) in btrfs_extent_io_tree_to_inode() argument
86 if (tree->owner == IO_TREE_INODE_IO) in btrfs_extent_io_tree_to_inode()
87 return tree->inode; in btrfs_extent_io_tree_to_inode()
[all …]
|
| H A D | extent-io-tree.h | 79 * Redefined bits above which are used only in the device allocation tree,
106 * The fs_info is needed for trace points, a tree attached to an inode
117 /* Who owns this io tree, should be one of IO_TREE_* */
138 const struct btrfs_inode *btrfs_extent_io_tree_to_inode(const struct extent_io_tree *tree);
139 const struct btrfs_fs_info *btrfs_extent_io_tree_to_fs_info(const struct extent_io_tree *tree);
142 struct extent_io_tree *tree, unsigned int owner);
143 void btrfs_extent_io_tree_release(struct extent_io_tree *tree);
144 int btrfs_lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
146 bool btrfs_try_lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
149 static inline int btrfs_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, in btrfs_lock_extent() argument
[all …]
|
| H A D | extent_map.c | 31 * Initialize the extent tree @tree. Should be called for each new inode or
34 void btrfs_extent_map_tree_init(struct extent_map_tree *tree) in btrfs_extent_map_tree_init() argument
36 tree->root = RB_ROOT; in btrfs_extent_map_tree_init()
37 INIT_LIST_HEAD(&tree->modified_extents); in btrfs_extent_map_tree_init()
38 rwlock_init(&tree->lock); in btrfs_extent_map_tree_init()
136 * Search through the tree for an extent_map with a given offset. If it can't
259 * removed from the tree and likely freed. Note that @merged is one of @prev/@next
349 * We can't modify an extent map that is in the tree and that is being in try_merge_map()
352 * the tree and 1 for this task (which is unpinning the extent map or in try_merge_map()
409 * -ENOENT when the extent is not found in the tree
[all …]
|
| /linux/kernel/ |
| H A 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
99 tree = kmalloc(struct_size(tree, pathname, sz), GFP_KERNEL); in alloc_tree()
100 if (tree) { in alloc_tree()
101 refcount_set(&tree->count, 1); in alloc_tree()
102 tree->goner = 0; in alloc_tree()
[all …]
|
| /linux/drivers/gpu/drm/xe/ |
| H A D | xe_range_fence.c | 24 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 …]
|
| /linux/Documentation/core-api/ |
| H A 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 …]
|
| /linux/include/linux/ |
| H A D | rbtree.h | 43 /* Find logical next and previous nodes in a tree */
48 * This function returns the first node (in sort order) of the tree.
63 * This function returns the last node (in sort order) of the tree.
125 * rb_erase() may rebalance the tree, causing us to miss some nodes.
185 * rb_add_cached() - insert @node into the leftmost cached tree @tree
187 * @tree: leftmost cached tree to insert @node into
193 rb_add_cached(struct rb_node *node, struct rb_root_cached *tree, in rb_add_cached() argument
196 struct rb_node **link = &tree->rb_root.rb_node; in rb_add_cached()
211 rb_insert_color_cached(node, tree, leftmost); in rb_add_cached()
217 * rb_add() - insert @node into @tree
[all …]
|
| H A 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 * 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 is specifying ranges, Pivots may appear in the
99 * specific position of a B-tree. Pivot values are inclusive of the slot with
[all …]
|
| H A D | radix-tree.h | 44 * The internal entry may be a pointer to the next level in the tree, a
46 * to another location in the tree and the lookup should be restarted. While
48 * the tree for this index (no matter what level of the tree it is found at).
49 * This means that storing a NULL entry in the tree is the same as deleting
50 * the entry from the tree.
61 /*** radix-tree API starts here ***/
92 * struct radix_tree_iter - radix tree iterator state
99 * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
100 * subinterval of slots contained within one radix tree leaf node. It is
102 * which holds the chunk's position in the tree and its size. For tagged
[all …]
|
| /linux/rust/kernel/ |
| H A D | maple_tree.rs | 22 /// A maple tree optimized for storing non-overlapping ranges.
26 /// Each range in the maple tree owns an instance of `T`.
31 tree: Opaque<bindings::maple_tree>, field
35 /// A maple tree with `MT_FLAGS_ALLOC_RANGE` set.
42 tree: MapleTree<T>, field
51 &self.tree in deref()
77 /// Create a new maple tree.
79 /// The tree will use the regular implementation with a higher branching factor, rather than
80 /// the allocation tree.
84 // SAFETY: This initializes a maple tree into a pinned slot. The maple tree will be in new()
[all …]
|
| H A D | rbtree.rs | 17 /// A red-black tree with owned nodes.
23 /// In the example below we do several operations on a tree. We note that insertions may fail if
29 /// // Create a new tree.
30 /// let mut tree = RBTree::new();
33 /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?;
34 /// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?;
35 /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?;
39 /// assert_eq!(tree.get(&10), Some(&100));
40 /// assert_eq!(tree.get(&20), Some(&200));
41 /// assert_eq!(tree.get(&30), Some(&300));
[all …]
|
| /linux/tools/include/linux/ |
| H A D | rbtree.h | 52 /* 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/sound/hda/core/ |
| H A D | sysfs.c | 79 * 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 D | deftree.c | 13 * 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 D | ematch.c | 162 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/gcc-plugins/ |
| H A D | gcc-common.h | 14 #include "tree.h"
16 #include "tree-inline.h"
46 #include "tree-pretty-print.h"
49 #include "tree-cfgcleanup.h"
50 #include "tree-ssa-operands.h"
51 #include "tree-into-ssa.h"
54 #include "tree-dump.h"
55 #include "tree-pass.h"
69 #include "tree-ssa-alias.h"
70 #include "tree-ssa.h"
[all …]
|
| H A D | randomize_layout_plugin.c | 54 static tree handle_randomize_layout_attr(tree *node, tree name, tree args, int flags, bool *no_add_… in handle_randomize_layout_attr()
56 tree type; in handle_randomize_layout_attr()
100 static tree handle_randomize_considered_attr(tree *node, tree name, tree args, int flags, bool *no_… in handle_randomize_considered_attr()
110 static tree handle_randomize_performed_attr(tree *node, tree name, tree args, int flags, bool *no_a… in handle_randomize_performed_attr()
150 tree tree_start;
155 static void partition_struct(tree *fields, unsigned long length, struct partition_group *size_group… in partition_struct()
191 static void performance_shuffle(tree *newtree, unsigned long length, ranctx *prng_state) in performance_shuffle()
211 tree tmp; in performance_shuffle()
228 static void full_shuffle(tree *newtree, unsigned long length, ranctx *prng_state) in full_shuffle()
233 tree tmp; in full_shuffle()
[all …]
|
| /linux/drivers/of/ |
| H A D | Kconfig | 12 bool "Device Tree and Open Firmware support"
14 This option enables the device tree infrastructure.
22 bool "Device Tree runtime unit tests"
27 This option builds in test cases for the device tree infrastructure
50 This option builds KUnit unit tests for device tree infrastructure.
55 bool "Build all Device Tree Blobs"
59 This option builds all possible Device Tree Blobs (DTBs) for the
87 On some platforms, the device tree can be manipulated at runtime.
89 can enable it manually to improve device tree unit test coverage.
106 bool "Device Tree overlays"
[all …]
|
| /linux/include/linux/ns/ |
| H A D | nstree_types.h | 10 * struct ns_tree_root - Root of a namespace tree
11 * @ns_rb: Red-black tree root for efficient lookups
14 * Each namespace tree maintains both an rbtree (for O(log n) lookups)
24 * struct ns_tree_node - Node in a namespace tree
25 * @ns_node: Red-black tree node
28 * Represents a namespace's position in a tree. Each namespace has
29 * multiple tree nodes for different trees (unified, per-type, owner).
37 * struct ns_tree - Namespace tree nodes and active reference count
40 * @ns_unified_node: Node in the global namespace tree
41 * @ns_tree_node: Node in the per-type namespace tree
[all …]
|
| /linux/lib/ |
| H A D | test_maple_tree.c | 3 * test_maple_tree.c: Test the maple tree API
7 * Any tests that only require the interface of the tree.
557 MT_BUG_ON(mas.tree, entry == NULL); in check_find()
1021 /* Create tree of 1-100 */ in check_ranges()
1029 /* Create tree of 1-200 */ in check_ranges()
1042 /* Create tree of 1-400 */ in check_ranges()
1070 /* Overwrite multiple levels at the end of the tree (slot 7) */ in check_ranges()
1134 * 8. Overwrite the whole tree in check_ranges()
1135 * 9. Try to overwrite the zero entry of an alloc tree. in check_ranges()
1287 /* Cause a 3 child split all the way up the tree. */ in check_ranges()
[all …]
|
| /linux/tools/perf/python/ |
| H A D | ilist.py | 18 from textual.widgets import Button, Footer, Header, Input, Label, Sparkline, Static, Tree
19 from textual.widgets.tree import TreeNode
27 """Abstraction for the data of value in the tree."""
52 """A metric in the tree."""
90 """A PMU and event within the tree."""
244 """Expand select a node in the tree."""
250 node.tree.select_node(node)
251 node.tree.scroll_to_node(node)
258 tree: Tree[TreeValue] = self.query_one("#root", Tree)
260 tree.action_cursor_up()
[all …]
|
| /linux/fs/unicode/ |
| H A D | mkutf8data.c | 111 * A compact binary tree, used to decode UTF-8 characters.
114 * bytes for an offset into the tree. The first byte contains the
189 struct tree;
190 static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *,
192 static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *);
345 struct tree { struct
350 struct tree *next; argument
355 int *(*leaf_index)(struct tree *, void *); argument
378 * Example lookup function for a tree. argument
380 static void *lookup(struct tree *tree, const char *key) in lookup() argument
[all …]
|
| /linux/arch/arm/mach-spear/ |
| H A D | Kconfig | 30 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
|