binsert.c

嵌入式系统设计与实验教材二源码linux内核移植与编译

/*
 * linux/fs/hfs/binsert.c
 *
 * Copyright (C) 1995-1997  Paul H. Hargrove
 * This file may be distributed under the terms of the GNU General 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 ================*/

/* btree locking functions */
static inline void hfs_btree_lock(struct hfs_btree *tree)
{
  while (tree->lock) 
    hfs_sleep_on(&tree->wait);
  tree->lock = 1;
}

static inline void hfs_btree_unlock(struct hfs_btree *tree)
{
  tree->lock = 0;
  hfs_wake_up(&tree->wait);
}

/*
 * 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;