[linux.git] / fs / hfs / brec.c

/*
 *  linux/fs/hfs/brec.c
 *
 * Copyright (C) 2001
 * Brad Boyer ([email protected])
 * (C) 2003 Ardis Technologies <[email protected]>
 *
 * Handle individual btree records
 */

#include "btree.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 *tree);

/* 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)) {
		if (node->tree->attributes & HFS_TREE_BIGKEYS)
			retval = node->tree->max_key_len + 2;
		else
			retval = node->tree->max_key_len + 1;
	} else {
		recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2);
		if (!recoff)
			return 0;
		if (node->tree->attributes & HFS_TREE_BIGKEYS) {
			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;
			}
		} else {
			retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1;
			if (retval > node->tree->max_key_len + 1) {
				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 = (fd->search_key->key_len | 1) + 1;
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_bnode_put(new_node);
		new_node = NULL;

		if (tree->attributes & HFS_TREE_VARIDXKEYS)
			key_len = fd->search_key->key_len + 1;
		else {
			fd->search_key->key_len = tree->max_key_len;
			key_len = tree->max_key_len + 1;
		}
		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);
		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);
	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)
		newkeylen = (hfs_bnode_read_u8(node, 14) | 1) + 1;
	else
		fd->keylength = newkeylen = tree->max_key_len + 1;
	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) {

			printk(KERN_DEBUG "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);
	if (!(tree->attributes & HFS_TREE_VARIDXKEYS))
		hfs_bnode_write_u8(parent, fd->keyoffset, newkeylen - 1);
	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_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)
			key_size = hfs_bnode_read_u8(node, 14) + 1;
		else
			key_size = tree->max_key_len + 1;
		hfs_bnode_copy(new_node, 14, node, 14, key_size);

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