42 	 * Catalog B-tree Header
47 	 * Attributes B-tree Header
132 /* Get a reference to a B*Tree and do some initial checks */
135 	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()
168 	tree->root = be32_to_cpu(head->root);  in hfs_btree_open()
169 	tree->leaf_count = be32_to_cpu(head->leaf_count);  in hfs_btree_open()
170 	tree->leaf_head = be32_to_cpu(head->leaf_head);  in hfs_btree_open()
171 	tree->leaf_tail = be32_to_cpu(head->leaf_tail);  in hfs_btree_open()
172 	tree->node_count = be32_to_cpu(head->node_count);  in hfs_btree_open()
173 	tree->free_nodes = be32_to_cpu(head->free_nodes);  in hfs_btree_open()
174 	tree->attributes = be32_to_cpu(head->attributes);  in hfs_btree_open()
175 	tree->node_size = be16_to_cpu(head->node_size);  in hfs_btree_open()
176 	tree->max_key_len = be16_to_cpu(head->max_key_len);  in hfs_btree_open()
177 	tree->depth = be16_to_cpu(head->depth);  in hfs_btree_open()
179 	/* Verify the tree and set the correct compare function */  in hfs_btree_open()
182 		if (tree->max_key_len != HFSPLUS_EXT_KEYLEN - sizeof(u16)) {  in hfs_btree_open()
184 				tree->max_key_len);  in hfs_btree_open()
187 		if (tree->attributes & HFS_TREE_VARIDXKEYS) {  in hfs_btree_open()
192 		tree->keycmp = hfsplus_ext_cmp_key;  in hfs_btree_open()
195 		if (tree->max_key_len != HFSPLUS_CAT_KEYLEN - sizeof(u16)) {  in hfs_btree_open()
197 				tree->max_key_len);  in hfs_btree_open()
200 		if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {  in hfs_btree_open()
207 			tree->keycmp = hfsplus_cat_bin_cmp_key;  in hfs_btree_open()
209 			tree->keycmp = hfsplus_cat_case_cmp_key;  in hfs_btree_open()
214 		if (tree->max_key_len != HFSPLUS_ATTR_KEYLEN - sizeof(u16)) {  in hfs_btree_open()
216 				tree->max_key_len);  in hfs_btree_open()
219 		tree->keycmp = hfsplus_attr_bin_cmp_key;  in hfs_btree_open()
222 		pr_err("unknown B*Tree requested\n");  in hfs_btree_open()
226 	if (!(tree->attributes & HFS_TREE_BIGKEYS)) {  in hfs_btree_open()
231 	size = tree->node_size;  in hfs_btree_open()
234 	if (!tree->node_count)  in hfs_btree_open()
237 	tree->node_size_shift = ffs(size) - 1;  in hfs_btree_open()
239 	tree->pages_per_bnode =  in hfs_btree_open()
240 		(tree->node_size + PAGE_SIZE - 1) >>  in hfs_btree_open()
245 	return tree;  in hfs_btree_open()
251 	tree->inode->i_mapping->a_ops = &hfsplus_aops;  in hfs_btree_open()
252 	iput(tree->inode);  in hfs_btree_open()
254 	kfree(tree);  in hfs_btree_open()
259 void hfs_btree_close(struct hfs_btree *tree)  in hfs_btree_close()  argument
264 	if (!tree)  in hfs_btree_close()
268 		while ((node = tree->node_hash[i])) {  in hfs_btree_close()
269 			tree->node_hash[i] = node->next_hash;  in hfs_btree_close()
273 					node->tree->cnid, node->this,  in hfs_btree_close()
276 			tree->node_hash_cnt--;  in hfs_btree_close()
279 	iput(tree->inode);  in hfs_btree_close()
280 	kfree(tree);  in hfs_btree_close()
283 int hfs_btree_write(struct hfs_btree *tree)  in hfs_btree_write()  argument
289 	node = hfs_bnode_find(tree, 0);  in hfs_btree_write()
298 	head->root = cpu_to_be32(tree->root);  in hfs_btree_write()
299 	head->leaf_count = cpu_to_be32(tree->leaf_count);  in hfs_btree_write()
300 	head->leaf_head = cpu_to_be32(tree->leaf_head);  in hfs_btree_write()
301 	head->leaf_tail = cpu_to_be32(tree->leaf_tail);  in hfs_btree_write()
302 	head->node_count = cpu_to_be32(tree->node_count);  in hfs_btree_write()
303 	head->free_nodes = cpu_to_be32(tree->free_nodes);  in hfs_btree_write()
304 	head->attributes = cpu_to_be32(tree->attributes);  in hfs_btree_write()
305 	head->depth = cpu_to_be16(tree->depth);  in hfs_btree_write()
315 	struct hfs_btree *tree = prev->tree;  in hfs_bmap_new_bmap()  local
320 	node = hfs_bnode_create(tree, idx);  in hfs_bmap_new_bmap()
324 	tree->free_nodes--;  in hfs_bmap_new_bmap()
331 	hfs_bnode_clear(node, 0, tree->node_size);  in hfs_bmap_new_bmap()
340 	hfs_bnode_write_u16(node, tree->node_size - 2, 14);  in hfs_bmap_new_bmap()
341 	hfs_bnode_write_u16(node, tree->node_size - 4, tree->node_size - 6);  in hfs_bmap_new_bmap()
346 /* Make sure @tree has enough space for the @rsvd_nodes */
347 int hfs_bmap_reserve(struct hfs_btree *tree, int rsvd_nodes)  in hfs_bmap_reserve()  argument
349 	struct inode *inode = tree->inode;  in hfs_bmap_reserve()
357 	while (tree->free_nodes < rsvd_nodes) {  in hfs_bmap_reserve()
358 		res = hfsplus_file_extend(inode, hfs_bnode_need_zeroout(tree));  in hfs_bmap_reserve()
363 				HFSPLUS_SB(tree->sb)->alloc_blksz_shift;  in hfs_bmap_reserve()
365 			hip->alloc_blocks << HFSPLUS_SB(tree->sb)->fs_shift;  in hfs_bmap_reserve()
367 		count = inode->i_size >> tree->node_size_shift;  in hfs_bmap_reserve()
368 		tree->free_nodes += count - tree->node_count;  in hfs_bmap_reserve()
369 		tree->node_count = count;  in hfs_bmap_reserve()
374 struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)  in hfs_bmap_alloc()  argument
385 	res = hfs_bmap_reserve(tree, 1);  in hfs_bmap_alloc()
390 	node = hfs_bnode_find(tree, nidx);  in hfs_bmap_alloc()
412 						tree->free_nodes--;  in hfs_bmap_alloc()
413 						mark_inode_dirty(tree->inode);  in hfs_bmap_alloc()
415 						return hfs_bnode_create(tree,  in hfs_bmap_alloc()
434 			next_node = hfs_bnode_find(tree, nidx);  in hfs_bmap_alloc()
451 	struct hfs_btree *tree;  in hfs_bmap_free()  local
459 	tree = node->tree;  in hfs_bmap_free()
461 	node = hfs_bnode_find(tree, 0);  in hfs_bmap_free()
479 		node = hfs_bnode_find(tree, i);  in hfs_bmap_free()
510 	tree->free_nodes++;  in hfs_bmap_free()
511 	mark_inode_dirty(tree->inode);  in hfs_bmap_free()