The transactional list provides a transaction-safe implementation of a double-linked list. Efficient insert and remove operations are supported anywhere within the list. More...
|
Files | |
| file | picotm-txlist-state.h |
| Provides non-transactional state and entries for transactional lists. | |
| file | picotm-txlist.h |
| Provides transactional lists. | |
Detailed Description
The struct txlist data structure represents a transactional double-linked list. To create a list, we first need list entries. These are represented by struct txlist_entry. We can add an instance of this data structure to any data value to turn it into a list entry. Here's an example for lists of values of type unsigned long.
This code initializes the list entry using txlist_entry_init(). The macro TXLIST_ENTRY_INITIALIZER initializes static or stack-allocated list entries. The example below illustrates this.
When both, macro and function initialization, is possible, the macro form is prefered. List entries are uninitialized with txlist_entry_uninit().
To store the list entries, we need non-transactional list state, which represents the shared state of a double-linked list. It's implemented by struct txlist_state. We can define and initialize a list state as illustrated in the example below.
This code uses the initializer function txlist_state_init(). For static or stack-allocated list states, there's the initializer macro TXLIST_STATE_INITIALIZER().
When both forms are possible, the initializer macro is the prefered form.
List-state clean up is performed by txlist_state_uninit(). The list state may not contain entries when the clean-up happens. This means that entries have to be cleaned up from within a transaction.
For many uses this requirement just imposes unnecessary overhead. A call to txlist_state_clear_and_uninit_entries() provies a non-transactional way of clearing the list from its entries. It erases each element from the list and calls a clean-up function on it. The example below shows the clean-up code for a list of struct ulong_item entries.
At this point we have a list state and list entries to add to the state. So far all code was non-transactional. Actual list access and manipulation is performed by transactional code.
To perform list operations within a transaction, we first need a list data structure for our transaction. It's represented by struct txlist. A call to txlist_of_state_tx() returns an instance.
Calling txlist_of_state_tx() multiple times for the same list state within the same transaction returns the same list. Lists are undefined after their transaction committed or aborted, or within other, concurrent transactions.
With the list, we can now append or prepend entries to the list state using txlist_push_back_tx() and txlist_push_front_tx(). The example below illustrates the use of txlist_push_back_tx().
After this transaction committed, the ulong data item item will be the back-end entry in list_state. If the transactions has to abort after the call to txlist_push_back_tx(), the transaction framework will automatically remove the appended entry during the rollback; thus restoring the original state.
To remove an entry from the list, we can call txlist_erase_tx(), as illustated in the example below.
As usual, all errors are detected and handled by the transaction framework. The benefits of transactional code show when we move entries between lists.
In this example, we remove an entry from a source list and append it to a destination list. The transaction framework automatically isolates these operations from concurrent transactions until the transaction commits. So concurrent transactions see the entry in either the source list or the destination list, but never in both. If the transaction has to roll back after the append operation, the transaction framework automatically removes the list entry from the destination list and returns it to its old position in the source list.
A call to txlist_size_tx() returns the number of list entries, a call to txlist_empty_tx() returns true if a list is empty. The former function might have linear complexity, the later function always has constant complexity. It's therefore better to use txlist_empty_tx() if it's only relevant whether there are entries.
If we known that their are entries in the list, calls to txlist_front_tx() and txlist_back_tx() return the front-end, resp. the back-end entry.
We can also iterate over the entries of a list. The first entry of the list is returned by txlist_begin_tx(). The terminator entry after the final entry is returned by txlist_end_tx(). The terminator entry is not a real entry and should not be dereferenced. Calls to txlist_entry_next_tx() and txlist_entry_prev_tx() return an entry's successor or predecessor. Here's and example that iterates over a list of values of type unsigned long and sums up the individual values.
If we have an entry in a list, we can insert another entry before the existing one with txlist_insert_tx(). In the example below, we insert before the terminator entry, which is equivalent to an append operation.
To append or prepend entries to a list, it's better use the appropriate push functions, though. The transaction framework might be able to optimize concurrency control for each. Also, inserting or removing from a list can make iteration loops invalid. It's therefore better to separate these operations cleanly.
Finally, to clear the whole list at once, there's txlist_clear_tx(). It's equivalent to a continuous erase operation, but prefered for its reduced overhead.
