Lines Matching refs:tree
42 * Catalog B-tree Header
47 * Attributes B-tree Header
135 struct hfs_btree *tree;
142 tree = kzalloc(sizeof(*tree), GFP_KERNEL);
143 if (!tree)
146 mutex_init(&tree->tree_lock);
147 spin_lock_init(&tree->hash_lock);
148 tree->sb = sb;
149 tree->cnid = id;
153 tree->inode = inode;
155 if (!HFSPLUS_I(tree->inode)->first_blocks) {
160 mapping = tree->inode->i_mapping;
168 tree->root = be32_to_cpu(head->root);
169 tree->leaf_count = be32_to_cpu(head->leaf_count);
170 tree->leaf_head = be32_to_cpu(head->leaf_head);
171 tree->leaf_tail = be32_to_cpu(head->leaf_tail);
172 tree->node_count = be32_to_cpu(head->node_count);
173 tree->free_nodes = be32_to_cpu(head->free_nodes);
174 tree->attributes = be32_to_cpu(head->attributes);
175 tree->node_size = be16_to_cpu(head->node_size);
176 tree->max_key_len = be16_to_cpu(head->max_key_len);
177 tree->depth = be16_to_cpu(head->depth);
179 /* Verify the tree and set the correct compare function */
182 if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) {
184 tree->max_key_len);
187 if (tree->attributes & HFS_TREE_VARIDXKEYS) {
192 tree->keycmp = hfsplus_ext_cmp_key;
195 if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) {
197 tree->max_key_len);
200 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
207 tree->keycmp = hfsplus_cat_bin_cmp_key;
209 tree->keycmp = hfsplus_cat_case_cmp_key;
214 if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {
216 tree->max_key_len);
219 tree->keycmp = hfsplus_attr_bin_cmp_key;
226 if (!(tree->attributes & HFS_TREE_BIGKEYS)) {
231 size = tree->node_size;
234 if (!tree->node_count)
237 tree->node_size_shift = ffs(size) - 1;
239 tree->pages_per_bnode =
240 (tree->node_size + PAGE_SIZE - 1) >>
245 return tree;
251 tree->inode->i_mapping->a_ops = &hfsplus_aops;
252 iput(tree->inode);
254 kfree(tree);
259 void hfs_btree_close(struct hfs_btree *tree)
264 if (!tree)
268 while ((node = tree->node_hash[i])) {
269 tree->node_hash[i] = node->next_hash;
273 node->tree->cnid, node->this,
276 tree->node_hash_cnt--;
279 iput(tree->inode);
280 kfree(tree);
283 int hfs_btree_write(struct hfs_btree *tree)
289 node = hfs_bnode_find(tree, 0);
298 head->root = cpu_to_be32(tree->root);
299 head->leaf_count = cpu_to_be32(tree->leaf_count);
300 head->leaf_head = cpu_to_be32(tree->leaf_head);
301 head->leaf_tail = cpu_to_be32(tree->leaf_tail);
302 head->node_count = cpu_to_be32(tree->node_count);
303 head->free_nodes = cpu_to_be32(tree->free_nodes);
304 head->attributes = cpu_to_be32(tree->attributes);
305 head->depth = cpu_to_be16(tree->depth);
315 struct hfs_btree *tree = prev->tree;
320 node = hfs_bnode_create(tree, idx);
324 tree->free_nodes--;
331 hfs_bnode_clear(node, 0, tree->node_size);
340 hfs_bnode_write_u16(node, tree->node_size - 2, 14);
341 hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);
346 /* Make sure @tree has enough space for the @rsvd_nodes */
347 int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes)
349 struct inode *inode = tree->inode;
357 while (tree->free_nodes < rsvd_nodes) {
358 res = hfsplus_file_extend(inode, hfs_bnode_need_zeroout(tree));
363 HFSPLUS_SB(tree->sb)->alloc_blksz_shift;
365 hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift;
367 count = inode->i_size >> tree->node_size_shift;
368 tree->free_nodes += count - tree->node_count;
369 tree->node_count = count;
374 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
385 res = hfs_bmap_reserve(tree, 1);
390 node = hfs_bnode_find(tree, nidx);
412 tree->free_nodes--;
413 mark_inode_dirty(tree->inode);
415 return hfs_bnode_create(tree,
434 next_node = hfs_bnode_find(tree, nidx);
451 struct hfs_btree *tree;
459 tree = node->tree;
461 node = hfs_bnode_find(tree, 0);
479 node = hfs_bnode_find(tree, i);
510 tree->free_nodes++;
511 mark_inode_dirty(tree->inode);