Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/list.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
rev   line source
jpayne@69 1 // Copyright (c) 2021 Cloudflare, Inc. and contributors
jpayne@69 2 // Licensed under the MIT License:
jpayne@69 3 //
jpayne@69 4 // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69 5 // of this software and associated documentation files (the "Software"), to deal
jpayne@69 6 // in the Software without restriction, including without limitation the rights
jpayne@69 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69 8 // copies of the Software, and to permit persons to whom the Software is
jpayne@69 9 // furnished to do so, subject to the following conditions:
jpayne@69 10 //
jpayne@69 11 // The above copyright notice and this permission notice shall be included in
jpayne@69 12 // all copies or substantial portions of the Software.
jpayne@69 13 //
jpayne@69 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69 20 // THE SOFTWARE.
jpayne@69 21
jpayne@69 22 #pragma once
jpayne@69 23
jpayne@69 24 #include "common.h"
jpayne@69 25
jpayne@69 26 KJ_BEGIN_HEADER
jpayne@69 27
jpayne@69 28 namespace kj {
jpayne@69 29
jpayne@69 30 template <typename T>
jpayne@69 31 class ListLink;
jpayne@69 32
jpayne@69 33 template <typename T, typename MaybeConstT, ListLink<T> T::*link>
jpayne@69 34 class ListIterator;
jpayne@69 35
jpayne@69 36 namespace _ { // (private)
jpayne@69 37
jpayne@69 38 KJ_NORETURN(void throwDoubleAdd());
jpayne@69 39 KJ_NORETURN(void throwRemovedNotPresent());
jpayne@69 40 KJ_NORETURN(void throwRemovedWrongList());
jpayne@69 41 KJ_NORETURN(void throwDestroyedWhileInList());
jpayne@69 42
jpayne@69 43 } // namespace _ (private)
jpayne@69 44
jpayne@69 45 template <typename T, ListLink<T> T::*link>
jpayne@69 46 class List {
jpayne@69 47 // A linked list that does no memory allocation.
jpayne@69 48 //
jpayne@69 49 // The list contains elements of type T that are allocated elsewhere. An existing object of type
jpayne@69 50 // T can be added to the list and removed again without doing any heap allocation. This is
jpayne@69 51 // achieved by requiring that T contains a field of type ListLink<T>. A pointer-to-member to
jpayne@69 52 // this field is the second parameter to the `List` template.
jpayne@69 53 //
jpayne@69 54 // kj::List is ideally suited to situations where an object wants to be able to "add itself" to
jpayne@69 55 // a list of objects waiting for a notification, with the ability to remove itself early if it
jpayne@69 56 // wants to stop waiting. With traditional STL containers, these operations would require memory
jpayne@69 57 // allocation.
jpayne@69 58 //
jpayne@69 59 // Example:
jpayne@69 60 //
jpayne@69 61 // struct Item {
jpayne@69 62 // ListLink<Waiter> link;
jpayne@69 63 // // ... other members ...
jpayne@69 64 // };
jpayne@69 65 //
jpayne@69 66 // kj::List<Item, &Item::link> itemList;
jpayne@69 67 //
jpayne@69 68 // Item foo;
jpayne@69 69 // itemList.add(foo);
jpayne@69 70 // itemList.remove(foo);
jpayne@69 71 //
jpayne@69 72 // Note that you MUST manually remove an element from the list before destroying it. ListLinks
jpayne@69 73 // do not automatically unlink themselves because this could lead to subtle thread-safety bugs
jpayne@69 74 // if the List is guarded by a mutex, and that mutex is not currently locked. Normally, you should
jpayne@69 75 // have T's destructor remove it from any lists. You can use `link.isLinked()` to check if the
jpayne@69 76 // item is currently in a list.
jpayne@69 77 //
jpayne@69 78 // kj::List is a doubly-linked list in order to allow O(1) removal of any element given only a
jpayne@69 79 // reference to the element. However, it only supports forward iteration.
jpayne@69 80 //
jpayne@69 81 // When iterating over a kj::List, you can safely remove current element which the iterator
jpayne@69 82 // points to without breaking the iteration. However, removing any *other* element could
jpayne@69 83 // invalidate the iterator.
jpayne@69 84
jpayne@69 85 public:
jpayne@69 86 List() = default;
jpayne@69 87 KJ_DISALLOW_COPY_AND_MOVE(List);
jpayne@69 88
jpayne@69 89 bool empty() const {
jpayne@69 90 return head == nullptr;
jpayne@69 91 }
jpayne@69 92
jpayne@69 93 size_t size() const {
jpayne@69 94 return listSize;
jpayne@69 95 }
jpayne@69 96
jpayne@69 97 void add(T& element) {
jpayne@69 98 if ((element.*link).prev != nullptr) _::throwDoubleAdd();
jpayne@69 99 *tail = element;
jpayne@69 100 (element.*link).prev = tail;
jpayne@69 101 tail = &((element.*link).next);
jpayne@69 102 ++listSize;
jpayne@69 103 }
jpayne@69 104
jpayne@69 105 void addFront(T& element) {
jpayne@69 106 if ((element.*link).prev != nullptr) _::throwDoubleAdd();
jpayne@69 107 (element.*link).next = head;
jpayne@69 108 (element.*link).prev = &head;
jpayne@69 109 KJ_IF_MAYBE(oldHead, head) {
jpayne@69 110 (oldHead->*link).prev = &(element.*link).next;
jpayne@69 111 } else {
jpayne@69 112 tail = &(element.*link).next;
jpayne@69 113 }
jpayne@69 114 head = element;
jpayne@69 115 ++listSize;
jpayne@69 116 }
jpayne@69 117
jpayne@69 118 void remove(T& element) {
jpayne@69 119 if ((element.*link).prev == nullptr) _::throwRemovedNotPresent();
jpayne@69 120 *((element.*link).prev) = (element.*link).next;
jpayne@69 121 KJ_IF_MAYBE(n, (element.*link).next) {
jpayne@69 122 (n->*link).prev = (element.*link).prev;
jpayne@69 123 } else {
jpayne@69 124 if (tail != &((element.*link).next)) _::throwRemovedWrongList();
jpayne@69 125 tail = (element.*link).prev;
jpayne@69 126 }
jpayne@69 127 (element.*link).next = nullptr;
jpayne@69 128 (element.*link).prev = nullptr;
jpayne@69 129 --listSize;
jpayne@69 130 }
jpayne@69 131
jpayne@69 132 typedef ListIterator<T, T, link> Iterator;
jpayne@69 133 typedef ListIterator<T, const T, link> ConstIterator;
jpayne@69 134
jpayne@69 135 Iterator begin() { return Iterator(head); }
jpayne@69 136 Iterator end() { return Iterator(nullptr); }
jpayne@69 137 ConstIterator begin() const { return ConstIterator(head); }
jpayne@69 138 ConstIterator end() const { return ConstIterator(nullptr); }
jpayne@69 139
jpayne@69 140 T& front() { return *begin(); }
jpayne@69 141 const T& front() const { return *begin(); }
jpayne@69 142
jpayne@69 143 private:
jpayne@69 144 Maybe<T&> head;
jpayne@69 145 Maybe<T&>* tail = &head;
jpayne@69 146 size_t listSize = 0;
jpayne@69 147 };
jpayne@69 148
jpayne@69 149 template <typename T>
jpayne@69 150 class ListLink {
jpayne@69 151 public:
jpayne@69 152 ListLink(): next(nullptr), prev(nullptr) {}
jpayne@69 153 ~ListLink() noexcept {
jpayne@69 154 // Intentionally `noexcept` because we want to crash if a dangling pointer was left in a list.
jpayne@69 155 if (prev != nullptr) _::throwDestroyedWhileInList();
jpayne@69 156 }
jpayne@69 157 KJ_DISALLOW_COPY_AND_MOVE(ListLink);
jpayne@69 158
jpayne@69 159 bool isLinked() const { return prev != nullptr; }
jpayne@69 160
jpayne@69 161 private:
jpayne@69 162 Maybe<T&> next;
jpayne@69 163 Maybe<T&>* prev;
jpayne@69 164
jpayne@69 165 template <typename U, ListLink<U> U::*link>
jpayne@69 166 friend class List;
jpayne@69 167 template <typename U, typename MaybeConstU, ListLink<U> U::*link>
jpayne@69 168 friend class ListIterator;
jpayne@69 169 };
jpayne@69 170
jpayne@69 171 template <typename T, typename MaybeConstT, ListLink<T> T::*link>
jpayne@69 172 class ListIterator {
jpayne@69 173 public:
jpayne@69 174 ListIterator() = default;
jpayne@69 175
jpayne@69 176 MaybeConstT& operator*() {
jpayne@69 177 KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69 178 return *_::readMaybe(current);
jpayne@69 179 }
jpayne@69 180 const T& operator*() const {
jpayne@69 181 KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69 182 return *_::readMaybe(current);
jpayne@69 183 }
jpayne@69 184 MaybeConstT* operator->() {
jpayne@69 185 KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69 186 return _::readMaybe(current);
jpayne@69 187 }
jpayne@69 188 const T* operator->() const {
jpayne@69 189 KJ_IREQUIRE(current != nullptr, "tried to dereference end of list");
jpayne@69 190 return _::readMaybe(current);
jpayne@69 191 }
jpayne@69 192
jpayne@69 193 inline ListIterator& operator++() {
jpayne@69 194 current = next;
jpayne@69 195 next = current.map([](MaybeConstT& obj) -> kj::Maybe<MaybeConstT&> { return (obj.*link).next; })
jpayne@69 196 .orDefault(nullptr);
jpayne@69 197 return *this;
jpayne@69 198 }
jpayne@69 199 inline ListIterator operator++(int) {
jpayne@69 200 ListIterator result = *this;
jpayne@69 201 ++*this;
jpayne@69 202 return result;
jpayne@69 203 }
jpayne@69 204
jpayne@69 205 inline bool operator==(const ListIterator& other) const {
jpayne@69 206 return _::readMaybe(current) == _::readMaybe(other.current);
jpayne@69 207 }
jpayne@69 208 inline bool operator!=(const ListIterator& other) const {
jpayne@69 209 return _::readMaybe(current) != _::readMaybe(other.current);
jpayne@69 210 }
jpayne@69 211
jpayne@69 212 private:
jpayne@69 213 Maybe<MaybeConstT&> current;
jpayne@69 214
jpayne@69 215 Maybe<MaybeConstT&> next;
jpayne@69 216 // so that the current item can be removed from the list without invalidating the iterator
jpayne@69 217
jpayne@69 218 explicit ListIterator(Maybe<MaybeConstT&> start)
jpayne@69 219 : current(start),
jpayne@69 220 next(start.map([](MaybeConstT& obj) -> kj::Maybe<MaybeConstT&> { return (obj.*link).next; })
jpayne@69 221 .orDefault(nullptr)) {}
jpayne@69 222 friend class List<T, link>;
jpayne@69 223 };
jpayne@69 224
jpayne@69 225 } // namespace kj
jpayne@69 226
jpayne@69 227 KJ_END_HEADER