xref: /art/compiler/utils/intrusive_forward_list.h

/*
 * Copyright (C) 2016 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
#define ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_

#include <stdint.h>
#include <functional>
#include <iterator>
#include <memory>
#include <type_traits>

#include "base/logging.h"
#include "base/macros.h"

namespace art {

struct IntrusiveForwardListHook {
  IntrusiveForwardListHook() : next_hook(nullptr) { }
  explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { }

  // Allow copyable values but do not copy the hook, it is not part of the value.
  IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED)
      : next_hook(nullptr) { }
  IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) {
    return *this;
  }

  mutable const IntrusiveForwardListHook* next_hook;
};

template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
class IntrusiveForwardListMemberHook;

template <typename T, typename HookTraits = IntrusiveForwardListMemberHook<T>>
class IntrusiveForwardList;

template <typename T, typename HookTraits>
class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_tag, T> {
 public:
  // Construct/copy/destroy (except the private constructor used by IntrusiveForwardList<>).
  IntrusiveForwardListIterator() : hook_(nullptr) { }
  IntrusiveForwardListIterator(const IntrusiveForwardListIterator& src) = default;
  IntrusiveForwardListIterator& operator=(const IntrusiveForwardListIterator& src) = default;

  // Conversion from iterator to const_iterator.
  template <typename OtherT,
            typename = typename std::enable_if<std::is_same<T, const OtherT>::value>::type>
  IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src)
      : hook_(src.hook_) { }

  // Iteration.
  IntrusiveForwardListIterator& operator++() {
    DCHECK(hook_ != nullptr);
    hook_ = hook_->next_hook;
    return *this;
  }
  IntrusiveForwardListIterator operator++(int) {
    IntrusiveForwardListIterator tmp(*this);
    ++*this;
    return tmp;
  }

  // Dereference
  T& operator*() const {
    DCHECK(hook_ != nullptr);
    return *HookTraits::GetValue(hook_);
  }
  T* operator->() const {
    return &**this;
  }

 private:
  explicit IntrusiveForwardListIterator(const IntrusiveForwardListHook* hook) : hook_(hook) { }

  const IntrusiveForwardListHook* hook_;

  template <typename OtherT, typename OtherTraits>
  friend class IntrusiveForwardListIterator;

  template <typename OtherT, typename OtherTraits>
  friend class IntrusiveForwardList;

  template <typename OtherT1, typename OtherT2, typename OtherTraits>
  friend typename std::enable_if<std::is_same<const OtherT1, const OtherT2>::value, bool>::type
  operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs,
             const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs);
};

template <typename T, typename OtherT, typename HookTraits>
typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator==(
    const IntrusiveForwardListIterator<T, HookTraits>& lhs,
    const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
  return lhs.hook_ == rhs.hook_;
}

template <typename T, typename OtherT, typename HookTraits>
typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator!=(
    const IntrusiveForwardListIterator<T, HookTraits>& lhs,
    const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
  return !(lhs == rhs);
}

// Intrusive version of std::forward_list<>. See also slist<> in Boost.Intrusive.
//
// This class template provides the same interface as std::forward_list<> as long
// as the functions are meaningful for an intrusive container; this excludes emplace
// functions and functions taking an std::initializer_list<> as the container does
// not construct elements.
template <typename T, typename HookTraits>
class IntrusiveForwardList {
 public:
  typedef HookTraits hook_traits;
  typedef       T  value_type;
  typedef       T& reference;
  typedef const T& const_reference;
  typedef       T* pointer;
  typedef const T* const_pointer;
  typedef IntrusiveForwardListIterator<      T, hook_traits> iterator;
  typedef IntrusiveForwardListIterator<const T, hook_traits> const_iterator;

  // Construct/copy/destroy.
  IntrusiveForwardList() = default;
  template <typename InputIterator>
  IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() {
    insert_after(before_begin(), first, last);
  }
  IntrusiveForwardList(IntrusiveForwardList&& src) : first_(src.first_.next_hook) {
    src.first_.next_hook = nullptr;
  }
  IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete;
  IntrusiveForwardList& operator=(IntrusiveForwardList&& src) {
    IntrusiveForwardList tmp(std::move(src));
    tmp.swap(*this);
    return *this;
  }
  ~IntrusiveForwardList() = default;

  // Iterators.
  iterator before_begin() { return iterator(&first_); }
  const_iterator before_begin() const { return const_iterator(&first_); }
  iterator begin() { return iterator(first_.next_hook); }
  const_iterator begin() const { return const_iterator(first_.next_hook); }
  iterator end() { return iterator(nullptr); }
  const_iterator end() const { return const_iterator(nullptr); }
  const_iterator cbefore_begin() const { return const_iterator(&first_); }
  const_iterator cbegin() const { return const_iterator(first_.next_hook); }
  const_iterator cend() const { return const_iterator(nullptr); }

  // Capacity.
  bool empty() const { return begin() == end(); }
  size_t max_size() { return static_cast<size_t>(-1); }

  // Element access.
  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }

  // Modifiers.
  template <typename InputIterator>
  void assign(InputIterator first, InputIterator last) {
    IntrusiveForwardList tmp(first, last);
    tmp.swap(*this);
  }
  void push_front(value_type& value) {
    insert_after(before_begin(), value);
  }
  void pop_front() {
    DCHECK(!empty());
    erase_after(before_begin());
  }
  iterator insert_after(const_iterator position, value_type& value) {
    const IntrusiveForwardListHook* new_hook = hook_traits::GetHook(&value);
    new_hook->next_hook = position.hook_->next_hook;
    position.hook_->next_hook = new_hook;
    return iterator(new_hook);
  }
  template <typename InputIterator>
  iterator insert_after(const_iterator position, InputIterator first, InputIterator last) {
    while (first != last) {
      position = insert_after(position, *first++);
    }
    return iterator(position.hook_);
  }
  iterator erase_after(const_iterator position) {
    const_iterator last = position;
    std::advance(last, 2);
    return erase_after(position, last);
  }
  iterator erase_after(const_iterator position, const_iterator last) {
    DCHECK(position != last);
    position.hook_->next_hook = last.hook_;
    return iterator(last.hook_);
  }
  void swap(IntrusiveForwardList& other) {
    std::swap(first_.next_hook, other.first_.next_hook);
  }
  void clear() {
    first_.next_hook = nullptr;
  }

  // Operations.
  void splice_after(const_iterator position, IntrusiveForwardList& src) {
    DCHECK(position != end());
    splice_after(position, src, src.before_begin(), src.end());
  }
  void splice_after(const_iterator position, IntrusiveForwardList&& src) {
    splice_after(position, src);  // Use l-value overload.
  }
  // Splice the element after `i`.
  void splice_after(const_iterator position, IntrusiveForwardList& src, const_iterator i) {
    // The standard specifies that this version does nothing if `position == i`
    // or `position == ++i`. We must handle the latter here because the overload
    // `splice_after(position, src, first, last)` does not allow `position` inside
    // the range `(first, last)`.
    if (++const_iterator(i) == position) {
      return;
    }
    const_iterator last = i;
    std::advance(last, 2);
    splice_after(position, src, i, last);
  }
  // Splice the element after `i`.
  void splice_after(const_iterator position, IntrusiveForwardList&& src, const_iterator i) {
    splice_after(position, src, i);  // Use l-value overload.
  }
  // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
  void splice_after(const_iterator position,
                    IntrusiveForwardList& src,
                    const_iterator first,
                    const_iterator last) {
    DCHECK(position != end());
    DCHECK(first != last);
    if (++const_iterator(first) == last) {
      // Nothing to do.
      return;
    }
    // If position is just before end() and last is src.end(), we can finish this quickly.
    if (++const_iterator(position) == end() && last == src.end()) {
      position.hook_->next_hook = first.hook_->next_hook;
      first.hook_->next_hook = nullptr;
      return;
    }
    // Otherwise we need to find the position before last to fix up the hook.
    const_iterator before_last = first;
    while (++const_iterator(before_last) != last) {
      ++before_last;
    }
    // Detach (first, last).
    const IntrusiveForwardListHook* first_taken = first.hook_->next_hook;
    first.hook_->next_hook = last.hook_;
    // Attach the sequence to the new position.
    before_last.hook_->next_hook = position.hook_->next_hook;
    position.hook_->next_hook = first_taken;
  }
  // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
  void splice_after(const_iterator position,
                    IntrusiveForwardList&& src,
                    const_iterator first,
                    const_iterator last) {
    splice_after(position, src, first, last);  // Use l-value overload.
  }
  void remove(const value_type& value) {
    remove_if([value](const value_type& v) { return value == v; });
  }
  template <typename Predicate>
  void remove_if(Predicate pred) {
    iterator prev = before_begin();
    for (iterator current = begin(); current != end(); ++current) {
      if (pred(*current)) {
        erase_after(prev);
        current = prev;
      } else {
        prev = current;
      }
    }
  }
  void unique() {
    unique(std::equal_to<value_type>());
  }
  template <typename BinaryPredicate>
  void unique(BinaryPredicate pred) {
    if (!empty()) {
      iterator prev = begin();
      iterator current = prev;
      ++current;
      for (; current != end(); ++current) {
        if (pred(*prev, *current)) {
          erase_after(prev);
          current = prev;
        } else {
          prev = current;
        }
      }
    }
  }
  void merge(IntrusiveForwardList& other) {
    merge(other, std::less<value_type>());
  }
  void merge(IntrusiveForwardList&& other) {
    merge(other);  // Use l-value overload.
  }
  template <typename Compare>
  void merge(IntrusiveForwardList& other, Compare cmp) {
    iterator prev = before_begin();
    iterator current = begin();
    iterator other_prev = other.before_begin();
    iterator other_current = other.begin();
    while (current != end() && other_current != other.end()) {
      if (cmp(*other_current, *current)) {
        ++other_current;
        splice_after(prev, other, other_prev);
        ++prev;
      } else {
        prev = current;
        ++current;
      }
      DCHECK(++const_iterator(prev) == current);
      DCHECK(++const_iterator(other_prev) == other_current);
    }
    splice_after(prev, other);
  }
  template <typename Compare>
  void merge(IntrusiveForwardList&& other, Compare cmp) {
    merge(other, cmp);  // Use l-value overload.
  }
  void sort() {
    sort(std::less<value_type>());
  }
  template <typename Compare>
  void sort(Compare cmp) {
    size_t n = std::distance(begin(), end());
    if (n >= 2u) {
      const_iterator middle = before_begin();
      std::advance(middle, n / 2u);
      IntrusiveForwardList second_half;
      second_half.splice_after(second_half.before_begin(), *this, middle, end());
      sort(cmp);
      second_half.sort(cmp);
      merge(second_half, cmp);
    }
  }
  void reverse() {
    IntrusiveForwardList reversed;
    while (!empty()) {
      value_type& value = front();
      erase_after(before_begin());
      reversed.insert_after(reversed.before_begin(), value);
    }
    reversed.swap(*this);
  }

  // Extensions.
  bool HasExactlyOneElement() const {
    return !empty() && ++begin() == end();
  }
  size_t SizeSlow() const {
    return std::distance(begin(), end());
  }
  bool ContainsNode(const_reference node) const {
    for (auto&& n : *this) {
      if (std::addressof(n) == std::addressof(node)) {
        return true;
      }
    }
    return false;
  }

 private:
  static IntrusiveForwardListHook* ModifiableHook(const IntrusiveForwardListHook* hook) {
    return const_cast<IntrusiveForwardListHook*>(hook);
  }

  IntrusiveForwardListHook first_;
};

template <typename T, typename HookTraits>
void swap(IntrusiveForwardList<T, HookTraits>& lhs, IntrusiveForwardList<T, HookTraits>& rhs) {
  lhs.swap(rhs);
}

template <typename T, typename HookTraits>
bool operator==(const IntrusiveForwardList<T, HookTraits>& lhs,
                const IntrusiveForwardList<T, HookTraits>& rhs) {
  auto lit = lhs.begin();
  auto rit = rhs.begin();
  for (; lit != lhs.end() && rit != rhs.end(); ++lit, ++rit) {
    if (*lit != *rit) {
      return false;
    }
  }
  return lit == lhs.end() && rit == rhs.end();
}

template <typename T, typename HookTraits>
bool operator!=(const IntrusiveForwardList<T, HookTraits>& lhs,
                const IntrusiveForwardList<T, HookTraits>& rhs) {
  return !(lhs == rhs);
}

template <typename T, typename HookTraits>
bool operator<(const IntrusiveForwardList<T, HookTraits>& lhs,
               const IntrusiveForwardList<T, HookTraits>& rhs) {
  return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
}

template <typename T, typename HookTraits>
bool operator>(const IntrusiveForwardList<T, HookTraits>& lhs,
               const IntrusiveForwardList<T, HookTraits>& rhs) {
  return rhs < lhs;
}

template <typename T, typename HookTraits>
bool operator<=(const IntrusiveForwardList<T, HookTraits>& lhs,
                const IntrusiveForwardList<T, HookTraits>& rhs) {
  return !(rhs < lhs);
}

template <typename T, typename HookTraits>
bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs,
                const IntrusiveForwardList<T, HookTraits>& rhs) {
  return !(lhs < rhs);
}

template <typename T, IntrusiveForwardListHook T::* NextPtr>
class IntrusiveForwardListMemberHook {
 public:
  static const IntrusiveForwardListHook* GetHook(const T* value) {
    return &(value->*NextPtr);
  }

  static T* GetValue(const IntrusiveForwardListHook* hook) {
    return reinterpret_cast<T*>(
        reinterpret_cast<uintptr_t>(hook) - OFFSETOF_MEMBERPTR(T, NextPtr));
  }
};

}  // namespace art

#endif  // ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_