libhfs_iso/node.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 /* @(#)node.c   1.2 02/02/10 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 "btree.h"
  41 #include "node.h"
  42
  43 # define NODESPACE(n)  \
  44   (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] - 2 * ((n).nd.ndNRecs + 1))
  45
  46 /*
  47  * NAME:        node->init()
  48  * DESCRIPTION: construct an empty node
  49  */
  50 void n_init(node *np, btree *bt, int type, int height)
  51 {
  52   np->bt   = bt;
  53   np->nnum = -1;
  54
  55   np->nd.ndFLink   = 0;
  56   np->nd.ndBLink   = 0;
  57   np->nd.ndType    = type;
  58   np->nd.ndNHeight = height;
  59   np->nd.ndNRecs   = 0;
  60   np->nd.ndResv2   = 0;
  61
  62   np->rnum    = -1;
  63   np->roff[0] = 0x00e;
  64
  65   memset(np->data, 0, sizeof(np->data));
  66 }
  67
  68 /*
  69  * NAME:        node->new()
  70  * DESCRIPTION: allocate a new b*-tree node
  71  */
  72 int n_new(node *np)
  73 {
  74   btree *bt = np->bt;
  75   unsigned long num;
  76
  77   if (bt->hdr.bthFree == 0)
  78     {
  79       ERROR(EIO, "b*-tree full");
  80       return -1;
  81     }
  82
  83   num = 0;
  84   while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
  85     ++num;
  86
  87   if (num == bt->hdr.bthNNodes)
  88     {
  89       ERROR(EIO, "free b*-tree node not found");
  90       return -1;
  91     }
  92
  93   np->nnum = num;
  94
  95   BMSET(bt->map, num);
  96   --bt->hdr.bthFree;
  97
  98   bt->flags |= HFS_UPDATE_BTHDR;
  99
 100   return 0;
 101 }
 102
 103 /*
 104  * NAME:        node->free()
 105  * DESCRIPTION: deallocate a b*-tree node
 106  */
 107 void n_free(node *np)
 108 {
 109   btree *bt = np->bt;
 110
 111   BMCLR(bt->map, np->nnum);
 112   ++bt->hdr.bthFree;
 113
 114   bt->flags |= HFS_UPDATE_BTHDR;
 115 }
 116
 117 /*
 118  * NAME:        node->compact()
 119  * DESCRIPTION: clean up a node, removing deleted records
 120  */
 121 void n_compact(node *np)
 122 {
 123   unsigned char *ptr;
 124   int offset, nrecs, i;
 125
 126   offset = 0x00e;
 127   ptr    = np->data + offset;
 128   nrecs  = 0;
 129
 130   for (i = 0; i < (int)np->nd.ndNRecs; ++i)
 131     {
 132       unsigned char *rec;
 133       int reclen;
 134
 135       rec    = HFS_NODEREC(*np, i);
 136       reclen = np->roff[i + 1] - np->roff[i];
 137
 138       if (HFS_RECKEYLEN(rec) > 0)
 139         {
 140           np->roff[nrecs++] = offset;
 141           offset += reclen;
 142
 143           if (ptr == rec)
 144             ptr += reclen;
 145           else
 146             {
 147               while (reclen--)
 148                 *ptr++ = *rec++;
 149             }
 150         }
 151     }
 152
 153   np->roff[nrecs] = offset;
 154   np->nd.ndNRecs  = nrecs;
 155 }
 156
 157 /*
 158  * NAME:        node->search()
 159  * DESCRIPTION: locate a record in a node, or the record it should follow
 160  */
 161 int n_search(node *np, unsigned char *key)
 162 {
 163   btree *bt = np->bt;
 164   int i, comp = -1;
 165
 166   for (i = np->nd.ndNRecs; i--; )
 167     {
 168       unsigned char *rec;
 169
 170       rec = HFS_NODEREC(*np, i);
 171
 172       if (HFS_RECKEYLEN(rec) == 0)
 173         continue;  /* deleted record */
 174
 175       comp = bt->compare(rec, key);
 176
 177       if (comp <= 0)
 178         break;
 179     }
 180
 181   np->rnum = i;
 182
 183   return comp == 0;
 184 }
 185
 186 /*
 187  * NAME:        node->index()
 188  * DESCRIPTION: create an index record from a key and node pointer
 189  */
 190 void n_index(btree *bt, unsigned char *key, unsigned long nnum,
 191              unsigned char *record, int *reclen)
 192 {
 193   if (bt == &bt->f.vol->cat)
 194     {
 195       /* force the key length to be 0x25 */
 196
 197       HFS_RECKEYLEN(record) = 0x25;
 198       memset(record + 1, 0, 0x25);
 199       memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
 200     }
 201   else
 202     memcpy(record, key, HFS_RECKEYSKIP(key));
 203
 204   d_putl(HFS_RECDATA(record), nnum);
 205
 206   if (reclen)
 207     *reclen = HFS_RECKEYSKIP(record) + 4;
 208 }
 209
 210 /*
 211  * NAME:        node->split()
 212  * DESCRIPTION: divide a node into two and insert a record
 213  */
 214 int n_split(node *left, unsigned char *record, int *reclen)
 215 {
 216   node right;
 217   int nrecs, i, mid;
 218   unsigned char *rec;
 219
 220   right = *left;
 221   right.nd.ndBLink = left->nnum;
 222
 223   if (n_new(&right) < 0)
 224     return -1;
 225
 226   left->nd.ndFLink = right.nnum;
 227   nrecs = left->nd.ndNRecs;
 228
 229   /*
 230    * Ensure node split leaves enough room for new record.
 231    * The size calculations used are based on the NODESPACE() macro, but
 232    * I don't know what the extra 2's and 1's are needed for.
 233    * John Witford <jwitford@hutch.com.au>
 234    */
 235   n_search(&right, record);
 236   mid = nrecs/2;
 237   for(;;)
 238     {
 239         if (right.rnum < mid)
 240         {
 241             if (   mid > 0
 242                 && (int)left->roff[mid] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
 243             {
 244                 --mid;
 245                 if (mid > 0)
 246                     continue;
 247             }
 248         }
 249         else
 250         {
 251             if (   mid < nrecs
 252                 && (int)right.roff[nrecs] - (int)right.roff[mid] + (int)left->roff[0] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
 253             {
 254                 ++mid;
 255                 if (mid < nrecs)
 256                     continue;
 257             }
 258         }
 259         break;
 260     }
 261
 262   for (i = 0; i < nrecs; ++i)
 263     {
 264         if (i < mid)
 265             rec = HFS_NODEREC(right, i);
 266         else
 267             rec = HFS_NODEREC(*left, i);
 268
 269         HFS_RECKEYLEN(rec) = 0;
 270     }
 271
 272 /* original code ...
 273   for (i = 0; i < nrecs; ++i)
 274     {
 275       if (i < nrecs / 2)
 276         rec = HFS_NODEREC(right, i);
 277       else
 278         rec = HFS_NODEREC(*left, i);
 279
 280       HFS_RECKEYLEN(rec) = 0;
 281     }
 282 */
 283   n_compact(left);
 284   n_compact(&right);
 285
 286   n_search(&right, record);
 287   if (right.rnum >= 0)
 288     n_insertx(&right, record, *reclen);
 289   else
 290     {
 291       n_search(left, record);
 292       n_insertx(left, record, *reclen);
 293     }
 294
 295   /* store the new/modified nodes */
 296
 297   if (bt_putnode(left) < 0 ||
 298       bt_putnode(&right) < 0)
 299     return -1;
 300
 301   /* create an index record for the new node in the parent */
 302
 303   n_index(right.bt, HFS_NODEREC(right, 0), right.nnum, record, reclen);
 304
 305   /* update link pointers */
 306
 307   if (left->bt->hdr.bthLNode == left->nnum)
 308     {
 309       left->bt->hdr.bthLNode = right.nnum;
 310       left->bt->flags |= HFS_UPDATE_BTHDR;
 311     }
 312
 313   if (right.nd.ndFLink)
 314     {
 315       node n;
 316
 317       n.bt   = right.bt;
 318       n.nnum = right.nd.ndFLink;
 319
 320       if (bt_getnode(&n) < 0)
 321         return -1;
 322
 323       n.nd.ndBLink = right.nnum;
 324
 325       if (bt_putnode(&n) < 0)
 326         return -1;
 327     }
 328
 329   return 0;
 330 }
 331
 332 /*
 333  * NAME:        node->insertx()
 334  * DESCRIPTION: insert a record into a node (which must already have room)
 335  */
 336 void n_insertx(node *np, unsigned char *record, int reclen)
 337 {
 338   int rnum, i;
 339   unsigned char *ptr;
 340
 341   rnum = np->rnum + 1;
 342
 343   /* push other records down to make room */
 344
 345   for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
 346        ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
 347     *(ptr - 1) = *(ptr - 1 - reclen);
 348
 349   ++np->nd.ndNRecs;
 350
 351   for (i = np->nd.ndNRecs; i > rnum; --i)
 352     np->roff[i] = np->roff[i - 1] + reclen;
 353
 354   /* write the new record */
 355
 356   memcpy(HFS_NODEREC(*np, rnum), record, reclen);
 357 }
 358
 359 /*
 360  * NAME:        node->insert()
 361  * DESCRIPTION: insert a new record into a node; return a record for parent
 362  */
 363 int n_insert(node *np, unsigned char *record, int *reclen)
 364 {
 365   n_compact(np);
 366
 367   /* check for free space */
 368
 369   if (np->nd.ndNRecs >= HFS_MAXRECS ||
 370       *reclen + 2 > (int)NODESPACE(*np))
 371     return n_split(np, record, reclen);
 372
 373   n_insertx(np, record, *reclen);
 374   *reclen = 0;
 375
 376   return bt_putnode(np);
 377 }
 378
 379 /*
 380  * NAME:        node->merge()
 381  * DESCRIPTION: combine two nodes into a single node
 382  */
 383 int n_merge(node *right, node *left, unsigned char *record, int *flag)
 384 {
 385   int i, offset;
 386
 387   /* copy records and offsets */
 388
 389   memcpy(HFS_NODEREC(*left, left->nd.ndNRecs), HFS_NODEREC(*right, 0),
 390          right->roff[right->nd.ndNRecs] - right->roff[0]);
 391
 392   offset = left->roff[left->nd.ndNRecs] - right->roff[0];
 393
 394   for (i = 1; i <= (int)right->nd.ndNRecs; ++i)
 395     left->roff[++left->nd.ndNRecs] = offset + right->roff[i];
 396
 397   /* update link pointers */
 398
 399   left->nd.ndFLink = right->nd.ndFLink;
 400
 401   if (bt_putnode(left) < 0)
 402     return -1;
 403
 404   if (right->bt->hdr.bthLNode == right->nnum)
 405     {
 406       right->bt->hdr.bthLNode = left->nnum;
 407       right->bt->flags |= HFS_UPDATE_BTHDR;
 408     }
 409
 410   if (right->nd.ndFLink)
 411     {
 412       node n;
 413
 414       n.bt   = right->bt;
 415       n.nnum = right->nd.ndFLink;
 416
 417       if (bt_getnode(&n) < 0)
 418         return -1;
 419
 420       n.nd.ndBLink = left->nnum;
 421
 422       if (bt_putnode(&n) < 0)
 423         return -1;
 424     }
 425
 426   n_free(right);
 427
 428   HFS_RECKEYLEN(record) = 0;
 429   *flag = 1;
 430
 431   return 0;
 432 }
 433
 434 /*
 435  * NAME:        node->delete()
 436  * DESCRIPTION: remove a record from a node
 437  */
 438 int n_delete(node *np, unsigned char *record, int *flag)
 439 {
 440   node left;
 441   unsigned char *rec;
 442
 443   rec = HFS_NODEREC(*np, np->rnum);
 444
 445   HFS_RECKEYLEN(rec) = 0;
 446   n_compact(np);
 447
 448   /* see if we can merge with our left sibling */
 449
 450   left.bt   = np->bt;
 451   left.nnum = np->nd.ndBLink;
 452
 453   if (left.nnum > 0)
 454     {
 455       if (bt_getnode(&left) < 0)
 456         return -1;
 457
 458       if ((int)(np->nd.ndNRecs + left.nd.ndNRecs) <= HFS_MAXRECS &&
 459           (int)(np->roff[np->nd.ndNRecs] - np->roff[0] +
 460           2 * np->nd.ndNRecs) <= (int)NODESPACE(left))
 461         return n_merge(np, &left, record, flag);
 462     }
 463
 464   if (np->rnum == 0)
 465     {
 466       /* special case: first record changed; update parent record key */
 467
 468       n_index(np->bt, HFS_NODEREC(*np, 0), np->nnum, record, 0);
 469       *flag = 1;
 470     }
 471
 472   return bt_putnode(np);
 473 }