Imported Upstream version 1.1.11upstream/1.1.11upstream

1 files changed, 740 insertions, 0 deletions

diff --git a/libhfs_iso/btree.c b/libhfs_iso/btree.c
new file mode 100644
index 0000000..9023428
--- /dev/null
+++ b/libhfs_iso/btree.c
@@ -0,0 +1,740 @@
+/*
+ * This file has been modified for the cdrkit suite.
+ *
+ * The behaviour and appearence of the program code below can differ to a major
+ * extent from the version distributed by the original author(s).
+ *
+ * For details, see Changelog file distributed with the cdrkit package. If you
+ * received this file from another source then ask the distributing person for
+ * a log of modifications.
+ *
+ */
+
+/* @(#)btree.c	1.3 04/06/17 joerg */
+/*
+ * hfsutils - tools for reading and writing Macintosh HFS volumes
+ * Copyright (C) 1996, 1997 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.
+ */
+
+#include <mconfig.h>
+#include <stdxlib.h>
+#include <strdefs.h>
+#include <errno.h>
+
+#include "internal.h"
+#include "data.h"
+#include "block.h"
+#include "file.h"
+#include "btree.h"
+#include "node.h"
+
+/*
+ * NAME:	btree->getnode()
+ * DESCRIPTION:	retrieve a numbered node from a B*-tree file
+ */
+int bt_getnode(node *np)
+{
+  btree *bt = np->bt;
+  block *bp = &np->data;
+  unsigned char *ptr;
+  int i;
+
+  /* verify the node exists and is marked as in-use */
+
+	/*
+	 * XXX This is the original code. As np->nnum is unsigned, the
+	 * XXX comparison for < 0 makes no sense.
+	 * XXX Thanks for a hint from Mike.Sullivan@Eng.Sun.COM
+	 */
+/*  if (np->nnum < 0 || (np->nnum > 0 && np->nnum >= bt->hdr.bthNNodes))*/
+
+  if (np->nnum > 0 && np->nnum >= bt->hdr.bthNNodes)
+    {
+      ERROR(EIO, "read nonexistent b*-tree node");
+      return -1;
+    }
+
+  if (bt->map && ! BMTST(bt->map, np->nnum))
+    {
+      ERROR(EIO, "read unallocated b*-tree node");
+      return -1;
+    }
+
+  if (f_getblock(&bt->f, np->nnum, bp) < 0)
+    return -1;
+
+  ptr = *bp;
+
+  d_fetchl(&ptr, (long *) &np->nd.ndFLink);
+  d_fetchl(&ptr, (long *) &np->nd.ndBLink);
+  d_fetchb(&ptr, (char *) &np->nd.ndType);
+  d_fetchb(&ptr, (char *) &np->nd.ndNHeight);
+  d_fetchw(&ptr, (short *) &np->nd.ndNRecs);
+  d_fetchw(&ptr, &np->nd.ndResv2);
+
+  if (np->nd.ndNRecs > HFS_MAXRECS)
+    {
+      ERROR(EIO, "too many b*-tree node records");
+      return -1;
+    }
+
+  i = np->nd.ndNRecs + 1;
+
+  ptr = *bp + HFS_BLOCKSZ - (2 * i);
+
+  while (i--)
+    d_fetchw(&ptr, (short *) &np->roff[i]);
+
+  return 0;
+}
+
+/*
+ * NAME:	btree->putnode()
+ * DESCRIPTION:	store a numbered node into a B*-tree file
+ */
+int bt_putnode(node *np)
+{
+  btree *bt = np->bt;
+  block *bp = &np->data;
+  unsigned char *ptr;
+  int i;
+
+  /* verify the node exists and is marked as in-use */
+
+  if (np->nnum && np->nnum >= bt->hdr.bthNNodes)
+    {
+      ERROR(EIO, "write nonexistent b*-tree node");
+      return -1;
+    }
+  else if (bt->map && ! BMTST(bt->map, np->nnum))
+    {
+      ERROR(EIO, "write unallocated b*-tree node");
+      return -1;
+    }
+
+  ptr = *bp;
+
+  d_storel(&ptr, np->nd.ndFLink);
+  d_storel(&ptr, np->nd.ndBLink);
+  d_storeb(&ptr, np->nd.ndType);
+  d_storeb(&ptr, np->nd.ndNHeight);
+  d_storew(&ptr, np->nd.ndNRecs);
+  d_storew(&ptr, np->nd.ndResv2);
+
+  if (np->nd.ndNRecs > HFS_MAXRECS)
+    {
+      ERROR(EIO, "too many b*-tree node records");
+      return -1;
+    }
+
+  i = np->nd.ndNRecs + 1;
+
+  ptr = *bp + HFS_BLOCKSZ - (2 * i);
+
+  while (i--)
+    d_storew(&ptr, np->roff[i]);
+
+  if (f_putblock(&bt->f, np->nnum, bp) < 0)
+    return -1;
+
+  return 0;
+}
+
+/*
+ * NAME:	btree->readhdr()
+ * DESCRIPTION:	read the header node of a B*-tree
+ */
+int bt_readhdr(btree *bt)
+{
+  unsigned char *ptr;
+  char *map;
+  int i;
+  unsigned long nnum;
+
+  bt->hdrnd.bt   = bt;
+  bt->hdrnd.nnum = 0;
+
+  if (bt_getnode(&bt->hdrnd) < 0)
+    return -1;
+
+  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");
+      return -1;
+    }
+
+  /* read header record */
+
+  ptr = HFS_NODEREC(bt->hdrnd, 0);
+
+  d_fetchw(&ptr, (short *) &bt->hdr.bthDepth);
+  d_fetchl(&ptr, (long *) &bt->hdr.bthRoot);
+  d_fetchl(&ptr, (long *) &bt->hdr.bthNRecs);
+  d_fetchl(&ptr, (long *) &bt->hdr.bthFNode);
+  d_fetchl(&ptr, (long *) &bt->hdr.bthLNode);
+  d_fetchw(&ptr, (short *) &bt->hdr.bthNodeSize);
+  d_fetchw(&ptr, (short *) &bt->hdr.bthKeyLen);
+  d_fetchl(&ptr, (long *) &bt->hdr.bthNNodes);
+  d_fetchl(&ptr, (long *) &bt->hdr.bthFree);
+
+  for (i = 0; i < 76; ++i)
+    d_fetchb(&ptr, (char *) &bt->hdr.bthResv[i]);
+
+  if (bt->hdr.bthNodeSize != HFS_BLOCKSZ)
+    {
+      ERROR(EINVAL, "unsupported b*-tree node size");
+      return -1;
+    }
+
+  /* read map record; construct btree bitmap */
+  /* don't set bt->map until we're done, since getnode() checks it */
+
+  map = ALLOC(char, HFS_MAP1SZ);
+  if (map == 0)
+    {
+      ERROR(ENOMEM, 0);
+      return -1;
+    }
+
+  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;
+      char *newmap;
+
+      n.bt   = bt;
+      n.nnum = nnum;
+
+      if (bt_getnode(&n) < 0)
+	{
+	  FREE(map);
+	  return -1;
+	}
+
+      if (n.nd.ndType != ndMapNode ||
+	  n.nd.ndNRecs != 1 ||
+	  n.roff[0] != 0x00e ||
+	  n.roff[1] != 0x1fa)
+	{
+	  FREE(map);
+	  ERROR(EIO, "malformed b*-tree map node");
+	  return -1;
+	}
+
+      newmap = REALLOC(map, char, bt->mapsz + HFS_MAPXSZ);
+      if (newmap == 0)
+	{
+	  FREE(map);
+	  ERROR(ENOMEM, 0);
+	  return -1;
+	}
+      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;
+}
+
+/*
+ * NAME:	btree->writehdr()
+ * DESCRIPTION:	write the header node of a B*-tree
+ */
+int bt_writehdr(btree *bt)
+{
+  unsigned char *ptr;
+  char *map;
+  unsigned long mapsz, nnum;
+  int i;
+
+  if (bt->hdrnd.bt != bt ||
+      bt->hdrnd.nnum != 0 ||
+      bt->hdrnd.nd.ndType != ndHdrNode ||
+      bt->hdrnd.nd.ndNRecs != 3)
+    abort();
+
+  ptr = HFS_NODEREC(bt->hdrnd, 0);
+
+  d_storew(&ptr, bt->hdr.bthDepth);
+  d_storel(&ptr, bt->hdr.bthRoot);
+  d_storel(&ptr, bt->hdr.bthNRecs);
+  d_storel(&ptr, bt->hdr.bthFNode);
+  d_storel(&ptr, bt->hdr.bthLNode);
+  d_storew(&ptr, bt->hdr.bthNodeSize);
+  d_storew(&ptr, bt->hdr.bthKeyLen);
+  d_storel(&ptr, bt->hdr.bthNNodes);
+  d_storel(&ptr, bt->hdr.bthFree);
+
+  for (i = 0; i < 76; ++i)
+    d_storeb(&ptr, bt->hdr.bthResv[i]);
+
+  memcpy(HFS_NODEREC(bt->hdrnd, 2), bt->map, HFS_MAP1SZ);
+
+  if (bt_putnode(&bt->hdrnd) < 0)
+    return -1;
+
+  map   = bt->map   + HFS_MAP1SZ;
+  mapsz = bt->mapsz - HFS_MAP1SZ;
+
+  nnum  = bt->hdrnd.nd.ndFLink;
+
+  while (mapsz)
+    {
+      node n;
+
+      if (nnum == 0)
+	{
+	  ERROR(EIO, "truncated b*-tree map");
+	  return -1;
+	}
+
+      n.bt   = bt;
+      n.nnum = nnum;
+
+      if (bt_getnode(&n) < 0)
+	return -1;
+
+      if (n.nd.ndType != ndMapNode ||
+	  n.nd.ndNRecs != 1 ||
+	  n.roff[0] != 0x00e ||
+	  n.roff[1] != 0x1fa)
+	{
+	  ERROR(EIO, "malformed b*-tree map node");
+	  return -1;
+	}
+
+      memcpy(HFS_NODEREC(n, 0), map, HFS_MAPXSZ);
+
+      if (bt_putnode(&n) < 0)
+	return -1;
+
+      map   += HFS_MAPXSZ;
+      mapsz -= HFS_MAPXSZ;
+
+      nnum = n.nd.ndFLink;
+    }
+
+  bt->flags &= ~HFS_UPDATE_BTHDR;
+
+  return 0;
+}
+
+/* High-Level B*-Tree Routines ============================================= */
+
+/*
+ * NAME:	btree->space()
+ * DESCRIPTION:	assert space for new records, or extend the file
+ */
+int bt_space(btree *bt, unsigned int nrecs)
+{
+  unsigned int nnodes;
+  int space;
+
+  nnodes = nrecs * (bt->hdr.bthDepth + 1);
+
+  if (nnodes <= bt->hdr.bthFree)
+    return 0;
+
+  /* make sure the extents tree has room too */
+
+  if (bt != &bt->f.vol->ext)
+    {
+      if (bt_space(&bt->f.vol->ext, 1) < 0)
+	return -1;
+    }
+
+  space = f_alloc(&bt->f);
+  if (space < 0)
+    return -1;
+
+  nnodes = space * (bt->f.vol->mdb.drAlBlkSiz / bt->hdr.bthNodeSize);
+
+  bt->hdr.bthNNodes += nnodes;
+  bt->hdr.bthFree   += nnodes;
+
+  bt->flags |= HFS_UPDATE_BTHDR;
+
+  bt->f.vol->flags |= HFS_UPDATE_ALTMDB;
+
+  while (bt->hdr.bthNNodes > bt->mapsz * 8)
+    {
+      char *newmap;
+      node mapnd;
+
+      /* extend tree map */
+
+      newmap = REALLOC(bt->map, char, bt->mapsz + HFS_MAPXSZ);
+      if (newmap == 0)
+	{
+	  ERROR(ENOMEM, 0);
+	  return -1;
+	}
+
+      memset(newmap + bt->mapsz, 0, HFS_MAPXSZ);
+
+      bt->map    = newmap;
+      bt->mapsz += HFS_MAPXSZ;
+
+      n_init(&mapnd, bt, ndMapNode, 0);
+      if (n_new(&mapnd) < 0)
+	return -1;
+
+      /* link the new map node */
+
+      if (bt->hdrnd.nd.ndFLink == 0)
+	{
+	  bt->hdrnd.nd.ndFLink = mapnd.nnum;
+	  mapnd.nd.ndBLink     = 0;
+	}
+      else
+	{
+	  node n;
+
+	  n.bt   = bt;
+	  n.nnum = bt->hdrnd.nd.ndFLink;
+
+	  for (;;)
+	    {
+	      if (bt_getnode(&n) < 0)
+		return -1;
+
+	      if (n.nd.ndFLink == 0)
+		break;
+
+	      n.nnum = n.nd.ndFLink;
+	    }
+
+	  n.nd.ndFLink     = mapnd.nnum;
+	  mapnd.nd.ndBLink = n.nnum;
+
+	  if (bt_putnode(&n) < 0)
+	    return -1;
+	}
+
+      mapnd.nd.ndNRecs = 1;
+      mapnd.roff[1]    = 0x1fa;
+
+      if (bt_putnode(&mapnd) < 0)
+	return -1;
+    }
+
+  return 0;
+}
+
+/*
+ * NAME:	btree->insertx()
+ * DESCRIPTION:	recursively locate a node and insert a record
+ */
+int bt_insertx(node *np, unsigned char *record, int *reclen)
+{
+  node child;
+  unsigned char *rec;
+
+  if (n_search(np, record))
+    {
+      ERROR(EIO, "b*-tree record already exists");
+      return -1;
+    }
+
+  switch ((unsigned char) np->nd.ndType)
+    {
+    case ndIndxNode:
+      if (np->rnum < 0)
+	rec = HFS_NODEREC(*np, 0);
+      else
+	rec = HFS_NODEREC(*np, np->rnum);
+
+      child.bt   = np->bt;
+      child.nnum = d_getl(HFS_RECDATA(rec));
+
+      if (bt_getnode(&child) < 0 ||
+	  bt_insertx(&child, record, reclen) < 0)
+	return -1;
+
+      if (np->rnum < 0)
+	{
+	  n_index(np->bt, HFS_NODEREC(child, 0), child.nnum, rec, 0);
+	  if (*reclen == 0)
+	    return bt_putnode(np);
+	}
+
+      return *reclen ? n_insert(np, record, reclen) : 0;
+
+    case ndLeafNode:
+      return n_insert(np, record, reclen);
+
+    default:
+      ERROR(EIO, "unexpected b*-tree node");
+      return -1;
+    }
+}
+
+/*
+ * NAME:	btree->insert()
+ * DESCRIPTION:	insert a new node record into a tree
+ */
+int bt_insert(btree *bt, unsigned char *record, int reclen)
+{
+  node root;
+
+  if (bt->hdr.bthRoot == 0)
+    {
+      /* create root node */
+
+      n_init(&root, bt, ndLeafNode, 1);
+      if (n_new(&root) < 0 ||
+	  bt_putnode(&root) < 0)
+	return -1;
+
+      bt->hdr.bthDepth = 1;
+      bt->hdr.bthRoot  = root.nnum;
+      bt->hdr.bthFNode = root.nnum;
+      bt->hdr.bthLNode = root.nnum;
+
+      bt->flags |= HFS_UPDATE_BTHDR;
+    }
+  else
+    {
+      root.bt   = bt;
+      root.nnum = bt->hdr.bthRoot;
+
+      if (bt_getnode(&root) < 0)
+	return -1;
+    }
+
+  if (bt_insertx(&root, record, &reclen) < 0)
+    return -1;
+
+  if (reclen)
+    {
+      unsigned char oroot[HFS_MAXRECLEN];
+      int orootlen;
+
+      /* root node was split; create a new root */
+
+      n_index(bt, HFS_NODEREC(root, 0), root.nnum, oroot, &orootlen);
+
+      n_init(&root, bt, ndIndxNode, root.nd.ndNHeight + 1);
+      if (n_new(&root) < 0)
+	return -1;
+
+      ++bt->hdr.bthDepth;
+      bt->hdr.bthRoot = root.nnum;
+
+      bt->flags |= HFS_UPDATE_BTHDR;
+
+      /* insert index records for new root */
+
+      n_search(&root, oroot);
+      n_insertx(&root, oroot, orootlen);
+
+      n_search(&root, record);
+      n_insertx(&root, record, reclen);
+
+      if (bt_putnode(&root) < 0)
+	return -1;
+    }
+
+  ++bt->hdr.bthNRecs;
+  bt->flags |= HFS_UPDATE_BTHDR;
+
+  return 0;
+}
+
+/*
+ * NAME:	btree->deletex()
+ * DESCRIPTION:	recursively locate a node and delete a record
+ */
+int bt_deletex(node *np, unsigned char *key, unsigned char *record, int *flag)
+{
+  node child;
+  unsigned char *rec;
+  int found;
+
+  found = n_search(np, key);
+
+  switch ((unsigned char) np->nd.ndType)
+    {
+    case ndIndxNode:
+      if (np->rnum < 0)
+	{
+	  ERROR(EIO, "b*-tree record not found");
+	  return -1;
+	}
+
+      rec = HFS_NODEREC(*np, np->rnum);
+
+      child.bt   = np->bt;
+      child.nnum = d_getl(HFS_RECDATA(rec));
+
+      if (bt_getnode(&child) < 0 ||
+	  bt_deletex(&child, key, rec, flag) < 0)
+	return -1;
+
+      if (*flag)
+	{
+	  *flag = 0;
+
+	  if (HFS_RECKEYLEN(rec) == 0)
+	    return n_delete(np, record, flag);
+
+	  if (np->rnum == 0)
+	    {
+	      n_index(np->bt, HFS_NODEREC(*np, 0), np->nnum, record, 0);
+	      *flag = 1;
+	    }
+
+	  return bt_putnode(np);
+	}
+
+      return 0;
+
+    case ndLeafNode:
+      if (found == 0)
+	{
+	  ERROR(EIO, "b*-tree record not found");
+	  return -1;
+	}
+
+      return n_delete(np, record, flag);
+
+    default:
+      ERROR(EIO, "unexpected b*-tree node");
+      return -1;
+    }
+}
+
+/*
+ * NAME:	btree->delete()
+ * DESCRIPTION:	remove a node record from a tree
+ */
+int bt_delete(btree *bt, unsigned char *key)
+{
+  node root;
+  unsigned char record[HFS_MAXRECLEN];
+  int flag = 0;
+
+  root.bt   = bt;
+  root.nnum = bt->hdr.bthRoot;
+
+  if (root.nnum == 0)
+    {
+      ERROR(EIO, "empty b*-tree");
+      return -1;
+    }
+
+  if (bt_getnode(&root) < 0 ||
+      bt_deletex(&root, key, record, &flag) < 0)
+    return -1;
+
+  if (bt->hdr.bthDepth > 1 && root.nd.ndNRecs == 1)
+    {
+      unsigned char *rec;
+
+      /* chop the root */
+
+      rec = HFS_NODEREC(root, 0);
+
+      --bt->hdr.bthDepth;
+      bt->hdr.bthRoot = d_getl(HFS_RECDATA(rec));
+
+      n_free(&root);
+    }
+  else if (bt->hdr.bthDepth == 1 && root.nd.ndNRecs == 0)
+    {
+      /* delete the root node */
+
+      bt->hdr.bthDepth = 0;
+      bt->hdr.bthRoot  = 0;
+      bt->hdr.bthFNode = 0;
+      bt->hdr.bthLNode = 0;
+
+      n_free(&root);
+    }
+
+  --bt->hdr.bthNRecs;
+  bt->flags |= HFS_UPDATE_BTHDR;
+
+  return 0;
+}
+
+/*
+ * NAME:	btree->search()
+ * DESCRIPTION:	locate a data record given a search key
+ */
+int bt_search(btree *bt, unsigned char *key, node *np)
+{
+  np->bt   = bt;
+  np->nnum = bt->hdr.bthRoot;
+
+  if (np->nnum == 0)
+    {
+      ERROR(ENOENT, 0);
+      return 0;
+    }
+
+  for (;;)
+    {
+      int found;
+      unsigned char *rec;
+
+      if (bt_getnode(np) < 0)
+	return -1;
+
+      found = n_search(np, key);
+
+      switch ((unsigned char) np->nd.ndType)
+	{
+	case ndIndxNode:
+	  if (np->rnum < 0)
+	    {
+	      ERROR(ENOENT, 0);
+	      return 0;
+	    }
+
+	  rec = HFS_NODEREC(*np, np->rnum);
+	  np->nnum = d_getl(HFS_RECDATA(rec));
+	  break;
+
+	case ndLeafNode:
+	  if (! found)
+	    ERROR(ENOENT, 0);
+
+	  return found;
+
+	default:
+	  ERROR(EIO, "unexpected b*-tree node");
+	  return -1;
+	}
+    }
+}