X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=qemu%2Froms%2Fopenbios%2Ffs%2Fhfs%2Fbtree.c;fp=qemu%2Froms%2Fopenbios%2Ffs%2Fhfs%2Fbtree.c;h=cd5c853473d450f5f03907e58401abb22177f2e3;hb=e44e3482bdb4d0ebde2d8b41830ac2cdb07948fb;hp=0000000000000000000000000000000000000000;hpb=9ca8dbcc65cfc63d6f5ef3312a33184e1d726e00;p=kvmfornfv.git

diff --git a/qemu/roms/openbios/fs/hfs/btree.c b/qemu/roms/openbios/fs/hfs/btree.c
new file mode 100644
index 000000000..cd5c85347
--- /dev/null
+++ b/qemu/roms/openbios/fs/hfs/btree.c
@@ -0,0 +1,230 @@
+/*
+ * 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;
+}