fs/hfs/brec.c

   1 /*
   2  * linux/fs/hfs/brec.c
   3  *
   4  * Copyright (C) 1995-1997  Paul H. Hargrove
   5  * This file may be distributed under the terms of the GNU 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 /*================ File-local functions ================*/
  19
  20 /*
  21  * first()
  22  *
  23  * returns HFS_BPATH_FIRST if elem->record == 1, 0 otherwise
  24  */
  25 static inline int first(const struct hfs_belem *elem)
  26 {
  27         return (elem->record == 1) ? HFS_BPATH_FIRST : 0;
  28 }
  29
  30 /*
  31  * overflow()
  32  *
  33  * return HFS_BPATH_OVERFLOW if the node has no room for an
  34  * additional pointer record, 0 otherwise.
  35  */
  36 static inline int overflow(const struct hfs_btree *tree,
  37                            const struct hfs_bnode *bnode)
  38 {
  39         /* there is some algebra involved in getting this form */
  40         return ((HFS_SECTOR_SIZE - sizeof(hfs_u32)) <
  41                  (bnode_end(bnode) + (2+bnode->ndNRecs)*sizeof(hfs_u16) +
  42                   ROUND(tree->bthKeyLen+1))) ?  HFS_BPATH_OVERFLOW : 0;
  43 }
  44
  45 /*
  46  * underflow()
  47  *
  48  * return HFS_BPATH_UNDERFLOW if the node will be less that 1/2 full
  49  * upon removal of a pointer record, 0 otherwise.
  50  */
  51 static inline int underflow(const struct hfs_btree *tree,
  52                             const struct hfs_bnode *bnode)
  53 {
  54         return ((bnode->ndNRecs * sizeof(hfs_u16) +
  55                  bnode_offset(bnode, bnode->ndNRecs)) <
  56                 (HFS_SECTOR_SIZE - sizeof(struct NodeDescriptor))/2) ?
  57                 HFS_BPATH_UNDERFLOW : 0;
  58 }
  59
  60 /*================ Global functions ================*/
  61
  62 /*
  63  * hfs_brec_next()
  64  *
  65  * Description:
  66  *   Obtain access to a child of an internal node in a B-tree.
  67  * Input Variable(s):
  68  *   struct hfs_brec *brec: pointer to the (struct hfs_brec) to
  69  *    add an element to.
  70  * Output Variable(s):
  71  *   NONE
  72  * Returns:
  73  *   struct hfs_belem *: pointer to the new path element or NULL
  74  * Preconditions:
  75  *   'brec' points to a "valid" (struct hfs_brec), the last element of
  76  *   which corresponds to a record in a bnode of type ndIndxNode and the
  77  *   'record' field indicates the index record for the desired child.
  78  * Postconditions:
  79  *   If the call to hfs_bnode_find() fails then 'brec' is released
  80  *   and a NULL is returned.
  81  *   Otherwise:
  82  *    Any ancestors in 'brec' that are not needed (as determined by the
  83  *     'keep_flags' field of 'brec) are released from 'brec'.
  84  *    A new element is added to 'brec' corresponding to the desired
  85  *     child.
  86  *    The child is obtained with the same 'lock_type' field as its
  87  *     parent.
  88  *    The 'record' field is initialized to the last record.
  89  *    A pointer to the new path element is returned.
  90  */
  91 struct hfs_belem *hfs_brec_next(struct hfs_brec *brec)
  92 {
  93         struct hfs_belem *elem = brec->bottom;
  94         hfs_u32 node;
  95         int lock_type;
  96
  97         /* release unneeded ancestors */
  98         elem->flags = first(elem) |
  99                       overflow(brec->tree, elem->bnr.bn) |
 100                       underflow(brec->tree, elem->bnr.bn);
 101         if (!(brec->keep_flags & elem->flags)) {
 102                 hfs_brec_relse(brec, brec->bottom-1);
 103         } else if ((brec->bottom-2 >= brec->top) &&
 104                    !(elem->flags & (elem-1)->flags)) {
 105                 hfs_brec_relse(brec, brec->bottom-2);
 106         }
 107
 108         node = hfs_get_hl(belem_record(elem));
 109         lock_type = elem->bnr.lock_type;
 110
 111         if (!node || hfs_bnode_in_brec(node, brec)) {
 112                 hfs_warn("hfs_bfind: corrupt btree\n");
 113                 hfs_brec_relse(brec, NULL);
 114                 return NULL;
 115         }
 116
 117         ++elem;
 118         ++brec->bottom;
 119
 120         elem->bnr = hfs_bnode_find(brec->tree, node, lock_type);
 121         if (!elem->bnr.bn) {
 122                 hfs_brec_relse(brec, NULL);
 123                 return NULL;
 124         }
 125         elem->record = elem->bnr.bn->ndNRecs;
 126
 127         return elem;
 128 }
 129
 130 /*
 131  * hfs_brec_lock()
 132  *
 133  * Description:
 134  *   This function obtains HFS_LOCK_WRITE access to the bnode
 135  *   containing this hfs_brec.  All descendents in the path from this
 136  *   record to the leaf are given HFS_LOCK_WRITE access and all
 137  *   ancestors in the path from the root to here are released.
 138  * Input Variable(s):
 139  *   struct hfs_brec *brec: pointer to the brec to obtain
 140  *    HFS_LOCK_WRITE access to some of the nodes of.
 141  *   struct hfs_belem *elem: the first node to lock or NULL for all
 142  * Output Variable(s):
 143  *   NONE
 144  * Returns:
 145  *   void
 146  * Preconditions:
 147  *   'brec' points to a "valid" (struct hfs_brec)
 148  * Postconditions:
 149  *   All nodes between the indicated node and the beginning of the path
 150  *    are released.  hfs_bnode_lock() is called in turn on each node
 151  *    from the indicated node to the leaf node of the path, with a
 152  *    lock_type argument of HFS_LOCK_WRITE.  If one of those calls
 153  *    results in deadlock, then this function will never return.
 154  */
 155 void hfs_brec_lock(struct hfs_brec *brec, struct hfs_belem *elem)
 156 {
 157         if (!elem) {
 158                 elem = brec->top;
 159         } else if (elem > brec->top) {
 160                 hfs_brec_relse(brec, elem-1);
 161         }
 162
 163         while (elem <= brec->bottom) {
 164                 hfs_bnode_lock(&elem->bnr, HFS_LOCK_WRITE);
 165                 ++elem;
 166         }
 167 }
 168
 169 /*
 170  * hfs_brec_init()
 171  *
 172  * Description:
 173  *   Obtain access to the root node of a B-tree.
 174  *   Note that this first must obtain access to the header node.
 175  * Input Variable(s):
 176  *   struct hfs_brec *brec: pointer to the (struct hfs_brec) to
 177  *    initialize
 178  *   struct hfs_btree *btree: pointer to the (struct hfs_btree)
 179  *   int lock_type: the type of access to get to the nodes.
 180  * Output Variable(s):
 181  *   NONE
 182  * Returns:
 183  *   struct hfs_belem *: pointer to the root path element or NULL
 184  * Preconditions:
 185  *   'brec' points to a (struct hfs_brec).
 186  *   'tree' points to a valid (struct hfs_btree).
 187  * Postconditions:
 188  *   If the two calls to brec_bnode_find() succeed then the return value
 189  *   points to a (struct hfs_belem) which corresponds to the root node
 190  *   of 'brec->tree'.
 191  *   Both the root and header nodes are obtained with the type of lock
 192  *   given by (flags & HFS_LOCK_MASK).
 193  *   The fields 'record' field of the root is set to its last record.
 194  *   If the header node is not needed to complete the appropriate
 195  *   operation (as determined by the 'keep_flags' field of 'brec') then
 196  *   it is released before this function returns.
 197  *   If either call to brec_bnode_find() fails, NULL is returned and the
 198  *   (struct hfs_brec) pointed to by 'brec' is invalid.
 199  */
 200 struct hfs_belem *hfs_brec_init(struct hfs_brec *brec, struct hfs_btree *tree,
 201                                 int flags)
 202 {
 203         struct hfs_belem *head = &brec->elem[0];
 204         struct hfs_belem *root = &brec->elem[1];
 205         int lock_type = flags & HFS_LOCK_MASK;
 206
 207         brec->tree = tree;
 208
 209         head->bnr = hfs_bnode_find(tree, 0, lock_type);
 210         if (!head->bnr.bn) {
 211                 return NULL;
 212         }
 213
 214         root->bnr = hfs_bnode_find(tree, tree->bthRoot, lock_type);
 215         if (!root->bnr.bn) {
 216                 hfs_bnode_relse(&head->bnr);
 217                 return NULL;
 218         }
 219
 220         root->record = root->bnr.bn->ndNRecs;
 221
 222         brec->top = head;
 223         brec->bottom = root;
 224
 225         brec->keep_flags = flags & HFS_BPATH_MASK;
 226
 227         /* HFS_BPATH_FIRST not applicable for root */
 228         /* and HFS_BPATH_UNDERFLOW is different */
 229         root->flags = overflow(tree, root->bnr.bn);
 230         if (root->record < 3) {
 231                 root->flags |= HFS_BPATH_UNDERFLOW;
 232         }
 233
 234         if (!(root->flags & brec->keep_flags)) {
 235                 hfs_brec_relse(brec, head);
 236         }
 237
 238         return root;
 239 }