fs/hfs/bins_del.c

   1 /*
   2  * linux/fs/hfs/bins_del.c
   3  *
   4  * Copyright (C) 1995-1997  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 common to inserting and deleting records
   8  * in a B-tree.
   9  *
  10  * "XXX" in a comment is a note to myself to consider changing something.
  11  *
  12  * In function preconditions the term "valid" applied to a pointer to
  13  * a structure means that the pointer is non-NULL and the structure it
  14  * points to has all fields initialized to consistent values.
  15  */
  16
  17 #include "hfs_btree.h"
  18
  19 /*================ File-local functions ================*/
  20
  21 /*
  22  * hfs_bnode_update_key()
  23  *
  24  * Description:
  25  *   Updates the key for a bnode in its parent.
  26  *   The key change is propagated up the tree as necessary.
  27  * Input Variable(s):
  28  *   struct hfs_brec *brec: the search path to update keys in
  29  *   struct hfs_belem *belem: the search path element with the changed key
  30  *   struct hfs_bnode *bnode: the bnode with the changed key
  31  *   int offset: the "distance" from 'belem->bn' to 'bnode':
  32  *    0 if the change is in 'belem->bn',
  33  *    1 if the change is in its right sibling, etc.
  34  * Output Variable(s):
  35  *   NONE
  36  * Returns:
  37  *   void
  38  * Preconditions:
  39  *   'brec' points to a valid (struct hfs_brec)
  40  *   'belem' points to a valid (struct hfs_belem) in 'brec'.
  41  *   'bnode' points to a valid (struct hfs_bnode) which is non-empty
  42  *    and is 'belem->bn' or one of its siblings.
  43  *   'offset' is as described above.
  44  * Postconditions:
  45  *   The key change is propagated up the tree as necessary.
  46  */
  47 void hfs_bnode_update_key(struct hfs_brec *brec, struct hfs_belem *belem,
  48                           struct hfs_bnode *bnode, int offset)
  49 {
  50         int record = (--belem)->record + offset;
  51         void *key = bnode_datastart(bnode) + 1;
  52         int keysize = brec->tree->bthKeyLen;
  53         struct hfs_belem *limit;
  54
  55         memcpy(1+bnode_key(belem->bnr.bn, record), key, keysize);
  56
  57         /* don't trash the header */
  58         if (brec->top > &brec->elem[1]) {
  59                 limit = brec->top;
  60         } else {
  61                 limit = &brec->elem[1];
  62         }
  63
  64         while ((belem > limit) && (record == 1)) {
  65                 record = (--belem)->record;
  66                 memcpy(1+belem_key(belem), key, keysize);
  67         }
  68 }
  69
  70 /*
  71  * hfs_bnode_shift_right()
  72  *
  73  * Description:
  74  *   Shifts some records from a node to its right neighbor.
  75  * Input Variable(s):
  76  *   struct hfs_bnode* left: the node to shift records from
  77  *   struct hfs_bnode* right: the node to shift records to
  78  *   hfs_u16 first: the number of the first record in 'left' to move to 'right'
  79  * Output Variable(s):
  80  *   NONE
  81  * Returns:
  82  *   void
  83  * Preconditions:
  84  *   'left' and 'right' point to valid (struct hfs_bnode)s.
  85  *   'left' contains at least 'first' records.
  86  *   'right' has enough free space to hold the records to be moved from 'left'
  87  * Postconditions:
  88  *   The record numbered 'first' and all records after it in 'left' are
  89  *   placed at the beginning of 'right'.
  90  *   The key corresponding to 'right' in its parent is NOT updated.
  91  */
  92 void hfs_bnode_shift_right(struct hfs_bnode *left, struct hfs_bnode *right,
  93                            int first)
  94 {
  95         int i, adjust, nrecs;
  96         unsigned size;
  97         hfs_u16 *to, *from;
  98
  99         if ((first <= 0) || (first > left->ndNRecs)) {
 100                 hfs_warn("bad argument to shift_right: first=%d, nrecs=%d\n",
 101                        first, left->ndNRecs);
 102                 return;
 103         }
 104
 105         /* initialize variables */
 106         nrecs = left->ndNRecs + 1 - first;
 107         size = bnode_end(left) - bnode_offset(left, first);
 108
 109         /* move (possibly empty) contents of right node forward */
 110         memmove(bnode_datastart(right) + size,
 111                 bnode_datastart(right),
 112                 bnode_end(right) - sizeof(struct NodeDescriptor));
 113
 114         /* copy in new records */
 115         memcpy(bnode_datastart(right), bnode_key(left,first), size);
 116
 117         /* fix up offsets in right node */
 118         i = right->ndNRecs + 1;
 119         from = RECTBL(right, i);
 120         to = from - nrecs;
 121         while (i--) {
 122                 hfs_put_hs(hfs_get_hs(from++) + size, to++);
 123         }
 124         adjust = sizeof(struct NodeDescriptor) - bnode_offset(left, first);
 125         i = nrecs-1;
 126         from = RECTBL(left, first+i);
 127         while (i--) {
 128                 hfs_put_hs(hfs_get_hs(from++) + adjust, to++);
 129         }
 130
 131         /* fix record counts */
 132         left->ndNRecs -= nrecs;
 133         right->ndNRecs += nrecs;
 134 }
 135
 136 /*
 137  * hfs_bnode_shift_left()
 138  *
 139  * Description:
 140  *   Shifts some records from a node to its left neighbor.
 141  * Input Variable(s):
 142  *   struct hfs_bnode* left: the node to shift records to
 143  *   struct hfs_bnode* right: the node to shift records from
 144  *   hfs_u16 last: the number of the last record in 'right' to move to 'left'
 145  * Output Variable(s):
 146  *   NONE
 147  * Returns:
 148  *   void
 149  * Preconditions:
 150  *   'left' and 'right' point to valid (struct hfs_bnode)s.
 151  *   'right' contains at least 'last' records.
 152  *   'left' has enough free space to hold the records to be moved from 'right'
 153  * Postconditions:
 154  *   The record numbered 'last' and all records before it in 'right' are
 155  *   placed at the end of 'left'.
 156  *   The key corresponding to 'right' in its parent is NOT updated.
 157  */
 158 void hfs_bnode_shift_left(struct hfs_bnode *left, struct hfs_bnode *right,
 159                           int last)
 160 {
 161         int i, adjust, nrecs;
 162         unsigned size;
 163         hfs_u16 *to, *from;
 164
 165         if ((last <= 0) || (last > right->ndNRecs)) {
 166                 hfs_warn("bad argument to shift_left: last=%d, nrecs=%d\n",
 167                        last, right->ndNRecs);
 168                 return;
 169         }
 170
 171         /* initialize variables */
 172         size = bnode_offset(right, last + 1) - sizeof(struct NodeDescriptor);
 173
 174         /* copy records to left node */
 175         memcpy(bnode_dataend(left), bnode_datastart(right), size);
 176
 177         /* move (possibly empty) remainder of right node backward */
 178         memmove(bnode_datastart(right), bnode_datastart(right) + size,
 179                         bnode_end(right) - bnode_offset(right, last + 1));
 180
 181         /* fix up offsets */
 182         nrecs = left->ndNRecs;
 183         i = last;
 184         from = RECTBL(right, 2);
 185         to = RECTBL(left, nrecs + 2);
 186         adjust = bnode_offset(left, nrecs + 1) - sizeof(struct NodeDescriptor);
 187         while (i--) {
 188                 hfs_put_hs(hfs_get_hs(from--) + adjust, to--);
 189         }
 190         i = right->ndNRecs + 1 - last;
 191         ++from;
 192         to = RECTBL(right, 1);
 193         while (i--) {
 194                 hfs_put_hs(hfs_get_hs(from--) - size, to--);
 195         }
 196
 197         /* fix record counts */
 198         left->ndNRecs += last;
 199         right->ndNRecs -= last;
 200 }
 201
 202 /*
 203  * hfs_bnode_in_brec()
 204  *
 205  * Description:
 206  *   Determines whethet a given bnode is part of a given brec.
 207  *   This is used to avoid deadlock in the case of a corrupted b-tree.
 208  * Input Variable(s):
 209  *   hfs_u32 node: the number of the node to check for.
 210  *   struct hfs_brec* brec: the brec to check in.
 211  * Output Variable(s):
 212  *   NONE
 213  * Returns:
 214  *   int: 1 it found, 0 if not
 215  * Preconditions:
 216  *   'brec' points to a valid struct hfs_brec.
 217  * Postconditions:
 218  *   'brec' is unchanged.
 219  */
 220 int hfs_bnode_in_brec(hfs_u32 node, const struct hfs_brec *brec)
 221 {
 222         const struct hfs_belem *belem = brec->bottom;
 223
 224         while (belem && (belem >= brec->top)) {
 225                 if (belem->bnr.bn && (belem->bnr.bn->node == node)) {
 226                         return 1;
 227                 }
 228                 --belem;
 229         }
 230         return 0;
 231 }