bdelete.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/bdelete.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 to delete records in a B-tree.
    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 /*================ Variable-like macros ================*/
   19 
   20 #define FULL (HFS_SECTOR_SIZE - sizeof(struct NodeDescriptor))
   21 #define NO_SPACE (HFS_SECTOR_SIZE+1)
   22 
   23 /*================ File-local functions ================*/
   24 
   25 /*
   26  * bdelete_nonempty()
   27  *
   28  * Description:
   29  *   Deletes a record from a given bnode without regard to it becoming empty.
   30  * Input Variable(s):
   31  *   struct hfs_brec* brec: pointer to the brec for the deletion
   32  *   struct hfs_belem* belem: which node in 'brec' to delete from
   33  * Output Variable(s):
   34  *   NONE
   35  * Returns:
   36  *   void
   37  * Preconditions:
   38  *   'brec' points to a valid (struct hfs_brec).
   39  *   'belem' points to a valid (struct hfs_belem) in 'brec'.
   40  * Postconditions:
   41  *   The record has been inserted in the position indicated by 'brec'.
   42  */
   43 static void bdelete_nonempty(struct hfs_brec *brec, struct hfs_belem *belem)
   44 {
   45         int i, rec, nrecs, tomove;
   46         hfs_u16 size;
   47         hfs_u8 *start;
   48         struct hfs_bnode *bnode = belem->bnr.bn;
   49 
   50         rec = belem->record;
   51         nrecs = bnode->ndNRecs;
   52         size = bnode_rsize(bnode, rec);
   53         tomove = bnode_offset(bnode, nrecs+1) - bnode_offset(bnode, rec+1);
   54         
   55         /* adjust the record table */
   56         for (i = rec+1; i <= nrecs; ++i) {
   57                 hfs_put_hs(bnode_offset(bnode,i+1) - size, RECTBL(bnode,i));
   58         }
   59 
   60         /* move it down */
   61         start = bnode_key(bnode, rec);
   62         memmove(start, start + size, tomove);
   63 
   64         /* update record count */
   65         --bnode->ndNRecs;
   66 }
   67 
   68 /*
   69  * del_root()
   70  *
   71  * Description:
   72  *   Delete the current root bnode.
   73  * Input Variable(s):
   74  *   struct hfs_bnode_ref *root: reference to the root bnode
   75  * Output Variable(s):
   76  *   NONE
   77  * Returns:
   78  *   int: 0 on success, error code on failure
   79  * Preconditions:
   80  *   'root' refers to the root bnode with HFS_LOCK_WRITE access.
   81  *   None of 'root's children are held with HFS_LOCK_WRITE access.
   82  * Postconditions:
   83  *   The current 'root' node is removed from the tree and the depth
   84  *    of the tree is reduced by one.
   85  *   If 'root' is an index node with exactly one child, then that
   86  *    child becomes the new root of the tree.
   87  *   If 'root' is an empty leaf node the tree becomes empty.
   88  *   Upon return access to 'root' is relinquished.
   89  */
   90 static int del_root(struct hfs_bnode_ref *root)
   91 {
   92         struct hfs_btree *tree = root->bn->tree;
   93         struct hfs_bnode_ref child;
   94         hfs_u32 node;
   95 
   96         if (root->bn->ndNRecs > 1) {
   97                 return 0;
   98         } else if (root->bn->ndNRecs == 0) {
   99                 /* tree is empty */
  100                 tree->bthRoot = 0;
  101                 tree->root = NULL;
  102                 tree->bthRoot = 0;
  103                 tree->bthFNode = 0;
  104                 tree->bthLNode = 0;
  105                 --tree->bthDepth;
  106                 tree->dirt = 1;
  107                 if (tree->bthDepth) {
  108                         hfs_warn("hfs_bdelete: empty tree with bthDepth=%d\n",
  109                                  tree->bthDepth);
  110                         goto bail;
  111                 }
  112                 return hfs_bnode_free(root);
  113         } else if (root->bn->ndType == ndIndxNode) {
  114                 /* tree is non-empty */
  115                 node = hfs_get_hl(bkey_record(bnode_datastart(root->bn)));
  116 
  117                 child = hfs_bnode_find(tree, node, HFS_LOCK_READ);
  118                 if (!child.bn) {
  119                         hfs_warn("hfs_bdelete: can't read child node.\n");
  120                         goto bail;
  121                 }
  122                         
  123                 child.bn->sticky = HFS_STICKY;
  124                 if (child.bn->next) {
  125                         child.bn->next->prev = child.bn->prev;
  126                 }
  127                 if (child.bn->prev) {
  128                         child.bn->prev->next = child.bn->next;
  129                 }
  130                 if (bhash(tree, child.bn->node) == child.bn) {
  131                         bhash(tree, child.bn->node) = child.bn->next;
  132                 }
  133                 child.bn->next = NULL;
  134                 child.bn->prev = NULL;
  135 
  136                 tree->bthRoot = child.bn->node;
  137                 tree->root = child.bn;
  138 
  139                 /* re-assign bthFNode and bthLNode if the new root is
  140                    a leaf node. */
  141                 if (child.bn->ndType == ndLeafNode) {
  142                         tree->bthFNode = node;
  143                         tree->bthLNode = node;
  144                 }
  145                 hfs_bnode_relse(&child);
  146 
  147                 tree->bthRoot = node;
  148                 --tree->bthDepth;
  149                 tree->dirt = 1;
  150                 if (!tree->bthDepth) {
  151                         hfs_warn("hfs_bdelete: non-empty tree with "
  152                                  "bthDepth == 0\n");
  153                         goto bail;
  154                 }
  155                 return hfs_bnode_free(root);    /* marks tree dirty */
  156         }
  157         hfs_bnode_relse(root);
  158         return 0;
  159 
  160 bail:
  161         hfs_bnode_relse(root);
  162         return -EIO;
  163 }
  164 
  165 
  166 /*
  167  * delete_empty_bnode()
  168  *
  169  * Description:
  170  *   Removes an empty non-root bnode from between 'left' and 'right'
  171  * Input Variable(s):
  172  *   hfs_u32 left_node: node number of 'left' or zero if 'left' is invalid
  173  *   struct hfs_bnode_ref *left: reference to the left neighbor of the
  174  *    bnode to remove, or invalid if no such neighbor exists.
  175  *   struct hfs_bnode_ref *center: reference to the bnode to remove
  176  *   hfs_u32 right_node: node number of 'right' or zero if 'right' is invalid
  177  *   struct hfs_bnode_ref *right: reference to the right neighbor of the
  178  *    bnode to remove, or invalid if no such neighbor exists.
  179  * Output Variable(s):
  180  *   NONE
  181  * Returns:
  182  *   void
  183  * Preconditions:
  184  *   'left_node' is as described above.
  185  *   'left' points to a valid (struct hfs_bnode_ref) having HFS_LOCK_WRITE
  186  *    access and referring to the left neighbor of 'center' if such a
  187  *    neighbor exists, or invalid if no such neighbor exists.
  188  *   'center' points to a valid (struct hfs_bnode_ref) having HFS_LOCK_WRITE
  189  *    access and referring to the bnode to delete.
  190  *   'right_node' is as described above.
  191  *   'right' points to a valid (struct hfs_bnode_ref) having HFS_LOCK_WRITE
  192  *    access and referring to the right neighbor of 'center' if such a
  193  *    neighbor exists, or invalid if no such neighbor exists.
  194  * Postconditions:
  195  *   If 'left' is valid its 'ndFLink' field becomes 'right_node'.
  196  *   If 'right' is valid its 'ndBLink' field becomes 'left_node'.
  197  *   If 'center' was the first leaf node then the tree's 'bthFNode'
  198  *    field becomes 'right_node' 
  199  *   If 'center' was the last leaf node then the tree's 'bthLNode'
  200  *    field becomes 'left_node' 
  201  *   'center' is NOT freed and access to the nodes is NOT relinquished.
  202  */
  203 static void delete_empty_bnode(hfs_u32 left_node, struct hfs_bnode_ref *left,
  204                                struct hfs_bnode_ref *center,
  205                                hfs_u32 right_node, struct hfs_bnode_ref *right)
  206 {
  207         struct hfs_bnode *bnode = center->bn;
  208 
  209         if (left_node) {
  210                 left->bn->ndFLink = right_node;
  211         } else if (bnode->ndType == ndLeafNode) {
  212                 bnode->tree->bthFNode = right_node;
  213                 bnode->tree->dirt = 1;
  214         }
  215 
  216         if (right_node) {
  217                 right->bn->ndBLink = left_node;
  218         } else if (bnode->ndType == ndLeafNode) {
  219                 bnode->tree->bthLNode = left_node;
  220                 bnode->tree->dirt = 1;
  221         }
  222 }
  223 
  224 /*
  225  * balance()
  226  *
  227  * Description:
  228  *   Attempt to equalize space usage in neighboring bnodes.
  229  * Input Variable(s):
  230  *   struct hfs_bnode *left: the left bnode.
  231  *   struct hfs_bnode *right: the right bnode.
  232  * Output Variable(s):
  233  *   NONE
  234  * Returns:
  235  *   void
  236  * Preconditions:
  237  *   'left' and 'right' point to valid (struct hfs_bnode)s obtained
  238  *    with HFS_LOCK_WRITE access, and are neighbors.
  239  * Postconditions:
  240  *   Records are shifted either left or right to make the space usage
  241  *   nearly equal.  When exact equality is not possible the break
  242  *   point is chosen to reduce data movement.
  243  *   The key corresponding to 'right' in its parent is NOT updated.
  244  */
  245 static void balance(struct hfs_bnode *left, struct hfs_bnode *right)
  246 {
  247         int index, left_free, right_free, half;
  248 
  249         left_free = bnode_freespace(left);
  250         right_free = bnode_freespace(right);
  251         half = (left_free + right_free)/2;
  252 
  253         if (left_free < right_free) {
  254                 /* shift right to balance */
  255                 index = left->ndNRecs + 1;
  256                 while (right_free >= half) {
  257                         --index;
  258                         right_free -= bnode_rsize(left,index)+sizeof(hfs_u16);
  259                 }
  260                 if (index < left->ndNRecs) {
  261 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
  262                         hfs_warn("shifting %d of %d recs right to balance: ",
  263                                left->ndNRecs - index, left->ndNRecs);
  264 #endif
  265                         hfs_bnode_shift_right(left, right, index+1);
  266 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
  267                         hfs_warn("%d,%d\n", left->ndNRecs, right->ndNRecs);
  268 #endif
  269                 }
  270         } else {
  271                 /* shift left to balance */
  272                 index = 0;
  273                 while (left_free >= half) {
  274                         ++index;
  275                         left_free -= bnode_rsize(right,index)+sizeof(hfs_u16);
  276                 }
  277                 if (index > 1) {
  278 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
  279                         hfs_warn("shifting %d of %d recs left to balance: ",
  280                                index-1, right->ndNRecs);
  281 #endif
  282                         hfs_bnode_shift_left(left, right, index-1);
  283 #if defined(DEBUG_ALL) || defined(DEBUG_BALANCE)
  284                         hfs_warn("%d,%d\n", left->ndNRecs, right->ndNRecs);
  285 #endif
  286                 }
  287         }
  288 }
  289 
  290 /*
  291  * bdelete()
  292  *
  293  * Delete the given record from a B-tree.
  294  */
  295 static int bdelete(struct hfs_brec *brec)
  296 {
  297         struct hfs_btree *tree = brec->tree;
  298         struct hfs_belem *belem = brec->bottom;
  299         struct hfs_belem *parent = (belem-1);
  300         struct hfs_bnode *bnode;
  301         hfs_u32 left_node, right_node;
  302         struct hfs_bnode_ref left, right;
  303         int left_space, right_space, min_space;
  304         int fix_right_key;
  305         int fix_key;
  306         
  307         while ((belem > brec->top) &&
  308                (belem->flags & (HFS_BPATH_UNDERFLOW | HFS_BPATH_FIRST))) {
  309                 bnode = belem->bnr.bn;
  310                 fix_key = belem->flags & HFS_BPATH_FIRST;
  311                 fix_right_key = 0;
  312 
  313                 bdelete_nonempty(brec, belem);
  314 
  315                 if (bnode->node == tree->root->node) {
  316                         del_root(&belem->bnr);
  317                         --brec->bottom;
  318                         goto done;
  319                 }
  320 
  321                 /* check for btree corruption which could lead to deadlock */
  322                 left_node = bnode->ndBLink;
  323                 right_node = bnode->ndFLink;
  324                 if ((left_node && hfs_bnode_in_brec(left_node, brec)) ||
  325                     (right_node && hfs_bnode_in_brec(right_node, brec)) ||
  326                     (left_node == right_node)) {
  327                         hfs_warn("hfs_bdelete: corrupt btree\n");
  328                         hfs_brec_relse(brec, NULL);
  329                         return -EIO;
  330                 }
  331 
  332                 /* grab the left neighbor if it exists */
  333                 if (left_node) {
  334                         hfs_bnode_lock(&belem->bnr, HFS_LOCK_RESRV);
  335                         left = hfs_bnode_find(tree,left_node,HFS_LOCK_WRITE);
  336                         if (!left.bn) {
  337                                 hfs_warn("hfs_bdelete: unable to read left "
  338                                          "neighbor.\n");
  339                                 hfs_brec_relse(brec, NULL);
  340                                 return -EIO;
  341                         }
  342                         hfs_bnode_lock(&belem->bnr, HFS_LOCK_WRITE);
  343                         if (parent->record != 1) {
  344                                 left_space = bnode_freespace(left.bn);
  345                         } else {
  346                                 left_space = NO_SPACE;
  347                         }
  348                 } else {
  349                         left.bn = NULL;
  350                         left_space = NO_SPACE;
  351                 }
  352 
  353                 /* grab the right neighbor if it exists */
  354                 if (right_node) {
  355                         right = hfs_bnode_find(tree,right_node,HFS_LOCK_WRITE);
  356                         if (!right.bn) {
  357                                 hfs_warn("hfs_bdelete: unable to read right "
  358                                          "neighbor.\n");
  359                                 hfs_bnode_relse(&left);
  360                                 hfs_brec_relse(brec, NULL);
  361                                 return -EIO;
  362                         }
  363                         if (parent->record < parent->bnr.bn->ndNRecs) {
  364                                 right_space = bnode_freespace(right.bn);
  365                         } else {
  366                                 right_space = NO_SPACE;
  367                         }
  368                 } else {
  369                         right.bn = NULL;
  370                         right_space = NO_SPACE;
  371                 }
  372 
  373                 if (left_space < right_space) {
  374                         min_space = left_space;
  375                 } else {
  376                         min_space = right_space;
  377                 }
  378 
  379                 if (min_space == NO_SPACE) {
  380                         hfs_warn("hfs_bdelete: no siblings?\n");
  381                         hfs_brec_relse(brec, NULL);
  382                         return -EIO;
  383                 }
  384 
  385                 if (bnode->ndNRecs == 0) {
  386                         delete_empty_bnode(left_node, &left, &belem->bnr,
  387                                            right_node, &right);
  388                 } else if (min_space + bnode_freespace(bnode) >= FULL) {
  389                         if ((right_space == NO_SPACE) ||
  390                             ((right_space == min_space) &&
  391                              (left_space != NO_SPACE))) {
  392                                 hfs_bnode_shift_left(left.bn, bnode,
  393                                                      bnode->ndNRecs);
  394                         } else {
  395                                 hfs_bnode_shift_right(bnode, right.bn, 1);
  396                                 fix_right_key = 1;
  397                         }
  398                         delete_empty_bnode(left_node, &left, &belem->bnr,
  399                                            right_node, &right);
  400                 } else if (min_space == right_space) {
  401                         balance(bnode, right.bn);
  402                         fix_right_key = 1;
  403                 } else {
  404                         balance(left.bn, bnode);
  405                         fix_key = 1;
  406                 }
  407 
  408                 if (fix_right_key) {
  409                         hfs_bnode_update_key(brec, belem, right.bn, 1);
  410                 }
  411 
  412                 hfs_bnode_relse(&left);
  413                 hfs_bnode_relse(&right);
  414 
  415                 if (bnode->ndNRecs) {
  416                         if (fix_key) {
  417                                 hfs_bnode_update_key(brec, belem, bnode, 0);
  418                         }
  419                         goto done;
  420                 }
  421 
  422                 hfs_bnode_free(&belem->bnr);
  423                 --brec->bottom;
  424                 belem = parent;
  425                 --parent;
  426         }
  427 
  428         if (belem < brec->top) {
  429                 hfs_warn("hfs_bdelete: Missing parent.\n");
  430                 hfs_brec_relse(brec, NULL);
  431                 return -EIO;
  432         }
  433 
  434         bdelete_nonempty(brec, belem);
  435 
  436 done:
  437         hfs_brec_relse(brec, NULL);
  438         return 0;
  439 }
  440 
  441 /*================ Global functions ================*/
  442 
  443 /*
  444  * hfs_bdelete()
  445  *
  446  * Delete the requested record from a B-tree.
  447  */
  448 int hfs_bdelete(struct hfs_btree *tree, const struct hfs_bkey *key)
  449 { 
  450         struct hfs_belem *belem;
  451         struct hfs_bnode *bnode;
  452         struct hfs_brec brec;
  453         int retval;
  454 
  455         if (!tree || (tree->magic != HFS_BTREE_MAGIC) || !key) {
  456                 hfs_warn("hfs_bdelete: invalid arguments.\n");
  457                 return -EINVAL;
  458         }
  459 
  460         retval = hfs_bfind(&brec, tree, key, HFS_BFIND_DELETE);
  461         if (!retval) {
  462                 belem = brec.bottom;
  463                 bnode = belem->bnr.bn;
  464 
  465                 belem->flags = 0;
  466                 if ((bnode->ndNRecs * sizeof(hfs_u16) + bnode_end(bnode) -
  467                      bnode_rsize(bnode, belem->record)) < FULL/2) {
  468                         belem->flags |= HFS_BPATH_UNDERFLOW;
  469                 }
  470                 if (belem->record == 1) {
  471                         belem->flags |= HFS_BPATH_FIRST;
  472                 }
  473 
  474                 if (!belem->flags) {
  475                         hfs_brec_lock(&brec, brec.bottom);
  476                 } else {
  477                         hfs_brec_lock(&brec, NULL);
  478                 }
  479 
  480                 retval = bdelete(&brec);
  481                 if (!retval) {
  482                         --brec.tree->bthNRecs;
  483                         brec.tree->dirt = 1;
  484                 }
  485                 hfs_brec_relse(&brec, NULL);
  486         }
  487         return retval;
  488 }
Cache object: 2c7c8cd4bd7f2645cd8866934e7e745d
[ 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/bdelete.c

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