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 14int 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", tree->cnid, __builtin_return_address(0)); 26 mutex_lock(&tree->tree_lock); 27 return 0; 28} 29 30void hfs_find_exit(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd) 31{ 32 hfs_bnode_put(hfsplus_handle, fd->bnode); 33 kfree(fd->search_key); 34 dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0)); 35 mutex_unlock(&fd->tree->tree_lock); 36 fd->tree = NULL; 37} 38 39int hfsplus_journalled_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) 40{ 41 void *ptr; 42 43 fd->tree = tree; 44 fd->bnode = NULL; 45 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); 46 if (!ptr) 47 return -ENOMEM; 48 fd->search_key = ptr; 49 fd->key = ptr + tree->max_key_len + 2; 50 dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0)); 51 return 0; 52} 53 54void hfsplus_journalled_find_exit(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd) 55{ 56 hfs_bnode_put(hfsplus_handle, fd->bnode); 57 kfree(fd->search_key); 58 dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0)); 59 fd->tree = NULL; 60} 61 62/* Find the record in bnode that best matches key (not greater than...)*/ 63int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd) 64{ 65 int cmpval; 66 u16 off, len, keylen; 67 int rec; 68 int b, e; 69 int res; 70 71 b = 0; 72 e = bnode->num_recs - 1; 73 res = -ENOENT; 74 do { 75 rec = (e + b) / 2; 76 len = hfs_brec_lenoff(bnode, rec, &off); 77 keylen = hfs_brec_keylen(bnode, rec); 78 if (keylen == 0) { 79 res = -EINVAL; 80 goto fail; 81 } 82 hfs_bnode_read(bnode, fd->key, off, keylen); 83 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); 84 if (!cmpval) { 85 e = rec; 86 res = 0; 87 goto done; 88 } 89 if (cmpval < 0) 90 b = rec + 1; 91 else 92 e = rec - 1; 93 } while (b <= e); 94 if (rec != e && e >= 0) { 95 len = hfs_brec_lenoff(bnode, e, &off); 96 keylen = hfs_brec_keylen(bnode, e); 97 if (keylen == 0) { 98 res = -EINVAL; 99 goto fail; 100 } 101 hfs_bnode_read(bnode, fd->key, off, keylen); 102 } 103done: 104 fd->record = e; 105 fd->keyoffset = off; 106 fd->keylength = keylen; 107 fd->entryoffset = off + keylen; 108 fd->entrylength = len - keylen; 109fail: 110 return res; 111} 112 113/* Traverse a B*Tree from the root to a leaf finding best fit to key */ 114/* Return allocated copy of node found, set recnum to best record */ 115int hfs_brec_find(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd) 116{ 117 struct hfs_btree *tree; 118 struct hfs_bnode *bnode; 119 u32 nidx, parent; 120 __be32 data; 121 int height, res; 122 123 tree = fd->tree; 124 if (fd->bnode) 125 hfs_bnode_put(hfsplus_handle, fd->bnode); 126 fd->bnode = NULL; 127 nidx = tree->root; 128 if (!nidx) 129 return -ENOENT; 130 height = tree->depth; 131 res = 0; 132 parent = 0; 133 for (;;) { 134 bnode = hfs_bnode_find(hfsplus_handle, tree, nidx); 135 if (IS_ERR(bnode)) { 136 res = PTR_ERR(bnode); 137 bnode = NULL; 138 break; 139 } 140 if (bnode->height != height) 141 goto invalid; 142 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 143 goto invalid; 144 bnode->parent = parent; 145 146 res = __hfs_brec_find(bnode, fd); 147 if (!height) 148 break; 149 if (fd->record < 0) 150 goto release; 151 152 parent = nidx; 153 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 154 nidx = be32_to_cpu(data); 155 hfs_bnode_put(hfsplus_handle, bnode); 156 } 157 fd->bnode = bnode; 158 return res; 159 160invalid: 161 printk("HFS+-fs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 162 height, bnode->height, bnode->type, nidx, parent); 163 res = -EIO; 164release: 165 hfs_bnode_put(hfsplus_handle, bnode); 166 return res; 167} 168 169int hfs_brec_read(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd, void *rec, int rec_len) 170{ 171 int res; 172 173 res = hfs_brec_find(hfsplus_handle, fd); 174 if (res) 175 return res; 176 if (fd->entrylength > rec_len) 177 return -EINVAL; 178 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 179 return 0; 180} 181 182int hfs_brec_goto(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd, int cnt) 183{ 184 struct hfs_btree *tree; 185 struct hfs_bnode *bnode; 186 int idx, res = 0; 187 u16 off, len, keylen; 188 189 bnode = fd->bnode; 190 tree = bnode->tree; 191 192 if (cnt < 0) { 193 cnt = -cnt; 194 while (cnt > fd->record) { 195 cnt -= fd->record + 1; 196 fd->record = bnode->num_recs - 1; 197 idx = bnode->prev; 198 if (!idx) { 199 res = -ENOENT; 200 goto out; 201 } 202 hfs_bnode_put(hfsplus_handle, bnode); 203 bnode = hfs_bnode_find(hfsplus_handle, tree, idx); 204 if (IS_ERR(bnode)) { 205 res = PTR_ERR(bnode); 206 bnode = NULL; 207 goto out; 208 } 209 } 210 fd->record -= cnt; 211 } else { 212 while (cnt >= bnode->num_recs - fd->record) { 213 cnt -= bnode->num_recs - fd->record; 214 fd->record = 0; 215 idx = bnode->next; 216 if (!idx) { 217 res = -ENOENT; 218 goto out; 219 } 220 hfs_bnode_put(hfsplus_handle, bnode); 221 bnode = hfs_bnode_find(hfsplus_handle, tree, idx); 222 if (IS_ERR(bnode)) { 223 res = PTR_ERR(bnode); 224 bnode = NULL; 225 goto out; 226 } 227 } 228 fd->record += cnt; 229 } 230 231 len = hfs_brec_lenoff(bnode, fd->record, &off); 232 keylen = hfs_brec_keylen(bnode, fd->record); 233 if (keylen == 0) { 234 res = -EINVAL; 235 goto out; 236 } 237 fd->keyoffset = off; 238 fd->keylength = keylen; 239 fd->entryoffset = off + keylen; 240 fd->entrylength = len - keylen; 241 hfs_bnode_read(bnode, fd->key, off, keylen); 242out: 243 fd->bnode = bnode; 244 return res; 245} 246