Root/
1 | /* |
2 | * Copyright (C) 2011 Red Hat, Inc. |
3 | * |
4 | * This file is released under the GPL. |
5 | */ |
6 | |
7 | #ifndef DM_BTREE_INTERNAL_H |
8 | #define DM_BTREE_INTERNAL_H |
9 | |
10 | #include "dm-btree.h" |
11 | |
12 | /*----------------------------------------------------------------*/ |
13 | |
14 | /* |
15 | * We'll need 2 accessor functions for n->csum and n->blocknr |
16 | * to support dm-btree-spine.c in that case. |
17 | */ |
18 | |
19 | enum node_flags { |
20 | INTERNAL_NODE = 1, |
21 | LEAF_NODE = 1 << 1 |
22 | }; |
23 | |
24 | /* |
25 | * Every btree node begins with this structure. Make sure it's a multiple |
26 | * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned. |
27 | */ |
28 | struct node_header { |
29 | __le32 csum; |
30 | __le32 flags; |
31 | __le64 blocknr; /* Block this node is supposed to live in. */ |
32 | |
33 | __le32 nr_entries; |
34 | __le32 max_entries; |
35 | __le32 value_size; |
36 | __le32 padding; |
37 | } __packed; |
38 | |
39 | struct btree_node { |
40 | struct node_header header; |
41 | __le64 keys[0]; |
42 | } __packed; |
43 | |
44 | |
45 | void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, |
46 | struct dm_btree_value_type *vt); |
47 | |
48 | int new_block(struct dm_btree_info *info, struct dm_block **result); |
49 | int unlock_block(struct dm_btree_info *info, struct dm_block *b); |
50 | |
51 | /* |
52 | * Spines keep track of the rolling locks. There are 2 variants, read-only |
53 | * and one that uses shadowing. These are separate structs to allow the |
54 | * type checker to spot misuse, for example accidentally calling read_lock |
55 | * on a shadow spine. |
56 | */ |
57 | struct ro_spine { |
58 | struct dm_btree_info *info; |
59 | |
60 | int count; |
61 | struct dm_block *nodes[2]; |
62 | }; |
63 | |
64 | void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info); |
65 | int exit_ro_spine(struct ro_spine *s); |
66 | int ro_step(struct ro_spine *s, dm_block_t new_child); |
67 | void ro_pop(struct ro_spine *s); |
68 | struct btree_node *ro_node(struct ro_spine *s); |
69 | |
70 | struct shadow_spine { |
71 | struct dm_btree_info *info; |
72 | |
73 | int count; |
74 | struct dm_block *nodes[2]; |
75 | |
76 | dm_block_t root; |
77 | }; |
78 | |
79 | void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info); |
80 | int exit_shadow_spine(struct shadow_spine *s); |
81 | |
82 | int shadow_step(struct shadow_spine *s, dm_block_t b, |
83 | struct dm_btree_value_type *vt); |
84 | |
85 | /* |
86 | * The spine must have at least one entry before calling this. |
87 | */ |
88 | struct dm_block *shadow_current(struct shadow_spine *s); |
89 | |
90 | /* |
91 | * The spine must have at least two entries before calling this. |
92 | */ |
93 | struct dm_block *shadow_parent(struct shadow_spine *s); |
94 | |
95 | int shadow_has_parent(struct shadow_spine *s); |
96 | |
97 | int shadow_root(struct shadow_spine *s); |
98 | |
99 | /* |
100 | * Some inlines. |
101 | */ |
102 | static inline __le64 *key_ptr(struct btree_node *n, uint32_t index) |
103 | { |
104 | return n->keys + index; |
105 | } |
106 | |
107 | static inline void *value_base(struct btree_node *n) |
108 | { |
109 | return &n->keys[le32_to_cpu(n->header.max_entries)]; |
110 | } |
111 | |
112 | static inline void *value_ptr(struct btree_node *n, uint32_t index) |
113 | { |
114 | uint32_t value_size = le32_to_cpu(n->header.value_size); |
115 | return value_base(n) + (value_size * index); |
116 | } |
117 | |
118 | /* |
119 | * Assumes the values are suitably-aligned and converts to core format. |
120 | */ |
121 | static inline uint64_t value64(struct btree_node *n, uint32_t index) |
122 | { |
123 | __le64 *values_le = value_base(n); |
124 | |
125 | return le64_to_cpu(values_le[index]); |
126 | } |
127 | |
128 | /* |
129 | * Searching for a key within a single node. |
130 | */ |
131 | int lower_bound(struct btree_node *n, uint64_t key); |
132 | |
133 | extern struct dm_block_validator btree_node_validator; |
134 | |
135 | #endif /* DM_BTREE_INTERNAL_H */ |
136 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9