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

Next file: linux/fs/hfs/bitmap.c
Previous file: linux/fs/hfs/bins_del.c
Back to the patch index
Back to the overall index

diff -u --recursive --new-file v2.1.77/linux/fs/hfs/binsert.c linux/fs/hfs/binsert.c
@@ -0,0 +1,541 @@
+/*
+ * linux/fs/hfs/binsert.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 insert 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 ================*/
+
+/*
+ * binsert_nonfull()
+ *
+ * Description:
+ *   Inserts a record in a given bnode known to have sufficient space.
+ * Input Variable(s):
+ *   struct hfs_brec* brec: pointer to the brec for the insertion
+ *   struct hfs_belem* belem: the element in the search path to insert in
+ *   struct hfs_bkey* key: pointer to the key for the record to insert
+ *   void* data: pointer to the record to insert
+ *   hfs_u16 keysize: size of the key to insert
+ *   hfs_u16 datasize: size of the record to insert
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   NONE
+ * Preconditions:
+ *   'brec' points to a valid (struct hfs_brec).
+ *   'belem' points to a valid (struct hfs_belem) in 'brec', the node
+ *    of which has enough free space to insert 'key' and 'data'.
+ *   'key' is a pointer to a valid (struct hfs_bkey) of length 'keysize'
+ *    which, in sorted order, belongs at the location indicated by 'brec'.
+ *   'data' is non-NULL an points to appropriate data of length 'datasize'
+ * Postconditions:
+ *   The record has been inserted in the position indicated by 'brec'.
+ */
+static void binsert_nonfull(struct hfs_brec *brec, struct hfs_belem *belem,
+			    const struct hfs_bkey *key, const void *data,
+			    hfs_u8 keysize, hfs_u16 datasize)
+{
+	int i, rec, nrecs, size, tomove;
+	hfs_u8 *start;
+	struct hfs_bnode *bnode = belem->bnr.bn;
+
+	rec = ++(belem->record);
+	size = ROUND(keysize+1) + datasize;
+	nrecs = bnode->ndNRecs + 1;
+	tomove = bnode_offset(bnode, nrecs) - bnode_offset(bnode, rec);
+	
+	/* adjust the record table */
+	for (i = nrecs; i >= rec; --i) {
+		hfs_put_hs(bnode_offset(bnode,i) + size, RECTBL(bnode,i+1));
+	}
+
+	/* make room */
+	start = bnode_key(bnode, rec);
+	memmove(start + size, start, tomove);
+
+	/* copy in the key and the data*/
+	*start = keysize;
+	keysize = ROUND(keysize+1);
+	memcpy(start + 1, (hfs_u8 *)key + 1, keysize-1);
+	memcpy(start + keysize, data, datasize);
+
+	/* update record count */
+	++bnode->ndNRecs;
+}
+
+/*
+ * add_root()
+ *
+ * Description:
+ *   Adds a new root to a B*-tree, increasing its height.
+ * Input Variable(s):
+ *   struct hfs_btree *tree: the tree to add a new root to
+ *   struct hfs_bnode *left: the new root's first child or NULL
+ *   struct hfs_bnode *right: the new root's second child or NULL
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   void
+ * Preconditions:
+ *   'tree' points to a valid (struct hfs_btree).
+ *   'left' and 'right' point to valid (struct hfs_bnode)s, which
+ *    resulted from splitting the old root node, or are both NULL
+ *    if there was no root node before.
+ * Postconditions:
+ *   Upon success a new root node is added to 'tree' with either
+ *    two children ('left' and 'right') or none.
+ */
+static void add_root(struct hfs_btree *tree,
+		     struct hfs_bnode *left,
+		     struct hfs_bnode *right)
+{
+	struct hfs_bnode_ref bnr;
+	struct hfs_bnode *root;
+	struct hfs_bkey *key;
+	int keylen = tree->bthKeyLen;
+
+	if (left && !right) {
+		hfs_warn("add_root: LEFT but no RIGHT\n");
+		return;
+	}
+
+	bnr = hfs_bnode_alloc(tree);
+	if (!(root = bnr.bn)) {
+		return;
+	}
+
+	root->sticky = HFS_STICKY;
+	tree->root = root;
+	tree->bthRoot = root->node;
+	++tree->bthDepth;
+
+	root->ndNHeight = tree->bthDepth;
+	root->ndFLink = 0;
+	root->ndBLink = 0;
+
+	if (!left) {
+		/* tree was empty */
+		root->ndType  = ndLeafNode;
+		root->ndNRecs = 0;
+
+		tree->bthFNode = root->node;
+		tree->bthLNode = root->node;
+	} else {
+		root->ndType  = ndIndxNode;
+		root->ndNRecs = 2;
+
+		hfs_put_hs(sizeof(struct NodeDescriptor) + ROUND(1+keylen) +
+			   sizeof(hfs_u32), RECTBL(root, 2));
+		key = bnode_key(root, 1);
+		key->KeyLen = keylen;
+		memcpy(key->value,
+		       ((struct hfs_bkey *)bnode_key(left, 1))->value, keylen);
+		hfs_put_hl(left->node, bkey_record(key));
+		
+		hfs_put_hs(sizeof(struct NodeDescriptor) + 2*ROUND(1+keylen) +
+			   2*sizeof(hfs_u32), RECTBL(root, 3));
+		key = bnode_key(root, 2);
+		key->KeyLen = keylen;
+		memcpy(key->value,
+		       ((struct hfs_bkey *)bnode_key(right, 1))->value, keylen);
+		hfs_put_hl(right->node, bkey_record(key));
+
+		/* the former root (left) is now just a normal node */
+		left->sticky = HFS_NOT_STICKY;
+		if ((left->next = bhash(tree, left->node))) {
+			left->next->prev = left;
+		}
+		bhash(tree, left->node) = left;
+	}
+	hfs_bnode_relse(&bnr);
+	tree->dirt = 1;
+}
+
+/*
+ * insert_empty_bnode()
+ *
+ * Description:
+ *   Adds an empty node to the right of 'left'.
+ * Input Variable(s):
+ *   struct hfs_btree *tree: the tree to add a node to
+ *   struct hfs_bnode *left: the node to add a node after
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   struct hfs_bnode_ref *: reference to the new bnode.
+ * Preconditions:
+ *   'tree' points to a valid (struct hfs_btree) with at least 1 free node.
+ *   'left' points to a valid (struct hfs_bnode) belonging to 'tree'.
+ * Postconditions:
+ *   If NULL is returned then 'tree' and 'left' are unchanged.
+ *   Otherwise a node with 0 records is inserted in the tree to the right
+ *   of the node 'left'.  The 'ndFLink' of 'left' and the 'ndBLink' of
+ *   the former right-neighbor of 'left' (if one existed) point to the
+ *   new node.	If 'left' had no right neighbor and is a leaf node the
+ *   the 'bthLNode' of 'tree' points to the new node.  The free-count and
+ *   bitmap for 'tree' are kept current by hfs_bnode_alloc() which supplies
+ *   the required node.
+ */
+static struct hfs_bnode_ref insert_empty_bnode(struct hfs_btree *tree,
+					       struct hfs_bnode *left)
+{
+	struct hfs_bnode_ref retval;
+	struct hfs_bnode_ref right;
+
+	retval = hfs_bnode_alloc(tree);
+	if (!retval.bn) {
+		hfs_warn("hfs_binsert: out of bnodes?.\n");
+		goto done;
+	}
+	retval.bn->sticky = HFS_NOT_STICKY;
+	if ((retval.bn->next = bhash(tree, retval.bn->node))) {
+		retval.bn->next->prev = retval.bn;
+	}
+	bhash(tree, retval.bn->node) = retval.bn;
+
+	if (left->ndFLink) {
+		right = hfs_bnode_find(tree, left->ndFLink, HFS_LOCK_WRITE);
+		if (!right.bn) {
+			hfs_warn("hfs_binsert: corrupt btree.\n");
+			hfs_bnode_bitop(tree, retval.bn->node, 0);
+			hfs_bnode_relse(&retval);
+			goto done;
+		}
+		right.bn->ndBLink = retval.bn->node;
+		hfs_bnode_relse(&right);
+	} else if (left->ndType == ndLeafNode) {
+		tree->bthLNode = retval.bn->node;
+		tree->dirt = 1;
+	}
+
+	retval.bn->ndFLink   = left->ndFLink;
+	retval.bn->ndBLink   = left->node;
+	retval.bn->ndType    = left->ndType;
+	retval.bn->ndNHeight = left->ndNHeight;
+	retval.bn->ndNRecs   = 0;
+
+	left->ndFLink = retval.bn->node;
+
+ done:
+	return retval;
+}
+
+/*
+ * split()
+ *
+ * Description:
+ *   Splits an over full node during insertion.
+ *   Picks the split point that results in the most-nearly equal
+ *   space usage in the new and old nodes.
+ * Input Variable(s):
+ *   struct hfs_belem *elem: the over full node.
+ *   int size: the number of bytes to be used by the new record and its key.
+ * Output Variable(s):
+ *   struct hfs_belem *elem: changed to indicate where the new record
+ *    should be inserted.
+ * Returns:
+ *   struct hfs_bnode_ref: reference to the new bnode.
+ * Preconditions:
+ *   'elem' points to a valid path element corresponding to the over full node.
+ *   'size' is positive.
+ * Postconditions:
+ *   The records in the node corresponding to 'elem' are redistributed across
+ *   the old and new nodes so that after inserting the new record, the space
+ *   usage in these two nodes is as equal as possible.
+ *   'elem' is updated so that a call to binsert_nonfull() will insert the
+ *   new record in the correct location.
+ */
+static inline struct hfs_bnode_ref split(struct hfs_belem *elem, int size)
+{
+	struct hfs_bnode *bnode = elem->bnr.bn;
+	int nrecs, cutoff, index, tmp, used, in_right;
+	struct hfs_bnode_ref right;
+
+	right = insert_empty_bnode(bnode->tree, bnode);
+	if (right.bn) {
+		nrecs = bnode->ndNRecs;
+		cutoff = (size + bnode_end(bnode) -
+			      sizeof(struct NodeDescriptor) +
+			      (nrecs+1)*sizeof(hfs_u16))/2;
+		used = 0;
+		in_right = 1;
+		/* note that this only works because records sizes are even */
+		for (index=1; index <= elem->record; ++index) {
+			tmp = (sizeof(hfs_u16) + bnode_rsize(bnode, index))/2;
+			used += tmp;
+			if (used > cutoff) {
+				goto found;
+			}
+			used += tmp;
+		}
+		tmp = (size + sizeof(hfs_u16))/2;
+		used += tmp;
+		if (used > cutoff) {
+			goto found;
+		}
+		in_right = 0;
+		used += tmp;
+		for (; index <= nrecs; ++index) {
+			tmp = (sizeof(hfs_u16) + bnode_rsize(bnode, index))/2;
+			used += tmp;
+			if (used > cutoff) {
+				goto found;
+			}
+			used += tmp;
+		}
+		/* couldn't find the split point! */
+		hfs_bnode_relse(&right);
+	}
+	return right;
+
+found:
+	if (in_right) {
+		elem->bnr = right;
+		elem->record -= index-1;
+	}
+	hfs_bnode_shift_right(bnode, right.bn, index);
+
+	return right;
+}
+
+/*
+ * binsert()
+ *
+ * Description:
+ *   Inserts a record in a tree known to have enough room, even if the
+ *   insertion requires the splitting of nodes.
+ * Input Variable(s):
+ *    struct hfs_brec *brec: partial path to the node to insert in
+ *    const struct hfs_bkey *key: key for the new record
+ *    const void *data: data for the new record
+ *    hfs_u8 keysize: size of the key
+ *    hfs_u16 datasize: size of the data
+ *    int reserve: number of nodes reserved in case of splits
+ * Output Variable(s):
+ *    *brec = NULL
+ * Returns:
+ *    int: 0 on success, error code on failure
+ * Preconditions:
+ *    'brec' points to a valid (struct hfs_brec) corresponding to a
+ *     record in a leaf node, after which a record is to be inserted,
+ *     or to "record 0" of the leaf node if the record is to be inserted
+ *     before all existing records in the node.	 The (struct hfs_brec)
+ *     includes all ancestors of the leaf node that are needed to
+ *     complete the insertion including the parents of any nodes that
+ *     will be split.
+ *    'key' points to a valid (struct hfs_bkey) which is appropriate
+ *     to this tree, and which belongs at the insertion point.
+ *    'data' points data appropriate for the indicated node.
+ *    'keysize' gives the size in bytes of the key.
+ *    'datasize' gives the size in bytes of the data.
+ *    'reserve' gives the number of nodes that have been reserved in the
+ *     tree to allow for splitting of nodes.
+ * Postconditions:
+ *    All 'reserve'd nodes have been either used or released.
+ *    *brec = NULL
+ *    On success the key and data have been inserted at the indicated
+ *    location in the tree, all appropriate fields of the in-core data
+ *    structures have been changed and updated versions of the on-disk
+ *    data structures have been scheduled for write-back to disk.
+ *    On failure the B*-tree is probably invalid both on disk and in-core.
+ *
+ *    XXX: Some attempt at repair might be made in the event of failure,
+ *    or the fs should be remounted read-only so things don't get worse.
+ */
+static int binsert(struct hfs_brec *brec, const struct hfs_bkey *key,
+		   const void *data, hfs_u8 keysize, hfs_u16 datasize,
+		   int reserve)
+{
+	struct hfs_bnode_ref left, right, other;
+	struct hfs_btree *tree = brec->tree;
+	struct hfs_belem *belem = brec->bottom;
+	int tmpsize = 1 + tree->bthKeyLen;
+	struct hfs_bkey *tmpkey = hfs_malloc(tmpsize);
+	hfs_u32 node;
+	
+	while ((belem >= brec->top) && (belem->flags & HFS_BPATH_OVERFLOW)) {
+		left = belem->bnr;
+		if (left.bn->ndFLink &&
+                    hfs_bnode_in_brec(left.bn->ndFLink, brec)) {
+			hfs_warn("hfs_binsert: corrupt btree\n");
+			tree->reserved -= reserve;
+			hfs_free(tmpkey, tmpsize);
+			return -EIO;
+		}
+			
+		right = split(belem, ROUND(keysize+1) + ROUND(datasize));
+		--reserve;
+		--tree->reserved;
+		if (!right.bn) {
+			hfs_warn("hfs_binsert: unable to split node!\n");
+			tree->reserved -= reserve;
+			hfs_free(tmpkey, tmpsize);
+			return -ENOSPC;
+		}
+		binsert_nonfull(brec, belem, key, data, keysize, datasize);
+	
+		if (belem->bnr.bn == left.bn) {
+			other = right;
+			if (belem->record == 1) {
+				hfs_bnode_update_key(brec, belem, left.bn, 0);
+			}
+		} else {
+			other = left;
+		}
+
+		if (left.bn->node == tree->root->node) {
+			add_root(tree, left.bn, right.bn);
+			hfs_bnode_relse(&other);
+			goto done;
+		}
+
+		data = &node;
+		datasize = sizeof(node);
+		node = htonl(right.bn->node);
+		key = tmpkey;
+		keysize = tree->bthKeyLen;
+		memcpy(tmpkey, bnode_key(right.bn, 1), keysize+1);
+		hfs_bnode_relse(&other);
+		
+		--belem;
+	}
+
+	if (belem < brec->top) {
+		hfs_warn("hfs_binsert: Missing parent.\n");
+		tree->reserved -= reserve;
+		hfs_free(tmpkey, tmpsize);
+		return -EIO;
+	}
+
+	binsert_nonfull(brec, belem, key, data, keysize, datasize);
+
+done:
+	tree->reserved -= reserve;
+	hfs_free(tmpkey, tmpsize);
+	return 0;
+}
+
+/*================ Global functions ================*/
+
+/*
+ * hfs_binsert()
+ *
+ * Description:
+ *   This function inserts a new record into a b-tree.
+ * Input Variable(s):
+ *   struct hfs_btree *tree: pointer to the (struct hfs_btree) to insert in
+ *   struct hfs_bkey *key: pointer to the (struct hfs_bkey) to insert
+ *   void *data: pointer to the data to associate with 'key' in the b-tree
+ *   unsigned int datasize: the size of the data
+ * Output Variable(s):
+ *   NONE
+ * Returns:
+ *   int: 0 on success, error code on failure
+ * Preconditions:
+ *   'tree' points to a valid (struct hfs_btree)
+ *   'key' points to a valid (struct hfs_bkey)
+ *   'data' points to valid memory of length 'datasize'
+ * Postconditions:
+ *   If zero is returned then the record has been inserted in the
+ *    indicated location updating all in-core data structures and
+ *    scheduling all on-disk data structures for write-back.
+ */
+int hfs_binsert(struct hfs_btree *tree, const struct hfs_bkey *key,
+		const void *data, hfs_u16 datasize)
+{ 
+	struct hfs_brec brec;
+	struct hfs_belem *belem;
+	int err, reserve, retval;
+	hfs_u8 keysize;
+
+	if (!tree || (tree->magic != HFS_BTREE_MAGIC) || !key || !data) {
+		hfs_warn("hfs_binsert: invalid arguments.\n");
+		return -EINVAL;
+	}
+
+	if (key->KeyLen > tree->bthKeyLen) {
+		hfs_warn("hfs_binsert: oversized key\n");
+		return -EINVAL;
+	}
+
+restart:
+	if (!tree->bthNRecs) {
+		/* create the root bnode */
+		add_root(tree, NULL, NULL);
+		if (!hfs_brec_init(&brec, tree, HFS_BFIND_INSERT)) {
+			hfs_warn("hfs_binsert: failed to create root.\n");
+			return -ENOSPC;
+		}
+	} else {
+		err = hfs_bfind(&brec, tree, key, HFS_BFIND_INSERT);
+		if (err < 0) {
+			hfs_warn("hfs_binsert: hfs_brec_find failed.\n");
+			return err;
+		} else if (err == 0) {
+			hfs_brec_relse(&brec, NULL);
+			return -EEXIST;
+		}
+	}
+
+	keysize = key->KeyLen;
+	datasize = ROUND(datasize);
+	belem = brec.bottom;
+	belem->flags = 0;
+	if (bnode_freespace(belem->bnr.bn) <
+			    (sizeof(hfs_u16) + ROUND(keysize+1) + datasize)) {
+		belem->flags |= HFS_BPATH_OVERFLOW;
+	}
+	if (belem->record == 0) {
+		belem->flags |= HFS_BPATH_FIRST;
+	}
+
+	if (!belem->flags) {
+		hfs_brec_lock(&brec, brec.bottom);
+		reserve = 0;
+	} else {
+		reserve = brec.bottom - brec.top;
+		if (brec.top == 0) {
+			++reserve;
+		}
+		/* make certain we have enough nodes to proceed */
+		if ((tree->bthFree - tree->reserved) < reserve) {
+			hfs_brec_relse(&brec, NULL);
+			while (tree->lock) {
+				hfs_sleep_on(&tree->wait);
+			}
+			tree->lock = 1;
+			if ((tree->bthFree - tree->reserved) < reserve) {
+				hfs_btree_extend(tree);
+			}
+			tree->lock = 0;
+			hfs_wake_up(&tree->wait);
+			if ((tree->bthFree - tree->reserved) < reserve) {
+				return -ENOSPC;
+			} else {
+				goto restart;
+			}
+		}
+		tree->reserved += reserve;
+		hfs_brec_lock(&brec, NULL);
+	}
+
+	retval = binsert(&brec, key, data, keysize, datasize, reserve);
+	hfs_brec_relse(&brec, NULL);
+	if (!retval) {
+		++tree->bthNRecs;
+		tree->dirt = 1;
+	}
+	return retval;
+}
FUNET's LINUX-ADM group, linux-adm@nic.funet.fi
TCL-scripts by Sam Shen, slshen@lbl.gov