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