| /linux-3.3/Documentation/ |
| D | prio_tree.txt | 32 overflow-sub-trees to handle each possible radix_index. For example,
33 in figure we have 3 overflow-sub-trees corresponding to radix indices
37 are indexed using heap and radix indices whereas the overflow-sub-trees below
39 indexed using heap and size indices. In overflow-sub-trees the size_index
65 5 [0,3,3] [2,2,4] [4,0,4] | Overflow-sub-trees
83 We do not optimize the height of overflow-sub-trees using index_bits.
84 The reason is: there can be many such overflow-sub-trees and all of
88 heap-and-size indexed overflow-sub-trees using prio_tree->index_bits.
89 Instead the overflow sub-trees are indexed using full BITS_PER_LONG bits
90 of size_index. This may lead to skewed sub-trees because most of the
[all …]
|
| D | rbtree.txt | 1 Red-black Trees (rbtree) in Linux
6 What are red-black trees, and what are they for?
9 Red-black trees are a type of self-balancing binary search tree, used for
10 storing sortable key/value data pairs. This differs from radix trees (which
16 Red-black trees are similar to AVL trees, but provide faster real-time bounded
23 There are a number of red-black trees in use in the kernel.
29 trees, as are epoll file descriptors, cryptographic keys, and network
33 information on the nature and implementation of Red Black Trees, see:
35 Linux Weekly News article on red-black trees
38 Wikipedia entry on red-black trees
[all …]
|
| D | HOWTO | 212 http://lxr.linux.no/+trees
224 - subsystem specific kernel trees and patches
296 Subsystem Specific kernel trees and patches
306 Most of these repositories are git trees, but there are also other SCMs
322 Before updates from subsystem trees are merged into the mainline 2.6.x
324 testing repository exists into which virtually all subsystem trees are
|
| /linux-3.3/kernel/ |
| D | audit_tree.c | 26 struct list_head trees; /* with root here */ member
55 * chunk.trees anchors tree.same_root hash_lock
149 INIT_LIST_HEAD(&chunk->trees); in alloc_chunk()
207 /* tagging and untagging inodes with trees */
245 list_del_init(&chunk->trees); in untag_chunk()
268 list_replace_init(&chunk->trees, &new->trees); in untag_chunk()
291 list_for_each_entry(owner, &new->trees, same_root) in untag_chunk()
345 list_add(&tree->same_root, &chunk->trees); in create_chunk()
421 list_replace_init(&old->trees, &chunk->trees); in tag_chunk()
436 list_for_each_entry(owner, &chunk->trees, same_root) in tag_chunk()
[all …]
|
| D | auditsc.c | 222 struct audit_tree_refs *trees, *first_trees; member
349 * ->first_trees points to its beginning, ->trees - to the current end of data.
350 * ->tree_count is the number of free entries in array pointed to by ->trees.
368 struct audit_tree_refs *p = ctx->trees; in put_tree_ref()
380 ctx->trees = p; in put_tree_ref()
389 struct audit_tree_refs *p = ctx->trees; in grow_tree_refs()
390 ctx->trees = kzalloc(sizeof(struct audit_tree_refs), GFP_KERNEL); in grow_tree_refs()
391 if (!ctx->trees) { in grow_tree_refs()
392 ctx->trees = p; in grow_tree_refs()
396 p->next = ctx->trees; in grow_tree_refs()
[all …]
|
| /linux-3.3/lib/zlib_deflate/ |
| D | defutil.h | 166 /* used by trees.c: */
179 int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
183 * The same heap array is used to build all trees.
187 /* Depth of each subtree used as tie breaker for trees of equal frequency
203 * - creating new Huffman trees less frequently may not provide fast
208 * trees more frequently.
220 ulg opt_len; /* bit length of current block with optimal trees */
221 ulg static_len; /* bit length of current block with static trees */
275 /* 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 $ */
332 /* Initialize the trees. */ in init_block()
730 /* Determine the bit length frequencies for literal and distance trees */ in build_bl_tree()
749 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", in build_bl_tree()
756 * Send the header for a block using dynamic Huffman trees: the counts, the
852 * Determine the best encoding for the current block: dynamic trees, static
853 * trees or store, and output the encoded block to the zip file. This function
[all …]
|
| /linux-3.3/Documentation/development-process/ |
| D | 2.Process | 163 subsystem tree and into the -next trees (described below). When the
234 first in trees dedicated to network device drivers, wireless networking,
237 those managing lower-level trees, this process is known as the "chain of
245 2.4: NEXT TREES
247 The chain of subsystem trees guides the flow of patches into the kernel,
256 the interesting subsystem trees, but that would be a big and error-prone
259 The answer comes in the form of -next trees, where subsystem trees are
260 collected for testing and review. The older of these trees, maintained by
263 trees; it also has some patches aimed at helping with debugging.
287 Linux-next trees are announced on the linux-kernel and linux-next mailing
[all …]
|
| D | 7.AdvancedTopics | 48 When you are ready to start putting up git trees for others to look at, you
91 an exported tree. Moving changesets between trees to avoid conflicts in
115 can affect your ability to get trees pulled in the future. Quoting Linus:
|
| /linux-3.3/Documentation/block/ |
| D | cfq-iosched.txt | 7 (for sequential workloads) and service trees (for random workloads) before
11 queues/service trees. This can be very helpful on highly seeky media like
60 CFQ has following service trees and various queues are put on these trees.
|
| /linux-3.3/Documentation/devicetree/ |
| D | 00-INDEX | 1 Documentation for device trees, a data structure by which bootloaders pass
10 - Booting Linux without Open Firmware, describes history and format of device trees.
|
| /linux-3.3/drivers/mtd/ |
| D | mtdswap.c | 127 struct mtdswap_tree trees[MTDSWAP_TREE_CNT]; member
175 #define TREE_ROOT(d, name) (&d->trees[MTDSWAP_ ## name].root)
178 #define TREE_COUNT(d, name) (d->trees[MTDSWAP_ ## name].count)
211 oldidx = tp - &d->trees[0]; in mtdswap_eb_detach()
213 d->trees[oldidx].count--; in mtdswap_eb_detach()
241 if (eb->root == &d->trees[idx].root) in mtdswap_rb_add()
245 root = &d->trees[idx].root; in mtdswap_rb_add()
248 d->trees[idx].count++; in mtdswap_rb_add()
816 if (d->trees[idx].root.rb_node != NULL) in __mtdswap_choose_gc_tree()
858 root = &d->trees[i].root; in mtdswap_choose_wl_tree()
[all …]
|
| /linux-3.3/drivers/md/persistent-data/ |
| D | dm-btree.h | 33 * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
130 * Remove a key if present. This doesn't remove empty sub trees. Normally
139 * been filled out. Remember trees can have zero entries, and as such have
|
| /linux-3.3/Documentation/power/ |
| D | pm_qos_interface.txt | 111 and recompute the new aggregated target, calling the notification trees if the
116 call the notification trees if the target was changed as a result of removing
124 The per-device PM QoS framework has 2 different and distinct notification trees:
|
| /linux-3.3/lib/ |
| D | btree.c | 14 * exercise to understand how B+Trees work. Turned out to be useful as well.
16 * B+Trees can be used similar to Linux radix trees (which don't have anything
17 * in common with textbook radix trees, beware). Prerequisite for them working
24 * helps B+Trees.
26 * Compared to radix trees, B+Trees are more efficient when dealing with a
28 * occupied with valid pointers. When densely populated, radix trees contain
29 * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
|
| /linux-3.3/scripts/dtc/ |
| D | dtc.h | 127 /* Live trees */
229 /* Flattened trees */
241 /* FS trees */
|
| /linux-3.3/include/linux/ |
| D | btree.h | 150 * The two trees @target and @victim may not contain the same keys,
152 * if the trees were merged successfully, and may return a failure
153 * when memory allocation fails, in which case both trees might have
|
| /linux-3.3/fs/xfs/ |
| D | xfs_trans.c | 77 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
82 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
112 * 4 exts * 2 trees * (2 * max depth - 1) * block size
114 * the allocation btrees: 2 trees * (max depth - 1) * block size
145 * the allocation btrees: 3 exts * 2 trees * (2 * max depth - 1) * block size
172 * the allocation btrees: 2 trees * (2 * max depth - 1) * block size
200 * the allocation btrees: 2 exts * 2 trees * (2 * max depth - 1) * block size
230 * the allocation btrees: 2 trees * (2 * max depth - 1) * block size
264 * the allocation btrees: 2 trees * (max depth - 1) * block size
303 * the allocation btrees: 2 trees * (max depth - 1) * block size
[all …]
|
| /linux-3.3/fs/ubifs/ |
| D | shrinker.c | 33 * dumps entire sub-trees.
84 * to destroy large sub-trees. Indeed, if a znode is old, then all its in shrink_tnc()
148 * shrink_tnc_trees - shrink UBIFS TNC trees.
|
| /linux-3.3/Documentation/devicetree/bindings/powerpc/fsl/cpm_qe/qe/ |
| D | par_io.txt | 26 the new device trees. Instead, each Par I/O bank should be represented
|
| /linux-3.3/Documentation/filesystems/ |
| D | hpfs.txt | 178 Old versions of this driver created sometimes unbalanced dnode trees. OS/2
180 unbalanced trees too :-) but both HPFS and HPFS386 contain bug that it rarely
181 crashes when the tree is not balanced. This driver handles unbalanced trees
|
| D | sharedsubtree.txt | 906 a) Create the necessary number of mount trees to
909 b) Do not attach any of the trees to its destination.
916 propagation trees; where 'n' is the number of mounts in the
919 Also there should be 'm' new mount trees, where 'm' is
926 attach each of the mount trees to their corresponding
930 delete all the newly created trees.
|
| D | btrfs.txt | 87 btrfsck: do a limited check of the FS extent trees.
|
| /linux-3.3/arch/powerpc/sysdev/qe_lib/ |
| D | qe.c | 539 * Newer device trees have an "fsl,qe" compatible property for the QE in qe_get_firmware_info()
540 * node, but we still need to support older device trees. in qe_get_firmware_info()
599 /* Older devices trees did not have an "fsl,qe" in qe_get_num_of_risc()
628 /* Older devices trees did not have an "fsl,qe" in qe_get_num_of_snums()
|
| /linux-3.3/Documentation/devicetree/bindings/powerpc/fsl/ |
| D | mpc5200.txt | 27 To express this information as completely as possible, 5200B device trees
31 It is *strongly* recommended that 5200B device trees follow this convention
|