123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712 |
- /* Declarations for the skip list template type.
- This file is part of xrcu.
- xrcu is free software: you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 3 of the License, or
- (at your option) any later version.
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with this program. If not, see <https://www.gnu.org/licenses/>. */
- #ifndef __SKIP_LIST_HPP__
- #define __SKIP_LIST_HPP__ 1
- #include "xrcu.hpp"
- #include "xatomic.hpp"
- #include "optional.hpp"
- #include "utils.hpp"
- #include <cstddef>
- #include <atomic>
- #include <functional>
- #include <initializer_list>
- namespace std
- {
- struct forward_iterator_tag;
- }
- namespace xrcu
- {
- namespace detail
- {
- struct sl_node_base;
- void sl_dealloc_node (void *base);
- sl_node_base* sl_alloc_node (unsigned int lvl, size_t size, uintptr_t **outpp);
- 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;
- struct sl_node_base : public finalizable
- {
- unsigned int nlvl;
- uintptr_t *next;
- sl_node_base (unsigned int lvl, uintptr_t *np) : nlvl (lvl), next (np)
- {
- }
- static sl_node_base* get (uintptr_t addr)
- {
- return ((sl_node_base *)(addr & ~SL_XBIT));
- }
- static uintptr_t& at (uintptr_t addr, unsigned int lvl)
- {
- return (sl_node_base::get(addr)->next[lvl]);
- }
- static uintptr_t* plen (uintptr_t addr)
- {
- return (sl_node_base::get(addr)->next - 1);
- }
- static void bump (uintptr_t *lenp, intptr_t off)
- {
- xatomic_add (lenp, off + off);
- }
- static sl_node_base* make_root (unsigned int depth)
- {
- uintptr_t *np;
- auto ret = sl_alloc_node (depth + 1, sizeof (sl_node_base), &np);
- return (new (ret) sl_node_base (depth, np + 1));
- }
- static unsigned int
- rand_lvl (std::atomic<size_t>& hw)
- {
- size_t lvl = ctz (xrand ()) * 2 / 3;
- if (lvl == 0)
- return (1);
- while (true)
- {
- auto prev = hw.load (std::memory_order_relaxed);
- if (lvl <= prev)
- return (lvl);
- else if (prev == SL_MAX_DEPTH ||
- hw.compare_exchange_weak (prev, prev + 1,
- std::memory_order_acq_rel, std::memory_order_relaxed))
- return (prev);
- xatomic_spin_nop ();
- }
- }
- void safe_destroy ()
- {
- sl_dealloc_node (this);
- }
- };
- template <class T>
- struct sl_node : public sl_node_base
- {
- T key;
- sl_node (unsigned int lvl, uintptr_t *np, const T& kv) :
- sl_node_base (lvl, np), key (kv)
- {
- }
- template <class ...Args>
- sl_node (unsigned int lvl, uintptr_t *np, Args... args) :
- sl_node_base (lvl, np), key (std::forward<Args&&>(args)...)
- {
- }
- 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);
- try
- {
- return (new (self) sl_node<T> (lvl, np, k));
- }
- 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);
- return (new (self) sl_node<T> (lvl, np, std::forward<Args&&>(args)...));
- }
- void safe_destroy ()
- {
- destroy<T> (&this->key);
- sl_dealloc_node (this);
- }
- };
- 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_base *> 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 skip_list<T, Cmp> _Self;
- typedef detail::sl_node<T> _Node;
- 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));
- }
- 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 (_Node::make_root (this->max_depth + 1),
- 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 = detail::sl_node_base::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;
- static const T& _Getk (uintptr_t addr)
- {
- return (((_Node *)_Node::get(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 = _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 = _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 = _Node::at (it, lvl);
- }
- else
- {
- uintptr_t qx = xatomic_cas (&_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 ? _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 = _Node::rand_lvl (this->hi_water);
- if (this->_Find_preds (n, key, detail::SL_UNLINK_ASSIST,
- preds, succs, &xroot) != 0)
- return (false);
- uintptr_t nv = (uintptr_t)_Node::copy (n, key);
- for (size_t lvl = 0; lvl < n; ++lvl)
- _Node::at(nv, lvl) = succs[lvl];
- uintptr_t pred = *preds;
- if (!xatomic_cas_bool (&_Node::at(pred, 0), *succs, nv))
- {
- _Node::get(nv)->safe_destroy ();
- return (this->_Insert (key));
- }
- for (size_t lvl = 1; lvl < n; ++lvl)
- while (true)
- {
- pred = preds[lvl];
- if (xatomic_cas_bool (&_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 = _Node::at (nv, ix)) == succs[ix])
- continue;
- else if (xatomic_cas (&_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 (_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);
- }
- _Node::bump (_Node::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);
- detail::sl_node_base *nodep = _Node::get (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);
- _Node::bump (_Node::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 (_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 (detail::sl_node_base *xroot)
- {
- for (uintptr_t run = (uintptr_t)xroot; run != 0; )
- {
- uintptr_t next = _Node::at (run, 0);
- if (Destroy)
- _Node::get(run)->safe_destroy ();
- else
- finalize (_Node::get (run));
- run = next;
- }
- }
- void _Lock_root ()
- {
- cs_guard g;
- while (true)
- {
- auto ptr = _Node::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 (_Node::plen ((uintptr_t)rh), ~(uintptr_t)1);
- xatomic_and (_Node::plen ((uintptr_t)lh), ~(uintptr_t)1);
- }
- void clear ()
- {
- auto xroot = _Node::make_root (this->max_depth);
- 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
|