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