Return to btree.c CVS log

Up to [Qemu by Fabrice Bellard] / qemu / roms / openbios / fs / hfs

Annotation of qemu/roms/openbios/fs/hfs/btree.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.