Subversion Repositories or1k

/*

 * linux/fs/hfs/bins_del.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 common to inserting and deleting 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 ================*/

/*

 * hfs_bnode_update_key()

 *

 * Description:

 *   Updates the key for a bnode in its parent.

 *   The key change is propagated up the tree as necessary.

 * Input Variable(s):

 *   struct hfs_brec *brec: the search path to update keys in

 *   struct hfs_belem *belem: the search path element with the changed key

 *   struct hfs_bnode *bnode: the bnode with the changed key

 *   int offset: the "distance" from 'belem->bn' to 'bnode':

 *    0 if the change is in 'belem->bn',

 *    1 if the change is in its right sibling, etc.

 * Output Variable(s):

 *   NONE

 * Returns:

 *   void

 * Preconditions:

 *   'brec' points to a valid (struct hfs_brec)

 *   'belem' points to a valid (struct hfs_belem) in 'brec'.

 *   'bnode' points to a valid (struct hfs_bnode) which is non-empty

 *    and is 'belem->bn' or one of its siblings.

 *   'offset' is as described above.

 * Postconditions:

 *   The key change is propagated up the tree as necessary.

 */

void hfs_bnode_update_key(struct hfs_brec *brec, struct hfs_belem *belem,

                          struct hfs_bnode *bnode, int offset)

{

        int record = (--belem)->record + offset;

        void *key = bnode_datastart(bnode) + 1;

        int keysize = brec->tree->bthKeyLen;

        struct hfs_belem *limit;

        memcpy(1+bnode_key(belem->bnr.bn, record), key, keysize);

        /* don't trash the header */

        if (brec->top > &brec->elem[1]) {

                limit = brec->top;

        } else {

                limit = &brec->elem[1];

        }

        while ((belem > limit) && (record == 1)) {

                record = (--belem)->record;

                memcpy(1+belem_key(belem), key, keysize);

        }

}

/*

 * hfs_bnode_shift_right()

 *

 * Description:

 *   Shifts some records from a node to its right neighbor.

 * Input Variable(s):

 *   struct hfs_bnode* left: the node to shift records from

 *   struct hfs_bnode* right: the node to shift records to

 *   hfs_u16 first: the number of the first record in 'left' to move to 'right'

 * Output Variable(s):

 *   NONE

 * Returns:

 *   void

 * Preconditions:

 *   'left' and 'right' point to valid (struct hfs_bnode)s.

 *   'left' contains at least 'first' records.

 *   'right' has enough free space to hold the records to be moved from 'left'

 * Postconditions:

 *   The record numbered 'first' and all records after it in 'left' are

 *   placed at the beginning of 'right'.

 *   The key corresponding to 'right' in its parent is NOT updated.

 */

void hfs_bnode_shift_right(struct hfs_bnode *left, struct hfs_bnode *right,

                           int first)

{

        int i, adjust, nrecs;

        unsigned size;

        hfs_u16 *to, *from;

        if ((first <= 0) || (first > left->ndNRecs)) {

                hfs_warn("bad argument to shift_right: first=%d, nrecs=%d\n",

                       first, left->ndNRecs);

                return;

        }

        /* initialize variables */

        nrecs = left->ndNRecs + 1 - first;

        size = bnode_end(left) - bnode_offset(left, first);

        /* move (possibly empty) contents of right node forward */

        memmove(bnode_datastart(right) + size,

                bnode_datastart(right),

                bnode_end(right) - sizeof(struct NodeDescriptor));

        /* copy in new records */

        memcpy(bnode_datastart(right), bnode_key(left,first), size);

        /* fix up offsets in right node */

        i = right->ndNRecs + 1;

        from = RECTBL(right, i);

        to = from - nrecs;

        while (i--) {

                hfs_put_hs(hfs_get_hs(from++) + size, to++);

        }

        adjust = sizeof(struct NodeDescriptor) - bnode_offset(left, first);

        i = nrecs-1;

        from = RECTBL(left, first+i);

        while (i--) {

                hfs_put_hs(hfs_get_hs(from++) + adjust, to++);

        }

        /* fix record counts */

        left->ndNRecs -= nrecs;

        right->ndNRecs += nrecs;

}

/*

 * hfs_bnode_shift_left()

 *

 * Description:

 *   Shifts some records from a node to its left neighbor.

 * Input Variable(s):

 *   struct hfs_bnode* left: the node to shift records to

 *   struct hfs_bnode* right: the node to shift records from

 *   hfs_u16 last: the number of the last record in 'right' to move to 'left'

 * Output Variable(s):

 *   NONE

 * Returns:

 *   void

 * Preconditions:

 *   'left' and 'right' point to valid (struct hfs_bnode)s.

 *   'right' contains at least 'last' records.

 *   'left' has enough free space to hold the records to be moved from 'right'

 * Postconditions:

 *   The record numbered 'last' and all records before it in 'right' are

 *   placed at the end of 'left'.

 *   The key corresponding to 'right' in its parent is NOT updated.

 */

void hfs_bnode_shift_left(struct hfs_bnode *left, struct hfs_bnode *right,

                          int last)

{

        int i, adjust, nrecs;

        unsigned size;

        hfs_u16 *to, *from;

        if ((last <= 0) || (last > right->ndNRecs)) {

                hfs_warn("bad argument to shift_left: last=%d, nrecs=%d\n",

                       last, right->ndNRecs);

                return;

        }

        /* initialize variables */

        size = bnode_offset(right, last + 1) - sizeof(struct NodeDescriptor);

        /* copy records to left node */

        memcpy(bnode_dataend(left), bnode_datastart(right), size);

        /* move (possibly empty) remainder of right node backward */

        memmove(bnode_datastart(right), bnode_datastart(right) + size,

                        bnode_end(right) - bnode_offset(right, last + 1));

        /* fix up offsets */

        nrecs = left->ndNRecs;

        i = last;

        from = RECTBL(right, 2);

        to = RECTBL(left, nrecs + 2);

        adjust = bnode_offset(left, nrecs + 1) - sizeof(struct NodeDescriptor);

        while (i--) {

                hfs_put_hs(hfs_get_hs(from--) + adjust, to--);

        }

        i = right->ndNRecs + 1 - last;

        ++from;

        to = RECTBL(right, 1);

        while (i--) {

                hfs_put_hs(hfs_get_hs(from--) - size, to--);

        }

        /* fix record counts */

        left->ndNRecs += last;

        right->ndNRecs -= last;

}

/*

 * hfs_bnode_in_brec()

 *

 * Description:

 *   Determines whethet a given bnode is part of a given brec.

 *   This is used to avoid deadlock in the case of a corrupted b-tree.

 * Input Variable(s):

 *   hfs_u32 node: the number of the node to check for.

 *   struct hfs_brec* brec: the brec to check in.

 * Output Variable(s):

 *   NONE

 * Returns:

 *   int: 1 it found, 0 if not

 * Preconditions:

 *   'brec' points to a valid struct hfs_brec.

 * Postconditions:

 *   'brec' is unchanged.

 */

int hfs_bnode_in_brec(hfs_u32 node, const struct hfs_brec *brec)

{

        const struct hfs_belem *belem = brec->bottom;

        while (belem && (belem >= brec->top)) {

                if (belem->bnr.bn && (belem->bnr.bn->node == node)) {

                        return 1;

                }

                --belem;

        }

        return 0;

}