Home
last modified time | relevance | path

Searched refs:tree (Results 1 – 25 of 69) sorted by relevance

123

/fs/hfs/
Dbtree.c21 struct hfs_btree *tree; in hfs_btree_open() local
27 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
28 if (!tree) in hfs_btree_open()
31 mutex_init(&tree->tree_lock); in hfs_btree_open()
32 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
34 tree->sb = sb; in hfs_btree_open()
35 tree->cnid = id; in hfs_btree_open()
36 tree->keycmp = keycmp; in hfs_btree_open()
38 tree->inode = iget_locked(sb, id); in hfs_btree_open()
39 if (!tree->inode) in hfs_btree_open()
[all …]
Dbrec.c16 static int hfs_btree_inc_height(struct hfs_btree *tree);
24 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
39 !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) { in hfs_brec_keylen()
40 if (node->tree->attributes & HFS_TREE_BIGKEYS) in hfs_brec_keylen()
41 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
43 retval = node->tree->max_key_len + 1; in hfs_brec_keylen()
45 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (node->tree->attributes & HFS_TREE_BIGKEYS) { in hfs_brec_keylen()
50 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.c48 struct hfs_btree *tree; in hfs_bnode_read_key() local
51 tree = node->tree; in hfs_bnode_read_key()
53 tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_read_key()
56 key_len = tree->max_key_len + 1; in hfs_bnode_read_key()
146 off = node->tree->node_size - 2; in hfs_bnode_dump()
153 if (node->tree->attributes & HFS_TREE_VARIDXKEYS) in hfs_bnode_dump()
156 tmp = node->tree->max_key_len + 1; in hfs_bnode_dump()
173 struct hfs_btree *tree; in hfs_bnode_unlink() local
177 tree = node->tree; in hfs_bnode_unlink()
179 tmp = hfs_bnode_find(tree, node->prev); in hfs_bnode_unlink()
[all …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 fd->tree = tree; in hfs_find_init()
21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
27 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
28 mutex_lock(&tree->tree_lock); in hfs_find_init()
37 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
38 mutex_unlock(&fd->tree->tree_lock); in hfs_find_exit()
39 fd->tree = NULL; in hfs_find_exit()
63 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); in __hfs_brec_find()
[all …]
Dinode.c76 struct hfs_btree *tree; in hfs_releasepage() local
83 tree = HFS_SB(sb)->ext_tree; in hfs_releasepage()
86 tree = HFS_SB(sb)->cat_tree; in hfs_releasepage()
93 if (!tree) in hfs_releasepage()
96 if (tree->node_size >= PAGE_SIZE) { in hfs_releasepage()
97 nidx = page->index >> (tree->node_size_shift - PAGE_SHIFT); in hfs_releasepage()
98 spin_lock(&tree->hash_lock); in hfs_releasepage()
99 node = hfs_bnode_findhash(tree, nidx); in hfs_releasepage()
108 spin_unlock(&tree->hash_lock); in hfs_releasepage()
110 nidx = page->index << (PAGE_SHIFT - tree->node_size_shift); in hfs_releasepage()
[all …]
/fs/hfsplus/
Dbtree.c135 struct hfs_btree *tree; in hfs_btree_open() local
142 tree = kzalloc(sizeof(*tree), GFP_KERNEL); in hfs_btree_open()
143 if (!tree) in hfs_btree_open()
146 mutex_init(&tree->tree_lock); in hfs_btree_open()
147 spin_lock_init(&tree->hash_lock); in hfs_btree_open()
148 tree->sb = sb; in hfs_btree_open()
149 tree->cnid = id; in hfs_btree_open()
153 tree->inode = inode; in hfs_btree_open()
155 if (!HFSPLUS_I(tree->inode)->first_blocks) { in hfs_btree_open()
160 mapping = tree->inode->i_mapping; in hfs_btree_open()
[all …]
Dbrec.c25 dataoff = node->tree->node_size - (rec + 2) * 2; in hfs_brec_lenoff()
40 !(node->tree->attributes & HFS_TREE_VARIDXKEYS) && in hfs_brec_keylen()
41 (node->tree->cnid != HFSPLUS_ATTR_CNID)) { in hfs_brec_keylen()
42 retval = node->tree->max_key_len + 2; in hfs_brec_keylen()
45 node->tree->node_size - (rec + 1) * 2); in hfs_brec_keylen()
48 if (recoff > node->tree->node_size - 2) { in hfs_brec_keylen()
54 if (retval > node->tree->max_key_len + 2) { in hfs_brec_keylen()
65 struct hfs_btree *tree; in hfs_brec_insert() local
72 tree = fd->tree; in hfs_brec_insert()
74 if (!tree->root) in hfs_brec_insert()
[all …]
Dbnode.c61 struct hfs_btree *tree; in hfs_bnode_read_key() local
64 tree = node->tree; in hfs_bnode_read_key()
66 tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_read_key()
67 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_read_key()
70 key_len = tree->max_key_len + 2; in hfs_bnode_read_key()
310 off = node->tree->node_size - 2; in hfs_bnode_dump()
317 if (node->tree->attributes & HFS_TREE_VARIDXKEYS || in hfs_bnode_dump()
318 node->tree->cnid == HFSPLUS_ATTR_CNID) in hfs_bnode_dump()
321 tmp = node->tree->max_key_len + 2; in hfs_bnode_dump()
337 struct hfs_btree *tree; in hfs_bnode_unlink() local
[all …]
Dbfind.c15 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) in hfs_find_init() argument
19 fd->tree = tree; in hfs_find_init()
21 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); in hfs_find_init()
25 fd->key = ptr + tree->max_key_len + 2; in hfs_find_init()
27 tree->cnid, __builtin_return_address(0)); in hfs_find_init()
28 switch (tree->cnid) { in hfs_find_init()
30 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); in hfs_find_init()
33 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); in hfs_find_init()
36 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); in hfs_find_init()
49 fd->tree->cnid, __builtin_return_address(0)); in hfs_find_exit()
[all …]
Dinode.c70 struct hfs_btree *tree; in hfsplus_releasepage() local
77 tree = HFSPLUS_SB(sb)->ext_tree; in hfsplus_releasepage()
80 tree = HFSPLUS_SB(sb)->cat_tree; in hfsplus_releasepage()
83 tree = HFSPLUS_SB(sb)->attr_tree; in hfsplus_releasepage()
89 if (!tree) in hfsplus_releasepage()
91 if (tree->node_size >= PAGE_SIZE) { in hfsplus_releasepage()
93 (tree->node_size_shift - PAGE_SHIFT); in hfsplus_releasepage()
94 spin_lock(&tree->hash_lock); in hfsplus_releasepage()
95 node = hfs_bnode_findhash(tree, nidx); in hfsplus_releasepage()
104 spin_unlock(&tree->hash_lock); in hfsplus_releasepage()
[all …]
Dhfsplus_fs.h104 struct hfs_btree *tree; member
288 struct hfs_btree *tree; member
397 void hfs_btree_close(struct hfs_btree *tree);
398 int hfs_btree_write(struct hfs_btree *tree);
399 int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes);
400 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree);
416 struct hfs_bnode *hfs_bnode_findhash(struct hfs_btree *tree, u32 cnid);
418 struct hfs_bnode *hfs_bnode_find(struct hfs_btree *tree, u32 num);
420 struct hfs_bnode *hfs_bnode_create(struct hfs_btree *tree, u32 num);
423 bool hfs_bnode_need_zeroout(struct hfs_btree *tree);
[all …]
Dextents.c104 res = hfs_bmap_reserve(fd->tree, fd->tree->depth + 1); in __hfsplus_ext_write_extent()
429 mutex_unlock(&fd.tree->tree_lock); in hfsplus_free_fork()
433 mutex_lock(&fd.tree->tree_lock); in hfsplus_free_fork()
590 mutex_unlock(&fd.tree->tree_lock); in hfsplus_file_truncate()
595 mutex_lock(&fd.tree->tree_lock); in hfsplus_file_truncate()
603 mutex_unlock(&fd.tree->tree_lock); in hfsplus_file_truncate()
615 mutex_lock(&fd.tree->tree_lock); in hfsplus_file_truncate()
/fs/unicode/
Dmkutf8data.c189 struct tree;
190 static utf8leaf_t *utf8nlookup(struct tree *, unsigned char *,
192 static utf8leaf_t *utf8lookup(struct tree *, unsigned char *, const char *);
345 struct tree { struct
350 struct tree *next; argument
355 int *(*leaf_index)(struct tree *, void *); argument
380 static void *lookup(struct tree *tree, const char *key) in lookup() argument
385 node = tree->root; in lookup()
417 static void tree_walk(struct tree *tree) in tree_walk() argument
428 printf("%s_%x root %p\n", tree->type, tree->maxage, tree->root); in tree_walk()
[all …]
/fs/btrfs/
Dextent_io.h263 struct extent_io_tree *tree, unsigned int owner,
265 void extent_io_tree_release(struct extent_io_tree *tree);
268 int lock_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
271 static inline int lock_extent(struct extent_io_tree *tree, u64 start, u64 end) in lock_extent() argument
273 return lock_extent_bits(tree, start, end, NULL); in lock_extent()
276 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end);
277 int extent_read_full_page(struct extent_io_tree *tree, struct page *page,
282 u64 count_range_bits(struct extent_io_tree *tree,
287 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
290 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
[all …]
Dordered-data.c141 static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree, in tree_search() argument
144 struct rb_root *root = &tree->tree; in tree_search()
149 if (tree->last) { in tree_search()
150 entry = rb_entry(tree->last, struct btrfs_ordered_extent, in tree_search()
153 return tree->last; in tree_search()
159 tree->last = ret; in tree_search()
180 struct btrfs_ordered_inode_tree *tree; in __btrfs_add_ordered_extent() local
184 tree = &BTRFS_I(inode)->ordered_tree; in __btrfs_add_ordered_extent()
218 spin_lock_irq(&tree->lock); in __btrfs_add_ordered_extent()
219 node = tree_insert(&tree->tree, file_offset, in __btrfs_add_ordered_extent()
[all …]
Dextent_io.c87 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
88 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
90 struct extent_io_tree *tree, u64 start, u64 end) in __btrfs_debug_check_extent_io_range() argument
92 struct inode *inode = tree->private_data; in __btrfs_debug_check_extent_io_range()
120 struct extent_io_tree *tree; member
152 struct extent_io_tree *tree = bio->bi_private; in submit_one_bio() local
156 if (tree->ops) in submit_one_bio()
157 ret = tree->ops->submit_bio_hook(tree->private_data, bio, in submit_one_bio()
251 struct extent_io_tree *tree, unsigned int owner, in extent_io_tree_init() argument
254 tree->fs_info = fs_info; in extent_io_tree_init()
[all …]
Dextent_map.c36 void extent_map_tree_init(struct extent_map_tree *tree) in extent_map_tree_init() argument
38 tree->map = RB_ROOT_CACHED; in extent_map_tree_init()
39 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
40 rwlock_init(&tree->lock); in extent_map_tree_init()
231 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) in try_merge_map() argument
250 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
262 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
281 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, in unpin_extent_cache() argument
288 write_lock(&tree->lock); in unpin_extent_cache()
289 em = lookup_extent_mapping(tree, start, len); in unpin_extent_cache()
[all …]
DMakefile5 btrfs-y += super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.o \
7 transaction.o inode.o file.o tree-defrag.o \
10 export.o tree-log.o free-space-cache.o zlib.o lzo.o zstd.o \
13 uuid-tree.o props.o free-space-tree.o tree-checker.o space-info.o \
23 tests/free-space-tree-tests.o tests/extent-map-tests.o
Dextent_map.h84 void extent_map_tree_init(struct extent_map_tree *tree);
85 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
87 int add_extent_mapping(struct extent_map_tree *tree,
89 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em);
90 void replace_extent_mapping(struct extent_map_tree *tree,
99 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, u64 gen);
100 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em);
101 struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
/fs/ext4/
Dextents_status.c171 void ext4_es_init_tree(struct ext4_es_tree *tree) in ext4_es_init_tree() argument
173 tree->root = RB_ROOT; in ext4_es_init_tree()
174 tree->cache_es = NULL; in ext4_es_init_tree()
180 struct ext4_es_tree *tree; in ext4_es_print_tree() local
184 tree = &EXT4_I(inode)->i_es_tree; in ext4_es_print_tree()
185 node = rb_first(&tree->root); in ext4_es_print_tree()
261 struct ext4_es_tree *tree = NULL; in __es_find_extent_range() local
268 tree = &EXT4_I(inode)->i_es_tree; in __es_find_extent_range()
272 if (tree->cache_es) { in __es_find_extent_range()
273 es1 = tree->cache_es; in __es_find_extent_range()
[all …]
/fs/ocfs2/
Duptodate.c159 unsigned int tree, to_purge, purged; in ocfs2_metadata_cache_purge() local
165 tree = !(ci->ci_flags & OCFS2_CACHE_FL_INLINE); in ocfs2_metadata_cache_purge()
170 to_purge, tree); in ocfs2_metadata_cache_purge()
175 if (tree) in ocfs2_metadata_cache_purge()
185 if (tree && purged != to_purge) in ocfs2_metadata_cache_purge()
352 struct ocfs2_meta_cache_item **tree) in ocfs2_expand_cache() argument
367 tree[i]->c_block = ci->ci_cache.ci_array[i]; in ocfs2_expand_cache()
375 __ocfs2_insert_cache_tree(ci, tree[i]); in ocfs2_expand_cache()
376 tree[i] = NULL; in ocfs2_expand_cache()
392 struct ocfs2_meta_cache_item *tree[OCFS2_CACHE_INFO_MAX_ARRAY] = in __ocfs2_set_buffer_uptodate() local
[all …]
Drefcounttree.c197 struct ocfs2_refcount_tree *tree = NULL; in ocfs2_find_refcount_tree() local
200 tree = rb_entry(n, struct ocfs2_refcount_tree, rf_node); in ocfs2_find_refcount_tree()
202 if (blkno < tree->rf_blkno) in ocfs2_find_refcount_tree()
204 else if (blkno > tree->rf_blkno) in ocfs2_find_refcount_tree()
207 return tree; in ocfs2_find_refcount_tree()
244 static void ocfs2_free_refcount_tree(struct ocfs2_refcount_tree *tree) in ocfs2_free_refcount_tree() argument
246 ocfs2_metadata_cache_exit(&tree->rf_ci); in ocfs2_free_refcount_tree()
247 ocfs2_simple_drop_lockres(OCFS2_SB(tree->rf_sb), &tree->rf_lockres); in ocfs2_free_refcount_tree()
248 ocfs2_lock_res_free(&tree->rf_lockres); in ocfs2_free_refcount_tree()
249 kfree(tree); in ocfs2_free_refcount_tree()
[all …]
/fs/btrfs/tests/
Dextent-io-tests.c439 struct extent_io_tree tree; in test_find_first_clear_extent_bit() local
444 extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL); in test_find_first_clear_extent_bit()
450 set_extent_bits(&tree, SZ_1M, SZ_4M - 1, in test_find_first_clear_extent_bit()
453 find_first_clear_extent_bit(&tree, SZ_512K, &start, &end, in test_find_first_clear_extent_bit()
463 set_extent_bits(&tree, SZ_32M, SZ_64M - 1, in test_find_first_clear_extent_bit()
469 find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end, in test_find_first_clear_extent_bit()
482 find_first_clear_extent_bit(&tree, SZ_2M, &start, &end, in test_find_first_clear_extent_bit()
495 set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED); in test_find_first_clear_extent_bit()
496 find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end, in test_find_first_clear_extent_bit()
505 find_first_clear_extent_bit(&tree, SZ_64M - SZ_8M, &start, &end, in test_find_first_clear_extent_bit()
[all …]
/fs/dlm/
Ddebug_fs.c421 struct rb_root *tree; in table_seq_start() local
450 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; in table_seq_start()
453 if (!RB_EMPTY_ROOT(tree)) { in table_seq_start()
454 for (node = rb_first(tree); node; node = rb_next(node)) { in table_seq_start()
482 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; in table_seq_start()
485 if (!RB_EMPTY_ROOT(tree)) { in table_seq_start()
486 node = rb_first(tree); in table_seq_start()
503 struct rb_root *tree; in table_seq_next() local
547 tree = toss ? &ls->ls_rsbtbl[bucket].toss : &ls->ls_rsbtbl[bucket].keep; in table_seq_next()
550 if (!RB_EMPTY_ROOT(tree)) { in table_seq_next()
[all …]
/fs/xfs/
Dxfs_dquot.c659 struct radix_tree_root *tree, in xfs_qm_dqget_cache_lookup() argument
666 dqp = radix_tree_lookup(tree, id); in xfs_qm_dqget_cache_lookup()
700 struct radix_tree_root *tree, in xfs_qm_dqget_cache_insert() argument
707 error = radix_tree_insert(tree, id, dqp); in xfs_qm_dqget_cache_insert()
767 struct radix_tree_root *tree = xfs_dquot_tree(qi, type); in xfs_qm_dqget() local
776 dqp = xfs_qm_dqget_cache_lookup(mp, qi, tree, id); in xfs_qm_dqget()
786 error = xfs_qm_dqget_cache_insert(mp, qi, tree, id, dqp); in xfs_qm_dqget()
856 struct radix_tree_root *tree = xfs_dquot_tree(qi, type); in xfs_qm_dqget_inode() local
871 dqp = xfs_qm_dqget_cache_lookup(mp, qi, tree, id); in xfs_qm_dqget_inode()
910 error = xfs_qm_dqget_cache_insert(mp, qi, tree, id, dqp); in xfs_qm_dqget_inode()

123