[linux-2.6-block.git] / fs / hfsplus / brec.c

// SPDX-License-Identifier: GPL-2.0
/*
 *  linux/fs/hfsplus/brec.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Handle individual btree records
 */

#include "hfsplus_fs.h"
#include "hfsplus_raw.h"

static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd);
static int hfs_brec_update_parent(struct hfs_find_data *fd);
static int hfs_btree_inc_height(struct hfs_btree *);

/* Get the length and offset of the given record in the given node */
u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off)
{
	__be16 retval[2];
	u16 dataoff;

	dataoff = node->tree->node_size - (rec + 2) * 2;
	hfs_bnode_read(node, retval, dataoff, 4);
	*off = be16_to_cpu(retval[1]);
	return be16_to_cpu(retval[0]) - *off;
}

/* Get the length of the key from a keyed record */
u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
{
	u16 retval, recoff;

	if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
		return 0;

	if ((node->type == HFS_NODE_INDEX) &&
	   !(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
	   (node->tree->cnid != HFSPLUS_ATTR_CNID)) {
		retval = node->tree->max_key_len + 2;
	} else {
		recoff = hfs_bnode_read_u16(node,
			node->tree->node_size - (rec + 1) * 2);
		if (!recoff)
			return 0;
		if (recoff > node->tree->node_size - 2) {
			pr_err("recoff %d too large\n", recoff);
			return 0;
		}

		retval = hfs_bnode_read_u16(node, recoff) + 2;
		if (retval > node->tree->max_key_len + 2) {
			pr_err("keylen %d too large\n",
				retval);
			retval = 0;
		}
	}
	return retval;
}

int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int entry_len)
{
	struct hfs_btree *tree;
	struct hfs_bnode *node, *new_node;
	int size, key_len, rec;
	int data_off, end_off;
	int idx_rec_off, data_rec_off, end_rec_off;
	__be32 cnid;

	tree = fd->tree;
	if (!fd->bnode) {
		if (!tree->root)
			hfs_btree_inc_height(tree);
		fd->bnode = hfs_bnode_find(tree, tree->leaf_head);
		if (IS_ERR(fd->bnode))
			return PTR_ERR(fd->bnode);
		fd->record = -1;
	}
	new_node = NULL;
	key_len = be16_to_cpu(fd->search_key->key_len) + 2;
again:
	/* new record idx and complete record size */
	rec = fd->record + 1;
	size = key_len + entry_len;

	node = fd->bnode;
	hfs_bnode_dump(node);
	/* get last offset */
	end_rec_off = tree->node_size - (node->num_recs + 1) * 2;
	end_off = hfs_bnode_read_u16(node, end_rec_off);
	end_rec_off -= 2;
	hfs_dbg(BNODE_MOD, "insert_rec: %d, %d, %d, %d\n",
		rec, size, end_off, end_rec_off);
	if (size > end_rec_off - end_off) {
		if (new_node)
			panic("not enough room!\n");
		new_node = hfs_bnode_split(fd);
		if (IS_ERR(new_node))
			return PTR_ERR(new_node);
		goto again;
	}
	if (node->type == HFS_NODE_LEAF) {
		tree->leaf_count++;
		mark_inode_dirty(tree->inode);
	}
	node->num_recs++;
	/* write new last offset */
	hfs_bnode_write_u16(node,
		offsetof(struct hfs_bnode_desc, num_recs),
		node->num_recs);
	hfs_bnode_write_u16(node, end_rec_off, end_off + size);
	data_off = end_off;
	data_rec_off = end_rec_off + 2;
	idx_rec_off = tree->node_size - (rec + 1) * 2;
	if (idx_rec_off == data_rec_off)
		goto skip;
	/* move all following entries */
	do {
		data_off = hfs_bnode_read_u16(node, data_rec_off + 2);
		hfs_bnode_write_u16(node, data_rec_off, data_off + size);
		data_rec_off += 2;
	} while (data_rec_off < idx_rec_off);

	/* move data away */
	hfs_bnode_move(node, data_off + size, data_off,
		       end_off - data_off);

skip:
	hfs_bnode_write(node, fd->search_key, data_off, key_len);
	hfs_bnode_write(node, entry, data_off + key_len, entry_len);
	hfs_bnode_dump(node);

	/*
	 * update parent key if we inserted a key
	 * at the start of the node and it is not the new node
	 */
	if (!rec && new_node != node) {
		hfs_bnode_read_key(node, fd->search_key, data_off + size);
		hfs_brec_update_parent(fd);
	}

	if (new_node) {
		hfs_bnode_put(fd->bnode);
		if (!new_node->parent) {
			hfs_btree_inc_height(tree);
			new_node->parent = tree->root;
		}
		fd->bnode = hfs_bnode_find(tree, new_node->parent);

		/* create index data entry */
		cnid = cpu_to_be32(new_node->this);
		entry = &cnid;
		entry_len = sizeof(cnid);

		/* get index key */
		hfs_bnode_read_key(new_node, fd->search_key, 14);
		__hfs_brec_find(fd->bnode, fd, hfs_find_rec_by_key);

		hfs_bnode_put(new_node);
		new_node = NULL;

		if ((tree->attributes & HFS_TREE_VARIDXKEYS) ||
				(tree->cnid == HFSPLUS_ATTR_CNID))
			key_len = be16_to_cpu(fd->search_key->key_len) + 2;
		else {
			fd->search_key->key_len =
				cpu_to_be16(tree->max_key_len);
			key_len = tree->max_key_len + 2;
		}
		goto again;
	}

	return 0;
}

