Home
last modified time | relevance | path

Searched +full:in +full:- +full:tree (Results 1 – 25 of 1049) sorted by relevance

12345678910>>...42

/linux-6.14.4/include/linux/
Dmaple_tree.h1 /* SPDX-License-Identifier: GPL-2.0+ */
5 * Maple Tree - An RCU-safe adaptive tree for storing ranges
6 * Copyright (c) 2018-2022 Oracle
17 * Allocated nodes are mutable until they have been inserted into the tree,
19 * from the tree and an RCU grace period has passed.
21 * Removed nodes have their ->parent set to point to themselves. RCU readers
22 * check ->parent before relying on the value that they loaded from the
25 * Nodes in the tree point to their parent unless bit 0 is set.
29 #define MAPLE_NODE_SLOTS 31 /* 256 bytes including ->parent */
32 #define MAPLE_ALLOC_SLOTS (MAPLE_NODE_SLOTS - 1)
[all …]
Drbtree.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
11 I know it's not the cleaner way, but in C (not in C++) to get
14 See Documentation/core-api/rbtree.rst for documentation and samples.
26 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
30 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
32 /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
34 ((node)->__rb_parent_color == (unsigned long)(node))
36 ((node)->__rb_parent_color = (unsigned long)(node))
43 /* Find logical next and previous nodes in a tree */
49 /* Postorder iteration - always visit the parent after its children */
[all …]
Dradix-tree.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
31 /* nodes->parent points to next preallocated node */
37 * The bottom two bits of the slot determine how the remaining bits in the
40 * 00 - data pointer
41 * 10 - internal entry
42 * x1 - value entry
44 * The internal entry may be a pointer to the next level in the tree, a
45 * sibling entry, or an indicator that the entry in this slot has been moved
46 * to another location in the tree and the lookup should be restarted. While
47 * NULL fits the 'data pointer' pattern, it means that there is no entry in
[all …]
/linux-6.14.4/fs/btrfs/
Dextent-io-tree.c1 // SPDX-License-Identifier: GPL-2.0
8 #include "extent-io-tree.h"
15 return !RB_EMPTY_NODE(&state->rb_node); in extent_state_in_tree()
27 list_add(&state->leak_list, &states); in btrfs_leak_debug_add_state()
36 list_del(&state->leak_list); in btrfs_leak_debug_del_state()
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()
47 state->start, state->end, state->state, in btrfs_extent_state_leak_debug_check()
49 refcount_read(&state->refs)); in btrfs_extent_state_leak_debug_check()
50 list_del(&state->leak_list); in btrfs_extent_state_leak_debug_check()
56 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
[all …]
Dextent_map.c1 // SPDX-License-Identifier: GPL-2.0
11 #include "disk-io.h"
21 return -ENOMEM; in extent_map_init()
31 * Initialize the extent tree @tree. Should be called for each new inode or
34 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
36 tree->root = RB_ROOT; in extent_map_tree_init()
37 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
38 rwlock_init(&tree->lock); in extent_map_tree_init()
51 RB_CLEAR_NODE(&em->rb_node); in alloc_extent_map()
52 refcount_set(&em->refs, 1); in alloc_extent_map()
[all …]
/linux-6.14.4/Documentation/core-api/
Dmaple_tree.rst1 .. SPDX-License-Identifier: GPL-2.0+
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
[all …]
/linux-6.14.4/Documentation/devicetree/
Dof_unittest.rst1 .. SPDX-License-Identifier: GPL-2.0
13 is attached to the live tree dynamically, independent of the machine's
18 (1) Documentation/devicetree/usage-model.rst
23 from the unflattened device tree data structure. This interface is used by
24 most of the device drivers in various use cases.
41 The EXPECT messages result in very noisy console messages that are difficult
45 from 'scripts/dtc/of_unittest_expect --help'.
48 3. Test-data
51 The Device Tree Source file (drivers/of/unittest-data/testcases.dts) contains
52 the test data required for executing the unit tests automated in
[all …]
Dusage-model.rst1 .. SPDX-License-Identifier: GPL-2.0
7 The Linux usage model for device tree data
11 This article describes how Linux uses the device tree. An overview of
12 the device tree data format can be found on the device tree usage page
17 The "Open Firmware Device Tree", or simply Devicetree (DT), is a data
23 Structurally, the DT is a tree, or acyclic graph with named nodes, and
26 links from one node to another outside of the natural tree structure.
29 is defined for how data should appear in the tree to describe typical
41 already being enumerated in existing systems.
44 ----------
[all …]
/linux-6.14.4/rust/kernel/
Drbtree.rs1 // SPDX-License-Identifier: GPL-2.0
3 //! Red-black trees.
7 //! Reference: <https://docs.kernel.org/core-api/rbtree.html>
17 /// A red-black tree with owned nodes.
19 /// It is backed by the kernel C red-black trees.
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)?;
[all …]
/linux-6.14.4/scripts/dtc/libfdt/
Dlibfdt.h1 /* SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause) */
5 * libfdt - Flat Device Tree manipulation
28 * tree, but its buffer did not have sufficient space to
29 * contain the expanded tree. Use fdt_open_into() to move the
30 * device tree to a buffer with more space. */
35 * offset which is out-of-bounds, or which points to an
44 * length, or the phandle value was either 0 or -1, which are
48 * tree created by the sequential-write functions, which is
51 /* Error codes: codes for bad device tree blobs */
53 /* FDT_ERR_TRUNCATED: FDT or a sub-block is improperly
[all …]
Dfdt_overlay.c1 // SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause)
3 * libfdt - Flat Device Tree manipulation
15 * overlay_get_target_phandle - retrieves the target phandle of a fragment
16 * @fdto: pointer to the device tree overlay blob
17 * @fragment: node offset of the fragment in the overlay
21 * property) instead of a path (target-path property).
26 * -1, if the phandle was malformed
37 if ((len != sizeof(*val)) || (fdt32_to_cpu(*val) == (uint32_t)-1)) in overlay_get_target_phandle()
38 return (uint32_t)-1; in overlay_get_target_phandle()
52 if (phandle == (uint32_t)-1) in fdt_overlay_target_offset()
[all …]
Dlibfdt_internal.h1 /* SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause) */
5 * libfdt - Flat Device Tree manipulation
10 #define FDT_ALIGN(x, a) (((x) + (a) - 1) & ~((a) - 1))
50 * Internal helpers to access tructural elements of the device tree
54 * where unaligned memory reads will be handled in a graceful manner.
83 * You should have another method of validating the device tree, such as a
91 * This does essentially no checks. Only the latest device-tree
92 * version is correctly handled. Inconsistencies or errors in the device
93 * tree may cause undefined behaviour or crashes. Invalid parameters
96 * If an error occurs when modifying the tree it may leave the tree in
[all …]
/linux-6.14.4/Documentation/arch/powerpc/
Dbootwrapper.rst12 The boot wrapper can be found in the arch/powerpc/boot/ directory. The
13 Makefile in that directory has targets for all the available image types.
17 others. U-Boot is typically found on embedded PowerPC hardware, but there
21 The boot wrapper is built from the makefile in arch/powerpc/boot/Makefile and
23 image. The details of the build system is discussed in the next section.
28 U-Boot (for versions that don't understand the device
29 tree). This image embeds a device tree blob inside
30 the image. The boot wrapper, kernel and device tree
31 are all embedded inside the U-Boot uImage file format
34 tree before jumping into the kernel.
[all …]
/linux-6.14.4/tools/include/linux/
Drbtree.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
11 I know it's not the cleaner way, but in C (not in C++) to get
14 See Documentation/core-api/rbtree.rst for documentation and samples.
34 #define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
39 #define RB_EMPTY_ROOT(root) (READ_ONCE((root)->rb_node) == NULL)
41 /* 'empty' nodes are nodes that are known not to be inserted in an rbtree */
43 ((node)->__rb_parent_color == (unsigned long)(node))
45 ((node)->__rb_parent_color = (unsigned long)(node))
52 /* Find logical next and previous nodes in a tree */
58 /* Postorder iteration - always visit the parent after its children */
[all …]
/linux-6.14.4/lib/zlib_deflate/
Ddeftree.c2 /* trees.c -- output deflated data using Huffman coding
3 * Copyright (C) 1995-1996 Jean-loup Gailly
4 * For conditions of distribution and use, see copyright notice in zlib.h
13 * Each code tree is stored in a compressed form which is itself
14 * a Huffman encoding of the lengths of all the code strings (in
16 * reconstructed from the lengths in the inflate process, as described
17 * in the deflate specification.
22 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
25 * Data Compression: Methods and Theory, pp. 49-50.
26 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
[all …]
/linux-6.14.4/drivers/gpu/drm/amd/display/dc/mpc/dcn10/
Ddcn10_mpc.c2 * Copyright 2012-15 Advanced Micro Devices, Inc.
6 * to deal in the Software without restriction, including without limitation
11 * The above copyright notice and this permission notice shall be included in
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
30 mpc10->mpc_regs->reg
33 mpc10->base.ctx
37 mpc10->mpc_shift->field_name, mpc10->mpc_mask->field_name
[all …]
/linux-6.14.4/Documentation/filesystems/
Dfsverity.rst1 .. SPDX-License-Identifier: GPL-2.0
6 fs-verity: read-only file-based authenticity protection
12 fs-verity (``fs/verity/``) is a support layer that filesystems can
14 of read-only files. Currently, it is supported by the ext4, f2fs, and
15 btrfs filesystems. Like fscrypt, not too much filesystem-specific
16 code is needed to support fs-verity.
18 fs-verity is similar to `dm-verity
19 <https://www.kernel.org/doc/Documentation/admin-guide/device-mapper/verity.rst>`_
21 filesystems supporting fs-verity, userspace can execute an ioctl that
22 causes the filesystem to build a Merkle tree for the file and persist
[all …]
/linux-6.14.4/block/
Dbfq-wf2q.c1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * Hierarchical Budget Worst-case Fair Weighted Fair Queueing
4 * (B-WF2Q+): hierarchical scheduling algorithm by which the BFQ I/O
9 #include "bfq-iosched.h"
12 * bfq_gt - compare two timestamps.
20 return (s64)(a - b) > 0; in bfq_gt()
23 static struct bfq_entity *bfq_root_active_entity(struct rb_root *tree) in bfq_root_active_entity() argument
25 struct rb_node *node = tree->rb_node; in bfq_root_active_entity()
34 return bfqq ? bfqq->ioprio_class - 1 : in bfq_class_idx()
35 BFQ_DEFAULT_GRP_CLASS - 1; in bfq_class_idx()
[all …]
/linux-6.14.4/drivers/gpu/drm/amd/display/dc/inc/hw/
Dmpc.h2 * Copyright 2012-15 Advanced Micro Devices, Inc.
6 * to deal in the Software without restriction, including without limitation
11 * The above copyright notice and this permission notice shall be included in
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 * OTHER DEALINGS IN THE SOFTWARE.
29 * Multiple Pipe/Plane Combiner (MPC) is a component in the hardware pipeline
30 * that performs blending of multiple planes, using global and per-pixel alpha.
31 * It also performs post-blending color correction operations according to the
[all …]
/linux-6.14.4/Documentation/filesystems/ext4/
Difork.rst1 .. SPDX-License-Identifier: GPL-2.0
4 ------------------------------
7 storage in ``inode.i_block`` can be used in different ways. In general,
14 The target of a symbolic link will be stored in this field if the target
21 In ext2/3, file block numbers were mapped to logical block numbers by
22 means of an (up to) three level 1-1 block map. To find the logical block
43 Extent Tree
46 In ext4, the file to logical block map has been replaced with an extent
47 tree. Under the old scheme, allocating a contiguous run of 1,000 blocks
51 very large files with a single extent, at a considerable reduction in
[all …]
/linux-6.14.4/lib/
Dradix-tree.c1 // SPDX-License-Identifier: GPL-2.0-or-later
24 #include <linux/radix-tree.h>
30 #include "radix-tree.h"
33 * Radix tree node cache.
38 * The radix tree is variable-height, so an insert operation not only has
43 * The worst case is a zero height tree with just a single item at index 0,
48 #define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
51 * The IDR does not have to be as high as the radix tree since it uses
54 #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
57 #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
[all …]
/linux-6.14.4/net/sched/
Dematch.c1 // SPDX-License-Identifier: GPL-2.0-or-later
18 * causing the current position in the sequence to be pushed onto a stack
20 * in the special ematch. Matching continues in the new sequence until a
26 * ------->-PUSH-------
27 * -->-- / -->-- \ -->--
29 * +-------+-------+-------+-------+-------+--------+
31 * +-------+-------+-------+-------+-------+--------+
33 * --------<-POP---------
39 * How to write an ematch in 60 seconds
40 * ------------------------------------
[all …]
/linux-6.14.4/fs/jfs/
Djfs_dmap.h1 /* SPDX-License-Identifier: GPL-2.0-or-later */
3 * Copyright (C) International Business Machines Corp., 2000-2002
11 #define TREESIZE (256+64+16+4+1) /* size of a dmap tree */
12 #define LEAFIND (64+16+4+1) /* index of 1st leaf of a dmap tree */
13 #define LPERDMAP 256 /* num leaves per dmap tree */
14 #define L2LPERDMAP 8 /* l2 number of leaves per dmap tree */
17 #define BUDMIN L2DBWORD /* max free string in a map word */
20 #define CTLTREESIZE (1024+256+64+16+4+1) /* size of a dmapctl tree */
21 #define CTLLEAFIND (256+64+16+4+1) /* idx of 1st leaf of a dmapctl tree */
22 #define LPERCTL 1024 /* num of leaves per dmapctl tree */
[all …]
/linux-6.14.4/fs/ext4/
Dextents_status.c1 // SPDX-License-Identifier: GPL-2.0
11 * Ext4 extents status tree core functions.
21 * According to previous discussion in Ext4 Developer Workshop, we
22 * will introduce a new structure called io tree to track all extent
23 * status in order to solve some problems that we have met
24 * (e.g. Reservation space warning), and provide extent-level locking.
25 * Delay extent tree is the first step to achieve this goal. It is
27 * extent tree, whose goal is only track delayed extents in memory to
30 * delay extent tree at the first commit. But for better understand
31 * what it does, it has been rename to extent status tree.
[all …]
/linux-6.14.4/scripts/tracing/
Ddraw_functrace.py2 # SPDX-License-Identifier: GPL-2.0-only
7 This script parses a trace provided by the function tracer in
9 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
15 # mount -t tracefs nodev /sys/kernel/tracing
21 Then you have your drawn trace in draw_functrace
28 """ This class provides a tree representation of the functions
29 call stack. If a function has no parent in the kernel (interrupt,
46 into the tree at the appropriate place.
59 tree = self
[all …]

12345678910>>...42