1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_LIBARTBASE_BASE_INTRUSIVE_FORWARD_LIST_H_
18 #define ART_LIBARTBASE_BASE_INTRUSIVE_FORWARD_LIST_H_
19
20 #include <stdint.h>
21 #include <functional>
22 #include <iterator>
23 #include <memory>
24 #include <type_traits>
25
26 #include <android-base/logging.h>
27
28 #include "base/casts.h"
29 #include "base/macros.h"
30
31 namespace art {
32
33 struct IntrusiveForwardListHook {
IntrusiveForwardListHookIntrusiveForwardListHook34 IntrusiveForwardListHook() : next_hook(nullptr) { }
IntrusiveForwardListHookIntrusiveForwardListHook35 explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { }
36
37 // Allow copyable values but do not copy the hook, it is not part of the value.
IntrusiveForwardListHookIntrusiveForwardListHook38 IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED)
39 : next_hook(nullptr) { }
40 IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) {
41 return *this;
42 }
43
44 mutable const IntrusiveForwardListHook* next_hook;
45 };
46
47 template <typename Derived, typename Tag = void>
48 struct IntrusiveForwardListNode : public IntrusiveForwardListHook {
49 };
50
51 template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
52 class IntrusiveForwardListMemberHookTraits;
53
54 template <typename T, typename Tag = void>
55 class IntrusiveForwardListBaseHookTraits;
56
57 template <typename T,
58 typename HookTraits = IntrusiveForwardListBaseHookTraits<std::remove_const_t<T>>>
59 class IntrusiveForwardList;
60
61 template <typename T, typename HookTraits>
62 class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_tag, T> {
63 public:
64 // Construct/copy/destroy (except the private constructor used by IntrusiveForwardList<>).
IntrusiveForwardListIterator()65 IntrusiveForwardListIterator() : hook_(nullptr) { }
66 IntrusiveForwardListIterator(const IntrusiveForwardListIterator& src) = default;
67 IntrusiveForwardListIterator& operator=(const IntrusiveForwardListIterator& src) = default;
68
69 // Conversion from iterator to const_iterator.
70 template <typename OtherT,
71 typename = std::enable_if_t<std::is_same_v<T, const OtherT>>>
IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT,HookTraits> & src)72 IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src) // NOLINT, implicit
73 : hook_(src.hook_) { }
74
75 // Iteration.
76 IntrusiveForwardListIterator& operator++() {
77 DCHECK(hook_ != nullptr);
78 hook_ = hook_->next_hook;
79 return *this;
80 }
81 IntrusiveForwardListIterator operator++(int) {
82 IntrusiveForwardListIterator tmp(*this);
83 ++*this;
84 return tmp;
85 }
86
87 // Dereference
88 T& operator*() const {
89 DCHECK(hook_ != nullptr);
90 return *HookTraits::GetValue(hook_);
91 }
92 T* operator->() const {
93 return &**this;
94 }
95
96 private:
IntrusiveForwardListIterator(const IntrusiveForwardListHook * hook)97 explicit IntrusiveForwardListIterator(const IntrusiveForwardListHook* hook) : hook_(hook) { }
98
99 const IntrusiveForwardListHook* hook_;
100
101 template <typename OtherT, typename OtherTraits>
102 friend class IntrusiveForwardListIterator;
103
104 template <typename OtherT, typename OtherTraits>
105 friend class IntrusiveForwardList;
106
107 template <typename OtherT1, typename OtherT2, typename OtherTraits>
108 friend std::enable_if_t<std::is_same_v<const OtherT1, const OtherT2>, bool>
109 operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs,
110 const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs);
111 };
112
113 template <typename T, typename OtherT, typename HookTraits>
114 std::enable_if_t<std::is_same_v<const T, const OtherT>, bool> operator==(
115 const IntrusiveForwardListIterator<T, HookTraits>& lhs,
116 const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
117 return lhs.hook_ == rhs.hook_;
118 }
119
120 template <typename T, typename OtherT, typename HookTraits>
121 std::enable_if_t<std::is_same_v<const T, const OtherT>, bool> operator!=(
122 const IntrusiveForwardListIterator<T, HookTraits>& lhs,
123 const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
124 return !(lhs == rhs);
125 }
126
127 // Intrusive version of std::forward_list<>. See also slist<> in Boost.Intrusive.
128 //
129 // This class template provides the same interface as std::forward_list<> as long
130 // as the functions are meaningful for an intrusive container; this excludes emplace
131 // functions and functions taking an std::initializer_list<> as the container does
132 // not construct elements.
133 template <typename T, typename HookTraits>
134 class IntrusiveForwardList {
135 public:
136 using hook_traits = HookTraits;
137 using value_type = T;
138 using reference = T&;
139 using const_reference = const T&;
140 using pointer = T*;
141 using const_pointer = const T*;
142 using iterator = IntrusiveForwardListIterator<T, hook_traits>;
143 using const_iterator = IntrusiveForwardListIterator<const T, hook_traits>;
144
145 // Construct/copy/destroy.
146 IntrusiveForwardList() = default;
147 template <typename InputIterator>
IntrusiveForwardList(InputIterator first,InputIterator last)148 IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() {
149 insert_after(before_begin(), first, last);
150 }
IntrusiveForwardList(IntrusiveForwardList && src)151 IntrusiveForwardList(IntrusiveForwardList&& src) noexcept : first_(src.first_.next_hook) {
152 src.first_.next_hook = nullptr;
153 }
154 IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete;
155 IntrusiveForwardList& operator=(IntrusiveForwardList&& src) noexcept {
156 IntrusiveForwardList tmp(std::move(src));
157 tmp.swap(*this);
158 return *this;
159 }
160 ~IntrusiveForwardList() = default;
161
162 // Iterators.
before_begin()163 iterator before_begin() { return iterator(&first_); }
before_begin()164 const_iterator before_begin() const { return const_iterator(&first_); }
begin()165 iterator begin() { return iterator(first_.next_hook); }
begin()166 const_iterator begin() const { return const_iterator(first_.next_hook); }
end()167 iterator end() { return iterator(nullptr); }
end()168 const_iterator end() const { return const_iterator(nullptr); }
cbefore_begin()169 const_iterator cbefore_begin() const { return const_iterator(&first_); }
cbegin()170 const_iterator cbegin() const { return const_iterator(first_.next_hook); }
cend()171 const_iterator cend() const { return const_iterator(nullptr); }
172
173 // Capacity.
empty()174 bool empty() const { return begin() == end(); }
max_size()175 size_t max_size() { return static_cast<size_t>(-1); }
176
177 // Element access.
front()178 reference front() { return *begin(); }
front()179 const_reference front() const { return *begin(); }
180
181 // Modifiers.
182 template <typename InputIterator>
assign(InputIterator first,InputIterator last)183 void assign(InputIterator first, InputIterator last) {
184 IntrusiveForwardList tmp(first, last);
185 tmp.swap(*this);
186 }
push_front(value_type & value)187 void push_front(value_type& value) {
188 insert_after(before_begin(), value);
189 }
pop_front()190 void pop_front() {
191 DCHECK(!empty());
192 erase_after(before_begin());
193 }
insert_after(const_iterator position,value_type & value)194 iterator insert_after(const_iterator position, value_type& value) {
195 const IntrusiveForwardListHook* new_hook = hook_traits::GetHook(&value);
196 new_hook->next_hook = position.hook_->next_hook;
197 position.hook_->next_hook = new_hook;
198 return iterator(new_hook);
199 }
200 template <typename InputIterator>
insert_after(const_iterator position,InputIterator first,InputIterator last)201 iterator insert_after(const_iterator position, InputIterator first, InputIterator last) {
202 while (first != last) {
203 position = insert_after(position, *first++);
204 }
205 return iterator(position.hook_);
206 }
erase_after(const_iterator position)207 iterator erase_after(const_iterator position) {
208 const_iterator last = position;
209 std::advance(last, 2);
210 return erase_after(position, last);
211 }
erase_after(const_iterator position,const_iterator last)212 iterator erase_after(const_iterator position, const_iterator last) {
213 DCHECK(position != last);
214 position.hook_->next_hook = last.hook_;
215 return iterator(last.hook_);
216 }
swap(IntrusiveForwardList & other)217 void swap(IntrusiveForwardList& other) {
218 std::swap(first_.next_hook, other.first_.next_hook);
219 }
clear()220 void clear() {
221 first_.next_hook = nullptr;
222 }
223
224 // Operations.
splice_after(const_iterator position,IntrusiveForwardList & src)225 void splice_after(const_iterator position, IntrusiveForwardList& src) {
226 DCHECK(position != end());
227 splice_after(position, src, src.before_begin(), src.end());
228 }
splice_after(const_iterator position,IntrusiveForwardList && src)229 void splice_after(const_iterator position, IntrusiveForwardList&& src) {
230 splice_after(position, src); // Use l-value overload.
231 }
232 // Splice the element after `i`.
splice_after(const_iterator position,IntrusiveForwardList & src,const_iterator i)233 void splice_after(const_iterator position, IntrusiveForwardList& src, const_iterator i) {
234 // The standard specifies that this version does nothing if `position == i`
235 // or `position == ++i`. We must handle the latter here because the overload
236 // `splice_after(position, src, first, last)` does not allow `position` inside
237 // the range `(first, last)`.
238 if (++const_iterator(i) == position) {
239 return;
240 }
241 const_iterator last = i;
242 std::advance(last, 2);
243 splice_after(position, src, i, last);
244 }
245 // Splice the element after `i`.
splice_after(const_iterator position,IntrusiveForwardList && src,const_iterator i)246 void splice_after(const_iterator position, IntrusiveForwardList&& src, const_iterator i) {
247 splice_after(position, src, i); // Use l-value overload.
248 }
249 // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
splice_after(const_iterator position,IntrusiveForwardList & src,const_iterator first,const_iterator last)250 void splice_after(const_iterator position,
251 IntrusiveForwardList& src,
252 const_iterator first,
253 const_iterator last) {
254 DCHECK(position != end());
255 DCHECK(first != last);
256 if (++const_iterator(first) == last) {
257 // Nothing to do.
258 return;
259 }
260 // If position is just before end() and last is src.end(), we can finish this quickly.
261 if (++const_iterator(position) == end() && last == src.end()) {
262 position.hook_->next_hook = first.hook_->next_hook;
263 first.hook_->next_hook = nullptr;
264 return;
265 }
266 // Otherwise we need to find the position before last to fix up the hook.
267 const_iterator before_last = first;
268 while (++const_iterator(before_last) != last) {
269 ++before_last;
270 }
271 // Detach (first, last).
272 const IntrusiveForwardListHook* first_taken = first.hook_->next_hook;
273 first.hook_->next_hook = last.hook_;
274 // Attach the sequence to the new position.
275 before_last.hook_->next_hook = position.hook_->next_hook;
276 position.hook_->next_hook = first_taken;
277 }
278 // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
splice_after(const_iterator position,IntrusiveForwardList && src,const_iterator first,const_iterator last)279 void splice_after(const_iterator position,
280 IntrusiveForwardList&& src,
281 const_iterator first,
282 const_iterator last) {
283 splice_after(position, src, first, last); // Use l-value overload.
284 }
remove(const value_type & value)285 void remove(const value_type& value) {
286 remove_if([value](const value_type& v) { return value == v; });
287 }
288 template <typename Predicate>
remove_if(Predicate pred)289 void remove_if(Predicate pred) {
290 iterator prev = before_begin();
291 for (iterator current = begin(); current != end(); ++current) {
292 if (pred(*current)) {
293 erase_after(prev);
294 current = prev;
295 } else {
296 prev = current;
297 }
298 }
299 }
unique()300 void unique() {
301 unique(std::equal_to<value_type>());
302 }
303 template <typename BinaryPredicate>
unique(BinaryPredicate pred)304 void unique(BinaryPredicate pred) {
305 if (!empty()) {
306 iterator prev = begin();
307 iterator current = prev;
308 ++current;
309 for (; current != end(); ++current) {
310 if (pred(*prev, *current)) {
311 erase_after(prev);
312 current = prev;
313 } else {
314 prev = current;
315 }
316 }
317 }
318 }
merge(IntrusiveForwardList & other)319 void merge(IntrusiveForwardList& other) {
320 merge(other, std::less<value_type>());
321 }
merge(IntrusiveForwardList && other)322 void merge(IntrusiveForwardList&& other) {
323 merge(other); // Use l-value overload.
324 }
325 template <typename Compare>
merge(IntrusiveForwardList & other,Compare cmp)326 void merge(IntrusiveForwardList& other, Compare cmp) {
327 iterator prev = before_begin();
328 iterator current = begin();
329 iterator other_prev = other.before_begin();
330 iterator other_current = other.begin();
331 while (current != end() && other_current != other.end()) {
332 if (cmp(*other_current, *current)) {
333 ++other_current;
334 splice_after(prev, other, other_prev);
335 ++prev;
336 } else {
337 prev = current;
338 ++current;
339 }
340 DCHECK(++const_iterator(prev) == current);
341 DCHECK(++const_iterator(other_prev) == other_current);
342 }
343 splice_after(prev, other);
344 }
345 template <typename Compare>
merge(IntrusiveForwardList && other,Compare cmp)346 void merge(IntrusiveForwardList&& other, Compare cmp) {
347 merge(other, cmp); // Use l-value overload.
348 }
sort()349 void sort() {
350 sort(std::less<value_type>());
351 }
352 template <typename Compare>
sort(Compare cmp)353 void sort(Compare cmp) {
354 size_t n = std::distance(begin(), end());
355 if (n >= 2u) {
356 const_iterator middle = before_begin();
357 std::advance(middle, n / 2u);
358 IntrusiveForwardList second_half;
359 second_half.splice_after(second_half.before_begin(), *this, middle, end());
360 sort(cmp);
361 second_half.sort(cmp);
362 merge(second_half, cmp);
363 }
364 }
reverse()365 void reverse() {
366 IntrusiveForwardList reversed;
367 while (!empty()) {
368 value_type& value = front();
369 erase_after(before_begin());
370 reversed.insert_after(reversed.before_begin(), value);
371 }
372 reversed.swap(*this);
373 }
374
375 // Extensions.
HasExactlyOneElement()376 bool HasExactlyOneElement() const {
377 return !empty() && ++begin() == end();
378 }
SizeSlow()379 size_t SizeSlow() const {
380 return std::distance(begin(), end());
381 }
ContainsNode(const_reference node)382 bool ContainsNode(const_reference node) const {
383 for (auto&& n : *this) {
384 if (std::addressof(n) == std::addressof(node)) {
385 return true;
386 }
387 }
388 return false;
389 }
390
391 private:
ModifiableHook(const IntrusiveForwardListHook * hook)392 static IntrusiveForwardListHook* ModifiableHook(const IntrusiveForwardListHook* hook) {
393 return const_cast<IntrusiveForwardListHook*>(hook);
394 }
395
396 IntrusiveForwardListHook first_;
397 };
398
399 template <typename T, typename HookTraits>
swap(IntrusiveForwardList<T,HookTraits> & lhs,IntrusiveForwardList<T,HookTraits> & rhs)400 void swap(IntrusiveForwardList<T, HookTraits>& lhs, IntrusiveForwardList<T, HookTraits>& rhs) {
401 lhs.swap(rhs);
402 }
403
404 template <typename T, typename HookTraits>
405 bool operator==(const IntrusiveForwardList<T, HookTraits>& lhs,
406 const IntrusiveForwardList<T, HookTraits>& rhs) {
407 auto lit = lhs.begin();
408 auto rit = rhs.begin();
409 for (; lit != lhs.end() && rit != rhs.end(); ++lit, ++rit) {
410 if (*lit != *rit) {
411 return false;
412 }
413 }
414 return lit == lhs.end() && rit == rhs.end();
415 }
416
417 template <typename T, typename HookTraits>
418 bool operator!=(const IntrusiveForwardList<T, HookTraits>& lhs,
419 const IntrusiveForwardList<T, HookTraits>& rhs) {
420 return !(lhs == rhs);
421 }
422
423 template <typename T, typename HookTraits>
424 bool operator<(const IntrusiveForwardList<T, HookTraits>& lhs,
425 const IntrusiveForwardList<T, HookTraits>& rhs) {
426 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
427 }
428
429 template <typename T, typename HookTraits>
430 bool operator>(const IntrusiveForwardList<T, HookTraits>& lhs,
431 const IntrusiveForwardList<T, HookTraits>& rhs) {
432 return rhs < lhs;
433 }
434
435 template <typename T, typename HookTraits>
436 bool operator<=(const IntrusiveForwardList<T, HookTraits>& lhs,
437 const IntrusiveForwardList<T, HookTraits>& rhs) {
438 return !(rhs < lhs);
439 }
440
441 template <typename T, typename HookTraits>
442 bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs,
443 const IntrusiveForwardList<T, HookTraits>& rhs) {
444 return !(lhs < rhs);
445 }
446
447 template <typename T, IntrusiveForwardListHook T::* NextPtr>
448 class IntrusiveForwardListMemberHookTraits {
449 public:
GetHook(const T * value)450 static const IntrusiveForwardListHook* GetHook(const T* value) {
451 return &(value->*NextPtr);
452 }
453
GetValue(const IntrusiveForwardListHook * hook)454 static T* GetValue(const IntrusiveForwardListHook* hook) {
455 return reinterpret_cast<T*>(
456 reinterpret_cast<uintptr_t>(hook) - OFFSETOF_MEMBERPTR(T, NextPtr));
457 }
458 };
459
460 template <typename T, typename Tag>
461 class IntrusiveForwardListBaseHookTraits {
462 public:
GetHook(const T * value)463 static const IntrusiveForwardListHook* GetHook(const T* value) {
464 // Explicit conversion to the "node" followed by implicit conversion to the "hook".
465 return static_cast<const IntrusiveForwardListNode<T, Tag>*>(value);
466 }
467
GetValue(const IntrusiveForwardListHook * hook)468 static T* GetValue(const IntrusiveForwardListHook* hook) {
469 return down_cast<T*>(down_cast<IntrusiveForwardListNode<T, Tag>*>(
470 const_cast<IntrusiveForwardListHook*>(hook)));
471 }
472 };
473
474 } // namespace art
475
476 #endif // ART_LIBARTBASE_BASE_INTRUSIVE_FORWARD_LIST_H_
477