1 /* 2 * linux/fs/hfsplus/bfind.c 3 * 4 * Copyright (C) 2001 5 * Brad Boyer (flar@allandria.com) 6 * (C) 2003 Ardis Technologies <roman@ardistech.com> 7 * 8 * Search routines for btrees 9 */ 10 11 #include <linux/slab.h> 12 #include "hfsplus_fs.h" 13 14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) 15 { 16 void *ptr; 17 18 fd->tree = tree; 19 fd->bnode = NULL; 20 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); 21 if (!ptr) 22 return -ENOMEM; 23 fd->search_key = ptr; 24 fd->key = ptr + tree->max_key_len + 2; 25 dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", 26 tree->cnid, __builtin_return_address(0)); 27 switch (tree->cnid) { 28 case HFSPLUS_CAT_CNID: 29 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); 30 break; 31 case HFSPLUS_EXT_CNID: 32 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); 33 break; 34 case HFSPLUS_ATTR_CNID: 35 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); 36 break; 37 default: 38 BUG(); 39 } 40 return 0; 41 } 42 43 void hfs_find_exit(struct hfs_find_data *fd) 44 { 45 hfs_bnode_put(fd->bnode); 46 kfree(fd->search_key); 47 dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", 48 fd->tree->cnid, __builtin_return_address(0)); 49 mutex_unlock(&fd->tree->tree_lock); 50 fd->tree = NULL; 51 } 52 53 int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode, 54 struct hfs_find_data *fd, 55 int *begin, 56 int *end, 57 int *cur_rec) 58 { 59 __be32 cur_cnid, search_cnid; 60 61 if (bnode->tree->cnid == HFSPLUS_EXT_CNID) { 62 cur_cnid = fd->key->ext.cnid; 63 search_cnid = fd->search_key->ext.cnid; 64 } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) { 65 cur_cnid = fd->key->cat.parent; 66 search_cnid = fd->search_key->cat.parent; 67 } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) { 68 cur_cnid = fd->key->attr.cnid; 69 search_cnid = fd->search_key->attr.cnid; 70 } else 71 BUG(); 72 73 if (cur_cnid == search_cnid) { 74 (*end) = (*cur_rec); 75 if ((*begin) == (*end)) 76 return 1; 77 } else { 78 if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid)) 79 (*begin) = (*cur_rec) + 1; 80 else 81 (*end) = (*cur_rec) - 1; 82 } 83 84 return 0; 85 } 86 87 int hfs_find_rec_by_key(struct hfs_bnode *bnode, 88 struct hfs_find_data *fd, 89 int *begin, 90 int *end, 91 int *cur_rec) 92 { 93 int cmpval; 94 95 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); 96 if (!cmpval) { 97 (*end) = (*cur_rec); 98 return 1; 99 } 100 if (cmpval < 0) 101 (*begin) = (*cur_rec) + 1; 102 else 103 *(end) = (*cur_rec) - 1; 104 105 return 0; 106 } 107 108 /* Find the record in bnode that best matches key (not greater than...)*/ 109 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, 110 search_strategy_t rec_found) 111 { 112 u16 off, len, keylen; 113 int rec; 114 int b, e; 115 int res; 116 117 if (!rec_found) 118 BUG(); 119 120 b = 0; 121 e = bnode->num_recs - 1; 122 res = -ENOENT; 123 do { 124 rec = (e + b) / 2; 125 len = hfs_brec_lenoff(bnode, rec, &off); 126 keylen = hfs_brec_keylen(bnode, rec); 127 if (keylen == 0) { 128 res = -EINVAL; 129 goto fail; 130 } 131 hfs_bnode_read(bnode, fd->key, off, keylen); 132 if (rec_found(bnode, fd, &b, &e, &rec)) { 133 res = 0; 134 goto done; 135 } 136 } while (b <= e); 137 138 if (rec != e && e >= 0) { 139 len = hfs_brec_lenoff(bnode, e, &off); 140 keylen = hfs_brec_keylen(bnode, e); 141 if (keylen == 0) { 142 res = -EINVAL; 143 goto fail; 144 } 145 hfs_bnode_read(bnode, fd->key, off, keylen); 146 } 147 148 done: 149 fd->record = e; 150 fd->keyoffset = off; 151 fd->keylength = keylen; 152 fd->entryoffset = off + keylen; 153 fd->entrylength = len - keylen; 154 155 fail: 156 return res; 157 } 158 159 /* Traverse a B*Tree from the root to a leaf finding best fit to key */ 160 /* Return allocated copy of node found, set recnum to best record */ 161 int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) 162 { 163 struct hfs_btree *tree; 164 struct hfs_bnode *bnode; 165 u32 nidx, parent; 166 __be32 data; 167 int height, res; 168 169 tree = fd->tree; 170 if (fd->bnode) 171 hfs_bnode_put(fd->bnode); 172 fd->bnode = NULL; 173 nidx = tree->root; 174 if (!nidx) 175 return -ENOENT; 176 height = tree->depth; 177 res = 0; 178 parent = 0; 179 for (;;) { 180 bnode = hfs_bnode_find(tree, nidx); 181 if (IS_ERR(bnode)) { 182 res = PTR_ERR(bnode); 183 bnode = NULL; 184 break; 185 } 186 if (bnode->height != height) 187 goto invalid; 188 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 189 goto invalid; 190 bnode->parent = parent; 191 192 res = __hfs_brec_find(bnode, fd, do_key_compare); 193 if (!height) 194 break; 195 if (fd->record < 0) 196 goto release; 197 198 parent = nidx; 199 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 200 nidx = be32_to_cpu(data); 201 hfs_bnode_put(bnode); 202 } 203 fd->bnode = bnode; 204 return res; 205 206 invalid: 207 printk(KERN_ERR "hfs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 208 height, bnode->height, bnode->type, nidx, parent); 209 res = -EIO; 210 release: 211 hfs_bnode_put(bnode); 212 return res; 213 } 214 215 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) 216 { 217 int res; 218 219 res = hfs_brec_find(fd, hfs_find_rec_by_key); 220 if (res) 221 return res; 222 if (fd->entrylength > rec_len) 223 return -EINVAL; 224 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 225 return 0; 226 } 227 228 int hfs_brec_goto(struct hfs_find_data *fd, int cnt) 229 { 230 struct hfs_btree *tree; 231 struct hfs_bnode *bnode; 232 int idx, res = 0; 233 u16 off, len, keylen; 234 235 bnode = fd->bnode; 236 tree = bnode->tree; 237 238 if (cnt < 0) { 239 cnt = -cnt; 240 while (cnt > fd->record) { 241 cnt -= fd->record + 1; 242 fd->record = bnode->num_recs - 1; 243 idx = bnode->prev; 244 if (!idx) { 245 res = -ENOENT; 246 goto out; 247 } 248 hfs_bnode_put(bnode); 249 bnode = hfs_bnode_find(tree, idx); 250 if (IS_ERR(bnode)) { 251 res = PTR_ERR(bnode); 252 bnode = NULL; 253 goto out; 254 } 255 } 256 fd->record -= cnt; 257 } else { 258 while (cnt >= bnode->num_recs - fd->record) { 259 cnt -= bnode->num_recs - fd->record; 260 fd->record = 0; 261 idx = bnode->next; 262 if (!idx) { 263 res = -ENOENT; 264 goto out; 265 } 266 hfs_bnode_put(bnode); 267 bnode = hfs_bnode_find(tree, idx); 268 if (IS_ERR(bnode)) { 269 res = PTR_ERR(bnode); 270 bnode = NULL; 271 goto out; 272 } 273 } 274 fd->record += cnt; 275 } 276 277 len = hfs_brec_lenoff(bnode, fd->record, &off); 278 keylen = hfs_brec_keylen(bnode, fd->record); 279 if (keylen == 0) { 280 res = -EINVAL; 281 goto out; 282 } 283 fd->keyoffset = off; 284 fd->keylength = keylen; 285 fd->entryoffset = off + keylen; 286 fd->entrylength = len - keylen; 287 hfs_bnode_read(bnode, fd->key, off, keylen); 288 out: 289 fd->bnode = bnode; 290 return res; 291 } 292