fs/hfs/bfind.c

   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 }