| /Linux-v6.1/include/linux/ |
| D | rbtree_latch.h | 3 * Latched RB-trees
7 * Since RB-trees have non-atomic modifications they're not immediately suited
129 * latch_tree_insert() - insert @node into the trees @root
131 * @root: trees to insert @node into
155 * latch_tree_erase() - removes @node from the trees @root
157 * @root: trees to remove @node from
160 * Removes @node from the trees @root in an ordered fashion such that we can
182 * latch_tree_find() - find the node matching @key in the trees @root
184 * @root: trees to search for @key
187 * Does a lockless lookup in the trees @root for the node matching @key.
|
| D | btree.h | 151 * The two trees @target and @victim may not contain the same keys,
153 * if the trees were merged successfully, and may return a failure
154 * when memory allocation fails, in which case both trees might have
|
| /Linux-v6.1/Documentation/core-api/ |
| D | rbtree.rst | 2 Red-black Trees (rbtree) in Linux
9 What are red-black trees, and what are they for?
12 Red-black trees are a type of self-balancing binary search tree, used for
13 storing sortable key/value data pairs. This differs from radix trees (which
19 Red-black trees are similar to AVL trees, but provide faster real-time bounded
26 There are a number of red-black trees in use in the kernel.
32 trees, as are epoll file descriptors, cryptographic keys, and network
36 information on the nature and implementation of Red Black Trees, see:
38 Linux Weekly News article on red-black trees
41 Wikipedia entry on red-black trees
[all …]
|
| D | generic-radix-tree.rst | 2 Generic radix trees/sparse arrays
6 :doc: Generic radix trees/sparse arrays
|
| /Linux-v6.1/Documentation/maintainer/ |
| D | rebasing-and-merging.rst | 54 That said, there are always exceptions. Some trees (linux-next being
90 If, instead, rebasing is limited to private trees, commits are based on a
99 Kernel work is accumulated in over 100 different subsystem trees, each of
110 from lower-level subsystem trees and from others, either sibling trees or
113 Merging from lower-level trees
135 Merging from sibling or upstream trees
139 trees tend to be a red flag when it comes time to push a branch upstream.
154 hide interactions with other trees that should not be happening (often) in
199 with the maintainer to carry both sets of changes in one of the trees or
201 merged into both trees. If the dependency is related to major
|
| /Linux-v6.1/Documentation/arm/google/ |
| D | chromebook-boot-flow.rst | 9 Image`_ which contains an OS image as well as a collection of device trees. It
34 Depthcharge_ will look through all device trees in the `FIT Image`_ trying to
36 through all device trees in the `FIT Image`_ trying to find the one that
42 trees:
59 trees with multiple revisions.
|
| /Linux-v6.1/arch/arm/mach-sti/ |
| D | Kconfig | 36 Trees.
45 Trees.
55 Trees.
|
| /Linux-v6.1/fs/unicode/ |
| D | mkutf8data.c | 1357 struct tree *trees; variable
1621 /* Two trees per age: nfdi and nfdicf */ in trees_init()
1623 trees = calloc(trees_count, sizeof(struct tree)); in trees_init()
1625 /* Assign ages to the trees. */ in trees_init()
1630 trees[--count].maxage = maxage; in trees_init()
1631 trees[--count].maxage = maxage; in trees_init()
1644 while (ages[j] < trees[i].maxage) in trees_init()
1646 trees[i].maxage = ages[j-1]; in trees_init()
1649 /* Set up the forwarding between trees. */ in trees_init()
1650 trees[trees_count-2].next = &trees[trees_count-1]; in trees_init()
[all …]
|
| /Linux-v6.1/Documentation/process/ |
| D | 2.Process.rst | 174 subsystem tree and into the -next trees (described below). When the
245 first in trees dedicated to network device drivers, wireless networking,
248 those managing lower-level trees, this process is known as the "chain of
256 Next trees
259 The chain of subsystem trees guides the flow of patches into the kernel,
268 the interesting subsystem trees, but that would be a big and error-prone
271 The answer comes in the form of -next trees, where subsystem trees are
272 collected for testing and review. The older of these trees, maintained by
275 trees; it also has some patches aimed at helping with debugging.
299 Linux-next trees are announced on the linux-kernel and linux-next mailing
[all …]
|
| D | howto.rst | 239 - Various stable trees with multiple major numbers
240 - Subsystem-specific trees
279 Various stable trees with multiple major numbers
292 Stable trees are maintained by the "stable" team <stable@vger.kernel.org>, and
302 Subsystem-specific trees
313 Most of these repositories are git trees, but there are also other SCMs
330 Before updates from subsystem trees are merged into the mainline tree,
332 testing repository exists into which virtually all subsystem trees are
|
| D | 7.AdvancedTopics.rst | 52 When you are ready to start putting up git trees for others to look at, you
95 an exported tree. Moving changesets between trees to avoid conflicts in
119 can affect your ability to get trees pulled in the future. Quoting Linus:
|
| /Linux-v6.1/drivers/md/persistent-data/ |
| D | dm-btree.h | 33 * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
137 * Remove a key if present. This doesn't remove empty sub trees. Normally
156 * been filled out. Remember trees can have zero entries, and as such have
164 * been filled out. Remember trees can have zero entries, and as such have
172 * It only works for single level trees and is internally recursive, so
|
| /Linux-v6.1/fs/xfs/libxfs/ |
| D | xfs_trans_resv.c | 57 * allocating an extent. In classic XFS there were two trees that will be
58 * modified (bnobt + cntbt). With rmap enabled, there are three trees
61 * num trees * ((2 blocks/level * max depth) - 1)
139 * the allocation btrees: 2 trees * (max depth - 1) * block size
178 * the allocation btrees: 2 trees * (max depth - 1) * block size
253 * the refcount btrees: nr_ops * 1 trees * (2 * max depth - 1) * block size
276 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
284 * the allocation btrees: 2 trees * (2 * max depth - 1) * block size
289 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
360 * 4 exts * 2 trees * (2 * max depth - 1) * block size
[all …]
|
| /Linux-v6.1/lib/zlib_deflate/ |
| D | defutil.h | 168 /* used by trees.c: */
181 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
185 * The same heap array is used to build all trees.
189 /* Depth of each subtree used as tie breaker for trees of equal frequency
205 * - creating new Huffman trees less frequently may not provide fast
210 * trees more frequently.
222 ulg opt_len; /* bit length of current block with optimal trees */
223 ulg static_len; /* bit length of current block with static trees */
273 /* in trees.c */
|
| D | deftree.c | 1 /* +++ trees.c */
2 /* trees.c -- output deflated data using Huffman coding
10 * The "deflation" process uses several Huffman trees. The more
33 /* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
278 /* Initialize the trees. */ in init_block()
676 /* Determine the bit length frequencies for literal and distance trees */ in build_bl_tree()
695 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", in build_bl_tree()
702 * Send the header for a block using dynamic Huffman trees: the counts, the
798 * Determine the best encoding for the current block: dynamic trees, static
799 * trees or store, and output the encoded block to the zip file. This function
[all …]
|
| /Linux-v6.1/Documentation/bpf/ |
| D | bpf_devel_QA.rst | 75 applied to one of the two BPF kernel trees.
80 get rejected or are not applicable to the BPF trees (but assigned to
85 A: There are two BPF kernel trees (git repositories). Once patches have
87 of the two BPF trees:
94 analogous to net and net-next trees for networking. Both bpf and
109 to other trees (e.g. tracing) with a small subset of the patches, but
110 net and net-next are always the main trees targeted for integration.
145 please make sure to rebase the patches against those trees in
164 automatically get accepted into net or net-next trees eventually:
169 them from the trees entirely. Therefore, we also reserve to rebase
[all …]
|
| /Linux-v6.1/scripts/dtc/libfdt/ |
| D | libfdt_internal.h | 111 * With this assumption enabled, normal device trees produced by libfdt
112 * and the compiler should be handled safely. Malicious device trees and
114 * device trees (e.g. those only partially loaded) can also cause
160 * device trees with this order.
|
| /Linux-v6.1/kernel/ |
| D | audit_tree.c | 29 struct list_head trees; /* with root here */ member
70 * chunk.trees anchors tree.same_root hash_lock
198 INIT_LIST_HEAD(&chunk->trees); in alloc_chunk()
270 /* tagging and untagging inodes with trees */
299 list_splice_init(&old->trees, &new->trees); in replace_chunk()
300 list_for_each_entry(owner, &new->trees, same_root) in replace_chunk()
366 list_del_init(&chunk->trees); in untag_chunk()
438 list_add(&tree->same_root, &chunk->trees); in create_chunk()
510 list_add(&tree->same_root, &chunk->trees); in tag_chunk()
1010 while (!list_empty(&chunk->trees)) { in evict_chunk()
[all …]
|
| /Linux-v6.1/drivers/mtd/ |
| D | mtdswap.c | 114 struct mtdswap_tree trees[MTDSWAP_TREE_CNT]; member
160 #define TREE_ROOT(d, name) (&d->trees[MTDSWAP_ ## name].root)
163 #define TREE_COUNT(d, name) (d->trees[MTDSWAP_ ## name].count)
196 oldidx = tp - &d->trees[0]; in mtdswap_eb_detach()
198 d->trees[oldidx].count--; in mtdswap_eb_detach()
226 if (eb->root == &d->trees[idx].root) in mtdswap_rb_add()
230 root = &d->trees[idx].root; in mtdswap_rb_add()
233 d->trees[idx].count++; in mtdswap_rb_add()
766 if (d->trees[idx].root.rb_node != NULL) in __mtdswap_choose_gc_tree()
808 root = &d->trees[i].root; in mtdswap_choose_wl_tree()
[all …]
|
| /Linux-v6.1/Documentation/riscv/ |
| D | patch-acceptance.rst | 24 course, maintain their own Linux kernel trees that contain code for
34 (Implementors, may, of course, maintain their own Linux kernel trees
|
| /Linux-v6.1/lib/ |
| D | btree.c | 12 * exercise to understand how B+Trees work. Turned out to be useful as well.
14 * B+Trees can be used similar to Linux radix trees (which don't have anything
15 * in common with textbook radix trees, beware). Prerequisite for them working
22 * helps B+Trees.
24 * Compared to radix trees, B+Trees are more efficient when dealing with a
26 * occupied with valid pointers. When densely populated, radix trees contain
27 * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
|
| /Linux-v6.1/Documentation/devicetree/bindings/clock/ |
| D | qoriq-clock.txt | 77 trees the children of the clockgen node are the clock providers.
110 device trees with these nodes, but new device trees should not use them.
|
| /Linux-v6.1/drivers/of/ |
| D | of_private.h | 112 * General utilities for working with live trees.
116 * own the devtree lock or work on detached trees only.
|
| /Linux-v6.1/sound/soc/tegra/ |
| D | tegra_wm8903.c | 63 * forcing it to active-low. This means that all older device-trees in tegra_wm8903_init()
140 /* older device-trees used wrong polarity for the headphones-detection GPIO */
|
| /Linux-v6.1/fs/ubifs/ |
| D | shrinker.c | 21 * dumps entire sub-trees.
72 * to destroy large sub-trees. Indeed, if a znode is old, then all its in shrink_tnc()
135 * shrink_tnc_trees - shrink UBIFS TNC trees.
|
