[mirror_ubuntu-bionic-kernel.git] / fs / hfs / bfind.c

/*
 *  linux/fs/hfs/bfind.c
 *
 * Copyright (C) 2001
 * Brad Boyer (flar@allandria.com)
 * (C) 2003 Ardis Technologies <roman@ardistech.com>
 *
 * Search routines for btrees
 */

#include <linux/slab.h>
#include "btree.h"

int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
{
	void *ptr;

	fd->tree = tree;
	fd->bnode = NULL;
	ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
	if (!ptr)
		return -ENOMEM;
	fd->search_key = ptr;
	fd->key = ptr + tree->max_key_len + 2;
	dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0));
	down(&tree->tree_lock);
	return 0;
}

void hfs_find_exit(struct hfs_find_data *fd)
{
	hfs_bnode_put(fd->bnode);
	kfree(fd->search_key);
	dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0));
	up(&fd->tree->tree_lock);
	fd->tree = NULL;
}

/* Find the record in bnode that best matches key (not greater than...)*/
int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
{
	int cmpval;
	u16 off, len, keylen;
	int rec;
	int b, e;
	int res;

	b = 0;
	e = bnode->num_recs - 1;
	res = -ENOENT;
	do {
		rec = (e + b) / 2;
		len = hfs_brec_lenoff(bnode, rec, &off);
		keylen = hfs_brec_keylen(bnode, rec);
		if (keylen == 0) {
			res = -EINVAL;
			goto fail;
		}
		hfs_bnode_read(bnode, fd->key, off, keylen);
		cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
		if (!cmpval) {
			e = rec;
			res = 0;
			goto done;
		}
		if (cmpval < 0)
			b = rec + 1;
		else
			e = rec - 1;
	} while (b <= e);
	if (rec != e && e >= 0) {
		len = hfs_brec_lenoff(bnode, e, &off);
		keylen = hfs_brec_keylen(bnode, e);
		if (keylen == 0) {
			res = -EINVAL;
			goto fail;
		}
		hfs_bnode_read(bnode, fd->key, off, keylen);
	}
done:
	fd->record = e;
	fd->keyoffset = off;
	fd->keylength = keylen;
	fd->entryoffset = off + keylen;
	fd->entrylength = len - keylen;
fail:
	return res;
}

/* Traverse a B*Tree from the root to a leaf finding best fit to key */
/* Return allocated copy of node found, set recnum to best record */
int hfs_brec_find(struct hfs_find_data *fd)
{
	struct hfs_btree *tree;
	struct hfs_bnode *bnode;
	u32 nidx, parent;
	__be32 data;
	int height, res;

	tree = fd->tree;
	if (fd->bnode)
		hfs_bnode_put(fd->bnode);
	fd->bnode = NULL;
	nidx = tree->root;
	if (!nidx)
		return -ENOENT;
	height = tree->depth;
	res = 0;
	parent = 0;
	for (;;) {
		bnode = hfs_bnode_find(tree, nidx);
		if (IS_ERR(bnode)) {
			res = PTR_ERR(bnode);
			bnode = NULL;
			break;
		}
		if (bnode->height != height)
			goto invalid;
		if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
			goto invalid;
		bnode->parent = parent;

		res = __hfs_brec_find(bnode, fd);
		if (!height)
			break;
		if (fd->record < 0)
			goto release;

		parent = nidx;
		hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
		nidx = be32_to_cpu(data);
		hfs_bnode_put(bnode);
	}
	fd->bnode = bnode;
	return res;

invalid:
	printk(KERN_ERR "hfs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
		height, bnode->height, bnode->type, nidx, parent);
	res = -EIO;
release:
	hfs_bnode_put(bnode);
	return res;
}

int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
{
	int res;

	res = hfs_brec_find(fd);
	if (res)
		return res;
	if (fd->entrylength > rec_len)
		return -EINVAL;
	hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
	return 0;
}