int hfs_brec_remove(struct hfs_find_data *fd)
{
	struct hfs_btree *tree;
	struct hfs_bnode *node, *parent;
	int end_off, rec_off, data_off, size;

	tree = fd->tree;
	node = fd->bnode;
again:
	rec_off = tree->node_size - (fd->record + 2) * 2;
	end_off = tree->node_size - (node->num_recs + 1) * 2;

	if (node->type == HFS_NODE_LEAF) {
		tree->leaf_count--;
		mark_inode_dirty(tree->inode);
	}
	hfs_bnode_dump(node);
	hfs_dbg(BNODE_MOD, "remove_rec: %d, %d\n",
		fd->record, fd->keylength + fd->entrylength);
	if (!--node->num_recs) {
		hfs_bnode_unlink(node);
		if (!node->parent)
			return 0;
		parent = hfs_bnode_find(tree, node->parent);
		if (IS_ERR(parent))
			return PTR_ERR(parent);
		hfs_bnode_put(node);
		node = fd->bnode = parent;

		__hfs_brec_find(node, fd, hfs_find_rec_by_key);
		goto again;
	}
	hfs_bnode_write_u16(node,
		offsetof(struct hfs_bnode_desc, num_recs),
		node->num_recs);

	if (rec_off == end_off)
		goto skip;
	size = fd->keylength + fd->entrylength;

	do {
		data_off = hfs_bnode_read_u16(node, rec_off);
		hfs_bnode_write_u16(node, rec_off + 2, data_off - size);
		rec_off -= 2;
	} while (rec_off >= end_off);

	/* fill hole */
	hfs_bnode_move(node, fd->keyoffset, fd->keyoffset + size,
		       data_off - fd->keyoffset - size);
skip:
	hfs_bnode_dump(node);
	if (!fd->record)
		hfs_brec_update_parent(fd);
	return 0;
}

static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
{
	struct hfs_btree *tree;
	struct hfs_bnode *node, *new_node, *next_node;
	struct hfs_bnode_desc node_desc;
	int num_recs, new_rec_off, new_off, old_rec_off;
	int data_start, data_end, size;

	tree = fd->tree;
	node = fd->bnode;
	new_node = hfs_bmap_alloc(tree);
	if (IS_ERR(new_node))
		return new_node;
	hfs_bnode_get(node);
	hfs_dbg(BNODE_MOD, "split_nodes: %d - %d - %d\n",
		node->this, new_node->this, node->next);
	new_node->next = node->next;
	new_node->prev = node->this;
	new_node->parent = node->parent;
	new_node->type = node->type;
	new_node->height = node->height;

	if (node->next)
		next_node = hfs_bnode_find(tree, node->next);
	else
		next_node = NULL;

	if (IS_ERR(next_node)) {
		hfs_bnode_put(node);
		hfs_bnode_put(new_node);
		return next_node;
	}

	size = tree->node_size / 2 - node->num_recs * 2 - 14;
	old_rec_off = tree->node_size - 4;
	num_recs = 1;
	for (;;) {
		data_start = hfs_bnode_read_u16(node, old_rec_off);
		if (data_start > size)
			break;
		old_rec_off -= 2;
		if (++num_recs < node->num_recs)
			continue;
		/* panic? */
		hfs_bnode_put(node);
		hfs_bnode_put(new_node);
		if (next_node)
			hfs_bnode_put(next_node);
		return ERR_PTR(-ENOSPC);
	}

	if (fd->record + 1 < num_recs) {
		/* new record is in the lower half,
		 * so leave some more space there
		 */
		old_rec_off += 2;
		num_recs--;
		data_start = hfs_bnode_read_u16(node, old_rec_off);
	} else {
		hfs_bnode_put(node);
		hfs_bnode_get(new_node);
		fd->bnode = new_node;
		fd->record -= num_recs;
		fd->keyoffset -= data_start - 14;
		fd->entryoffset -= data_start - 14;
	}
	new_node->num_recs = node->num_recs - num_recs;
	node->num_recs = num_recs;

	new_rec_off = tree->node_size - 2;
	new_off = 14;
	size = data_start - new_off;
	num_recs = new_node->num_recs;
	data_end = data_start;
	while (num_recs) {
		hfs_bnode_write_u16(new_node, new_rec_off, new_off);
		old_rec_off -= 2;
		new_rec_off -= 2;
		data_end = hfs_bnode_read_u16(node, old_rec_off);
		new_off = data_end - size;
		num_recs--;
	}
	hfs_bnode_write_u16(new_node, new_rec_off, new_off);
	hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start);

	/* update new bnode header */
	node_desc.next = cpu_to_be32(new_node->next);
	node_desc.prev = cpu_to_be32(new_node->prev);
	node_desc.type = new_node->type;
	node_desc.height = new_node->height;
	node_desc.num_recs = cpu_to_be16(new_node->num_recs);
	node_desc.reserved = 0;
	hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));

	/* update previous bnode header */
	node->next = new_node->this;
	hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc));
	node_desc.next = cpu_to_be32(node->next);
	node_desc.num_recs = cpu_to_be16(node->num_recs);
	hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc));

	/* update next bnode header */
	if (next_node) {
		next_node->prev = new_node->this;
		hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc));
		node_desc.prev = cpu_to_be32(next_node->prev);
		hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc));
		hfs_bnode_put(next_node);
	} else if (node->this == tree->leaf_tail) {
		/* if there is no next node, this might be the new tail */
		tree->leaf_tail = new_node->this;
		mark_inode_dirty(tree->inode);
	}

	hfs_bnode_dump(node);
	hfs_bnode_dump(new_node);
	hfs_bnode_put(node);

	return new_node;
}

