jpayne@69: // Copyright (c) 2021 Cloudflare, Inc. and contributors
jpayne@69: // Licensed under the MIT License:
jpayne@69: //
jpayne@69: // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69: // of this software and associated documentation files (the "Software"), to deal
jpayne@69: // in the Software without restriction, including without limitation the rights
jpayne@69: // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69: // copies of the Software, and to permit persons to whom the Software is
jpayne@69: // furnished to do so, subject to the following conditions:
jpayne@69: //
jpayne@69: // The above copyright notice and this permission notice shall be included in
jpayne@69: // all copies or substantial portions of the Software.
jpayne@69: //
jpayne@69: // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69: // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69: // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69: // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69: // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69: // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69: // THE SOFTWARE.
jpayne@69: 
jpayne@69: #pragma once
jpayne@69: 
jpayne@69: #include "common.h"
jpayne@69: 
jpayne@69: KJ_BEGIN_HEADER
jpayne@69: 
jpayne@69: namespace kj {
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class ListLink;
jpayne@69: 
jpayne@69: template <typename T, typename MaybeConstT, ListLink<T> T::*link>
jpayne@69: class ListIterator;
jpayne@69: 
jpayne@69: namespace _ {  // (private)
jpayne@69: 
jpayne@69: KJ_NORETURN(void throwDoubleAdd());
jpayne@69: KJ_NORETURN(void throwRemovedNotPresent());
jpayne@69: KJ_NORETURN(void throwRemovedWrongList());
jpayne@69: KJ_NORETURN(void throwDestroyedWhileInList());
jpayne@69: 
jpayne@69: }  // namespace _ (private)
jpayne@69: 
jpayne@69: template <typename T, ListLink<T> T::*link>
jpayne@69: class List {
jpayne@69:   // A linked list that does no memory allocation.
jpayne@69:   //
jpayne@69:   // The list contains elements of type T that are allocated elsewhere. An existing object of type
jpayne@69:   // T can be added to the list and removed again without doing any heap allocation. This is
jpayne@69:   // achieved by requiring that T contains a field of type ListLink<T>. A pointer-to-member to
jpayne@69:   // this field is the second parameter to the `List` template.
jpayne@69:   //
jpayne@69:   // kj::List is ideally suited to situations where an object wants to be able to "add itself" to
jpayne@69:   // a list of objects waiting for a notification, with the ability to remove itself early if it
jpayne@69:   // wants to stop waiting. With traditional STL containers, these operations would require memory
jpayne@69:   // allocation.
jpayne@69:   //
jpayne@69:   // Example:
jpayne@69:   //
jpayne@69:   //     struct Item {
jpayne@69:   //       ListLink<Waiter> link;
jpayne@69:   //       // ... other members ...
jpayne@69:   //     };
jpayne@69:   //
jpayne@69:   //     kj::List<Item, &Item::link> itemList;
jpayne@69:   //
jpayne@69:   //     Item foo;
jpayne@69:   //     itemList.add(foo);
jpayne@69:   //     itemList.remove(foo);
jpayne@69:   //
jpayne@69:   // Note that you MUST manually remove an element from the list before destroying it. ListLinks
jpayne@69:   // do not automatically unlink themselves because this could lead to subtle thread-safety bugs
jpayne@69:   // if the List is guarded by a mutex, and that mutex is not currently locked. Normally, you should
jpayne@69:   // have T's destructor remove it from any lists. You can use `link.isLinked()` to check if the
jpayne@69:   // item is currently in a list.
jpayne@69:   //
jpayne@69:   // kj::List is a doubly-linked list in order to allow O(1) removal of any element given only a
jpayne@69:   // reference to the element. However, it only supports forward iteration.
jpayne@69:   //
jpayne@69:   // When iterating over a kj::List, you can safely remove current element which the iterator
jpayne@69:   // points to without breaking the iteration. However, removing any *other* element could
jpayne@69:   // invalidate the iterator.
jpayne@69: 
jpayne@69: public:
jpayne@69:   List() = default;
jpayne@69:   KJ_DISALLOW_COPY_AND_MOVE(List);
jpayne@69: 
jpayne@69:   bool empty() const {
jpayne@69:     return head == nullptr;
jpayne@69:   }
jpayne@69: 
jpayne@69:   size_t size() const {
jpayne@69:     return listSize;
jpayne@69:   }
jpayne@69: 
jpayne@69:   void add(T& element) {
jpayne@69:     if ((element.*link).prev != nullptr) _::throwDoubleAdd();
jpayne@69:     *tail = element;
jpayne@69:     (element.*link).prev = tail;
jpayne@69:     tail = &((element.*link).next);
jpayne@69:     ++listSize;
jpayne@69:   }
jpayne@69: 
jpayne@69:   void addFront(T& element) {
jpayne@69:     if ((element.*link).prev != nullptr) _::throwDoubleAdd();
jpayne@69:     (element.*link).next = head;
jpayne@69:     (element.*link).prev = &head;
jpayne@69:     KJ_IF_MAYBE(oldHead, head) {
jpayne@69:       (oldHead->*link).prev = &(element.*link).next;
jpayne@69:     } else {
jpayne@69:       tail = &(element.*link).next;
jpayne@69:     }
jpayne@69:     head = element;
jpayne@69:     ++listSize;
jpayne@69:   }
jpayne@69: 
jpayne@69:   void remove(T& element) {
jpayne@69:     if ((element.*link).prev == nullptr) _::throwRemovedNotPresent();
jpayne@69:     *((element.*link).prev) = (element.*link).next;
jpayne@69:     KJ_IF_MAYBE(n, (element.*link).next) {
jpayne@69:       (n->*link).prev = (element.*link).prev;
jpayne@69:     } else {
jpayne@69:       if (tail != &((element.*link).next)) _::throwRemovedWrongList();
jpayne@69:       tail = (element.*link).prev;
jpayne@69:     }
jpayne@69:     (element.*link).next = nullptr;
jpayne@69:     (element.*link).prev = nullptr;
jpayne@69:     --listSize;
jpayne@69:   }
jpayne@69: 
jpayne@69:   typedef ListIterator<T, T, link> Iterator;
jpayne@69:   typedef ListIterator<T, const T, link> ConstIterator;
jpayne@69: 
jpayne@69:   Iterator begin() { return Iterator(head); }
jpayne@69:   Iterator end() { return Iterator(nullptr); }
jpayne@69:   ConstIterator begin() const { return ConstIterator(head); }
jpayne@69:   ConstIterator end() const { return ConstIterator(nullptr); }
jpayne@69: 
jpayne@69:   T& front() { return *begin(); }
jpayne@69:   const T& front() const { return *begin(); }
jpayne@69: 
jpayne@69: private:
jpayne@69:   Maybe<T&> head;
jpayne@69:   Maybe<T&>* tail = &head;
jpayne@69:   size_t listSize = 0;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T>
jpayne@69: class ListLink {
jpayne@69: public:
jpayne@69:   ListLink(): next(nullptr), prev(nullptr) {}
jpayne@69:   ~ListLink() noexcept {
jpayne@69:     // Intentionally `noexcept` because we want to crash if a dangling pointer was left in a list.
jpayne@69:     if (prev != nullptr) _::throwDestroyedWhileInList();
jpayne@69:   }
jpayne@69:   KJ_DISALLOW_COPY_AND_MOVE(ListLink);
jpayne@69: 
jpayne@69:   bool isLinked() const { return prev != nullptr; }
jpayne@69: 
jpayne@69: private:
jpayne@69:   Maybe<T&> next;
jpayne@69:   Maybe<T&>* prev;
jpayne@69: 
jpayne@69:   template <typename U, ListLink<U> U::*link>
jpayne@69:   friend class List;
jpayne@69:   template <typename U, typename MaybeConstU, ListLink<U> U::*link>
jpayne@69:   friend class ListIterator;
jpayne@69: };
jpayne@69: 
jpayne@69: template <typename T, typename MaybeConstT, ListLink<T> T::*link>
jpayne@69: class ListIterator {
jpayne@69: public:
jpayne@69:   ListIterator() = default;
jpayne@69: 
jpayne@69:   MaybeConstT& operator*() {
jpayne@69:     KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69:     return *_::readMaybe(current);
jpayne@69:   }
jpayne@69:   const T& operator*() const {
jpayne@69:     KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69:     return *_::readMaybe(current);
jpayne@69:   }
jpayne@69:   MaybeConstT* operator->() {
jpayne@69:     KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69:     return _::readMaybe(current);
jpayne@69:   }
jpayne@69:   const T* operator->() const {
jpayne@69:     KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69:     return _::readMaybe(current);
jpayne@69:   }
jpayne@69: 
jpayne@69:   inline ListIterator& operator++() {
jpayne@69:     current = next;
jpayne@69:     next = current.map([](MaybeConstT& obj) -> kj::Maybe<MaybeConstT&> { return (obj.*link).next; })
jpayne@69:         .orDefault(nullptr);
jpayne@69:     return *this;
jpayne@69:   }
jpayne@69:   inline ListIterator operator++(int) {
jpayne@69:     ListIterator result = *this;
jpayne@69:     ++*this;
jpayne@69:     return result;
jpayne@69:   }
jpayne@69: 
jpayne@69:   inline bool operator==(const ListIterator& other) const {
jpayne@69:     return _::readMaybe(current) == _::readMaybe(other.current);
jpayne@69:   }
jpayne@69:   inline bool operator!=(const ListIterator& other) const {
jpayne@69:     return _::readMaybe(current) != _::readMaybe(other.current);
jpayne@69:   }
jpayne@69: 
jpayne@69: private:
jpayne@69:   Maybe<MaybeConstT&> current;
jpayne@69: 
jpayne@69:   Maybe<MaybeConstT&> next;
jpayne@69:   // so that the current item can be removed from the list without invalidating the iterator
jpayne@69: 
jpayne@69:   explicit ListIterator(Maybe<MaybeConstT&> start)
jpayne@69:       : current(start),
jpayne@69:         next(start.map([](MaybeConstT& obj) -> kj::Maybe<MaybeConstT&> { return (obj.*link).next; })
jpayne@69:             .orDefault(nullptr)) {}
jpayne@69:   friend class List<T, link>;
jpayne@69: };
jpayne@69: 
jpayne@69: } // namespace kj
jpayne@69: 
jpayne@69: KJ_END_HEADER