bfind.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    1 /*
    2  * linux/fs/hfs/bfind.c
    3  *
    4  * Copyright (C) 1995, 1996  Paul H. Hargrove
    5  * This file may be distributed under the terms of the GNU General Public License.
    6  *
    7  * This file contains the code to access records in a btree.
    8  *
    9  * "XXX" in a comment is a note to myself to consider changing something.
   10  *
   11  * In function preconditions the term "valid" applied to a pointer to
   12  * a structure means that the pointer is non-NULL and the structure it
   13  * points to has all fields initialized to consistent values.
   14  */
   15 
   16 #include "hfs_btree.h"
   17 
   18 /*================ Global functions ================*/
   19 
   20 /*
   21  * hfs_brec_relse()
   22  *
   23  * Description:
   24  *   This function releases some of the nodes associated with a brec.
   25  * Input Variable(s):
   26  *   struct hfs_brec *brec: pointer to the brec to release some nodes from.
   27  *   struct hfs_belem *elem: the last node to release or NULL for all
   28  * Output Variable(s):
   29  *   NONE
   30  * Returns:
   31  *   void
   32  * Preconditions:
   33  *   'brec' points to a "valid" (struct hfs_brec)
   34  * Postconditions: 
   35  *   All nodes between the indicated node and the beginning of the path
   36  *    are released.
   37  */
   38 void hfs_brec_relse(struct hfs_brec *brec, struct hfs_belem *elem)
   39 {
   40         if (!elem) {
   41                 elem = brec->bottom;
   42         }
   43 
   44         while (brec->top <= elem) {
   45                 hfs_bnode_relse(&brec->top->bnr);
   46                 ++brec->top;
   47         }
   48 }
   49 
   50 /*
   51  * hfs_bfind()
   52  *
   53  * Description:
   54  *   This function has sole responsibility for locating existing
   55  *   records in a B-tree.  Given a B-tree and a key it locates the
   56  *   "greatest" record "less than or equal to" the given key.  The
   57  *   exact behavior is determined by the bits of the flags variable as
   58  *   follows:
   59  *     ('flags' & HFS_LOCK_MASK):
   60  *      The lock_type argument to be used when calling hfs_bnode_find().
   61  *     HFS_BFIND_EXACT: only accept an exact match, otherwise take the
   62  *      "largest" record less than 'target' as a "match"
   63  *     HFS_BFIND_LOCK: request HFS_LOCK_WRITE access to the node containing
   64  *      the "matching" record when it is located
   65  *     HFS_BPATH_FIRST: keep access to internal nodes when accessing their
   66  *      first child.
   67  *     HFS_BPATH_OVERFLOW: keep access to internal nodes when the accessed
   68  *      child is too full to insert another pointer record.
   69  *     HFS_BPATH_UNDERFLOW: keep access to internal nodes when the accessed
   70  *      child is would be less than half full upon removing a pointer record.
   71  * Input Variable(s):
   72  *   struct hfs_brec *brec: pointer to the (struct hfs_brec) to hold
   73  *    the search results.
   74  *   struct hfs_bkey *target: pointer to the (struct hfs_bkey)
   75  *    to search for
   76  *   int flags: bitwise OR of flags which determine the function's behavior
   77  * Output Variable(s):
   78  *   'brec' contains the results of the search on success or is invalid
   79  *    on failure.
   80  * Returns:
   81  *   int: 0 or 1 on success or an error code on failure:
   82  *     -EINVAL: one of the input variables was NULL.
   83  *     -ENOENT: tree is valid but empty or no "matching" record was located.
   84  *       If the HFS_BFIND_EXACT bit of 'flags' is not set then the case of no
   85  *       matching record will give a 'brec' with a 'record' field of zero
   86  *       rather than returning this error.
   87  *     -EIO: an I/O operation or an assertion about the structure of a
   88  *       valid B-tree failed indicating corruption of either the B-tree
   89  *       structure on the disk or one of the in-core structures representing
   90  *       the B-tree.
   91  *       (This could also be returned if a kmalloc() call failed in a
   92  *       subordinate routine that is intended to get the data from the
   93  *       disk or the buffer cache.)
   94  * Preconditions:
   95  *   'brec' is NULL or points to a (struct hfs_brec) with a 'tree' field
   96  *    which points to a valid (struct hfs_btree).
   97  *   'target' is NULL or points to a "valid" (struct hfs_bkey)
   98  * Postconditions:
   99  *   If 'brec', 'brec->tree' or 'target' is NULL then -EINVAL is returned.
  100  *   If 'brec', 'brec->tree' and 'target' are non-NULL but the tree
  101  *   is empty then -ENOENT is returned.
  102  *   If 'brec', 'brec->tree' and 'target' are non-NULL but the call to
  103  *   hfs_brec_init() fails then '*brec' is NULL and -EIO is returned.
  104  *   If 'brec', 'brec->tree' and 'target' are non-NULL and the tree is
  105  *   non-empty then the tree is searched as follows:
  106  *    If any call to hfs_brec_next() fails or returns a node that is
  107  *     neither an index node nor a leaf node then -EIO is returned to
  108  *     indicate that the B-tree or buffer-cache are corrupted.
  109  *    If every record in the tree is "greater than" the given key
  110  *     and the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned.
  111  *    If every record in the tree is "greater than" the given key
  112  *     and the HFS_BFIND_EXACT bit of 'flags' is clear then 'brec' refers
  113  *     to the first leaf node in the tree and has a 'record' field of
  114  *     zero, and 1 is returned.
  115  *    If a "matching" record is located with key "equal to" 'target'
  116  *     then the return value is 0 and 'brec' indicates the record.
  117  *    If a "matching" record is located with key "greater than" 'target'
  118  *     then the behavior is determined as follows:
  119  *      If the HFS_BFIND_EXACT bit of 'flags' is not set then 1 is returned
  120  *       and 'brec' refers to the "matching" record.
  121  *      If the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned.
  122  *    If the return value is non-negative and the HFS_BFIND_LOCK bit of
  123  *     'flags' is set then hfs_brec_lock() is called on the bottom element
  124  *     of 'brec' before returning.
  125  */
  126 int hfs_bfind(struct hfs_brec *brec, struct hfs_btree *tree,
  127               const struct hfs_bkey *target, int flags)
  128 {
  129         struct hfs_belem *curr;
  130         struct hfs_bkey *key;
  131         struct hfs_bnode *bn;
  132         int result, ntype;
  133 
  134         /* check for invalid arguments */
  135         if (!brec || (tree->magic != HFS_BTREE_MAGIC) || !target) {
  136                 return -EINVAL;
  137         }
  138 
  139         /* check for empty tree */
  140         if (!tree->root || !tree->bthNRecs) {
  141                 return -ENOENT;
  142         }
  143 
  144         /* start search at root of tree */
  145         if (!(curr = hfs_brec_init(brec, tree, flags))) {
  146                 return -EIO;
  147         }
  148 
  149         /* traverse the tree */
  150         do {
  151                 bn = curr->bnr.bn;
  152 
  153                 if (!curr->record) {
  154                         hfs_warn("hfs_bfind: empty bnode\n");
  155                         hfs_brec_relse(brec, NULL);
  156                         return -EIO;
  157                 }
  158 
  159                 /* reverse linear search yielding largest key "less
  160                    than or equal to" 'target'.
  161                    It is questionable whether a binary search would be
  162                    significantly faster */
  163                 do {
  164                         key = belem_key(curr);
  165                         if (!key->KeyLen) {
  166                                 hfs_warn("hfs_bfind: empty key\n");
  167                                 hfs_brec_relse(brec, NULL);
  168                                 return -EIO;
  169                         }
  170                         result = (tree->compare)(target, key);
  171                 } while ((result<0) && (--curr->record));
  172 
  173                 ntype = bn->ndType;
  174 
  175                 /* see if all keys > target */
  176                 if (!curr->record) {
  177                         if (bn->ndBLink) {
  178                                 /* at a node other than the left-most at a
  179                                    given level it means the parent had an
  180                                    incorrect key for this child */
  181                                 hfs_brec_relse(brec, NULL);
  182                                 hfs_warn("hfs_bfind: corrupted b-tree %d.\n",
  183                                          (int)ntohl(tree->entry.cnid));
  184                                 return -EIO;
  185                         }
  186                         if (flags & HFS_BFIND_EXACT) {
  187                                 /* we're not going to find it */
  188                                 hfs_brec_relse(brec, NULL);
  189                                 return -ENOENT;
  190                         }
  191                         if (ntype == ndIndxNode) {
  192                                 /* since we are at the left-most node at
  193                                    the current level and looking for the
  194                                    predecessor of 'target' keep going down */
  195                                 curr->record = 1;
  196                         } else {
  197                                 /* we're at first leaf so fall through */
  198                         }
  199                 }
  200 
  201                 /* get next node if necessary */
  202                 if ((ntype == ndIndxNode) && !(curr = hfs_brec_next(brec))) {
  203                         return -EIO;
  204                 }
  205         } while (ntype == ndIndxNode);
  206 
  207         if (key->KeyLen > tree->bthKeyLen) {
  208                 hfs_warn("hfs_bfind: oversized key\n");
  209                 hfs_brec_relse(brec, NULL);
  210                 return -EIO;
  211         }
  212 
  213         if (ntype != ndLeafNode) {
  214                 hfs_warn("hfs_bfind: invalid node type %02x in node %d of "
  215                          "btree %d\n", bn->ndType, bn->node,
  216                          (int)ntohl(tree->entry.cnid));
  217                 hfs_brec_relse(brec, NULL);
  218                 return -EIO;
  219         }
  220 
  221         if ((flags & HFS_BFIND_EXACT) && result) {
  222                 hfs_brec_relse(brec, NULL);
  223                 return -ENOENT;
  224         }
  225 
  226         if (!(flags & HFS_BPATH_MASK)) {
  227                 hfs_brec_relse(brec, brec->bottom-1);
  228         }
  229 
  230         if (flags & HFS_BFIND_LOCK) {
  231                 hfs_brec_lock(brec, brec->bottom);
  232         }
  233 
  234         brec->key  = brec_key(brec);
  235         brec->data = bkey_record(brec->key);
  236 
  237         return result ? 1 : 0;
  238 }
  239 
  240 /*
  241  * hfs_bsucc()
  242  *
  243  * Description:
  244  *   This function overwrites '*brec' with its successor in the B-tree,
  245  *   obtaining the same type of access.
  246  * Input Variable(s):
  247  *   struct hfs_brec *brec: address of the (struct hfs_brec) to overwrite
  248  *    with its successor
  249  * Output Variable(s):
  250  *   struct hfs_brec *brec: address of the successor of the original
  251  *    '*brec' or to invalid data
  252  * Returns:
  253  *   int: 0 on success, or one of -EINVAL, -EIO, or -EINVAL on failure
  254  * Preconditions:
  255  *   'brec' pointers to a "valid" (struct hfs_brec)
  256  * Postconditions:
  257  *   If the given '*brec' is not "valid" -EINVAL is returned and
  258  *    '*brec' is unchanged.
  259  *   If the given 'brec' is "valid" but has no successor then -ENOENT
  260  *    is returned and '*brec' is invalid.
  261  *   If a call to hfs_bnode_find() is necessary to find the successor,
  262  *    but fails then -EIO is returned and '*brec' is invalid.
  263  *   If none of the three previous conditions prevents finding the
  264  *    successor of '*brec', then 0 is returned, and '*brec' is overwritten
  265  *    with the (struct hfs_brec) for its successor.
  266  *   In the cases when '*brec' is invalid, the old records is freed.
  267  */
  268 int hfs_bsucc(struct hfs_brec *brec, int count)
  269 {
  270         struct hfs_belem *belem;
  271         struct hfs_bnode *bn;
  272 
  273         if (!brec || !(belem = brec->bottom) || (belem != brec->top) ||
  274             !(bn = belem->bnr.bn) || (bn->magic != HFS_BNODE_MAGIC) ||
  275             !bn->tree || (bn->tree->magic != HFS_BTREE_MAGIC) ||
  276             !hfs_buffer_ok(bn->buf)) {
  277                 hfs_warn("hfs_bsucc: invalid/corrupt arguments.\n");
  278                 return -EINVAL;
  279         }
  280 
  281         while (count) {
  282                 int left = bn->ndNRecs - belem->record;
  283 
  284                 if (left < count) {
  285                         struct hfs_bnode_ref old;
  286                         hfs_u32 node;
  287 
  288                         /* Advance to next node */
  289                         if (!(node = bn->ndFLink)) {
  290                                 hfs_brec_relse(brec, belem);
  291                                 return -ENOENT;
  292                         }
  293                         if (node == bn->node) {
  294                                 hfs_warn("hfs_bsucc: corrupt btree\n");
  295                                 hfs_brec_relse(brec, belem);
  296                                 return -EIO;
  297                         }
  298                         old = belem->bnr;
  299                         belem->bnr = hfs_bnode_find(brec->tree, node,
  300                                                     belem->bnr.lock_type);
  301                         hfs_bnode_relse(&old);
  302                         if (!(bn = belem->bnr.bn)) {
  303                                 return -EIO;
  304                         }
  305                         belem->record = 1;
  306                         count -= (left + 1);
  307                 } else {
  308                         belem->record += count;
  309                         break;
  310                 }
  311         }
  312         brec->key  = belem_key(belem);
  313         brec->data = bkey_record(brec->key);
  314 
  315         if (brec->key->KeyLen > brec->tree->bthKeyLen) {
  316                 hfs_warn("hfs_bsucc: oversized key\n");
  317                 hfs_brec_relse(brec, NULL);
  318                 return -EIO;
  319         }
  320 
  321         return 0;
  322 }
Cache object: 2129af433f2f4aa0b145ccae4937b3b3
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/fs/hfs/bfind.c

FreeBSD/Linux Kernel Cross Reference
sys/fs/hfs/bfind.c
