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