C++ bindings for libpmemobj (part 3) - persistent queue example
The best way to learn to code is usually by implementing an example. We are going
to be creating a linked-list based queue data structure using the the
pmem::obj::persistent_ptr classes and libpmemobj C API. But
first, a little bit of CS 101 :)
Queue is a collection of elements with two important operations:
push- adds element to the
tailof the structure
pop- removes element from the
headof the structure
This makes the queue a First-In-First-Out (FIFO) data structure.
The common implementations use either arrays or singly linked-lists to store elements. As previously stated, we are going to use the latter.
Push operation consists of several steps. First, a new object is created that
contains the data (
value) and a pointer to the
next entry. Initially the
memory content of those variables is unknown, so we need to assign user input
NULL to the
After we’ve done that, let’s link the newly created object to the structure
by assigning it to the
next field of the current tail entry. Obviously, if the
NULL there’s nothing to do :)
As the last step, we have to update the
tail variable of the queue structure to
point to our new object. If this is the first entry and both
we have to remember to update the
head as well.
The first step of the pop operation is to update the
head variable of the queue
structure to point to the
head->next (the second entry). The object which is
being removed is currently not linked to anything.
Next, the removed object has to be freed. And if there are no more entries in
the queue (the
head variable is
tail variable has to be set to
What about persistence?
When implementing algorithms that operate on persistent memory, we have to carefully consider what happens to the data structure if the application is interrupted (for example, by a power failure) at any moment during its operation.
The pmemobj library takes care of those issues and it’s enough to simply wrap your code in a transaction block to make it failsafe atomic (i.e. done completely or not at all).
I intentionally described the queue operations in indivisible steps, so that it’s clear that when the algorithm is interrupted for some reason, we can end up with either persistent memory leak or corrupted data structure.
As the operations were already described, and the actual implementation, in alignment to the premise of C++ bindings, is identical to the volatile one, I’ll talk only about the data structure.
First let’s define our list entry structure. As we just learned, it has to
next pointer and a value.
Our queue structure, which will also be our root object, consists of two fields:
pmem_queue::pop() functions look exactly like a
volatile implementation, but with a transaction block and
pmemobj_free() instead of
Complete implementation is available here.