Commit | Line | Data |
---|---|---|
17c76b01 KS |
1 | /* |
2 | * btree.h - NILFS B-tree. | |
3 | * | |
4 | * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation. | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or modify | |
7 | * it under the terms of the GNU General Public License as published by | |
8 | * the Free Software Foundation; either version 2 of the License, or | |
9 | * (at your option) any later version. | |
10 | * | |
11 | * This program is distributed in the hope that it will be useful, | |
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | * GNU General Public License for more details. | |
15 | * | |
4b420ab4 | 16 | * Written by Koji Sato. |
17c76b01 KS |
17 | */ |
18 | ||
19 | #ifndef _NILFS_BTREE_H | |
20 | #define _NILFS_BTREE_H | |
21 | ||
22 | #include <linux/types.h> | |
23 | #include <linux/buffer_head.h> | |
24 | #include <linux/list.h> | |
25 | #include <linux/nilfs2_fs.h> | |
26 | #include "btnode.h" | |
27 | #include "bmap.h" | |
28 | ||
41c88bd7 LH |
29 | /** |
30 | * struct nilfs_btree_path - A path on which B-tree operations are executed | |
31 | * @bp_bh: buffer head of node block | |
32 | * @bp_sib_bh: buffer head of sibling node block | |
33 | * @bp_index: index of child node | |
34 | * @bp_oldreq: ptr end request for old ptr | |
35 | * @bp_newreq: ptr alloc request for new ptr | |
36 | * @bp_op: rebalance operation | |
37 | */ | |
38 | struct nilfs_btree_path { | |
39 | struct buffer_head *bp_bh; | |
40 | struct buffer_head *bp_sib_bh; | |
41 | int bp_index; | |
42 | union nilfs_bmap_ptr_req bp_oldreq; | |
43 | union nilfs_bmap_ptr_req bp_newreq; | |
44 | struct nilfs_btnode_chkey_ctxt bp_ctxt; | |
e7c274f8 | 45 | void (*bp_op)(struct nilfs_bmap *, struct nilfs_btree_path *, |
41c88bd7 LH |
46 | int, __u64 *, __u64 *); |
47 | }; | |
17c76b01 KS |
48 | |
49 | #define NILFS_BTREE_ROOT_SIZE NILFS_BMAP_SIZE | |
50 | #define NILFS_BTREE_ROOT_NCHILDREN_MAX \ | |
51 | ((NILFS_BTREE_ROOT_SIZE - sizeof(struct nilfs_btree_node)) / \ | |
52 | (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */))) | |
53 | #define NILFS_BTREE_ROOT_NCHILDREN_MIN 0 | |
54 | #define NILFS_BTREE_NODE_EXTRA_PAD_SIZE (sizeof(__le64)) | |
55 | #define NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize) \ | |
56 | (((nodesize) - sizeof(struct nilfs_btree_node) - \ | |
57 | NILFS_BTREE_NODE_EXTRA_PAD_SIZE) / \ | |
58 | (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */))) | |
59 | #define NILFS_BTREE_NODE_NCHILDREN_MIN(nodesize) \ | |
60 | ((NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize) - 1) / 2 + 1) | |
61 | #define NILFS_BTREE_KEY_MIN ((__u64)0) | |
62 | #define NILFS_BTREE_KEY_MAX (~(__u64)0) | |
63 | ||
41c88bd7 | 64 | extern struct kmem_cache *nilfs_btree_path_cache; |
17c76b01 | 65 | |
3033342a | 66 | int nilfs_btree_init(struct nilfs_bmap *); |
17c76b01 | 67 | int nilfs_btree_convert_and_insert(struct nilfs_bmap *, __u64, __u64, |
3033342a | 68 | const __u64 *, const __u64 *, int); |
17c76b01 KS |
69 | void nilfs_btree_init_gc(struct nilfs_bmap *); |
70 | ||
1d5385b9 RK |
71 | int nilfs_btree_broken_node_block(struct buffer_head *bh); |
72 | ||
17c76b01 | 73 | #endif /* _NILFS_BTREE_H */ |