204
Listing 11-7. Pseudocode of a sorted tree insert operation
57 template
58 void array::insert_element(pmem::obj::pool_base &pop,
59
const Value &entry) {
60
auto &working_copy = v[1 - current];
61
auto &consistent_copy = v[current];
62
63
auto consistent_insert_position = std::lower_bound(
64
std::begin(consistent_copy.entries),
65
std::begin(consistent_copy.entries) +
66
consistent_copy.size, entry);
67
auto working_insert_position =
68
std::begin(working_copy.entries) +
std::distance(std::begin(consistent_copy.entries),
69
consistent_insert_position);
70
71
std::copy(std::begin(consistent_copy.entries),
72
consistent_insert_position,
73
std::begin(working_copy.entries));
74
75
*working_insert_position = entry;
76
77
std::copy(consistent_insert_position,
78
std::begin(consistent_copy.entries) +
consistent_copy.size,
79
working_insert_position + 1);
Figure 11-3. Overview of a sorted tree insert operation
Chapter 11 Designing Data struCtures for persistent MeMory