btree.c

open source bios with linux platform, very good and can be reused.

/*
 * 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., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * $Id: btree.c,v 1.10 1998/11/02 22:08:54 rob Exp $
 */

#include "openbios/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 = 0;
  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 == 0)
    ERROR(ENOMEM, 0);

  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 == 0)
	ERROR(ENOMEM, 0);

      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, 0);

  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, 0);

	  rec  = HFS_NODEREC(*np, np->rnum);
	  nnum = d_getul(HFS_RECDATA(rec));

	  break;

	case ndLeafNode:
	  if (! found)
	    ERROR(ENOENT, 0);

	  goto done;

	default:
	  found = -1;
	  ERROR(EIO, "unexpected b*-tree node");
	}
    }

done:
fail:
  return found;
}