Viewing file:  brec.c (6.99 KB) -rw-r--r--
Select action/file-type:
 (+) |  (+) |  (+) | Code (+) | Session (+) |  (+) | SDB (+) |  (+) |  (+) |  (+) |  (+) |  (+) |
/*
* linux/fs/hfs/brec.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 access records in a btree.
*
* "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 ================*/
/*
* first()
*
* returns HFS_BPATH_FIRST if elem->record == 1, 0 otherwise
*/
static inline int first(const struct hfs_belem *elem)
{
return (elem->record == 1) ? HFS_BPATH_FIRST : 0;
}
/*
* overflow()
*
* return HFS_BPATH_OVERFLOW if the node has no room for an
* additional pointer record, 0 otherwise.
*/
static inline int overflow(const struct hfs_btree *tree,
const struct hfs_bnode *bnode)
{
/* there is some algebra involved in getting this form */
return ((HFS_SECTOR_SIZE - sizeof(hfs_u32)) <
(bnode_end(bnode) + (2+bnode->ndNRecs)*sizeof(hfs_u16) +
ROUND(tree->bthKeyLen+1))) ? HFS_BPATH_OVERFLOW : 0;
}
/*
* underflow()
*
* return HFS_BPATH_UNDERFLOW if the node will be less that 1/2 full
* upon removal of a pointer record, 0 otherwise.
*/
static inline int underflow(const struct hfs_btree *tree,
const struct hfs_bnode *bnode)
{
return ((bnode->ndNRecs * sizeof(hfs_u16) +
bnode_offset(bnode, bnode->ndNRecs)) <
(HFS_SECTOR_SIZE - sizeof(struct NodeDescriptor))/2) ?
HFS_BPATH_UNDERFLOW : 0;
}
/*================ Global functions ================*/
/*
* hfs_brec_next()
*
* Description:
* Obtain access to a child of an internal node in a B-tree.
* Input Variable(s):
* struct hfs_brec *brec: pointer to the (struct hfs_brec) to
* add an element to.
* Output Variable(s):
* NONE
* Returns:
* struct hfs_belem *: pointer to the new path element or NULL
* Preconditions:
* 'brec' points to a "valid" (struct hfs_brec), the last element of
* which corresponds to a record in a bnode of type ndIndxNode and the
* 'record' field indicates the index record for the desired child.
* Postconditions:
* If the call to hfs_bnode_find() fails then 'brec' is released
* and a NULL is returned.
* Otherwise:
* Any ancestors in 'brec' that are not needed (as determined by the
* 'keep_flags' field of 'brec) are released from 'brec'.
* A new element is added to 'brec' corresponding to the desired
* child.
* The child is obtained with the same 'lock_type' field as its
* parent.
* The 'record' field is initialized to the last record.
* A pointer to the new path element is returned.
*/
struct hfs_belem *hfs_brec_next(struct hfs_brec *brec)
{
struct hfs_belem *elem = brec->bottom;
hfs_u32 node;
int lock_type;
/* release unneeded ancestors */
elem->flags = first(elem) |
overflow(brec->tree, elem->bnr.bn) |
underflow(brec->tree, elem->bnr.bn);
if (!(brec->keep_flags & elem->flags)) {
hfs_brec_relse(brec, brec->bottom-1);
} else if ((brec->bottom-2 >= brec->top) &&
!(elem->flags & (elem-1)->flags)) {
hfs_brec_relse(brec, brec->bottom-2);
}
node = hfs_get_hl(belem_record(elem));
lock_type = elem->bnr.lock_type;
if (!node || hfs_bnode_in_brec(node, brec)) {
hfs_warn("hfs_bfind: corrupt btree\n");
hfs_brec_relse(brec, NULL);
return NULL;
}
++elem;
++brec->bottom;
elem->bnr = hfs_bnode_find(brec->tree, node, lock_type);
if (!elem->bnr.bn) {
hfs_brec_relse(brec, NULL);
return NULL;
}
elem->record = elem->bnr.bn->ndNRecs;
return elem;
}
/*
* hfs_brec_lock()
*
* Description:
* This function obtains HFS_LOCK_WRITE access to the bnode
* containing this hfs_brec. All descendents in the path from this
* record to the leaf are given HFS_LOCK_WRITE access and all
* ancestors in the path from the root to here are released.
* Input Variable(s):
* struct hfs_brec *brec: pointer to the brec to obtain
* HFS_LOCK_WRITE access to some of the nodes of.
* struct hfs_belem *elem: the first node to lock or NULL for all
* Output Variable(s):
* NONE
* Returns:
* void
* Preconditions:
* 'brec' points to a "valid" (struct hfs_brec)
* Postconditions:
* All nodes between the indicated node and the beginning of the path
* are released. hfs_bnode_lock() is called in turn on each node
* from the indicated node to the leaf node of the path, with a
* lock_type argument of HFS_LOCK_WRITE. If one of those calls
* results in deadlock, then this function will never return.
*/
void hfs_brec_lock(struct hfs_brec *brec, struct hfs_belem *elem)
{
if (!elem) {
elem = brec->top;
} else if (elem > brec->top) {
hfs_brec_relse(brec, elem-1);
}
while (elem <= brec->bottom) {
hfs_bnode_lock(&elem->bnr, HFS_LOCK_WRITE);
++elem;
}
}
/*
* hfs_brec_init()
*
* Description:
* Obtain access to the root node of a B-tree.
* Note that this first must obtain access to the header node.
* Input Variable(s):
* struct hfs_brec *brec: pointer to the (struct hfs_brec) to
* initialize
* struct hfs_btree *btree: pointer to the (struct hfs_btree)
* int lock_type: the type of access to get to the nodes.
* Output Variable(s):
* NONE
* Returns:
* struct hfs_belem *: pointer to the root path element or NULL
* Preconditions:
* 'brec' points to a (struct hfs_brec).
* 'tree' points to a valid (struct hfs_btree).
* Postconditions:
* If the two calls to brec_bnode_find() succeed then the return value
* points to a (struct hfs_belem) which corresponds to the root node
* of 'brec->tree'.
* Both the root and header nodes are obtained with the type of lock
* given by (flags & HFS_LOCK_MASK).
* The fields 'record' field of the root is set to its last record.
* If the header node is not needed to complete the appropriate
* operation (as determined by the 'keep_flags' field of 'brec') then
* it is released before this function returns.
* If either call to brec_bnode_find() fails, NULL is returned and the
* (struct hfs_brec) pointed to by 'brec' is invalid.
*/
struct hfs_belem *hfs_brec_init(struct hfs_brec *brec, struct hfs_btree *tree,
int flags)
{
struct hfs_belem *head = &brec->elem[0];
struct hfs_belem *root = &brec->elem[1];
int lock_type = flags & HFS_LOCK_MASK;
brec->tree = tree;
head->bnr = hfs_bnode_find(tree, 0, lock_type);
if (!head->bnr.bn) {
return NULL;
}
root->bnr = hfs_bnode_find(tree, tree->bthRoot, lock_type);
if (!root->bnr.bn) {
hfs_bnode_relse(&head->bnr);
return NULL;
}
root->record = root->bnr.bn->ndNRecs;
brec->top = head;
brec->bottom = root;
brec->keep_flags = flags & HFS_BPATH_MASK;
/* HFS_BPATH_FIRST not applicable for root */
/* and HFS_BPATH_UNDERFLOW is different */
root->flags = overflow(tree, root->bnr.bn);
if (root->record < 3) {
root->flags |= HFS_BPATH_UNDERFLOW;
}
if (!(root->flags & brec->keep_flags)) {
hfs_brec_relse(brec, head);
}
return root;
}
|