| /openbmc/linux/include/linux/ |
| H A 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.
|
| /openbmc/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
|
| /openbmc/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
|
| /openbmc/u-boot/tools/binman/ |
| H A D | state.py | 157 Device trees being used (U-Boot proper, SPL, TPL)
164 """Yield all the nodes that need to be updated in all device trees
166 The property referenced by this node is added to any device trees which
185 """Add a new property to affected device trees with an integer value of 0.
194 """Add a new subnode to a node in affected device trees
211 """Add a new string property to affected device trees
221 """Update an integer property in affected device trees with an integer value
|
| /openbmc/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.
|
| /openbmc/linux/arch/arm/mach-sti/ |
| H A D | Kconfig | 36 Trees.
45 Trees.
55 Trees.
|
| /openbmc/u-boot/lib/zlib/ |
| H A D | deflate.h | 190 /* used by trees.c: */
203 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
207 * The same heap array is used to build all trees.
211 /* Depth of each subtree used as tie breaker for trees of equal frequency
227 * - creating new Huffman trees less frequently may not provide fast
232 * trees more frequently.
244 ulg opt_len; /* bit length of current block with optimal trees */
245 ulg static_len; /* bit length of current block with static trees */
292 /* in trees.c */
|
| /openbmc/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 …]
|
| /openbmc/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 the tag
208 Trees chapter
|
| /openbmc/openbmc/poky/meta/recipes-devtools/rsync/files/ |
| H A D | 0001-Add-missing-prototypes-to-function-declarations.patch | 27 zlib/trees.c | 2 +-
139 diff --git a/zlib/trees.c b/zlib/trees.c
141 --- a/zlib/trees.c
142 +++ b/zlib/trees.c
|
| /openbmc/linux/fs/xfs/libxfs/ |
| H A 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 * (
[all...] |
| /openbmc/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
|
| /openbmc/linux/Documentation/mm/damon/ |
| H A D | maintainer-profile.rst | 13 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.
|
| /openbmc/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 */
|
| /openbmc/openbmc/poky/meta/classes-recipe/ |
| H A D | devicetree.bbclass | 11 # addition to device trees this bbclass also handles compilation of device tree
16 # However this class on purpose separates the deployed device trees into the
18 # output. Additionally the device trees are populated into the sysroot for
24 # device trees built with them are at least GPL-2.0-only (and in some cases dual
|
| /openbmc/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.
|
| /openbmc/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()
1010 while (!list_empty(&chunk->trees)) { in evict_chunk()
[all …]
|
| /openbmc/linux/drivers/md/ |
| H A D | dm-bufio.c | 396 * We spread entries across multiple trees to reduce contention
401 struct buffer_tree trees[]; member
414 read_lock_bh(&bc->trees[cache_index(block, bc->num_locks)].u.spinlock); in cache_read_lock()
416 down_read(&bc->trees[cache_index(block, bc->num_locks)].u.lock); in cache_read_lock()
422 read_unlock_bh(&bc->trees[cache_index(block, bc->num_locks)].u.spinlock); in cache_read_unlock()
424 up_read(&bc->trees[cache_index(block, bc->num_locks)].u.lock); in cache_read_unlock()
430 write_lock_bh(&bc->trees[cache_index(block, bc->num_locks)].u.spinlock); in cache_write_lock()
432 down_write(&bc->trees[cache_index(block, bc->num_locks)].u.lock); in cache_write_lock()
438 write_unlock_bh(&bc->trees[cache_index(block, bc->num_locks)].u.spinlock); in cache_write_unlock()
440 up_write(&bc->trees[cache_index(block, bc->num_locks)].u.lock); in cache_write_unlock()
[all …]
|
| /openbmc/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 …]
|
| /openbmc/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 …]
|
| /openbmc/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%
|
| /openbmc/qemu/include/qemu/ |
| H A D | interval-tree.h | 3 * Interval trees.
12 * For now, don't expose Linux Red-Black Trees separately, but retain the
|
| /openbmc/linux/Documentation/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
|