libhfs_iso/btree.c

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