1 2 3#include "hfs_btree.h" 4 5/*================ Global functions ================*/ 6 7/* 8 * hfs_brec_relse() 9 * 10 * Description: 11 * This function releases some of the nodes associated with a brec. 12 * Input Variable(s): 13 * struct hfs_brec *brec: pointer to the brec to release some nodes from. 14 * struct hfs_belem *elem: the last node to release or NULL for all 15 * Output Variable(s): 16 * NONE 17 * Returns: 18 * void 19 * Preconditions: 20 * 'brec' points to a "valid" (struct hfs_brec) 21 * Postconditions: 22 * All nodes between the indicated node and the beginning of the path 23 * are released. 24 */ 25void hfs_brec_relse(struct hfs_brec *brec, struct hfs_belem *elem) 26{ 27 if (!elem) { 28 elem = brec->bottom; 29 } 30 31 while (brec->top <= elem) { 32 hfs_bnode_relse(&brec->top->bnr); 33 ++brec->top; 34 } 35} 36 37/* 38 * hfs_bfind() 39 * 40 * Description: 41 * This function has sole responsibility for locating existing 42 * records in a B-tree. Given a B-tree and a key it locates the 43 * "greatest" record "less than or equal to" the given key. The 44 * exact behavior is determined by the bits of the flags variable as 45 * follows: 46 * ('flags' & HFS_LOCK_MASK): 47 * The lock_type argument to be used when calling hfs_bnode_find(). 48 * HFS_BFIND_EXACT: only accept an exact match, otherwise take the 49 * "largest" record less than 'target' as a "match" 50 * HFS_BFIND_LOCK: request HFS_LOCK_WRITE access to the node containing 51 * the "matching" record when it is located 52 * HFS_BPATH_FIRST: keep access to internal nodes when accessing their 53 * first child. 54 * HFS_BPATH_OVERFLOW: keep access to internal nodes when the accessed 55 * child is too full to insert another pointer record. 56 * HFS_BPATH_UNDERFLOW: keep access to internal nodes when the accessed 57 * child is would be less than half full upon removing a pointer record. 58 * Input Variable(s): 59 * struct hfs_brec *brec: pointer to the (struct hfs_brec) to hold 60 * the search results. 61 * struct hfs_bkey *target: pointer to the (struct hfs_bkey) 62 * to search for 63 * int flags: bitwise OR of flags which determine the function's behavior 64 * Output Variable(s): 65 * 'brec' contains the results of the search on success or is invalid 66 * on failure. 67 * Returns: 68 * int: 0 or 1 on success or an error code on failure: 69 * -EINVAL: one of the input variables was NULL. 70 * -ENOENT: tree is valid but empty or no "matching" record was located. 71 * If the HFS_BFIND_EXACT bit of 'flags' is not set then the case of no 72 * matching record will give a 'brec' with a 'record' field of zero 73 * rather than returning this error. 74 * -EIO: an I/O operation or an assertion about the structure of a 75 * valid B-tree failed indicating corruption of either the B-tree 76 * structure on the disk or one of the in-core structures representing 77 * the B-tree. 78 * (This could also be returned if a kmalloc() call failed in a 79 * subordinate routine that is intended to get the data from the 80 * disk or the buffer cache.) 81 * Preconditions: 82 * 'brec' is NULL or points to a (struct hfs_brec) with a 'tree' field 83 * which points to a valid (struct hfs_btree). 84 * 'target' is NULL or points to a "valid" (struct hfs_bkey) 85 * Postconditions: 86 * If 'brec', 'brec->tree' or 'target' is NULL then -EINVAL is returned. 87 * If 'brec', 'brec->tree' and 'target' are non-NULL but the tree 88 * is empty then -ENOENT is returned. 89 * If 'brec', 'brec->tree' and 'target' are non-NULL but the call to 90 * hfs_brec_init() fails then '*brec' is NULL and -EIO is returned. 91 * If 'brec', 'brec->tree' and 'target' are non-NULL and the tree is 92 * non-empty then the tree is searched as follows: 93 * If any call to hfs_brec_next() fails or returns a node that is 94 * neither an index node nor a leaf node then -EIO is returned to 95 * indicate that the B-tree or buffer-cache are corrupted. 96 * If every record in the tree is "greater than" the given key 97 * and the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned. 98 * If every record in the tree is "greater than" the given key 99 * and the HFS_BFIND_EXACT bit of 'flags' is clear then 'brec' refers 100 * to the first leaf node in the tree and has a 'record' field of 101 * zero, and 1 is returned. 102 * If a "matching" record is located with key "equal to" 'target' 103 * then the return value is 0 and 'brec' indicates the record. 104 * If a "matching" record is located with key "greater than" 'target' 105 * then the behavior is determined as follows: 106 * If the HFS_BFIND_EXACT bit of 'flags' is not set then 1 is returned 107 * and 'brec' refers to the "matching" record. 108 * If the HFS_BFIND_EXACT bit of 'flags' is set then -ENOENT is returned. 109 * If the return value is non-negative and the HFS_BFIND_LOCK bit of 110 * 'flags' is set then hfs_brec_lock() is called on the bottom element 111 * of 'brec' before returning. 112 */ 113int hfs_bfind(struct hfs_brec *brec, struct hfs_btree *tree, 114 const struct hfs_bkey *target, int flags) 115{ 116 struct hfs_belem *curr; 117 struct hfs_bkey *key; 118 struct hfs_bnode *bn; 119 int result, ntype; 120 121 /* check for invalid arguments */ 122 if (!brec || (tree->magic != HFS_BTREE_MAGIC) || !target) { 123 return -EINVAL; 124 } 125 126 /* check for empty tree */ 127 if (!tree->root || !tree->bthNRecs) { 128 return -ENOENT; 129 } 130 131 /* start search at root of tree */ 132 if (!(curr = hfs_brec_init(brec, tree, flags))) { 133 return -EIO; 134 } 135 136 /* traverse the tree */ 137 do { 138 bn = curr->bnr.bn; 139 140 if (!curr->record) { 141 hfs_warn("hfs_bfind: empty bnode\n"); 142 hfs_brec_relse(brec, NULL); 143 return -EIO; 144 } 145 146 /* reverse linear search yielding largest key "less 147 than or equal to" 'target'. 148 It is questionable whether a binary search would be 149 significantly faster */ 150 do { 151 key = belem_key(curr); 152 if (!key->KeyLen) { 153 hfs_warn("hfs_bfind: empty key\n"); 154 hfs_brec_relse(brec, NULL); 155 return -EIO; 156 } 157 result = (tree->compare)(target, key); 158 } while ((result<0) && (--curr->record)); 159 160 ntype = bn->ndType; 161 162 /* see if all keys > target */ 163 if (!curr->record) { 164 if (bn->ndBLink) { 165 /* at a node other than the left-most at a 166 given level it means the parent had an 167 incorrect key for this child */ 168 hfs_brec_relse(brec, NULL); 169 hfs_warn("hfs_bfind: corrupted b-tree %d.\n", 170 (int)ntohl(tree->entry.cnid)); 171 return -EIO; 172 } 173 if (flags & HFS_BFIND_EXACT) { 174 /* we're not going to find it */ 175 hfs_brec_relse(brec, NULL); 176 return -ENOENT; 177 } 178 if (ntype == ndIndxNode) { 179 /* since we are at the left-most node at 180 the current level and looking for the 181 predecessor of 'target' keep going down */ 182 curr->record = 1; 183 } else { 184 /* we're at first leaf so fall through */ 185 } 186 } 187 188 /* get next node if necessary */ 189 if ((ntype == ndIndxNode) && !(curr = hfs_brec_next(brec))) { 190 return -EIO; 191 } 192 } while (ntype == ndIndxNode); 193 194 if (key->KeyLen > tree->bthKeyLen) { 195 hfs_warn("hfs_bfind: oversized key\n"); 196 hfs_brec_relse(brec, NULL); 197 return -EIO; 198 } 199 200 if (ntype != ndLeafNode) { 201 hfs_warn("hfs_bfind: invalid node type %02x in node %d of " 202 "btree %d\n", bn->ndType, bn->node, 203 (int)ntohl(tree->entry.cnid)); 204 hfs_brec_relse(brec, NULL); 205 return -EIO; 206 } 207 208 if ((flags & HFS_BFIND_EXACT) && result) { 209 hfs_brec_relse(brec, NULL); 210 return -ENOENT; 211 } 212 213 if (!(flags & HFS_BPATH_MASK)) { 214 hfs_brec_relse(brec, brec->bottom-1); 215 } 216 217 if (flags & HFS_BFIND_LOCK) { 218 hfs_brec_lock(brec, brec->bottom); 219 } 220 221 brec->key = brec_key(brec); 222 brec->data = bkey_record(brec->key); 223 224 return result ? 1 : 0; 225} 226 227/* 228 * hfs_bsucc() 229 * 230 * Description: 231 * This function overwrites '*brec' with its successor in the B-tree, 232 * obtaining the same type of access. 233 * Input Variable(s): 234 * struct hfs_brec *brec: address of the (struct hfs_brec) to overwrite 235 * with its successor 236 * Output Variable(s): 237 * struct hfs_brec *brec: address of the successor of the original 238 * '*brec' or to invalid data 239 * Returns: 240 * int: 0 on success, or one of -EINVAL, -EIO, or -EINVAL on failure 241 * Preconditions: 242 * 'brec' pointers to a "valid" (struct hfs_brec) 243 * Postconditions: 244 * If the given '*brec' is not "valid" -EINVAL is returned and 245 * '*brec' is unchanged. 246 * If the given 'brec' is "valid" but has no successor then -ENOENT 247 * is returned and '*brec' is invalid. 248 * If a call to hfs_bnode_find() is necessary to find the successor, 249 * but fails then -EIO is returned and '*brec' is invalid. 250 * If none of the three previous conditions prevents finding the 251 * successor of '*brec', then 0 is returned, and '*brec' is overwritten 252 * with the (struct hfs_brec) for its successor. 253 * In the cases when '*brec' is invalid, the old records is freed. 254 */ 255int hfs_bsucc(struct hfs_brec *brec, int count) 256{ 257 struct hfs_belem *belem; 258 struct hfs_bnode *bn; 259 260 if (!brec || !(belem = brec->bottom) || (belem != brec->top) || 261 !(bn = belem->bnr.bn) || (bn->magic != HFS_BNODE_MAGIC) || 262 !bn->tree || (bn->tree->magic != HFS_BTREE_MAGIC) || 263 !hfs_buffer_ok(bn->buf)) { 264 hfs_warn("hfs_bsucc: invalid/corrupt arguments.\n"); 265 return -EINVAL; 266 } 267 268 while (count) { 269 int left = bn->ndNRecs - belem->record; 270 271 if (left < count) { 272 struct hfs_bnode_ref old; 273 hfs_u32 node; 274 275 /* Advance to next node */ 276 if (!(node = bn->ndFLink)) { 277 hfs_brec_relse(brec, belem); 278 return -ENOENT; 279 } 280 if (node == bn->node) { 281 hfs_warn("hfs_bsucc: corrupt btree\n"); 282 hfs_brec_relse(brec, belem); 283 return -EIO; 284 } 285 old = belem->bnr; 286 belem->bnr = hfs_bnode_find(brec->tree, node, 287 belem->bnr.lock_type); 288 hfs_bnode_relse(&old); 289 if (!(bn = belem->bnr.bn)) { 290 return -EIO; 291 } 292 belem->record = 1; 293 count -= (left + 1); 294 } else { 295 belem->record += count; 296 break; 297 } 298 } 299 brec->key = belem_key(belem); 300 brec->data = bkey_record(brec->key); 301 302 if (brec->key->KeyLen > brec->tree->bthKeyLen) { 303 hfs_warn("hfs_bsucc: oversized key\n"); 304 hfs_brec_relse(brec, NULL); 305 return -EIO; 306 } 307 308 return 0; 309} 310