binsert.c

嵌入式系统设计与实例开发实验教材二源码 多线程应用程序设计 串行端口程序设计 AD接口实验 CAN总线通信实验 GPS通信实验 Linux内核移植与编译实验 IC卡读写实验 SD驱动使

	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);
			hfs_btree_lock(tree);
			if ((tree->bthFree - tree->reserved) < reserve) {
				hfs_btree_extend(tree);
			}
			hfs_btree_unlock(tree);
			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;
}