1
2
3
4
5
6
7
8
9
10
11#include <linux/slab.h>
12#include "hfsplus_fs.h"
13
14
15void 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
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
54
55int 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
104invalid:
105 printk("HFS+-fs: inconsistency in B*Tree\n");
106 err = -EIO;
107release:
108 hfsplus_put_bnode(bnode);
109 return err;
110}
111
112int 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
126int 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);
183out:
184 fd->bnode = bnode;
185 return res;
186}
187
188int 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
205void 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
