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