Mercurial > repos > rliterman > csp2

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