code:
#ifndef __SKIP_LIST_HPP__
#define __SKIP_LIST_HPP__   1

#include "xrcu.hpp"
#include "xatomic.hpp"
#include "optional.hpp"
#include <cstddef>
#include <atomic>
#include <functional>
#include <initializer_list>

namespace std
{
  struct forward_iterator_tag;
}

namespace xrcu
{

namespace detail
{

void* sl_alloc_node (unsigned int lvl, size_t size, uintptr_t **outpp);
void sl_dealloc_node (void *base);

template <class T>
struct sl_node : public finalizable
{
  unsigned int nlvl;
  uintptr_t *next;
  optional<T> key;

  sl_node (unsigned int lvl, uintptr_t *np) : nlvl (lvl), next (np)
    {
    }

  static sl_node<T>* copy (unsigned int lvl, const T& k)
    {
      uintptr_t *np;
      auto self = (sl_node<T> *)sl_alloc_node (lvl, sizeof (sl_node<T>), &np);

      new (self) sl_node<T> (lvl, np);

      try
        {
          self->key = k;
          return (self);
        }
      catch (...)
        {
          sl_dealloc_node (self);
          throw;
        }
    }

  template <class ...Args>
  static sl_node<T>* move (unsigned int lvl, Args... args)
    {
      uintptr_t *np;
      auto self = (sl_node<T> *)sl_alloc_node (lvl, sizeof (sl_node<T>), &np);

      new (self) sl_node<T> (lvl, np);
      new (&self->key) optional<T> (std::forward<Args&&>(args)...);
      return (self);
    }

  void safe_destroy ()
    {
      this->key.reset ();
      sl_dealloc_node (this);
    }
};

static const uintptr_t SL_XBIT = 1;
static const unsigned int SL_MAX_DEPTH = 24;

static const int SL_UNLINK_SKIP = -1;
static const int SL_UNLINK_NONE = 0;
static const int SL_UNLINK_ASSIST = 1;
static const int SL_UNLINK_FORCE = 2;

inline void
init_preds_succs (uintptr_t *p1, uintptr_t *p2)
{
  for (unsigned int i = 0; i < SL_MAX_DEPTH; ++i)
    p1[i] = p2[i] = 0;
}

} // namespace detail

template <class T, class Cmp = std::less<T> >
struct skip_list
{
  std::atomic<detail::sl_node<T> *> head;
  Cmp cmpfn;
  unsigned int max_depth;
  std::atomic<size_t> hi_water { 1 };

  typedef T value_type;
  typedef T key_type;
  typedef Cmp key_compare;
  typedef Cmp value_compare;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  typedef T& reference;
  typedef const T& const_reference;
  typedef T* pointer;
  typedef const T* const_pointer;

  typedef detail::sl_node<T> node_type;
  typedef skip_list<T, Cmp> _Self;

  node_type* _Make_root ()
    {
      uintptr_t *np;
      auto ret = (node_type *)
        detail::sl_alloc_node (this->max_depth + 1,
                               sizeof (node_type), &np);

      new (ret) node_type (this->max_depth, np + 1);
      return (ret);
    }

  uintptr_t _Head () const
    {
      return ((uintptr_t)this->head.load (std::memory_order_relaxed));
    }

  size_t _Hiwater () const
    {
      return (this->hi_water.load (std::memory_order_relaxed));
    }

  static node_type* _Node (uintptr_t addr)
    {
      return ((node_type *)(addr & ~detail::SL_XBIT));
    }

  static uintptr_t& _Node_at (uintptr_t addr, unsigned int lvl)
    {
      return (_Self::_Node(addr)->next[lvl]);
    }

  static unsigned int _Node_lvl (uintptr_t addr)
    {
      return (_Self::_Node(addr)->nlvl);
    }

  uintptr_t* _Root_plen (uintptr_t addr)
    {
      return (_Self::_Node(addr)->next - 1);
    }

  void _Bump_len (uintptr_t *lenp, intptr_t off)
    {
      xatomic_add (lenp, off + off);
    }

  void _Init (Cmp c, unsigned int depth)
    {
      this->cmpfn = c;
      if ((this->max_depth = depth) > detail::SL_MAX_DEPTH)
        this->max_depth = detail::SL_MAX_DEPTH;

      this->head.store (this->_Make_root (), std::memory_order_relaxed);
    }

  skip_list (Cmp c = Cmp (), unsigned int depth = detail::SL_MAX_DEPTH)
    {
      this->_Init (c, depth);
    }

  template <class Iter>
  skip_list (Iter first, Iter last,
      Cmp c = Cmp (), unsigned int depth = detail::SL_MAX_DEPTH)
    {
      this->_Init (c, depth);
      for (; first != last; ++first)
        this->insert (*first);
    }

  skip_list (std::initializer_list<T> lst,
      Cmp c = Cmp (), unsigned int depth = detail::SL_MAX_DEPTH) :
        skip_list (lst.begin (), lst.end (), c, depth)
    {
    }

  skip_list (const _Self& right) : skip_list (right.begin (), right.end ())
    {
    }

  skip_list (_Self&& right)
    {
      this->head.store (right.head.load (std::memory_order_relaxed),
                        std::memory_order_relaxed);
      this->cmpfn = right.cmpfn;
      this->max_depth = right.max_depth;
      this->hi_water.store (right.hi_water.load (std::memory_order_relaxed),
                            std::memory_order_relaxed);

      right.head.store (nullptr, std::memory_order_relaxed);
    }

  struct iterator : public cs_guard
    {
      uintptr_t node;

      typedef std::forward_iterator_tag iterator_category;

      iterator () : node (0)
        {
        }

      iterator (uintptr_t addr) : node (addr)
        {
        }

      iterator (const iterator& right) : node (right.node)
        {
        }

      iterator (iterator&& right) : node (right.node)
        {
          right.node = 0;
        }

      iterator& operator++ ()
        {
          while (true)
            {
              if (this->node == 0)
                break;

              this->node = skip_list<T, Cmp>::_Node_at (this->node, 0);
              if ((this->node & detail::SL_XBIT) == 0)
                break;
            }

          return (*this);
        }

      iterator operator++ (int)
        {
          iterator tmp { this->node };
          ++*this;
          return (tmp);
        }

      const T& operator* () const
        {
          return (skip_list<T, Cmp>::_Getk (this->node));
        }

      const T* operator-> () const
        {
          return (&**this);
        }

      iterator& operator= (const iterator& right)
        {
          this->node = right.node;
          return (*this);
        }

      iterator& operator= (iterator&& right)
        {
          this->node = right.node;
          right.node = 0;
          return (*this);
        }

      bool operator== (const iterator& right) const
        {
          return (this->node == right.node);
        }

      bool operator!= (const iterator& right) const
        {
          return (this->node != right.node);
        }
    };

  typedef iterator const_iterator;

  unsigned int _Rand_lvl ()
    {
      size_t lvl = ctz (xrand ()) * 2 / 3;

      if (lvl == 0)
        return (1);
      while (true)
        {
          auto prev = this->_Hiwater ();
          if (lvl <= prev)
            return (lvl);
          else if (prev == detail::SL_MAX_DEPTH ||
              this->hi_water.compare_exchange_weak (prev, prev + 1,
                std::memory_order_acq_rel, std::memory_order_relaxed))
            return (prev);

          xatomic_spin_nop ();
        }
    }

  static const T& _Getk (uintptr_t addr)
    {
      return (*_Self::_Node(addr)->key);
    }

  uintptr_t _Find_preds (int n, const T& key, int unlink,
      uintptr_t *preds = nullptr, uintptr_t *succs = nullptr,
      uintptr_t *outp = nullptr) const
    {
      bool got = false;
      uintptr_t pr = this->_Head (), it = 0;

      if (outp)
        *outp = pr;

      for (int lvl = (int)this->_Hiwater () - 1; lvl >= 0; --lvl)
        {
          uintptr_t next = _Self::_Node_at (pr, lvl);
          if (next == 0 && lvl >= n)
            continue;
          else if (next & detail::SL_XBIT)
            return (this->_Find_preds (n, key, unlink, preds, succs, outp));

          for (it = next; it != 0; )
            {
              next = _Self::_Node_at (it, lvl);
              while (next & detail::SL_XBIT)
                {
                  if (unlink == detail::SL_UNLINK_SKIP ||
                      unlink == detail::SL_UNLINK_NONE)
                    { // Skip logically deleted elements.
                      if ((it = next & ~detail::SL_XBIT) == 0)
                        break;

                      next = _Self::_Node_at (it, lvl);
                    }
                  else
                    {
                      uintptr_t qx = xatomic_cas (&_Self::_Node_at(pr, lvl),
                                                  it, next & ~detail::SL_XBIT);
                      if (qx == it)
                        it = next & ~detail::SL_XBIT;
                      else
                        {
                          if (qx & detail::SL_XBIT)
                            return (this->_Find_preds (n,
                              key, unlink, preds, succs, outp));

                          it = qx;
                        }

                      next = it ? _Self::_Node_at (it, lvl) : 0;
                    }
                }

              if (it == 0 || this->cmpfn (key, _Self::_Getk (it)) ||
                  (unlink != detail::SL_UNLINK_FORCE &&
                    (got = !this->cmpfn (_Self::_Getk (it), key))))
                break;

              pr = it, it = next;
            }

          if (preds)
            preds[lvl] = pr, succs[lvl] = it;
        }

      return (got || unlink == detail::SL_UNLINK_SKIP ? it : 0);
    }

  optional<T> find (const T& key) const
    {
      cs_guard g;
      uintptr_t rv = this->_Find_preds (0, key, detail::SL_UNLINK_NONE);
      return (rv ? optional<T> (this->_Getk (rv)) : optional<T> ());
    }

  bool contains (const T& key) const
    {
      cs_guard g;
      return (this->_Find_preds (0, key, detail::SL_UNLINK_NONE) != 0);
    }

  const_iterator lower_bound (const T& key) const
    {
      uintptr_t preds[detail::SL_MAX_DEPTH], succs[detail::SL_MAX_DEPTH];
      detail::init_preds_succs (preds, succs);

      cs_guard g;
      this->_Find_preds (0, key, detail::SL_UNLINK_NONE, preds, succs);

      uintptr_t it_val;
      for (auto val : preds)
        if ((it_val = val) != 0)
          break;

      const_iterator ret { it_val };
      if (ret.node == this->_Head ())
        ++ret;

      return (ret);
    }

  const_iterator upper_bound (const T& key) const
    {
      cs_guard g;
      uintptr_t it = this->_Find_preds (0, key, detail::SL_UNLINK_SKIP);
      const_iterator ret { it };
      if (it)
        ++ret;

      return (ret);
    }

  bool _Insert (const T& key)
    {
      uintptr_t xroot;
      uintptr_t preds[detail::SL_MAX_DEPTH], succs[detail::SL_MAX_DEPTH];

      detail::init_preds_succs (preds, succs);

      size_t n = this->_Rand_lvl ();
      if (this->_Find_preds (n, key, detail::SL_UNLINK_ASSIST,
          preds, succs, &xroot) != 0)
        return (false);

      uintptr_t nv = (uintptr_t)node_type::copy (n, key);

      for (size_t lvl = 0; lvl < n; ++lvl)
        _Self::_Node_at(nv, lvl) = succs[lvl];

      uintptr_t pred = *preds;
      if (!xatomic_cas_bool (&_Self::_Node_at(pred, 0), *succs, nv))
        {
          _Self::_Node(nv)->safe_destroy ();
          return (this->_Insert (key));
        }

      for (size_t lvl = 1; lvl < n; ++lvl)
        while (true)
          {
            pred = preds[lvl];
            if (xatomic_cas_bool (&_Self::_Node_at(pred, lvl),
                                  succs[lvl], nv))
              break;   // Successful link.

            this->_Find_preds (n, key, detail::SL_UNLINK_ASSIST, preds, succs);
            for (size_t ix = lvl; ix < n; ++ix)
              if ((pred = _Self::_Node_at (nv, ix)) == succs[ix])
                continue;
              else if (xatomic_cas (&_Self::_Node_at(nv, ix),
                                    pred, succs[ix]) & detail::SL_XBIT)
                { // Another thread is removing this very key - Bail out.
                  this->_Find_preds (0, key, detail::SL_UNLINK_FORCE);
                  return (false);
                }
          }

      if (_Self::_Node_at (nv, n - 1) & detail::SL_XBIT)
        { // Another thread is removing this key - Make sure it's unlinked.
          this->_Find_preds (0, key, detail::SL_UNLINK_FORCE);
          return (false);
        }

      this->_Bump_len (this->_Root_plen (xroot), 1);
      return (true);
    }

