URL
https://opencores.org/ocsvn/or1k/or1k/trunk
Subversion Repositories or1k
[/] [or1k/] [tags/] [LINUX_2_4_26_OR32/] [linux/] [linux-2.4/] [fs/] [hfs/] [bins_del.c] - Rev 1780
Go to most recent revision | Compare with Previous | Blame | View Log
/* * 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; }
Go to most recent revision | Compare with Previous | Blame | View Log