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
|
This page was automatically generated by the
LXR engine.
|