diff options
Diffstat (limited to 'fs/hfs/bfind.c')
| -rw-r--r-- | fs/hfs/bfind.c | 322 |
1 files changed, 322 insertions, 0 deletions
diff --git a/fs/hfs/bfind.c b/fs/hfs/bfind.c new file mode 100644 index 000000000..d8d7e933d --- /dev/null +++ b/fs/hfs/bfind.c @@ -0,0 +1,322 @@ +/* + * linux/fs/hfs/bfind.c + * + * Copyright (C) 1995, 1996 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" + +/*================ Global functions ================*/ + +/* + * hfs_brec_relse() + * + * Description: + * This function releases some of the nodes associated with a brec. + * Input Variable(s): + * struct hfs_brec *brec: pointer to the brec to release some nodes from. + * struct hfs_belem *elem: the last node to release 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. + */ +void hfs_brec_relse(struct hfs_brec *brec, struct hfs_belem *elem) +{ + if (!elem) { + elem = brec->bottom; + } + + while (brec->top <= elem) { + hfs_bnode_relse(&brec->top->bnr); + ++brec->top; + } +} + +/* + * hfs_bfind() + * + * Description: + * This function has sole responsibility for locating existing + * records in a B-tree. Given a B-tree and a key it locates the + * "greatest" record "less than or equal to" the given key. The + * exact behavior is determined by the bits of the flags variable as + * follows: + * ('flags' & HFS_LOCK_MASK): + * The lock_type argument to be used when calling hfs_bnode_find(). + * HFS_BFIND_EXACT: only accept an exact match, otherwise take the + * "largest" record less than 'target' as a "match" + * HFS_BFIND_LOCK: request HFS_LOCK_WRITE access to the node containing + * the "matching" record when it is located + * HFS_BPATH_FIRST: keep access to internal nodes when accessing their + * first child. + * HFS_BPATH_OVERFLOW: keep access to internal nodes when the accessed + * child is too full to insert another pointer record. + * HFS_BPATH_UNDERFLOW: keep access to internal nodes when the accessed + * child is would be less than half full upon removing a pointer record. + * Input Variable(s): + * struct hfs_brec *brec: pointer to the (struct hfs_brec) to hold + * the search results. + * struct hfs_bkey *target: pointer to the (struct hfs_bkey) + * to search for + * int flags: bitwise OR of flags which determine the function's behavior + * Output Variable(s): + * 'brec' contains the results of the search on success or is invalid + * on failure. + * Returns: + * int: 0 or 1 on success or an error code on failure: + * -EINVAL: one of the input variables was NULL. + * -ENOENT: tree is valid but empty or no "matching" record was located. + * If the HFS_BFIND_EXACT bit of 'flags' is not set then the case of no + * matching record will give a 'brec' with a 'record' field of zero + * rather than returning this error. + * -EIO: an I/O operation or an assertion about the structure of a + * valid B-tree failed indicating corruption of either the B-tree + * structure on the disk or one of the in-core structures representing + * the B-tree. + * (This could also be returned if a kmalloc() call failed in a + * subordinate routine that is intended to get the data from the + * disk or the buffer cache.) + * Preconditions: + * 'brec' is NULL or points to a (struct hfs_brec) with a 'tree' field + * which points to a valid (struct hfs_btree). + * 'target' is NULL or points to a "valid" (struct hfs_bkey) + * Postconditions: + * If 'brec', 'brec->tree' or 'target' is NULL then -EINVAL is returned. + * If 'brec', 'brec->tree' and 'target' are non-NULL but the tree + * is empty then -ENOENT is returned. + * If 'brec', 'brec->tree' and 'target' are non-NULL but the call to + * hfs_brec_init() fails then '*brec' is NULL and -EIO is returned. + * If 'brec', 'brec->tree' and 'target' are non-NULL and the tree is + * non-empty then the tree is searched as follows: + * If any call to hfs_brec_next() fails or returns a node that is + * neither an index node nor a leaf node then -EIO is returned to + * indicate that the B-tree or buffer-cache are corrupted. + * If every record in the tree is "greater than" the given key + * and the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned. + * If every record in the tree is "greater than" the given key + * and the HFS_BFIND_EXACT bit of 'flags' is clear then 'brec' refers + * to the first leaf node in the tree and has a 'record' field of + * zero, and 1 is returned. + * If a "matching" record is located with key "equal to" 'target' + * then the return value is 0 and 'brec' indicates the record. + * If a "matching" record is located with key "greater than" 'target' + * then the behavior is determined as follows: + * If the HFS_BFIND_EXACT bit of 'flags' is not set then 1 is returned + * and 'brec' refers to the "matching" record. + * If the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned. + * If the return value is non-negative and the HFS_BFIND_LOCK bit of + * 'flags' is set then hfs_brec_lock() is called on the bottom element + * of 'brec' before returning. + */ +int hfs_bfind(struct hfs_brec *brec, struct hfs_btree *tree, + const struct hfs_bkey *target, int flags) +{ + struct hfs_belem *curr; + struct hfs_bkey *key; + struct hfs_bnode *bn; + int result, ntype; + + /* check for invalid arguments */ + if (!brec || (tree->magic != HFS_BTREE_MAGIC) || !target) { + return -EINVAL; + } + + /* check for empty tree */ + if (!tree->root || !tree->bthNRecs) { + return -ENOENT; + } + + /* start search at root of tree */ + if (!(curr = hfs_brec_init(brec, tree, flags))) { + return -EIO; + } + + /* traverse the tree */ + do { + bn = curr->bnr.bn; + + if (!curr->record) { + hfs_warn("hfs_bfind: empty bnode\n"); + hfs_brec_relse(brec, NULL); + return -EIO; + } + + /* reverse linear search yielding largest key "less + than or equal to" 'target'. + It is questionable whether a binary search would be + significantly faster */ + do { + key = belem_key(curr); + if (!key->KeyLen) { + hfs_warn("hfs_bfind: empty key\n"); + hfs_brec_relse(brec, NULL); + return -EIO; + } + result = (tree->compare)(target, key); + } while ((result<0) && (--curr->record)); + + ntype = bn->ndType; + + /* see if all keys > target */ + if (!curr->record) { + if (bn->ndBLink) { + /* at a node other than the left-most at a + given level it means the parent had an + incorrect key for this child */ + hfs_brec_relse(brec, NULL); + hfs_warn("hfs_bfind: corrupted b-tree %d.\n", + (int)ntohl(tree->entry.cnid)); + return -EIO; + } + if (flags & HFS_BFIND_EXACT) { + /* we're not going to find it */ + hfs_brec_relse(brec, NULL); + return -ENOENT; + } + if (ntype == ndIndxNode) { + /* since we are at the left-most node at + the current level and looking for the + predecessor of 'target' keep going down */ + curr->record = 1; + } else { + /* we're at first leaf so fall through */ + } + } + + /* get next node if necessary */ + if ((ntype == ndIndxNode) && !(curr = hfs_brec_next(brec))) { + return -EIO; + } + } while (ntype == ndIndxNode); + + if (key->KeyLen > tree->bthKeyLen) { + hfs_warn("hfs_bfind: oversized key\n"); + hfs_brec_relse(brec, NULL); + return -EIO; + } + + if (ntype != ndLeafNode) { + hfs_warn("hfs_bfind: invalid node type %02x in node %d of " + "btree %d\n", bn->ndType, bn->node, + (int)ntohl(tree->entry.cnid)); + hfs_brec_relse(brec, NULL); + return -EIO; + } + + if ((flags & HFS_BFIND_EXACT) && result) { + hfs_brec_relse(brec, NULL); + return -ENOENT; + } + + if (!(flags & HFS_BPATH_MASK)) { + hfs_brec_relse(brec, brec->bottom-1); + } + + if (flags & HFS_BFIND_LOCK) { + hfs_brec_lock(brec, brec->bottom); + } + + brec->key = brec_key(brec); + brec->data = bkey_record(brec->key); + + return result ? 1 : 0; +} + +/* + * hfs_bsucc() + * + * Description: + * This function overwrites '*brec' with its successor in the B-tree, + * obtaining the same type of access. + * Input Variable(s): + * struct hfs_brec *brec: address of the (struct hfs_brec) to overwrite + * with its successor + * Output Variable(s): + * struct hfs_brec *brec: address of the successor of the original + * '*brec' or to invalid data + * Returns: + * int: 0 on success, or one of -EINVAL, -EIO, or -EINVAL on failure + * Preconditions: + * 'brec' pointers to a "valid" (struct hfs_brec) + * Postconditions: + * If the given '*brec' is not "valid" -EINVAL is returned and + * '*brec' is unchanged. + * If the given 'brec' is "valid" but has no successor then -ENOENT + * is returned and '*brec' is invalid. + * If a call to hfs_bnode_find() is necessary to find the successor, + * but fails then -EIO is returned and '*brec' is invalid. + * If none of the three previous conditions prevents finding the + * successor of '*brec', then 0 is returned, and '*brec' is overwritten + * with the (struct hfs_brec) for its successor. + * In the cases when '*brec' is invalid, the old records is freed. + */ +int hfs_bsucc(struct hfs_brec *brec, int count) +{ + struct hfs_belem *belem; + struct hfs_bnode *bn; + + if (!brec || !(belem = brec->bottom) || (belem != brec->top) || + !(bn = belem->bnr.bn) || (bn->magic != HFS_BNODE_MAGIC) || + !bn->tree || (bn->tree->magic != HFS_BTREE_MAGIC) || + !hfs_buffer_ok(bn->buf)) { + hfs_warn("hfs_bsucc: invalid/corrupt arguments.\n"); + return -EINVAL; + } + + while (count) { + int left = bn->ndNRecs - belem->record; + + if (left < count) { + struct hfs_bnode_ref old; + hfs_u32 node; + + /* Advance to next node */ + if (!(node = bn->ndFLink)) { + hfs_brec_relse(brec, belem); + return -ENOENT; + } + if (node == bn->node) { + hfs_warn("hfs_bsucc: corrupt btree\n"); + hfs_brec_relse(brec, belem); + return -EIO; + } + old = belem->bnr; + belem->bnr = hfs_bnode_find(brec->tree, node, + belem->bnr.lock_type); + hfs_bnode_relse(&old); + if (!(bn = belem->bnr.bn)) { + return -EIO; + } + belem->record = 1; + count -= (left + 1); + } else { + belem->record += count; + break; + } + } + brec->key = belem_key(belem); + brec->data = bkey_record(brec->key); + + if (brec->key->KeyLen > brec->tree->bthKeyLen) { + hfs_warn("hfs_bsucc: oversized key\n"); + hfs_brec_relse(brec, NULL); + return -EIO; + } + + return 0; +} |