List of Listings

Chapter 1. Hello, world of concurrency in C++!

Listing 1.1. A simple Hello, Concurrent World program

Chapter 2. Managing threads

Listing 2.1. A function that returns while a thread still has access to local variables

Listing 2.2. Waiting for a thread to finish

Listing 2.3. Using RAII to wait for a thread to complete

Listing 2.4. Detaching a thread to handle other documents

Listing 2.5. Returning a std::thread from a function

Listing 2.6. scoped_thread and example usage

Listing 2.7. Spawn some threads and wait for them to finish

Listing 2.8. A naïve parallel version of std::accumulate

Chapter 3. Sharing data between threads

Listing 3.1. Protecting a list with a mutex

Listing 3.2. Accidentally passing out a reference to protected data

Listing 3.3. The interface to the std::stack container adapter

Listing 3.4. An outline class definition for a thread-safe stack

Listing 3.5. A fleshed-out class definition for a thread-safe stack

Listing 3.6. Using std::lock() and std::lock_guard in a swap operation

Listing 3.7. Using a lock hierarchy to prevent deadlock

Listing 3.8. A simple hierarchical mutex

Listing 3.9. Using std::lock() and std::unique_lock in a swap operation

Listing 3.10. Locking one mutex at a time in a comparison operator

Listing 3.11. Thread-safe lazy initialization using a mutex

Listing 3.12. Thread-safe lazy initialization of a class member using std::call_once

Listing 3.13. Protecting a data structure with a boost::shared_mutex

Chapter 4. Synchronizing concurrent operations

Listing 4.1. Waiting for data to process with a std::condition_variable

Listing 4.2. std::queue interface

Listing 4.3. The interface of your threadsafe_queue

Listing 4.4. Extracting push() and wait_and_pop() from listing 4.1

Listing 4.5. Full class definition for a thread-safe queue using condition variables

Listing 4.6. Using std::future to get the return value of an asynchronous task

Listing 4.7. Passing arguments to a function with std::async

Listing 4.8. Partial class definition for a specialization of std::packaged_task< >

Listing 4.9. Running code on a GUI thread using std::packaged_task

Listing 4.10. Handling multiple connections from a single thread using promises

Listing 4.11. Waiting for a condition variable with a timeout

Listing 4.12. A sequential implementation of Quicksort

Listing 4.13. Parallel Quicksort using futures

Listing 4.14. A sample implementation of spawn_task

Listing 4.15. A simple implementation of an ATM logic class

Listing 4.16. The getting_pin state function for the simple ATM implementation

Chapter 5. The C++ memory model and operations on atomic types

Listing 5.1. Implementation of a spinlock mutex using std::atomic_flag

Listing 5.2. Reading and writing variables from different threads

Listing 5.3. Order of evaluation of arguments to a function call is unspecified

Listing 5.4. Sequential consistency implies a total ordering

Listing 5.5. Relaxed operations have very few ordering requirements

Listing 5.6. Relaxed operations on multiple threads

Listing 5.7. Acquire-release doesn’t imply a total ordering

Listing 5.8. Acquire-release operations can impose ordering on relaxed operations

Listing 5.9. Transitive synchronization using acquire and release ordering

Listing 5.10. Using std::memory_order_consume to synchronize data

Listing 5.11. Reading values from a queue with atomic operations

Listing 5.12. Relaxed operations can be ordered with fences

Listing 5.13. Enforcing ordering on nonatomic operations

Chapter 6. Designing lock-based concurrent data structures

Listing 6.1. A class definition for a thread-safe stack

Listing 6.2. The full class definition for a thread-safe queue using condition variables

Listing 6.3. A thread-safe queue holding std::shared_ptr<> instances

Listing 6.4. A simple single-threaded queue implementation

Listing 6.5. A simple queue with a dummy node

Listing 6.6. A thread-safe queue with fine-grained locking

Listing 6.7. A thread-safe queue with locking and waiting: internals and interface

Listing 6.8. A thread-safe queue with locking and waiting: pushing new values

Listing 6.9. A thread-safe queue with locking and waiting: wait_and_pop()

Listing 6.10. A thread-safe queue with locking and waiting: try_pop() and empty()

