capnproto

list.h (7053B)

---

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