static int hfs_brec_update_parent(struct hfs_find_data *fd)
{
	struct hfs_btree *tree;
	struct hfs_bnode *node, *new_node, *parent;
	int newkeylen, diff;
	int rec, rec_off, end_rec_off;
	int start_off, end_off;

	tree = fd->tree;
	node = fd->bnode;
	new_node = NULL;
	if (!node->parent)
		return 0;

again:
	parent = hfs_bnode_find(tree, node->parent);
	if (IS_ERR(parent))
		return PTR_ERR(parent);
	__hfs_brec_find(parent, fd, hfs_find_rec_by_key);
	if (fd->record < 0)
		return -ENOENT;
	hfs_bnode_dump(parent);
	rec = fd->record;

	/* size difference between old and new key */
	if ((tree->attributes & HFS_TREE_VARIDXKEYS) ||
				(tree->cnid == HFSPLUS_ATTR_CNID))
		newkeylen = hfs_bnode_read_u16(node, 14) + 2;
	else
		fd->keylength = newkeylen = tree->max_key_len + 2;
	hfs_dbg(BNODE_MOD, "update_rec: %d, %d, %d\n",
		rec, fd->keylength, newkeylen);

	rec_off = tree->node_size - (rec + 2) * 2;
	end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
	diff = newkeylen - fd->keylength;
	if (!diff)
		goto skip;
	if (diff > 0) {
		end_off = hfs_bnode_read_u16(parent, end_rec_off);
		if (end_rec_off - end_off < diff) {

			hfs_dbg(BNODE_MOD, "splitting index node\n");
			fd->bnode = parent;
			new_node = hfs_bnode_split(fd);
			if (IS_ERR(new_node))
				return PTR_ERR(new_node);
			parent = fd->bnode;
			rec = fd->record;
			rec_off = tree->node_size - (rec + 2) * 2;
			end_rec_off = tree->node_size -
				(parent->num_recs + 1) * 2;
		}
	}

	end_off = start_off = hfs_bnode_read_u16(parent, rec_off);
	hfs_bnode_write_u16(parent, rec_off, start_off + diff);
	start_off -= 4;	/* move previous cnid too */

	while (rec_off > end_rec_off) {
		rec_off -= 2;
		end_off = hfs_bnode_read_u16(parent, rec_off);
		hfs_bnode_write_u16(parent, rec_off, end_off + diff);
	}
	hfs_bnode_move(parent, start_off + diff, start_off,
		       end_off - start_off);
skip:
	hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen);
	hfs_bnode_dump(parent);

	hfs_bnode_put(node);
	node = parent;

	if (new_node) {
		__be32 cnid;

		fd->bnode = hfs_bnode_find(tree, new_node->parent);
		/* create index key and entry */
		hfs_bnode_read_key(new_node, fd->search_key, 14);
		cnid = cpu_to_be32(new_node->this);

		__hfs_brec_find(fd->bnode, fd, hfs_find_rec_by_key);
		hfs_brec_insert(fd, &cnid, sizeof(cnid));
		hfs_bnode_put(fd->bnode);
		hfs_bnode_put(new_node);

		if (!rec) {
			if (new_node == node)
				goto out;
			/* restore search_key */
			hfs_bnode_read_key(node, fd->search_key, 14);
		}
	}

	if (!rec && node->parent)
		goto again;
out:
	fd->bnode = node;
	return 0;
}