int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
{
	struct hfs_btree *tree;
	struct hfs_bnode *bnode;
	int idx, res = 0;
	u16 off, len, keylen;

	bnode = fd->bnode;
	tree = bnode->tree;

	if (cnt < 0) {
		cnt = -cnt;
		while (cnt > fd->record) {
			cnt -= fd->record + 1;
			fd->record = bnode->num_recs - 1;
			idx = bnode->prev;
			if (!idx) {
				res = -ENOENT;
				goto out;
			}
			hfs_bnode_put(bnode);
			bnode = hfs_bnode_find(tree, idx);
			if (IS_ERR(bnode)) {
				res = PTR_ERR(bnode);
				bnode = NULL;
				goto out;
			}
		}
		fd->record -= cnt;
	} else {
		while (cnt >= bnode->num_recs - fd->record) {
			cnt -= bnode->num_recs - fd->record;
			fd->record = 0;
			idx = bnode->next;
			if (!idx) {
				res = -ENOENT;
				goto out;
			}
			hfs_bnode_put(bnode);
			bnode = hfs_bnode_find(tree, idx);
			if (IS_ERR(bnode)) {
				res = PTR_ERR(bnode);
				bnode = NULL;
				goto out;
			}
		}
		fd->record += cnt;
	}

	len = hfs_brec_lenoff(bnode, fd->record, &off);
	keylen = hfs_brec_keylen(bnode, fd->record);
	if (keylen == 0) {
		res = -EINVAL;
		goto out;
	}
	fd->keyoffset = off;
	fd->keylength = keylen;
	fd->entryoffset = off + keylen;
	fd->entrylength = len - keylen;
	hfs_bnode_read(bnode, fd->key, off, keylen);
out:
	fd->bnode = bnode;
	return res;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/hfs/bfind.c
	3	*
	4	* Copyright (C) 2001
	5	* Brad Boyer (flar@allandria.com)
	6	* (C) 2003 Ardis Technologies <roman@ardistech.com>
	7	*
	8	* Search routines for btrees
	9	*/
	10
	11	#include <linux/slab.h>
	12	#include "btree.h"
	13
	14	int hfs_find_init(struct hfs_btree tree, struct hfs_find_data fd)
	15	{
	16	void *ptr;
	17
	18	fd->tree = tree;
	19	fd->bnode = NULL;
	20	ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
	21	if (!ptr)
	22	return -ENOMEM;
	23	fd->search_key = ptr;
	24	fd->key = ptr + tree->max_key_len + 2;
	25	dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0));
	26	down(&tree->tree_lock);
	27	return 0;
	28	}
	29
	30	void hfs_find_exit(struct hfs_find_data *fd)
	31	{
	32	hfs_bnode_put(fd->bnode);
	33	kfree(fd->search_key);
	34	dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0));
	35	up(&fd->tree->tree_lock);
	36	fd->tree = NULL;
	37	}
	38
	39	/* Find the record in bnode that best matches key (not greater than...)*/
	40	int __hfs_brec_find(struct hfs_bnode bnode, struct hfs_find_data fd)
	41	{
	42	int cmpval;
	43	u16 off, len, keylen;
	44	int rec;
	45	int b, e;
	46	int res;
	47
	48	b = 0;
	49	e = bnode->num_recs - 1;
	50	res = -ENOENT;
	51	do {
	52	rec = (e + b) / 2;
	53	len = hfs_brec_lenoff(bnode, rec, &off);
	54	keylen = hfs_brec_keylen(bnode, rec);
55581d01	55	if (keylen == 0) {
cf059462	56	res = -EINVAL;
55581d01	57	goto fail;
cf059462	58	}
1da177e4 LT	59	hfs_bnode_read(bnode, fd->key, off, keylen);
	60	cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
	61	if (!cmpval) {
	62	e = rec;
	63	res = 0;
	64	goto done;
	65	}
	66	if (cmpval < 0)
	67	b = rec + 1;
	68	else
	69	e = rec - 1;
	70	} while (b <= e);
1da177e4 LT	71	if (rec != e && e >= 0) {
	72	len = hfs_brec_lenoff(bnode, e, &off);
	73	keylen = hfs_brec_keylen(bnode, e);
55581d01	74	if (keylen == 0) {
cf059462	75	res = -EINVAL;
55581d01	76	goto fail;
cf059462	77	}
1da177e4 LT	78	hfs_bnode_read(bnode, fd->key, off, keylen);
	79	}
	80	done:
	81	fd->record = e;
	82	fd->keyoffset = off;
	83	fd->keylength = keylen;
	84	fd->entryoffset = off + keylen;
	85	fd->entrylength = len - keylen;
55581d01	86	fail:
1da177e4 LT	87	return res;
	88	}
	89
	90	/* Traverse a BTree from the root to a leaf finding best fit to key /
	91	/* Return allocated copy of node found, set recnum to best record */
	92	int hfs_brec_find(struct hfs_find_data *fd)
	93	{
	94	struct hfs_btree *tree;
	95	struct hfs_bnode *bnode;
	96	u32 nidx, parent;
	97	__be32 data;
	98	int height, res;
	99
	100	tree = fd->tree;
	101	if (fd->bnode)
	102	hfs_bnode_put(fd->bnode);
	103	fd->bnode = NULL;
	104	nidx = tree->root;
	105	if (!nidx)
	106	return -ENOENT;
	107	height = tree->depth;
	108	res = 0;
	109	parent = 0;
	110	for (;;) {
	111	bnode = hfs_bnode_find(tree, nidx);
	112	if (IS_ERR(bnode)) {
	113	res = PTR_ERR(bnode);
	114	bnode = NULL;
	115	break;
	116	}
	117	if (bnode->height != height)
	118	goto invalid;
	119	if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
	120	goto invalid;
	121	bnode->parent = parent;
	122
	123	res = __hfs_brec_find(bnode, fd);
	124	if (!height)
	125	break;
	126	if (fd->record < 0)
	127	goto release;
	128
	129	parent = nidx;
	130	hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
	131	nidx = be32_to_cpu(data);
	132	hfs_bnode_put(bnode);
	133	}
	134	fd->bnode = bnode;
	135	return res;
	136
	137	invalid:
7cf3cc30	138	printk(KERN_ERR "hfs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
1da177e4 LT	139	height, bnode->height, bnode->type, nidx, parent);
	140	res = -EIO;
	141	release:
	142	hfs_bnode_put(bnode);
	143	return res;
	144	}
	145
	146	int hfs_brec_read(struct hfs_find_data fd, void rec, int rec_len)
	147	{
	148	int res;
	149
	150	res = hfs_brec_find(fd);
	151	if (res)
	152	return res;
	153	if (fd->entrylength > rec_len)
	154	return -EINVAL;
	155	hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
	156	return 0;
	157	}
	158
	159	int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
	160	{
	161	struct hfs_btree *tree;
	162	struct hfs_bnode *bnode;
	163	int idx, res = 0;
	164	u16 off, len, keylen;
	165
	166	bnode = fd->bnode;
	167	tree = bnode->tree;
	168
	169	if (cnt < 0) {
	170	cnt = -cnt;
	171	while (cnt > fd->record) {
	172	cnt -= fd->record + 1;
	173	fd->record = bnode->num_recs - 1;
	174	idx = bnode->prev;
	175	if (!idx) {
	176	res = -ENOENT;
	177	goto out;
	178	}
	179	hfs_bnode_put(bnode);
	180	bnode = hfs_bnode_find(tree, idx);
	181	if (IS_ERR(bnode)) {
	182	res = PTR_ERR(bnode);
	183	bnode = NULL;
	184	goto out;
	185	}
	186	}
	187	fd->record -= cnt;
	188	} else {
	189	while (cnt >= bnode->num_recs - fd->record) {
	190	cnt -= bnode->num_recs - fd->record;
	191	fd->record = 0;
	192	idx = bnode->next;
	193	if (!idx) {
	194	res = -ENOENT;
	195	goto out;
	196	}
	197	hfs_bnode_put(bnode);
	198	bnode = hfs_bnode_find(tree, idx);
	199	if (IS_ERR(bnode)) {
	200	res = PTR_ERR(bnode);
	201	bnode = NULL;
	202	goto out;
203	}
204	}
205	fd->record += cnt;
206	}
207
208	len = hfs_brec_lenoff(bnode, fd->record, &off);
209	keylen = hfs_brec_keylen(bnode, fd->record);
55581d01	210	if (keylen == 0) {
cf059462 ES	211	res = -EINVAL;
	212	goto out;
	213	}
1da177e4 LT	214	fd->keyoffset = off;
	215	fd->keylength = keylen;
	216	fd->entryoffset = off + keylen;
	217	fd->entrylength = len - keylen;
	218	hfs_bnode_read(bnode, fd->key, off, keylen);
	219	out:
	220	fd->bnode = bnode;
	221	return res;
	222	}