/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- * vim: set ts=8 sts=2 et sw=2 tw=80: * 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 ds_SinglyLinkedList_h #define ds_SinglyLinkedList_h #include "mozilla/Assertions.h" #include <utility> namespace js { /* * Circular singly linked list that requires only one word per element and for * the list itself. * * Requires T has field |T::next| for the link pointer. */ template <typename T> class SinglyLinkedList { T* last_ = nullptr; public: SinglyLinkedList() { static_assert(std::is_same_v<decltype(T::next), T*>, "SinglyLinkedList requires T has a next field of type T*"); MOZ_ASSERT(isEmpty()); } SinglyLinkedList(T* first, T* last) : last_(last) { MOZ_ASSERT(!last_->next); last_->next = first; } // It's not possible for elements to be present in more than one list, so copy // operations are not provided. SinglyLinkedList(const SinglyLinkedList& other) = delete; SinglyLinkedList& operator=(const SinglyLinkedList& other) = delete; SinglyLinkedList(SinglyLinkedList&& other) { std::swap(last_, other.last_); MOZ_ASSERT(other.isEmpty()); } SinglyLinkedList& operator=(SinglyLinkedList&& other) { MOZ_ASSERT(isEmpty()); return *new (this) SinglyLinkedList(std::move(other)); } ~SinglyLinkedList() { MOZ_ASSERT(isEmpty()); } bool isEmpty() const { return !last_; } // These return nullptr if the list is empty. T* first() const { if (isEmpty()) { return nullptr; } T* element = last_->next; MOZ_ASSERT(element); return element; } T* last() const { return last_; } T* popFront() { MOZ_ASSERT(!isEmpty()); T* element = last_->next; if (element == last_) { last_ = nullptr; } else { last_->next = element->next; } element->next = nullptr; return element; } // popBack cannot be implemented in constant time for a singly linked list. void pushFront(T* element) { MOZ_ASSERT(!element->next); if (isEmpty()) { element->next = element; last_ = element; return; } element->next = last_->next; last_->next = element; } void pushBack(T* element) { pushFront(element); moveFrontToBack(); } void moveFrontToBack() { MOZ_ASSERT(!isEmpty()); last_ = last_->next; } void append(SinglyLinkedList&& other) { if (other.isEmpty()) { return; } if (isEmpty()) { new (this) SinglyLinkedList(std::move(other)); return; } T* firstElement = first(); last()->next = other.first(); other.last()->next = firstElement; last_ = other.last(); other.last_ = nullptr; } // template <typename T> class Iterator { T* i = nullptr; T* last = nullptr; public: explicit Iterator(const SinglyLinkedList& list) : i(list.first()), last(list.last()) {} bool done() const { return !i; } void next() { MOZ_ASSERT(!done()); i = i == last ? nullptr : i->next; } T* get() const { MOZ_ASSERT(!done()); return i; } T& operator*() const { return *get(); } T* operator->() const { return get(); } }; Iterator iter() const { return Iterator(*this); } // Extracts a non-circular linked list and clears this object. T* release() { if (isEmpty()) { return nullptr; } T* list = first(); MOZ_ASSERT(last_->next); last_->next = nullptr; last_ = nullptr; return list; } }; } /* namespace js */ #endif /* ds_SinglyLinkedList_h */