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 "base/casts.h" 27 #include "base/logging.h" 28 #include "base/macros.h" 29 30 namespace art { 31 32 struct IntrusiveForwardListHook { 33 IntrusiveForwardListHook() : next_hook(nullptr) { } 34 explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { } 35 36 // Allow copyable values but do not copy the hook, it is not part of the value. 37 IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED) 38 : next_hook(nullptr) { } 39 IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) { 40 return *this; 41 } 42 43 mutable const IntrusiveForwardListHook* next_hook; 44 }; 45 46 template <typename Derived, typename Tag = void> 47 struct IntrusiveForwardListNode : public IntrusiveForwardListHook { 48 }; 49 50 template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook> 51 class IntrusiveForwardListMemberHookTraits; 52 53 template <typename T, typename Tag = void> 54 class IntrusiveForwardListBaseHookTraits; 55 56 template <typename T, 57 typename HookTraits = 58 IntrusiveForwardListBaseHookTraits<typename std::remove_const<T>::type>> 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<>). 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 = typename std::enable_if<std::is_same<T, const OtherT>::value>::type> 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: 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 typename std::enable_if<std::is_same<const OtherT1, const OtherT2>::value, bool>::type 109 operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs, 110 const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs); 111 }; 112 113 template <typename T, typename OtherT, typename HookTraits> 114 typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type 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 typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type 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 typedef HookTraits hook_traits; 137 typedef T value_type; 138 typedef T& reference; 139 typedef const T& const_reference; 140 typedef T* pointer; 141 typedef const T* const_pointer; 142 typedef IntrusiveForwardListIterator< T, hook_traits> iterator; 143 typedef IntrusiveForwardListIterator<const T, hook_traits> const_iterator; 144 145 // Construct/copy/destroy. 146 IntrusiveForwardList() = default; 147 template <typename InputIterator> 148 IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() { 149 insert_after(before_begin(), first, last); 150 } 151 IntrusiveForwardList(IntrusiveForwardList&& src) : first_(src.first_.next_hook) { 152 src.first_.next_hook = nullptr; 153 } 154 IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete; 155 IntrusiveForwardList& operator=(IntrusiveForwardList&& src) { 156 IntrusiveForwardList tmp(std::move(src)); 157 tmp.swap(*this); 158 return *this; 159 } 160 ~IntrusiveForwardList() = default; 161 162 // Iterators. 163 iterator before_begin() { return iterator(&first_); } 164 const_iterator before_begin() const { return const_iterator(&first_); } 165 iterator begin() { return iterator(first_.next_hook); } 166 const_iterator begin() const { return const_iterator(first_.next_hook); } 167 iterator end() { return iterator(nullptr); } 168 const_iterator end() const { return const_iterator(nullptr); } 169 const_iterator cbefore_begin() const { return const_iterator(&first_); } 170 const_iterator cbegin() const { return const_iterator(first_.next_hook); } 171 const_iterator cend() const { return const_iterator(nullptr); } 172 173 // Capacity. 174 bool empty() const { return begin() == end(); } 175 size_t max_size() { return static_cast<size_t>(-1); } 176 177 // Element access. 178 reference front() { return *begin(); } 179 const_reference front() const { return *begin(); } 180 181 // Modifiers. 182 template <typename InputIterator> 183 void assign(InputIterator first, InputIterator last) { 184 IntrusiveForwardList tmp(first, last); 185 tmp.swap(*this); 186 } 187 void push_front(value_type& value) { 188 insert_after(before_begin(), value); 189 } 190 void pop_front() { 191 DCHECK(!empty()); 192 erase_after(before_begin()); 193 } 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> 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 } 207 iterator erase_after(const_iterator position) { 208 const_iterator last = position; 209 std::advance(last, 2); 210 return erase_after(position, last); 211 } 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 } 217 void swap(IntrusiveForwardList& other) { 218 std::swap(first_.next_hook, other.first_.next_hook); 219 } 220 void clear() { 221 first_.next_hook = nullptr; 222 } 223 224 // Operations. 225 void splice_after(const_iterator position, IntrusiveForwardList& src) { 226 DCHECK(position != end()); 227 splice_after(position, src, src.before_begin(), src.end()); 228 } 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`. 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`. 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)`. 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)`. 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 } 285 void remove(const value_type& value) { 286 remove_if([value](const value_type& v) { return value == v; }); 287 } 288 template <typename Predicate> 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 } 300 void unique() { 301 unique(std::equal_to<value_type>()); 302 } 303 template <typename BinaryPredicate> 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 } 319 void merge(IntrusiveForwardList& other) { 320 merge(other, std::less<value_type>()); 321 } 322 void merge(IntrusiveForwardList&& other) { 323 merge(other); // Use l-value overload. 324 } 325 template <typename Compare> 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> 346 void merge(IntrusiveForwardList&& other, Compare cmp) { 347 merge(other, cmp); // Use l-value overload. 348 } 349 void sort() { 350 sort(std::less<value_type>()); 351 } 352 template <typename Compare> 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 } 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. 376 bool HasExactlyOneElement() const { 377 return !empty() && ++begin() == end(); 378 } 379 size_t SizeSlow() const { 380 return std::distance(begin(), end()); 381 } 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: 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> 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: 450 static const IntrusiveForwardListHook* GetHook(const T* value) { 451 return &(value->*NextPtr); 452 } 453 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: 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 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_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_ 477