2 * linux/fs/hfsplus/bfind.c
5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Search routines for btrees
11 #include <linux/slab.h>
12 #include "hfsplus_fs.h"
14 int hfs_find_init(struct hfs_btree
*tree
, struct hfs_find_data
*fd
)
20 ptr
= kmalloc(tree
->max_key_len
* 2 + 4, GFP_KERNEL
);
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
);
30 void hfs_find_exit(struct hfs_find_data
*fd
)
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
);
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
)
49 e
= bnode
->num_recs
- 1;
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
);
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
);
75 fd
->keylength
= keylen
;
76 fd
->entryoffset
= off
+ keylen
;
77 fd
->entrylength
= len
- keylen
;
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
)
85 struct hfs_btree
*tree
;
86 struct hfs_bnode
*bnode
;
93 hfs_bnode_put(fd
->bnode
);
102 bnode
= hfs_bnode_find(tree
, nidx
);
104 res
= PTR_ERR(bnode
);
108 if (bnode
->height
!= height
)
110 if (bnode
->type
!= (--height
? HFS_NODE_INDEX
: HFS_NODE_LEAF
))
112 bnode
->parent
= parent
;
114 res
= __hfs_brec_find(bnode
, fd
);
121 hfs_bnode_read(bnode
, &data
, fd
->entryoffset
, 4);
122 nidx
= be32_to_cpu(data
);
123 hfs_bnode_put(bnode
);
129 printk(KERN_ERR
"hfs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
130 height
, bnode
->height
, bnode
->type
, nidx
, parent
);
133 hfs_bnode_put(bnode
);
137 int hfs_brec_read(struct hfs_find_data
*fd
, void *rec
, int rec_len
)
141 res
= hfs_brec_find(fd
);
144 if (fd
->entrylength
> rec_len
)
146 hfs_bnode_read(fd
->bnode
, rec
, fd
->entryoffset
, fd
->entrylength
);
150 int hfs_brec_goto(struct hfs_find_data
*fd
, int cnt
)
152 struct hfs_btree
*tree
;
153 struct hfs_bnode
*bnode
;
155 u16 off
, len
, keylen
;
162 while (cnt
> fd
->record
) {
163 cnt
-= fd
->record
+ 1;
164 fd
->record
= bnode
->num_recs
- 1;
170 hfs_bnode_put(bnode
);
171 bnode
= hfs_bnode_find(tree
, idx
);
173 res
= PTR_ERR(bnode
);
180 while (cnt
>= bnode
->num_recs
- fd
->record
) {
181 cnt
-= bnode
->num_recs
- fd
->record
;
188 hfs_bnode_put(bnode
);
189 bnode
= hfs_bnode_find(tree
, idx
);
191 res
= PTR_ERR(bnode
);
199 len
= hfs_brec_lenoff(bnode
, fd
->record
, &off
);
200 keylen
= hfs_brec_keylen(bnode
, fd
->record
);
202 fd
->keylength
= keylen
;
203 fd
->entryoffset
= off
+ keylen
;
204 fd
->entrylength
= len
- keylen
;
205 hfs_bnode_read(bnode
, fd
->key
, off
, keylen
);
This page took 0.034023 seconds and 5 git commands to generate.