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