Merge branch 'for-linus' of git://git.kernel.dk/linux-2.6-block
[linux-2.6] / fs / hfsplus / bfind.c
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 }