Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
FreeBSD/Linux Kernel Cross Reference
sys/fs/hfsplus/bfind.c
Version:
- FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
SearchContext: - none - 3 - 10
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 /* Find the record in bnode that best matches key (not greater than...)*/ 15 void hfsplus_find_rec(hfsplus_bnode *bnode, struct hfsplus_find_data *fd) 16 { 17 int cmpval; 18 u16 off, len, keylen; 19 int rec; 20 int b, e; 21 22 b = 0; 23 e = bnode->num_recs - 1; 24 do { 25 rec = (e + b) / 2; 26 len = hfsplus_brec_lenoff(bnode, rec, &off); 27 keylen = hfsplus_brec_keylen(bnode, rec); 28 hfsplus_bnode_readbytes(bnode, fd->key, off, keylen); 29 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); 30 if (!cmpval) { 31 fd->exact = 1; 32 e = rec; 33 break; 34 } 35 if (cmpval < 0) 36 b = rec + 1; 37 else 38 e = rec - 1; 39 } while (b <= e); 40 //printk("%d: %d,%d,%d\n", bnode->this, b, e, rec); 41 if (rec != e && e >= 0) { 42 len = hfsplus_brec_lenoff(bnode, e, &off); 43 keylen = hfsplus_brec_keylen(bnode, e); 44 hfsplus_bnode_readbytes(bnode, fd->key, off, keylen); 45 } 46 fd->record = e; 47 fd->keyoffset = off; 48 fd->keylength = keylen; 49 fd->entryoffset = off + keylen; 50 fd->entrylength = len - keylen; 51 } 52 53 /* Traverse a B*Tree from the root to a leaf finding best fit to key */ 54 /* Return allocated copy of node found, set recnum to best record */ 55 int hfsplus_btree_find(struct hfsplus_find_data *fd) 56 { 57 hfsplus_btree *tree; 58 hfsplus_bnode *bnode; 59 u32 data, nidx, parent; 60 int height, err; 61 62 tree = fd->tree; 63 if (fd->bnode) 64 hfsplus_put_bnode(fd->bnode); 65 fd->bnode = NULL; 66 fd->exact = 0; 67 nidx = tree->root; 68 if (!nidx) 69 return -ENOENT; 70 height = tree->depth; 71 err = 0; 72 parent = 0; 73 for (;;) { 74 bnode = hfsplus_find_bnode(tree, nidx); 75 if (!bnode) { 76 err = -EIO; 77 break; 78 } 79 if (bnode->height != height) 80 goto invalid; 81 if (bnode->kind != (--height ? HFSPLUS_NODE_NDX : HFSPLUS_NODE_LEAF)) 82 goto invalid; 83 bnode->parent = parent; 84 85 hfsplus_find_rec(bnode, fd); 86 if (fd->record < 0) { 87 err = -ENOENT; 88 goto release; 89 } 90 if (!height) { 91 if (!fd->exact) 92 err = -ENOENT; 93 break; 94 } 95 96 parent = nidx; 97 hfsplus_bnode_readbytes(bnode, &data, fd->entryoffset, 4); 98 nidx = be32_to_cpu(data); 99 hfsplus_put_bnode(bnode); 100 } 101 fd->bnode = bnode; 102 return err; 103 104 invalid: 105 printk("HFS+-fs: inconsistency in B*Tree\n"); 106 err = -EIO; 107 release: 108 hfsplus_put_bnode(bnode); 109 return err; 110 } 111 112 int hfsplus_btree_find_entry(struct hfsplus_find_data *fd, 113 void *entry, int entry_len) 114 { 115 int res; 116 117 res = hfsplus_btree_find(fd); 118 if (res) 119 return res; 120 if (fd->entrylength > entry_len) 121 return -EINVAL; 122 hfsplus_bnode_readbytes(fd->bnode, entry, fd->entryoffset, fd->entrylength); 123 return 0; 124 } 125 126 int hfsplus_btree_move(struct hfsplus_find_data *fd, int cnt) 127 { 128 struct hfsplus_btree *tree; 129 hfsplus_bnode *bnode; 130 int idx, res = 0; 131 u16 off, len, keylen; 132 133 bnode = fd->bnode; 134 tree = bnode->tree; 135 136 if (cnt < -0xFFFF || cnt > 0xFFFF) 137 return -EINVAL; 138 139 if (cnt < 0) { 140 cnt = -cnt; 141 while (cnt > fd->record) { 142 cnt -= fd->record + 1; 143 fd->record = bnode->num_recs - 1; 144 idx = bnode->prev; 145 if (!idx) { 146 res = -ENOENT; 147 goto out; 148 } 149 hfsplus_put_bnode(bnode); 150 bnode = hfsplus_find_bnode(tree, idx); 151 if (!bnode) { 152 res = -EIO; 153 goto out; 154 } 155 } 156 fd->record -= cnt; 157 } else { 158 while (cnt >= bnode->num_recs - fd->record) { 159 cnt -= bnode->num_recs - fd->record; 160 fd->record = 0; 161 idx = bnode->next; 162 if (!idx) { 163 res = -ENOENT; 164 goto out; 165 } 166 hfsplus_put_bnode(bnode); 167 bnode = hfsplus_find_bnode(tree, idx); 168 if (!bnode) { 169 res = -EIO; 170 goto out; 171 } 172 } 173 fd->record += cnt; 174 } 175 176 len = hfsplus_brec_lenoff(bnode, fd->record, &off); 177 keylen = hfsplus_brec_keylen(bnode, fd->record); 178 fd->keyoffset = off; 179 fd->keylength = keylen; 180 fd->entryoffset = off + keylen; 181 fd->entrylength = len - keylen; 182 hfsplus_bnode_readbytes(bnode, fd->key, off, keylen); 183 out: 184 fd->bnode = bnode; 185 return res; 186 } 187 188 int hfsplus_find_init(hfsplus_btree *tree, struct hfsplus_find_data *fd) 189 { 190 fd->tree = tree; 191 fd->bnode = NULL; 192 fd->search_key = kmalloc(tree->max_key_len + 2, GFP_KERNEL); 193 if (!fd->search_key) 194 return -ENOMEM; 195 fd->key = kmalloc(tree->max_key_len + 2, GFP_KERNEL); 196 if (!fd->key) { 197 kfree(fd->search_key); 198 return -ENOMEM; 199 } 200 dprint(DBG_BNODE_REFS, "find_init: %d (%p)\n", tree->cnid, __builtin_return_address(0)); 201 down(&tree->tree_lock); 202 return 0; 203 } 204 205 void hfsplus_find_exit(struct hfsplus_find_data *fd) 206 { 207 hfsplus_put_bnode(fd->bnode); 208 kfree(fd->search_key); 209 kfree(fd->key); 210 dprint(DBG_BNODE_REFS, "find_exit: %d (%p)\n", fd->tree->cnid, __builtin_return_address(0)); 211 up(&fd->tree->tree_lock); 212 fd->tree = NULL; 213 }
Cache object: 3c52c67124cdc39be540dc3e8c257a2a
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]