From 7772ea4579a45bcf63ebd5e68be66ba1a9c72dfa Mon Sep 17 00:00:00 2001 From: Clyne Sullivan Date: Fri, 11 Nov 2016 15:02:17 -0500 Subject: chibios! --- include/estd/ContiguousRange.hpp | 164 ---- include/estd/IntegerSequence.hpp | 229 ----- include/estd/IntrusiveForwardList.hpp | 1120 ------------------------- include/estd/IntrusiveList.hpp | 1208 --------------------------- include/estd/ReferenceHolder.hpp | 61 -- include/estd/ReverseAdaptor.hpp | 83 -- include/estd/SortedIntrusiveForwardList.hpp | 355 -------- include/estd/SortedIntrusiveList.hpp | 353 -------- include/estd/TypeErasedFunctor.hpp | 99 --- include/estd/apply.hpp | 73 -- include/estd/invoke.hpp | 147 ---- 11 files changed, 3892 deletions(-) delete mode 100644 include/estd/ContiguousRange.hpp delete mode 100644 include/estd/IntegerSequence.hpp delete mode 100644 include/estd/IntrusiveForwardList.hpp delete mode 100644 include/estd/IntrusiveList.hpp delete mode 100644 include/estd/ReferenceHolder.hpp delete mode 100644 include/estd/ReverseAdaptor.hpp delete mode 100644 include/estd/SortedIntrusiveForwardList.hpp delete mode 100644 include/estd/SortedIntrusiveList.hpp delete mode 100644 include/estd/TypeErasedFunctor.hpp delete mode 100644 include/estd/apply.hpp delete mode 100644 include/estd/invoke.hpp (limited to 'include/estd') diff --git a/include/estd/ContiguousRange.hpp b/include/estd/ContiguousRange.hpp deleted file mode 100644 index adfc8a0..0000000 --- a/include/estd/ContiguousRange.hpp +++ /dev/null @@ -1,164 +0,0 @@ -/** - * \file - * \brief ContiguousRange template class header. - * - * \author Copyright (C) 2014-2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_CONTIGUOUSRANGE_HPP_ -#define ESTD_CONTIGUOUSRANGE_HPP_ - -#include - -namespace estd -{ - -/** - * \brief ContiguousRange template class is a pair of iterators to contiguous sequence of elements in memory - * - * \tparam T is the type of data in the range - */ - -template -class ContiguousRange -{ -public: - - /// value_type type - using value_type = T; - - /// pointer type - using pointer = value_type*; - - /// const_pointer type - using const_pointer = const value_type*; - - /// reference type - using reference = value_type&; - - /// const_reference type - using const_reference = const value_type&; - - /// iterator type - using iterator = value_type*; - - /// const_iterator type - using const_iterator = const value_type*; - - /// size_type type - using size_type = std::size_t; - - /// difference_type type - using difference_type = std::ptrdiff_t; - - /// reverse_iterator type - using reverse_iterator = std::reverse_iterator; - - /// const_reverse_iterator type - using const_reverse_iterator = std::reverse_iterator; - - /** - * \brief ContiguousRange's constructor. - * - * \param [in] beginn is an iterator to first element in the range - * \param [in] endd is an iterator to "one past the last" element in the range - */ - - constexpr ContiguousRange(const iterator beginn, const iterator endd) noexcept : - begin_{beginn}, - end_{endd} - { - - } - - /** - * \brief Empty ContiguousRange's constructor. - */ - - constexpr explicit ContiguousRange() noexcept : - ContiguousRange{nullptr, nullptr} - { - - } - - /** - * \brief ContiguousRange's constructor using C-style array. - * - * \tparam N is the number of elements in the array - * - * \param [in] array is the array used to initialize the range - */ - - template - constexpr explicit ContiguousRange(T (& array)[N]) noexcept : - ContiguousRange{array, array + N} - { - - } - - /** - * \brief ContiguousRange's constructor using single value - * - * \param [in] value is a reference to variable used to initialize the range - */ - - constexpr explicit ContiguousRange(T& value) noexcept : - ContiguousRange{&value, &value + 1} - { - - } - - /** - * \return iterator to first element in the range - */ - - constexpr iterator begin() const noexcept - { - return begin_; - } - - /** - * \return iterator to "one past the last" element in the range - */ - - constexpr iterator end() const noexcept - { - return end_; - } - - /** - * \return number of elements in the range - */ - - constexpr size_type size() const noexcept - { - return end_ - begin_; - } - - /** - * \param [in] i is the index of element that will be accessed - * - * \return reference to element at given index - */ - - reference operator[](const size_type i) const noexcept - { - return begin_[i]; - } - -private: - - /// iterator to first element in the range - iterator begin_; - - /// iterator to "one past the last" element in the range - iterator end_; -}; - -} // namespace estd - -#endif // ESTD_CONTIGUOUSRANGE_HPP_ diff --git a/include/estd/IntegerSequence.hpp b/include/estd/IntegerSequence.hpp deleted file mode 100644 index a0776f5..0000000 --- a/include/estd/IntegerSequence.hpp +++ /dev/null @@ -1,229 +0,0 @@ -/** - * \file - * \brief IntegerSequence template class header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_INTEGERSEQUENCE_HPP_ -#define ESTD_INTEGERSEQUENCE_HPP_ - -#include - -namespace estd -{ - -/** - * \brief Compile-time sequence of integers - * - * Similar to std::integer_sequence from C++14 - http://en.cppreference.com/w/cpp/utility/integer_sequence - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam Integers is a non-type parameter pack representing the sequence - */ - -template -class IntegerSequence -{ -public: - - /// integer type used for the elements of the sequence - using value_type = T; - - /** - * \return number of elements in the sequence - */ - - constexpr static std::size_t size() noexcept - { - return sizeof...(Integers); - }; -}; - -/** - * \brief Compile-time sequence of std::size_t elements - * - * Similar to std::index_sequence from C++14 - http://en.cppreference.com/w/cpp/utility/integer_sequence - * - * \tparam Indexes is a non-type parameter pack representing the sequence - */ - -template -using IndexSequence = IntegerSequence; - -namespace internal -{ - -/** - * \brief IntegerSequence with two internal type aliases. - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam Integers is a non-type parameter pack representing the sequence - */ - -template -struct TypedSequence : IntegerSequence -{ - /// type of base class - using base = IntegerSequence; - - /// type of class - using type = TypedSequence; -}; - -/** - * \brief TypedSequence with doubled number of elements - * - * \tparam Sequence is the type of sequence that will be doubled - */ - -template -struct DoubledIntegerSequence; - -/** - * \brief TypedSequence with doubled number of elements - * - * Specialization for TypedSequence. - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam Integers is a non-type parameter pack representing the sequence - */ - -template -struct DoubledIntegerSequence> -{ - /// TypedSequence with doubled number of elements - TypedSequence is turned into - /// TypedSequence - using type = TypedSequence; -}; - -/** - * \brief TypedSequence optionally extended by one element - * - * \tparam Extend selects whether the sequence will be extended by one element (true) or not (false) - * \tparam Sequence is the type of sequence that will optionally be extended - */ - -template -struct ExtendedIntegerSequence -{ - /// same as \a Sequence - using type = Sequence; -}; - -/** - * \brief TypedSequence optionally extended by one element - * - * Specialization for the case with extending. - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam Integers is a non-type parameter pack representing the sequence - */ - -template -struct ExtendedIntegerSequence> -{ - /// sequence extended by one element - TypedSequence is turned into - /// TypedSequence - using type = TypedSequence; -}; - -/** - * \brief Implementation of generator of IntegerSequence types - * - * Generates TypedSequence type. - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam N is the requested number of elements in the sequence - */ - -template -struct MakeIntegerSequenceImplementation : - ExtendedIntegerSequence::type>::type> -{ - -}; - -/** - * \brief Implementation of generator of IntegerSequence types - * - * Specialization for terminal case - 0 elements - generates TypedSequence type. - * - * \tparam T is an integer type to use for the elements of the sequence - */ - -template -struct MakeIntegerSequenceImplementation -{ - /// empty TypedSequence type - using type = TypedSequence; -}; - -/** - * \brief Wrapper for MakeIntegerSequenceImplementation that ensures \a N is non-negative - * - * Generates TypedSequence type. - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam N is the requested number of elements in the sequence, must be non-negative - */ - -template -struct MakeIntegerSequenceImplementationWrapper : - std::enable_if= 0, MakeIntegerSequenceImplementation(N)>>::type -{ - static_assert(N >= 0, "Number of elements in the sequence must be non-negative!"); -}; - -} // namespace internal - -/** - * \brief Generator of IntegerSequence types - * - * Similar to std::make_integer_sequence from C++14 - http://en.cppreference.com/w/cpp/utility/integer_sequence - * - * Whole implementation is based on code from http://stackoverflow.com/a/20101039/157344 - * - * Generates IntegerSequence type. - * - * \tparam T is an integer type to use for the elements of the sequence - * \tparam N is the requested number of elements in the sequence - */ - -template -using MakeIntegerSequence = typename internal::MakeIntegerSequenceImplementationWrapper::type::base; - -/** - * \brief Generator of IndexSequence types - * - * Similar to std::make_index_sequence from C++14 - http://en.cppreference.com/w/cpp/utility/integer_sequence - * - * Generates IndexSequence<0, 1, ..., N - 1> type. - * - * \tparam N is the requested number of elements in the sequence - */ - -template -using MakeIndexSequence = MakeIntegerSequence; - -/** - * \brief Generator of IndexSequence types - * - * Similar to std::index_sequence_for from C++14 - http://en.cppreference.com/w/cpp/utility/integer_sequence - * - * Generates IndexSequence<0, 1, ..., sizeof...(T) - 1> type. - * - * \tparam T is the type parameter pack for which an index sequence of the same length will be generated - */ - -template -using IndexSequenceFor = MakeIndexSequence; - -} // namespace estd - -#endif // ESTD_INTEGERSEQUENCE_HPP_ diff --git a/include/estd/IntrusiveForwardList.hpp b/include/estd/IntrusiveForwardList.hpp deleted file mode 100644 index faa98d1..0000000 --- a/include/estd/IntrusiveForwardList.hpp +++ /dev/null @@ -1,1120 +0,0 @@ -/** - * \file - * \brief IntrusiveForwardList template class header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_INTRUSIVEFORWARDLIST_HPP_ -#define ESTD_INTRUSIVEFORWARDLIST_HPP_ - -#include - -#include - -namespace estd -{ - -namespace internal -{ - -class IntrusiveForwardListBase; - -} - -/** - * \brief IntrusiveForwardListNode class is the node that is needed for the object to be linked in IntrusiveForwardList - * - * To some extent, this class can be considered to be a limited (raw) iterator. - * - * The object that wants to be linked in IntrusiveForwardList must contain a variable of this type - one for each - * intrusive forward list that will be used with object. - */ - -class IntrusiveForwardListNode -{ -public: - - /// AccessKey class is used to limit access to IntrusiveForwardListNode's linkAfter() and unlinkNext() functions - - /// only internal::IntrusiveForwardListBase can link/unlink nodes - class AccessKey - { - friend class internal::IntrusiveForwardListBase; - - /** - * \brief AccessKey's constructor - */ - - constexpr AccessKey() - { - - } - - AccessKey(const AccessKey&) = delete; - AccessKey(AccessKey&&) = delete; - const AccessKey& operator=(const AccessKey&) = delete; - AccessKey& operator=(AccessKey&&) = delete; - }; - - /** - * \brief IntrusiveForwardListNode's constructor - */ - - constexpr IntrusiveForwardListNode() : - nextNode_{} - { - - } - - /** - * \brief IntrusiveForwardListNode's move constructor - * - * \param [in] other is a rvalue reference to IntrusiveForwardListNode used as source of move construction - */ - - IntrusiveForwardListNode(IntrusiveForwardListNode&& other) : - nextNode_{other.nextNode_} - { - other.reset(); - } - - /** - * \return pointer to next node on the list - */ - - IntrusiveForwardListNode* getNextNode() const - { - return nextNode_; - } - - /** - * \return true if the node is linked in some list, false otherwise - */ - - bool isLinked() const - { - return nextNode_ != nullptr; - } - - /** - * \brief Links the node in the list after \a position. - * - * \note Access to this function is restricted only to functions from internal::IntrusiveForwardListBase class - * - * \param [in] position is a pointer to node after which this node will be linked - * \param [in] accessKey is used to limit access to this function - */ - - void linkAfter(IntrusiveForwardListNode* const position, AccessKey) - { - nextNode_ = position->getNextNode(); - position->nextNode_ = this; - } - - /** - * \brief Swaps contents with another node. - * - * \param [in] other is a reference to IntrusiveForwardListNode with which contents of this node will be swapped - */ - - void swap(IntrusiveForwardListNode& other) - { - using std::swap; - swap(nextNode_, other.nextNode_); - } - - /** - * \brief Unlinks the node following this one from the list. - * - * \note Access to this function is restricted only to functions from internal::IntrusiveForwardListBase class - * - * \param [in] accessKey is used to limit access to this function - */ - - void unlinkNext(AccessKey) - { - auto& nextNode = *nextNode_; - nextNode_ = nextNode.nextNode_; - - nextNode.reset(); - } - - IntrusiveForwardListNode(const IntrusiveForwardListNode&) = delete; - const IntrusiveForwardListNode& operator=(const IntrusiveForwardListNode&) = delete; - IntrusiveForwardListNode& operator=(IntrusiveForwardListNode&&) = delete; - -private: - - /** - * \brief Resets the node to the same state as right after construction. - */ - - void reset() - { - nextNode_ = {}; - } - - /// pointer to next node on the list - IntrusiveForwardListNode* nextNode_; -}; - -/** - * \brief Swaps contents of two nodes. - * - * \param [in] left is a reference to IntrusiveForwardListNode with which contents of \a right will be swapped - * \param [in] right is a reference to IntrusiveForwardListNode with which contents of \a left will be swapped - */ - -inline void swap(IntrusiveForwardListNode& left, IntrusiveForwardListNode& right) -{ - left.swap(right); -} - -namespace internal -{ - -/** - * \brief IntrusiveForwardListBase class provides base functionalities for IntrusiveForwardList class, but without any - * knowledge about types - * - * This class tries to provide an interface similar to std::forward_list. - */ - -class IntrusiveForwardListBase -{ -public: - - /** - * \brief IntrusiveForwardListBase's constructor - */ - - constexpr IntrusiveForwardListBase() : - rootNode_{} - { - - } - - /** - * \brief IntrusiveForwardListBase's destructor - * - * Unlinks all nodes from the list. - */ - - ~IntrusiveForwardListBase() - { - clear(); - } - - /** - * \return pointer to "one before the first" node on the list - */ - - IntrusiveForwardListNode* before_begin() - { - return &rootNode_; - } - - /** - * \return const pointer to "one before the first" node on the list - */ - - const IntrusiveForwardListNode* before_begin() const - { - return &rootNode_; - } - - /** - * \return pointer to first node on the list - */ - - IntrusiveForwardListNode* begin() - { - return rootNode_.getNextNode(); - } - - /** - * \return const pointer to first node on the list - */ - - const IntrusiveForwardListNode* begin() const - { - return rootNode_.getNextNode(); - } - - /** - * \return const pointer to "one before the first" node on the list - */ - - const IntrusiveForwardListNode* cbefore_begin() const - { - return before_begin(); - } - - /** - * \return const pointer to first node on the list - */ - - const IntrusiveForwardListNode* cbegin() const - { - return begin(); - } - - /** - * \return const pointer to "one past the last" node on the list - */ - - const IntrusiveForwardListNode* cend() const - { - return end(); - } - - /** - * \brief Unlinks all nodes from the list. - */ - - void clear() - { - while (empty() == false) - pop_front(); - } - - /** - * \return true is the list is empty, false otherwise - */ - - bool empty() const - { - return begin() == end(); - } - - /** - * \return pointer to "one past the last" node on the list - */ - - IntrusiveForwardListNode* end() - { - return nullptr; - } - - /** - * \return const pointer to "one past the last" node on the list - */ - - const IntrusiveForwardListNode* end() const - { - return nullptr; - } - - /** - * \brief Unlinks the first node from the list. - */ - - void pop_front() - { - erase_after(before_begin()); - } - - /** - * \brief Links the node at the beginning of the list. - * - * \param [in] newNode is a reference to node that will be linked in the list - */ - - void push_front(IntrusiveForwardListNode& newNode) - { - insert_after(before_begin(), newNode); - } - - /** - * \brief Swaps contents with another list. - * - * \param [in] other is a reference to IntrusiveForwardListBase with which contents of this list will be swapped - */ - - void swap(IntrusiveForwardListBase& other) - { - rootNode_.swap(other.rootNode_); - } - - /** - * \brief Unlinks the node following \a position from the list. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is a pointer to the node preceding the one which will be unlinked from the list - * - * \return pointer to the node that was following the node which was unlinked - */ - - static IntrusiveForwardListNode* erase_after(IntrusiveForwardListNode* const position) - { - position->unlinkNext({}); - return position->getNextNode(); - } - - /** - * \brief Links the node in the list after \a position. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is a pointer to node after which \a newNode will be linked - * \param [in] newNode is a reference to node that will be linked in the list - */ - - static void insert_after(IntrusiveForwardListNode* const position, IntrusiveForwardListNode& newNode) - { - newNode.linkAfter(position, {}); - } - - /** - * \brief Transfers the node from one list to another list after \a position. - * - * \note No instance of any list is needed for this operation. - * - * \param [in] position is a pointer to node after which spliced node will be linked - * \param [in] beforeSplicedNode is a pointer to node preceding the one which will be spliced from one list to - * another - */ - - static void splice_after(IntrusiveForwardListNode* const position, - IntrusiveForwardListNode* const beforeSplicedNode) - { - const auto splicedNode = beforeSplicedNode->getNextNode(); - erase_after(beforeSplicedNode); - insert_after(position, *splicedNode); - } - - IntrusiveForwardListBase(const IntrusiveForwardListBase&) = delete; - IntrusiveForwardListBase(IntrusiveForwardListBase&&) = default; - const IntrusiveForwardListBase& operator=(const IntrusiveForwardListBase&) = delete; - IntrusiveForwardListBase& operator=(IntrusiveForwardListBase&&) = delete; - -private: - - /// root node of the intrusive forward list - IntrusiveForwardListNode rootNode_; -}; - -/** - * \brief Swaps contents of two lists. - * - * \param [in] left is a reference to IntrusiveForwardListBase with which contents of \a right will be swapped - * \param [in] right is a reference to IntrusiveForwardListBase with which contents of \a left will be swapped - */ - -inline void swap(IntrusiveForwardListBase& left, IntrusiveForwardListBase& right) -{ - left.swap(right); -} - -} // namespace internal - -/** - * \brief IntrusiveForwardListIterator class is an iterator of elements on IntrusiveForwardList. - * - * This class provides an interface similar to std::forward_list::iterator. - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - */ - -template -class IntrusiveForwardListIterator -{ -public: - - /// difference type - using difference_type = ptrdiff_t; - - /// category of the iterator - using iterator_category = std::forward_iterator_tag; - - /// pointer to object "pointed to" by the iterator - using pointer = U*; - - /// reference to object "pointed to" by the iterator - using reference = U&; - - /// value "pointed to" by the iterator - using value_type = U; - - /** - * \brief IntrusiveForwardListIterator's constructor - */ - - constexpr IntrusiveForwardListIterator() : - node_{} - { - - } - - /** - * \brief IntrusiveForwardListIterator's constructor - * - * \param [in] node is a pointer to IntrusiveForwardListNode of element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveForwardListIterator(IntrusiveForwardListNode* const node) : - node_{node} - { - - } - - /** - * \brief IntrusiveForwardListIterator's constructor - * - * \param [in] element is a reference to element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveForwardListIterator(reference element) : - node_{&(element.*NodePointer)} - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - } - - /** - * \brief IntrusiveForwardListIterator's binary infix pointer member access operator - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer operator->() const - { - return getPointer(); - } - - /** - * \brief IntrusiveForwardListIterator's unary prefix dereference operator - * - * \return reference to object "pointed to" by the iterator - */ - - reference operator*() const - { - return *getPointer(); - } - - /** - * \brief IntrusiveForwardListIterator's unary prefix increment operator - * - * \return reference to "this" iterator - */ - - IntrusiveForwardListIterator& operator++() - { - node_ = node_->getNextNode(); - return *this; - } - - /** - * \brief IntrusiveForwardListIterator's unary postfix increment operator - * - * \return copy of "this" iterator before increment - */ - - IntrusiveForwardListIterator operator++(int) - { - const auto temporary = *this; - node_ = node_->getNextNode(); - return temporary; - } - - /** - * \brief IntrusiveForwardListIterator's "equal to" comparison operator - * - * \param [in] other is a const reference to IntrusiveForwardListIterator on right-hand side of equality operator - * - * \return true if both iterators are equal, false otherwise - */ - - bool operator==(const IntrusiveForwardListIterator& other) const - { - return node_ == other.node_; - } - -private: - - /** - * \brief Converts contained pointer to IntrusiveForwardListNode to pointer to object that contains this node. - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer getPointer() const - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - - const auto offset = reinterpret_cast(&(static_cast(nullptr)->*NodePointer)); - return reinterpret_cast(reinterpret_cast(node_) - offset); - } - - /// pointer to IntrusiveForwardListNode of the object "pointed to" by the iterator - IntrusiveForwardListNode* node_; -}; - -/** - * \brief IntrusiveForwardListIterator's "not equal to" comparison operator - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveForwardListIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveForwardListIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveForwardListIterator& left, - const IntrusiveForwardListIterator& right) -{ - return (left == right) == false; -} - -/** - * \brief IntrusiveForwardListConstIterator class is a const iterator of elements on IntrusiveForwardList. - * - * This class provides an interface similar to std::forward_list::const_iterator. - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a const pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - */ - -template -class IntrusiveForwardListConstIterator -{ -public: - - /// difference type - using difference_type = ptrdiff_t; - - /// category of the iterator - using iterator_category = std::forward_iterator_tag; - - /// pointer to object "pointed to" by the iterator - using pointer = const U*; - - /// reference to object "pointed to" by the iterator - using reference = const U&; - - /// value "pointed to" by the iterator - using value_type = U; - - /** - * \brief IntrusiveForwardListConstIterator's constructor - */ - - constexpr IntrusiveForwardListConstIterator() : - node_{} - { - - } - - /** - * \brief IntrusiveForwardListConstIterator's constructor - * - * \param [in] node is a pointer to const IntrusiveForwardListNode of element that will be "pointed to" by the - * iterator - */ - - constexpr explicit IntrusiveForwardListConstIterator(const IntrusiveForwardListNode* const node) : - node_{node} - { - - } - - /** - * \brief IntrusiveForwardListConstIterator's constructor - * - * \param [in] element is a const reference to element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveForwardListConstIterator(reference element) : - node_{&(element.*NodePointer)} - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - } - - /** - * \brief IntrusiveForwardListConstIterator's constructor - * - * Converts non-const iterator (IntrusiveForwardListIterator) to const iterator (IntrusiveForwardListConstIterator). - * - * \tparam NonConstNodePointer is a non-const version of \a NodePointer - * - * \param [in] iterator is a const reference to non-const iterator (IntrusiveForwardListIterator) - */ - - template - constexpr - IntrusiveForwardListConstIterator(const IntrusiveForwardListIterator& iterator) : - IntrusiveForwardListConstIterator{*iterator} - { - - } - - /** - * \brief IntrusiveForwardListConstIterator's binary infix pointer member access operator - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer operator->() const - { - return getPointer(); - } - - /** - * \brief IntrusiveForwardListConstIterator's unary prefix dereference operator - * - * \return reference to object "pointed to" by the iterator - */ - - reference operator*() const - { - return *getPointer(); - } - - /** - * \brief IntrusiveForwardListConstIterator's unary prefix increment operator - * - * \return reference to "this" iterator - */ - - IntrusiveForwardListConstIterator& operator++() - { - node_ = node_->getNextNode(); - return *this; - } - - /** - * \brief IntrusiveForwardListConstIterator's unary postfix increment operator - * - * \return copy of "this" iterator before increment - */ - - IntrusiveForwardListConstIterator operator++(int) - { - const auto temporary = *this; - node_ = node_->getNextNode(); - return temporary; - } - - /** - * \brief IntrusiveForwardListConstIterator's "equal to" comparison operator - * - * \param [in] other is a const reference to IntrusiveForwardListConstIterator on right-hand side of equality - * operator - * - * \return true if both iterators are equal, false otherwise - */ - - bool operator==(const IntrusiveForwardListConstIterator& other) const - { - return node_ == other.node_; - } - -private: - - /** - * \brief Converts contained pointer to IntrusiveForwardListNode to pointer to object that contains this node. - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer getPointer() const - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - - const auto offset = reinterpret_cast(&(static_cast(nullptr)->*NodePointer)); - return reinterpret_cast(reinterpret_cast(node_) - offset); - } - - /// pointer to const IntrusiveForwardListNode of the object "pointed to" by the iterator - const IntrusiveForwardListNode* node_; -}; - -/** - * \brief IntrusiveForwardListConstIterator's "not equal to" comparison operator - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a const pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveForwardListConstIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveForwardListConstIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveForwardListConstIterator& left, - const IntrusiveForwardListConstIterator& right) -{ - return (left == right) == false; -} - -/** - * \brief "Equal to" comparison operator for IntrusiveForwardListIterator and IntrusiveForwardListConstIterator - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam ConstNodePointer is a const pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveForwardListIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveForwardListConstIterator on right-hand side of comparison operator - * - * \return true if both iterators are equal, false otherwise - */ - -template -inline bool operator==(const IntrusiveForwardListIterator& left, - const IntrusiveForwardListConstIterator& right) -{ - return decltype(right){left} == right; -} - -/** - * \brief "Not equal to" comparison operator for IntrusiveForwardListIterator and IntrusiveForwardListConstIterator - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam ConstNodePointer is a const pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveForwardListIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveForwardListConstIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveForwardListIterator& left, - const IntrusiveForwardListConstIterator& right) -{ - return (left == right) == false; -} - -/** - * \brief "Not equal to" comparison operator for IntrusiveForwardListConstIterator and IntrusiveForwardListIterator - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam ConstNodePointer is a const pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveForwardListConstIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveForwardListIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveForwardListConstIterator& left, - const IntrusiveForwardListIterator& right) -{ - return right != left; -} - -/** - * \brief IntrusiveForwardList class is an intrusive linear singly linked list. - * - * This class tries to provide an interface similar to std::forward_list. - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; using different type than \a T can be used - * to break circular dependencies, because \a T must be fully defined to instantiate this class, but it is enough to - * forward declare \a U - it only needs to be fully defined to use member functions - */ - -template -class IntrusiveForwardList -{ -public: - - /// const iterator of elements on the list - using const_iterator = IntrusiveForwardListConstIterator; - - /// const pointer to value linked in the list - using const_pointer = const U*; - - /// const reference to value linked in the list - using const_reference = const U&; - - /// iterator of elements on the list - using iterator = IntrusiveForwardListIterator; - - /// pointer to value linked in the list - using pointer = U*; - - /// reference to value linked in the list - using reference = U&; - - /// value linked in the list - using value_type = U; - - /** - * \brief IntrusiveForwardList's constructor - */ - - constexpr IntrusiveForwardList() : - intrusiveForwardListBase_{} - { - - } - - /** - * \return iterator of "one before the first" element on the list - */ - - iterator before_begin() - { - return iterator{intrusiveForwardListBase_.before_begin()}; - } - - /** - * \return const iterator of "one before the first" element on the list - */ - - const_iterator before_begin() const - { - return const_iterator{intrusiveForwardListBase_.before_begin()}; - } - - /** - * \return iterator of first element on the list - */ - - iterator begin() - { - return iterator{intrusiveForwardListBase_.begin()}; - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator begin() const - { - return const_iterator{intrusiveForwardListBase_.begin()}; - } - - /** - * \return const iterator of "one before the first" element on the list - */ - - const_iterator cbefore_begin() const - { - return before_begin(); - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator cbegin() const - { - return begin(); - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator cend() const - { - return end(); - } - - /** - * \brief Unlinks all elements from the list. - */ - - void clear() - { - intrusiveForwardListBase_.clear(); - } - - /** - * \return true is the list is empty, false otherwise - */ - - bool empty() const - { - return intrusiveForwardListBase_.empty(); - } - - /** - * \return iterator of "one past the last" element on the list - */ - - iterator end() - { - return iterator{intrusiveForwardListBase_.end()}; - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator end() const - { - return const_iterator{intrusiveForwardListBase_.end()}; - } - - /** - * \return reference to first element on the list - */ - - reference front() - { - return *begin(); - } - - /** - * \return const reference to first element on the list - */ - - const_reference front() const - { - return *begin(); - } - - /** - * \brief Unlinks the first element from the list. - */ - - void pop_front() - { - erase_after(before_begin()); - } - - /** - * \brief Links the element at the beginning of the list. - * - * \param [in] newElement is a reference to the element that will be linked in the list - */ - - void push_front(reference newElement) - { - insert_after(before_begin(), newElement); - } - - /** - * \brief Swaps contents with another list. - * - * \param [in] other is a reference to IntrusiveForwardList with which contents of this list will be swapped - */ - - void swap(IntrusiveForwardList& other) - { - intrusiveForwardListBase_.swap(other.intrusiveForwardListBase_); - } - - /** - * \brief Unlinks the element following \a position from the list. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is an iterator preceding the element which will be unlinked from the list - * - * \return iterator of the element that was following the element which was unlinked - */ - - static iterator erase_after(const iterator position) - { - auto& positionNode = (*position).*NodePointer; - const auto afterNextNode = internal::IntrusiveForwardListBase::erase_after(&positionNode); - return iterator{afterNextNode}; - } - - /** - * \brief Links the element in the list after \a position. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is an iterator of the element after which \a newNode will be linked - * \param [in] newElement is a reference to the element that will be linked in the list - * - * \return iterator of \a newElement - */ - - static iterator insert_after(const iterator position, reference newElement) - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - - auto& positionNode = (*position).*NodePointer; - auto& newElementNode = newElement.*NodePointer; - internal::IntrusiveForwardListBase::insert_after(&positionNode, newElementNode); - return iterator{&newElementNode}; - } - - /** - * \brief Transfers the element from one list to another list after \a position. - * - * \note No instance of any list is needed for this operation. - * - * \param [in] position is an iterator of the element after which spliced element will be linked - * \param [in] beforeSplicedElement is an iterator of the element preceding the one which will be spliced from one - * list to another - */ - - static void splice_after(const iterator position, const iterator beforeSplicedElement) - { - auto& positionNode = (*position).*NodePointer; - auto& beforeSplicedElementNode = (*beforeSplicedElement).*NodePointer; - internal::IntrusiveForwardListBase::splice_after(&positionNode, &beforeSplicedElementNode); - } - - IntrusiveForwardList(const IntrusiveForwardList&) = delete; - IntrusiveForwardList(IntrusiveForwardList&&) = default; - const IntrusiveForwardList& operator=(const IntrusiveForwardList&) = delete; - IntrusiveForwardList& operator=(IntrusiveForwardList&&) = delete; - -private: - - /// internal IntrusiveForwardListBase object - internal::IntrusiveForwardListBase intrusiveForwardListBase_; -}; - -/** - * \brief Swaps contents of two lists. - * - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a reference to IntrusiveForwardList with which contents of \a right will be swapped - * \param [in] right is a reference to IntrusiveForwardList with which contents of \a left will be swapped - */ - -template -inline void swap(IntrusiveForwardList& left, IntrusiveForwardList& right) -{ - left.swap(right); -} - -} // namespace estd - -#endif // ESTD_INTRUSIVEFORWARDLIST_HPP_ diff --git a/include/estd/IntrusiveList.hpp b/include/estd/IntrusiveList.hpp deleted file mode 100644 index 82597f4..0000000 --- a/include/estd/IntrusiveList.hpp +++ /dev/null @@ -1,1208 +0,0 @@ -/** - * \file - * \brief IntrusiveList template class header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_INTRUSIVELIST_HPP_ -#define ESTD_INTRUSIVELIST_HPP_ - -#include - -#include - -namespace estd -{ - -namespace internal -{ - -class IntrusiveListBase; - -} - -/** - * \brief IntrusiveListNode class is the node that is needed for the object to be linked in IntrusiveList - * - * To some extent, this class can be considered to be a limited (raw) iterator. - * - * The object that wants to be linked in IntrusiveList must contain a variable of this type - one for each intrusive - * list that will be used with object. - */ - -class IntrusiveListNode -{ -public: - - /// LinkAccessKey class is used to limit access to IntrusiveListNode::link() function - only - /// internal::IntrusiveListBase can link nodes to the list - class LinkAccessKey - { - friend class internal::IntrusiveListBase; - - /** - * \brief LinkAccessKey's constructor - */ - - constexpr LinkAccessKey() - { - - } - - LinkAccessKey(const LinkAccessKey&) = delete; - LinkAccessKey(LinkAccessKey&&) = delete; - const LinkAccessKey& operator=(const LinkAccessKey&) = delete; - LinkAccessKey& operator=(LinkAccessKey&&) = delete; - }; - - /** - * \brief IntrusiveListNode's constructor - */ - - constexpr IntrusiveListNode() : - nextNode_{this}, - previousNode_{this} - { - - } - - /** - * \brief IntrusiveListNode's move constructor - * - * \param [in] other is a rvalue reference to IntrusiveListNode used as source of move construction - */ - - IntrusiveListNode(IntrusiveListNode&& other) - { - if (other.isLinked() == false) - { - reset(); - return; - } - - nextNode_ = other.nextNode_; - previousNode_ = other.previousNode_; - nextNode_->previousNode_ = previousNode_->nextNode_ = this; - other.reset(); - } - - /** - * \brief IntrusiveListNode's destructor - * - * Unlinks the node from the list. - */ - - ~IntrusiveListNode() - { - unlink(); - } - - /** - * \return reference to next node on the list - */ - - IntrusiveListNode& getNextNode() const - { - return *nextNode_; - } - - /** - * \return reference to previous node on the list - */ - - IntrusiveListNode& getPreviousNode() const - { - return *previousNode_; - } - - /** - * \return true if the node is linked in some list, false otherwise - */ - - bool isLinked() const - { - return nextNode_ != this; - } - - /** - * \brief Links the node in the list before \a position. - * - * \note Access to this function is restricted only to functions from internal::IntrusiveListBase class - * - * \param [in] position is a reference to node before which this node will be linked - * \param [in] linkAccessKey is used to limit access to this function - */ - - void link(IntrusiveListNode& position, LinkAccessKey) - { - unlink(); - - nextNode_ = &position; - previousNode_ = position.previousNode_; - position.previousNode_->nextNode_ = this; - position.previousNode_ = this; - } - - /** - * \brief Swaps contents with another node. - * - * \param [in] other is a reference to IntrusiveListNode with which contents of this node will be swapped - */ - - void swap(IntrusiveListNode& other) - { - const auto thisWasLinked = isLinked(); - const auto otherWasLinked = other.isLinked(); - - if (thisWasLinked == true || otherWasLinked == true) - { - using std::swap; - swap(nextNode_, other.nextNode_); - swap(previousNode_, other.previousNode_); - - if (thisWasLinked == true) - other.nextNode_->previousNode_ = other.previousNode_->nextNode_ = &other; - else - other.reset(); - - if (otherWasLinked == true) - nextNode_->previousNode_ = previousNode_->nextNode_ = this; - else - reset(); - } - } - - /** - * \brief Unlinks the node from the list. - */ - - void unlink() - { - previousNode_->nextNode_ = nextNode_; - nextNode_->previousNode_ = previousNode_; - - reset(); - } - - IntrusiveListNode(const IntrusiveListNode&) = delete; - const IntrusiveListNode& operator=(const IntrusiveListNode&) = delete; - IntrusiveListNode& operator=(IntrusiveListNode&&) = delete; - -private: - - /** - * \brief Resets the node to the same state as right after construction. - */ - - void reset() - { - nextNode_ = this; - previousNode_ = this; - } - - /// reference to next node on the list - IntrusiveListNode* nextNode_; - - /// reference to previous node on the list - IntrusiveListNode* previousNode_; -}; - -namespace internal -{ - -/** - * \brief IntrusiveListBase class provides base functionalities for IntrusiveList class, but without any knowledge about - * types - * - * This class tries to provide an interface similar to std::list. - */ - -class IntrusiveListBase -{ -public: - - /** - * \brief IntrusiveListBase's constructor - */ - - constexpr IntrusiveListBase() : - rootNode_{} - { - - } - - /** - * \brief IntrusiveListBase's destructor - * - * Unlinks all nodes from the list. - */ - - ~IntrusiveListBase() - { - clear(); - } - - /** - * \return reference to first node on the list - */ - - IntrusiveListNode& begin() - { - return rootNode_.getNextNode(); - } - - /** - * \return const reference to first node on the list - */ - - const IntrusiveListNode& begin() const - { - return rootNode_.getNextNode(); - } - - /** - * \return const reference to first node on the list - */ - - const IntrusiveListNode& cbegin() const - { - return begin(); - } - - /** - * \return const reference to "one past the last" node on the list - */ - - const IntrusiveListNode& cend() const - { - return end(); - } - - /** - * \brief Unlinks all nodes from the list. - */ - - void clear() - { - while (empty() == false) - pop_front(); - } - - /** - * \return true is the list is empty, false otherwise - */ - - bool empty() const - { - return &begin() == &end(); - } - - /** - * \return reference to "one past the last" node on the list - */ - - IntrusiveListNode& end() - { - return rootNode_; - } - - /** - * \return const reference to "one past the last" node on the list - */ - - const IntrusiveListNode& end() const - { - return rootNode_; - } - - /** - * \brief Unlinks the last node from the list. - */ - - void pop_back() - { - erase(end().getPreviousNode()); - } - - /** - * \brief Unlinks the first node from the list. - */ - - void pop_front() - { - erase(begin()); - } - - /** - * \brief Links the node at the end of the list. - * - * \param [in] newNode is a reference to node that will be linked in the list - */ - - void push_back(IntrusiveListNode& newNode) - { - insert(end(), newNode); - } - - /** - * \brief Links the node at the beginning of the list. - * - * \param [in] newNode is a reference to node that will be linked in the list - */ - - void push_front(IntrusiveListNode& newNode) - { - insert(begin(), newNode); - } - - /** - * \brief Swaps contents with another list. - * - * \param [in] other is a reference to IntrusiveListBase with which contents of this list will be swapped - */ - - void swap(IntrusiveListBase& other) - { - rootNode_.swap(other.rootNode_); - } - - /** - * \brief Unlinks the node at \a position from the list. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is a reference to the node that will be unlinked from the list - * - * \return reference to the node that was following the node which was unlinked - */ - - static IntrusiveListNode& erase(IntrusiveListNode& position) - { - auto& next = position.getNextNode(); - position.unlink(); - return next; - } - - /** - * \brief Links the node in the list before \a position. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is a reference to node before which \a newNode will be linked - * \param [in] newNode is a reference to node that will be linked in the list - */ - - static void insert(IntrusiveListNode& position, IntrusiveListNode& newNode) - { - newNode.link(position, {}); - } - - /** - * \brief Transfers the node from one list to another list before \a position. - * - * \note No instance of any list is needed for this operation. - * - * \param [in] position is a reference to node before which \a splicedNode will be linked - * \param [in] splicedNode is a reference to node that will be spliced from one list to another - */ - - static void splice(IntrusiveListNode& position, IntrusiveListNode& splicedNode) - { - insert(position, splicedNode); - } - - IntrusiveListBase(const IntrusiveListBase&) = delete; - IntrusiveListBase(IntrusiveListBase&&) = default; - const IntrusiveListBase& operator=(const IntrusiveListBase&) = delete; - IntrusiveListBase& operator=(IntrusiveListBase&&) = delete; - -private: - - /// root node of the intrusive list - IntrusiveListNode rootNode_; -}; - -/** - * \brief Swaps contents of two lists. - * - * \param [in] left is a reference to IntrusiveListBase with which contents of \a right will be swapped - * \param [in] right is a reference to IntrusiveListBase with which contents of \a left will be swapped - */ - -inline void swap(IntrusiveListBase& left, IntrusiveListBase& right) -{ - left.swap(right); -} - -} // namespace internal - -/** - * \brief IntrusiveListIterator class is an iterator of elements on IntrusiveList. - * - * This class provides an interface similar to std::list::iterator. - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - */ - -template -class IntrusiveListIterator -{ -public: - - /// difference type - using difference_type = ptrdiff_t; - - /// category of the iterator - using iterator_category = std::bidirectional_iterator_tag; - - /// pointer to object "pointed to" by the iterator - using pointer = U*; - - /// reference to object "pointed to" by the iterator - using reference = U&; - - /// value "pointed to" by the iterator - using value_type = U; - - /** - * \brief IntrusiveListIterator's constructor - */ - - constexpr IntrusiveListIterator() : - node_{} - { - - } - - /** - * \brief IntrusiveListIterator's constructor - * - * \param [in] node is a pointer to IntrusiveListNode of element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveListIterator(IntrusiveListNode* const node) : - node_{node} - { - - } - - /** - * \brief IntrusiveListIterator's constructor - * - * \param [in] element is a reference to element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveListIterator(reference element) : - node_{&(element.*NodePointer)} - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - } - - /** - * \brief IntrusiveListIterator's binary infix pointer member access operator - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer operator->() const - { - return getPointer(); - } - - /** - * \brief IntrusiveListIterator's unary prefix dereference operator - * - * \return reference to object "pointed to" by the iterator - */ - - reference operator*() const - { - return *getPointer(); - } - - /** - * \brief IntrusiveListIterator's unary prefix increment operator - * - * \return reference to "this" iterator - */ - - IntrusiveListIterator& operator++() - { - node_ = &node_->getNextNode(); - return *this; - } - - /** - * \brief IntrusiveListIterator's unary postfix increment operator - * - * \return copy of "this" iterator before increment - */ - - IntrusiveListIterator operator++(int) - { - const auto temporary = *this; - node_ = &node_->getNextNode(); - return temporary; - } - - /** - * \brief IntrusiveListIterator's unary prefix decrement operator - * - * \return reference to "this" iterator - */ - - IntrusiveListIterator& operator--() - { - node_ = &node_->getPreviousNode(); - return *this; - } - - /** - * \brief IntrusiveListIterator's unary postfix decrement operator - * - * \return copy of "this" iterator before decrement - */ - - IntrusiveListIterator operator--(int) - { - const auto temporary = *this; - node_ = &node_->getPreviousNode(); - return temporary; - } - - /** - * \brief IntrusiveListIterator's "equal to" comparison operator - * - * \param [in] other is a const reference to IntrusiveListIterator on right-hand side of comparison operator - * - * \return true if both iterators are equal, false otherwise - */ - - bool operator==(const IntrusiveListIterator& other) const - { - return node_ == other.node_; - } - -private: - - /** - * \brief Converts contained pointer to IntrusiveListNode to pointer to object that contains this node. - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer getPointer() const - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - - const auto offset = reinterpret_cast(&(static_cast(nullptr)->*NodePointer)); - return reinterpret_cast(reinterpret_cast(node_) - offset); - } - - /// pointer to IntrusiveListNode of the object "pointed to" by the iterator - IntrusiveListNode* node_; -}; - -/** - * \brief IntrusiveListIterator's "not equal to" comparison operator - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveListIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveListIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveListIterator& left, - const IntrusiveListIterator& right) -{ - return (left == right) == false; -} - -/** - * \brief IntrusiveListConstIterator class is a const iterator of elements on IntrusiveList. - * - * This class provides an interface similar to std::list::const_iterator. - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a const pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - */ - -template -class IntrusiveListConstIterator -{ -public: - - /// difference type - using difference_type = ptrdiff_t; - - /// category of the iterator - using iterator_category = std::bidirectional_iterator_tag; - - /// pointer to object "pointed to" by the iterator - using pointer = const U*; - - /// reference to object "pointed to" by the iterator - using reference = const U&; - - /// value "pointed to" by the iterator - using value_type = U; - - /** - * \brief IntrusiveListConstIterator's constructor - */ - - constexpr IntrusiveListConstIterator() : - node_{} - { - - } - - /** - * \brief IntrusiveListConstIterator's constructor - * - * \param [in] node is a pointer to const IntrusiveListNode of element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveListConstIterator(const IntrusiveListNode* const node) : - node_{node} - { - - } - - /** - * \brief IntrusiveListConstIterator's constructor - * - * \param [in] element is a const reference to element that will be "pointed to" by the iterator - */ - - constexpr explicit IntrusiveListConstIterator(reference element) : - node_{&(element.*NodePointer)} - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - } - - /** - * \brief IntrusiveListConstIterator's constructor - * - * Converts non-const iterator (IntrusiveListIterator) to const iterator (IntrusiveListConstIterator). - * - * \tparam NonConstNodePointer is a non-const version of \a NodePointer - * - * \param [in] iterator is a const reference to non-const iterator (IntrusiveListIterator) - */ - - template - constexpr IntrusiveListConstIterator(const IntrusiveListIterator& iterator) : - IntrusiveListConstIterator{*iterator} - { - - } - - /** - * \brief IntrusiveListConstIterator's binary infix pointer member access operator - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer operator->() const - { - return getPointer(); - } - - /** - * \brief IntrusiveListConstIterator's unary prefix dereference operator - * - * \return reference to object "pointed to" by the iterator - */ - - reference operator*() const - { - return *getPointer(); - } - - /** - * \brief IntrusiveListConstIterator's unary prefix increment operator - * - * \return reference to "this" iterator - */ - - IntrusiveListConstIterator& operator++() - { - node_ = &node_->getNextNode(); - return *this; - } - - /** - * \brief IntrusiveListConstIterator's unary postfix increment operator - * - * \return copy of "this" iterator before increment - */ - - IntrusiveListConstIterator operator++(int) - { - const auto temporary = *this; - node_ = &node_->getNextNode(); - return temporary; - } - - /** - * \brief IntrusiveListConstIterator's unary prefix decrement operator - * - * \return reference to "this" iterator - */ - - IntrusiveListConstIterator& operator--() - { - node_ = &node_->getPreviousNode(); - return *this; - } - - /** - * \brief IntrusiveListConstIterator's unary postfix decrement operator - * - * \return copy of "this" iterator before decrement - */ - - IntrusiveListConstIterator operator--(int) - { - const auto temporary = *this; - node_ = &node_->getPreviousNode(); - return temporary; - } - - /** - * \brief IntrusiveListConstIterator's "equal to" comparison operator - * - * \param [in] other is a const reference to IntrusiveListConstIterator on right-hand side of comparison operator - * - * \return true if both iterators are equal, false otherwise - */ - - bool operator==(const IntrusiveListConstIterator& other) const - { - return node_ == other.node_; - } - -private: - - /** - * \brief Converts contained pointer to IntrusiveListNode to pointer to object that contains this node. - * - * \return pointer to object "pointed to" by the iterator - */ - - pointer getPointer() const - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - - const auto offset = reinterpret_cast(&(static_cast(nullptr)->*NodePointer)); - return reinterpret_cast(reinterpret_cast(node_) - offset); - } - - /// pointer to const IntrusiveListNode of the object "pointed to" by the iterator - const IntrusiveListNode* node_; -}; - -/** - * \brief IntrusiveListConstIterator's "not equal to" comparison operator - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a const pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveListConstIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveListConstIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveListConstIterator& left, - const IntrusiveListConstIterator& right) -{ - return (left == right) == false; -} - -/** - * \brief "Equal to" comparison operator for IntrusiveListIterator and IntrusiveListConstIterator - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam ConstNodePointer is a const pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveListIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveListConstIterator on right-hand side of comparison operator - * - * \return true if both iterators are equal, false otherwise - */ - -template -inline bool operator==(const IntrusiveListIterator& left, - const IntrusiveListConstIterator& right) -{ - return decltype(right){left} == right; -} - -/** - * \brief "Not equal to" comparison operator for IntrusiveListIterator and IntrusiveListConstIterator - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam ConstNodePointer is a const pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveListIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveListConstIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveListIterator& left, - const IntrusiveListConstIterator& right) -{ - return (left == right) == false; -} - -/** - * \brief "Not equal to" comparison operator for IntrusiveListConstIterator and IntrusiveListIterator - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam ConstNodePointer is a const pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a const reference to IntrusiveListConstIterator on left-hand side of comparison operator - * \param [in] right is a const reference to IntrusiveListIterator on right-hand side of comparison operator - * - * \return true if iterators are not equal, false otherwise - */ - -template -inline bool operator!=(const IntrusiveListConstIterator& left, - const IntrusiveListIterator& right) -{ - return right != left; -} - -/** - * \brief IntrusiveList class is an intrusive circular doubly linked list. - * - * This class tries to provide an interface similar to std::list. - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; using different type than \a T can be used - * to break circular dependencies, because \a T must be fully defined to instantiate this class, but it is enough to - * forward declare \a U - it only needs to be fully defined to use member functions - */ - -template -class IntrusiveList -{ -public: - - /// const iterator of elements on the list - using const_iterator = IntrusiveListConstIterator; - - /// const reverse iterator of elements on the list - using const_reverse_iterator = std::reverse_iterator; - - /// const pointer to value linked in the list - using const_pointer = const U*; - - /// const reference to value linked in the list - using const_reference = const U&; - - /// iterator of elements on the list - using iterator = IntrusiveListIterator; - - /// reverse iterator of elements on the list - using reverse_iterator = std::reverse_iterator; - - /// pointer to value linked in the list - using pointer = U*; - - /// reference to value linked in the list - using reference = U&; - - /// value linked in the list - using value_type = U; - - /** - * \brief IntrusiveList's constructor - */ - - constexpr IntrusiveList() : - intrusiveListBase_{} - { - - } - - /** - * \return reference to last element on the list - */ - - reference back() - { - return *--end(); - } - - /** - * \return const reference to last element on the list - */ - - const_reference back() const - { - return *--end(); - } - - /** - * \return iterator of first element on the list - */ - - iterator begin() - { - return iterator{&intrusiveListBase_.begin()}; - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator begin() const - { - return const_iterator{&intrusiveListBase_.begin()}; - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator cbegin() const - { - return begin(); - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator cend() const - { - return end(); - } - - /** - * \brief Unlinks all elements from the list. - */ - - void clear() - { - intrusiveListBase_.clear(); - } - - /** - * \return true is the list is empty, false otherwise - */ - - bool empty() const - { - return intrusiveListBase_.empty(); - } - - /** - * \return iterator of "one past the last" element on the list - */ - - iterator end() - { - return iterator{&intrusiveListBase_.end()}; - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator end() const - { - return const_iterator{&intrusiveListBase_.end()}; - } - - /** - * \return reference to first element on the list - */ - - reference front() - { - return *begin(); - } - - /** - * \return const reference to first element on the list - */ - - const_reference front() const - { - return *begin(); - } - - /** - * \brief Unlinks the last element from the list. - */ - - void pop_back() - { - erase(--end()); - } - - /** - * \brief Unlinks the first element from the list. - */ - - void pop_front() - { - erase(begin()); - } - - /** - * \brief Links the element at the end of the list. - * - * \param [in] newElement is a reference to the element that will be linked in the list - */ - - void push_back(reference newElement) - { - insert(end(), newElement); - } - - /** - * \brief Links the element at the beginning of the list. - * - * \param [in] newElement is a reference to the element that will be linked in the list - */ - - void push_front(reference newElement) - { - insert(begin(), newElement); - } - - /** - * \brief Swaps contents with another list. - * - * \param [in] other is a reference to IntrusiveList with which contents of this list will be swapped - */ - - void swap(IntrusiveList& other) - { - intrusiveListBase_.swap(other.intrusiveListBase_); - } - - /** - * \brief Unlinks the element at \a position from the list. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is an iterator of the element that will be unlinked from the list - * - * \return iterator of the element that was following the element which was unlinked - */ - - static iterator erase(const iterator position) - { - auto& positionNode = (*position).*NodePointer; - auto& nextNode = internal::IntrusiveListBase::erase(positionNode); - return iterator{&nextNode}; - } - - /** - * \brief Links the element in the list before \a position. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is an iterator of the element before which \a newNode will be linked - * \param [in] newElement is a reference to the element that will be linked in the list - * - * \return iterator of \a newElement - */ - - static iterator insert(const iterator position, reference newElement) - { - static_assert(std::is_convertible::value == true, "U must be implicitly convertible to T!"); - - auto& positionNode = (*position).*NodePointer; - auto& newElementNode = newElement.*NodePointer; - internal::IntrusiveListBase::insert(positionNode, newElementNode); - return iterator{&newElementNode}; - } - - /** - * \brief Transfers the element from one list to another list before \a position. - * - * \note No instance of any list is needed for this operation. - * - * \param [in] position is an iterator of the element before which \a splicedElement will be linked - * \param [in] splicedElement is an iterator of the element that will be spliced from one list to another - */ - - static void splice(const iterator position, const iterator splicedElement) - { - auto& positionNode = (*position).*NodePointer; - auto& splicedElementNode = (*splicedElement).*NodePointer; - internal::IntrusiveListBase::splice(positionNode, splicedElementNode); - } - - IntrusiveList(const IntrusiveList&) = delete; - IntrusiveList(IntrusiveList&&) = default; - const IntrusiveList& operator=(const IntrusiveList&) = delete; - IntrusiveList& operator=(IntrusiveList&&) = delete; - -private: - - /// internal IntrusiveListBase object - internal::IntrusiveListBase intrusiveListBase_; -}; - -/** - * \brief Swaps contents of two lists. - * - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a reference to IntrusiveList with which contents of \a right will be swapped - * \param [in] right is a reference to IntrusiveList with which contents of \a left will be swapped - */ - -template -inline void swap(IntrusiveList& left, IntrusiveList& right) -{ - left.swap(right); -} - -} // namespace estd - -#endif // ESTD_INTRUSIVELIST_HPP_ diff --git a/include/estd/ReferenceHolder.hpp b/include/estd/ReferenceHolder.hpp deleted file mode 100644 index 2bb4602..0000000 --- a/include/estd/ReferenceHolder.hpp +++ /dev/null @@ -1,61 +0,0 @@ -/** - * \file - * \brief ReferenceHolder template class header. - * - * \author Copyright (C) 2014-2016 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_REFERENCEHOLDER_HPP_ -#define ESTD_REFERENCEHOLDER_HPP_ - -namespace estd -{ - -/** - * \brief ReferenceHolder template class is a ROMable holder of a reference. - * - * \tparam T is the type of reference held in the object - */ - -template -class ReferenceHolder -{ -public: - - /** - * \brief ReferenceHolder constructor. - * - * \param [in] reference is a reference that will be held by the object - */ - - constexpr explicit ReferenceHolder(T& reference) noexcept : - reference_{reference} - { - - } - - /// \return reference held by the object - constexpr operator T&() const noexcept - { - return reference_; - } - - /// \return reference held by the object - constexpr T& get() const noexcept - { - return reference_; - } - -private: - - /// reference held by the object - T& reference_; -}; - -} // namespace estd - -#endif // ESTD_REFERENCEHOLDER_HPP_ diff --git a/include/estd/ReverseAdaptor.hpp b/include/estd/ReverseAdaptor.hpp deleted file mode 100644 index 6738cac..0000000 --- a/include/estd/ReverseAdaptor.hpp +++ /dev/null @@ -1,83 +0,0 @@ -/** - * \file - * \brief ReverseAdaptor template class header. - * - * \author Copyright (C) 2014-2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_REVERSEADAPTOR_HPP_ -#define ESTD_REVERSEADAPTOR_HPP_ - -namespace estd -{ - -/** - * \brief ReverseAdaptor template class is an adaptor that "reverses" access to the container - * - * \tparam T is the type of container - */ - -template -class ReverseAdaptor -{ -public: - - /** - * \brief ReverseAdaptor's constructor. - * - * \param [in] container is a reference to container - */ - - constexpr explicit ReverseAdaptor(T& container) noexcept : - container_{container} - { - - } - - /** - * \return reverse_iterator to the beginning of "reversed" container (last element of original container) - */ - - typename T::reverse_iterator begin() const noexcept - { - return container_.rbegin(); - } - - /** - * \return reverse_iterator to the end of "reversed" container (before-the-first element of original container) - */ - - typename T::reverse_iterator end() const noexcept - { - return container_.rend(); - } - -private: - - /// reference to container - T& container_; -}; - -/** - * \brief Helper factory function to make ReverseAdaptor object with deduced template arguments - * - * \tparam T is the type of container - * - * \param [in] container is a reference to container - * - * \return ReverseAdaptor object - */ - -template -ReverseAdaptor makeReverseAdaptor(T& container) -{ - return ReverseAdaptor{container}; -} - -} // namespace estd - -#endif // ESTD_REVERSEADAPTOR_HPP_ diff --git a/include/estd/SortedIntrusiveForwardList.hpp b/include/estd/SortedIntrusiveForwardList.hpp deleted file mode 100644 index de35845..0000000 --- a/include/estd/SortedIntrusiveForwardList.hpp +++ /dev/null @@ -1,355 +0,0 @@ -/** - * \file - * \brief SortedIntrusiveForwardList template class header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_SORTEDINTRUSIVEFORWARDLIST_HPP_ -#define ESTD_SORTEDINTRUSIVEFORWARDLIST_HPP_ - -#include "estd/IntrusiveForwardList.hpp" - -#include - -namespace estd -{ - -/** - * \brief SortedIntrusiveForwardList class is an IntrusiveForwardList with sorted elements - * - * This class tries to provide an interface similar to std::forward_list. - * - * \note The elements are sorted as long as the user does not modify the contents. - * - * \tparam Compare is a type of functor used for comparison, std::less results in descending order, std::greater - in - * ascending order - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; using different type than \a T can be used - * to break circular dependencies, because \a T must be fully defined to instantiate this class, but it is enough to - * forward declare \a U - it only needs to be fully defined to use member functions - */ - -template -class SortedIntrusiveForwardList -{ -public: - - /// unsorted intrusive forward list used internally - using UnsortedIntrusiveForwardList = IntrusiveForwardList; - - /// const iterator of elements on the list - using const_iterator = typename UnsortedIntrusiveForwardList::const_iterator; - - /// const pointer to value linked in the list - using const_pointer = typename UnsortedIntrusiveForwardList::const_pointer; - - /// const reference to value linked in the list - using const_reference = typename UnsortedIntrusiveForwardList::const_reference; - - /// iterator of elements on the list - using iterator = typename UnsortedIntrusiveForwardList::iterator; - - /// pointer to value linked in the list - using pointer = typename UnsortedIntrusiveForwardList::pointer; - - /// reference to value linked in the list - using reference = typename UnsortedIntrusiveForwardList::reference; - - /// value linked in the list - using value_type = typename UnsortedIntrusiveForwardList::value_type; - - /** - * \brief SortedIntrusiveForwardList's constructor - * - * \param [in] compare is a reference to Compare object used to copy-construct internal comparison functor - */ - - constexpr SortedIntrusiveForwardList(const Compare& compare = Compare{}) : - implementation_{compare} - { - - } - - /** - * \return iterator of "one before the first" element on the list - */ - - iterator before_begin() - { - return implementation_.intrusiveForwardList.before_begin(); - } - - /** - * \return const iterator of "one before the first" element on the list - */ - - const_iterator before_begin() const - { - return implementation_.intrusiveForwardList.before_begin(); - } - - /** - * \return iterator of first element on the list - */ - - iterator begin() - { - return implementation_.intrusiveForwardList.begin(); - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator begin() const - { - return implementation_.intrusiveForwardList.begin(); - } - - /** - * \return const iterator of "one before the first" element on the list - */ - - const_iterator cbefore_begin() const - { - return implementation_.intrusiveForwardList.cbefore_begin(); - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator cbegin() const - { - return implementation_.intrusiveForwardList.cbegin(); - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator cend() const - { - return implementation_.intrusiveForwardList.cend(); - } - - /** - * \brief Unlinks all elements from the list. - */ - - void clear() - { - implementation_.intrusiveForwardList.clear(); - } - - /** - * \return true is the list is empty, false otherwise - */ - - bool empty() const - { - return implementation_.intrusiveForwardList.empty(); - } - - /** - * \return iterator of "one past the last" element on the list - */ - - iterator end() - { - return implementation_.intrusiveForwardList.end(); - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator end() const - { - return implementation_.intrusiveForwardList.end(); - } - - /** - * \return reference to first element on the list - */ - - reference front() - { - return implementation_.intrusiveForwardList.front(); - } - - /** - * \return const reference to first element on the list - */ - - const_reference front() const - { - return implementation_.intrusiveForwardList.front(); - } - - /** - * \brief Links the element in the list, keeping it sorted. - * - * \param [in] newElement is a reference to the element that will be linked in the list - * - * \return iterator of \a newElement - */ - - iterator insert(reference newElement) - { - return UnsortedIntrusiveForwardList::insert_after(implementation_.findInsertPositionBefore(newElement), - newElement); - } - - /** - * \brief Unlinks the first element from the list. - */ - - void pop_front() - { - implementation_.intrusiveForwardList.pop_front(); - } - - /** - * \brief Transfers the element from another list to this one, keeping it sorted. - * - * \param [in] beforeSplicedElement is an iterator of the element preceding the one which will be spliced from - * another list to this one - */ - - void splice_after(const iterator beforeSplicedElement) - { - const auto splicedElement = std::next(beforeSplicedElement); - UnsortedIntrusiveForwardList::splice_after(implementation_.findInsertPositionBefore(*splicedElement), - beforeSplicedElement); - } - - /** - * \brief Swaps contents with another list. - * - * \param [in] other is a reference to SortedIntrusiveForwardList with which contents of this list will be swapped - */ - - void swap(SortedIntrusiveForwardList& other) - { - implementation_.swap(other.implementation_); - } - - /** - * \brief Unlinks the element following \a position from the list. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is an iterator preceding the element which will be unlinked from the list - * - * \return iterator of the element that was following the element which was unlinked - */ - - static iterator erase_after(const iterator position) - { - return UnsortedIntrusiveForwardList::erase_after(position); - } - - SortedIntrusiveForwardList(const SortedIntrusiveForwardList&) = delete; - SortedIntrusiveForwardList(SortedIntrusiveForwardList&&) = default; - const SortedIntrusiveForwardList& operator=(const SortedIntrusiveForwardList&) = delete; - SortedIntrusiveForwardList& operator=(SortedIntrusiveForwardList&&) = delete; - -private: - - /// Implementation struct is used primarily for "Empty Base Optimization" with \a Compare type - struct Implementation : public Compare - { - /** - * \brief Implementation's constructor - * - * \param [in] comparee is a reference to Compare object used to copy-construct internal comparison functor - */ - - constexpr Implementation(const Compare& comparee) : - Compare{comparee}, - intrusiveForwardList{} - { - - } - - /** - * \brief Finds insert position "before" the position that satisfies sorting criteria. - * - * \param [in] newElement is a const reference to new element that is going to be inserted/spliced - * - * \return iterator for which Compare's function call operator of next value and \a newElement returns true. - */ - - iterator findInsertPositionBefore(const_reference newElement) - { - auto it = intrusiveForwardList.before_begin(); - auto next = intrusiveForwardList.begin(); - const auto end = intrusiveForwardList.end(); - - while (next != end && this->Compare::operator()(*next, newElement) == false) - { - it = next; - ++next; - } - - return it; - } - - /** - * \brief Swaps contents with another instance. - * - * \param [in] other is a reference to Implementation with which contents of this instance will be swapped - */ - - void swap(Implementation& other) - { - intrusiveForwardList.swap(other.intrusiveForwardList); - using std::swap; - swap(static_cast(*this), static_cast(other)); - } - - Implementation(const Implementation&) = delete; - Implementation(Implementation&&) = default; - const Implementation& operator=(const Implementation&) = delete; - Implementation& operator=(Implementation&&) = delete; - - /// internal unsorted IntrusiveForwardList - UnsortedIntrusiveForwardList intrusiveForwardList; - }; - - /// internal Implementation object - unsorted IntrusiveForwardList and Compare instance - Implementation implementation_; -}; - -/** - * \brief Swaps contents of two lists. - * - * \tparam Compare is a type of functor used for comparison, std::less results in descending order, std::greater - in - * ascending order - * \tparam T is the type that has the IntrusiveForwardListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveForwardListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a reference to SortedIntrusiveForwardList with which contents of \a right will be swapped - * \param [in] right is a reference to SortedIntrusiveForwardList with which contents of \a left will be swapped - */ - -template -inline void swap(SortedIntrusiveForwardList& left, - SortedIntrusiveForwardList& right) -{ - left.swap(right); -} - -} // namespace estd - -#endif // ESTD_SORTEDINTRUSIVEFORWARDLIST_HPP_ diff --git a/include/estd/SortedIntrusiveList.hpp b/include/estd/SortedIntrusiveList.hpp deleted file mode 100644 index 1d65ee3..0000000 --- a/include/estd/SortedIntrusiveList.hpp +++ /dev/null @@ -1,353 +0,0 @@ -/** - * \file - * \brief SortedIntrusiveList template class header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_SORTEDINTRUSIVELIST_HPP_ -#define ESTD_SORTEDINTRUSIVELIST_HPP_ - -#include "estd/IntrusiveList.hpp" - -#include - -namespace estd -{ - -/** - * \brief SortedIntrusiveList class is an IntrusiveList with sorted elements - * - * This class tries to provide an interface similar to std::list. - * - * \note The elements are sorted as long as the user does not modify the contents. - * - * \tparam Compare is a type of functor used for comparison, std::less results in descending order, std::greater - in - * ascending order - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; using different type than \a T can be used - * to break circular dependencies, because \a T must be fully defined to instantiate this class, but it is enough to - * forward declare \a U - it only needs to be fully defined to use member functions - */ - -template -class SortedIntrusiveList -{ -public: - - /// unsorted intrusive list used internally - using UnsortedIntrusiveList = IntrusiveList; - - /// const iterator of elements on the list - using const_iterator = typename UnsortedIntrusiveList::const_iterator; - - /// const reverse iterator of elements on the list - using const_reverse_iterator = typename UnsortedIntrusiveList::const_reverse_iterator; - - /// const pointer to value linked in the list - using const_pointer = typename UnsortedIntrusiveList::const_pointer; - - /// const reference to value linked in the list - using const_reference = typename UnsortedIntrusiveList::const_reference; - - /// iterator of elements on the list - using iterator = typename UnsortedIntrusiveList::iterator; - - /// reverse iterator of elements on the list - using reverse_iterator = typename UnsortedIntrusiveList::reverse_iterator; - - /// pointer to value linked in the list - using pointer = typename UnsortedIntrusiveList::pointer; - - /// reference to value linked in the list - using reference = typename UnsortedIntrusiveList::reference; - - /// value linked in the list - using value_type = typename UnsortedIntrusiveList::value_type; - - /** - * \brief SortedIntrusiveList's constructor - * - * \param [in] compare is a reference to Compare object used to copy-construct internal comparison functor - */ - - constexpr SortedIntrusiveList(const Compare& compare = Compare{}) : - implementation_{compare} - { - - } - - /** - * \return reference to last element on the list - */ - - reference back() - { - return implementation_.intrusiveList.back(); - } - - /** - * \return const reference to last element on the list - */ - - const_reference back() const - { - return implementation_.intrusiveList.back(); - } - - /** - * \return iterator of first element on the list - */ - - iterator begin() - { - return implementation_.intrusiveList.begin(); - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator begin() const - { - return implementation_.intrusiveList.begin(); - } - - /** - * \return const iterator of first element on the list - */ - - const_iterator cbegin() const - { - return implementation_.intrusiveList.cbegin(); - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator cend() const - { - return implementation_.intrusiveList.cend(); - } - - /** - * \brief Unlinks all elements from the list. - */ - - void clear() - { - implementation_.intrusiveList.clear(); - } - - /** - * \return true is the list is empty, false otherwise - */ - - bool empty() const - { - return implementation_.intrusiveList.empty(); - } - - /** - * \return iterator of "one past the last" element on the list - */ - - iterator end() - { - return implementation_.intrusiveList.end(); - } - - /** - * \return const iterator of "one past the last" element on the list - */ - - const_iterator end() const - { - return implementation_.intrusiveList.end(); - } - - /** - * \return reference to first element on the list - */ - - reference front() - { - return implementation_.intrusiveList.front(); - } - - /** - * \return const reference to first element on the list - */ - - const_reference front() const - { - return implementation_.intrusiveList.front(); - } - - /** - * \brief Links the element in the list, keeping it sorted. - * - * \param [in] newElement is a reference to the element that will be linked in the list - * - * \return iterator of \a newElement - */ - - iterator insert(reference newElement) - { - return UnsortedIntrusiveList::insert(implementation_.findInsertPosition(newElement), newElement); - } - - /** - * \brief Unlinks the last element from the list. - */ - - void pop_back() - { - implementation_.intrusiveList.pop_back(); - } - - /** - * \brief Unlinks the first element from the list. - */ - - void pop_front() - { - implementation_.intrusiveList.pop_front(); - } - - /** - * \brief Transfers the element from another list to this one, keeping it sorted. - * - * \param [in] splicedElement is an iterator of the element that will be spliced from another list to this one - */ - - void splice(const iterator splicedElement) - { - UnsortedIntrusiveList::splice(implementation_.findInsertPosition(*splicedElement), splicedElement); - } - - /** - * \brief Swaps contents with another list. - * - * \param [in] other is a reference to SortedIntrusiveList with which contents of this list will be swapped - */ - - void swap(SortedIntrusiveList& other) - { - implementation_.swap(other.implementation_); - } - - /** - * \brief Unlinks the element at \a position from the list. - * - * \note No instance of the list is needed for this operation. - * - * \param [in] position is an iterator of the element that will be unlinked from the list - * - * \return iterator of the element that was following the element which was unlinked - */ - - static iterator erase(const iterator position) - { - return UnsortedIntrusiveList::erase(position); - } - - SortedIntrusiveList(const SortedIntrusiveList&) = delete; - SortedIntrusiveList(SortedIntrusiveList&&) = default; - const SortedIntrusiveList& operator=(const SortedIntrusiveList&) = delete; - SortedIntrusiveList& operator=(SortedIntrusiveList&&) = delete; - -private: - - /// Implementation struct is used primarily for "Empty Base Optimization" with \a Compare type - struct Implementation : public Compare - { - /** - * \brief Implementation's constructor - * - * \param [in] comparee is a reference to Compare object used to copy-construct internal comparison functor - */ - - constexpr Implementation(const Compare& comparee) : - Compare{comparee}, - intrusiveList{} - { - - } - - /** - * \brief Finds insert position that satisfies sorting criteria. - * - * \param [in] newElement is a const reference to new element that is going to be inserted/spliced - * - * \return iterator for which Compare's function call operator of dereferenced value and \a newElement returns - * true. - */ - - iterator findInsertPosition(const_reference newElement) - { - return std::find_if(intrusiveList.begin(), intrusiveList.end(), - [this, &newElement](const_reference& element) -> bool - { - return this->Compare::operator()(element, newElement); - } - ); - } - - /** - * \brief Swaps contents with another instance. - * - * \param [in] other is a reference to Implementation with which contents of this instance will be swapped - */ - - void swap(Implementation& other) - { - intrusiveList.swap(other.intrusiveList); - using std::swap; - swap(static_cast(*this), static_cast(other)); - } - - Implementation(const Implementation&) = delete; - Implementation(Implementation&&) = default; - const Implementation& operator=(const Implementation&) = delete; - Implementation& operator=(Implementation&&) = delete; - - /// internal unsorted IntrusiveList - UnsortedIntrusiveList intrusiveList; - }; - - /// internal Implementation object - unsorted IntrusiveList and Compare instance - Implementation implementation_; -}; - -/** - * \brief Swaps contents of two lists. - * - * \tparam Compare is a type of functor used for comparison, std::less results in descending order, std::greater - in - * ascending order - * \tparam T is the type that has the IntrusiveListNode variable - * \tparam NodePointer is a pointer-to-member to IntrusiveListNode variable in \a T - * \tparam U is the type that will be stored on the list; it can be different from \a T, but must be implicitly - * convertible to \a T (so usually a type derived from \a T); default - \a T; - * - * \param [in] left is a reference to SortedIntrusiveList with which contents of \a right will be swapped - * \param [in] right is a reference to SortedIntrusiveList with which contents of \a left will be swapped - */ - -template -inline void swap(SortedIntrusiveList& left, - SortedIntrusiveList& right) -{ - left.swap(right); -} - -} // namespace estd - -#endif // ESTD_SORTEDINTRUSIVELIST_HPP_ diff --git a/include/estd/TypeErasedFunctor.hpp b/include/estd/TypeErasedFunctor.hpp deleted file mode 100644 index a19d59b..0000000 --- a/include/estd/TypeErasedFunctor.hpp +++ /dev/null @@ -1,99 +0,0 @@ -/** - * \file - * \brief TypeErasedFunctor template class header - * - * \author Copyright (C) 2014-2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_TYPEERASEDFUNCTOR_HPP_ -#define ESTD_TYPEERASEDFUNCTOR_HPP_ - -namespace estd -{ - -template -class TypeErasedFunctor; - -/** - * \brief TypeErasedFunctor class is an interface for type-erased functors. - * - * Overload with const operator()(). - * - * \tparam R is the type returned by TypeErasedFunctor::operator()() const - * \tparam Args are the types of arguments for TypeErasedFunctor::operator()() const - */ - -template -class TypeErasedFunctor -{ -public: - - /** - * \brief Function call operator of TypeErasedFunctor - * - * \param [in,out] args are arguments for derived function - * - * \return value returned by derived function - */ - - virtual R operator()(Args... args) const = 0; - -protected: - - /** - * \brief TypeErasedFunctor's destructor - * - * \note Polymorphic objects of TypeErasedFunctor type must not be deleted via pointer/reference - */ - - ~TypeErasedFunctor() - { - - } -}; - -/** - * \brief TypeErasedFunctor class is an interface for type-erased functors. - * - * Overload with non-const operator()(). - * - * \tparam R is the type returned by TypeErasedFunctor::operator()() - * \tparam Args are the types of arguments for TypeErasedFunctor::operator()() - */ - -template -class TypeErasedFunctor -{ -public: - - /** - * \brief Function call operator of TypeErasedFunctor - * - * \param [in,out] args are arguments for derived function - * - * \return value returned by derived function - */ - - virtual R operator()(Args... args) = 0; - -protected: - - /** - * \brief TypeErasedFunctor's destructor - * - * \note Polymorphic objects of TypeErasedFunctor type must not be deleted via pointer/reference - */ - - ~TypeErasedFunctor() - { - - } -}; - -} // namespace estd - -#endif // ESTD_TYPEERASEDFUNCTOR_HPP_ diff --git a/include/estd/apply.hpp b/include/estd/apply.hpp deleted file mode 100644 index 743cce6..0000000 --- a/include/estd/apply.hpp +++ /dev/null @@ -1,73 +0,0 @@ -/** - * \file - * \brief apply() header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_APPLY_HPP_ -#define ESTD_APPLY_HPP_ - -#include "estd/IntegerSequence.hpp" -#include "estd/invoke.hpp" - -#include - -namespace estd -{ - -namespace internal -{ - -/** - * \brief Implementation of apply() - * - * \tparam Function is the function object that will be invoked - * \tparam Tuple is the type of tuple of arguments - * \tparam Indexes is a sequence of std::size_t indexes for \a Tuple - * - * \param [in] function is the function object that will be executed - * \param [in] tuple is the tuple of arguments - * - * \return value returned by call to \a function with arguments from \a tuple - */ - -template -constexpr auto apply(Function&& function, Tuple&& tuple, estd::IndexSequence) -> - decltype(estd::invoke(std::forward(function), std::get(std::forward(tuple))...)) -{ - return estd::invoke(std::forward(function), std::get(std::forward(tuple))...); -} - -} // namespace internal - -/** - * \brief Invokes callable object with a tuple of arguments. - * - * Implementation inspired by http://en.cppreference.com/w/cpp/experimental/apply - * - * \tparam Function is the function object that will be invoked - * \tparam Tuple is the type of tuple of arguments - * - * \param [in] function is the function object that will be executed - * \param [in] tuple is the tuple of arguments - * - * \return value returned by call to \a function with arguments from \a tuple - */ - -template -constexpr auto apply(Function&& function, Tuple&& tuple) -> - decltype(internal::apply(std::forward(function), std::forward(tuple), - estd::MakeIndexSequence::type>{}>{})) -{ - return internal::apply(std::forward(function), std::forward(tuple), - estd::MakeIndexSequence::type>{}>{}); -} - -} // namespace estd - -#endif // ESTD_APPLY_HPP_ diff --git a/include/estd/invoke.hpp b/include/estd/invoke.hpp deleted file mode 100644 index bdac1a0..0000000 --- a/include/estd/invoke.hpp +++ /dev/null @@ -1,147 +0,0 @@ -/** - * \file - * \brief invoke() header - * - * \author Copyright (C) 2015 Kamil Szczygiel http://www.distortec.com http://www.freddiechopin.info - * - * \par License - * This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not - * distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. - */ - -#ifndef ESTD_INVOKE_HPP_ -#define ESTD_INVOKE_HPP_ - -#include - -namespace estd -{ - -namespace internal -{ - -/** - * \brief Implementation of invoke() for function objects - * - * \tparam Function is the function object that will be executed - * \tparam Args are the arguments for \a Function - * - * \param [in] function is the function object that will be executed - * \param [in] args are arguments for \a function - * - * \return value returned by call to \a function with \a args - */ - -template -inline auto invoke(Function&& function, Args&&... args) -> - decltype(std::forward(function)(std::forward(args)...)) -{ - return std::forward(function)(std::forward(args)...); -} - -/** - * \brief Implementation of invoke() for member functions - * - * \tparam T is the type returned by call to member function - * \tparam Base is the type of base class - * \tparam Derived is the type of derived class - * \tparam Args are the arguments for member function - * - * \param [in] memberFunction is a pointer to member function of \a object that will be executed - * \param [in] object is an object or a reference to object on which \a memberFunction will be executed - * \param [in] args are arguments for \a memberFunction - * - * \return value returned by call to \a memberFunction on \a object with \a args - */ - -template -inline auto invoke(T Base::* memberFunction, Derived&& object, Args&&... args) -> - decltype((std::forward(object).*memberFunction)(std::forward(args)...)) -{ - return (std::forward(object).*memberFunction)(std::forward(args)...); -} - -/** - * \brief Implementation of invoke() for member functions - * - * \tparam MemberFunction is the type or pointer to member function - * \tparam Pointer is the type of pointer to object - * \tparam Args are the arguments for member function - * - * \param [in] memberFunction is a pointer to member function of object that will be executed - * \param [in] pointer is a pointer to object on which \a memberFunction will be executed - * \param [in] args are arguments for \a memberFunction - * - * \return value returned by call to \a memberFunction on \a (*pointer) with \a args - */ - -template -inline auto invoke(MemberFunction memberFunction, Pointer&& pointer, Args&&... args) -> - decltype(((*std::forward(pointer)).*memberFunction)(std::forward(args)...)) -{ - return ((*std::forward(pointer)).*memberFunction)(std::forward(args)...); -} - -/** - * \brief Implementation of invoke() for data members - * - * \tparam T is the type of data member - * \tparam Base is the type of base class - * \tparam Derived is the type of derived class - * - * \param [in] dataMember is a pointer to data member of \a object that will be accessed - * \param [in] object is an object or a reference to object in which \a dataMember will be accessed - * - * \return value returned by access to \a dataMember in \a object - */ - -template -inline auto invoke(T Base::* dataMember, Derived&& object) -> decltype(std::forward(object).*dataMember) -{ - return std::forward(object).*dataMember; -} - -/** - * \brief Implementation of invoke() for data members - * - * \tparam DataMember is the type or pointer to data member - * \tparam Pointer is the type of pointer to object - * - * \param [in] dataMember is a pointer to data member of object that will be accessed - * \param [in] pointer is a pointer to object in which \a dataMember will be accessed - * - * \return value returned by access to \a dataMember in \a (*pointer) - */ - -template -inline auto invoke(DataMember dataMember, Pointer&& pointer) -> decltype((*std::forward(pointer)).*dataMember) -{ - return (*std::forward(pointer)).*dataMember; -} - -} // namespace internal - -/** - * \brief Invokes callable object in an appropriate way. - * - * Implementation inspired by http://en.cppreference.com/w/cpp/utility/functional/invoke - * - * \tparam Function is the function object that will be executed - * \tparam Args are the arguments for \a Function - * - * \param [in] function is the function object that will be executed - * \param [in] args are arguments for \a function - * - * \return value returned by call to \a function with \a args - */ - -template -auto invoke(Function&& function, Args&&... args) -> - decltype(internal::invoke(std::forward(function), std::forward(args)...)) -{ - return internal::invoke(std::forward(function), std::forward(args)...); -} - -} // namespace estd - -#endif // ESTD_INVOKE_HPP_ -- cgit v1.2.3