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 */ 35int 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 */ 88int 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 */ 140int 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 */ 252int 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 */ 337int 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 */ 437int 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 */ 485int 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 */ 557int 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 */ 620int 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 */ 674int 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