5 * Brad Boyer (flar@allandria.com)
6 * (C) 2003 Ardis Technologies <roman@ardistech.com>
8 * Search routines for btrees
11 #include <linux/slab.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 mutex_lock(&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 mutex_unlock(&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
);
59 hfs_bnode_read(bnode
, fd
->key
, off
, keylen
);
60 cmpval
= bnode
->tree
->keycmp(fd
->key
, fd
->search_key
);
71 if (rec
!= e
&& e
>= 0) {
72 len
= hfs_brec_lenoff(bnode
, e
, &off
);
73 keylen
= hfs_brec_keylen(bnode
, e
);
78 hfs_bnode_read(bnode
, fd
->key
, off
, keylen
);
83 fd
->keylength
= keylen
;
84 fd
->entryoffset
= off
+ keylen
;
85 fd
->entrylength
= len
- keylen
;
90 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
91 /* Return allocated copy of node found, set recnum to best record */
92 int hfs_brec_find(struct hfs_find_data
*fd
)
94 struct hfs_btree
*tree
;
95 struct hfs_bnode
*bnode
;
102 hfs_bnode_put(fd
->bnode
);
107 height
= tree
->depth
;
111 bnode
= hfs_bnode_find(tree
, nidx
);
113 res
= PTR_ERR(bnode
);
117 if (bnode
->height
!= height
)
119 if (bnode
->type
!= (--height
? HFS_NODE_INDEX
: HFS_NODE_LEAF
))
121 bnode
->parent
= parent
;
123 res
= __hfs_brec_find(bnode
, fd
);
130 hfs_bnode_read(bnode
, &data
, fd
->entryoffset
, 4);
131 nidx
= be32_to_cpu(data
);
132 hfs_bnode_put(bnode
);
138 printk(KERN_ERR
"hfs: inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
139 height
, bnode
->height
, bnode
->type
, nidx
, parent
);
142 hfs_bnode_put(bnode
);
146 int hfs_brec_read(struct hfs_find_data
*fd
, void *rec
, int rec_len
)
150 res
= hfs_brec_find(fd
);
153 if (fd
->entrylength
> rec_len
)
155 hfs_bnode_read(fd
->bnode
, rec
, fd
->entryoffset
, fd
->entrylength
);
159 int hfs_brec_goto(struct hfs_find_data
*fd
, int cnt
)
161 struct hfs_btree
*tree
;
162 struct hfs_bnode
*bnode
;
164 u16 off
, len
, keylen
;
171 while (cnt
> fd
->record
) {
172 cnt
-= fd
->record
+ 1;
173 fd
->record
= bnode
->num_recs
- 1;
179 hfs_bnode_put(bnode
);
180 bnode
= hfs_bnode_find(tree
, idx
);
182 res
= PTR_ERR(bnode
);
189 while (cnt
>= bnode
->num_recs
- fd
->record
) {
190 cnt
-= bnode
->num_recs
- fd
->record
;
197 hfs_bnode_put(bnode
);
198 bnode
= hfs_bnode_find(tree
, idx
);
200 res
= PTR_ERR(bnode
);
208 len
= hfs_brec_lenoff(bnode
, fd
->record
, &off
);
209 keylen
= hfs_brec_keylen(bnode
, fd
->record
);
215 fd
->keylength
= keylen
;
216 fd
->entryoffset
= off
+ keylen
;
217 fd
->entrylength
= len
- keylen
;
218 hfs_bnode_read(bnode
, fd
->key
, off
, keylen
);
This page took 0.034627 seconds and 5 git commands to generate.