diff options
Diffstat (limited to 'qemu/roms/openbios/fs/hfs/btree.c')
-rw-r--r-- | qemu/roms/openbios/fs/hfs/btree.c | 230 |
1 files changed, 0 insertions, 230 deletions
diff --git a/qemu/roms/openbios/fs/hfs/btree.c b/qemu/roms/openbios/fs/hfs/btree.c deleted file mode 100644 index cd5c85347..000000000 --- a/qemu/roms/openbios/fs/hfs/btree.c +++ /dev/null @@ -1,230 +0,0 @@ -/* - * libhfs - library for reading and writing Macintosh HFS volumes - * Copyright (C) 1996-1998 Robert Leslie - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, - * MA 02110-1301, USA. - * - * $Id: btree.c,v 1.10 1998/11/02 22:08:54 rob Exp $ - */ - -#include "config.h" - -#include "libhfs.h" -#include "btree.h" -#include "data.h" -#include "file.h" -#include "block.h" -#include "node.h" - -/* - * NAME: btree->getnode() - * DESCRIPTION: retrieve a numbered node from a B*-tree file - */ -int bt_getnode(node *np, btree *bt, unsigned long nnum) -{ - block *bp = &np->data; - const byte *ptr; - int i; - - np->bt = bt; - np->nnum = nnum; - -# if 0 - fprintf(stderr, "BTREE: GET vol \"%s\" btree \"%s\" node %lu\n", - bt->f.vol->mdb.drVN, bt->f.name, np->nnum); -# endif - - /* verify the node exists and is marked as in-use */ - - if (nnum > 0 && nnum >= bt->hdr.bthNNodes) - ERROR(EIO, "read nonexistent b*-tree node"); - else if (bt->map && ! BMTST(bt->map, nnum)) - ERROR(EIO, "read unallocated b*-tree node"); - - if (f_getblock(&bt->f, nnum, bp) == -1) - goto fail; - - ptr = *bp; - - d_fetchul(&ptr, &np->nd.ndFLink); - d_fetchul(&ptr, &np->nd.ndBLink); - d_fetchsb(&ptr, &np->nd.ndType); - d_fetchsb(&ptr, &np->nd.ndNHeight); - d_fetchuw(&ptr, &np->nd.ndNRecs); - d_fetchsw(&ptr, &np->nd.ndResv2); - - if (np->nd.ndNRecs > HFS_MAX_NRECS) - ERROR(EIO, "too many b*-tree node records"); - - i = np->nd.ndNRecs + 1; - - ptr = *bp + HFS_BLOCKSZ - (2 * i); - - while (i--) - d_fetchuw(&ptr, &np->roff[i]); - - return 0; - -fail: - return -1; -} - - -/* - * NAME: btree->readhdr() - * DESCRIPTION: read the header node of a B*-tree - */ -int bt_readhdr(btree *bt) -{ - const byte *ptr; - byte *map = NULL; - int i; - unsigned long nnum; - - if (bt_getnode(&bt->hdrnd, bt, 0) == -1) - goto fail; - - if (bt->hdrnd.nd.ndType != ndHdrNode || - bt->hdrnd.nd.ndNRecs != 3 || - bt->hdrnd.roff[0] != 0x00e || - bt->hdrnd.roff[1] != 0x078 || - bt->hdrnd.roff[2] != 0x0f8 || - bt->hdrnd.roff[3] != 0x1f8) - ERROR(EIO, "malformed b*-tree header node"); - - /* read header record */ - - ptr = HFS_NODEREC(bt->hdrnd, 0); - - d_fetchuw(&ptr, &bt->hdr.bthDepth); - d_fetchul(&ptr, &bt->hdr.bthRoot); - d_fetchul(&ptr, &bt->hdr.bthNRecs); - d_fetchul(&ptr, &bt->hdr.bthFNode); - d_fetchul(&ptr, &bt->hdr.bthLNode); - d_fetchuw(&ptr, &bt->hdr.bthNodeSize); - d_fetchuw(&ptr, &bt->hdr.bthKeyLen); - d_fetchul(&ptr, &bt->hdr.bthNNodes); - d_fetchul(&ptr, &bt->hdr.bthFree); - - for (i = 0; i < 76; ++i) - d_fetchsb(&ptr, &bt->hdr.bthResv[i]); - - if (bt->hdr.bthNodeSize != HFS_BLOCKSZ) - ERROR(EINVAL, "unsupported b*-tree node size"); - - /* read map record; construct btree bitmap */ - /* don't set bt->map until we're done, since getnode() checks it */ - - map = ALLOC(byte, HFS_MAP1SZ); - if (map == NULL) - ERROR(ENOMEM, NULL); - - memcpy(map, HFS_NODEREC(bt->hdrnd, 2), HFS_MAP1SZ); - bt->mapsz = HFS_MAP1SZ; - - /* read continuation map records, if any */ - - nnum = bt->hdrnd.nd.ndFLink; - - while (nnum) - { - node n; - byte *newmap; - - if (bt_getnode(&n, bt, nnum) == -1) - goto fail; - - if (n.nd.ndType != ndMapNode || - n.nd.ndNRecs != 1 || - n.roff[0] != 0x00e || - n.roff[1] != 0x1fa) - ERROR(EIO, "malformed b*-tree map node"); - - newmap = REALLOC(map, byte, bt->mapsz + HFS_MAPXSZ); - if (newmap == NULL) - ERROR(ENOMEM, NULL); - - map = newmap; - - memcpy(map + bt->mapsz, HFS_NODEREC(n, 0), HFS_MAPXSZ); - bt->mapsz += HFS_MAPXSZ; - - nnum = n.nd.ndFLink; - } - - bt->map = map; - - return 0; - -fail: - FREE(map); - return -1; -} - - -/* - * NAME: btree->search() - * DESCRIPTION: locate a data record given a search key - */ -int bt_search(btree *bt, const byte *key, node *np) -{ - int found = 0; - unsigned long nnum; - - nnum = bt->hdr.bthRoot; - - if (nnum == 0) - ERROR(ENOENT, NULL); - - while (1) - { - const byte *rec; - - if (bt_getnode(np, bt, nnum) == -1) - { - found = -1; - goto fail; - } - - found = n_search(np, key); - - switch (np->nd.ndType) - { - case ndIndxNode: - if (np->rnum == -1) - ERROR(ENOENT, NULL); - - rec = HFS_NODEREC(*np, np->rnum); - nnum = d_getul(HFS_RECDATA(rec)); - - break; - - case ndLeafNode: - if (! found) - ERROR(ENOENT, NULL); - - goto done; - - default: - found = -1; - ERROR(EIO, "unexpected b*-tree node"); - } - } - -done: -fail: - return found; -} |