diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/util-inl.h | 102 | ||||
-rw-r--r-- | src/util.h | 63 |
2 files changed, 165 insertions, 0 deletions
diff --git a/src/util-inl.h b/src/util-inl.h index 6e962feffa..75bdb4784a 100644 --- a/src/util-inl.h +++ b/src/util-inl.h @@ -5,6 +5,108 @@ namespace node { +template <typename T> +ListNode<T>::ListNode() : prev_(this), next_(this) {} + +template <typename T> +ListNode<T>::~ListNode() { + Remove(); +} + +template <typename T> +void ListNode<T>::Remove() { + prev_->next_ = next_; + next_->prev_ = prev_; + prev_ = this; + next_ = this; +} + +template <typename T> +bool ListNode<T>::IsEmpty() const { + return prev_ == this; +} + +template <typename T, ListNodeMember(T) M> +ListHead<T, M>::Iterator::Iterator(ListNode<T>* node) : node_(node) {} + +template <typename T, ListNodeMember(T) M> +T* ListHead<T, M>::Iterator::operator*() const { + return ContainerOf(M, node_); +} + +template <typename T, ListNodeMember(T) M> +const typename ListHead<T, M>::Iterator& +ListHead<T, M>::Iterator::operator++() { + node_ = node_->next_; + return *this; +} + +template <typename T, ListNodeMember(T) M> +bool ListHead<T, M>::Iterator::operator!=(const Iterator& that) const { + return node_ != that.node_; +} + +template <typename T, ListNodeMember(T) M> +ListHead<T, M>::~ListHead() { + while (IsEmpty() == false) + head_.next_->Remove(); +} + +template <typename T, ListNodeMember(T) M> +void ListHead<T, M>::MoveBack(ListHead* that) { + if (IsEmpty()) + return; + ListNode<T>* to = &that->head_; + head_.next_->prev_ = to->prev_; + to->prev_->next_ = head_.next_; + head_.prev_->next_ = to; + to->prev_ = head_.prev_; + head_.prev_ = &head_; + head_.next_ = &head_; +} + +template <typename T, ListNodeMember(T) M> +void ListHead<T, M>::PushBack(T* element) { + ListNode<T>* that = &(element->*M); + head_.prev_->next_ = that; + that->prev_ = head_.prev_; + that->next_ = &head_; + head_.prev_ = that; +} + +template <typename T, ListNodeMember(T) M> +void ListHead<T, M>::PushFront(T* element) { + ListNode<T>* that = &(element->*M); + head_.next_->prev_ = that; + that->prev_ = &head_; + that->next_ = head_.next_; + head_.next_ = that; +} + +template <typename T, ListNodeMember(T) M> +bool ListHead<T, M>::IsEmpty() const { + return head_.IsEmpty(); +} + +template <typename T, ListNodeMember(T) M> +T* ListHead<T, M>::PopFront() { + if (IsEmpty()) + return nullptr; + ListNode<T>* node = head_.next_; + node->Remove(); + return ContainerOf(M, node); +} + +template <typename T, ListNodeMember(T) M> +typename ListHead<T, M>::Iterator ListHead<T, M>::begin() const { + return Iterator(head_.next_); +} + +template <typename T, ListNodeMember(T) M> +typename ListHead<T, M>::Iterator ListHead<T, M>::end() const { + return Iterator(const_cast<ListNode<T>*>(&head_)); +} + template <typename Inner, typename Outer> ContainerOfHelper<Inner, Outer>::ContainerOfHelper(Inner Outer::*field, Inner* pointer) diff --git a/src/util.h b/src/util.h index e0fa0fd009..5742252688 100644 --- a/src/util.h +++ b/src/util.h @@ -45,6 +45,69 @@ namespace node { #define UNREACHABLE() abort() +// TAILQ-style intrusive list node. +template <typename T> +class ListNode; + +template <typename T> +using ListNodeMember = ListNode<T> T::*; + +// VS 2013 doesn't understand dependent templates. +#ifdef _MSC_VER +#define ListNodeMember(T) ListNodeMember +#else +#define ListNodeMember(T) ListNodeMember<T> +#endif + +// TAILQ-style intrusive list head. +template <typename T, ListNodeMember(T) M> +class ListHead; + +template <typename T> +class ListNode { + public: + inline ListNode(); + inline ~ListNode(); + inline void Remove(); + inline bool IsEmpty() const; + + private: + template <typename U, ListNodeMember(U) M> friend class ListHead; + ListNode* prev_; + ListNode* next_; + DISALLOW_COPY_AND_ASSIGN(ListNode); +}; + +template <typename T, ListNodeMember(T) M> +class ListHead { + public: + class Iterator { + public: + inline T* operator*() const; + inline const Iterator& operator++(); + inline bool operator!=(const Iterator& that) const; + + private: + friend class ListHead; + inline explicit Iterator(ListNode<T>* node); + ListNode<T>* node_; + }; + + inline ListHead() = default; + inline ~ListHead(); + inline void MoveBack(ListHead* that); + inline void PushBack(T* element); + inline void PushFront(T* element); + inline bool IsEmpty() const; + inline T* PopFront(); + inline Iterator begin() const; + inline Iterator end() const; + + private: + ListNode<T> head_; + DISALLOW_COPY_AND_ASSIGN(ListHead); +}; + // The helper is for doing safe downcasts from base types to derived types. template <typename Inner, typename Outer> class ContainerOfHelper { |