| /linux/Documentation/core-api/ |
| H A 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 …]
|
| H A D | generic-radix-tree.rst | 2 Generic radix trees/sparse arrays
6 :doc: Generic radix trees/sparse arrays
|
| /linux/Documentation/maintainer/ |
| H A 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/Documentation/arch/arm/google/ |
| H A 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/fs/unicode/ |
| H A 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/arch/arm/mach-sti/ |
| H A D | Kconfig | 36 Trees.
45 Trees.
55 Trees.
|
| /linux/Documentation/process/ |
| H A 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 …]
|
| H A D | stable-kernel-rules.rst | 43 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 this tag in the sign-off area::
207 Trees chapter
|
| H A D | howto.rst | 238 - Various stable trees with multiple major numbers
239 - Subsystem-specific trees
278 Various stable trees with multiple major numbers
291 Stable trees are maintained by the "stable" team <stable@vger.kernel.org>, and
301 Subsystem-specific trees
312 Most of these repositories are git trees, but there are also other SCMs
329 Before updates from subsystem trees are merged into the mainline tree,
331 testing repository exists into which virtually all subsystem trees are
|
| /linux/lib/zlib_deflate/ |
| H A 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 */
|
| H A 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/drivers/md/persistent-data/ |
| H A D | dm-btree.h | 34 * 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/fs/xfs/libxfs/ |
| H A D | xfs_trans_resv.c | 60 * allocating an extent. In classic XFS there were two trees that will be
61 * modified (bnobt + cntbt). With rmap enabled, there are three trees
64 * num trees * ((2 blocks/level * max depth) - 1)
150 * the allocation btrees: 2 trees * (max depth - 1) * block size
189 * the allocation btrees: 2 trees * (max depth - 1) * block size
273 * the refcount btrees: nr_ops * 1 trees * (2 * max depth - 1) * block size
276 * the rtrefcount btrees: nr_ops * 1 trees * (2 * max depth - 1) * block size
307 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
315 * the allocation btrees: 2 trees * (2 * max depth - 1) * block size
320 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
[all …]
|
| /linux/kernel/ |
| H A 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()
[all...] |
| /linux/drivers/mtd/ |
| H A 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/scripts/dtc/libfdt/ |
| H A 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/Documentation/bpf/ |
| H A D | bpf_devel_QA.rst | 102 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/lib/ |
| H A 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/Documentation/mm/damon/ |
| H A D | maintainer-profile.rst | 14 SCM Trees
17 There are multiple Linux trees for DAMON development. Patches under
58 <https://git.kernel.org/akpm/mm/h/mm-stable>`_ trees depend on the memory
|
| /linux/Documentation/devicetree/bindings/clock/ |
| H A D | fsl,qoriq-clock-legacy.yaml | 14 device trees with these nodes, but new device trees should not use them.
|
| /linux/fs/btrfs/ |
| H A D | ctree.h | 104 * Only subvolume trees and their reloc trees have this bit set.
114 * While for non-shareable trees, we just simply do a tree search
191 /* Used only for log trees of subvolumes, not for the log root tree */
194 /* Used only for log trees of subvolumes, not for the log root tree */
202 * trees where the field can be updated directly.
310 /* Used only by log trees, when logging csum items */
|
| /linux/Documentation/arch/riscv/ |
| H A D | patch-acceptance.rst | 44 ECR. (Developers may, of course, maintain their own Linux kernel trees
58 (Implementers, may, of course, maintain their own Linux kernel trees containing
|
| /linux/drivers/md/dm-vdo/ |
| H A D | block-map.h | 24 * consists of a collection of 60 radix trees gradually allocated as logical addresses are used.
29 * radix trees assigned to that zone. The concurrency guarantees of this single-threaded model
271 /* The trees for finding block map pages */
273 /* The expanded trees awaiting growth */
|
| /linux/include/linux/ |
| H A 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/Documentation/filesystems/ |
| H A D | directory-locking.rst | 74 operations on directory trees, but we obviously do not have the full
77 Trees grow as we do operations; memory pressure prunes them. Normally
89 dcache trees. Lookup is already holding the parent locked. If alias is
241 suppose the parents are initially in different trees; we would lock the
|