Home
last modified time | relevance | path

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

12345678910>>...47

/linux/include/linux/
H A 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 …]
H A 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 …]
H A 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/fs/btrfs/
H A 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()
47 "state leak: start %llu end %llu state %u in tree %d refs %d", in btrfs_extent_state_leak_debug_check()
48 state->start, state->end, state->state, in btrfs_extent_state_leak_debug_check()
50 refcount_read(&state->refs)); in btrfs_extent_state_leak_debug_check()
51 list_del(&state->leak_list); in btrfs_extent_state_leak_debug_check()
57 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
[all …]
H A Dextent_map.c1 // SPDX-License-Identifier: GPL-2.0
11 #include "disk-io.h"
21 return -ENOMEM; in btrfs_extent_map_init()
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()
51 RB_CLEAR_NODE(&em->rb_node); in btrfs_alloc_extent_map()
52 refcount_set(&em->refs, 1); in btrfs_alloc_extent_map()
[all …]
/linux/Documentation/core-api/
H A 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 …]
H A Drbtree.rst2 Red-black Trees (rbtree) in Linux
9 What are red-black trees, and what are they for?
10 ------------------------------------------------
12 Red-black trees are a type of self-balancing binary search tree, used for
16 be easily traversed in order, and must be tuned for a specific size and
19 Red-black trees are similar to AVL trees, but provide faster real-time bounded
21 three rotations, respectively, to balance the tree), with slightly slower
26 There are a number of red-black trees in use in the kernel.
29 The high-resolution timer code uses an rbtree to organize outstanding
30 timer requests. The ext3 filesystem tracks directory entries in a
[all …]
/linux/rust/kernel/
H A 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 …]
H A Dmaple_tree.rs1 // SPDX-License-Identifier: GPL-2.0
7 //! Reference: <https://docs.kernel.org/core-api/maple_tree.html>
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
50 fn deref(&self) -> &MapleTree<T> { in deref()
51 &self.tree in deref()
56 fn to_maple_range(range: impl RangeBounds<usize>) -> Option<(usize, usize)> { in to_maple_range()
[all …]
/linux/scripts/dtc/libfdt/
H A Dlibfdt.h1 /* SPDX-License-Identifier: (GPL-2.0-or-later OR BSD-2-Clause) */
5 * libfdt - Flat Device Tree manipulation
28 * tree, bu
[all...]
H A 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 - retrieve
[all...]
H A 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) -
[all...]
/linux/tools/perf/python/
H A Dilist.py2 # SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause)
18 from textual.widgets import Button, Footer, Header, Input, Label, Sparkline, Static, Tree
19 from textual.widgets.tree import TreeNode
23 return (info[key] + "\n") if key in info else ""
27 """Abstraction for the data of value in the tree."""
30 def name(self) -> str:
34 def description(self) -> str:
38 def matches(self, query: str) -> bool:
42 def parse(self) -> perf.evlist:
46 def value(self, evlist: perf.evlist, evsel: perf.evsel, cpu: int, thread: int) -> float:
[all …]
/linux/lib/zlib_deflate/
H A 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/tools/include/linux/
H A 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/Documentation/arch/powerpc/
H A 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/Documentation/filesystems/
H A 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/block/
H A 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/lib/
H A 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/Documentation/filesystems/ext4/
H A 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/net/sched/
H A 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/fs/jfs/
H A 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/kernel/
H A Daudit_tree.c1 // SPDX-License-Identifier: GPL-2.0
54 * audit_tree_group->mark_mutex. Thus as long as we hold
55 * audit_tree_group->mark_mutex and check that the mark is alive by
61 * the same tree.
63 * time and used in AUDIT_TREE rule matching.
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
86 * revert - several operations have very unpleasant cleanup logics and
[all …]
/linux/Documentation/maintainer/
H A Drebasing-and-merging.rst1 .. SPDX-License-Identifier: GPL-2.0
8 Git source-code management system. Git is a powerful tool with a lot of
10 ways to use those features. This document looks in particular at the use
11 of rebasing and merging. Maintainers often get in trouble when they use
15 One thing to be aware of in general is that, unlike many other projects,
16 the kernel community is not scared by seeing merge commits in its
30 - Changing the parent (starting) commit upon which a series of patches is
33 release. We'll call this operation "reparenting" in the discussion
36 - Changing the history of a set of patches by fixing (or deleting) broken
38 the order in which commits are applied. In the following text, this
[all …]
/linux/Documentation/ABI/testing/
H A Dsysfs-firmware-ofw5 When using OpenFirmware or a Flattened Device Tree to enumerate
6 hardware, the device tree structure will be exposed in this
9 It is possible for multiple device-tree directories to exist.
10 Some device drivers use a separate detached device tree which
11 have no attachment to the system tree and will appear in a
15 path directly, but instead should follow /proc/device-tree
17 in the future, but the symlink is the stable ABI.
19 The /proc/device-tree symlink replaces the devicetree /proc
24 hierarchy of directories, one per device tree node. The
27 in the directory. The contents of each file is the exact
[all …]

12345678910>>...47