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

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

diff -u --recursive --new-file v2.1.77/linux/fs/hfs/brec.c linux/fs/hfs/brec.c
@@ -0,0 +1,239 @@
+/*
+ * linux/fs/hfs/brec.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 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"
+
+/*================ File-local functions ================*/
+
+/*
+ * first()
+ *
+ * returns HFS_BPATH_FIRST if elem->record == 1, 0 otherwise
+ */
+static inline int first(const struct hfs_belem *elem)
+{
+	return (elem->record == 1) ? HFS_BPATH_FIRST : 0;
+}
+
+/*
+ * overflow()
+ *
+ * return HFS_BPATH_OVERFLOW if the node has no room for an 
+ * additional pointer record, 0 otherwise.
+ */
+static inline int overflow(const struct hfs_btree *tree,
+			   const struct hfs_bnode *bnode)
+{
+	/* there is some algebra involved in getting this form */
+	return ((HFS_SECTOR_SIZE - sizeof(hfs_u32)) <
+		 (bnode_end(bnode) + (2+bnode->ndNRecs)*sizeof(hfs_u16) +
+		  ROUND(tree->bthKeyLen+1))) ?  HFS_BPATH_OVERFLOW : 0;
+}
+
+/*
+ * underflow()
+ *
+ * return HFS_BPATH_UNDERFLOW if the node will be less that 1/2 full
+ * upon removal of a pointer record, 0 otherwise.
+ */
+static inline int underflow(const struct hfs_btree *tree,
+			    const struct hfs_bnode *bnode)
+{
+	return ((bnode->ndNRecs * sizeof(hfs_u16) +
+		 bnode_offset(bnode, bnode->ndNRecs)) <
+		(HFS_SECTOR_SIZE - sizeof(struct NodeDescriptor))/2) ?
+		HFS_BPATH_UNDERFLOW : 0;
+}
+
+/*================ Global functions ================*/
+
+/*
+ * hfs_brec_next()
+ *
+ * Description:
+ *   Obtain access to a child of an internal node in a B-tree.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: pointer to the (struct hfs_brec) to
+ *    add an element to.
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   struct hfs_belem *: pointer to the new path element or NULL
+ * Preconditions:
+ *   'brec' points to a "valid" (struct hfs_brec), the last element of
+ *   which corresponds to a record in a bnode of type ndIndxNode and the
+ *   'record' field indicates the index record for the desired child.
+ * Postconditions:
+ *   If the call to hfs_bnode_find() fails then 'brec' is released
+ *   and a NULL is returned.
+ *   Otherwise:
+ *    Any ancestors in 'brec' that are not needed (as determined by the
+ *     'keep_flags' field of 'brec) are released from 'brec'.
+ *    A new element is added to 'brec' corresponding to the desired
+ *     child.
+ *    The child is obtained with the same 'lock_type' field as its
+ *     parent.
+ *    The 'record' field is initialized to the last record.
+ *    A pointer to the new path element is returned.
+ */
+struct hfs_belem *hfs_brec_next(struct hfs_brec *brec)
+{
+	struct hfs_belem *elem = brec->bottom;
+	hfs_u32 node;
+	int lock_type;
+
+	/* release unneeded ancestors */
+	elem->flags = first(elem) |
+		      overflow(brec->tree, elem->bnr.bn) |
+		      underflow(brec->tree, elem->bnr.bn);
+	if (!(brec->keep_flags & elem->flags)) {
+		hfs_brec_relse(brec, brec->bottom-1);
+	} else if ((brec->bottom-2 >= brec->top) &&
+		   !(elem->flags & (elem-1)->flags)) {
+		hfs_brec_relse(brec, brec->bottom-2);
+	}
+
+	node = hfs_get_hl(belem_record(elem));
+	lock_type = elem->bnr.lock_type;
+
+	if (!node || hfs_bnode_in_brec(node, brec)) {
+		hfs_warn("hfs_bfind: corrupt btree\n");
+		hfs_brec_relse(brec, NULL);
+		return NULL;
+	}
+
+	++elem;
+	++brec->bottom;
+
+	elem->bnr = hfs_bnode_find(brec->tree, node, lock_type);
+	if (!elem->bnr.bn) {
+		hfs_brec_relse(brec, NULL);
+		return NULL;
+	}
+	elem->record = elem->bnr.bn->ndNRecs;
+
+	return elem;
+}
+
+/*
+ * hfs_brec_lock()
+ *
+ * Description:
+ *   This function obtains HFS_LOCK_WRITE access to the bnode
+ *   containing this hfs_brec.	All descendents in the path from this
+ *   record to the leaf are given HFS_LOCK_WRITE access and all
+ *   ancestors in the path from the root to here are released.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: pointer to the brec to obtain
+ *    HFS_LOCK_WRITE access to some of the nodes of.
+ *   struct hfs_belem *elem: the first node to lock 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.  hfs_bnode_lock() is called in turn on each node
+ *    from the indicated node to the leaf node of the path, with a
+ *    lock_type argument of HFS_LOCK_WRITE.  If one of those calls
+ *    results in deadlock, then this function will never return.
+ */
+void hfs_brec_lock(struct hfs_brec *brec, struct hfs_belem *elem) 
+{
+	if (!elem) {
+		elem = brec->top;
+	} else if (elem > brec->top) {
+		hfs_brec_relse(brec, elem-1);
+	}
+
+	while (elem <= brec->bottom) {
+		hfs_bnode_lock(&elem->bnr, HFS_LOCK_WRITE);
+		++elem;
+	}
+}
+
+/*
+ * hfs_brec_init()
+ *
+ * Description:
+ *   Obtain access to the root node of a B-tree.
+ *   Note that this first must obtain access to the header node.
+ * Input Variable(s):
+ *   struct hfs_brec *brec: pointer to the (struct hfs_brec) to
+ *    initialize
+ *   struct hfs_btree *btree: pointer to the (struct hfs_btree)
+ *   int lock_type: the type of access to get to the nodes.
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   struct hfs_belem *: pointer to the root path element or NULL
+ * Preconditions:
+ *   'brec' points to a (struct hfs_brec).
+ *   'tree' points to a valid (struct hfs_btree).
+ * Postconditions:
+ *   If the two calls to brec_bnode_find() succeed then the return value
+ *   points to a (struct hfs_belem) which corresponds to the root node
+ *   of 'brec->tree'.
+ *   Both the root and header nodes are obtained with the type of lock
+ *   given by (flags & HFS_LOCK_MASK).
+ *   The fields 'record' field of the root is set to its last record.
+ *   If the header node is not needed to complete the appropriate
+ *   operation (as determined by the 'keep_flags' field of 'brec') then
+ *   it is released before this function returns.
+ *   If either call to brec_bnode_find() fails, NULL is returned and the
+ *   (struct hfs_brec) pointed to by 'brec' is invalid.
+ */
+struct hfs_belem *hfs_brec_init(struct hfs_brec *brec, struct hfs_btree *tree,
+				int flags)
+{
+	struct hfs_belem *head = &brec->elem[0];
+	struct hfs_belem *root = &brec->elem[1];
+	int lock_type = flags & HFS_LOCK_MASK;
+
+	brec->tree = tree;
+
+	head->bnr = hfs_bnode_find(tree, 0, lock_type);
+	if (!head->bnr.bn) {
+		return NULL;
+	}
+
+	root->bnr = hfs_bnode_find(tree, tree->bthRoot, lock_type);
+	if (!root->bnr.bn) {
+		hfs_bnode_relse(&head->bnr);
+		return NULL;
+	}
+
+	root->record = root->bnr.bn->ndNRecs;
+	
+	brec->top = head;
+	brec->bottom = root;
+	
+	brec->keep_flags = flags & HFS_BPATH_MASK;
+
+	/* HFS_BPATH_FIRST not applicable for root */
+	/* and HFS_BPATH_UNDERFLOW is different */
+	root->flags = overflow(tree, root->bnr.bn);
+	if (root->record < 3) {
+		root->flags |= HFS_BPATH_UNDERFLOW;
+	}
+
+	if (!(root->flags & brec->keep_flags)) {
+		hfs_brec_relse(brec, head);
+	}
+
+	return root;
+}