1 /*
2  *  linux/fs/hfsplus/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 "hfsplus_fs.h"
13 
14 /* Find the record in bnode that best matches key (not greater than...)*/
hfsplus_find_rec(hfsplus_bnode * bnode,struct hfsplus_find_data * fd)15 void hfsplus_find_rec(hfsplus_bnode *bnode, struct hfsplus_find_data *fd)
16 {
17 	int cmpval;
18 	u16 off, len, keylen;
19 	int rec;
20 	int b, e;
21 
22 	b = 0;
23 	e = bnode->num_recs - 1;
24 	do {
25 		rec = (e + b) / 2;
26 		len = hfsplus_brec_lenoff(bnode, rec, &off);
27 		keylen = hfsplus_brec_keylen(bnode, rec);
28 		hfsplus_bnode_readbytes(bnode, fd->key, off, keylen);
29 		cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
30 		if (!cmpval) {
31 			fd->exact = 1;
32 			e = rec;
33 			break;
34 		}
35 		if (cmpval < 0)
36 			b = rec + 1;
37 		else
38 			e = rec - 1;
39 	} while (b <= e);
40 	//printk("%d: %d,%d,%d\n", bnode->this, b, e, rec);
41 	if (rec != e && e >= 0) {
42 		len = hfsplus_brec_lenoff(bnode, e, &off);
43 		keylen = hfsplus_brec_keylen(bnode, e);
44 		hfsplus_bnode_readbytes(bnode, fd->key, off, keylen);
45 	}
46 	fd->record = e;
47 	fd->keyoffset = off;
48 	fd->keylength = keylen;
49 	fd->entryoffset = off + keylen;
50 	fd->entrylength = len - keylen;
51 }
52 
53 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
54 /* Return allocated copy of node found, set recnum to best record */
hfsplus_btree_find(struct hfsplus_find_data * fd)55 int hfsplus_btree_find(struct hfsplus_find_data *fd)
56 {
57 	hfsplus_btree *tree;
58 	hfsplus_bnode *bnode;
59 	u32 data, nidx, parent;
60 	int height, err;
61 
62 	tree = fd->tree;
63 	if (fd->bnode)
64 		hfsplus_put_bnode(fd->bnode);
65 	fd->bnode = NULL;
66 	fd->exact = 0;
67 	nidx = tree->root;
68 	if (!nidx)
69 		return -ENOENT;
70 	height = tree->depth;
71 	err = 0;
72 	parent = 0;
73 	for (;;) {
74 		bnode = hfsplus_find_bnode(tree, nidx);
75 		if (!bnode) {
76 			err = -EIO;
77 			break;
78 		}
79 		if (bnode->height != height)
80 			goto invalid;
81 		if (bnode->kind != (--height ? HFSPLUS_NODE_NDX : HFSPLUS_NODE_LEAF))
82 			goto invalid;
83 		bnode->parent = parent;
84 
85 		hfsplus_find_rec(bnode, fd);
86 		if (fd->record < 0) {
87 			err = -ENOENT;
88 			goto release;
89 		}
90 		if (!height) {
91 			if (!fd->exact)
92 				err = -ENOENT;
93 			break;
94 		}
95 
96 		parent = nidx;
97 		hfsplus_bnode_readbytes(bnode, &data, fd->entryoffset, 4);
98 		nidx = be32_to_cpu(data);
99 		hfsplus_put_bnode(bnode);
100 	}
101 	fd->bnode = bnode;
102 	return err;
103 
104 invalid:
105 	printk("HFS+-fs: inconsistency in B*Tree\n");
106 	err = -EIO;
107 release:
108 	hfsplus_put_bnode(bnode);
109 	return err;
110 }
111 
hfsplus_btree_find_entry(struct hfsplus_find_data * fd,void * entry,int entry_len)112 int hfsplus_btree_find_entry(struct hfsplus_find_data *fd,
113 			     void *entry, int entry_len)
114 {
115 	int res;
116 
117 	res = hfsplus_btree_find(fd);
118 	if (res)
119 		return res;
120 	if (fd->entrylength > entry_len)
121 		return -EINVAL;
122 	hfsplus_bnode_readbytes(fd->bnode, entry, fd->entryoffset, fd->entrylength);
123 	return 0;
124 }
125 
hfsplus_btree_move(struct hfsplus_find_data * fd,int cnt)126 int hfsplus_btree_move(struct hfsplus_find_data *fd, int cnt)
127 {
128 	struct hfsplus_btree *tree;
129 	hfsplus_bnode *bnode;
130 	int idx, res = 0;
131 	u16 off, len, keylen;
132 
133 	bnode = fd->bnode;
134 	tree = bnode->tree;
135 
136 	if (cnt < -0xFFFF || cnt > 0xFFFF)
137 		return -EINVAL;
138 
139 	if (cnt < 0) {
140 		cnt = -cnt;
141 		while (cnt > fd->record) {
142 			cnt -= fd->record + 1;
143 			fd->record = bnode->num_recs - 1;
144 			idx = bnode->prev;
145 			if (!idx) {
146 				res = -ENOENT;
147 				goto out;
148 			}
149 			hfsplus_put_bnode(bnode);
150 			bnode = hfsplus_find_bnode(tree, idx);
151 			if (!bnode) {
152 				res = -EIO;
153 				goto out;
154 			}
155 		}
156 		fd->record -= cnt;
157 	} else {
158 		while (cnt >= bnode->num_recs - fd->record) {
159 			cnt -= bnode->num_recs - fd->record;
160 			fd->record = 0;
161 			idx = bnode->next;
162 			if (!idx) {
163 				res = -ENOENT;
164 				goto out;
165 			}
166 			hfsplus_put_bnode(bnode);
167 			bnode = hfsplus_find_bnode(tree, idx);
168 			if (!bnode) {
169 				res = -EIO;
170 				goto out;
171 			}
172 		}
173 		fd->record += cnt;
174 	}
175 
176 	len = hfsplus_brec_lenoff(bnode, fd->record, &off);
177 	keylen = hfsplus_brec_keylen(bnode, fd->record);
178 	fd->keyoffset = off;
179 	fd->keylength = keylen;
180 	fd->entryoffset = off + keylen;
181 	fd->entrylength = len - keylen;
182 	hfsplus_bnode_readbytes(bnode, fd->key, off, keylen);
183 out:
184 	fd->bnode = bnode;
185 	return res;
186 }
187 
hfsplus_find_init(hfsplus_btree * tree,struct hfsplus_find_data * fd)188 int hfsplus_find_init(hfsplus_btree *tree, struct hfsplus_find_data *fd)
189 {
190 	fd->tree = tree;
191 	fd->bnode = NULL;
192 	fd->search_key = kmalloc(tree->max_key_len + 2, GFP_KERNEL);
193 	if (!fd->search_key)
194 		return -ENOMEM;
195 	fd->key = kmalloc(tree->max_key_len + 2, GFP_KERNEL);
196 	if (!fd->key) {
197 		kfree(fd->search_key);
198 		return -ENOMEM;
199 	}
200 	dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0));
201 	down(&tree->tree_lock);
202 	return 0;
203 }
204 
hfsplus_find_exit(struct hfsplus_find_data * fd)205 void hfsplus_find_exit(struct hfsplus_find_data *fd)
206 {
207 	hfsplus_put_bnode(fd->bnode);
208 	kfree(fd->search_key);
209 	kfree(fd->key);
210 	dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0));
211 	up(&fd->tree->tree_lock);
212 	fd->tree = NULL;
213 }
214