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