Listing 6.11. A thread-safe lookup table

Listing 6.12. Obtaining contents of a threadsafe_lookup_table as a std::map<>

Listing 6.13. A thread-safe list with iteration support

Chapter 7. Designing lock-free concurrent data structures

Listing 7.1. Implementation of a spin-lock mutex using std::atomic_flag

Listing 7.2. Implementing push() without locks

Listing 7.3. A lock-free stack that leaks nodes

Listing 7.4. Reclaiming nodes when no threads are in pop()

Listing 7.5. The reference-counted reclamation machinery

Listing 7.6. An implementation of pop() using hazard pointers

Listing 7.7. A simple implementation of get_hazard_pointer_for_current_thread()

Listing 7.8. A simple implementation of the reclaim functions

Listing 7.9. A lock-free stack using a lock-free std::shared_ptr<> implementation

Listing 7.10. Pushing a node on a lock-free stack using split reference counts

Listing 7.11. Popping a node from a lock-free stack using split reference counts

Listing 7.12. A lock-free stack with reference counting and relaxed atomic operations

Listing 7.13. A single-producer, single-consumer lock-free queue

Listing 7.14. A (broken) first attempt at revising push()

Listing 7.15. Implementing push() for a lock-free queue with a reference-counted tail

Listing 7.16. Popping a node from a lock-free queue with a reference-counted tail

Listing 7.17. Releasing a node reference in a lock-free queue

Listing 7.18. Obtaining a new reference to a node in a lock-free queue

Listing 7.19. Freeing an external counter to a node in a lock-free queue

Listing 7.20. pop() modified to allow helping on the push() side

Listing 7.21. A sample push() with helping for a lock-free queue

Chapter 8. Designing concurrent code

Listing 8.1. Parallel Quicksort using a stack of pending chunks to sort

Listing 8.2. A naïve parallel version of std::accumulate (from listing 2.8)

Listing 8.3. A parallel version of std::accumulate using std::packaged_task

Listing 8.4. An exception-safe parallel version of std::accumulate

Listing 8.5. An exception-safe parallel version of std::accumulate using std::async

Listing 8.6. Separating GUI thread from task thread

Listing 8.7. A parallel version of std::for_each

Listing 8.8. A parallel version of std::for_each using std::async

Listing 8.9. An implementation of a parallel find algorithm

Listing 8.10. An implementation of a parallel find algorithm using std::async

Listing 8.11. Calculating partial sums in parallel by dividing the problem

Listing 8.12. A simple barrier class

Listing 8.13. A parallel implementation of partial_sum by pairwise updates

Chapter 9. Advanced thread management

Listing 9.1. Simple thread pool

Listing 9.2. A thread pool with waitable tasks

Listing 9.3. parallel_accumulate using a thread pool with waitable tasks

Listing 9.4. An implementation of run_pending_task()

Listing 9.5. A thread pool–based implementation of Quicksort

Listing 9.6. A thread pool with thread-local work queues

Listing 9.7. Lock-based queue for work stealing

Listing 9.8. A thread pool that uses work stealing

Listing 9.9. Basic implementation of interruptible_thread

Listing 9.10. A broken version of interruptible_wait for std::condition_variable

Listing 9.11. Using a timeout in interruptible_wait for std::condition_variable

Listing 9.12. interruptible_wait for std::condition_variable_any

Listing 9.13. Monitoring the filesystem in the background

Chapter 10. Testing and debugging multithreaded applications

Listing 10.1. An example test for concurrent push() and pop() calls on a queue

Appendix A. Brief reference for some C++11 language features

Listing A.1. A class with a move constructor

Listing A.2. A simple move-only type

Listing A.3. A class with a trivial default constructor

Listing A.4. A simple lambda with a deduced return type

Appendix C. A message-passing framework and complete ATM example

Listing C.1. A simple message queue

Listing C.2. The sender class

Listing C.3. The receiver class

Listing C.4. The dispatcher class

Listing C.5. The TemplateDispatcher class template

Listing C.6. ATM messages

Listing C.7. The ATM state machine

Listing C.8. The bank state machine

Listing C.9. The user-interface state machine

Listing C.10. The driving code