Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- llvm/ADT/AllocatorList.h - Custom allocator list ---------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_ALLOCATORLIST_H

#define LLVM_ADT_ALLOCATORLIST_H

#include "llvm/ADT/ilist_node.h"

#include "llvm/ADT/iterator.h"

#include "llvm/ADT/simple_ilist.h"

#include "llvm/Support/Allocator.h"

#include <cassert>

#include <cstddef>

#include <iterator>

#include <type_traits>

#include <utility>

namespace llvm {

/// A linked-list with a custom, local allocator.

///

/// Expose a std::list-like interface that owns and uses a custom LLVM-style

/// allocator (e.g., BumpPtrAllocator), leveraging \a simple_ilist for the

/// implementation details.

///

/// Because this list owns the allocator, calling \a splice() with a different

/// list isn't generally safe.  As such, \a splice has been left out of the

/// interface entirely.

template <class T, class AllocatorT> class AllocatorList : AllocatorT {

  struct Node : ilist_node<Node> {

    Node(Node &&) = delete;

    Node(const Node &) = delete;

    Node &operator=(Node &&) = delete;

    Node &operator=(const Node &) = delete;

    Node(T &&V) : V(std::move(V)) {}

    Node(const T &V) : V(V) {}

    template <class... Ts> Node(Ts &&... Vs) : V(std::forward<Ts>(Vs)...) {}

    T V;

  };

  using list_type = simple_ilist<Node>;

  list_type List;

  AllocatorT &getAlloc() { return *this; }

  const AllocatorT &getAlloc() const { return *this; }

  template <class... ArgTs> Node *create(ArgTs &&... Args) {

    return new (getAlloc()) Node(std::forward<ArgTs>(Args)...);

  }

  struct Cloner {

    AllocatorList &AL;

    Cloner(AllocatorList &AL) : AL(AL) {}

    Node *operator()(const Node &N) const { return AL.create(N.V); }

  };

  struct Disposer {

    AllocatorList &AL;

    Disposer(AllocatorList &AL) : AL(AL) {}

    void operator()(Node *N) const {

      N->~Node();

      AL.getAlloc().Deallocate(N);

    }

  };

public:

  using value_type = T;

  using pointer = T *;

  using reference = T &;

  using const_pointer = const T *;

  using const_reference = const T &;

  using size_type = typename list_type::size_type;

  using difference_type = typename list_type::difference_type;

private:

  template <class ValueT, class IteratorBase>

  class IteratorImpl

      : public iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>,

                                     IteratorBase,

                                     std::bidirectional_iterator_tag, ValueT> {

    template <class OtherValueT, class OtherIteratorBase>

    friend class IteratorImpl;

    friend AllocatorList;

    using base_type =

        iterator_adaptor_base<IteratorImpl<ValueT, IteratorBase>, IteratorBase,

                              std::bidirectional_iterator_tag, ValueT>;

  public:

    using value_type = ValueT;

    using pointer = ValueT *;

    using reference = ValueT &;

    IteratorImpl() = default;

    IteratorImpl(const IteratorImpl &) = default;

    IteratorImpl &operator=(const IteratorImpl &) = default;

    explicit IteratorImpl(const IteratorBase &I) : base_type(I) {}

    template <class OtherValueT, class OtherIteratorBase>

    IteratorImpl(const IteratorImpl<OtherValueT, OtherIteratorBase> &X,

                 std::enable_if_t<std::is_convertible<

                     OtherIteratorBase, IteratorBase>::value> * = nullptr)

        : base_type(X.wrapped()) {}

    ~IteratorImpl() = default;

    reference operator*() const { return base_type::wrapped()->V; }

    pointer operator->() const { return &operator*(); }

  };

public:

  using iterator = IteratorImpl<T, typename list_type::iterator>;

  using reverse_iterator =

      IteratorImpl<T, typename list_type::reverse_iterator>;

  using const_iterator =

      IteratorImpl<const T, typename list_type::const_iterator>;

  using const_reverse_iterator =

      IteratorImpl<const T, typename list_type::const_reverse_iterator>;

  AllocatorList() = default;

  AllocatorList(AllocatorList &&X)

      : AllocatorT(std::move(X.getAlloc())), List(std::move(X.List)) {}

  AllocatorList(const AllocatorList &X) {

    List.cloneFrom(X.List, Cloner(*this), Disposer(*this));

  }

  AllocatorList &operator=(AllocatorList &&X) {

    clear(); // Dispose of current nodes explicitly.

    List = std::move(X.List);

    getAlloc() = std::move(X.getAlloc());

    return *this;

  }

  AllocatorList &operator=(const AllocatorList &X) {

    List.cloneFrom(X.List, Cloner(*this), Disposer(*this));

    return *this;

  }

  ~AllocatorList() { clear(); }

  void swap(AllocatorList &RHS) {

    List.swap(RHS.List);

    std::swap(getAlloc(), RHS.getAlloc());

  }

  bool empty() { return List.empty(); }

  size_t size() { return List.size(); }

  iterator begin() { return iterator(List.begin()); }

  iterator end() { return iterator(List.end()); }

  const_iterator begin() const { return const_iterator(List.begin()); }

  const_iterator end() const { return const_iterator(List.end()); }

  reverse_iterator rbegin() { return reverse_iterator(List.rbegin()); }

  reverse_iterator rend() { return reverse_iterator(List.rend()); }

  const_reverse_iterator rbegin() const {

    return const_reverse_iterator(List.rbegin());

  }

  const_reverse_iterator rend() const {

    return const_reverse_iterator(List.rend());

  }

  T &back() { return List.back().V; }

  T &front() { return List.front().V; }

  const T &back() const { return List.back().V; }

  const T &front() const { return List.front().V; }

  template <class... Ts> iterator emplace(iterator I, Ts &&... Vs) {

    return iterator(List.insert(I.wrapped(), *create(std::forward<Ts>(Vs)...)));

  }

  iterator insert(iterator I, T &&V) {

    return iterator(List.insert(I.wrapped(), *create(std::move(V))));

  }

  iterator insert(iterator I, const T &V) {

    return iterator(List.insert(I.wrapped(), *create(V)));

  }

  template <class Iterator>

  void insert(iterator I, Iterator First, Iterator Last) {

    for (; First != Last; ++First)

      List.insert(I.wrapped(), *create(*First));

  }

  iterator erase(iterator I) {

    return iterator(List.eraseAndDispose(I.wrapped(), Disposer(*this)));

  }

  iterator erase(iterator First, iterator Last) {

    return iterator(

        List.eraseAndDispose(First.wrapped(), Last.wrapped(), Disposer(*this)));

  }

  void clear() { List.clearAndDispose(Disposer(*this)); }

  void pop_back() { List.eraseAndDispose(--List.end(), Disposer(*this)); }

  void pop_front() { List.eraseAndDispose(List.begin(), Disposer(*this)); }

  void push_back(T &&V) { insert(end(), std::move(V)); }

  void push_front(T &&V) { insert(begin(), std::move(V)); }

  void push_back(const T &V) { insert(end(), V); }

  void push_front(const T &V) { insert(begin(), V); }

  template <class... Ts> void emplace_back(Ts &&... Vs) {

    emplace(end(), std::forward<Ts>(Vs)...);

  }

  template <class... Ts> void emplace_front(Ts &&... Vs) {

    emplace(begin(), std::forward<Ts>(Vs)...);

  }

  /// Reset the underlying allocator.

  ///

  /// \pre \c empty()

  void resetAlloc() {

    assert(empty() && "Cannot reset allocator if not empty");

    getAlloc().Reset();

  }

};

template <class T> using BumpPtrList = AllocatorList<T, BumpPtrAllocator>;

} // end namespace llvm

#endif // LLVM_ADT_ALLOCATORLIST_H