aboutsummaryrefslogtreecommitdiffstats
path: root/fs/hfs/bfind.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/hfs/bfind.c')
-rw-r--r--fs/hfs/bfind.c210
1 files changed, 210 insertions, 0 deletions
diff --git a/fs/hfs/bfind.c b/fs/hfs/bfind.c
new file mode 100644
index 000000000000..89450ae32228
--- /dev/null
+++ b/fs/hfs/bfind.c
@@ -0,0 +1,210 @@
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
14int 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
30void 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...)*/
40int __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 }
73done:
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 */
84int 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
129invalid:
130 printk("HFS: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
131 height, bnode->height, bnode->type, nidx, parent);
132 res = -EIO;
133release:
134 hfs_bnode_put(bnode);
135 return res;
136}
137
138int 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
151int 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);
207out:
208 fd->bnode = bnode;
209 return res;
210}
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-27 10:23:25 -0500