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 down(&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 up(&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 hfs_bnode_read(bnode, fd->key, off, keylen); 79 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); 80 if (!cmpval) { 81 e = rec; 82 res = 0; 83 goto done; 84 } 85 if (cmpval < 0) 86 b = rec + 1; 87 else 88 e = rec - 1; 89 } while (b <= e); 90 if (rec != e && e >= 0) { 91 len = hfs_brec_lenoff(bnode, e, &off); 92 keylen = hfs_brec_keylen(bnode, e); 93 hfs_bnode_read(bnode, fd->key, off, keylen); 94 } 95done: 96 fd->record = e; 97 fd->keyoffset = off; 98 fd->keylength = keylen; 99 fd->entryoffset = off + keylen; 100 fd->entrylength = len - keylen; 101 return res; 102} 103 104/* Traverse a B*Tree from the root to a leaf finding best fit to key */ 105/* Return allocated copy of node found, set recnum to best record */ 106int hfs_brec_find(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd) 107{ 108 struct hfs_btree *tree; 109 struct hfs_bnode *bnode; 110 u32 nidx, parent; 111 __be32 data; 112 int height, res; 113 114 tree = fd->tree; 115 if (fd->bnode) 116 hfs_bnode_put(hfsplus_handle, fd->bnode); 117 fd->bnode = NULL; 118 nidx = tree->root; 119 if (!nidx) 120 return -ENOENT; 121 height = tree->depth; 122 res = 0; 123 parent = 0; 124 for (;;) { 125 bnode = hfs_bnode_find(hfsplus_handle, tree, nidx); 126 if (IS_ERR(bnode)) { 127 res = PTR_ERR(bnode); 128 bnode = NULL; 129 break; 130 } 131 if (bnode->height != height) 132 goto invalid; 133 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 134 goto invalid; 135 bnode->parent = parent; 136 137 res = __hfs_brec_find(bnode, fd); 138 if (!height) 139 break; 140 if (fd->record < 0) 141 goto release; 142 143 parent = nidx; 144 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 145 nidx = be32_to_cpu(data); 146 hfs_bnode_put(hfsplus_handle, bnode); 147 } 148 fd->bnode = bnode; 149 return res; 150 151invalid: 152 printk("HFS+-fs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 153 height, bnode->height, bnode->type, nidx, parent); 154 res = -EIO; 155release: 156 hfs_bnode_put(hfsplus_handle, bnode); 157 return res; 158} 159 160int hfs_brec_read(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd, void *rec, int rec_len) 161{ 162 int res; 163 164 res = hfs_brec_find(hfsplus_handle, fd); 165 if (res) 166 return res; 167 if (fd->entrylength > rec_len) 168 return -EINVAL; 169 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 170 return 0; 171} 172 173int hfs_brec_goto(hfsplus_handle_t *hfsplus_handle, struct hfs_find_data *fd, int cnt) 174{ 175 struct hfs_btree *tree; 176 struct hfs_bnode *bnode; 177 int idx, res = 0; 178 u16 off, len, keylen; 179 180 bnode = fd->bnode; 181 tree = bnode->tree; 182 183 if (cnt < 0) { 184 cnt = -cnt; 185 while (cnt > fd->record) { 186 cnt -= fd->record + 1; 187 fd->record = bnode->num_recs - 1; 188 idx = bnode->prev; 189 if (!idx) { 190 res = -ENOENT; 191 goto out; 192 } 193 hfs_bnode_put(hfsplus_handle, bnode); 194 bnode = hfs_bnode_find(hfsplus_handle, tree, idx); 195 if (IS_ERR(bnode)) { 196 res = PTR_ERR(bnode); 197 bnode = NULL; 198 goto out; 199 } 200 } 201 fd->record -= cnt; 202 } else { 203 while (cnt >= bnode->num_recs - fd->record) { 204 cnt -= bnode->num_recs - fd->record; 205 fd->record = 0; 206 idx = bnode->next; 207 if (!idx) { 208 res = -ENOENT; 209 goto out; 210 } 211 hfs_bnode_put(hfsplus_handle, bnode); 212 bnode = hfs_bnode_find(hfsplus_handle, tree, idx); 213 if (IS_ERR(bnode)) { 214 res = PTR_ERR(bnode); 215 bnode = NULL; 216 goto out; 217 } 218 } 219 fd->record += cnt; 220 } 221 222 len = hfs_brec_lenoff(bnode, fd->record, &off); 223 keylen = hfs_brec_keylen(bnode, fd->record); 224 fd->keyoffset = off; 225 fd->keylength = keylen; 226 fd->entryoffset = off + keylen; 227 fd->entrylength = len - keylen; 228 hfs_bnode_read(bnode, fd->key, off, keylen); 229out: 230 fd->bnode = bnode; 231 return res; 232} 233