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 | * | |
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 */ |