| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef LIB_ESCHER_UTIL_INTRUSIVE_LIST_H_ |
| #define LIB_ESCHER_UTIL_INTRUSIVE_LIST_H_ |
| |
| #ifndef NDEBUG |
| #include "lib/fxl/logging.h" |
| #endif |
| |
| namespace escher { |
| |
| // Base class for items that can be stored in an IntrusiveList. |
| // |
| // TODO(SCN-693): A fancier implementation would make next/prev private. Until |
| // then, we trust Escher clients to not frob these pointers. |
| template <typename T> |
| struct IntrusiveListItem { |
| T* prev = nullptr; |
| T* next = nullptr; |
| |
| #ifndef NDEBUG |
| void* list = nullptr; |
| #endif |
| }; |
| |
| template <typename T> |
| class IntrusiveList { |
| public: |
| ~IntrusiveList() { Clear(); } |
| |
| void Clear() { |
| IntrusiveListItem<T>* current = head_; |
| while (current) { |
| #ifndef NDEBUG |
| FXL_DCHECK(current->list == this); |
| current->list = nullptr; |
| #endif |
| IntrusiveListItem<T>* next = current->next; |
| current->next = nullptr; |
| current->prev = nullptr; |
| current = next; |
| } |
| head_ = nullptr; |
| } |
| |
| class Iterator { |
| public: |
| friend class IntrusiveList<T>; |
| Iterator(T* item) : item_(item) {} |
| |
| Iterator() = default; |
| |
| explicit operator bool() const { return item_ != nullptr; } |
| |
| bool operator==(const Iterator& other) const { |
| return item_ == other.item_; |
| } |
| bool operator!=(const Iterator& other) const { |
| return item_ != other.item_; |
| } |
| |
| T& operator*() { return *static_cast<T*>(item_); } |
| const T& operator*() const { return *static_cast<T*>(item_); } |
| |
| T* get() { return static_cast<T*>(item_); } |
| const T* get() const { return static_cast<T*>(item_); } |
| |
| T* operator->() { return get(); } |
| const T* operator->() const { return get(); } |
| |
| // Pre-increment. |
| Iterator operator++() { |
| item_ = item_->next; |
| return *this; |
| } |
| |
| // Post-increment. |
| Iterator operator++(int) { |
| Iterator result = *this; |
| ++*this; |
| return result; |
| } |
| |
| private: |
| IntrusiveListItem<T>* item_ = nullptr; |
| }; |
| |
| Iterator begin() { return Iterator(head_); } |
| |
| Iterator end() { return Iterator(); } |
| |
| bool IsEmpty() const { return head_ == nullptr; } |
| |
| // Return iterator following the last removed item. |
| Iterator Erase(Iterator it) { |
| auto item = it.get(); |
| return Iterator(item ? Erase(item) : nullptr); |
| } |
| |
| // Return the list item that follows the erased item. |
| T* Erase(T* item) { |
| #ifndef NDEBUG |
| FXL_DCHECK(item); |
| FXL_DCHECK(item->list == this); |
| item->list = nullptr; |
| #endif |
| |
| auto* next = item->next; |
| auto* prev = item->prev; |
| |
| if (prev) { |
| prev->next = next; |
| } else { |
| head_ = next; |
| } |
| |
| if (next) { |
| next->prev = prev; |
| } |
| |
| item->next = item->prev = nullptr; |
| |
| return next; |
| } |
| |
| // If the list is not empty, erase and return the first item. Otherwise, |
| // return nullptr. |
| T* PopFront() { |
| if (head_) { |
| auto result = head_; |
| Erase(head_); |
| return result; |
| } else { |
| return nullptr; |
| } |
| } |
| |
| void InsertFront(Iterator it) { |
| auto* item = it.get(); |
| if (head_) |
| head_->prev = item; |
| |
| item->next = head_; |
| item->prev = nullptr; |
| head_ = item; |
| |
| #ifndef NDEBUG |
| FXL_DCHECK(item->list == nullptr); |
| item->list = this; |
| #endif |
| } |
| |
| void MoveToFront(IntrusiveList<T>& other, Iterator it) { |
| other.Erase(it); |
| InsertFront(it); |
| } |
| |
| private: |
| T* head_ = nullptr; |
| }; |
| |
| } // namespace escher |
| |
| #endif // LIB_ESCHER_UTIL_INTRUSIVE_LIST_H_ |