Home
last modified time | relevance | path

Searched full:tree (Results 1 – 25 of 2008) sorted by relevance

12345678910>>...81

/linux-3.3/fs/hfs/
Dbtree.c17 /* Get a reference to a B*Tree and do some initial checks */
20 struct hfs_btree *tree; in hfs_btree_open() local
26 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
27 if (!tree) in hfs_btree_open()
30 mutex_init(&tree->tree_lock); in hfs_btree_open()
31 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
33 tree->sb = sb; in hfs_btree_open()
34 tree->cnid = id; in hfs_btree_open()
35 tree->keycmp = keycmp; in hfs_btree_open()
37 tree->inode = iget_locked(sb, id); in hfs_btree_open()
[all …]
Dbrec.c15 static int hfs_btree_inc_height(struct hfs_btree *tree);
23 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
38 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
39 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
40 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
42 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
44 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
47 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
49 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
56 if (retval > node->tree->max_key_len + 1) { in hfs_brec_keylen()
[all …]
Dbnode.c47 struct hfs_btree *tree; in hfs_bnode_read_key() local
50 tree = node->tree; in hfs_bnode_read_key()
52 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
55 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
100 struct hfs_btree *tree; in hfs_bnode_copy() local
106 tree = src_node->tree; in hfs_bnode_copy()
147 off = node->tree->node_size - 2; in hfs_bnode_dump()
154 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
157 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
173 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
Dbfind.c14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
18 fd->tree = tree; in hfs_find_init()
20 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
24 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
25 dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0)); in hfs_find_init()
26 mutex_lock(&tree->tree_lock); in hfs_find_init()
34 dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
35 mutex_unlock(&fd->tree->tree_lock); in hfs_find_exit()
36 fd->tree = NULL; in hfs_find_exit()
60 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); in __hfs_brec_find()
[all …]
/linux-3.3/fs/hfsplus/
Dbtree.c19 /* Get a reference to a B*Tree and do some initial checks */
22 struct hfs_btree *tree; in hfs_btree_open() local
29 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
30 if (!tree) in hfs_btree_open()
33 mutex_init(&tree->tree_lock); in hfs_btree_open()
34 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
35 tree->sb = sb; in hfs_btree_open()
36 tree->cnid = id; in hfs_btree_open()
40 tree->inode = inode; in hfs_btree_open()
42 if (!HFSPLUS_I(tree->inode)->first_blocks) { in hfs_btree_open()
[all …]
Dbrec.c24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
46 if (recoff > node->tree->node_size - 2) { in hfs_brec_keylen()
52 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
63 struct hfs_btree *tree; in hfs_brec_insert() local
70 tree = fd->tree; in hfs_brec_insert()
72 if (!tree->root) in hfs_brec_insert()
73 hfs_btree_inc_height(tree); in hfs_brec_insert()
[all …]
Dbnode.c60 struct hfs_btree *tree; in hfs_bnode_read_key() local
63 tree = node->tree; in hfs_bnode_read_key()
65 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
68 key_len = tree->max_key_len + 2; in hfs_bnode_read_key()
128 struct hfs_btree *tree; in hfs_bnode_copy() local
135 tree = src_node->tree; in hfs_bnode_copy()
310 off = node->tree->node_size - 2; in hfs_bnode_dump()
317 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
320 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
336 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
Dbfind.c14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
18 fd->tree = tree; in hfs_find_init()
20 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
24 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
26 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
27 mutex_lock(&tree->tree_lock); in hfs_find_init()
36 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
37 mutex_unlock(&fd->tree->tree_lock); in hfs_find_exit()
38 fd->tree = NULL; in hfs_find_exit()
62 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); in __hfs_brec_find()
[all …]
/linux-3.3/kernel/
Daudit_tree.c46 * the same tree.
53 * tree.chunks anchors chunk.owners[].list hash_lock
54 * tree.rules anchors rule.rlist audit_filter_mutex
55 * chunk.trees anchors tree.same_root hash_lock
59 * tree is refcounted; one reference for "some rules on rules_list refer to
75 struct audit_tree *tree; in alloc_tree() local
77 tree = kmalloc(sizeof(struct audit_tree) + strlen(s) + 1, GFP_KERNEL); in alloc_tree()
78 if (tree) { in alloc_tree()
79 atomic_set(&tree->count, 1); in alloc_tree()
80 tree->goner = 0; in alloc_tree()
[all …]
/linux-3.3/fs/btrfs/
Dextent_map.c29 * extent_map_tree_init - initialize extent map tree
30 * @tree: tree to initialize
32 * Initialize the extent tree @tree. Should be called for each new inode
35 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
37 tree->map = RB_ROOT; in extent_map_tree_init()
38 rwlock_init(&tree->lock); in extent_map_tree_init()
108 * search through the tree for an extent_map with a given offset. If
186 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) in try_merge_map() argument
201 rb_erase(&merge->rb_node, &tree->map); in try_merge_map()
212 rb_erase(&merge->rb_node, &tree->map); in try_merge_map()
[all …]
Dextent_io.c44 struct extent_io_tree *tree; member
84 "state %lu in tree %p refs %d\n", in extent_io_exit()
87 state->state, state->tree, atomic_read(&state->refs)); in extent_io_exit()
107 void extent_io_tree_init(struct extent_io_tree *tree, in extent_io_tree_init() argument
110 tree->state = RB_ROOT; in extent_io_tree_init()
111 INIT_RADIX_TREE(&tree->buffer, GFP_ATOMIC); in extent_io_tree_init()
112 tree->ops = NULL; in extent_io_tree_init()
113 tree->dirty_bytes = 0; in extent_io_tree_init()
114 spin_lock_init(&tree->lock); in extent_io_tree_init()
115 spin_lock_init(&tree->buffer_lock); in extent_io_tree_init()
[all …]
Dextent_io.h111 struct extent_io_tree *tree; member
176 void extent_io_tree_init(struct extent_io_tree *tree,
179 struct extent_io_tree *tree, struct page *page,
181 int try_release_extent_buffer(struct extent_io_tree *tree, struct page *page);
183 struct extent_io_tree *tree, struct page *page,
185 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end, gfp_t mask);
186 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
188 int unlock_extent(struct extent_io_tree *tree, u64 start, u64 end, gfp_t mask);
189 int unlock_extent_cached(struct extent_io_tree *tree, u64 start, u64 end,
191 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
[all …]
Dordered-data.c36 * in the tree
63 * look for a given offset in the tree, and if it can't be found return the
140 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree, in tree_search() argument
143 struct rb_root *root = &tree->tree; in tree_search()
148 if (tree->last) { in tree_search()
149 entry = rb_entry(tree->last, struct btrfs_ordered_extent, in tree_search()
152 return tree->last; in tree_search()
158 tree->last = ret; in tree_search()
162 /* allocate and add a new ordered_extent into the per-inode tree.
166 * extent allocation tree
[all …]
/linux-3.3/lib/zlib_deflate/
Ddeftree.c13 * Each code tree is stored in a compressed form which is itself
88 /* The static literal tree. Since the bit lengths are imposed, there is no
90 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init
95 /* The static distance tree. (Actually a trivial tree since all codes use
115 const ct_data *static_tree; /* static tree or NULL */
118 int elems; /* max number of elements in the tree */
137 static void pqdownheap (deflate_state *s, ct_data *tree, int k);
139 static void gen_codes (ct_data *tree, int max_code, ush *bl_count);
141 static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
142 static void send_tree (deflate_state *s, ct_data *tree, int max_code);
[all …]
/linux-3.3/net/sched/
Dematch.c166 static inline struct tcf_ematch *tcf_em_get_match(struct tcf_ematch_tree *tree, in tcf_em_get_match() argument
169 return &tree->matches[index]; in tcf_em_get_match()
286 * tcf_em_tree_validate - validate ematch config TLV and build ematch tree
289 * @nla: ematch tree configuration TLV
290 * @tree: destination ematch tree variable to store the resulting
291 * ematch tree.
294 * ematch tree in @tree. The resulting tree must later be copied into
296 * provide the ematch tree variable of the private classifier data directly,
302 struct tcf_ematch_tree *tree) in tcf_em_tree_validate() argument
310 memset(tree, 0, sizeof(*tree)); in tcf_em_tree_validate()
[all …]
/linux-3.3/scripts/tracing/
Ddraw_functrace.py9 The resulted trace is processed into a tree to produce a more human
10 view of the call stack by drawing textual but hierarchical tree of
28 """ This class provides a tree representation of the functions
46 into the tree at the appropriate place.
59 tree = self
60 while tree != CallTree.ROOT and tree._func != func:
61 tree = tree._parent
62 if tree == CallTree.ROOT:
65 return tree
114 tree = CallTree.ROOT
[all …]
/linux-3.3/Documentation/block/
Dcfq-iosched.txt15 Setting slice_idle to 0 will remove all the idling on queues/service tree
64 All cfq queues doing synchronous sequential IO go on to sync-idle tree.
65 On this tree we idle on each queue individually.
67 All synchronous non-sequential queues go on sync-noidle tree. Also any
68 request which are marked with REQ_NOIDLE go on this service tree. On this
69 tree we do not idle on individual queues instead idle on the whole group
70 of queues or the tree. So if there are 4 queues waiting for IO to dispatch
72 no more IO on this service tree.
74 All async writes go on async service tree. There is no idling on async
80 all the queues move to sync-noidle tree and only tree idle remains. This
[all …]
/linux-3.3/scripts/dtc/libfdt/
Dlibfdt.h4 * libfdt - Flat Device Tree manipulation
68 * tree, but its buffer did not have sufficient space to
69 * contain the expanded tree. Use fdt_open_into() to move the
70 * device tree to a buffer with more space. */
86 * tree created by the sequential-write functions, which is
89 /* Error codes: codes for bad device tree blobs */
91 /* FDT_ERR_TRUNCATED: Structure block of the given device tree
94 /* FDT_ERR_BADMAGIC: Given "device tree" appears not to be a
95 * device tree at all - it is missing the flattened device
96 * tree magic number. */
[all …]
/linux-3.3/Documentation/devicetree/
Dbooting-without-of.txt21 2) Device tree generalities
22 3) Device tree "structure" block
23 4) Device tree "strings" block
25 III - Required content of the device tree
38 IV - "dtc", the device tree compiler
65 small device tree, though it is encouraged
93 - Add a chapter about the device-tree
95 the tree that can be "compiled" by dtc.
105 - Add some definitions of interrupt tree (simple/complex)
127 but no new board support will be accepted in the main tree that
[all …]
/linux-3.3/lib/
DKconfig35 This option is provided for the case where no in-kernel-tree
37 the kernel tree does. Such modules that use library CRC-CCITT
43 This option is provided for the case where no in-kernel-tree
45 the kernel tree does. Such modules that use library CRC16
52 kernel tree needs to calculate CRC checks for use with the
58 This option is provided for the case where no in-kernel-tree
60 the kernel tree does. Such modules that use library CRC ITU-T V.41
68 This option is provided for the case where no in-kernel-tree
70 kernel tree does. Such modules that use library CRC32 functions
76 This option is provided for the case where no in-kernel-tree
[all …]
/linux-3.3/scripts/dtc/
Dfstree.c31 struct node *tree; in read_fstree() local
37 tree = build_node(NULL, NULL); in read_fstree()
64 add_property(tree, prop); in read_fstree()
72 add_child(tree, newchild); in read_fstree()
79 return tree; in read_fstree()
84 struct node *tree; in dt_from_fs() local
86 tree = read_fstree(dirname); in dt_from_fs()
87 tree = name_node(tree, ""); in dt_from_fs()
89 return build_boot_info(NULL, tree, guess_boot_cpuid(tree)); in dt_from_fs()
/linux-3.3/Documentation/powerpc/
Dbootwrapper.txt26 tree). This image embeds a device tree blob inside
27 the image. The boot wrapper, kernel and device tree
31 tree before jumping into the kernel.
36 which populates the embedded device tree with data
42 dtbImage.%: Similar to zImage, except device tree blob is embedded
47 interface for passing a device tree directly.
59 a device tree blob. This image is a flat binary that
63 the embedded device tree for all information.
86 tree blob inside the image.
91 a device tree to the kernel at boot. If using an older
[all …]
/linux-3.3/Documentation/
Dprio_tree.txt6 A regular radix-priority-search-tree indexes vmas using only heap_index and
15 similar to a pure binary radix tree.
17 A regular radix-priority-search-tree helps to store and query
18 intervals (vmas). However, a regular radix-priority-search-tree is only
21 Therefore, the prio_tree.c extends the regular radix-priority-search-tree
26 tree cannot index them all, we build an overflow-sub-tree that indexes such
29 indexed by regular radix-priority-search-tree whereas others are pushed
30 into an overflow-subtree. Note that all vmas in an overflow-sub-tree have
36 In the final tree the first few (prio_tree_root->index_bits) levels
54 1 [1,6,7] [4,3,7] | search tree
[all …]
Drbtree.txt9 Red-black trees are a type of self-balancing binary search tree, used for
18 three rotations, respectively, to balance the tree), with slightly slower
28 red-black tree. Virtual memory areas (VMAs) are tracked with red-black
49 tree implementations. Instead of using pointers to separate rb_node and data
52 users are expected to write their own tree search and insert functions
59 Data nodes in an rbtree tree are structures containing a struct rb_node member:
78 Writing a search function for your tree is fairly straightforward: start at the
106 Inserting data in the tree involves first searching for the place to insert the
107 new node, then inserting the node and rebalancing ("recoloring") the tree.
133 /* Add new node and rebalance tree. */
[all …]
/linux-3.3/fs/jfs/
Djfs_dmap.h24 #define TREESIZE (256+64+16+4+1) /* size of a dmap tree */
25 #define LEAFIND (64+16+4+1) /* index of 1st leaf of a dmap tree */
26 #define LPERDMAP 256 /* num leaves per dmap tree */
27 #define L2LPERDMAP 8 /* l2 number of leaves per dmap tree */
33 #define CTLTREESIZE (1024+256+64+16+4+1) /* size of a dmapctl tree */
34 #define CTLLEAFIND (256+64+16+4+1) /* idx of 1st leaf of a dmapctl tree */
35 #define LPERCTL 1024 /* num of leaves per dmapctl tree */
36 #define L2LPERCTL 10 /* l2 num of leaves per dmapctl tree */
37 #define ROOT 0 /* index of the root of a tree */
62 * of the tree.
[all …]

12345678910>>...81