• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 {
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 =
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<>).
IntrusiveForwardListIterator()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>
IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT,HookTraits> & src)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:
IntrusiveForwardListIterator(const IntrusiveForwardListHook * hook)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>
IntrusiveForwardList(InputIterator first,InputIterator last)149   IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() {
150     insert_after(before_begin(), first, last);
151   }
IntrusiveForwardList(IntrusiveForwardList && src)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.
before_begin()164   iterator before_begin() { return iterator(&first_); }
before_begin()165   const_iterator before_begin() const { return const_iterator(&first_); }
begin()166   iterator begin() { return iterator(first_.next_hook); }
begin()167   const_iterator begin() const { return const_iterator(first_.next_hook); }
end()168   iterator end() { return iterator(nullptr); }
end()169   const_iterator end() const { return const_iterator(nullptr); }
cbefore_begin()170   const_iterator cbefore_begin() const { return const_iterator(&first_); }
cbegin()171   const_iterator cbegin() const { return const_iterator(first_.next_hook); }
cend()172   const_iterator cend() const { return const_iterator(nullptr); }
173 
174   // Capacity.
empty()175   bool empty() const { return begin() == end(); }
max_size()176   size_t max_size() { return static_cast<size_t>(-1); }
177 
178   // Element access.
front()179   reference front() { return *begin(); }
front()180   const_reference front() const { return *begin(); }
181 
182   // Modifiers.
183   template <typename InputIterator>
assign(InputIterator first,InputIterator last)184   void assign(InputIterator first, InputIterator last) {
185     IntrusiveForwardList tmp(first, last);
186     tmp.swap(*this);
187   }
push_front(value_type & value)188   void push_front(value_type& value) {
189     insert_after(before_begin(), value);
190   }
pop_front()191   void pop_front() {
192     DCHECK(!empty());
193     erase_after(before_begin());
194   }
insert_after(const_iterator position,value_type & value)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>
insert_after(const_iterator position,InputIterator first,InputIterator last)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   }
erase_after(const_iterator position)208   iterator erase_after(const_iterator position) {
209     const_iterator last = position;
210     std::advance(last, 2);
211     return erase_after(position, last);
212   }
erase_after(const_iterator position,const_iterator last)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   }
swap(IntrusiveForwardList & other)218   void swap(IntrusiveForwardList& other) {
219     std::swap(first_.next_hook, other.first_.next_hook);
220   }
clear()221   void clear() {
222     first_.next_hook = nullptr;
223   }
224 
225   // Operations.
splice_after(const_iterator position,IntrusiveForwardList & src)226   void splice_after(const_iterator position, IntrusiveForwardList& src) {
227     DCHECK(position != end());
228     splice_after(position, src, src.before_begin(), src.end());
229   }
splice_after(const_iterator position,IntrusiveForwardList && src)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`.
splice_after(const_iterator position,IntrusiveForwardList & src,const_iterator 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`.
splice_after(const_iterator position,IntrusiveForwardList && src,const_iterator 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)`.
splice_after(const_iterator position,IntrusiveForwardList & src,const_iterator first,const_iterator 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)`.
splice_after(const_iterator position,IntrusiveForwardList && src,const_iterator first,const_iterator 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   }
remove(const value_type & value)286   void remove(const value_type& value) {
287     remove_if([value](const value_type& v) { return value == v; });
288   }
289   template <typename Predicate>
remove_if(Predicate pred)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   }
unique()301   void unique() {
302     unique(std::equal_to<value_type>());
303   }
304   template <typename BinaryPredicate>
unique(BinaryPredicate pred)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   }
merge(IntrusiveForwardList & other)320   void merge(IntrusiveForwardList& other) {
321     merge(other, std::less<value_type>());
322   }
merge(IntrusiveForwardList && other)323   void merge(IntrusiveForwardList&& other) {
324     merge(other);  // Use l-value overload.
325   }
326   template <typename Compare>
merge(IntrusiveForwardList & other,Compare cmp)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>
merge(IntrusiveForwardList && other,Compare cmp)347   void merge(IntrusiveForwardList&& other, Compare cmp) {
348     merge(other, cmp);  // Use l-value overload.
349   }
sort()350   void sort() {
351     sort(std::less<value_type>());
352   }
353   template <typename Compare>
sort(Compare cmp)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   }
reverse()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.
HasExactlyOneElement()377   bool HasExactlyOneElement() const {
378     return !empty() && ++begin() == end();
379   }
SizeSlow()380   size_t SizeSlow() const {
381     return std::distance(begin(), end());
382   }
ContainsNode(const_reference node)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:
ModifiableHook(const IntrusiveForwardListHook * hook)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>
swap(IntrusiveForwardList<T,HookTraits> & lhs,IntrusiveForwardList<T,HookTraits> & rhs)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:
GetHook(const T * value)451   static const IntrusiveForwardListHook* GetHook(const T* value) {
452     return &(value->*NextPtr);
453   }
454 
GetValue(const IntrusiveForwardListHook * hook)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:
GetHook(const T * value)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 
GetValue(const IntrusiveForwardListHook * hook)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