203
Listing 11-6. Sorted array layout
41 template
42 struct entries_t {
43
Value entries[slots];
44
size_t size;
45 };
46
47 template
48 class array {
49 public:
50 void insert(pmem::obj::pool_base &pop, const Value &);
51 void insert_element(pmem::obj::pool_base &pop, const Value&);
52
53 entries_t v[2];
54 uint32_t current;
55 };
• Lines 41-45: We define the helper structure, which consists of an
array of indexes and a size.
• Line 53: We define two elements array of entries_t structures.
entries_t holds an array of elements (entries array) and the number
of elements in the node as the size variable.
• Line 54: This variable determines which entries_t structure from
line 53 is used. It can be only 0 or 1. Figure 11-2 shows the situation
where the current is equal to 0 and points to the first element of the v
array.
To understand why we need two versions of the entries_t structure and a current
field, Figure 11-3 shows how the insert operation works, and the corresponding
pseudocode appears in Listing 11-7.
Chapter 11 Designing Data struCtures for persistent MeMory