qemu/roms/openbios/fs/hfs/btree.c

   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., 51 Franklin Street - Fifth Floor, Boston,
  18  * MA 02110-1301, USA.
  19  *
  20  * $Id: btree.c,v 1.10 1998/11/02 22:08:54 rob Exp $
  21  */
  22
  23 #include "config.h"
  24
  25 #include "libhfs.h"
  26 #include "btree.h"
  27 #include "data.h"
  28 #include "file.h"
  29 #include "block.h"
  30 #include "node.h"
  31
  32 /*
  33  * NAME:        btree->getnode()
  34  * DESCRIPTION: retrieve a numbered node from a B*-tree file
  35  */
  36 int bt_getnode(node *np, btree *bt, unsigned long nnum)
  37 {
  38   block *bp = &np->data;
  39   const byte *ptr;
  40   int i;
  41
  42   np->bt   = bt;
  43   np->nnum = nnum;
  44
  45 # if 0
  46   fprintf(stderr, "BTREE: GET vol \"%s\" btree \"%s\" node %lu\n",
  47           bt->f.vol->mdb.drVN, bt->f.name, np->nnum);
  48 # endif
  49
  50   /* verify the node exists and is marked as in-use */
  51
  52   if (nnum > 0 && nnum >= bt->hdr.bthNNodes)
  53     ERROR(EIO, "read nonexistent b*-tree node");
  54   else if (bt->map && ! BMTST(bt->map, nnum))
  55     ERROR(EIO, "read unallocated b*-tree node");
  56
  57   if (f_getblock(&bt->f, nnum, bp) == -1)
  58     goto fail;
  59
  60   ptr = *bp;
  61
  62   d_fetchul(&ptr, &np->nd.ndFLink);
  63   d_fetchul(&ptr, &np->nd.ndBLink);
  64   d_fetchsb(&ptr, &np->nd.ndType);
  65   d_fetchsb(&ptr, &np->nd.ndNHeight);
  66   d_fetchuw(&ptr, &np->nd.ndNRecs);
  67   d_fetchsw(&ptr, &np->nd.ndResv2);
  68
  69   if (np->nd.ndNRecs > HFS_MAX_NRECS)
  70     ERROR(EIO, "too many b*-tree node records");
  71
  72   i = np->nd.ndNRecs + 1;
  73
  74   ptr = *bp + HFS_BLOCKSZ - (2 * i);
  75
  76   while (i--)
  77     d_fetchuw(&ptr, &np->roff[i]);
  78
  79   return 0;
  80
  81 fail:
  82   return -1;
  83 }
  84
  85
  86 /*
  87  * NAME:        btree->readhdr()
  88  * DESCRIPTION: read the header node of a B*-tree
  89  */
  90 int bt_readhdr(btree *bt)
  91 {
  92   const byte *ptr;
  93   byte *map = NULL;
  94   int i;
  95   unsigned long nnum;
  96
  97   if (bt_getnode(&bt->hdrnd, bt, 0) == -1)
  98     goto fail;
  99
 100   if (bt->hdrnd.nd.ndType != ndHdrNode ||
 101       bt->hdrnd.nd.ndNRecs != 3 ||
 102       bt->hdrnd.roff[0] != 0x00e ||
 103       bt->hdrnd.roff[1] != 0x078 ||
 104       bt->hdrnd.roff[2] != 0x0f8 ||
 105       bt->hdrnd.roff[3] != 0x1f8)
 106     ERROR(EIO, "malformed b*-tree header node");
 107
 108   /* read header record */
 109
 110   ptr = HFS_NODEREC(bt->hdrnd, 0);
 111
 112   d_fetchuw(&ptr, &bt->hdr.bthDepth);
 113   d_fetchul(&ptr, &bt->hdr.bthRoot);
 114   d_fetchul(&ptr, &bt->hdr.bthNRecs);
 115   d_fetchul(&ptr, &bt->hdr.bthFNode);
 116   d_fetchul(&ptr, &bt->hdr.bthLNode);
 117   d_fetchuw(&ptr, &bt->hdr.bthNodeSize);
 118   d_fetchuw(&ptr, &bt->hdr.bthKeyLen);
 119   d_fetchul(&ptr, &bt->hdr.bthNNodes);
 120   d_fetchul(&ptr, &bt->hdr.bthFree);
 121
 122   for (i = 0; i < 76; ++i)
 123     d_fetchsb(&ptr, &bt->hdr.bthResv[i]);
 124
 125   if (bt->hdr.bthNodeSize != HFS_BLOCKSZ)
 126     ERROR(EINVAL, "unsupported b*-tree node size");
 127
 128   /* read map record; construct btree bitmap */
 129   /* don't set bt->map until we're done, since getnode() checks it */
 130
 131   map = ALLOC(byte, HFS_MAP1SZ);
 132   if (map == NULL)
 133     ERROR(ENOMEM, NULL);
 134
 135   memcpy(map, HFS_NODEREC(bt->hdrnd, 2), HFS_MAP1SZ);
 136   bt->mapsz = HFS_MAP1SZ;
 137
 138   /* read continuation map records, if any */
 139
 140   nnum = bt->hdrnd.nd.ndFLink;
 141
 142   while (nnum)
 143     {
 144       node n;
 145       byte *newmap;
 146
 147       if (bt_getnode(&n, bt, nnum) == -1)
 148         goto fail;
 149
 150       if (n.nd.ndType != ndMapNode ||
 151           n.nd.ndNRecs != 1 ||
 152           n.roff[0] != 0x00e ||
 153           n.roff[1] != 0x1fa)
 154         ERROR(EIO, "malformed b*-tree map node");
 155
 156       newmap = REALLOC(map, byte, bt->mapsz + HFS_MAPXSZ);
 157       if (newmap == NULL)
 158         ERROR(ENOMEM, NULL);
 159
 160       map = newmap;
 161
 162       memcpy(map + bt->mapsz, HFS_NODEREC(n, 0), HFS_MAPXSZ);
 163       bt->mapsz += HFS_MAPXSZ;
 164
 165       nnum = n.nd.ndFLink;
 166     }
 167
 168   bt->map = map;
 169
 170   return 0;
 171
 172 fail:
 173   FREE(map);
 174   return -1;
 175 }
 176
 177
 178 /*
 179  * NAME:        btree->search()
 180  * DESCRIPTION: locate a data record given a search key
 181  */
 182 int bt_search(btree *bt, const byte *key, node *np)
 183 {
 184   int found = 0;
 185   unsigned long nnum;
 186
 187   nnum = bt->hdr.bthRoot;
 188
 189   if (nnum == 0)
 190     ERROR(ENOENT, NULL);
 191
 192   while (1)
 193     {
 194       const byte *rec;
 195
 196       if (bt_getnode(np, bt, nnum) == -1)
 197         {
 198           found = -1;
 199           goto fail;
 200         }
 201
 202       found = n_search(np, key);
 203
 204       switch (np->nd.ndType)
 205         {
 206         case ndIndxNode:
 207           if (np->rnum == -1)
 208             ERROR(ENOENT, NULL);
 209
 210           rec  = HFS_NODEREC(*np, np->rnum);
 211           nnum = d_getul(HFS_RECDATA(rec));
 212
 213           break;
 214
 215         case ndLeafNode:
 216           if (! found)
 217             ERROR(ENOENT, NULL);
 218
 219           goto done;
 220
 221         default:
 222           found = -1;
 223           ERROR(EIO, "unexpected b*-tree node");
 224         }
 225     }
 226
 227 done:
 228 fail:
 229   return found;
 230 }