Merge branch 'for-2.6.30' into for-2.6.31
[linux-2.6] / fs / nilfs2 / btree.h
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  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
19  *
20  * Written by Koji Sato <koji@osrg.net>.
21  */
22
23 #ifndef _NILFS_BTREE_H
24 #define _NILFS_BTREE_H
25
26 #include <linux/types.h>
27 #include <linux/buffer_head.h>
28 #include <linux/list.h>
29 #include <linux/nilfs2_fs.h>
30 #include "btnode.h"
31 #include "bmap.h"
32
33 struct nilfs_btree;
34 struct nilfs_btree_path;
35
36 /**
37  * struct nilfs_btree_operations - B-tree operation table
38  */
39 struct nilfs_btree_operations {
40         __u64 (*btop_find_target)(const struct nilfs_btree *,
41                                   const struct nilfs_btree_path *, __u64);
42         void (*btop_set_target)(struct nilfs_btree *, __u64, __u64);
43
44         struct the_nilfs *(*btop_get_nilfs)(struct nilfs_btree *);
45
46         int (*btop_propagate)(struct nilfs_btree *,
47                               struct nilfs_btree_path *,
48                               int,
49                               struct buffer_head *);
50         int (*btop_assign)(struct nilfs_btree *,
51                            struct nilfs_btree_path *,
52                            int,
53                            struct buffer_head **,
54                            sector_t,
55                            union nilfs_binfo *);
56 };
57
58 /**
59  * struct nilfs_btree_node - B-tree node
60  * @bn_flags: flags
61  * @bn_level: level
62  * @bn_nchildren: number of children
63  * @bn_pad: padding
64  */
65 struct nilfs_btree_node {
66         __u8 bn_flags;
67         __u8 bn_level;
68         __le16 bn_nchildren;
69         __le32 bn_pad;
70 };
71
72 /* flags */
73 #define NILFS_BTREE_NODE_ROOT   0x01
74
75 /* level */
76 #define NILFS_BTREE_LEVEL_DATA          0
77 #define NILFS_BTREE_LEVEL_NODE_MIN      (NILFS_BTREE_LEVEL_DATA + 1)
78 #define NILFS_BTREE_LEVEL_MAX           14
79
80 /**
81  * struct nilfs_btree - B-tree structure
82  * @bt_bmap: bmap base structure
83  * @bt_ops: B-tree operation table
84  */
85 struct nilfs_btree {
86         struct nilfs_bmap bt_bmap;
87
88         /* B-tree-specific members */
89         const struct nilfs_btree_operations *bt_ops;
90 };
91
92
93 #define NILFS_BTREE_ROOT_SIZE           NILFS_BMAP_SIZE
94 #define NILFS_BTREE_ROOT_NCHILDREN_MAX                                  \
95         ((NILFS_BTREE_ROOT_SIZE - sizeof(struct nilfs_btree_node)) /    \
96          (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */)))
97 #define NILFS_BTREE_ROOT_NCHILDREN_MIN  0
98 #define NILFS_BTREE_NODE_EXTRA_PAD_SIZE (sizeof(__le64))
99 #define NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize)                        \
100         (((nodesize) - sizeof(struct nilfs_btree_node) -                \
101                 NILFS_BTREE_NODE_EXTRA_PAD_SIZE) /                      \
102          (sizeof(__le64 /* dkey */) + sizeof(__le64 /* dptr */)))
103 #define NILFS_BTREE_NODE_NCHILDREN_MIN(nodesize)                        \
104         ((NILFS_BTREE_NODE_NCHILDREN_MAX(nodesize) - 1) / 2 + 1)
105 #define NILFS_BTREE_KEY_MIN     ((__u64)0)
106 #define NILFS_BTREE_KEY_MAX     (~(__u64)0)
107
108
109 int nilfs_btree_path_cache_init(void);
110 void nilfs_btree_path_cache_destroy(void);
111 int nilfs_btree_init(struct nilfs_bmap *, __u64, __u64);
112 int nilfs_btree_convert_and_insert(struct nilfs_bmap *, __u64, __u64,
113                                    const __u64 *, const __u64 *,
114                                    int, __u64, __u64);
115 void nilfs_btree_init_gc(struct nilfs_bmap *);
116
117 #endif  /* _NILFS_BTREE_H */