  bool insert (const T& key)
    {
      cs_guard g;
      return (this->_Insert (key));
    }

  uintptr_t _Erase (const T& key)
    {
      uintptr_t xroot, it = this->_Find_preds (this->_Hiwater (), key,
                                               detail::SL_UNLINK_NONE,
                                               nullptr, nullptr, &xroot);

      if (it == 0)
        return (it);

      node_type *nodep = _Self::_Node (it);
      uintptr_t qx = 0, next = 0;

      for (int lvl = nodep->nlvl - 1; lvl >= 0; --lvl)
        {
          qx = nodep->next[lvl];
          do
            {
              next = qx;
              qx = xatomic_cas (&nodep->next[lvl],
                next, next | detail::SL_XBIT);

              if (qx & detail::SL_XBIT)
                {
                  if (lvl == 0)
                    return (0);
                  break;
                }
            }
          while (next != qx);
        }

      // Unlink the item.
      this->_Find_preds (0, key, detail::SL_UNLINK_FORCE);
      this->_Bump_len (this->_Root_plen (xroot), -1);
      finalize (nodep);
      return (it);
    }

  bool erase (const T& key)
    {
      cs_guard g;
      return (this->_Erase (key) != 0);
    }

  optional<T> remove (const T& key)
    {
      cs_guard g;
      uintptr_t it = this->_Erase (key);
      return (it ? optional<T> (_Self::_Getk (it)) : optional<T> ());
    }

  const_iterator cbegin () const
    {
      return (iterator (_Self::_Node_at (this->_Head (), 0)));
    }

  iterator begin ()
    {
      return (this->cbegin ());
    }

  const_iterator begin () const
    {
      return (this->cbegin ());
    }

  iterator end ()
    {
      return (this->cend ());
    }

  const_iterator end () const
    {
      return (this->cend ());
    }

  const_iterator cend () const
    {
      return (iterator (0));
    }

  size_t size () const
    {
      cs_guard g;
      uintptr_t *p = this->head.load (std::memory_order_relaxed)->next - 1;
      return (*p >> 1);
    }

  size_t max_size () const
    {
      return ((~(size_t)0) >> 1);
    }

  bool empty () const
    {
      return (this->size () == 0);
    }

  template <bool Destroy = false>
  void _Fini_root (node_type *xroot)
    {
      for (uintptr_t run = (uintptr_t)xroot; run != 0; )
        {
          uintptr_t next = _Self::_Node_at (run, 0);

          if (Destroy)
            _Self::_Node(run)->safe_destroy ();
          else
            finalize (_Self::_Node (run));

          run = next;
        }
    }

  void _Lock_root ()
    {
      cs_guard g;
      while (true)
        {
          auto ptr = this->_Root_plen ((uintptr_t)
            this->head.load (std::memory_order_relaxed));
          auto val = *ptr;

          if ((val & 1) == 0 && xatomic_cas_bool (ptr, val, val | 1))
            break;

          xatomic_spin_nop ();
        }
    }

  template <class Iter>
  void assign (Iter first, Iter last)
    {
      _Self tmp (first, last);
      auto tp = tmp.head.load (std::memory_order_relaxed);
      tmp.head.store (this->head.exchange (tp, std::memory_order_acq_rel));
    }

  void assign (std::initializer_list<T> lst)
    {
      this->assign (lst.begin (), lst.end ());
    }

  _Self& operator= (const _Self& right)
    {
      this->assign (right.begin (), right.end ());
      return (*this);
    }

  _Self& operator= (_Self&& right)
    {
      auto tp = right.head.load (std::memory_order_relaxed);
      this->_Fini_root<> (this->head.exchange (tp, std::memory_order_acq_rel));
      right.head.store (nullptr, std::memory_order_relaxed);
    }

  void swap (_Self& right)
    {
      if (this == &right)
        return;

      this->_Lock_root ();
      right._Lock_root ();

      auto lw = this->hi_water.load (std::memory_order_relaxed);
      auto rw = right.hi_water.load (std::memory_order_relaxed);

      this->hi_water.store (rw, std::memory_order_relaxed);
      right.hi_water.store (lw, std::memory_order_relaxed);

      auto lh = this->head.load (std::memory_order_relaxed);
      auto rh = right.head.load (std::memory_order_relaxed);

      this->head.store (rh, std::memory_order_relaxed);
      right.head.store (lh, std::memory_order_relaxed);

      xatomic_and (this->_Root_plen ((uintptr_t)rh), ~(uintptr_t)1);
      xatomic_and (right._Root_plen ((uintptr_t)lh), ~(uintptr_t)1);
    }

  void clear ()
    {
      auto xroot = this->_Make_root ();
      auto prev = this->head.exchange (xroot, std::memory_order_release);
      this->_Fini_root<> (prev);
    }

  ~skip_list ()
    {
      this->_Fini_root<true> (this->head.load (std::memory_order_relaxed));
    }
};

} // namespace xrcu

namespace std
{

template <class T, class Cmp>
void swap (xrcu::skip_list<T, Cmp>& left,
           xrcu::skip_list<T, Cmp>& right)
{
  left.swap (right);
}

} // namespace std

#endif


code:
#include "stack.hpp"
#include "xatomic.hpp"
#include <atomic>

namespace xrcu
{

namespace detail
{

static const uintptr_t SPIN_BIT = 1;

static inline bool
node_spinning_p (const stack_node_base *np)
{
  return (((uintptr_t)np) & SPIN_BIT);
}

static inline stack_node_base*
get_node (const stack_node_base::ptr_type& head)
{
  return (head.load (std::memory_order_relaxed));
}

stack_node_base* stack_node_base::root (const ptr_type& head)
{
  auto ret = (uintptr_t)get_node (head);
  return (((stack_node_base *)(ret & ~SPIN_BIT)));
}

void stack_node_base::push (ptr_type& head, stack_node_base *nodep)
{
  while (true)
    {
      nodep->next = get_node (head);
      if (!node_spinning_p (nodep->next) &&
          head.compare_exchange_weak (nodep->next, nodep,
            std::memory_order_acq_rel, std::memory_order_relaxed))
        break;

      xatomic_spin_nop ();
    }
}

void stack_node_base::push (ptr_type& head,
  stack_node_base *nodep, stack_node_base **outp)
{
  while (true)
    {
      auto tmp = get_node (head);
      if (!node_spinning_p (tmp))
        {
          *outp = tmp;
          if (head.compare_exchange_weak (tmp, nodep,
              std::memory_order_acq_rel, std::memory_order_relaxed))
            break;
        }

      xatomic_spin_nop ();
    }
}

stack_node_base* stack_node_base::pop (ptr_type& head)
{
  while (true)
    {
      auto nodep = get_node (head);
      if (node_spinning_p (nodep))
        ;
      else if (!nodep)
        return (nodep);
      else if (head.compare_exchange_weak (nodep, nodep->next,
          std::memory_order_acq_rel, std::memory_order_relaxed))
        {
          nodep->next = nullptr;
          return (nodep);
        }

      xatomic_spin_nop ();
    }
}

static inline stack_node_base*
set_spin (stack_node_base::ptr_type& head)
{
  while (true)
    {
      auto tmp = get_node (head);
      if (!node_spinning_p (tmp) &&
          head.compare_exchange_weak (tmp,
            (stack_node_base *)((uintptr_t)tmp | SPIN_BIT),
            std::memory_order_acq_rel, std::memory_order_relaxed))
        return (tmp);

      xatomic_spin_nop ();
    }
}

void stack_node_base::swap (ptr_type& h1, ptr_type& h2)
{
  // Prevent any further modifications.
  auto ln = set_spin (h1), rn = set_spin (h2);

  // Swap the root nodes.
  h1.store (rn, std::memory_order_release);
  h2.store (ln, std::memory_order_release);
}

stack_node_base* stack_node_base::clear (ptr_type& head)
{
  auto ret = set_spin (head);
  head.store (nullptr, std::memory_order_release);
  return (ret);
}

size_t stack_node_base::size (const ptr_type& head)
{
  auto runp = get_node (head);
  size_t ret = 0;

  for (; runp; runp = runp->next, ++ret) ;
  return (ret);
}

} } // namespaces

repo_name: avarzille/xrcu

license: mit


code:
#ifndef __XRCU_STACK_HPP__
#define __XRCU_STACK_HPP__   1

#include "xrcu.hpp"
#include "optional.hpp"
#include <atomic>
#include <cstddef>
#include <utility>
#include <initializer_list>

namespace std
{
  struct forward_iterator_tag;
}

namespace xrcu
{

namespace detail
{

struct stack_node_base
{
  stack_node_base *next = nullptr;
  typedef std::atomic<stack_node_base *> ptr_type;

  static stack_node_base* root (const ptr_type& head);

  static void push (ptr_type& head, stack_node_base *nodep);

  static void push (ptr_type& head,
    stack_node_base *nodep, stack_node_base **outp);

  static stack_node_base* pop (ptr_type& head);

  static void swap (ptr_type& h1, ptr_type& h2);

  static stack_node_base* clear (ptr_type& head);

  static size_t size (const ptr_type& head);
};

struct stack_iter_base : public cs_guard
{
  stack_node_base *runp;

  typedef std::forward_iterator_tag iterator_category;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;

  stack_iter_base (stack_node_base *rp) : runp (rp)
    {
    }

  stack_iter_base (const stack_iter_base& right) : runp (right.runp)
    {
    }

  stack_iter_base (stack_iter_base&& right) : runp (right.runp)
    {
      right.runp = nullptr;
    }

  void _Adv ()
    {
      this->runp = this->runp->next;
    }

  bool operator== (const stack_iter_base& right) const
    {
      return (this->runp == right.runp);
    }

  bool operator!= (const stack_iter_base& right) const
    {
      return (this->runp != right.runp);
    }
};

} // namespace detail.

template <class T>
struct stack
{
  std::atomic<detail::stack_node_base *> hnode;

  struct _Stknode : public detail::stack_node_base, finalizable
    {
      T value;

      _Stknode (const T& v) : value (v)
        {
        }

      _Stknode (T&& v) : value (std::move (v))
        {
        }

      template <class ...Args>
      _Stknode (Args&&... args) : value (std::forward<Args>(args)...)
        {
        }

      void safe_destroy ()
        {
          auto runp = this->next;
          delete this;
          stack<T>::_Clean_nodes (runp);
        }
    };

  typedef _Stknode node_type;
  typedef T value_type;
  typedef T& reference;
  typedef const T& const_reference;
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;

  void _Reset (detail::stack_node_base *ptr)
    {
      this->hnode.store (ptr, std::memory_order_relaxed);
    }

  static void _Clean_nodes (detail::stack_node_base *runp)
    {
      while (runp)
        {
          auto tmp = runp->next;
          delete (node_type *)runp;
          runp = tmp;
        }
    }

  template <class T1>
  void _Init (T1 first, T1 last, std::false_type)
    {
      detail::stack_node_base *runp = nullptr, **outp = &runp;
      try
        {
          for (; first != last; ++first)
            {
              *outp = new node_type (*first);
              outp = &(*outp)->next;
            }
        }
      catch (...)
        {
          _Clean_nodes (runp);
          throw;
        }

      this->_Reset (runp);
    }

  template <class T1, class T2>
  void _Init (T1 n, const T2& value, std::true_type)
    {
      detail::stack_node_base *runp = nullptr, **outp = &runp;

      try
        {
          for (T1 x = 0; x != n; ++x)
            {
              *outp = new node_type (value);
              outp = &(*outp)->next;
            }
        }
      catch (...)
        {
          _Clean_nodes (runp);
          throw;
        }

      this->_Reset (runp);
    }