static int hfs_btree_inc_height(struct hfs_btree *tree)
{
	struct hfs_bnode *node, *new_node;
	struct hfs_bnode_desc node_desc;
	int key_size, rec;
	__be32 cnid;

	node = NULL;
	if (tree->root) {
		node = hfs_bnode_find(tree, tree->root);
		if (IS_ERR(node))
			return PTR_ERR(node);
	}
	new_node = hfs_bmap_alloc(tree);
	if (IS_ERR(new_node)) {
		hfs_bnode_put(node);
		return PTR_ERR(new_node);
	}

	tree->root = new_node->this;
	if (!tree->depth) {
		tree->leaf_head = tree->leaf_tail = new_node->this;
		new_node->type = HFS_NODE_LEAF;
		new_node->num_recs = 0;
	} else {
		new_node->type = HFS_NODE_INDEX;
		new_node->num_recs = 1;
	}
	new_node->parent = 0;
	new_node->next = 0;
	new_node->prev = 0;
	new_node->height = ++tree->depth;

	node_desc.next = cpu_to_be32(new_node->next);
	node_desc.prev = cpu_to_be32(new_node->prev);
	node_desc.type = new_node->type;
	node_desc.height = new_node->height;
	node_desc.num_recs = cpu_to_be16(new_node->num_recs);
	node_desc.reserved = 0;
	hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));

	rec = tree->node_size - 2;
	hfs_bnode_write_u16(new_node, rec, 14);

	if (node) {
		/* insert old root idx into new root */
		node->parent = tree->root;
		if (node->type == HFS_NODE_LEAF ||
				tree->attributes & HFS_TREE_VARIDXKEYS ||
				tree->cnid == HFSPLUS_ATTR_CNID)
			key_size = hfs_bnode_read_u16(node, 14) + 2;
		else
			key_size = tree->max_key_len + 2;
		hfs_bnode_copy(new_node, 14, node, 14, key_size);

		if (!(tree->attributes & HFS_TREE_VARIDXKEYS) &&
				(tree->cnid != HFSPLUS_ATTR_CNID)) {
			key_size = tree->max_key_len + 2;
			hfs_bnode_write_u16(new_node, 14, tree->max_key_len);
		}
		cnid = cpu_to_be32(node->this);
		hfs_bnode_write(new_node, &cnid, 14 + key_size, 4);

		rec -= 2;
		hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4);

		hfs_bnode_put(node);
	}
	hfs_bnode_put(new_node);
	mark_inode_dirty(tree->inode);

	return 0;
}
Commit	Line	Data
b2441318	1	// SPDX-License-Identifier: GPL-2.0
1da177e4 LT	2	/*
	3	* linux/fs/hfsplus/brec.c
	4	*
	5	* Copyright (C) 2001
	6	* Brad Boyer (flar@allandria.com)
	7	* (C) 2003 Ardis Technologies <roman@ardistech.com>
	8	*
	9	* Handle individual btree records
	10	*/
	11
	12	#include "hfsplus_fs.h"
	13	#include "hfsplus_raw.h"
	14
	15	static struct hfs_bnode hfs_bnode_split(struct hfs_find_data fd);
	16	static int hfs_brec_update_parent(struct hfs_find_data *fd);
	17	static int hfs_btree_inc_height(struct hfs_btree *);
	18
	19	/* Get the length and offset of the given record in the given node */
	20	u16 hfs_brec_lenoff(struct hfs_bnode node, u16 rec, u16 off)
	21	{
	22	__be16 retval[2];
	23	u16 dataoff;
	24
	25	dataoff = node->tree->node_size - (rec + 2) * 2;
	26	hfs_bnode_read(node, retval, dataoff, 4);
	27	*off = be16_to_cpu(retval[1]);
	28	return be16_to_cpu(retval[0]) - *off;
	29	}
	30
	31	/* Get the length of the key from a keyed record */
	32	u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
	33	{
	34	u16 retval, recoff;
	35
	36	if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
	37	return 0;
	38
	39	if ((node->type == HFS_NODE_INDEX) &&
324ef39a VD	40	!(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
324ef39a VD	41	(node->tree->cnid != HFSPLUS_ATTR_CNID)) {
1da177e4 LT	42	retval = node->tree->max_key_len + 2;
1da177e4 LT	43	} else {
2753cc28 AS	44	recoff = hfs_bnode_read_u16(node,
2753cc28 AS	45	node->tree->node_size - (rec + 1) * 2);
1da177e4 LT	46	if (!recoff)
1da177e4 LT	47	return 0;
aac4e419	48	if (recoff > node->tree->node_size - 2) {
d6142673	49	pr_err("recoff %d too large\n", recoff);
aac4e419 NA	50	return 0;
aac4e419 NA	51	}
13571a69 CH	52
	53	retval = hfs_bnode_read_u16(node, recoff) + 2;
	54	if (retval > node->tree->max_key_len + 2) {
d6142673	55	pr_err("keylen %d too large\n",
13571a69 CH	56	retval);
13571a69 CH	57	retval = 0;
9250f925	58	}
1da177e4 LT	59	}
	60	return retval;
	61	}
	62
	63	int hfs_brec_insert(struct hfs_find_data fd, void entry, int entry_len)
	64	{
	65	struct hfs_btree *tree;
	66	struct hfs_bnode node, new_node;
	67	int size, key_len, rec;
	68	int data_off, end_off;
	69	int idx_rec_off, data_rec_off, end_rec_off;
	70	__be32 cnid;
	71
	72	tree = fd->tree;
	73	if (!fd->bnode) {
	74	if (!tree->root)
	75	hfs_btree_inc_height(tree);
	76	fd->bnode = hfs_bnode_find(tree, tree->leaf_head);
	77	if (IS_ERR(fd->bnode))
	78	return PTR_ERR(fd->bnode);
	79	fd->record = -1;
	80	}
	81	new_node = NULL;
	82	key_len = be16_to_cpu(fd->search_key->key_len) + 2;
	83	again:
	84	/* new record idx and complete record size */
	85	rec = fd->record + 1;
	86	size = key_len + entry_len;
	87
	88	node = fd->bnode;
	89	hfs_bnode_dump(node);
	90	/* get last offset */
	91	end_rec_off = tree->node_size - (node->num_recs + 1) * 2;
	92	end_off = hfs_bnode_read_u16(node, end_rec_off);
	93	end_rec_off -= 2;
c2b3e1f7	94	hfs_dbg(BNODE_MOD, "insert_rec: %d, %d, %d, %d\n",
2753cc28	95	rec, size, end_off, end_rec_off);
1da177e4 LT	96	if (size > end_rec_off - end_off) {
	97	if (new_node)
	98	panic("not enough room!\n");
	99	new_node = hfs_bnode_split(fd);
	100	if (IS_ERR(new_node))
	101	return PTR_ERR(new_node);
	102	goto again;
	103	}
	104	if (node->type == HFS_NODE_LEAF) {
	105	tree->leaf_count++;
	106	mark_inode_dirty(tree->inode);
	107	}
	108	node->num_recs++;
	109	/* write new last offset */
2753cc28 AS	110	hfs_bnode_write_u16(node,
	111	offsetof(struct hfs_bnode_desc, num_recs),
	112	node->num_recs);
1da177e4 LT	113	hfs_bnode_write_u16(node, end_rec_off, end_off + size);
	114	data_off = end_off;
	115	data_rec_off = end_rec_off + 2;
	116	idx_rec_off = tree->node_size - (rec + 1) * 2;
	117	if (idx_rec_off == data_rec_off)
	118	goto skip;
	119	/* move all following entries */
	120	do {
	121	data_off = hfs_bnode_read_u16(node, data_rec_off + 2);
	122	hfs_bnode_write_u16(node, data_rec_off, data_off + size);
	123	data_rec_off += 2;
	124	} while (data_rec_off < idx_rec_off);
	125
	126	/* move data away */
	127	hfs_bnode_move(node, data_off + size, data_off,
	128	end_off - data_off);
	129
	130	skip:
	131	hfs_bnode_write(node, fd->search_key, data_off, key_len);
	132	hfs_bnode_write(node, entry, data_off + key_len, entry_len);
	133	hfs_bnode_dump(node);
	134
98cf21c6 SA	135	/*
	136	* update parent key if we inserted a key
	137	* at the start of the node and it is not the new node
	138	*/
	139	if (!rec && new_node != node) {
	140	hfs_bnode_read_key(node, fd->search_key, data_off + size);
	141	hfs_brec_update_parent(fd);
	142	}
1da177e4	143
98cf21c6	144	if (new_node) {
1da177e4 LT	145	hfs_bnode_put(fd->bnode);
	146	if (!new_node->parent) {
	147	hfs_btree_inc_height(tree);
	148	new_node->parent = tree->root;
	149	}
	150	fd->bnode = hfs_bnode_find(tree, new_node->parent);
	151
	152	/* create index data entry */
	153	cnid = cpu_to_be32(new_node->this);
	154	entry = &cnid;
	155	entry_len = sizeof(cnid);
	156
	157	/* get index key */
	158	hfs_bnode_read_key(new_node, fd->search_key, 14);
324ef39a	159	__hfs_brec_find(fd->bnode, fd, hfs_find_rec_by_key);
1da177e4 LT	160
	161	hfs_bnode_put(new_node);
	162	new_node = NULL;
	163
324ef39a VD	164	if ((tree->attributes & HFS_TREE_VARIDXKEYS) \|\|
324ef39a VD	165	(tree->cnid == HFSPLUS_ATTR_CNID))
1da177e4 LT	166	key_len = be16_to_cpu(fd->search_key->key_len) + 2;
1da177e4 LT	167	else {
2753cc28 AS	168	fd->search_key->key_len =
2753cc28 AS	169	cpu_to_be16(tree->max_key_len);
1da177e4 LT	170	key_len = tree->max_key_len + 2;
	171	}
	172	goto again;
	173	}
	174
1da177e4 LT	175	return 0;
	176	}
	177
	178	int hfs_brec_remove(struct hfs_find_data *fd)
	179	{
	180	struct hfs_btree *tree;
	181	struct hfs_bnode node, parent;
	182	int end_off, rec_off, data_off, size;
	183
	184	tree = fd->tree;
	185	node = fd->bnode;
	186	again:
	187	rec_off = tree->node_size - (fd->record + 2) * 2;
	188	end_off = tree->node_size - (node->num_recs + 1) * 2;
	189
	190	if (node->type == HFS_NODE_LEAF) {
	191	tree->leaf_count--;
	192	mark_inode_dirty(tree->inode);
	193	}
	194	hfs_bnode_dump(node);
c2b3e1f7	195	hfs_dbg(BNODE_MOD, "remove_rec: %d, %d\n",
2753cc28	196	fd->record, fd->keylength + fd->entrylength);
1da177e4 LT	197	if (!--node->num_recs) {
	198	hfs_bnode_unlink(node);
	199	if (!node->parent)
	200	return 0;
	201	parent = hfs_bnode_find(tree, node->parent);
	202	if (IS_ERR(parent))
	203	return PTR_ERR(parent);
	204	hfs_bnode_put(node);
	205	node = fd->bnode = parent;
	206
324ef39a	207	__hfs_brec_find(node, fd, hfs_find_rec_by_key);
1da177e4 LT	208	goto again;
1da177e4 LT	209	}
2753cc28 AS	210	hfs_bnode_write_u16(node,
	211	offsetof(struct hfs_bnode_desc, num_recs),
	212	node->num_recs);
1da177e4 LT	213
	214	if (rec_off == end_off)
	215	goto skip;
	216	size = fd->keylength + fd->entrylength;
	217
	218	do {
	219	data_off = hfs_bnode_read_u16(node, rec_off);
	220	hfs_bnode_write_u16(node, rec_off + 2, data_off - size);
	221	rec_off -= 2;
	222	} while (rec_off >= end_off);
	223
	224	/* fill hole */
	225	hfs_bnode_move(node, fd->keyoffset, fd->keyoffset + size,
	226	data_off - fd->keyoffset - size);
	227	skip:
	228	hfs_bnode_dump(node);
	229	if (!fd->record)
	230	hfs_brec_update_parent(fd);
	231	return 0;
	232	}
	233
	234	static struct hfs_bnode hfs_bnode_split(struct hfs_find_data fd)
	235	{
	236	struct hfs_btree *tree;
b6b41424	237	struct hfs_bnode node, new_node, *next_node;
1da177e4 LT	238	struct hfs_bnode_desc node_desc;
	239	int num_recs, new_rec_off, new_off, old_rec_off;
	240	int data_start, data_end, size;
	241
	242	tree = fd->tree;
	243	node = fd->bnode;
	244	new_node = hfs_bmap_alloc(tree);
	245	if (IS_ERR(new_node))
	246	return new_node;
	247	hfs_bnode_get(node);
c2b3e1f7	248	hfs_dbg(BNODE_MOD, "split_nodes: %d - %d - %d\n",
1da177e4 LT	249	node->this, new_node->this, node->next);
	250	new_node->next = node->next;
	251	new_node->prev = node->this;
	252	new_node->parent = node->parent;
	253	new_node->type = node->type;
	254	new_node->height = node->height;
	255
b6b41424 AV	256	if (node->next)
	257	next_node = hfs_bnode_find(tree, node->next);
	258	else
	259	next_node = NULL;
	260
	261	if (IS_ERR(next_node)) {
	262	hfs_bnode_put(node);
	263	hfs_bnode_put(new_node);
	264	return next_node;
	265	}
	266
1da177e4 LT	267	size = tree->node_size / 2 - node->num_recs * 2 - 14;
	268	old_rec_off = tree->node_size - 4;
	269	num_recs = 1;
	270	for (;;) {
	271	data_start = hfs_bnode_read_u16(node, old_rec_off);
	272	if (data_start > size)
	273	break;
	274	old_rec_off -= 2;
	275	if (++num_recs < node->num_recs)
	276	continue;
	277	/* panic? */
	278	hfs_bnode_put(node);
	279	hfs_bnode_put(new_node);
b6b41424 AV	280	if (next_node)
b6b41424 AV	281	hfs_bnode_put(next_node);
1da177e4 LT	282	return ERR_PTR(-ENOSPC);
	283	}
	284
	285	if (fd->record + 1 < num_recs) {
	286	/* new record is in the lower half,
	287	* so leave some more space there
	288	*/
	289	old_rec_off += 2;
	290	num_recs--;
	291	data_start = hfs_bnode_read_u16(node, old_rec_off);
	292	} else {
	293	hfs_bnode_put(node);
	294	hfs_bnode_get(new_node);
	295	fd->bnode = new_node;
	296	fd->record -= num_recs;
	297	fd->keyoffset -= data_start - 14;
	298	fd->entryoffset -= data_start - 14;
	299	}
	300	new_node->num_recs = node->num_recs - num_recs;
	301	node->num_recs = num_recs;
	302
	303	new_rec_off = tree->node_size - 2;
	304	new_off = 14;
	305	size = data_start - new_off;
	306	num_recs = new_node->num_recs;
	307	data_end = data_start;
	308	while (num_recs) {
	309	hfs_bnode_write_u16(new_node, new_rec_off, new_off);
	310	old_rec_off -= 2;
	311	new_rec_off -= 2;
	312	data_end = hfs_bnode_read_u16(node, old_rec_off);
	313	new_off = data_end - size;
	314	num_recs--;
	315	}
	316	hfs_bnode_write_u16(new_node, new_rec_off, new_off);
	317	hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start);
	318
	319	/* update new bnode header */
	320	node_desc.next = cpu_to_be32(new_node->next);
	321	node_desc.prev = cpu_to_be32(new_node->prev);
	322	node_desc.type = new_node->type;
	323	node_desc.height = new_node->height;
	324	node_desc.num_recs = cpu_to_be16(new_node->num_recs);
	325	node_desc.reserved = 0;
	326	hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
	327
	328	/* update previous bnode header */
	329	node->next = new_node->this;
	330	hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc));
	331	node_desc.next = cpu_to_be32(node->next);
	332	node_desc.num_recs = cpu_to_be16(node->num_recs);
	333	hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc));
	334
	335	/* update next bnode header */
