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

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

diff -u --recursive --new-file v2.1.77/linux/fs/hfs/bfind.c linux/fs/hfs/bfind.c
@@ -0,0 +1,322 @@
+/*
+ * linux/fs/hfs/bfind.c
+ *
+ * Copyright (C) 1995, 1996  Paul H. Hargrove
+ * This file may be distributed under the terms of the GNU Public License.
+ *
+ * This file contains the code to access records in a btree.
+ *
+ * "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"
+
+/*================ Global functions ================*/
+
+/*
+ * hfs_brec_relse()
+ *
+ * Description:
+ *   This function releases some of the nodes associated with a brec.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: pointer to the brec to release some nodes from.
+ *   struct hfs_belem *elem: the last node to release or NULL for all
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   void
+ * Preconditions:
+ *   'brec' points to a "valid" (struct hfs_brec)
+ * Postconditions: 
+ *   All nodes between the indicated node and the beginning of the path
+ *    are released.
+ */
+void hfs_brec_relse(struct hfs_brec *brec, struct hfs_belem *elem)
+{
+	if (!elem) {
+		elem = brec->bottom;
+	}
+
+	while (brec->top <= elem) {
+		hfs_bnode_relse(&brec->top->bnr);
+		++brec->top;
+	}
+}
+
+/*
+ * hfs_bfind()
+ *
+ * Description:
+ *   This function has sole responsibility for locating existing
+ *   records in a B-tree.  Given a B-tree and a key it locates the
+ *   "greatest" record "less than or equal to" the given key.  The
+ *   exact behavior is determined by the bits of the flags variable as
+ *   follows:
+ *     ('flags' & HFS_LOCK_MASK):
+ *      The lock_type argument to be used when calling hfs_bnode_find().
+ *     HFS_BFIND_EXACT: only accept an exact match, otherwise take the
+ *	"largest" record less than 'target' as a "match"
+ *     HFS_BFIND_LOCK: request HFS_LOCK_WRITE access to the node containing
+ *	the "matching" record when it is located
+ *     HFS_BPATH_FIRST: keep access to internal nodes when accessing their
+ *      first child.
+ *     HFS_BPATH_OVERFLOW: keep access to internal nodes when the accessed
+ *      child is too full to insert another pointer record.
+ *     HFS_BPATH_UNDERFLOW: keep access to internal nodes when the accessed
+ *      child is would be less than half full upon removing a pointer record.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: pointer to the (struct hfs_brec) to hold
+ *    the search results.
+ *   struct hfs_bkey *target: pointer to the (struct hfs_bkey)
+ *    to search for
+ *   int flags: bitwise OR of flags which determine the function's behavior
+ * Output Variable(s):
+ *   'brec' contains the results of the search on success or is invalid
+ *    on failure.
+ * Returns:
+ *   int: 0 or 1 on success or an error code on failure:
+ *     -EINVAL: one of the input variables was NULL.
+ *     -ENOENT: tree is valid but empty or no "matching" record was located.
+ *	 If the HFS_BFIND_EXACT bit of 'flags' is not set then the case of no
+ *	 matching record will give a 'brec' with a 'record' field of zero
+ *	 rather than returning this error.
+ *     -EIO: an I/O operation or an assertion about the structure of a
+ *       valid B-tree failed indicating corruption of either the B-tree
+ *       structure on the disk or one of the in-core structures representing
+ *       the B-tree.
+ *	 (This could also be returned if a kmalloc() call failed in a
+ *	 subordinate routine that is intended to get the data from the
+ *	 disk or the buffer cache.)
+ * Preconditions:
+ *   'brec' is NULL or points to a (struct hfs_brec) with a 'tree' field
+ *    which points to a valid (struct hfs_btree).
+ *   'target' is NULL or points to a "valid" (struct hfs_bkey)
+ * Postconditions:
+ *   If 'brec', 'brec->tree' or 'target' is NULL then -EINVAL is returned.
+ *   If 'brec', 'brec->tree' and 'target' are non-NULL but the tree
+ *   is empty then -ENOENT is returned.
+ *   If 'brec', 'brec->tree' and 'target' are non-NULL but the call to
+ *   hfs_brec_init() fails then '*brec' is NULL and -EIO is returned.
+ *   If 'brec', 'brec->tree' and 'target' are non-NULL and the tree is
+ *   non-empty then the tree is searched as follows:
+ *    If any call to hfs_brec_next() fails or returns a node that is
+ *     neither an index node nor a leaf node then -EIO is returned to
+ *     indicate that the B-tree or buffer-cache are corrupted.
+ *    If every record in the tree is "greater than" the given key
+ *     and the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned.
+ *    If every record in the tree is "greater than" the given key
+ *     and the HFS_BFIND_EXACT bit of 'flags' is clear then 'brec' refers
+ *     to the first leaf node in the tree and has a 'record' field of
+ *     zero, and 1 is returned.
+ *    If a "matching" record is located with key "equal to" 'target'
+ *     then the return value is 0 and 'brec' indicates the record.
+ *    If a "matching" record is located with key "greater than" 'target'
+ *     then the behavior is determined as follows:
+ *	If the HFS_BFIND_EXACT bit of 'flags' is not set then 1 is returned
+ *       and 'brec' refers to the "matching" record.
+ *	If the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned.
+ *    If the return value is non-negative and the HFS_BFIND_LOCK bit of
+ *     'flags' is set then hfs_brec_lock() is called on the bottom element
+ *     of 'brec' before returning.
+ */
+int hfs_bfind(struct hfs_brec *brec, struct hfs_btree *tree,
+	      const struct hfs_bkey *target, int flags)
+{
+	struct hfs_belem *curr;
+	struct hfs_bkey *key;
+	struct hfs_bnode *bn;
+	int result, ntype;
+
+	/* check for invalid arguments */
+	if (!brec || (tree->magic != HFS_BTREE_MAGIC) || !target) {
+		return -EINVAL;
+	}
+
+	/* check for empty tree */
+	if (!tree->root || !tree->bthNRecs) {
+		return -ENOENT;
+	}
+
+	/* start search at root of tree */
+	if (!(curr = hfs_brec_init(brec, tree, flags))) {
+		return -EIO;
+	}
+
+	/* traverse the tree */
+	do {
+		bn = curr->bnr.bn;
+
+		if (!curr->record) {
+			hfs_warn("hfs_bfind: empty bnode\n");
+			hfs_brec_relse(brec, NULL);
+			return -EIO;
+		}
+
+		/* reverse linear search yielding largest key "less
+		   than or equal to" 'target'.
+		   It is questionable whether a binary search would be
+		   significantly faster */
+		do {
+			key = belem_key(curr);
+			if (!key->KeyLen) {
+				hfs_warn("hfs_bfind: empty key\n");
+				hfs_brec_relse(brec, NULL);
+				return -EIO;
+			}
+			result = (tree->compare)(target, key);
+		} while ((result<0) && (--curr->record));
+
+		ntype = bn->ndType;
+
+		/* see if all keys > target */
+		if (!curr->record) {
+			if (bn->ndBLink) {
+				/* at a node other than the left-most at a
+				   given level it means the parent had an
+				   incorrect key for this child */
+				hfs_brec_relse(brec, NULL);
+				hfs_warn("hfs_bfind: corrupted b-tree %d.\n",
+					 (int)ntohl(tree->entry.cnid));
+				return -EIO;
+			}
+			if (flags & HFS_BFIND_EXACT) {
+				/* we're not going to find it */
+				hfs_brec_relse(brec, NULL);
+				return -ENOENT;
+			}
+			if (ntype == ndIndxNode) {
+				/* since we are at the left-most node at
+				   the current level and looking for the
+				   predecessor of 'target' keep going down */
+				curr->record = 1;
+			} else {
+				/* we're at first leaf so fall through */
+			}
+		}
+
+		/* get next node if necessary */
+		if ((ntype == ndIndxNode) && !(curr = hfs_brec_next(brec))) {
+			return -EIO;
+		}
+	} while (ntype == ndIndxNode);
+
+	if (key->KeyLen > tree->bthKeyLen) {
+		hfs_warn("hfs_bfind: oversized key\n");
+		hfs_brec_relse(brec, NULL);
+		return -EIO;
+	}
+
+	if (ntype != ndLeafNode) {
+		hfs_warn("hfs_bfind: invalid node type %02x in node %d of "
+		         "btree %d\n", bn->ndType, bn->node,
+		         (int)ntohl(tree->entry.cnid));
+		hfs_brec_relse(brec, NULL);
+		return -EIO;
+	}
+
+	if ((flags & HFS_BFIND_EXACT) && result) {
+		hfs_brec_relse(brec, NULL);
+		return -ENOENT;
+	}
+
+	if (!(flags & HFS_BPATH_MASK)) {
+		hfs_brec_relse(brec, brec->bottom-1);
+	}
+
+	if (flags & HFS_BFIND_LOCK) {
+		hfs_brec_lock(brec, brec->bottom);
+	}
+
+	brec->key  = brec_key(brec);
+	brec->data = bkey_record(brec->key);
+
+	return result ? 1 : 0;
+}
+
+/*
+ * hfs_bsucc()
+ *
+ * Description:
+ *   This function overwrites '*brec' with its successor in the B-tree,
+ *   obtaining the same type of access.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: address of the (struct hfs_brec) to overwrite
+ *    with its successor
+ * Output Variable(s):
+ *   struct hfs_brec *brec: address of the successor of the original
+ *    '*brec' or to invalid data
+ * Returns:
+ *   int: 0 on success, or one of -EINVAL, -EIO, or -EINVAL on failure
+ * Preconditions:
+ *   'brec' pointers to a "valid" (struct hfs_brec)
+ * Postconditions:
+ *   If the given '*brec' is not "valid" -EINVAL is returned and
+ *    '*brec' is unchanged.
+ *   If the given 'brec' is "valid" but has no successor then -ENOENT
+ *    is returned and '*brec' is invalid.
+ *   If a call to hfs_bnode_find() is necessary to find the successor,
+ *    but fails then -EIO is returned and '*brec' is invalid.
+ *   If none of the three previous conditions prevents finding the
+ *    successor of '*brec', then 0 is returned, and '*brec' is overwritten
+ *    with the (struct hfs_brec) for its successor.
+ *   In the cases when '*brec' is invalid, the old records is freed.
+ */
+int hfs_bsucc(struct hfs_brec *brec, int count)
+{
+	struct hfs_belem *belem;
+	struct hfs_bnode *bn;
+
+	if (!brec || !(belem = brec->bottom) || (belem != brec->top) ||
+	    !(bn = belem->bnr.bn) || (bn->magic != HFS_BNODE_MAGIC) ||
+	    !bn->tree || (bn->tree->magic != HFS_BTREE_MAGIC) ||
+	    !hfs_buffer_ok(bn->buf)) {
+		hfs_warn("hfs_bsucc: invalid/corrupt arguments.\n");
+		return -EINVAL;
+	}
+
+	while (count) {
+		int left = bn->ndNRecs - belem->record;
+
+		if (left < count) {
+			struct hfs_bnode_ref old;
+			hfs_u32 node;
+
+			/* Advance to next node */
+			if (!(node = bn->ndFLink)) {
+				hfs_brec_relse(brec, belem);
+				return -ENOENT;
+			}
+			if (node == bn->node) {
+				hfs_warn("hfs_bsucc: corrupt btree\n");
+				hfs_brec_relse(brec, belem);
+				return -EIO;
+			}
+			old = belem->bnr;
+			belem->bnr = hfs_bnode_find(brec->tree, node,
+						    belem->bnr.lock_type);
+			hfs_bnode_relse(&old);
+			if (!(bn = belem->bnr.bn)) {
+				return -EIO;
+			}
+			belem->record = 1;
+			count -= (left + 1);
+		} else {
+			belem->record += count;
+			break;
+		}
+	}
+	brec->key  = belem_key(belem);
+	brec->data = bkey_record(brec->key);
+
+	if (brec->key->KeyLen > brec->tree->bthKeyLen) {
+		hfs_warn("hfs_bsucc: oversized key\n");
+		hfs_brec_relse(brec, NULL);
+		return -EIO;
+	}
+
+	return 0;
+}