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