b6b41424	336	if (next_node) {
1da177e4 LT	337	next_node->prev = new_node->this;
	338	hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc));
	339	node_desc.prev = cpu_to_be32(next_node->prev);
	340	hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc));
	341	hfs_bnode_put(next_node);
	342	} else if (node->this == tree->leaf_tail) {
	343	/* if there is no next node, this might be the new tail */
	344	tree->leaf_tail = new_node->this;
	345	mark_inode_dirty(tree->inode);
	346	}
	347
	348	hfs_bnode_dump(node);
	349	hfs_bnode_dump(new_node);
	350	hfs_bnode_put(node);
	351
	352	return new_node;
	353	}
	354
	355	static int hfs_brec_update_parent(struct hfs_find_data *fd)
	356	{
	357	struct hfs_btree *tree;
	358	struct hfs_bnode node, new_node, *parent;
	359	int newkeylen, diff;
	360	int rec, rec_off, end_rec_off;
	361	int start_off, end_off;
	362
	363	tree = fd->tree;
	364	node = fd->bnode;
	365	new_node = NULL;
	366	if (!node->parent)
	367	return 0;
	368
	369	again:
	370	parent = hfs_bnode_find(tree, node->parent);
	371	if (IS_ERR(parent))
	372	return PTR_ERR(parent);
324ef39a	373	__hfs_brec_find(parent, fd, hfs_find_rec_by_key);
98cf21c6 SA	374	if (fd->record < 0)
98cf21c6 SA	375	return -ENOENT;
1da177e4 LT	376	hfs_bnode_dump(parent);
	377	rec = fd->record;
	378
	379	/* size difference between old and new key */
324ef39a VD	380	if ((tree->attributes & HFS_TREE_VARIDXKEYS) \|\|
324ef39a VD	381	(tree->cnid == HFSPLUS_ATTR_CNID))
1da177e4 LT	382	newkeylen = hfs_bnode_read_u16(node, 14) + 2;
	383	else
	384	fd->keylength = newkeylen = tree->max_key_len + 2;
c2b3e1f7	385	hfs_dbg(BNODE_MOD, "update_rec: %d, %d, %d\n",
2753cc28	386	rec, fd->keylength, newkeylen);
1da177e4 LT	387
	388	rec_off = tree->node_size - (rec + 2) * 2;
	389	end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
	390	diff = newkeylen - fd->keylength;
	391	if (!diff)
	392	goto skip;
	393	if (diff > 0) {
	394	end_off = hfs_bnode_read_u16(parent, end_rec_off);
	395	if (end_rec_off - end_off < diff) {
	396
c2b3e1f7	397	hfs_dbg(BNODE_MOD, "splitting index node\n");
1da177e4 LT	398	fd->bnode = parent;
	399	new_node = hfs_bnode_split(fd);
	400	if (IS_ERR(new_node))
	401	return PTR_ERR(new_node);
	402	parent = fd->bnode;
	403	rec = fd->record;
	404	rec_off = tree->node_size - (rec + 2) * 2;
2753cc28 AS	405	end_rec_off = tree->node_size -
2753cc28 AS	406	(parent->num_recs + 1) * 2;
1da177e4 LT	407	}
	408	}
	409
	410	end_off = start_off = hfs_bnode_read_u16(parent, rec_off);
	411	hfs_bnode_write_u16(parent, rec_off, start_off + diff);
	412	start_off -= 4; /* move previous cnid too */
	413
	414	while (rec_off > end_rec_off) {
	415	rec_off -= 2;
	416	end_off = hfs_bnode_read_u16(parent, rec_off);
	417	hfs_bnode_write_u16(parent, rec_off, end_off + diff);
	418	}
	419	hfs_bnode_move(parent, start_off + diff, start_off,
	420	end_off - start_off);
	421	skip:
	422	hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen);
	423	hfs_bnode_dump(parent);
	424
	425	hfs_bnode_put(node);
	426	node = parent;
	427
	428	if (new_node) {
	429	__be32 cnid;
	430
	431	fd->bnode = hfs_bnode_find(tree, new_node->parent);
	432	/* create index key and entry */
	433	hfs_bnode_read_key(new_node, fd->search_key, 14);
	434	cnid = cpu_to_be32(new_node->this);
	435
324ef39a	436	__hfs_brec_find(fd->bnode, fd, hfs_find_rec_by_key);
1da177e4 LT	437	hfs_brec_insert(fd, &cnid, sizeof(cnid));
	438	hfs_bnode_put(fd->bnode);
	439	hfs_bnode_put(new_node);
	440
	441	if (!rec) {
	442	if (new_node == node)
	443	goto out;
	444	/* restore search_key */
	445	hfs_bnode_read_key(node, fd->search_key, 14);
	446	}
	447	}
	448
	449	if (!rec && node->parent)
	450	goto again;
	451	out:
	452	fd->bnode = node;
	453	return 0;
	454	}
	455
	456	static int hfs_btree_inc_height(struct hfs_btree *tree)
	457	{
	458	struct hfs_bnode node, new_node;
	459	struct hfs_bnode_desc node_desc;
	460	int key_size, rec;
	461	__be32 cnid;
	462
	463	node = NULL;
	464	if (tree->root) {
	465	node = hfs_bnode_find(tree, tree->root);
	466	if (IS_ERR(node))
	467	return PTR_ERR(node);
	468	}
	469	new_node = hfs_bmap_alloc(tree);
	470	if (IS_ERR(new_node)) {
	471	hfs_bnode_put(node);
	472	return PTR_ERR(new_node);
	473	}
	474
	475	tree->root = new_node->this;
	476	if (!tree->depth) {
	477	tree->leaf_head = tree->leaf_tail = new_node->this;
	478	new_node->type = HFS_NODE_LEAF;
	479	new_node->num_recs = 0;
	480	} else {
	481	new_node->type = HFS_NODE_INDEX;
	482	new_node->num_recs = 1;
	483	}
	484	new_node->parent = 0;
	485	new_node->next = 0;
	486	new_node->prev = 0;
	487	new_node->height = ++tree->depth;
	488
	489	node_desc.next = cpu_to_be32(new_node->next);
	490	node_desc.prev = cpu_to_be32(new_node->prev);
	491	node_desc.type = new_node->type;
	492	node_desc.height = new_node->height;
	493	node_desc.num_recs = cpu_to_be16(new_node->num_recs);
	494	node_desc.reserved = 0;
	495	hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
	496
	497	rec = tree->node_size - 2;
	498	hfs_bnode_write_u16(new_node, rec, 14);
	499
	500	if (node) {
501	/* insert old root idx into new root */
502	node->parent = tree->root;
503	if (node->type == HFS_NODE_LEAF \|\|
324ef39a VD	504	tree->attributes & HFS_TREE_VARIDXKEYS \|\|
324ef39a VD	505	tree->cnid == HFSPLUS_ATTR_CNID)
1da177e4 LT	506	key_size = hfs_bnode_read_u16(node, 14) + 2;
	507	else
	508	key_size = tree->max_key_len + 2;
	509	hfs_bnode_copy(new_node, 14, node, 14, key_size);
	510
324ef39a VD	511	if (!(tree->attributes & HFS_TREE_VARIDXKEYS) &&
324ef39a VD	512	(tree->cnid != HFSPLUS_ATTR_CNID)) {
1da177e4 LT	513	key_size = tree->max_key_len + 2;
	514	hfs_bnode_write_u16(new_node, 14, tree->max_key_len);
	515	}
	516	cnid = cpu_to_be32(node->this);
	517	hfs_bnode_write(new_node, &cnid, 14 + key_size, 4);
	518
	519	rec -= 2;
	520	hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4);
	521
	522	hfs_bnode_put(node);
	523	}
	524	hfs_bnode_put(new_node);
	525	mark_inode_dirty(tree->inode);
	526
	527	return 0;
	528	}