  stack ()
    {
      this->_Reset (nullptr);
    }

  template <class T1, class T2>
  stack (T1 first, T2 last)
    {
      this->_Reset (nullptr);
      this->_Init (first, last, typename std::is_integral<T1>::type ());
    }

  stack (std::initializer_list<T> lst) : stack (lst.begin (), lst.end ())
    {
    }

  stack (const stack<T>& right) : stack (right.begin (), right.end ())
    {
    }

  stack (stack<T>&& right)
    {
      this->_Reset (right._Root ());
      right._Reset (nullptr);
    }

  void push (const T& value)
    {
      cs_guard g;
      detail::stack_node_base::push (this->hnode, new node_type (value));
    }

  void push (T&& value)
    {
      cs_guard g;
      detail::stack_node_base::push (this->hnode,
        new node_type (std::move (value)));
    }

  template <class Iter>
  void _Push (Iter first, Iter last, std::false_type)
    {
      if (first == last)
        return;

      node_type *np;

      try
        {
          np = new node_type (*first);
          auto **outp = &np->next;

          for (++first; first != last; ++first)
            {
              node_type *tmp = new node_type (*first);
              *outp = tmp, outp = &tmp->next;
            }

          detail::stack_node_base::push (this->hnode, np, outp);
        }
      catch (...)
        {
          _Clean_nodes (np);
          throw;
        }
    }

  template <class T1, class T2>
  void _Push (T1 n, const T2& value, std::true_type)
    {
      if (n == 0)
        return;

      node_type *np;

      try
        {
          np = new node_type (value);
          auto **outp = &np->next;

          for (; n != 0; --n)
            {
              node_type *tmp = new node_type (value);
              *outp = tmp, outp = &tmp->next;
            }

          detail::stack_node_base::push (this->hnode, np, outp);
        }
      catch (...)
        {
          _Clean_nodes (np);
          throw;
        }
    }

  template <class T1, class T2>
  void push (T1 first, T2 last)
    {
      this->_Push (first, last, typename std::is_integral<T1>::type ());
    }

  template <class ...Args>
  void emplace (Args&& ...args)
    {
      detail::stack_node_base::push (this->hnode,
        new node_type (std::forward<Args>(args)...));
    }

  optional<T> pop ()
    {
      cs_guard g;
      auto node = detail::stack_node_base::pop (this->hnode);

      if (!node)
        return (optional<T> ());

      optional<T> ret { ((node_type *)node)->value };
      finalize ((node_type *)node);
      return (ret);
    }

  node_type* _Root ()
    {
      return ((node_type *)detail::stack_node_base::root (this->hnode));
    }

  node_type* _Root () const
    {
      return ((node_type *)detail::stack_node_base::root (this->hnode));
    }

  optional<T> top ()
    {
      cs_guard g;
      auto node = this->_Root ();
      return (node ? optional<T> { node->value } : optional<T> ());
    }

  struct iterator : public detail::stack_iter_base
    {
      typedef T value_type;
      typedef T& reference;
      typedef T* pointer;

      iterator (detail::stack_node_base *rp = nullptr) :
          detail::stack_iter_base (rp)
        {
        }

      iterator (const iterator& it) : detail::stack_iter_base (it)
        {
        }

      iterator (iterator&& it) : detail::stack_iter_base (std::move (it))
        {
        }

      T& operator* ()
        {
          return (((node_type *)this->runp)->value);
        }

      const T& operator* () const
        {
          return (((const node_type *)this->runp)->value);
        }

      T* operator-> ()
        {
          return (&**this);
        }

      const T* operator-> () const
        {
          return (&**this);
        }

      iterator& operator++ ()
        {
          this->_Adv ();
          return (*this);
        }

      iterator operator++ (int)
        {
          iterator tmp = { this->runp };
          this->_Adv ();
          return (tmp);
        }
    };

  typedef const iterator const_iterator;

  iterator begin ()
    {
      return (iterator (this->_Root ()));
    }

  iterator end ()
    {
      return (iterator ());
    }

  const_iterator cbegin () const
    {
      return (const_iterator (this->_Root ()));
    }

  const_iterator cend () const
    {
      return (const_iterator ());
    }

  const_iterator begin () const
    {
      return (this->cbegin ());
    }

  const_iterator end () const
    {
      return (this->cend ());
    }

  size_t size () const
    {
      cs_guard g;
      return (detail::stack_node_base::size (this->hnode));
    }

  size_t max_size () const
    {
      return (~(size_t)0);
    }

  bool empty () const
    {
      return (this->_Root () == nullptr);
    }

  void swap (stack<T>& right)
    {
      cs_guard g;

      if (this != &right)
        detail::stack_node_base::swap (this->hnode, right.hnode);
    }

  stack<T>& operator= (const stack<T>& right)
    {
      cs_guard g;

      if (this != &right)
        this->assign (right.begin (), right.end ());

      return (*this);
    }

  stack<T>& operator= (stack<T>&& right)
    {
      this->swap (right);
      finalize (right._Root ());
      right._Reset (nullptr);
      return (*this);
    }

  bool operator== (const stack<T>& right) const
    {
      auto x1 = this->cbegin (), x2 = this->cend ();
      auto y1 = right.cbegin (), y2 = right.cend ();

      for (; x1 != x2 && y1 != y2; ++x1, ++y1)
        if (*x1 != *y1)
          return (false);

      return (x1 == x2 && y1 == y2);
    }

  bool operator!= (const stack<T>& right) const
    {
      return (!(*this == right));
    }

  bool operator< (const stack<T>& right) const
    {
      auto x1 = this->cbegin (), x2 = this->cend ();
      auto y1 = right.cbegin (), y2 = right.cend ();

      for (; x1 != x2; ++x1, ++y1)
        {
          if (y1 == y2 || *y1 < *x1)
            return (false);
          else if (*x1 < *y1)
            return (true);
        }

      return (y1 != y2);
    }

  bool operator> (const stack<T>& right) const
    {
      return (right < *this);
    }

  bool operator<= (const stack<T>& right) const
    {
      return (!(right < *this));
    }

  bool operator>= (const stack<T>& right) const
    {
      return (!(*this < right));
    }

  void clear ()
    {
      auto prev = detail::stack_node_base::clear (this->hnode);
      finalize ((node_type *)prev);
    }

  template <class T1, class T2>
  void assign (T1 first, T2 last)
    {
      auto tmp = stack<T> (first, last);
      this->swap (tmp);
      finalize (tmp._Root ());
      tmp._Reset (nullptr);
    }

  void assign (std::initializer_list<T> lst)
    {
      this->assign (lst.begin (), lst.end ());
    }

  ~stack ()
    {
      auto tmp = this->_Root ();
      if (!tmp)
        return;

      _Clean_nodes (tmp);
      this->_Reset (nullptr);
    }
};

} // namespace xrcu

namespace std
{

template <class T>
void swap (xrcu::stack<T>& left, xrcu::stack<T>& right)
{
  return (left.swap (right));
}

} // namespace std

#endif


code:
#ifndef __XRCU_TESTS_HASH__
#define __XRCU_TESTS_HASH__   1

#include "../hash_table.hpp"
#include "utils.hpp"
#include <thread>
#include <algorithm>
#include <cstdio>

typedef xrcu::hash_table<int, std::string> table_t;

