patch-2.1.78 linux/fs/hfs/bins_del.c

• Lines: 232
• Date: Sun Jan 4 10:40:17 1998
• Orig file: v2.1.77/linux/fs/hfs/bins_del.c
• Orig date: Wed Dec 31 16:00:00 1969

diff -u --recursive --new-file v2.1.77/linux/fs/hfs/bins_del.c linux/fs/hfs/bins_del.c
@@ -0,0 +1,231 @@
+/*
+ * linux/fs/hfs/bins_del.c
+ *
+ * Copyright (C) 1995-1997  Paul H. Hargrove
+ * This file may be distributed under the terms of the GNU Public License.
+ *
+ * This file contains the code common to inserting and deleting records
+ * in a B-tree.
+ *
+ * "XXX" in a comment is a note to myself to consider changing something.
+ *
+ * In function preconditions the term "valid" applied to a pointer to
+ * a structure means that the pointer is non-NULL and the structure it
+ * points to has all fields initialized to consistent values.
+ */
+
+#include "hfs_btree.h"
+
+/*================ File-local functions ================*/
+
+/*
+ * hfs_bnode_update_key()
+ *
+ * Description:
+ *   Updates the key for a bnode in its parent.
+ *   The key change is propagated up the tree as necessary.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: the search path to update keys in
+ *   struct hfs_belem *belem: the search path element with the changed key
+ *   struct hfs_bnode *bnode: the bnode with the changed key
+ *   int offset: the "distance" from 'belem->bn' to 'bnode':
+ *    0 if the change is in 'belem->bn',
+ *    1 if the change is in its right sibling, etc.
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   void
+ * Preconditions:
+ *   'brec' points to a valid (struct hfs_brec)
+ *   'belem' points to a valid (struct hfs_belem) in 'brec'.
+ *   'bnode' points to a valid (struct hfs_bnode) which is non-empty
+ *    and is 'belem->bn' or one of its siblings.
+ *   'offset' is as described above.
+ * Postconditions:
+ *   The key change is propagated up the tree as necessary.
+ */
+void hfs_bnode_update_key(struct hfs_brec *brec, struct hfs_belem *belem,
+			  struct hfs_bnode *bnode, int offset)
+{
+	int record = (--belem)->record + offset;
+	void *key = bnode_datastart(bnode) + 1;
+	int keysize = brec->tree->bthKeyLen;
+	struct hfs_belem *limit;
+
+  	memcpy(1+bnode_key(belem->bnr.bn, record), key, keysize);
+
+	/* don't trash the header */
+	if (brec->top > &brec->elem[1]) {
+		limit = brec->top;
+	} else {
+		limit = &brec->elem[1];
+	}
+
+	while ((belem > limit) && (record == 1)) {
+		record = (--belem)->record;
+		memcpy(1+belem_key(belem), key, keysize);
+	}
+}
+
+/*
+ * hfs_bnode_shift_right()
+ *
+ * Description:
+ *   Shifts some records from a node to its right neighbor.
+ * Input Variable(s):
+ *   struct hfs_bnode* left: the node to shift records from
+ *   struct hfs_bnode* right: the node to shift records to
+ *   hfs_u16 first: the number of the first record in 'left' to move to 'right'
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   void
+ * Preconditions:
+ *   'left' and 'right' point to valid (struct hfs_bnode)s.
+ *   'left' contains at least 'first' records.
+ *   'right' has enough free space to hold the records to be moved from 'left'
+ * Postconditions:
+ *   The record numbered 'first' and all records after it in 'left' are
+ *   placed at the beginning of 'right'.
+ *   The key corresponding to 'right' in its parent is NOT updated.
+ */
+void hfs_bnode_shift_right(struct hfs_bnode *left, struct hfs_bnode *right,
+			   int first)
+{
+	int i, adjust, nrecs;
+	unsigned size;
+	hfs_u16 *to, *from;
+
+	if ((first <= 0) || (first > left->ndNRecs)) {
+		hfs_warn("bad argument to shift_right: first=%d, nrecs=%d\n",
+		       first, left->ndNRecs);
+		return;
+	}
+
+	/* initialize variables */
+	nrecs = left->ndNRecs + 1 - first;
+	size = bnode_end(left) - bnode_offset(left, first);
+
+	/* move (possibly empty) contents of right node forward */
+	memmove(bnode_datastart(right) + size,
+		bnode_datastart(right), 
+		bnode_end(right) - sizeof(struct NodeDescriptor));
+
+	/* copy in new records */
+	memcpy(bnode_datastart(right), bnode_key(left,first), size);
+
+	/* fix up offsets in right node */
+	i = right->ndNRecs + 1;
+	from = RECTBL(right, i);
+	to = from - nrecs;
+	while (i--) {
+		hfs_put_hs(hfs_get_hs(from++) + size, to++);
+	}
+	adjust = sizeof(struct NodeDescriptor) - bnode_offset(left, first);
+	i = nrecs-1;
+	from = RECTBL(left, first+i);
+	while (i--) {
+		hfs_put_hs(hfs_get_hs(from++) + adjust, to++);
+	}
+
+	/* fix record counts */
+	left->ndNRecs -= nrecs;
+	right->ndNRecs += nrecs;
+}
+
+/*
+ * hfs_bnode_shift_left()
+ *
+ * Description:
+ *   Shifts some records from a node to its left neighbor.
+ * Input Variable(s):
+ *   struct hfs_bnode* left: the node to shift records to
+ *   struct hfs_bnode* right: the node to shift records from
+ *   hfs_u16 last: the number of the last record in 'right' to move to 'left'
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   void
+ * Preconditions:
+ *   'left' and 'right' point to valid (struct hfs_bnode)s.
+ *   'right' contains at least 'last' records.
+ *   'left' has enough free space to hold the records to be moved from 'right'
+ * Postconditions:
+ *   The record numbered 'last' and all records before it in 'right' are
+ *   placed at the end of 'left'.
+ *   The key corresponding to 'right' in its parent is NOT updated.
+ */
+void hfs_bnode_shift_left(struct hfs_bnode *left, struct hfs_bnode *right,
+			  int last)
+{
+	int i, adjust, nrecs;
+	unsigned size;
+	hfs_u16 *to, *from;
+
+	if ((last <= 0) || (last > right->ndNRecs)) {
+		hfs_warn("bad argument to shift_left: last=%d, nrecs=%d\n",
+		       last, right->ndNRecs);
+		return;
+	}
+
+	/* initialize variables */
+	size = bnode_offset(right, last + 1) - sizeof(struct NodeDescriptor);
+
+	/* copy records to left node */
+	memcpy(bnode_dataend(left), bnode_datastart(right), size);
+
+	/* move (possibly empty) remainder of right node backward */
+	memmove(bnode_datastart(right), bnode_datastart(right) + size, 
+			bnode_end(right) - bnode_offset(right, last + 1));
+
+	/* fix up offsets */
+	nrecs = left->ndNRecs;
+	i = last;
+	from = RECTBL(right, 2);
+	to = RECTBL(left, nrecs + 2);
+	adjust = bnode_offset(left, nrecs + 1) - sizeof(struct NodeDescriptor);
+	while (i--) {
+		hfs_put_hs(hfs_get_hs(from--) + adjust, to--);
+	}
+	i = right->ndNRecs + 1 - last;
+	++from;
+	to = RECTBL(right, 1);
+	while (i--) {
+		hfs_put_hs(hfs_get_hs(from--) - size, to--);
+	}
+
+	/* fix record counts */
+	left->ndNRecs += last;
+	right->ndNRecs -= last;
+}
+
+/*
+ * hfs_bnode_in_brec()
+ *
+ * Description:
+ *   Determines whethet a given bnode is part of a given brec.
+ *   This is used to avoid deadlock in the case of a corrupted b-tree.
+ * Input Variable(s):
+ *   hfs_u32 node: the number of the node to check for.
+ *   struct hfs_brec* brec: the brec to check in.
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   int: 1 it found, 0 if not
+ * Preconditions:
+ *   'brec' points to a valid struct hfs_brec.
+ * Postconditions:
+ *   'brec' is unchanged.
+ */
+int hfs_bnode_in_brec(hfs_u32 node, const struct hfs_brec *brec)
+{
+	const struct hfs_belem *belem = brec->bottom;
+
+	while (belem && (belem >= brec->top)) {
+		if (belem->bnr.bn && (belem->bnr.bn->node == node)) {
+			return 1;
+		}
+		--belem;
+	}
+	return 0;
+}