summaryrefslogtreecommitdiff
path: root/libhfs_iso/node.c
diff options
context:
space:
mode:
Diffstat (limited to 'libhfs_iso/node.c')
-rw-r--r--libhfs_iso/node.c473
1 files changed, 473 insertions, 0 deletions
diff --git a/libhfs_iso/node.c b/libhfs_iso/node.c
new file mode 100644
index 0000000..8fce735
--- /dev/null
+++ b/libhfs_iso/node.c
@@ -0,0 +1,473 @@
+/*
+ * 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.
+ *
+ */
+
+/* @(#)node.c 1.2 02/02/10 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 "btree.h"
+#include "node.h"
+
+# define NODESPACE(n) \
+ (HFS_BLOCKSZ - (n).roff[(n).nd.ndNRecs] - 2 * ((n).nd.ndNRecs + 1))
+
+/*
+ * NAME: node->init()
+ * DESCRIPTION: construct an empty node
+ */
+void n_init(node *np, btree *bt, int type, int height)
+{
+ np->bt = bt;
+ np->nnum = -1;
+
+ np->nd.ndFLink = 0;
+ np->nd.ndBLink = 0;
+ np->nd.ndType = type;
+ np->nd.ndNHeight = height;
+ np->nd.ndNRecs = 0;
+ np->nd.ndResv2 = 0;
+
+ np->rnum = -1;
+ np->roff[0] = 0x00e;
+
+ memset(np->data, 0, sizeof(np->data));
+}
+
+/*
+ * NAME: node->new()
+ * DESCRIPTION: allocate a new b*-tree node
+ */
+int n_new(node *np)
+{
+ btree *bt = np->bt;
+ unsigned long num;
+
+ if (bt->hdr.bthFree == 0)
+ {
+ ERROR(EIO, "b*-tree full");
+ return -1;
+ }
+
+ num = 0;
+ while (num < bt->hdr.bthNNodes && BMTST(bt->map, num))
+ ++num;
+
+ if (num == bt->hdr.bthNNodes)
+ {
+ ERROR(EIO, "free b*-tree node not found");
+ return -1;
+ }
+
+ np->nnum = num;
+
+ BMSET(bt->map, num);
+ --bt->hdr.bthFree;
+
+ bt->flags |= HFS_UPDATE_BTHDR;
+
+ return 0;
+}
+
+/*
+ * NAME: node->free()
+ * DESCRIPTION: deallocate a b*-tree node
+ */
+void n_free(node *np)
+{
+ btree *bt = np->bt;
+
+ BMCLR(bt->map, np->nnum);
+ ++bt->hdr.bthFree;
+
+ bt->flags |= HFS_UPDATE_BTHDR;
+}
+
+/*
+ * NAME: node->compact()
+ * DESCRIPTION: clean up a node, removing deleted records
+ */
+void n_compact(node *np)
+{
+ unsigned char *ptr;
+ int offset, nrecs, i;
+
+ offset = 0x00e;
+ ptr = np->data + offset;
+ nrecs = 0;
+
+ for (i = 0; i < (int)np->nd.ndNRecs; ++i)
+ {
+ unsigned char *rec;
+ int reclen;
+
+ rec = HFS_NODEREC(*np, i);
+ reclen = np->roff[i + 1] - np->roff[i];
+
+ if (HFS_RECKEYLEN(rec) > 0)
+ {
+ np->roff[nrecs++] = offset;
+ offset += reclen;
+
+ if (ptr == rec)
+ ptr += reclen;
+ else
+ {
+ while (reclen--)
+ *ptr++ = *rec++;
+ }
+ }
+ }
+
+ np->roff[nrecs] = offset;
+ np->nd.ndNRecs = nrecs;
+}
+
+/*
+ * NAME: node->search()
+ * DESCRIPTION: locate a record in a node, or the record it should follow
+ */
+int n_search(node *np, unsigned char *key)
+{
+ btree *bt = np->bt;
+ int i, comp = -1;
+
+ for (i = np->nd.ndNRecs; i--; )
+ {
+ unsigned char *rec;
+
+ rec = HFS_NODEREC(*np, i);
+
+ if (HFS_RECKEYLEN(rec) == 0)
+ continue; /* deleted record */
+
+ comp = bt->compare(rec, key);
+
+ if (comp <= 0)
+ break;
+ }
+
+ np->rnum = i;
+
+ return comp == 0;
+}
+
+/*
+ * NAME: node->index()
+ * DESCRIPTION: create an index record from a key and node pointer
+ */
+void n_index(btree *bt, unsigned char *key, unsigned long nnum,
+ unsigned char *record, int *reclen)
+{
+ if (bt == &bt->f.vol->cat)
+ {
+ /* force the key length to be 0x25 */
+
+ HFS_RECKEYLEN(record) = 0x25;
+ memset(record + 1, 0, 0x25);
+ memcpy(record + 1, key + 1, HFS_RECKEYLEN(key));
+ }
+ else
+ memcpy(record, key, HFS_RECKEYSKIP(key));
+
+ d_putl(HFS_RECDATA(record), nnum);
+
+ if (reclen)
+ *reclen = HFS_RECKEYSKIP(record) + 4;
+}
+
+/*
+ * NAME: node->split()
+ * DESCRIPTION: divide a node into two and insert a record
+ */
+int n_split(node *left, unsigned char *record, int *reclen)
+{
+ node right;
+ int nrecs, i, mid;
+ unsigned char *rec;
+
+ right = *left;
+ right.nd.ndBLink = left->nnum;
+
+ if (n_new(&right) < 0)
+ return -1;
+
+ left->nd.ndFLink = right.nnum;
+ nrecs = left->nd.ndNRecs;
+
+ /*
+ * Ensure node split leaves enough room for new record.
+ * The size calculations used are based on the NODESPACE() macro, but
+ * I don't know what the extra 2's and 1's are needed for.
+ * John Witford <jwitford@hutch.com.au>
+ */
+ n_search(&right, record);
+ mid = nrecs/2;
+ for(;;)
+ {
+ if (right.rnum < mid)
+ {
+ if ( mid > 0
+ && (int)left->roff[mid] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
+ {
+ --mid;
+ if (mid > 0)
+ continue;
+ }
+ }
+ else
+ {
+ if ( mid < nrecs
+ && (int)right.roff[nrecs] - (int)right.roff[mid] + (int)left->roff[0] + *reclen + 2 > HFS_BLOCKSZ - 2 * (mid + 1))
+ {
+ ++mid;
+ if (mid < nrecs)
+ continue;
+ }
+ }
+ break;
+ }
+
+ for (i = 0; i < nrecs; ++i)
+ {
+ if (i < mid)
+ rec = HFS_NODEREC(right, i);
+ else
+ rec = HFS_NODEREC(*left, i);
+
+ HFS_RECKEYLEN(rec) = 0;
+ }
+
+/* original code ...
+ for (i = 0; i < nrecs; ++i)
+ {
+ if (i < nrecs / 2)
+ rec = HFS_NODEREC(right, i);
+ else
+ rec = HFS_NODEREC(*left, i);
+
+ HFS_RECKEYLEN(rec) = 0;
+ }
+*/
+ n_compact(left);
+ n_compact(&right);
+
+ n_search(&right, record);
+ if (right.rnum >= 0)
+ n_insertx(&right, record, *reclen);
+ else
+ {
+ n_search(left, record);
+ n_insertx(left, record, *reclen);
+ }
+
+ /* store the new/modified nodes */
+
+ if (bt_putnode(left) < 0 ||
+ bt_putnode(&right) < 0)
+ return -1;
+
+ /* create an index record for the new node in the parent */
+
+ n_index(right.bt, HFS_NODEREC(right, 0), right.nnum, record, reclen);
+
+ /* update link pointers */
+
+ if (left->bt->hdr.bthLNode == left->nnum)
+ {
+ left->bt->hdr.bthLNode = right.nnum;
+ left->bt->flags |= HFS_UPDATE_BTHDR;
+ }
+
+ if (right.nd.ndFLink)
+ {
+ node n;
+
+ n.bt = right.bt;
+ n.nnum = right.nd.ndFLink;
+
+ if (bt_getnode(&n) < 0)
+ return -1;
+
+ n.nd.ndBLink = right.nnum;
+
+ if (bt_putnode(&n) < 0)
+ return -1;
+ }
+
+ return 0;
+}
+
+/*
+ * NAME: node->insertx()
+ * DESCRIPTION: insert a record into a node (which must already have room)
+ */
+void n_insertx(node *np, unsigned char *record, int reclen)
+{
+ int rnum, i;
+ unsigned char *ptr;
+
+ rnum = np->rnum + 1;
+
+ /* push other records down to make room */
+
+ for (ptr = HFS_NODEREC(*np, np->nd.ndNRecs) + reclen;
+ ptr > HFS_NODEREC(*np, rnum) + reclen; --ptr)
+ *(ptr - 1) = *(ptr - 1 - reclen);
+
+ ++np->nd.ndNRecs;
+
+ for (i = np->nd.ndNRecs; i > rnum; --i)
+ np->roff[i] = np->roff[i - 1] + reclen;
+
+ /* write the new record */
+
+ memcpy(HFS_NODEREC(*np, rnum), record, reclen);
+}
+
+/*
+ * NAME: node->insert()
+ * DESCRIPTION: insert a new record into a node; return a record for parent
+ */
+int n_insert(node *np, unsigned char *record, int *reclen)
+{
+ n_compact(np);
+
+ /* check for free space */
+
+ if (np->nd.ndNRecs >= HFS_MAXRECS ||
+ *reclen + 2 > (int)NODESPACE(*np))
+ return n_split(np, record, reclen);
+
+ n_insertx(np, record, *reclen);
+ *reclen = 0;
+
+ return bt_putnode(np);
+}
+
+/*
+ * NAME: node->merge()
+ * DESCRIPTION: combine two nodes into a single node
+ */
+int n_merge(node *right, node *left, unsigned char *record, int *flag)
+{
+ int i, offset;
+
+ /* copy records and offsets */
+
+ memcpy(HFS_NODEREC(*left, left->nd.ndNRecs), HFS_NODEREC(*right, 0),
+ right->roff[right->nd.ndNRecs] - right->roff[0]);
+
+ offset = left->roff[left->nd.ndNRecs] - right->roff[0];
+
+ for (i = 1; i <= (int)right->nd.ndNRecs; ++i)
+ left->roff[++left->nd.ndNRecs] = offset + right->roff[i];
+
+ /* update link pointers */
+
+ left->nd.ndFLink = right->nd.ndFLink;
+
+ if (bt_putnode(left) < 0)
+ return -1;
+
+ if (right->bt->hdr.bthLNode == right->nnum)
+ {
+ right->bt->hdr.bthLNode = left->nnum;
+ right->bt->flags |= HFS_UPDATE_BTHDR;
+ }
+
+ if (right->nd.ndFLink)
+ {
+ node n;
+
+ n.bt = right->bt;
+ n.nnum = right->nd.ndFLink;
+
+ if (bt_getnode(&n) < 0)
+ return -1;
+
+ n.nd.ndBLink = left->nnum;
+
+ if (bt_putnode(&n) < 0)
+ return -1;
+ }
+
+ n_free(right);
+
+ HFS_RECKEYLEN(record) = 0;
+ *flag = 1;
+
+ return 0;
+}
+
+/*
+ * NAME: node->delete()
+ * DESCRIPTION: remove a record from a node
+ */
+int n_delete(node *np, unsigned char *record, int *flag)
+{
+ node left;
+ unsigned char *rec;
+
+ rec = HFS_NODEREC(*np, np->rnum);
+
+ HFS_RECKEYLEN(rec) = 0;
+ n_compact(np);
+
+ /* see if we can merge with our left sibling */
+
+ left.bt = np->bt;
+ left.nnum = np->nd.ndBLink;
+
+ if (left.nnum > 0)
+ {
+ if (bt_getnode(&left) < 0)
+ return -1;
+
+ if ((int)(np->nd.ndNRecs + left.nd.ndNRecs) <= HFS_MAXRECS &&
+ (int)(np->roff[np->nd.ndNRecs] - np->roff[0] +
+ 2 * np->nd.ndNRecs) <= (int)NODESPACE(left))
+ return n_merge(np, &left, record, flag);
+ }
+
+ if (np->rnum == 0)
+ {
+ /* special case: first record changed; update parent record key */
+
+ n_index(np->bt, HFS_NODEREC(*np, 0), np->nnum, record, 0);
+ *flag = 1;
+ }
+
+ return bt_putnode(np);
+}