1 |
/* |
2 |
* libhfs - library for reading and writing Macintosh HFS volumes |
3 |
* Copyright (C) 1996-1998 Robert Leslie |
4 |
* |
5 |
* This program is free software; you can redistribute it and/or modify |
6 |
* it under the terms of the GNU General Public License as published by |
7 |
* the Free Software Foundation; either version 2 of the License, or |
8 |
* (at your option) any later version. |
9 |
* |
10 |
* This program is distributed in the hope that it will be useful, |
11 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 |
* GNU General Public License for more details. |
14 |
* |
15 |
* You should have received a copy of the GNU General Public License |
16 |
* along with this program; if not, write to the Free Software |
17 |
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. |
18 |
* |
19 |
*/ |
20 |
|
21 |
# ifdef HAVE_CONFIG_H |
22 |
# include "config.h" |
23 |
# endif |
24 |
|
25 |
# include <stdlib.h> |
26 |
# include <string.h> |
27 |
# include <errno.h> |
28 |
|
29 |
# include "libhfs.h" |
30 |
# include "btree.h" |
31 |
# include "data.h" |
32 |
# include "file.h" |
33 |
# include "block.h" |
34 |
# include "node.h" |
35 |
|
36 |
/* |
37 |
* NAME: btree->getnode() |
38 |
* DESCRIPTION: retrieve a numbered node from a B*-tree file |
39 |
*/ |
40 |
int bt_getnode(node *np, btree *bt, unsigned long nnum) |
41 |
{ |
42 |
block *bp = &np->data; |
43 |
const byte *ptr; |
44 |
int i; |
45 |
|
46 |
np->bt = bt; |
47 |
np->nnum = nnum; |
48 |
|
49 |
# if 0 |
50 |
fprintf(stderr, "BTREE: GET vol \"%s\" btree \"%s\" node %lu\n", |
51 |
bt->f.vol->mdb.drVN, bt->f.name, np->nnum); |
52 |
# endif |
53 |
|
54 |
/* verify the node exists and is marked as in-use */ |
55 |
|
56 |
if (nnum > 0 && nnum >= bt->hdr.bthNNodes) |
57 |
ERROR(EIO, "read nonexistent b*-tree node"); |
58 |
else if (bt->map && ! BMTST(bt->map, nnum)) |
59 |
ERROR(EIO, "read unallocated b*-tree node"); |
60 |
|
61 |
if (f_getblock(&bt->f, nnum, bp) == -1) |
62 |
goto fail; |
63 |
|
64 |
ptr = *bp; |
65 |
|
66 |
d_fetchul(&ptr, &np->nd.ndFLink); |
67 |
d_fetchul(&ptr, &np->nd.ndBLink); |
68 |
d_fetchsb(&ptr, &np->nd.ndType); |
69 |
d_fetchsb(&ptr, &np->nd.ndNHeight); |
70 |
d_fetchuw(&ptr, &np->nd.ndNRecs); |
71 |
d_fetchsw(&ptr, &np->nd.ndResv2); |
72 |
|
73 |
if (np->nd.ndNRecs > HFS_MAX_NRECS) |
74 |
ERROR(EIO, "too many b*-tree node records"); |
75 |
|
76 |
i = np->nd.ndNRecs + 1; |
77 |
|
78 |
ptr = *bp + HFS_BLOCKSZ - (2 * i); |
79 |
|
80 |
while (i--) |
81 |
d_fetchuw(&ptr, &np->roff[i]); |
82 |
|
83 |
return 0; |
84 |
|
85 |
fail: |
86 |
return -1; |
87 |
} |
88 |
|
89 |
/* |
90 |
* NAME: btree->putnode() |
91 |
* DESCRIPTION: store a numbered node into a B*-tree file |
92 |
*/ |
93 |
int bt_putnode(node *np) |
94 |
{ |
95 |
btree *bt = np->bt; |
96 |
block *bp = &np->data; |
97 |
byte *ptr; |
98 |
int i; |
99 |
|
100 |
# if 0 |
101 |
fprintf(stderr, "BTREE: PUT vol \"%s\" btree \"%s\" node %lu\n", |
102 |
bt->f.vol->mdb.drVN, bt->f.name, np->nnum); |
103 |
# endif |
104 |
|
105 |
/* verify the node exists and is marked as in-use */ |
106 |
|
107 |
if (np->nnum > 0 && np->nnum >= bt->hdr.bthNNodes) |
108 |
ERROR(EIO, "write nonexistent b*-tree node"); |
109 |
else if (bt->map && ! BMTST(bt->map, np->nnum)) |
110 |
ERROR(EIO, "write unallocated b*-tree node"); |
111 |
|
112 |
ptr = *bp; |
113 |
|
114 |
d_storeul(&ptr, np->nd.ndFLink); |
115 |
d_storeul(&ptr, np->nd.ndBLink); |
116 |
d_storesb(&ptr, np->nd.ndType); |
117 |
d_storesb(&ptr, np->nd.ndNHeight); |
118 |
d_storeuw(&ptr, np->nd.ndNRecs); |
119 |
d_storesw(&ptr, np->nd.ndResv2); |
120 |
|
121 |
if (np->nd.ndNRecs > HFS_MAX_NRECS) |
122 |
ERROR(EIO, "too many b*-tree node records"); |
123 |
|
124 |
i = np->nd.ndNRecs + 1; |
125 |
|
126 |
ptr = *bp + HFS_BLOCKSZ - (2 * i); |
127 |
|
128 |
while (i--) |
129 |
d_storeuw(&ptr, np->roff[i]); |
130 |
|
131 |
return f_putblock(&bt->f, np->nnum, bp); |
132 |
|
133 |
fail: |
134 |
return -1; |
135 |
} |
136 |
|
137 |
/* |
138 |
* NAME: btree->readhdr() |
139 |
* DESCRIPTION: read the header node of a B*-tree |
140 |
*/ |
141 |
int bt_readhdr(btree *bt) |
142 |
{ |
143 |
const byte *ptr; |
144 |
byte *map = 0; |
145 |
int i; |
146 |
unsigned long nnum; |
147 |
|
148 |
if (bt_getnode(&bt->hdrnd, bt, 0) == -1) |
149 |
goto fail; |
150 |
|
151 |
if (bt->hdrnd.nd.ndType != ndHdrNode || |
152 |
bt->hdrnd.nd.ndNRecs != 3 || |
153 |
bt->hdrnd.roff[0] != 0x00e || |
154 |
bt->hdrnd.roff[1] != 0x078 || |
155 |
bt->hdrnd.roff[2] != 0x0f8 || |
156 |
bt->hdrnd.roff[3] != 0x1f8) |
157 |
ERROR(EIO, "malformed b*-tree header node"); |
158 |
|
159 |
/* read header record */ |
160 |
|
161 |
ptr = HFS_NODEREC(bt->hdrnd, 0); |
162 |
|
163 |
d_fetchuw(&ptr, &bt->hdr.bthDepth); |
164 |
d_fetchul(&ptr, &bt->hdr.bthRoot); |
165 |
d_fetchul(&ptr, &bt->hdr.bthNRecs); |
166 |
d_fetchul(&ptr, &bt->hdr.bthFNode); |
167 |
d_fetchul(&ptr, &bt->hdr.bthLNode); |
168 |
d_fetchuw(&ptr, &bt->hdr.bthNodeSize); |
169 |
d_fetchuw(&ptr, &bt->hdr.bthKeyLen); |
170 |
d_fetchul(&ptr, &bt->hdr.bthNNodes); |
171 |
d_fetchul(&ptr, &bt->hdr.bthFree); |
172 |
|
173 |
for (i = 0; i < 76; ++i) |
174 |
d_fetchsb(&ptr, &bt->hdr.bthResv[i]); |
175 |
|
176 |
if (bt->hdr.bthNodeSize != HFS_BLOCKSZ) |
177 |
ERROR(EINVAL, "unsupported b*-tree node size"); |
178 |
|
179 |
/* read map record; construct btree bitmap */ |
180 |
/* don't set bt->map until we're done, since getnode() checks it */ |
181 |
|
182 |
map = ALLOC(byte, HFS_MAP1SZ); |
183 |
if (map == 0) |
184 |
ERROR(ENOMEM, 0); |
185 |
|
186 |
memcpy(map, HFS_NODEREC(bt->hdrnd, 2), HFS_MAP1SZ); |
187 |
bt->mapsz = HFS_MAP1SZ; |
188 |
|
189 |
/* read continuation map records, if any */ |
190 |
|
191 |
nnum = bt->hdrnd.nd.ndFLink; |
192 |
|
193 |
while (nnum) |
194 |
{ |
195 |
node n; |
196 |
byte *newmap; |
197 |
|
198 |
if (bt_getnode(&n, bt, nnum) == -1) |
199 |
goto fail; |
200 |
|
201 |
if (n.nd.ndType != ndMapNode || |
202 |
n.nd.ndNRecs != 1 || |
203 |
n.roff[0] != 0x00e || |
204 |
n.roff[1] != 0x1fa) |
205 |
ERROR(EIO, "malformed b*-tree map node"); |
206 |
|
207 |
newmap = REALLOC(map, byte, bt->mapsz + HFS_MAPXSZ); |
208 |
if (newmap == 0) |
209 |
ERROR(ENOMEM, 0); |
210 |
|
211 |
map = newmap; |
212 |
|
213 |
memcpy(map + bt->mapsz, HFS_NODEREC(n, 0), HFS_MAPXSZ); |
214 |
bt->mapsz += HFS_MAPXSZ; |
215 |
|
216 |
nnum = n.nd.ndFLink; |
217 |
} |
218 |
|
219 |
bt->map = map; |
220 |
|
221 |
return 0; |
222 |
|
223 |
fail: |
224 |
FREE(map); |
225 |
return -1; |
226 |
} |
227 |
|
228 |
/* |
229 |
* NAME: btree->writehdr() |
230 |
* DESCRIPTION: write the header node of a B*-tree |
231 |
*/ |
232 |
int bt_writehdr(btree *bt) |
233 |
{ |
234 |
byte *ptr, *map; |
235 |
unsigned long mapsz, nnum; |
236 |
int i; |
237 |
|
238 |
ASSERT(bt->hdrnd.bt == bt && |
239 |
bt->hdrnd.nnum == 0 && |
240 |
bt->hdrnd.nd.ndType == ndHdrNode && |
241 |
bt->hdrnd.nd.ndNRecs == 3); |
242 |
|
243 |
ptr = HFS_NODEREC(bt->hdrnd, 0); |
244 |
|
245 |
d_storeuw(&ptr, bt->hdr.bthDepth); |
246 |
d_storeul(&ptr, bt->hdr.bthRoot); |
247 |
d_storeul(&ptr, bt->hdr.bthNRecs); |
248 |
d_storeul(&ptr, bt->hdr.bthFNode); |
249 |
d_storeul(&ptr, bt->hdr.bthLNode); |
250 |
d_storeuw(&ptr, bt->hdr.bthNodeSize); |
251 |
d_storeuw(&ptr, bt->hdr.bthKeyLen); |
252 |
d_storeul(&ptr, bt->hdr.bthNNodes); |
253 |
d_storeul(&ptr, bt->hdr.bthFree); |
254 |
|
255 |
for (i = 0; i < 76; ++i) |
256 |
d_storesb(&ptr, bt->hdr.bthResv[i]); |
257 |
|
258 |
memcpy(HFS_NODEREC(bt->hdrnd, 2), bt->map, HFS_MAP1SZ); |
259 |
|
260 |
if (bt_putnode(&bt->hdrnd) == -1) |
261 |
goto fail; |
262 |
|
263 |
map = bt->map + HFS_MAP1SZ; |
264 |
mapsz = bt->mapsz - HFS_MAP1SZ; |
265 |
|
266 |
nnum = bt->hdrnd.nd.ndFLink; |
267 |
|
268 |
while (mapsz) |
269 |
{ |
270 |
node n; |
271 |
|
272 |
if (nnum == 0) |
273 |
ERROR(EIO, "truncated b*-tree map"); |
274 |
|
275 |
if (bt_getnode(&n, bt, nnum) == -1) |
276 |
goto fail; |
277 |
|
278 |
if (n.nd.ndType != ndMapNode || |
279 |
n.nd.ndNRecs != 1 || |
280 |
n.roff[0] != 0x00e || |
281 |
n.roff[1] != 0x1fa) |
282 |
ERROR(EIO, "malformed b*-tree map node"); |
283 |
|
284 |
memcpy(HFS_NODEREC(n, 0), map, HFS_MAPXSZ); |
285 |
|
286 |
if (bt_putnode(&n) == -1) |
287 |
goto fail; |
288 |
|
289 |
map += HFS_MAPXSZ; |
290 |
mapsz -= HFS_MAPXSZ; |
291 |
|
292 |
nnum = n.nd.ndFLink; |
293 |
} |
294 |
|
295 |
bt->flags &= ~HFS_BT_UPDATE_HDR; |
296 |
|
297 |
return 0; |
298 |
|
299 |
fail: |
300 |
return -1; |
301 |
} |
302 |
|
303 |
/* High-Level B*-Tree Routines ============================================= */ |
304 |
|
305 |
/* |
306 |
* NAME: btree->space() |
307 |
* DESCRIPTION: assert space for new records, or extend the file |
308 |
*/ |
309 |
int bt_space(btree *bt, unsigned int nrecs) |
310 |
{ |
311 |
unsigned int nnodes; |
312 |
long space; |
313 |
|
314 |
nnodes = nrecs * (bt->hdr.bthDepth + 1); |
315 |
|
316 |
if (nnodes <= bt->hdr.bthFree) |
317 |
goto done; |
318 |
|
319 |
/* make sure the extents tree has room too */ |
320 |
|
321 |
if (bt != &bt->f.vol->ext) |
322 |
{ |
323 |
if (bt_space(&bt->f.vol->ext, 1) == -1) |
324 |
goto fail; |
325 |
} |
326 |
|
327 |
space = f_alloc(&bt->f); |
328 |
if (space == -1) |
329 |
goto fail; |
330 |
|
331 |
nnodes = space * (bt->f.vol->mdb.drAlBlkSiz / bt->hdr.bthNodeSize); |
332 |
|
333 |
bt->hdr.bthNNodes += nnodes; |
334 |
bt->hdr.bthFree += nnodes; |
335 |
|
336 |
bt->flags |= HFS_BT_UPDATE_HDR; |
337 |
|
338 |
bt->f.vol->flags |= HFS_VOL_UPDATE_ALTMDB; |
339 |
|
340 |
while (bt->hdr.bthNNodes > bt->mapsz * 8) |
341 |
{ |
342 |
byte *newmap; |
343 |
node mapnd; |
344 |
|
345 |
/* extend tree map */ |
346 |
|
347 |
newmap = REALLOC(bt->map, byte, bt->mapsz + HFS_MAPXSZ); |
348 |
if (newmap == 0) |
349 |
ERROR(ENOMEM, 0); |
350 |
|
351 |
memset(newmap + bt->mapsz, 0, HFS_MAPXSZ); |
352 |
|
353 |
bt->map = newmap; |
354 |
bt->mapsz += HFS_MAPXSZ; |
355 |
|
356 |
n_init(&mapnd, bt, ndMapNode, 0); |
357 |
if (n_new(&mapnd) == -1) |
358 |
goto fail; |
359 |
|
360 |
mapnd.nd.ndNRecs = 1; |
361 |
mapnd.roff[1] = 0x1fa; |
362 |
|
363 |
/* link the new map node */ |
364 |
|
365 |
if (bt->hdrnd.nd.ndFLink == 0) |
366 |
{ |
367 |
bt->hdrnd.nd.ndFLink = mapnd.nnum; |
368 |
mapnd.nd.ndBLink = 0; |
369 |
} |
370 |
else |
371 |
{ |
372 |
node n; |
373 |
unsigned long nnum; |
374 |
|
375 |
nnum = bt->hdrnd.nd.ndFLink; |
376 |
|
377 |
while (1) |
378 |
{ |
379 |
if (bt_getnode(&n, bt, nnum) == -1) |
380 |
goto fail; |
381 |
|
382 |
if (n.nd.ndFLink == 0) |
383 |
break; |
384 |
|
385 |
nnum = n.nd.ndFLink; |
386 |
} |
387 |
|
388 |
n.nd.ndFLink = mapnd.nnum; |
389 |
mapnd.nd.ndBLink = n.nnum; |
390 |
|
391 |
if (bt_putnode(&n) == -1) |
392 |
goto fail; |
393 |
} |
394 |
|
395 |
if (bt_putnode(&mapnd) == -1) |
396 |
goto fail; |
397 |
} |
398 |
|
399 |
done: |
400 |
return 0; |
401 |
|
402 |
fail: |
403 |
return -1; |
404 |
} |
405 |
|
406 |
/* |
407 |
* NAME: insertx() |
408 |
* DESCRIPTION: recursively locate a node and insert a record |
409 |
*/ |
410 |
static |
411 |
int insertx(node *np, byte *record, unsigned int *reclen) |
412 |
{ |
413 |
node child; |
414 |
byte *rec; |
415 |
int result = 0; |
416 |
|
417 |
if (n_search(np, record)) |
418 |
ERROR(EIO, "b*-tree record already exists"); |
419 |
|
420 |
switch (np->nd.ndType) |
421 |
{ |
422 |
case ndIndxNode: |
423 |
if (np->rnum == -1) |
424 |
rec = HFS_NODEREC(*np, 0); |
425 |
else |
426 |
rec = HFS_NODEREC(*np, np->rnum); |
427 |
|
428 |
if (bt_getnode(&child, np->bt, d_getul(HFS_RECDATA(rec))) == -1 || |
429 |
insertx(&child, record, reclen) == -1) |
430 |
goto fail; |
431 |
|
432 |
if (np->rnum == -1) |
433 |
{ |
434 |
n_index(&child, rec, 0); |
435 |
if (*reclen == 0) |
436 |
{ |
437 |
result = bt_putnode(np); |
438 |
goto done; |
439 |
} |
440 |
} |
441 |
|
442 |
if (*reclen) |
443 |
result = n_insert(np, record, reclen); |
444 |
|
445 |
break; |
446 |
|
447 |
case ndLeafNode: |
448 |
result = n_insert(np, record, reclen); |
449 |
break; |
450 |
|
451 |
default: |
452 |
ERROR(EIO, "unexpected b*-tree node"); |
453 |
} |
454 |
|
455 |
done: |
456 |
return result; |
457 |
|
458 |
fail: |
459 |
return -1; |
460 |
} |
461 |
|
462 |
/* |
463 |
* NAME: btree->insert() |
464 |
* DESCRIPTION: insert a new node record into a tree |
465 |
*/ |
466 |
int bt_insert(btree *bt, const byte *record, unsigned int reclen) |
467 |
{ |
468 |
node root; |
469 |
byte newrec[HFS_MAX_RECLEN]; |
470 |
|
471 |
if (bt->hdr.bthRoot == 0) |
472 |
{ |
473 |
/* create root node */ |
474 |
|
475 |
n_init(&root, bt, ndLeafNode, 1); |
476 |
if (n_new(&root) == -1 || |
477 |
bt_putnode(&root) == -1) |
478 |
goto fail; |
479 |
|
480 |
bt->hdr.bthDepth = 1; |
481 |
bt->hdr.bthRoot = root.nnum; |
482 |
bt->hdr.bthFNode = root.nnum; |
483 |
bt->hdr.bthLNode = root.nnum; |
484 |
|
485 |
bt->flags |= HFS_BT_UPDATE_HDR; |
486 |
} |
487 |
else if (bt_getnode(&root, bt, bt->hdr.bthRoot) == -1) |
488 |
goto fail; |
489 |
|
490 |
memcpy(newrec, record, reclen); |
491 |
|
492 |
if (insertx(&root, newrec, &reclen) == -1) |
493 |
goto fail; |
494 |
|
495 |
if (reclen) |
496 |
{ |
497 |
byte oroot[HFS_MAX_RECLEN]; |
498 |
unsigned int orootlen; |
499 |
|
500 |
/* root node was split; create a new root */ |
501 |
|
502 |
n_index(&root, oroot, &orootlen); |
503 |
|
504 |
n_init(&root, bt, ndIndxNode, root.nd.ndNHeight + 1); |
505 |
if (n_new(&root) == -1) |
506 |
goto fail; |
507 |
|
508 |
++bt->hdr.bthDepth; |
509 |
bt->hdr.bthRoot = root.nnum; |
510 |
|
511 |
bt->flags |= HFS_BT_UPDATE_HDR; |
512 |
|
513 |
/* insert index records for new root */ |
514 |
|
515 |
n_search(&root, oroot); |
516 |
n_insertx(&root, oroot, orootlen); |
517 |
|
518 |
n_search(&root, newrec); |
519 |
n_insertx(&root, newrec, reclen); |
520 |
|
521 |
if (bt_putnode(&root) == -1) |
522 |
goto fail; |
523 |
} |
524 |
|
525 |
++bt->hdr.bthNRecs; |
526 |
bt->flags |= HFS_BT_UPDATE_HDR; |
527 |
|
528 |
return 0; |
529 |
|
530 |
fail: |
531 |
return -1; |
532 |
} |
533 |
|
534 |
/* |
535 |
* NAME: deletex() |
536 |
* DESCRIPTION: recursively locate a node and delete a record |
537 |
*/ |
538 |
static |
539 |
int deletex(node *np, const byte *key, byte *record, int *flag) |
540 |
{ |
541 |
node child; |
542 |
byte *rec; |
543 |
int found, result = 0; |
544 |
|
545 |
found = n_search(np, key); |
546 |
|
547 |
switch (np->nd.ndType) |
548 |
{ |
549 |
case ndIndxNode: |
550 |
if (np->rnum == -1) |
551 |
ERROR(EIO, "b*-tree record not found"); |
552 |
|
553 |
rec = HFS_NODEREC(*np, np->rnum); |
554 |
|
555 |
if (bt_getnode(&child, np->bt, d_getul(HFS_RECDATA(rec))) == -1 || |
556 |
deletex(&child, key, rec, flag) == -1) |
557 |
goto fail; |
558 |
|
559 |
if (*flag) |
560 |
{ |
561 |
*flag = 0; |
562 |
|
563 |
if (HFS_RECKEYLEN(rec) == 0) |
564 |
{ |
565 |
result = n_delete(np, record, flag); |
566 |
break; |
567 |
} |
568 |
|
569 |
if (np->rnum == 0) |
570 |
{ |
571 |
/* propagate index record change into parent */ |
572 |
|
573 |
n_index(np, record, 0); |
574 |
*flag = 1; |
575 |
} |
576 |
|
577 |
result = bt_putnode(np); |
578 |
} |
579 |
|
580 |
break; |
581 |
|
582 |
case ndLeafNode: |
583 |
if (found == 0) |
584 |
ERROR(EIO, "b*-tree record not found"); |
585 |
|
586 |
result = n_delete(np, record, flag); |
587 |
break; |
588 |
|
589 |
default: |
590 |
ERROR(EIO, "unexpected b*-tree node"); |
591 |
} |
592 |
|
593 |
return result; |
594 |
|
595 |
fail: |
596 |
return -1; |
597 |
} |
598 |
|
599 |
/* |
600 |
* NAME: btree->delete() |
601 |
* DESCRIPTION: remove a node record from a tree |
602 |
*/ |
603 |
int bt_delete(btree *bt, const byte *key) |
604 |
{ |
605 |
node root; |
606 |
byte record[HFS_MAX_RECLEN]; |
607 |
int flag = 0; |
608 |
|
609 |
if (bt->hdr.bthRoot == 0) |
610 |
ERROR(EIO, "empty b*-tree"); |
611 |
|
612 |
if (bt_getnode(&root, bt, bt->hdr.bthRoot) == -1 || |
613 |
deletex(&root, key, record, &flag) == -1) |
614 |
goto fail; |
615 |
|
616 |
if (bt->hdr.bthDepth > 1 && root.nd.ndNRecs == 1) |
617 |
{ |
618 |
const byte *rec; |
619 |
|
620 |
/* root only has one record; eliminate it and decrease the tree depth */ |
621 |
|
622 |
rec = HFS_NODEREC(root, 0); |
623 |
|
624 |
--bt->hdr.bthDepth; |
625 |
bt->hdr.bthRoot = d_getul(HFS_RECDATA(rec)); |
626 |
|
627 |
if (n_free(&root) == -1) |
628 |
goto fail; |
629 |
} |
630 |
else if (bt->hdr.bthDepth == 1 && root.nd.ndNRecs == 0) |
631 |
{ |
632 |
/* root node was deleted */ |
633 |
|
634 |
bt->hdr.bthDepth = 0; |
635 |
bt->hdr.bthRoot = 0; |
636 |
} |
637 |
|
638 |
--bt->hdr.bthNRecs; |
639 |
bt->flags |= HFS_BT_UPDATE_HDR; |
640 |
|
641 |
return 0; |
642 |
|
643 |
fail: |
644 |
return -1; |
645 |
} |
646 |
|
647 |
/* |
648 |
* NAME: btree->search() |
649 |
* DESCRIPTION: locate a data record given a search key |
650 |
*/ |
651 |
int bt_search(btree *bt, const byte *key, node *np) |
652 |
{ |
653 |
int found = 0; |
654 |
unsigned long nnum; |
655 |
|
656 |
nnum = bt->hdr.bthRoot; |
657 |
|
658 |
if (nnum == 0) |
659 |
ERROR(ENOENT, 0); |
660 |
|
661 |
while (1) |
662 |
{ |
663 |
const byte *rec; |
664 |
|
665 |
if (bt_getnode(np, bt, nnum) == -1) |
666 |
{ |
667 |
found = -1; |
668 |
goto fail; |
669 |
} |
670 |
|
671 |
found = n_search(np, key); |
672 |
|
673 |
switch (np->nd.ndType) |
674 |
{ |
675 |
case ndIndxNode: |
676 |
if (np->rnum == -1) |
677 |
ERROR(ENOENT, 0); |
678 |
|
679 |
rec = HFS_NODEREC(*np, np->rnum); |
680 |
nnum = d_getul(HFS_RECDATA(rec)); |
681 |
|
682 |
break; |
683 |
|
684 |
case ndLeafNode: |
685 |
if (! found) |
686 |
ERROR(ENOENT, 0); |
687 |
|
688 |
goto done; |
689 |
|
690 |
default: |
691 |
found = -1; |
692 |
ERROR(EIO, "unexpected b*-tree node"); |
693 |
} |
694 |
} |
695 |
|
696 |
done: |
697 |
fail: |
698 |
return found; |
699 |
} |