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