1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
// vim: ts=8 sw=2 smarttab
#pragma once
#include <ostream>
#include "node_extent_mutable.h"
#include "node_types.h"
#include "stages/stage_types.h"
namespace crimson::os::seastore::onode {
#ifdef UNIT_TESTS_BUILT
enum class InsertType { BEGIN, LAST, MID };
struct split_expectation_t {
match_stage_t split_stage;
match_stage_t insert_stage;
bool is_insert_left;
InsertType insert_type;
};
struct last_split_info_t {
search_position_t split_pos;
match_stage_t insert_stage;
bool is_insert_left;
InsertType insert_type;
bool match(const split_expectation_t& e) const {
match_stage_t split_stage;
if (split_pos.nxt.nxt.index == 0) {
if (split_pos.nxt.index == 0) {
split_stage = 2;
} else {
split_stage = 1;
}
} else {
split_stage = 0;
}
return split_stage == e.split_stage &&
insert_stage == e.insert_stage &&
is_insert_left == e.is_insert_left &&
insert_type == e.insert_type;
}
bool match_split_pos(const search_position_t& pos) const {
return split_pos == pos;
}
};
extern last_split_info_t last_split;
#endif
struct key_hobj_t;
struct key_view_t;
class NodeExtentMutable;
/**
* NodeImpl
*
* Hides type specific node layout implementations for Node.
*/
class NodeImpl {
public:
using alloc_ertr = crimson::errorator<
crimson::ct_error::input_output_error,
crimson::ct_error::invarg,
crimson::ct_error::enoent,
crimson::ct_error::erange>;
virtual ~NodeImpl() = default;
virtual field_type_t field_type() const = 0;
virtual laddr_t laddr() const = 0;
virtual void prepare_mutate(context_t) = 0;
virtual bool is_level_tail() const = 0;
virtual bool is_empty() const = 0;
virtual level_t level() const = 0;
virtual node_offset_t free_size() const = 0;
virtual key_view_t get_key_view(const search_position_t&) const = 0;
virtual key_view_t get_largest_key_view() const = 0;
virtual void next_position(search_position_t&) const = 0;
virtual node_stats_t get_stats() const = 0;
virtual std::ostream& dump(std::ostream&) const = 0;
virtual std::ostream& dump_brief(std::ostream&) const = 0;
virtual void validate_layout() const = 0;
virtual void test_copy_to(NodeExtentMutable&) const = 0;
virtual void test_set_tail(NodeExtentMutable&) = 0;
protected:
NodeImpl() = default;
};
/**
* InternalNodeImpl
*
* Hides type specific node layout implementations for InternalNode.
*/
class InternalNodeImpl : public NodeImpl {
public:
struct internal_marker_t {};
virtual ~InternalNodeImpl() = default;
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual const laddr_packed_t* get_p_value(
const search_position_t&,
key_view_t* = nullptr, internal_marker_t = {}) const {
ceph_abort("impossible path");
}
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual lookup_result_t<node_type_t::INTERNAL> lower_bound(
const key_hobj_t&, MatchHistory&,
key_view_t* = nullptr, internal_marker_t = {}) const {
ceph_abort("impossible path");
}
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual const laddr_packed_t* insert(
const key_view_t&, const laddr_packed_t&, search_position_t&, match_stage_t&, node_offset_t&) {
ceph_abort("impossible path");
}
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual std::tuple<search_position_t, bool, const laddr_packed_t*> split_insert(
NodeExtentMutable&, NodeImpl&, const key_view_t&, const laddr_packed_t&,
search_position_t&, match_stage_t&, node_offset_t&) {
ceph_abort("impossible path");
}
virtual void replace_child_addr(const search_position_t&, laddr_t dst, laddr_t src) = 0;
virtual std::tuple<match_stage_t, node_offset_t> evaluate_insert(
const key_view_t&, const laddr_t&, search_position_t&) const = 0;
struct fresh_impl_t {
InternalNodeImplURef impl;
NodeExtentMutable mut;
std::pair<NodeImplURef, NodeExtentMutable> make_pair() {
return {std::move(impl), mut};
}
};
static alloc_ertr::future<fresh_impl_t> allocate(context_t, field_type_t, bool, level_t);
static InternalNodeImplURef load(NodeExtentRef, field_type_t, bool);
protected:
InternalNodeImpl() = default;
};
/**
* LeafNodeImpl
*
* Hides type specific node layout implementations for LeafNode.
*/
class LeafNodeImpl : public NodeImpl {
public:
struct leaf_marker_t {};
virtual ~LeafNodeImpl() = default;
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual const onode_t* get_p_value(
const search_position_t&,
key_view_t* = nullptr, leaf_marker_t={}) const {
ceph_abort("impossible path");
}
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual lookup_result_t<node_type_t::LEAF> lower_bound(
const key_hobj_t&, MatchHistory&,
key_view_t* = nullptr, leaf_marker_t = {}) const {
ceph_abort("impossible path");
}
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual const onode_t* insert(
const key_hobj_t&, const onode_t&, search_position_t&, match_stage_t&, node_offset_t&) {
ceph_abort("impossible path");
}
#pragma GCC diagnostic ignored "-Woverloaded-virtual"
virtual std::tuple<search_position_t, bool, const onode_t*> split_insert(
NodeExtentMutable&, NodeImpl&, const key_hobj_t&, const onode_t&,
search_position_t&, match_stage_t&, node_offset_t&) {
ceph_abort("impossible path");
}
virtual void get_largest_slot(
search_position_t&, key_view_t&, const onode_t**) const = 0;
virtual std::tuple<match_stage_t, node_offset_t> evaluate_insert(
const key_hobj_t&, const onode_t&,
const MatchHistory&, match_stat_t, search_position_t&) const = 0;
struct fresh_impl_t {
LeafNodeImplURef impl;
NodeExtentMutable mut;
std::pair<NodeImplURef, NodeExtentMutable> make_pair() {
return {std::move(impl), mut};
}
};
static alloc_ertr::future<fresh_impl_t> allocate(context_t, field_type_t, bool);
static LeafNodeImplURef load(NodeExtentRef, field_type_t, bool);
protected:
LeafNodeImpl() = default;
};
}
|
