intrusive_impl.hpp

Go to the documentation of this file.

/******************************************************************************
** Copyright © 2011 by J.M.McGuiness, coder@hussar.me.uk
**
** This library is free software; you can redistribute it and/or
** modify it under the terms of the GNU Lesser General Public
** License as published by the Free Software Foundation; either
** version 2.1 of the License, or (at your option) any later version.
**
** This library 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
** Lesser General Public License for more details.
**
** You should have received a copy of the GNU Lesser General Public
** License along with this library; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
 
namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE { namespace intrusive {
 
template<class V, class LkT>
inline bool
stack<V, LkT>::empty() const noexcept(true) {
// TODO  assert((!prefront_.next) || (prefront_.next.get()));
   return size_ctr==0;
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::size_type
stack<V, LkT>::size() const noexcept(true) {
   return size_ctr.get();
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::size_type
stack<V, LkT>::size_n() const noexcept(true) {
   size_type ret=0;
   for ([[maybe_unused]] auto const &i: *this) {
      ++ret;
   }
   return ret;
}
 
template<class V, class LkT>
inline
stack<V, LkT>::stack() noexcept(true)
: prefront_(), size_ctr() {
   // Make sure iterators to begin() don't accidentally attempt to delete prefront_! Don't need to be atomic about this.
   prefront_.sp_acquire();
   assert(prefront_.next.get()==nullptr || prefront_.next->sp_count());
}
 
template<class V, class LkT>
inline
stack<V, LkT>::stack(stack &&s) noexcept(true)
: prefront_(), size_ctr() {
   prefront_.next.swap(s.prefront_.next);
   size_ctr.swap(s.size_ctr);
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::value_type
stack<V, LkT>::top() noexcept(true) {
   assert(prefront_.next.get()==nullptr || prefront_.next->sp_count());
   assert(prefront_.next->sp_count()>0);
   return value_type(prefront_.next.get());
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::value_type
stack<V, LkT>::top() const noexcept(true) {
   assert(prefront_.next.get()==nullptr || prefront_.next->sp_count());
   assert(prefront_.next->sp_count()>0);
   return value_type(prefront_.next.get());
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::iterator
stack<V, LkT>::begin() noexcept(true) {
   return iterator(typename iterator::value_type(dynamic_cast<typename iterator::node_ptr_t::value_type *>(&prefront_)));
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::const_iterator
stack<V, LkT>::begin() const noexcept(true) {
   return const_iterator(typename const_iterator::value_type(dynamic_cast<typename iterator::node_ptr_t::value_type *>(&prefront_)));
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::iterator
stack<V, LkT>::end() noexcept(true) {
   return private_::end<V, LkT>();
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::const_iterator
stack<V, LkT>::end() const noexcept(true) {
   return private_::end<V const, LkT>();
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::node_details_t::base_t::atomic_ptr_t
stack<V, LkT>::unlink_node(typename node_details_t::base_t::atomic_ptr_t &node) noexcept(true) {
   using ptr_t=typename node_details_t::base_t::atomic_ptr_t;
// TODO  return node.assign([](ptr_t const &ptr) {return ptr.get() ? ptr->next : ptr;});
   return node.assign([](ptr_t const &ptr) {return ptr->next;});
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::pop() noexcept(true) {
   if (!this->empty()) {
      --this->size_ctr;
      {
         // Unlink the node to be deleted first, to ensure only one thread at a time reduces the reference count.
         value_type retain_next(prefront_.next.get());
         assert(retain_next->sp_count()>=1);
         value_type unlinked_node(unlink_node(prefront_.next).get());
         // Remove the list ownership and function ownership.
         unlinked_node->sp_release();
         assert(unlinked_node->sp_count()>=1);
      }
      assert(prefront_.next.get()==nullptr || prefront_.next->sp_count()>=1);
   }
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::erase(iterator v) noexcept(true) {
   if (!this->empty()) {
      if (v==this->begin()) {
         this->pop();
      } else if (v!=this->end()) {
         --size_ctr;
         value_type del(*v);
         assert(del->sp_count()>0);
         unlink_node(v.node->next);
         del->sp_release();
         assert(del->sp_count()>0);
      }
   }
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::size_type
stack<V, LkT>::erase(const_reference v) noexcept(true) {
   iterator start=begin();
   while (start!=end() && *start!=v) {
      ++start;
   }
   if (start!=end()) {
      erase(start);
      return 1;
   } else {
      return 0;
   }
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::pop_front() noexcept(true) {
   this->pop();
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::clear() noexcept(true) {
   while (!this->empty()) {
      this->erase(this->begin());
   }
   assert(this->empty());
}
 
template<class V, class LkT>
inline
stack<V, LkT>::~stack() noexcept(true) {
   this->clear();
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::insert(typename node_details_t::base_t::atomic_ptr_t i, value_type v) noexcept(true) {
   assert(v->sp_count()>=0);
   // Acquire a reference count for the list, which will now own it also.
   v->sp_acquire();
   assert(v->sp_count()>=1);
   assert(dynamic_cast<typename node_details_t::base_t::atomic_ptr_t::value_type>(i.get()));
   typename node_details_t::base_t::atomic_ptr_t expected;
   do {
      // Linking v->next to the tail does not need to be atomic, because no-one else should be mucking around with v->next, otherwise the slist is broken.
      assert(static_cast<bool>(i));
      expected=i->next;
      assert(dynamic_cast<typename node_details_t::base_t::atomic_ptr_t::value_type>(v.get().get()));
      v->next=expected;
   } while (!i->next.compare_exchange_strong(expected.get(), v.get().get()));
   assert(i->next->sp_count()>=1);
   assert(v->sp_count()>=1);
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::insert(value_type v) noexcept(true) {
   assert(v->sp_count()>=1);
   // Acquire a reference count for the list, which will now own it also.
   v->sp_acquire();
   assert(v->sp_count()>=1);
   typename node_details_t::base_t::atomic_ptr_t expected;
   do {
      // Linking v->next to the tail does not need to be atomic, because no-one else should be mucking around with v->next, otherwise the slist is broken.
      expected=prefront_.next;
      assert(dynamic_cast<typename node_details_t::base_t::atomic_ptr_t::value_type>(v.get().get()));
      v->next=expected;
   } while (!prefront_.next.compare_exchange_strong(expected.get(), v.get().get()));
   assert(dynamic_cast<typename node_details_t::base_t::atomic_ptr_t::value_type>(prefront_.next.get()));
   assert(prefront_.next->sp_count()>=1);
   assert(v->sp_count()>=1);
   ++size_ctr;
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::push(value_type const &v) noexcept(true) {
   this->insert(v);
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::push(value_type &&v) noexcept(true) {
   this->insert(v);
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::push_front(value_type const &v) noexcept(true) {
   this->push(std::move(v));
}
 
template<class V, class LkT>
inline void
stack<V, LkT>::push_front(value_type &&v) noexcept(true) {
   this->push(std::forward<value_type>(v));
}
 
template<class V, class LkT>
inline typename stack<V, LkT>::value_type
stack<V, LkT>::pop_top_nochk() noexcept(true) {
   assert(!empty());
   --this->size_ctr;
   // Unlink the node to be deleted first, to ensure only one thread at a time reduces the reference count.
   value_type ret(unlink_node(prefront_.next).get());
   // Remove the list ownership and function ownership.
   assert(ret->sp_count()>=1);
   ret->sp_release();
   return ret;
}
 
template<class V, class LkT>
inline
slist<V, LkT>::slist() noexcept(true)
: base_t(), penultimate_() {
}
 
template<class V, class LkT>
inline
slist<V, LkT>::slist(slist &&s) noexcept(true)
: base_t(), penultimate_() {
   s.prefront_.sp_acquire();
   this->prefront_.swap(s.prefront_);
   this->prefront_.sp_release();
   penultimate_.swap(s.penultimate_);
   this->size_ctr.swap(s.size_ctr);
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::value_type
slist<V, LkT>::front() noexcept(true) {
   return this->top();
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::value_type
slist<V, LkT>::front() const noexcept(true) {
   return this->top();
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::iterator
slist<V, LkT>::find(const_reference v) noexcept(true) {
   if (!this->empty()) {
      return std::find(this->begin(), this->end(), v);
   } else {
      return this->end();
   }
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::const_iterator
slist<V, LkT>::find(const_reference v) const noexcept(true) {
   if (!this->empty()) {
      return std::find(this->begin(), this->end(), v);
   } else {
      return this->end();
   }
}
 
template<class V, class LkT>
inline void
slist<V, LkT>::pop_front() noexcept(true) {
   base_t::pop_front();
   if (!this->prefront_.next.get()) {
      penultimate_=typename node_details_t::base_t::atomic_ptr_t();
   }
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::size_type
slist<V, LkT>::erase(const_reference v) noexcept(true) {
   size_type num_erased=0;
   iterator iter_to_erase(this->begin());
   while ((iter_to_erase=std::find(iter_to_erase, this->end(), v))!=this->end()) {
      this->erase(iter_to_erase++);
      ++num_erased;
   }
   return num_erased;
}
 
template<class V, class LkT>
inline
slist<V, LkT>::~slist() noexcept(true) {
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::value_type
slist<V, LkT>::back() noexcept(true) {
   assert(penultimate_->next->sp_count()>0);
   return value_type(static_cast<typename value_type::value_type *>(penultimate_->next));
}
 
template<class V, class LkT>
inline typename slist<V, LkT>::value_type
slist<V, LkT>::back() const noexcept(true) {
   assert(penultimate_->next->sp_count()>0);
   return value_type(static_cast<typename value_type::value_type const *>(penultimate_->next));
}
 
template<class V, class LkT>
inline void
slist<V, LkT>::push_front(value_type const &v) noexcept(true) {
   typename node_details_t::base_t::atomic_ptr_t const was_empty=this->prefront_.next;
   this->insert(typename node_details_t::base_t::atomic_ptr_t(&this->prefront_), v);
   if (!was_empty.get()) {
      penultimate_=&this->prefront_;
   } else if (!v->next->next) {
      penultimate_=v.get().get();
   }
   ++this->size_ctr;
}
 
template<class V, class LkT>
inline void
slist<V, LkT>::push_front(value_type &&v) noexcept(true) {
   typename node_details_t::base_t::atomic_ptr_t const was_empty=this->prefront_.next;
   this->insert(typename node_details_t::base_t::atomic_ptr_t(&this->prefront_), v);
   if (!was_empty.get()) {
      penultimate_=&this->prefront_;
   } else if (!v->next->next) {
      penultimate_=v.get();
   }
   ++this->size_ctr;
}
 
template<class V, class LkT>
inline void
slist<V, LkT>::move_penultimate(typename node_details_t::base_t::atomic_ptr_t &node) noexcept(true) {
   using ptr_t=typename node_details_t::base_t::atomic_ptr_t;
   assert(dynamic_cast<typename node_details_t::base_t::atomic_ptr_t::value_type>(node->next.get()));
   node.assign([&node](ptr_t const &) {return node->next;});
   assert(dynamic_cast<typename node_details_t::base_t::atomic_ptr_t::value_type>(node->next.get()));
}
 
template<class V, class LkT>
inline void
slist<V, LkT>::push_back(value_type const &v) noexcept(true) {
   if (!this->empty()) {
      // Note how penultimate_ is the penultimate member of the slist, not the last, which allows us to do this in constant time.
      this->insert(penultimate_->next, v);
      move_penultimate(penultimate_);
      ++this->size_ctr;
   } else {
      push_front(v);
   }
}
 
template<class V, class LkT>
inline void
slist<V, LkT>::push_back(value_type &&v) noexcept(true) {
   if (!this->empty()) {
      // Note how penultimate_ is the penultimate member of the slist, not the last, which allows us to do this in constant time.
      this->insert(penultimate_->next, v);
      move_penultimate(penultimate_);
      ++this->size_ctr;
   } else {
      push_front(std::forward<value_type>(v));
   }
}
 
template<class V, class LkT>
inline bool
slist<V, LkT>::penultimate_reachable_from_prefront() const noexcept(true) {
   bool ret=this->empty();
   for (const_iterator i(this->begin()); i!=this->end(); ++i) {
      if (i.real_node.get()==penultimate_->next) {
         ret=true;
         break;
      }
   }
   return ret;
}
 
} } }