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