1 files changed, 398 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/libs/atomic/doc/examples.qbk b/3rdParty/Boost/src/libs/atomic/doc/examples.qbk
new file mode 100644
index 0000000..e34c402
--- /dev/null
+++ b/3rdParty/Boost/src/libs/atomic/doc/examples.qbk
@@ -0,0 +1,398 @@
+[/
+ / Copyright (c) 2009 Helge Bahmann
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section:example_reference_counters Reference counting]
+
+The purpose of a ['reference counter] is to count the number
+of pointers to an object. The object can be destroyed as
+soon as the reference counter reaches zero.
+
+[section Implementation]
+
+[c++]
+
+  #include <boost/intrusive_ptr.hpp>
+  #include <boost/atomic.hpp>
+
+  class X {
+  public:
+    typedef boost::intrusive_ptr<X> pointer;
+    X() : refcount_(0) {}
+
+  private:
+    mutable boost::atomic<int> refcount_;
+    friend void intrusive_ptr_add_ref(const X * x)
+    {
+      x->refcount_.fetch_add(1, boost::memory_order_relaxed);
+    }
+    friend void intrusive_ptr_release(const X * x)
+    {
+      if (x->refcount_.fetch_sub(1, boost::memory_order_release) == 1) {
+        boost::atomic_thread_fence(boost::memory_order_acquire);
+        delete x;
+      }
+    }
+  };
+
+[endsect]
+
+[section Usage]
+
+[c++]
+
+  X::pointer x = new X;
+
+[endsect]
+
+[section Discussion]
+
+Increasing the reference counter can always be done with
+[^memory_order_relaxed]: New references to an object can only
+be formed from an existing reference, and passing an existing
+reference from one thread to another must already provide any
+required synchronization.
+
+It is important to enforce any possible access to the object in
+one thread (through an existing reference) to ['happen before]
+deleting the object in a different thread. This is achieved
+by a "release" operation after dropping a reference (any
+access to the object through this reference must obviously
+happened before), and an "acquire" operation before
+deleting the object.
+
+It would be possible to use [^memory_order_acq_rel] for the
+[^fetch_sub] operation, but this results in unneeded "acquire"
+operations when the reference counter does not yet reach zero
+and may impose a performance penalty.
+
+[endsect]
+
+[endsect]
+
+[section:example_spinlock Spinlock]
+
+The purpose of a ['spin lock] is to prevent multiple threads
+from concurrently accessing a shared data structure. In contrast
+to a mutex, threads will busy-wait and waste CPU cycles instead
+of yielding the CPU to another thread. ['Do not use spinlocks
+unless you are certain that you understand the consequences.]
+
+[section Implementation]
+
+[c++]
+
+  #include <boost/atomic.hpp>
+
+  class spinlock {
+  private:
+    typedef enum {Locked, Unlocked} LockState;
+    boost::atomic<LockState> state_;
+
+  public:
+    spinlock() : state_(Unlocked) {}
+
+    void lock()
+    {
+      while (state_.exchange(Locked, boost::memory_order_acquire) == Locked) {
+        /* busy-wait */
+      }
+    }
+    void unlock()
+    {
+      state_.store(Unlocked, boost::memory_order_release);
+    }
+  };
+
+[endsect]
+
+[section Usage]
+
+[c++]
+
+  spinlock s;
+
+  s.lock();
+  // access data structure here
+  s.unlock();
+
+[endsect]
+
+[section Discussion]
+
+The purpose of the spinlock is to make sure that one access
+to the shared data structure always strictly "happens before"
+another. The usage of acquire/release in lock/unlock is required
+and sufficient to guarantee this ordering.
+
+It would be correct to write the "lock" operation in the following
+way:
+
+[c++]
+
+  lock()
+  {
+    while (state_.exchange(Locked, boost::memory_order_relaxed) == Locked) {
+      /* busy-wait */
+    }
+    atomic_thread_fence(boost::memory_order_acquire);
+  }
+
+This "optimization" is however a) useless and b) may in fact hurt:
+a) Since the thread will be busily spinning on a blocked spinlock,
+it does not matter if it will waste the CPU cycles with just
+"exchange" operations or with both useless "exchange" and "acquire"
+operations. b) A tight "exchange" loop without any
+memory-synchronizing instruction introduced through an "acquire"
+operation will on some systems monopolize the memory subsystem
+and degrade the performance of other system components.
+
+[endsect]
+
+[endsect]
+
+[section:singleton Singleton with double-checked locking pattern]
+
+The purpose of the ['Singleton with double-checked locking pattern] is to ensure
+that at most one instance of a particular object is created.
+If one instance has been created already, access to the existing
+object should be as light-weight as possible.
+
+[section Implementation]
+
+[c++]
+
+  #include <boost/atomic.hpp>
+  #include <boost/thread/mutex.hpp>
+
+  class X {
+  public:
+    static X * instance()
+    {
+      X * tmp = instance_.load(boost::memory_order_consume);
+      if (!tmp) {
+        boost::mutex::scoped_lock guard(instantiation_mutex);
+        tmp = instance_.load(boost::memory_order_consume);
+        if (!tmp) {
+          tmp = new X;
+          instance_.store(tmp, boost::memory_order_release);
+        }
+      }
+      return tmp;
+    }
+  private:
+    static boost::atomic<X *> instance_;
+    static boost::mutex instantiation_mutex;
+  };
+
+  boost::atomic<X *> X::instance_(0);
+
+[endsect]
+
+[section Usage]
+
+[c++]
+
+  X * x = X::instance();
+  // dereference x
+
+[endsect]
+
+[section Discussion]
+
+The mutex makes sure that only one instance of the object is
+ever created. The [^instance] method must make sure that any
+dereference of the object strictly "happens after" creating
+the instance in another thread. The use of [^memory_order_release]
+after creating and initializing the object and [^memory_order_consume]
+before dereferencing the object provides this guarantee.
+
+It would be permissible to use [^memory_order_acquire] instead of
+[^memory_order_consume], but this provides a stronger guarantee
+than is required since only operations depending on the value of
+the pointer need to be ordered.
+
+[endsect]
+
+[endsect]
+
+[section:example_ringbuffer Wait-free ring buffer]
+
+A ['wait-free ring buffer] provides a mechanism for relaying objects
+from one single "producer" thread to one single "consumer" thread without
+any locks. The operations on this data structure are "wait-free" which
+means that each operation finishes within a constant number of steps.
+This makes this data structure suitable for use in hard real-time systems
+or for communication with interrupt/signal handlers.
+
+[section Implementation]
+
+[c++]
+
+  #include <boost/atomic.hpp>
+
+  template<typename T, size_t Size>
+  class ringbuffer {
+  public:
+    ringbuffer() : head_(0), tail_(0) {}
+
+    bool push(const T & value)
+    {
+      size_t head = head_.load(boost::memory_order_relaxed);
+      size_t next_head = next(head);
+      if (next_head == tail_.load(boost::memory_order_acquire))
+        return false;
+      ring_[head] = value;
+      head_.store(next_head, boost::memory_order_release);
+      return true;
+    }
+    bool pop(T & value)
+    {
+      size_t tail = tail_.load(boost::memory_order_relaxed);
+      if (tail == head_.load(boost::memory_order_acquire))
+        return false;
+      value = ring_[tail];
+      tail_.store(next(tail), boost::memory_order_release);
+      return true;
+    }
+  private:
+    size_t next(size_t current)
+    {
+      return (current + 1) % Size;
+    }
+    T ring_[Size];
+    boost::atomic<size_t> head_, tail_;
+  };
+
+[endsect]
+
+[section Usage]
+
+[c++]
+
+  ringbuffer<int, 32> r;
+
+  // try to insert an element
+  if (r.push(42)) { /* succeeded */ }
+  else { /* buffer full */ }
+
+  // try to retrieve an element
+  int value;
+  if (r.pop(value)) { /* succeeded */ }
+  else { /* buffer empty */ }
+
+[endsect]
+
+[section Discussion]
+
+The implementation makes sure that the ring indices do
+not "lap-around" each other to ensure that no elements
+are either lost or read twice.
+
+Furthermore it must guarantee that read-access to a
+particular object in [^pop] "happens after" it has been
+written in [^push]. This is achieved by writing [^head_ ]
+with "release" and reading it with "acquire". Conversely
+the implementation also ensures that read access to
+a particular ring element "happens before" before
+rewriting this element with a new value by accessing [^tail_]
+with appropriate ordering constraints.
+
+[endsect]
+
+[endsect]
+
+[section:mp_queue Wait-free multi-producer queue]
+
+The purpose of the ['wait-free multi-producer queue] is to allow
+an arbitrary number of producers to enqueue objects which are
+retrieved and processed in FIFO order by a single consumer.
+
+[section Implementation]
+
+[c++]
+
+  template<typename T>
+  class waitfree_queue {
+  public:
+    struct node {
+      T data;
+      node * next;
+    };
+    void push(const T &data)
+    {
+      node * n = new node;
+      n->data = data;
+      node * stale_head = head_.load(boost::memory_order_relaxed);
+      do {
+        n->next = stale_head;
+      } while (!head_.compare_exchange_weak(stale_head, n, boost::memory_order_release));
+    }
+
+    node * pop_all(void)
+    {
+      T * last = pop_all_reverse(), * first = 0;
+      while(last) {
+        T * tmp = last;
+        last = last->next;
+        tmp->next = first;
+        first = tmp;
+      }
+      return first;
+    }
+
+    waitfree_queue() : head_(0) {}
+
+    // alternative interface if ordering is of no importance
+    node * pop_all_reverse(void)
+    {
+      return head_.exchange(0, boost::memory_order_consume);
+    }
+  private:
+    boost::atomic<node *> head_;
+  };
+
+[endsect]
+
+[section Usage]
+
+[c++]
+
+  waitfree_queue<int> q;
+
+  // insert elements
+  q.push(42);
+  q.push(2);
+
+  // pop elements
+  waitfree_queue<int>::node * x = q.pop_all()
+  while(x) {
+    X * tmp = x;
+    x = x->next;
+    // process tmp->data, probably delete it afterwards
+    delete tmp;
+  }
+
+[endsect]
+
+[section Discussion]
+
+The implementation guarantees that all objects enqueued are
+processed in the order they were enqueued by building a singly-linked
+list of object in reverse processing order. The queue is atomically
+emptied by the consumer and brought into correct order.
+
+It must be guaranteed that any access to an object to be enqueued
+by the producer "happens before" any access by the consumer. This
+is assured by inserting objects into the list with ['release] and
+dequeuing them with ['consume] memory order. It is not
+necessary to use ['acquire] memory order in [^waitfree_queue::pop_all]
+because all operations involved depend on the value of
+the atomic pointer through dereference
+
+[endsect]
+
+[endsect]