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