diff options
author | Ralf Baechle <ralf@linux-mips.org> | 1998-03-17 22:05:47 +0000 |
---|---|---|
committer | Ralf Baechle <ralf@linux-mips.org> | 1998-03-17 22:05:47 +0000 |
commit | 27cfca1ec98e91261b1a5355d10a8996464b63af (patch) | |
tree | 8e895a53e372fa682b4c0a585b9377d67ed70d0e /fs/hfs/brec.c | |
parent | 6a76fb7214c477ccf6582bd79c5b4ccc4f9c41b1 (diff) |
Look Ma' what I found on my harddisk ...
o New faster syscalls for 2.1.x, too
o Upgrade to 2.1.89.
Don't try to run this. It's flaky as hell. But feel free to debug ...
Diffstat (limited to 'fs/hfs/brec.c')
-rw-r--r-- | fs/hfs/brec.c | 239 |
1 files changed, 239 insertions, 0 deletions
diff --git a/fs/hfs/brec.c b/fs/hfs/brec.c new file mode 100644 index 000000000..8f6d70c07 --- /dev/null +++ b/fs/hfs/brec.c @@ -0,0 +1,239 @@ +/* + * linux/fs/hfs/brec.c + * + * Copyright (C) 1995-1997 Paul H. Hargrove + * This file may be distributed under the terms of the GNU 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; +} |