namespace ht_test
{

static std::string&
mutate (std::string& in, const char *s)
{
  in += s;
  return (in);
}

static std::string
mknew (std::string& in, const char *s)
{
  return (in + s);
}

void test_single_threaded ()
{
  table_t tx { { -1, "abc" }, { -2, "def" }, { -3, "ghi" } };
  ASSERT (tx.size () == 3);
  ASSERT (!tx.empty ());
  ASSERT (tx.find (-2, std::string ("")) == "def");

  for (int i = 0; i < 4000; ++i)
    tx.insert (i, mkstr (i));

  for (int i = -3; i < 4000; ++i)
    ASSERT (tx.contains (i));

  tx.update (101, mutate, "!!!");
  ASSERT (tx.find(101, std::string ("")).find ("!!!") != std::string::npos);

  tx.update (2002, mknew, "!!!");
  ASSERT (tx.find(2002, std::string ("")).find ("!!!") != std::string::npos);

  auto old_size = tx.size ();

  int i;
  for (i = 0; i < 1000; i += 2)
    ASSERT (tx.erase (i));

  ASSERT (tx.size () == old_size - i / 2);

  auto prev = tx.remove (101);
  ASSERT (prev.has_value ());

  i = 0;
  for (const auto& q : tx)
    {
      ASSERT (q.second.size () > 0);
      ++i;
    }

  ASSERT ((size_t)i == tx.size ());

  auto old = tx;
  tx.clear ();

  ASSERT (tx.size () == 0);
  ASSERT (old.size () != 0);

  tx.swap (old);
  ASSERT (old.size () == 0);
  ASSERT (tx.size () != 0);

  ASSERT (!xrcu::in_cs ());
}

static void
mt_inserter (table_t *tx, int index)
{
  for (int i = 0; i < INSERTER_LOOPS; ++i)
    {
      int key = index * INSERTER_LOOPS + i;
      ASSERT (tx->insert (key, mkstr (key)));
    }
}

static bool
ht_consistent (table_t& tx)
{
  if (tx.empty ())
    return (true);

  for (auto p : tx)
    if (mkstr (p.first) != p.second)
      return (false);

  return (true);
}

void test_insert_mt ()
{
  table_t tx;
  std::vector<std::thread> thrs;

  for (int i = 0; i < INSERTER_THREADS; ++i)
    thrs.push_back (std::thread (mt_inserter, &tx, i));

  for (auto& thr: thrs)
    thr.join ();

  ASSERT (tx.size () == INSERTER_THREADS * INSERTER_LOOPS);
  ASSERT (ht_consistent (tx));
}

static void
mt_inserter_ov (table_t *tx, int index)
{
  for (int i = 0; i < INSERTER_LOOPS; ++i)
    {
      int key = index * (INSERTER_LOOPS / 2) + i;
      tx->insert (key, mkstr (key));
    }
}

void test_insert_mt_ov ()
{
  table_t tx;
  std::vector<std::thread> thrs;

  for (int i = 0; i < INSERTER_THREADS; ++i)
    thrs.push_back (std::thread (mt_inserter_ov, &tx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (tx.size () == (INSERTER_THREADS + 1) * INSERTER_LOOPS / 2);
  ASSERT (ht_consistent (tx));
}

static void
mt_eraser (table_t *tx, int index)
{
  for (int i = 0; i < ERASER_LOOPS; ++i)
    {
      int key = index * ERASER_LOOPS + i;
      auto prev = tx->remove (key);
      ASSERT (prev.has_value ());
      ASSERT ((*prev)[0] == '-');
    }
}

static void
fill_table_for_erase (table_t& tx)
{
  for (int i = 0; i < ERASER_THREADS * ERASER_LOOPS; ++i)
    tx.insert (i, mkstr (-i - 1));
}

void test_erase_mt ()
{
  table_t tx;
  fill_table_for_erase (tx);

  std::vector<std::thread> thrs;

  for (int i = 0; i < ERASER_THREADS; ++i)
    thrs.push_back (std::thread (mt_eraser, &tx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (tx.empty ());
}

static void
mt_eraser_ov (table_t *tx, int index)
{
  for (int i = 0; i < ERASER_LOOPS; ++i)
    {
      int key = index * (ERASER_LOOPS / 2) + i;
      tx->erase (key);
    }
}

void test_erase_mt_ov ()
{
  table_t tx;
  fill_table_for_erase (tx);

  std::vector<std::thread> thrs;
  for (int i = 0; i < ERASER_THREADS; ++i)
    thrs.push_back (std::thread (mt_eraser_ov, &tx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (tx.size () == (ERASER_THREADS - 1) * ERASER_LOOPS / 2);
}

static void
mt_mutator (table_t *tx)
{
  int keys[MUTATOR_KEY_SIZE];
  for (int i = 0; i < MUTATOR_KEY_SIZE; ++i)
    keys[i] = i;

  std::random_shuffle (keys, keys + MUTATOR_KEY_SIZE);
  for (int i = 0; i < MUTATOR_KEY_SIZE; ++i)
    if (!tx->insert (keys[i], std::string ("")))
      tx->erase (keys[i]);
}

void test_mutate_mt ()
{
  table_t tx;
  std::vector<std::thread> thrs;

  for (int i = 0; i < MUTATOR_THREADS; ++i)
    thrs.push_back (std::thread (mt_mutator, &tx));

  for (auto& thr : thrs)
    thr.join ();

  for (auto q : tx)
    ASSERT (q.first <= MUTATOR_KEY_SIZE && q.second.empty ());
}

void test_iter ()
{
  table_t tx;

  for (int i = 0; i < 5; ++i)
    tx.insert (i, mkstr (i));

  auto it = tx.begin ();

  for (int i = 10; i < 1000; ++i)
    tx.insert (i, mkstr (i));

  int c = 0;
  for (; it != tx.end (); ++it, ++c)
    ;

  ASSERT (c >= 5);
}

test_module hash_table_tests
{
  "hash table",
  {
    { "API in a single thread", test_single_threaded },
    { "multi threaded insertions", test_insert_mt },
    { "multi threaded overlapped insertions", test_insert_mt_ov },
    { "multi threaded erasures", test_erase_mt },
    { "multi threaded overlapped erasures", test_erase_mt_ov },
    { "multi threaded mutations", test_mutate_mt },
    { "iteration during modifications", test_iter }
  }
};

} // namespace ht_test

#endif


code:
#ifndef __XRCU_TESTS_OPT__
#define __XRCU_TESTS_OPT__   1

#include "../optional.hpp"
#include "utils.hpp"

namespace opt_test
{

void test_optional ()
{
  xrcu::optional<std::string> opt;

  ASSERT (!opt.has_value ());
  opt.reset ();
  ASSERT (!opt.has_value ());
  opt = mkstr (100);
  ASSERT (opt.has_value ());

  *opt += mkstr (200);
  ASSERT (*opt == mkstr (100) + mkstr (200));

  opt->clear ();
  ASSERT (opt.has_value ());
  ASSERT (opt->empty ());

  opt.reset ();
  ASSERT (!opt.has_value ());

  std::string s = mkstr (300);
  opt = s;
  ASSERT (s == *opt);

  xrcu::optional<std::string> o2 { opt };
  ASSERT (*o2 == *opt);

  o2.reset ();
  ASSERT (opt.has_value ());

  xrcu::optional<std::string> o3 { mkstr (400) };
  ASSERT (o3.has_value ());
}

test_module optional_tests
{
  "optional",
  {
    { "API", test_optional }
  }
};

} // namespace opt_test

#endif


code:
#ifndef __XRCU_TESTS_QUEUE__
#define __XRCU_TESTS_QUEUE__   1

#include "../queue.hpp"
#include "utils.hpp"
#include <thread>

namespace q_test
{

typedef xrcu::queue<std::string> queue_t;

void test_single_threaded ()
{
  {
    queue_t q;
    ASSERT (q.empty ());
    ASSERT (!q.back().has_value ());
  }

  {
    queue_t q { 3, std::string ("???") };
    ASSERT (q.size () == 3);
    for (const auto& s : q)
      ASSERT (s == "???");
  }

  {
    queue_t q { std::string ("abc"), std::string ("def"),
                std::string ("ghi"), std::string ("jkl") };
    ASSERT (q.size () == 4);

    queue_t q2 { q };

    ASSERT (q == q2);

    queue_t q3 { std::move (q2) };
    ASSERT (q3 == q);
  }

  queue_t q;
  const int NELEM = 100;

  for (int i = 0; i < NELEM; ++i)
    q.push (mkstr (i));

  ASSERT (*q.pop () == mkstr (0));

  queue_t q2;
  q.swap (q2);

  ASSERT (q.empty ());

  q = q2;
  ASSERT (!q.empty ());
  ASSERT (q == q2);

  q.clear ();
  ASSERT (q.empty ());
  q.assign (q2.begin (), q2.end ());
  ASSERT (q == q2);

  q.clear ();
  q2.clear ();

  q.push (mkstr (10));
  q2.push (mkstr (20));
  ASSERT (q < q2);

  q.pop ();
  q.push (mkstr (30));
  ASSERT (q > q2);

  q2.pop ();
  q2.push (mkstr (30));
  q2.push (mkstr (40));
  ASSERT (q <= q2);

  q.push (mkstr (50));
  ASSERT (q >= q2);
}

static void
mt_inserter (queue_t *qp, int index)
{
  for (int i = 0; i < INSERTER_LOOPS; ++i)
    qp->push (mkstr (index * INSERTER_LOOPS + i));
}

void test_push_mt ()
{
  queue_t q;
  std::vector<std::thread> thrs;

  for (int i = 0; i < INSERTER_THREADS; ++i)
    thrs.push_back (std::thread (mt_inserter, &q, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (q.size () == INSERTER_THREADS * INSERTER_LOOPS);
}

test_module queue_tests
{
  "queue",
  {
    { "API in a single thread", test_single_threaded },
    { "multi threaded pushes", test_push_mt }
  }
};

}

#endif


code:
#ifndef __XRCU_TESTS_SL__
#define __XRCU_TESTS_SL__   1

#include "../skip_list.hpp"
#include <thread>
#include <cstdio>
#include <cctype>
#include "utils.hpp"

typedef xrcu::skip_list<std::string> sklist_t;

namespace sl_test
{

void test_single_threaded ()
{
  sklist_t sl;

  ASSERT (sl.empty ());

  sl.assign ({ mkstr (-1), mkstr (-2), mkstr (-3) });
  ASSERT (sl.size () == 3);
  ASSERT (sl.upper_bound (mkstr (0)) == sl.end ());
  ASSERT (sl.lower_bound (std::string ("-0")) == sl.begin ());

  sl.clear ();
  ASSERT (sl.empty ());

  for (int i = 0; i < 1000; ++i)
    ASSERT (sl.insert (mkstr (i)));

  ASSERT (!sl.insert (mkstr (813)));

  ASSERT (sl.size () == 1000);

  auto prev = sl.remove (mkstr (101));
  ASSERT (prev.has_value ());
  ASSERT (*prev == mkstr (101));
  ASSERT (!sl.erase (mkstr (101)));
  ASSERT (sl.erase (mkstr (999)));

  for (const auto& s : sl)
    for (auto ch : s)
      ASSERT (isdigit (ch));

  {
    const int PIVOT = 572;
    auto it = sl.lower_bound (mkstr (PIVOT));
    ASSERT (it != sl.end ());
    ASSERT (*it == mkstr (PIVOT - 1));

    it = sl.upper_bound (mkstr (PIVOT));
    ASSERT (it != sl.end ());
    ASSERT (*it == mkstr (PIVOT + 1));

    sklist_t s2 { std::string ("aaa"), std::string ("bbb"),
                  std::string ("ccc"), std::string ("ddd") };

    sl.swap (s2);
    ASSERT (sl.size () == 4);
    ASSERT (sl.contains (std::string ("aaa")));
  }

  ASSERT (!xrcu::in_cs ());
}

static void
mt_inserter (sklist_t *sx, int index)
{
  for (int i = 0; i < INSERTER_LOOPS; ++i)
    ASSERT (sx->insert (mkstr (index * INSERTER_LOOPS + i)));
}

static bool
sl_consistent (sklist_t& sx)
{
  if (sx.empty ())
    return (true);

  auto it = sx.begin ();
  std::string s1 = *it;

  for (++it; it != sx.end (); ++it)
    {
      std::string s2 = *it;
      if (!(s1 < s2))
        return (false);

      s1.swap (s2);
    }

  return (true);
}

void test_insert_mt ()
{
  sklist_t sx;
  std::vector<std::thread> thrs;

  for (int i = 0; i < INSERTER_THREADS; ++i)
    thrs.push_back (std::thread (mt_inserter, &sx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (sx.size () == INSERTER_THREADS * INSERTER_LOOPS);
  ASSERT (sl_consistent (sx));
}

static void
mt_inserter_ov (sklist_t *sx, int index)
{
  for (int i = 0; i < INSERTER_LOOPS; ++i)
    sx->insert (mkstr (index * (INSERTER_LOOPS / 2) + i));
}

void test_insert_mt_ov ()
{
  sklist_t sx;
  std::vector<std::thread> thrs;

  for (int i = 0; i < INSERTER_THREADS; ++i)
    thrs.push_back (std::thread (mt_inserter_ov, &sx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (sx.size () == (INSERTER_THREADS + 1) * INSERTER_LOOPS / 2);
  ASSERT (sl_consistent (sx));
}

static void
mt_eraser (sklist_t *sx, int index)
{
  for (int i = 0; i < ERASER_LOOPS; ++i)
    {
      auto prev = sx->remove (mkstr (index * ERASER_LOOPS + i));
      ASSERT (prev.has_value ());
      for (auto ch : *prev)
        ASSERT (isdigit (ch));
    }
}

static void
fill_list_for_erase (sklist_t& sx)
{
  for (int i = 0; i < ERASER_THREADS * ERASER_LOOPS; ++i)
    sx.insert (mkstr (i));
}

void test_erase_mt ()
{
  sklist_t sx;
  fill_list_for_erase (sx);

  std::vector<std::thread> thrs;
  for (int i = 0; i < ERASER_THREADS; ++i)
    thrs.push_back (std::thread (mt_eraser, &sx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (sx.empty ());
}

static void
mt_eraser_ov (sklist_t *sx, int index)
{
  for (int i = 0; i < ERASER_LOOPS; ++i)
    sx->erase (mkstr (index * (ERASER_LOOPS / 2) + i));
}

void test_erase_mt_ov ()
{
  sklist_t sx;
  fill_list_for_erase (sx);

  std::vector<std::thread> thrs;
  for (int i = 0; i < ERASER_THREADS; ++i)
    thrs.push_back (std::thread (mt_eraser_ov, &sx, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (sx.size () == (ERASER_THREADS - 1) * ERASER_LOOPS / 2);
  ASSERT (sl_consistent (sx));
}

test_module skip_list_tests
{
  "skip list",
  {
    { "API in a single thread", test_single_threaded },
    { "multi threaded insertions", test_insert_mt },
    { "multi threaded overlapped insertions", test_insert_mt_ov },
    { "multi threaded erasures", test_erase_mt },
    { "multi threaded overlapped erasures", test_erase_mt_ov }
  }
};

} // namespace sl_test

#endif


code:
#ifndef __XRCU_TESTS_STACK__
#define __XRCU_TESTS_STACK__   1

#include "../stack.hpp"
#include "utils.hpp"
#include <thread>

namespace stk_test
{

typedef xrcu::stack<std::string> stack_t;

void test_single_threaded ()
{
  {
    stack_t stk;
    ASSERT (stk.empty ());
    ASSERT (!stk.top().has_value ());
  }

  {
    stack_t stk { 3, std::string ("???") };
    ASSERT (stk.size () == 3);
    for (const auto& s : stk)
      ASSERT (s == "???");
  }

  {
    stack_t stk { std::string ("abc"), std::string ("def"),
                  std::string ("ghi"), std::string ("jkl") };
    ASSERT (stk.size () == 4);
  }

  {
    std::string vals[] = { "abc", "def", "ghi" };
    stack_t stk { vals, vals + 3 };
    size_t i = 0;

    for (const auto& s : stk)
      ASSERT (s == vals[i++]);

    stack_t s2 { stk };
    ASSERT (s2 == stk);

    stack_t s3 { std::move (s2) };
    ASSERT (stk == s3);
  }

  stack_t stk;
  const int NELEM = 100;

  for (int i = 0; i < NELEM; ++i)
    stk.push (mkstr (i));

  ASSERT (*stk.top() == mkstr (NELEM - 1));

  stack_t s2;
  stk.swap (s2);

  ASSERT (stk.empty ());

  stk = s2;
  ASSERT (!stk.empty ());
  ASSERT (stk == s2);

  stk.clear ();
  ASSERT (stk.empty ());
  stk.assign (s2.begin (), s2.end ());
  ASSERT (stk == s2);

  stk.clear ();
  s2.clear ();

  stk.push (mkstr (10));
  s2.push (mkstr (20));
  ASSERT (stk < s2);

  stk.pop ();
  stk.push (mkstr (30));
  ASSERT (stk > s2);

  s2.pop ();
  s2.push (mkstr (30));
  s2.push (mkstr (40));
  ASSERT (stk <= s2);

  stk.push (mkstr (50));
  ASSERT (stk >= s2);

  ASSERT (!xrcu::in_cs ());
}

static void
mt_inserter (stack_t *stkp, int index)
{
  for (int i = 0; i < INSERTER_LOOPS; ++i)
    stkp->push (mkstr (index * INSERTER_LOOPS + i));
}

void test_push_mt ()
{
  stack_t stk;
  std::vector<std::thread> thrs;

  for (int i = 0; i < INSERTER_THREADS; ++i)
    thrs.push_back (std::thread (mt_inserter, &stk, i));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (stk.size () == INSERTER_THREADS * INSERTER_LOOPS);
}

test_module stack_tests
{
  "stack",
  {
    { "API in a single thread", test_single_threaded },
    { "multi threaded pushes", test_push_mt }
  }
};

} // namespace stk_test

#endif


code:
#include "xrcu.hpp"
#include "opt.hpp"
#include "sl.hpp"
#include "hash.hpp"
#include "stack.hpp"
#include "queue.hpp"

int main ()
{
  run_tests ();
  return (0);
}


code:
#ifndef __XRCU_TESTS_UTILS__
#define __XRCU_TESTS_UTILS__   1

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <initializer_list>
#include <cstdlib>
#include <cstdio>

#define ASSERT(Cond)   \
  do   \
    {   \
      if (!(Cond))   \
        {   \
          std::cerr << "\n\nAssertion failed: " << #Cond <<   \
            "\nLine: " << __LINE__ << "\nFile: " << __FILE__ << "\n\n";   \
          exit (EXIT_FAILURE);   \
        }   \
    }   \
  while (0)

struct test_fn
{
  std::string msg;
  void (*fct) (void);

  test_fn (const std::string& m, void (*f) (void)) : msg (m), fct (f)
    {
    }

  void run () const
    {
      std::cout << "Testing " << this->msg << "...";
      this->fct ();
      std::cout << " OK\n";
    }
};

std::vector<test_fn>& test_suite ()
{
  static std::vector<test_fn> ts;
  return (ts);
}

void run_tests ()
{
  for (auto& tst : test_suite ())
    tst.run ();

  std::cout << "Done\n";
}

struct test_module
{
  typedef std::pair<std::string, void (*) (void)> pair_type;

  test_module (const char *name, std::initializer_list<pair_type> tests)
    {
      std::string nm = std::string (" (") + name + ") ";

      for (auto pair : tests)
        test_suite().push_back (test_fn (pair.first + nm, pair.second));
    }
};

// Common constants for all tests.
static const int INSERTER_LOOPS = 2000;
static const int INSERTER_THREADS = 32;

static const int ERASER_THREADS = 16;
static const int ERASER_LOOPS = 2000;

static const int MUTATOR_KEY_SIZE = 200;
static const int MUTATOR_THREADS = 32;

inline std::string mkstr (int i)
{
  char buf[100];
  sprintf (buf, "%d", i);
  return (std::string (buf));
}

#endif


code:
#ifndef __XRCU_TESTS_XRCU__
#define __XRCU_TESTS_XRCU__   1

#include "../xrcu.hpp"
#include "utils.hpp"
#include <thread>
#include <atomic>

namespace xrcu_test
{

static std::atomic<int> G_CNT;

struct tst_fin : public xrcu::finalizable
{
  ~tst_fin ()
    {
      G_CNT.fetch_add (1);
    }
};

void test_xrcu ()
{
  xrcu::enter_cs ();
  ASSERT (xrcu::in_cs ());
  xrcu::exit_cs ();
  ASSERT (!xrcu::in_cs ());

  xrcu::enter_cs ();
  tst_fin *p = new tst_fin ();
  finalize (p);
  xrcu::flush_finalizers ();
  ASSERT (G_CNT.load () == 0);
  xrcu::exit_cs ();
  ASSERT (G_CNT.load () == 1);
}

static void
mt_xrcu (tst_fin *fp)
{
  xrcu::cs_guard g;
  finalize (fp);
}

void test_xrcu_mt ()
{
  const int NTHREADS = 100;
  std::vector<std::thread> thrs;

  G_CNT.store (0);

  for (int i = 0; i < NTHREADS; ++i)
    thrs.push_back (std::thread (mt_xrcu, new tst_fin ()));

  for (auto& thr : thrs)
    thr.join ();

  ASSERT (G_CNT.load () == NTHREADS);
}

test_module xrcu_tests
{
  "xrcu",
  {
    { "API", test_xrcu },
    { "API with multiple threads", test_xrcu_mt }
  }
};

} // namespace xrcu_test

#endif


code:
#ifndef __XRCU_UTILS_HPP__
#define __XRCU_UTILS_HPP__   1

#include "xrcu.hpp"
#include <utility>

namespace xrcu
{

namespace detail
{

template <class T>
struct alignas (8) type_wrapper : public finalizable
{
  T value;

  type_wrapper (const T& val) : value (val)
    {
    }

  template <class ...Args>
  type_wrapper (Args&&... args) : value (std::forward<Args>(args)...)
    {
    }
};

template <bool Integral, class T>
struct wrapped_traits
{
  static const uintptr_t XBIT = (uintptr_t)1 << (sizeof (uintptr_t) * 8 - 1);
  static const uintptr_t FREE = (~(uintptr_t)0) & ~XBIT;
  static const uintptr_t DELT = FREE >> 1;
  typedef T value_type;

  static uintptr_t make (T val)
    {
      return ((uintptr_t)(typename std::make_unsigned<T>::type)val);
    }

  static T get (uintptr_t w)
    {
      return ((T)(w & ~XBIT));
    }

  static void destroy (uintptr_t) {}
  static void free (uintptr_t) {}
};

template <class T>
struct wrapped_traits<false, T>
{
  static const uintptr_t XBIT = 1;
  static const uintptr_t FREE = 2;
  static const uintptr_t DELT = 4;
  typedef T value_type;

  static uintptr_t make (const T& val)
    {
      return ((uintptr_t)(new type_wrapper<T> (val)));
    }

  template <class ...Args>
  static uintptr_t make (Args&&... args)
    {
      return ((uintptr_t)(new type_wrapper<T> (std::forward<Args>(args)...)));
    }

  static uintptr_t make (T&& val)
    {
      return ((uintptr_t)(new type_wrapper<T> (std::forward<T&&> (val))));
    }

  static T& get (uintptr_t addr)
    {
      return (((type_wrapper<T> *)(addr & ~XBIT))->value);
    }

  static void destroy (uintptr_t addr)
    {
      finalize ((type_wrapper<T> *)addr);
    }

  static void free (uintptr_t addr)
    {
      delete (type_wrapper<T> *)addr;
    }
};

} // namespace detail

} // namespace xrcu

#endif


code: const int MAJOR = 0; const int MINOR = 1;


code:
#ifndef __XRCU_XATOMIC_HPP__
#define __XRCU_XATOMIC_HPP__   1

#include <cstdint>

/*
 * This file defines an interface for atomic operations that isn't (quite)
 * achievable with the C++ standard atomic API. Basically, instead of using
 * a template class, we use raw pointers.
 *
 * This interface is needed because for some inexplicable reason, it is not
 * possible to get a pointer to the underlying integer in the std::atomic
 * interface (it may not even exist as such).
 *
 * While we are at it, we also define a few additional operations that are
 * not present in the standard (double CAS, atomic spin).
 *
 * Note that these aren't template functions; we only require these atomic
 * ops to work on pointer-sized values, so we don't bother with anything else.
 */

namespace xrcu
{

#if (defined (__GNUC__) && (__GNUC__ > 4 ||   \
    (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))) || (defined (__clang__) &&   \
    defined (__clang_major__) && (__clang_major__ >= 4 ||   \
      (__clang_major__ == 3 && __clang_minor__ >= 8)))

inline uintptr_t
xatomic_cas (uintptr_t *ptr, uintptr_t exp, uintptr_t nval)
{
  __atomic_compare_exchange_n (ptr, &exp, nval, 0,
    __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
  return (exp);
}

inline uintptr_t
xatomic_or (uintptr_t *ptr, uintptr_t val)
{
  return (__atomic_fetch_or (ptr, val, __ATOMIC_ACQ_REL));
}

inline void
xatomic_and (uintptr_t *ptr, uintptr_t val)
{
  (void)__atomic_and_fetch (ptr, val, __ATOMIC_ACQ_REL);
}

inline uintptr_t
xatomic_swap (uintptr_t *ptr, uintptr_t val)
{
  return (__atomic_exchange_n (ptr, val, __ATOMIC_ACQ_REL));
}

inline uintptr_t
xatomic_add (uintptr_t *ptr, intptr_t val)
{
  return (__atomic_fetch_add (ptr, val, __ATOMIC_ACQ_REL));
}

#else

#include <atomic>

static_assert (sizeof (uintptr_t) == sizeof (std::atomic_uintptr_t) &&
  alignof (uintptr_t) == alignof (std::atomic_uintptr_t),
  "unsupported compiler (uintptr_t and atomic_uintptr_t mismatch)");

inline uintptr_t
xatomic_cas (uintptr_t *ptr, uintptr_t exp, uintptr_t nval)
{
  reinterpret_cast<std::atomic_uintptr_t&>(ptr).compare_exchange_weak
    (exp, nval, std::memory_order_acq_rel, std::memory_order_relaxed);
  return (exp);
}

inline uintptr_t
xatomic_swap (uintptr_t *ptr, uintptr_t val)
{
  return (reinterpret_cast<std::atomic_uintptr_t&>(ptr).exchange
    (ptr, val, std::memory_order_acq_rel));
}

inline uintptr_t
xatomic_add (uintptr_t *ptr, intptr_t val)
{
  return (reinterpret_cast<std::atomic_uintptr_t&>(ptr).fetch_add
    (ptr, val, std::memory_order_acq_rel));
}

inline uintptr_t
xatomic_or (uintptr_t *ptr, uintptr_t val)
{
  while (true)
    {
      uintptr_t ret = *ptr;
      if (xatomic_cas (ptr, ret, ret | val) == ret)
        return (ret);

      xatomic_spin_nop ();
    }
}

inline void
xatomic_and (uintptr_t *ptr, uintptr_t val)
{
  while (true)
    {
      uintptr_t ret = *ptr;
      if (xatomic_cas (ptr, ret, ret & val) == ret)
        return;

      xatomic_spin_nop ();
    }
}

#endif

#if defined (__GNUC__)

#  if defined (__i386__) || defined (__x86_64__)

inline void
xatomic_spin_nop ()
{
  __asm__ __volatile__ ("pause" : : : "memory");
}

#  elif defined (__aarch64__) || defined (__arm__)

inline void
xatomic_spin_nop ()
{
  __asm__ __volatile__ ("wfe" : : : "memory");
}

#  else

inline void
xatomic_spin_nop ()
{
  __atomic_thread_fence (__ATOMIC_ACQUIRE);
}

#  endif

#else

#include <atomic>

inline void
xatomic_spin_nop ()
{
  std::atomic_thread_fence (std::memory_order_acquire);
}

#endif

inline bool
xatomic_cas_bool (uintptr_t *ptr, uintptr_t exp, uintptr_t nval)
{
  return (xatomic_cas (ptr, exp, nval) == exp);
}

// Try to define double-width CAS.

#if defined (__GNUC__)

#  if defined (__amd64) || defined (__amd64__) ||   \
      defined (__x86_64) || defined (__x86_64__)

#    define XRCU_HAVE_XATOMIC_DCAS

#    if defined (_ILP32) || defined (__ILP32__)

inline bool
xatomic_dcas_bool (uintptr_t *ptr, uintptr_t elo,
  uintptr_t ehi, uintptr_t nlo, uintptr_t nhi)
{
  uint64_t exp = ((uint64_t)ehi << 32) | elo;
  uint64_t nval = ((uint64_t)nhi << 32) | nlo;
  return (__atomic_compare_exchange_n ((uint64_t *)ptr,
    &exp, nval, 0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED));
}

#    else

inline bool
xatomic_dcas_bool (uintptr_t *ptr, uintptr_t elo,
  uintptr_t ehi, uintptr_t nlo, uintptr_t nhi)
{
  char r;

  __asm__ __volatile__
    (
      "lock; cmpxchg16b %0\n\t"
      "setz %1"
      : "+m" (*ptr), "=q" (r)
      : "d" (ehi), "a" (elo),
        "c" (nhi), "b" (nlo)
      : "memory"
    );

  return ((bool)r);
}

#    endif   // ILP32

#  elif defined (__i386) || defined (__i386__)

#    define XRCU_HAVE_XATOMIC_DCAS

#    if defined (__PIC__) && __GNUC__ < 5

inline bool
xatomic_dcas_bool (uintptr_t *ptr, uintptr_t elo,
  uintptr_t ehi, uintptr_t nlo, uintptr_t nhi)
{
  uintptr_t s;
  char r;

  __asm__ __volatile__
    (
      "movl %%ebx, %2\n\t"
      "leal %0, %%edi\n\t"
      "movl %7, %%ebx\n\t"
      "lock; cmpxchg8b (%%edi)\n\t"
      "movl %2, %%ebx\n\t"
      "setz %1"
      : "=m" (*ptr), "=a" (r), "=m" (s)
      : "m" (*ptr), "d" (ehi), "a" (elo),
        "c" (nhi), "m" (nlo)
      : "%edi", "memory"
    );

  return ((bool)r);
}

#    else

inline bool
xatomic_dcas_bool (uintptr_t *ptr, uintptr_t elo,
  uintptr_t ehi, uintptr_t nlo, uintptr_t nhi)
{
  char r;
  __asm__ __volatile__
    (
      "lock; cmpxchg8b %0\n\t"
      "setz %1"
      : "+m" (*ptr), "=a" (r)
      : "d" (ehi), "a" (elo),
        "c" (nhi), "b" (nlo)
      : "memory"
    );

  return ((bool)r);
}

#    endif // PIC.

#  elif (defined (__arm__) || defined (__thumb__)) &&   \
       ((!defined (__thumb__) || (defined (__thumb2__) &&   \
         !defined (__ARM_ARCH_7__)) && !defined (__ARCH_ARM_7M__) &&   \
         !defined (__ARM_ARCH_7EM__)) && (!defined (__clang__) ||   \
        (__clang_major__ == 3 && __clang_minor__ >= 3)))

#    define XRCU_HAVE_XATOMIC_DCAS

inline bool
xatomic_dcas_bool (uintptr_t *ptr, uintptr_t elo,
  uintptr_t ehi, uintptr_t nlo, uintptr_t nhi)
{
  uint64_t qv = ((uint64_t)ehi << 32) | elo;
  uint64_t nv = ((uint64_t)nhi << 32) | nlo;

  while (true)
    {
      uint64_t tmp;
      __asm__ __volatile__
        (
          "ldrexd %0, %H0, [%1]"
          : "=&r" (tmp) : "r" (ptr)
        );

      if (tmp != qv)
        return (false);

      int r;
      __asm__ __volatile__
        (
          "strexd %0, %3, %H3, [%2]"
          : "=&r" (r), "+m" (*ptr)
          : "r" (ptr), "r" (nv)
          : "cc"
        );

      if (r == 0)
        return (true);
    }
}

#  elif defined (__aarch64__)

#    define XRCU_HAVE_XATOMIC_DCAS

inline bool
xatomic_dcas_bool (uintptr_t *ptr, uintptr_t elo,
  uintptr_t ehi, uintptr_t nlo, uintptr_t nhi)
{
  while (true)
    {
      uintptr_t t1, t2;
      __asm__ __volatile__
        (
          "ldaxp %0, %1, %2"
          : "=&r" (t1), "=&r" (t2)
          : "Q" (*ptr)
        );

      if (t1 != elo || t2 != ehi)
        return (false);

      int r;
      __asm__ __volatile__
        (
          "stxp %w0, %2, %3, %1"
          : "=&r" (r), "=Q" (*ptr)
          : "r" (nlo), "r" (nhi)
        );

      if (r == 0)
        return (true);
    }
}

#  endif

#endif

} // namespace xrcu

#endif


code:
#include "xrcu.hpp"
#include "xatomic.hpp"
#include "version.hpp"
#include <thread>
#include <mutex>
#include <atomic>
#include <chrono>
#include <cstdint>
#include <ctime>
#include <functional>

namespace xrcu
{

struct td_link
{
  td_link *next;
  td_link *prev;

  void init_head ()
    {
      this->next = this->prev = this;
    }

  void add (td_link *headp)
    { // Add self to HEADP.
      this->next = headp->next;
      this->prev = headp;
      headp->next->prev = this;
      headp->next = this;
    }

  void del ()
    { // Unlink self.
      this->next->prev = this->prev;
      this->prev->next = this->next;
    }

  bool empty_p () const
    {
      return (this == this->next);
    }

  bool linked_p () const
    {
      return (this->next != nullptr);
    }

  void splice (td_link *dst)
    {
      if (this->empty_p ())
        return;

      this->next->prev = dst;
      this->prev->next = dst->next;
      dst->next->prev = this->prev;
      dst->next = this->next;
    }
};

static const uintptr_t GP_PHASE_BIT =
  (uintptr_t)1 << (sizeof (uintptr_t) * 8 - 1);

static const uintptr_t GP_NEST_MASK = GP_PHASE_BIT - 1;

// Possible states for a reader thread.
enum
{
  rd_active,
  rd_inactive,
  rd_old
};

struct registry
{
  std::atomic_uintptr_t counter;
  td_link root;
  std::mutex td_mtx;
  std::mutex gp_mtx;

  static const unsigned int QS_ATTEMPTS = 1000;

  registry () : counter (1)
    {
      this->root.init_head ();
    }

  void add_tdata (td_link *lp)
    {
      this->td_mtx.lock ();
      lp->add (&this->root);
      this->td_mtx.unlock ();
    }

  uintptr_t get_ctr () const
    {
      return (this->counter.load (std::memory_order_relaxed));
    }

  void poll_readers (td_link *, td_link *, td_link *);

  void sync ();
};

static registry global_reg;

// Maximum number of pending finalizers before flushing.
#ifndef XRCU_MAX_FINS
#  define XRCU_MAX_FINS   1000
#endif

static const unsigned int MAX_FINS = XRCU_MAX_FINS;

struct tl_data : public td_link
{
  bool must_flush;
  unsigned int n_fins;
  std::atomic_uintptr_t counter;
  size_t xrand_val;
  finalizable *fin_objs;

  uintptr_t get_ctr () const
    {
      return (this->counter.load (std::memory_order_relaxed));
    }

  int state () const
    {
      auto val = this->counter.load (std::memory_order_acquire);
      if (!(val & GP_NEST_MASK))
        return (rd_inactive);
      else if (!((val ^ global_reg.get_ctr ()) & GP_PHASE_BIT))
        return (rd_active);
      else
        return (rd_old);
    }

  bool in_cs () const
    {
      return ((this->get_ctr () & GP_NEST_MASK) != 0);
    }

  bool flush_all ()
    {
      if (!sync ())
        return (false);

      for (auto f = this->fin_objs; f != nullptr; )
        {
          auto next = f->_Fin_next;
          f->safe_destroy ();
          f = next;
        }

      this->fin_objs = nullptr;
      this->n_fins = 0;
      this->must_flush = false;
      return (true);
    }

  void finalize (finalizable *finp)
    {
      finp->_Fin_next = this->fin_objs;
      this->fin_objs = finp;

      if (++this->n_fins < MAX_FINS)
        ;
      else if (!this->flush_all ())
        /* Couldn't reclaim memory since we are in a critical section.
         * Set the flag to do it ASAP. */
        this->must_flush = true;
    }

  ~tl_data ()
    {
      if (!this->linked_p ())
        return;

      this->counter.store (0, std::memory_order_release);

      if (this->n_fins > 0)
        this->flush_all ();

      global_reg.td_mtx.lock ();
      this->del ();
      global_reg.td_mtx.unlock ();
    }
};

static thread_local tl_data tldata {};

static inline tl_data*
local_data ()
{
  auto self = &tldata;
  if (!self->linked_p ())
    global_reg.add_tdata (self);

  return (self);
}

void enter_cs ()
{
  auto self = local_data ();
  auto val = self->get_ctr ();
  val = (val & GP_NEST_MASK) == 0 ? global_reg.get_ctr () : val + 1;
  self->counter.store (val, std::memory_order_release);
}

void exit_cs ()
{
  auto self = local_data ();
  auto val = self->get_ctr ();
  self->counter.store (val - 1, std::memory_order_release);

  if (self->must_flush && !self->in_cs ())
    self->flush_all ();
}

bool in_cs ()
{
  auto self = &tldata;
  return (self->linked_p () && self->in_cs ());
}

void registry::poll_readers (td_link *readers, td_link *outp, td_link *qsp)
{
  for (unsigned int loops = 0 ; ; ++loops)
    {
      td_link *next, *runp = readers->next;
      for (; runp != readers; runp = next)
        {
          next = runp->next;
          switch (((tl_data *)runp)->state ())
            {
              case rd_active:
                if (outp != nullptr)
                  {
                    runp->del ();
                    runp->add (outp);
                    break;
                  }

              // Fallthrough.
              case rd_inactive:
                runp->del ();
                runp->add (qsp);
                break;

              default:
                break;
            }
        }

      if (readers->empty_p ())
        break;

      this->td_mtx.unlock ();
      if (loops < QS_ATTEMPTS)
        xatomic_spin_nop ();
      else
        std::this_thread::sleep_for (std::chrono::milliseconds (1));
      this->td_mtx.lock ();
    }
}

void registry::sync ()
{
  this->gp_mtx.lock ();
  this->td_mtx.lock ();

  if (this->root.empty_p ())
    {
      this->td_mtx.unlock ();
      this->gp_mtx.unlock ();
      return;
    }

  td_link out, qs;
  qs.init_head ();
  out.init_head ();

  std::atomic_thread_fence (std::memory_order_acq_rel);
  poll_readers (&this->root, &out, &qs);

  this->counter.store (this->get_ctr () ^ GP_PHASE_BIT,
                       std::memory_order_relaxed);

  poll_readers (&out, nullptr, &qs);
  qs.splice (&this->root);
  this->td_mtx.unlock ();
  this->gp_mtx.unlock ();
}

bool sync ()
{
  if (in_cs ())
    return (false);

  global_reg.sync ();
  return (true);
}

void finalize (finalizable *finp)
{
  if (finp)
    local_data()->finalize (finp);
}

bool flush_finalizers ()
{
  auto tld = local_data ();
  bool ret = tld->flush_all ();

  if (!ret)
    tld->must_flush = true;

  return (ret);
}

unsigned int xrand ()
{
  auto self = &tldata;   // Avoid local_data ()
  if (!self->xrand_val)
    self->xrand_val = (unsigned int)(time (nullptr) ^
      std::hash<std::thread::id>() (std::this_thread::get_id ()));

  self->xrand_val = self->xrand_val * 1103515245 + 12345;
  return (self->xrand_val >> 16);
}

static void
atfork_prepare ()
{
  global_reg.td_mtx.lock ();
}

static void
atfork_parent ()
{
  global_reg.td_mtx.unlock ();
}

static void
atfork_child ()
{
  atfork_parent ();
  // Reset the registry
  global_reg.root.init_head ();

  auto self = &tldata;
  if (!self->linked_p ())
    return;

  // Manually add ourselves to the registry without locking.
  self->add (&global_reg.root);
}

atfork atfork_data ()
{
  atfork ret;
  ret.prepare = atfork_prepare;
  ret.parent = atfork_parent;
  ret.child = atfork_child;
  return (ret);
}

void library_version (int& major, int& minor)
{
  major = MAJOR, minor = MINOR;
}

} // namespace rcu


code:
#ifndef __XRCU_HPP__
#define __XRCU_HPP__   1

namespace xrcu
{

// Enter a read-side critical section.
extern void enter_cs ();

// Exit a read-side critical section.
extern void exit_cs ();

// Test if the calling thread is in a read-side critical section.
extern bool in_cs ();

/* Wait until all readers have entered a quiescent state.
 * Returns false if a deadlock is detected, true otherwise. */
extern bool sync ();

// Base type for finalizable objects.
struct finalizable
{
  finalizable *_Fin_next = nullptr;

  virtual void safe_destroy ()
    {
      delete this;
    }

  virtual ~finalizable () {}
};

// Add FINP to the list of objects to be finalized after a grace period.
extern void finalize (finalizable *finp);

/* Force destruction of pending finalizable objects.
 * Returns true if they were destroyed. */
extern bool flush_finalizers ();

struct cs_guard
{
  cs_guard ()
    {
      enter_cs ();
    }

  ~cs_guard ()
    {
      exit_cs ();
    }
};

// Miscellaneous functions that don't belong anywhere else.
struct atfork
{
  void (*prepare) (void);
  void (*parent) (void);
  void (*child) (void);
};

// Fetch the `pthread_atfork' callbacks for XRCU.
extern atfork atfork_data ();

// Count the number of trailing zeroes.

#ifdef __GNUC__

inline unsigned int
ctz (unsigned int val)
{
  return (__builtin_ctz (val));
}

#else

unsigned int ctz (unsigned int val)
{
  unsigned int ret = 0;

  val &= ~val + 1;   // Isolate the LSB.
  ret += !!(val & 0xaaaaaaaau) << 0;
  ret += !!(val & 0xccccccccu) << 1;
  ret += !!(val & 0xf0f0f0f0u) << 2;
  ret += !!(val & 0xff00ff00u) << 3;
  ret += !!(val & 0xffff0000u) << 4;

  return (ret);
}

#endif

// Generate a pseudo-random number (thread-safe).
extern unsigned int xrand ();

// Get the library version.
extern void library_version (int& major, int& minor);

} // namespace xrcu

#endif


code:
;; Per-directory local variables for GNU Emacs 23 and later.

((nil
  . ((fill-column . 78)
     (tab-width   .  8)
     (sentence-end-double-space . t)

     ;; For use with 'bug-reference-prog-mode'.
     (bug-reference-url-format . "http://bugs.gnu.org/%s")
     (bug-reference-bug-regexp
      . "<https?://\\(debbugs\\|bugs\\)\\.gnu\\.org/\\([0-9]+\\)>")))
 (c-mode          . ((c-file-style . "gnu")))
 (scheme-mode
  .
  ((indent-tabs-mode . nil)
   (eval . (put 'eval-when 'scheme-indent-function 1))
   (eval . (put 'call-with-prompt 'scheme-indent-function 1))
   (eval . (put 'test-assert 'scheme-indent-function 1))
   (eval . (put 'test-assertm 'scheme-indent-function 1))
   (eval . (put 'test-equalm 'scheme-indent-function 1))
   (eval . (put 'test-equal 'scheme-indent-function 1))
   (eval . (put 'test-eq 'scheme-indent-function 1))
   (eval . (put 'call-with-input-string 'scheme-indent-function 1))
   (eval . (put 'guard 'scheme-indent-function 1))
   (eval . (put 'lambda* 'scheme-indent-function 1))
   (eval . (put 'substitute* 'scheme-indent-function 1))
   (eval . (put 'match-record 'scheme-indent-function 2))

   ;; 'modify-phases' and its keywords.
   (eval . (put 'modify-phases 'scheme-indent-function 1))
   (eval . (put 'replace 'scheme-indent-function 1))
   (eval . (put 'add-before 'scheme-indent-function 2))
   (eval . (put 'add-after 'scheme-indent-function 2))

   (eval . (put 'modify-services 'scheme-indent-function 1))
   (eval . (put 'with-directory-excursion 'scheme-indent-function 1))
   (eval . (put 'with-file-lock 'scheme-indent-function 1))
   (eval . (put 'with-file-lock/no-wait 'scheme-indent-function 1))
   (eval . (put 'with-profile-lock 'scheme-indent-function 1))
   (eval . (put 'with-writable-file 'scheme-indent-function 2))

   (eval . (put 'package 'scheme-indent-function 0))
   (eval . (put 'package/inherit 'scheme-indent-function 1))
   (eval . (put 'origin 'scheme-indent-function 0))
   (eval . (put 'build-system 'scheme-indent-function 0))
   (eval . (put 'bag 'scheme-indent-function 0))
   (eval . (put 'graft 'scheme-indent-function 0))
   (eval . (put 'operating-system 'scheme-indent-function 0))
   (eval . (put 'file-system 'scheme-indent-function 0))
   (eval . (put 'manifest-entry 'scheme-indent-function 0))
   (eval . (put 'manifest-pattern 'scheme-indent-function 0))
   (eval . (put 'substitute-keyword-arguments 'scheme-indent-function 1))
   (eval . (put 'with-store 'scheme-indent-function 1))
   (eval . (put 'with-external-store 'scheme-indent-function 1))
   (eval . (put 'with-error-handling 'scheme-indent-function 0))
   (eval . (put 'with-mutex 'scheme-indent-function 1))
   (eval . (put 'with-atomic-file-output 'scheme-indent-function 1))
   (eval . (put 'call-with-compressed-output-port 'scheme-indent-function 2))
   (eval . (put 'call-with-decompressed-port 'scheme-indent-function 2))
   (eval . (put 'call-with-gzip-input-port 'scheme-indent-function 1))
   (eval . (put 'call-with-gzip-output-port 'scheme-indent-function 1))
   (eval . (put 'call-with-lzip-input-port 'scheme-indent-function 1))
   (eval . (put 'call-with-lzip-output-port 'scheme-indent-function 1))
   (eval . (put 'signature-case 'scheme-indent-function 1))
   (eval . (put 'emacs-batch-eval 'scheme-indent-function 0))
   (eval . (put 'emacs-batch-edit-file 'scheme-indent-function 1))
   (eval . (put 'emacs-substitute-sexps 'scheme-indent-function 1))
   (eval . (put 'emacs-substitute-variables 'scheme-indent-function 1))
   (eval . (put 'with-derivation-narinfo 'scheme-indent-function 1))
   (eval . (put 'with-derivation-substitute 'scheme-indent-function 2))
   (eval . (put 'with-status-report 'scheme-indent-function 1))
   (eval . (put 'with-status-verbosity 'scheme-indent-function 1))
   (eval . (put 'with-build-handler 'scheme-indent-function 1))

   (eval . (put 'mlambda 'scheme-indent-function 1))
   (eval . (put 'mlambdaq 'scheme-indent-function 1))
   (eval . (put 'syntax-parameterize 'scheme-indent-function 1))
   (eval . (put 'with-monad 'scheme-indent-function 1))
   (eval . (put 'mbegin 'scheme-indent-function 1))
   (eval . (put 'mwhen 'scheme-indent-function 1))
   (eval . (put 'munless 'scheme-indent-function 1))
   (eval . (put 'mlet* 'scheme-indent-function 2))
   (eval . (put 'mlet 'scheme-indent-function 2))
   (eval . (put 'run-with-store 'scheme-indent-function 1))
   (eval . (put 'run-with-state 'scheme-indent-function 1))
   (eval . (put 'wrap-program 'scheme-indent-function 1))
   (eval . (put 'with-imported-modules 'scheme-indent-function 1))
   (eval . (put 'with-extensions 'scheme-indent-function 1))
   (eval . (put 'with-parameters 'scheme-indent-function 1))
   (eval . (put 'let-system 'scheme-indent-function 1))

   (eval . (put 'with-database 'scheme-indent-function 2))
   (eval . (put 'call-with-transaction 'scheme-indent-function 1))
   (eval . (put 'with-statement 'scheme-indent-function 3))
   (eval . (put 'call-with-retrying-transaction 'scheme-indent-function 1))
   (eval . (put 'call-with-savepoint 'scheme-indent-function 1))
   (eval . (put 'call-with-retrying-savepoint 'scheme-indent-function 1))

   (eval . (put 'call-with-container 'scheme-indent-function 1))
   (eval . (put 'container-excursion 'scheme-indent-function 1))
   (eval . (put 'eventually 'scheme-indent-function 1))

   (eval . (put 'call-with-progress-reporter 'scheme-indent-function 1))
   (eval . (put 'with-repository 'scheme-indent-function 2))
   (eval . (put 'with-temporary-git-repository 'scheme-indent-function 2))
   (eval . (put 'with-environment-variables 'scheme-indent-function 1))
   (eval . (put 'with-fresh-gnupg-setup 'scheme-indent-function 1))

   (eval . (put 'with-paginated-output-port 'scheme-indent-function 1))

   ;; This notably allows '(' in Paredit to not insert a space when the
   ;; preceding symbol is one of these.
   (eval . (modify-syntax-entry ?~ "'"))
   (eval . (modify-syntax-entry ?$ "'"))
   (eval . (modify-syntax-entry ?+ "'"))))
 (emacs-lisp-mode . ((indent-tabs-mode . nil)))
 (texinfo-mode    . ((indent-tabs-mode . nil)
                     (fill-column . 72))))


code:
*.eps
*.go
*.log
*.pdf
*.png
*.tar.xz
*.tmp
*~
.#*
\#*\#
,*
/ABOUT-NLS
/INSTALL
/aclocal.m4
/autom4te.cache
/build-aux/ar-lib
/build-aux/compile
/build-aux/config.guess
/build-aux/config.rpath
/build-aux/config.sub
/build-aux/depcomp
/build-aux/install-sh
/build-aux/mdate-sh
/build-aux/missing
/build-aux/test-driver
/build-aux/texinfo.tex
/config.status
/configure
/doc/*.1
/doc/.dirstamp
/doc/contributing.*.texi
/doc/guix*.aux
/doc/guix*.cp
/doc/guix*.cps
/doc/guix*.fn
/doc/guix*.fns
/doc/guix*.html
/doc/guix*.info
/doc/guix*.info-[0-9]
/doc/guix*.ky
/doc/guix*.pg
/doc/guix*.toc
/doc/guix*.t2p
/doc/guix*.tp
/doc/guix*.vr
/doc/guix*.vrs
/doc/guix.*.texi
/doc/guix-cookbook.*.texi
/doc/guix.aux
/doc/guix.cp
/doc/guix.cps
/doc/guix.fn
/doc/guix.fns
/doc/guix.html
/doc/guix.info
/doc/guix.info-[0-9]
/doc/guix.ky
/doc/guix.pg
/doc/guix.toc
/doc/guix.t2p
/doc/guix.tp
/doc/guix.vr
/doc/guix.vrs
/doc/os-config-bare-bones.texi
/doc/os-config-desktop.texi
/doc/stamp-vti
/doc/version.texi
/doc/version-*.texi
/etc/committer.scm
/etc/gnu-store.mount
/etc/guix-daemon.cil
/etc/guix-daemon.conf
/etc/guix-daemon.service
/etc/guix-publish.conf
/etc/guix-publish.service
/etc/init.d/guix-daemon
/guix-daemon
/guix/config.scm
/libformat.a
/libstore.a
/libutil.a
/m4/*
/m4/ChangeLog
/m4/gettext.m4
/m4/iconv.m4
/m4/lib-ld.m4
/m4/lib-link.m4
/m4/lib-prefix.m4
/m4/nls.m4
/m4/po.m4
/m4/progtest.m4
/nix/config.h
/nix/config.h.in
/po/doc/*.mo
/po/guix/*.gmo
/po/guix/*.insert-header
/po/guix/*.mo
/po/guix/ChangeLog
/po/guix/Makefile.in.in
/po/guix/Makevars.template
/po/guix/POTFILES
/po/guix/Rules-quot
/po/guix/boldquot.sed
/po/guix/en@boldquot.*
/po/guix/en@quot.*
/po/guix/guix.pot
/po/guix/insert-header.sin
/po/guix/quot.sed
/po/guix/remove-potcdate.sed
/po/guix/remove-potcdate.sin
/po/guix/stamp-po
/po/packages/*.gmo
/po/packages/*.insert-header
/po/packages/*.mo
/po/packages/ChangeLog
/po/packages/Makefile.in.in
/po/packages/Makevars.template
/po/packages/POTFILES
/po/packages/Rules-quot
/po/packages/boldquot.sed
/po/packages/en@boldquot.*
/po/packages/en@quot.*
/po/packages/guix-packages.pot
/po/packages/insert-header.sin
/po/packages/quot.sed
/po/packages/remove-potcdate.sed
/po/packages/remove-potcdate.sin
/po/packages/stamp-po
/pre-inst-env
/scripts/guix
/test-env
/test-tmp
/tests/*.trs
/tests/services/*.trs
GPATH
GRTAGS
GTAGS
Makefile
Makefile.in
config.cache
stamp-h[0-9]
tmp
/doc/os-config-lightweight-desktop.texi
/nix/scripts/download
/.version
/doc/stamp-[0-9]
/gnu/packages/bootstrap

path: .gitignore


code:
;; This is a Guix channel.

(channel
  (version 0)
  (news-file "etc/news.scm")
  (keyring-reference "keyring")
  (url "https://git.savannah.gnu.org/git/guix.git")) ;the primary URL

path: .guix-channel


code:
# This list is used to avoid multiple name/email instances of the same
# contributors reported by "git log" and "git shortlog" commands.

Adriano Peluso <catonano@gmail.com>
Al McElrath <hello@yrns.org> <hello@atonesir.com>
Alex Sassmannshausen <alex@pompo.co> <alex.sassmannshausen@gmail.com>
Alexander I. Grafov <grafov@gmail.com>
Alírio Eyng <alirioeyng@gmail.com>
Amin Bandali <bandali@gnu.org> <mab@gnu.org>
Amirouche Boubekki <amirouche@hypermove.net>
Andreas Enge <andreas@enge.fr> <andreas.enge@inria.fr>
Andreas Enge <andreas@enge.fr> <privat@xobs-novena>
Andy Wingo <wingo@igalia.com> <wingo@pobox.com>
Ben Woodcroft <donttrustben@gmail.com>
Ben Woodcroft <donttrustben@gmail.com> <b.woodcroft@uq.edu.au>
Ben Woodcroft <donttrustben@gmail.com> <donttrustben near gmail.com>
Brett Gilio <brettg@gnu.org> <brettg@posteo.net>
Claes Wallin (韋嘉誠) <claes.wallin@greatsinodevelopment.com>
Cyprien Nicolas <cyprien@nicolas.tf> <c.nicolas+gitorious@gmail.com>
Daniel Pimentel <d4n1@d4n1.org> <d4n1@member.fsf.org>
Danny Milosavljevic <dannym@scratchpost.org> <dannym+a@scratchpost.org>
David Hashe <david.hashe@dhashe.com> <address@hidden>
David Thompson <davet@gnu.org> <dthompson2@worcester.edu>
David Thompson <davet@gnu.org> <dthompson@member.fsf.org>
David Thompson <davet@gnu.org> <dthompson@vistahigherlearning.com>
Deck Pickard <deck.r.pickard@gmail.com> <nebu@kipple>
Eric Bavier <bavier@member.fsf.org> <ericbavier@gmail.com>
Eric Bavier <bavier@member.fsf.org> <bavier@posteo.net>
Eric Dvorsak <eric@dvorsak.fr> <yenda1@gmail.com>
George Clemmer <myglc2@gmail.com>
ison <ison@airmail.cc> <ison111@protonmail.com>
Ivan Vilata i Balaguer <ivan@selidor.net>
Jakob L. Kreuze <zerodaysfordays@sdf.org> <zerodaysfordays@sdf.lonestar.org>
Jeff Mickey <j@codemac.net> <jm@igneous.io>
John Darrington <jmd@gnu.org> <john@darrington.wattle.id.au>
John J. Foerch <jjfoerch@earthlink.net>
Joshua Grant <tadni@riseup.net> <gzg@riseup.net>
Joshua Grant <tadni@riseup.net> <jgrant@parenthetical.io>
Joshua Grant <tadni@riseup.net> <tadnimi@gmail.com>
Joshua Grant <tadni@riseup.net> <youlysses@riseup.net>
Kei Kebreau <kei@openmailbox.org> <kkebreau@posteo.net>
Leo Famulari <leo@famulari.name> <lfamular@gmail.com>
Ludovic Courtès <ludo@gnu.org> <ludovic.courtes@inria.fr>
Marek Benc <dusxmt@gmx.com> <merkur32@gmail.com>
Marius Bakke <mbakke@fastmail.com> <m.bakke@warwick.ac.uk>
Mathieu Lirzin <mthl@gnu.org> <mthl@openmailbox.org>
Mathieu Lirzin <mthl@gnu.org> <mathieu.lirzin@openmailbox.org>
Mathieu Othacehe <m.othacehe@gmail.com>
Mathieu Othacehe <mathieu.othacehe@parrot.com>
Mathieu Othacehe <othacehe@gnu.org>
Nikita Karetnikov <nikita@karetnikov.org> <nikita.karetnikov@gmail.com>
nikita <nikita@n0.is>
nikita <nikita@n0.is> ng0 <ng0@n0.is>
nikita <nikita@n0.is> Nils Gillmann <ng0@n0.is>
nikita <nikita@n0.is> Nils Gillmann <gillmann@infotropique.org>
nikita <nikita@n0.is> ng0 <ng0@crash.cx>
nikita <nikita@n0.is> <ng0@infotropique.org>
nikita <nikita@n0.is> <ng0@no-reply.infotropique.org>
nikita <nikita@n0.is> <ng0@no-reply.pragmatique.xyz>
nikita <nikita@n0.is> <ng0@pragmatique.xyz>
nikita <nikita@n0.is> <contact.ng0@cryptolab.net>
nikita <nikita@n0.is> <ng0@we.make.ritual.n0.is>
nikita <nikita@n0.is> <ngillmann@runbox.com>
nikita <nikita@n0.is> <niasterisk@grrlz.net>
nikita <nikita@n0.is> <ng@niasterisk.space>
nikita <nikita@n0.is> <ng0@libertad.pw>
Pierre Neidhardt <mail@ambrevar.xyz>
Pierre-Antoine Rouby <pierre-antoine.rouby@inria.fr>
Pjotr Prins <pjotr.guix@thebird.nl> <pjotr.public01@thebird.nl>
Pjotr Prins <pjotr.guix@thebird.nl> <pjotr.public12@thebird.nl>
Pjotr Prins <pjotr.guix@thebird.nl> <pjotr.public12@email>
Raimon Grau <raimonster@gmail.com> <raimon@3scale.net>
Raoul Jean Pierre Bonnal <ilpuccio.febo@gmail.com>
Raymond Nicholson <rain1@openmailbox.org>
Rene Saavedra <rennes@openmailbox.org>
Ricardo Wurmus <rekado@elephly.net>
Ricardo Wurmus <rekado@elephly.net> <ricardo.wurmus@mdc-berlin.de>
Sou Bunnbu (宋文武) <iyzsong@gmail.com>
Sou Bunnbu (宋文武) <iyzsong@gmail.com> <iyzsong@member.fsf.org>
Stefan Reichör <stefan@xsteve.at>
Taylan Ulrich Bayırlı/Kammer <taylanbayirli@gmail.com>
Theodoros Foradis <theodoros.for@openmailbox.org> <theodoros@foradis.org>
Thomas Danckaert <thomas.danckaert@gmail.com> <post@thomasdanckaert.be>
Tobias Geerinckx-Rice <me@tobias.gr> <tobias.geerinckx.rice@gmail.com>
Tomáš Čech <sleep_walker@gnu.org> <sleep_walker@suse.cz>
Vincent Legoll <vincent.legoll@gmail.com> <vincent.legoll@idgrilles.fr>

path: .mailmap


code:
GNU Guix consists of Scheme code that implements the deployment model
of the Nix package management tool.  In fact, it currently talks to a
build daemon whose code comes from Nix (see the manual for details.)

Nix was initially written by Eelco Dolstra; other people have been
contributing to it.  See `nix/AUTHORS' for details.

The list of GNU Guix contributors is now generated from the output of
'git log' and written to this file, as can be seen in release tarballs.

path: AUTHORS


code:
Contributor Covenant Code of Conduct

  Note: In the sequel, "project" refers to GNU Guix, and "project
  maintainer(s)" refers to maintainer(s) of GNU Guix.

Our Pledge

In the interest of fostering an open and welcoming environment, we as
contributors and maintainers pledge to making participation in our project and
our community a harassment-free experience for everyone, regardless of age, body
size, disability, ethnicity, gender identity and expression, level of experience,
education, socio-economic status, nationality, personal appearance, race,
religion, or sexual identity and orientation.

Our Standards

Examples of behavior that contributes to creating a positive environment
include:

* Using welcoming and inclusive language
* Being respectful of differing viewpoints and experiences
* Gracefully accepting constructive criticism
* Focusing on what is best for the community
* Showing empathy towards other community members

Examples of unacceptable behavior by participants include:

* The use of sexualized language or imagery and unwelcome sexual attention or
advances
* Trolling, insulting/derogatory comments, and personal or political attacks
* Public or private harassment
* Publishing others’ private information, such as a physical or electronic
address, without explicit permission
* Other conduct which could reasonably be considered inappropriate in a
professional setting

Our Responsibilities

Project maintainers are responsible for clarifying the standards of acceptable
behavior and are expected to take appropriate and fair corrective action in
response to any instances of unacceptable behavior.

Project maintainers have the right and responsibility to remove, edit, or
reject comments, commits, code, wiki edits, issues, and other contributions
that are not aligned to this Code of Conduct, or to ban temporarily or
permanently any contributor for other behaviors that they deem inappropriate,
threatening, offensive, or harmful.

Scope

This Code of Conduct applies both within project spaces and in public spaces
when an individual is representing the project or its community. Examples of
representing a project or community include using an official project e-mail
address, posting via an official social media account, or acting as an appointed
representative at an online or offline event. Representation of a project may be
further defined and clarified by project maintainers.

Enforcement

Instances of abusive, harassing, or otherwise unacceptable behavior may be
reported by contacting the project team at guix-maintainers@gnu.org. All
complaints will be reviewed and investigated and will result in a response that
is deemed necessary and appropriate to the circumstances. The project team is
obligated to maintain confidentiality with regard to the reporter of an incident.
Further details of specific enforcement policies may be posted separately.

Project maintainers who do not follow or enforce the Code of Conduct in good
faith may face temporary or permanent repercussions as determined by other
members of the project’s leadership.

Attribution

This Code of Conduct is adapted from the Contributor Covenant, version 1.4,
available at https://www.contributor-covenant.org/version/1/4/code-of-conduct.html

path: CODE-OF-CONDUCT


code:
Normally a ChangeLog is generated at "make dist" time and available in
source tarballs.

If not, see the Git commit log at <http://git.sv.gnu.org/cgit/guix.git/>.

path: ChangeLog


code:
-*- mode: org; coding: utf-8; -*-

#+TITLE: Hacking GNU Guix and Its Incredible Distro

Copyright © 2012, 2013, 2014, 2016, 2017, 2019 Ludovic Courtès <ludo@gnu.org>
Copyright © 2015, 2017 Mathieu Lirzin <mthl@gnu.org>
Copyright © 2017 Leo Famulari <leo@famulari.name>
Copyright © 2017 Arun Isaac <arunisaac@systemreboot.net>

  Copying and distribution of this file, with or without modification,
  are permitted in any medium without royalty provided the copyright
  notice and this notice are preserved.

* Contributing

See the manual for useful hacking informations, either by running

  info -f doc/guix.info "Contributing"

or by checking the [[https://guix.gnu.org/manual/devel/en/html_node/Contributing.html][web copy of the manual]].

path: HACKING