Home
last modified time | relevance | path

Searched full:trees (Results 1 – 25 of 338) sorted by relevance

12345678910>>...14

/Linux-v6.6/include/linux/
Drbtree_latch.h3 * 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.
Dbtree.h151 * 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.6/Documentation/core-api/
Drbtree.rst2 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 …]
Dgeneric-radix-tree.rst2 Generic radix trees/sparse arrays
6 :doc: Generic radix trees/sparse arrays
/Linux-v6.6/Documentation/maintainer/
Drebasing-and-merging.rst54 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.6/Documentation/arch/arm/google/
Dchromebook-boot-flow.rst9 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.6/arch/arm/mach-sti/
DKconfig36 Trees.
45 Trees.
55 Trees.
/Linux-v6.6/fs/unicode/
Dmkutf8data.c1357 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.6/Documentation/process/
D2.Process.rst174 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 …]
Dstable-kernel-rules.rst43 There are three options to submit a change to -stable trees:
61 submitted, or already present in all newer stable trees still supported. This is
71 for stable trees, add the tag
208 Trees section in Everything you ever wanted to know about Linux -stable releases
Dhowto.rst239 - 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
Dmaintainer-netdev.rst26 volume of traffic have their own specific mailing lists and trees.
62 git trees and patch flow
65 There are two networking trees (git repositories) in play. Both are
70 for the future release. You can find the trees here:
140 sub-maintainer, who will send it on to the networking trees;
243 history in netdev trees is immutable.
/Linux-v6.6/fs/xfs/libxfs/
Dxfs_trans_resv.c57 * 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.6/drivers/md/persistent-data/
Ddm-btree.h34 * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
138 * Remove a key if present. This doesn't remove empty sub trees. Normally
157 * been filled out. Remember trees can have zero entries, and as such have
165 * been filled out. Remember trees can have zero entries, and as such have
173 * It only works for single level trees and is internally recursive, so
/Linux-v6.6/lib/zlib_deflate/
Ddefutil.h168 /* 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 */
Ddeftree.c1 /* +++ 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.6/Documentation/mm/damon/
Dmaintainer-profile.rst13 SCM Trees
16 There are multiple Linux trees for DAMON development. Patches under
45 mm-stable[3] trees depend on the memory management subsystem maintainer.
/Linux-v6.6/kernel/
Daudit_tree.c29 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.6/scripts/dtc/libfdt/
Dlibfdt_internal.h111 * 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.6/drivers/mtd/
Dmtdswap.c114 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.6/Documentation/bpf/
Dbpf_devel_QA.rst102 applied to one of the two BPF kernel trees.
107 get rejected or are not applicable to the BPF trees (but assigned to
112 A: There are two BPF kernel trees (git repositories). Once patches have
114 of the two BPF trees:
121 analogous to net and net-next trees for networking. Both bpf and
137 to other trees (e.g. tracing) with a small subset of the patches, but
138 net and net-next are always the main trees targeted for integration.
174 please make sure to rebase the patches against those trees in
193 automatically get accepted into net or net-next trees eventually:
198 them from the trees entirely. Therefore, we also reserve to rebase
[all …]
/Linux-v6.6/lib/
Dbtree.c12 * 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.6/Documentation/riscv/
Dpatch-acceptance.rst44 ECR. (Developers may, of course, maintain their own Linux kernel trees
58 (Implementers, may, of course, maintain their own Linux kernel trees containing
/Linux-v6.6/fs/btrfs/
Dctree.h129 * Only subvolume trees and their reloc trees have this bit set.
139 * While for non-shareable trees, we just simply do a tree search
216 /* Used only for log trees of subvolumes, not for the log root tree */
219 /* Used only for log trees of subvolumes, not for the log root tree */
326 /* Used only by log trees, when logging csum items */
/Linux-v6.6/drivers/md/
Ddm-bufio.c392 * We spread entries across multiple trees to reduce contention
396 struct buffer_tree trees[]; member
406 down_read(&bc->trees[cache_index(block, bc->num_locks)].lock); in cache_read_lock()
411 up_read(&bc->trees[cache_index(block, bc->num_locks)].lock); in cache_read_unlock()
416 down_write(&bc->trees[cache_index(block, bc->num_locks)].lock); in cache_write_lock()
421 up_write(&bc->trees[cache_index(block, bc->num_locks)].lock); in cache_write_unlock()
446 down_write(&lh->cache->trees[index].lock); in __lh_lock()
448 down_read(&lh->cache->trees[index].lock); in __lh_lock()
454 up_write(&lh->cache->trees[index].lock); in __lh_unlock()
456 up_read(&lh->cache->trees[index].lock); in __lh_unlock()
[all …]

12345678910>>...14