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

/*
 *  linux/fs/hfsplus/brec.c
 *
 * Copyright (C) 2001
 * Brad Boyer ([email protected])
 * (C) 2003 Ardis Technologies <[email protected]>
 *
 * 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)) {
		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 (node->tree->attributes & HFS_TREE_BIGKEYS)
			retval = hfs_bnode_read_u16(node, recoff) + 2;
		else
			retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1;
	}
	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;
	dprint(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);

	if (new_node) {
		/* update parent key if we inserted a key
		 * at the start of the first node
		 */
		if (!rec && new_node != node)
			hfs_brec_update_parent(fd);

		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 = 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;
	}

	if (!rec)
		hfs_brec_update_parent(fd);

	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);
	dprint(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;
	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);
	dprint(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;

	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);
		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 (new_node->next) {
		struct hfs_bnode *next_node = hfs_bnode_find(tree, new_node->next);
		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_bnode_dump(parent);
	rec = fd->record;

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