Viewing file:  binsert.c (15.89 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* 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;
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;
}
|