File: /usr/src/linux/fs/hfs/bfind.c
1 /*
2 * linux/fs/hfs/bfind.c
3 *
4 * Copyright (C) 1995, 1996 Paul H. Hargrove
5 * This file may be distributed under the terms of the GNU General Public License.
6 *
7 * This file contains the code to access records in a btree.
8 *
9 * "XXX" in a comment is a note to myself to consider changing something.
10 *
11 * In function preconditions the term "valid" applied to a pointer to
12 * a structure means that the pointer is non-NULL and the structure it
13 * points to has all fields initialized to consistent values.
14 */
15
16 #include "hfs_btree.h"
17
18 /*================ Global functions ================*/
19
20 /*
21 * hfs_brec_relse()
22 *
23 * Description:
24 * This function releases some of the nodes associated with a brec.
25 * Input Variable(s):
26 * struct hfs_brec *brec: pointer to the brec to release some nodes from.
27 * struct hfs_belem *elem: the last node to release or NULL for all
28 * Output Variable(s):
29 * NONE
30 * Returns:
31 * void
32 * Preconditions:
33 * 'brec' points to a "valid" (struct hfs_brec)
34 * Postconditions:
35 * All nodes between the indicated node and the beginning of the path
36 * are released.
37 */
38 void hfs_brec_relse(struct hfs_brec *brec, struct hfs_belem *elem)
39 {
40 if (!elem) {
41 elem = brec->bottom;
42 }
43
44 while (brec->top <= elem) {
45 hfs_bnode_relse(&brec->top->bnr);
46 ++brec->top;
47 }
48 }
49
50 /*
51 * hfs_bfind()
52 *
53 * Description:
54 * This function has sole responsibility for locating existing
55 * records in a B-tree. Given a B-tree and a key it locates the
56 * "greatest" record "less than or equal to" the given key. The
57 * exact behavior is determined by the bits of the flags variable as
58 * follows:
59 * ('flags' & HFS_LOCK_MASK):
60 * The lock_type argument to be used when calling hfs_bnode_find().
61 * HFS_BFIND_EXACT: only accept an exact match, otherwise take the
62 * "largest" record less than 'target' as a "match"
63 * HFS_BFIND_LOCK: request HFS_LOCK_WRITE access to the node containing
64 * the "matching" record when it is located
65 * HFS_BPATH_FIRST: keep access to internal nodes when accessing their
66 * first child.
67 * HFS_BPATH_OVERFLOW: keep access to internal nodes when the accessed
68 * child is too full to insert another pointer record.
69 * HFS_BPATH_UNDERFLOW: keep access to internal nodes when the accessed
70 * child is would be less than half full upon removing a pointer record.
71 * Input Variable(s):
72 * struct hfs_brec *brec: pointer to the (struct hfs_brec) to hold
73 * the search results.
74 * struct hfs_bkey *target: pointer to the (struct hfs_bkey)
75 * to search for
76 * int flags: bitwise OR of flags which determine the function's behavior
77 * Output Variable(s):
78 * 'brec' contains the results of the search on success or is invalid
79 * on failure.
80 * Returns:
81 * int: 0 or 1 on success or an error code on failure:
82 * -EINVAL: one of the input variables was NULL.
83 * -ENOENT: tree is valid but empty or no "matching" record was located.
84 * If the HFS_BFIND_EXACT bit of 'flags' is not set then the case of no
85 * matching record will give a 'brec' with a 'record' field of zero
86 * rather than returning this error.
87 * -EIO: an I/O operation or an assertion about the structure of a
88 * valid B-tree failed indicating corruption of either the B-tree
89 * structure on the disk or one of the in-core structures representing
90 * the B-tree.
91 * (This could also be returned if a kmalloc() call failed in a
92 * subordinate routine that is intended to get the data from the
93 * disk or the buffer cache.)
94 * Preconditions:
95 * 'brec' is NULL or points to a (struct hfs_brec) with a 'tree' field
96 * which points to a valid (struct hfs_btree).
97 * 'target' is NULL or points to a "valid" (struct hfs_bkey)
98 * Postconditions:
99 * If 'brec', 'brec->tree' or 'target' is NULL then -EINVAL is returned.
100 * If 'brec', 'brec->tree' and 'target' are non-NULL but the tree
101 * is empty then -ENOENT is returned.
102 * If 'brec', 'brec->tree' and 'target' are non-NULL but the call to
103 * hfs_brec_init() fails then '*brec' is NULL and -EIO is returned.
104 * If 'brec', 'brec->tree' and 'target' are non-NULL and the tree is
105 * non-empty then the tree is searched as follows:
106 * If any call to hfs_brec_next() fails or returns a node that is
107 * neither an index node nor a leaf node then -EIO is returned to
108 * indicate that the B-tree or buffer-cache are corrupted.
109 * If every record in the tree is "greater than" the given key
110 * and the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned.
111 * If every record in the tree is "greater than" the given key
112 * and the HFS_BFIND_EXACT bit of 'flags' is clear then 'brec' refers
113 * to the first leaf node in the tree and has a 'record' field of
114 * zero, and 1 is returned.
115 * If a "matching" record is located with key "equal to" 'target'
116 * then the return value is 0 and 'brec' indicates the record.
117 * If a "matching" record is located with key "greater than" 'target'
118 * then the behavior is determined as follows:
119 * If the HFS_BFIND_EXACT bit of 'flags' is not set then 1 is returned
120 * and 'brec' refers to the "matching" record.
121 * If the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned.
122 * If the return value is non-negative and the HFS_BFIND_LOCK bit of
123 * 'flags' is set then hfs_brec_lock() is called on the bottom element
124 * of 'brec' before returning.
125 */
126 int hfs_bfind(struct hfs_brec *brec, struct hfs_btree *tree,
127 const struct hfs_bkey *target, int flags)
128 {
129 struct hfs_belem *curr;
130 struct hfs_bkey *key;
131 struct hfs_bnode *bn;
132 int result, ntype;
133
134 /* check for invalid arguments */
135 if (!brec || (tree->magic != HFS_BTREE_MAGIC) || !target) {
136 return -EINVAL;
137 }
138
139 /* check for empty tree */
140 if (!tree->root || !tree->bthNRecs) {
141 return -ENOENT;
142 }
143
144 /* start search at root of tree */
145 if (!(curr = hfs_brec_init(brec, tree, flags))) {
146 return -EIO;
147 }
148
149 /* traverse the tree */
150 do {
151 bn = curr->bnr.bn;
152
153 if (!curr->record) {
154 hfs_warn("hfs_bfind: empty bnode\n");
155 hfs_brec_relse(brec, NULL);
156 return -EIO;
157 }
158
159 /* reverse linear search yielding largest key "less
160 than or equal to" 'target'.
161 It is questionable whether a binary search would be
162 significantly faster */
163 do {
164 key = belem_key(curr);
165 if (!key->KeyLen) {
166 hfs_warn("hfs_bfind: empty key\n");
167 hfs_brec_relse(brec, NULL);
168 return -EIO;
169 }
170 result = (tree->compare)(target, key);
171 } while ((result<0) && (--curr->record));
172
173 ntype = bn->ndType;
174
175 /* see if all keys > target */
176 if (!curr->record) {
177 if (bn->ndBLink) {
178 /* at a node other than the left-most at a
179 given level it means the parent had an
180 incorrect key for this child */
181 hfs_brec_relse(brec, NULL);
182 hfs_warn("hfs_bfind: corrupted b-tree %d.\n",
183 (int)ntohl(tree->entry.cnid));
184 return -EIO;
185 }
186 if (flags & HFS_BFIND_EXACT) {
187 /* we're not going to find it */
188 hfs_brec_relse(brec, NULL);
189 return -ENOENT;
190 }
191 if (ntype == ndIndxNode) {
192 /* since we are at the left-most node at
193 the current level and looking for the
194 predecessor of 'target' keep going down */
195 curr->record = 1;
196 } else {
197 /* we're at first leaf so fall through */
198 }
199 }
200
201 /* get next node if necessary */
202 if ((ntype == ndIndxNode) && !(curr = hfs_brec_next(brec))) {
203 return -EIO;
204 }
205 } while (ntype == ndIndxNode);
206
207 if (key->KeyLen > tree->bthKeyLen) {
208 hfs_warn("hfs_bfind: oversized key\n");
209 hfs_brec_relse(brec, NULL);
210 return -EIO;
211 }
212
213 if (ntype != ndLeafNode) {
214 hfs_warn("hfs_bfind: invalid node type %02x in node %d of "
215 "btree %d\n", bn->ndType, bn->node,
216 (int)ntohl(tree->entry.cnid));
217 hfs_brec_relse(brec, NULL);
218 return -EIO;
219 }
220
221 if ((flags & HFS_BFIND_EXACT) && result) {
222 hfs_brec_relse(brec, NULL);
223 return -ENOENT;
224 }
225
226 if (!(flags & HFS_BPATH_MASK)) {
227 hfs_brec_relse(brec, brec->bottom-1);
228 }
229
230 if (flags & HFS_BFIND_LOCK) {
231 hfs_brec_lock(brec, brec->bottom);
232 }
233
234 brec->key = brec_key(brec);
235 brec->data = bkey_record(brec->key);
236
237 return result ? 1 : 0;
238 }
239
240 /*
241 * hfs_bsucc()
242 *
243 * Description:
244 * This function overwrites '*brec' with its successor in the B-tree,
245 * obtaining the same type of access.
246 * Input Variable(s):
247 * struct hfs_brec *brec: address of the (struct hfs_brec) to overwrite
248 * with its successor
249 * Output Variable(s):
250 * struct hfs_brec *brec: address of the successor of the original
251 * '*brec' or to invalid data
252 * Returns:
253 * int: 0 on success, or one of -EINVAL, -EIO, or -EINVAL on failure
254 * Preconditions:
255 * 'brec' pointers to a "valid" (struct hfs_brec)
256 * Postconditions:
257 * If the given '*brec' is not "valid" -EINVAL is returned and
258 * '*brec' is unchanged.
259 * If the given 'brec' is "valid" but has no successor then -ENOENT
260 * is returned and '*brec' is invalid.
261 * If a call to hfs_bnode_find() is necessary to find the successor,
262 * but fails then -EIO is returned and '*brec' is invalid.
263 * If none of the three previous conditions prevents finding the
264 * successor of '*brec', then 0 is returned, and '*brec' is overwritten
265 * with the (struct hfs_brec) for its successor.
266 * In the cases when '*brec' is invalid, the old records is freed.
267 */
268 int hfs_bsucc(struct hfs_brec *brec, int count)
269 {
270 struct hfs_belem *belem;
271 struct hfs_bnode *bn;
272
273 if (!brec || !(belem = brec->bottom) || (belem != brec->top) ||
274 !(bn = belem->bnr.bn) || (bn->magic != HFS_BNODE_MAGIC) ||
275 !bn->tree || (bn->tree->magic != HFS_BTREE_MAGIC) ||
276 !hfs_buffer_ok(bn->buf)) {
277 hfs_warn("hfs_bsucc: invalid/corrupt arguments.\n");
278 return -EINVAL;
279 }
280
281 while (count) {
282 int left = bn->ndNRecs - belem->record;
283
284 if (left < count) {
285 struct hfs_bnode_ref old;
286 hfs_u32 node;
287
288 /* Advance to next node */
289 if (!(node = bn->ndFLink)) {
290 hfs_brec_relse(brec, belem);
291 return -ENOENT;
292 }
293 if (node == bn->node) {
294 hfs_warn("hfs_bsucc: corrupt btree\n");
295 hfs_brec_relse(brec, belem);
296 return -EIO;
297 }
298 old = belem->bnr;
299 belem->bnr = hfs_bnode_find(brec->tree, node,
300 belem->bnr.lock_type);
301 hfs_bnode_relse(&old);
302 if (!(bn = belem->bnr.bn)) {
303 return -EIO;
304 }
305 belem->record = 1;
306 count -= (left + 1);
307 } else {
308 belem->record += count;
309 break;
310 }
311 }
312 brec->key = belem_key(belem);
313 brec->data = bkey_record(brec->key);
314
315 if (brec->key->KeyLen > brec->tree->bthKeyLen) {
316 hfs_warn("hfs_bsucc: oversized key\n");
317 hfs_brec_relse(brec, NULL);
318 return -EIO;
319 }
320
321 return 0;
322 }
323