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