202
• Lines 126-129: When there is no element with the specified key in the
hash table, we insert both a value and a key to their respective vectors
in persistent memory in a transaction.
• Line 131: After inserting data to persistent memory, we update the
state of the volatile data structure. Note that this operation does not
have to be atomic. If a program crashes, the bucket array will be
rebuilt on startup.
• Lines 149-150: We define the layout of the persistent data. Key and
values are stored in separate pmem::obj::vector.
• Lines 153-156: We define a function that returns the runtime object of
this hash table.
Sorted Array with Versioning
This section presents an overview of an algorithm for inserting elements into a sorted
array and preserving the order of elements. This algorithm guarantees data consistency
using the versioning technique.
First, we describe the layout of our sorted array. Figure 11-2 and Listing 11-6 show
that there are two arrays of elements and two size fields. Additionally, one current field
stores information about which array and size variable is currently used.
Figure 11-2. Sorted array layout
Chapter 11 Designing Data struCtures for persistent MeMory
• Lines 126-129: When there is no element with the specified key in the
hash table, we insert both a value and a key to their respective vectors
in persistent memory in a transaction.
• Line 131: After inserting data to persistent memory, we update the
state of the volatile data structure. Note that this operation does not
have to be atomic. If a program crashes, the bucket array will be
rebuilt on startup.
• Lines 149-150: We define the layout of the persistent data. Key and
values are stored in separate pmem::obj::vector.
• Lines 153-156: We define a function that returns the runtime object of
this hash table.
Sorted Array with Versioning
This section presents an overview of an algorithm for inserting elements into a sorted
array and preserving the order of elements. This algorithm guarantees data consistency
using the versioning technique.
First, we describe the layout of our sorted array. Figure 11-2 and Listing 11-6 show
that there are two arrays of elements and two size fields. Additionally, one current field
stores information about which array and size variable is currently used.
Figure 11-2. Sorted array layout
Chapter 11 Designing Data struCtures for persistent MeMory