//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- 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
//
//===----------------------------------------------------------------------===//
///
/// \file
/// This file defines classes to implement an intrusive doubly linked list class
/// (i.e. each node of the list must contain a next and previous field for the
/// list.
///
/// The ilist class itself should be a plug in replacement for list. This list
/// replacement does not provide a constant time size() method, so be careful to
/// use empty() when you really want to know if it's empty.
///
/// The ilist class is implemented as a circular list. The list itself contains
/// a sentinel node, whose Next points at begin() and whose Prev points at
/// rbegin(). The sentinel node itself serves as end() and rend().
///
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_ILIST_H
#define LLVM_ADT_ILIST_H
#include "llvm/ADT/simple_ilist.h"
#include <cassert>
#include <cstddef>
#include <iterator>
namespace llvm {
/// Use delete by default for iplist and ilist.
///
/// Specialize this to get different behaviour for ownership-related API. (If
/// you really want ownership semantics, consider using std::list or building
/// something like \a BumpPtrList.)
///
/// \see ilist_noalloc_traits
template <typename NodeTy> struct ilist_alloc_traits {
static void deleteNode(NodeTy *V) { delete V; }
};
/// Custom traits to do nothing on deletion.
///
/// Specialize ilist_alloc_traits to inherit from this to disable the
/// non-intrusive deletion in iplist (which implies ownership).
///
/// If you want purely intrusive semantics with no callbacks, consider using \a
/// simple_ilist instead.
///
/// \code
/// template <>
/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {};
/// \endcode
template <typename NodeTy> struct ilist_noalloc_traits {
static void deleteNode(NodeTy *V) {}
};
/// Callbacks do nothing by default in iplist and ilist.
///
/// Specialize this for to use callbacks for when nodes change their list
/// membership.
template <typename NodeTy> struct ilist_callback_traits {
void addNodeToList(NodeTy *) {}
void removeNodeFromList(NodeTy *) {}
/// Callback before transferring nodes to this list. The nodes may already be
/// in this same list.
template <class Iterator>
void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
Iterator /*last*/) {
(void)OldList;
}
};
/// A fragment for template traits for intrusive list that provides default
/// node related operations.
///
/// TODO: Remove this layer of indirection. It's not necessary.
template <typename NodeTy>
struct ilist_node_traits : ilist_alloc_traits<NodeTy>,
ilist_callback_traits<NodeTy> {};
/// Template traits for intrusive list.
///
/// Customize callbacks and allocation semantics.
template <typename NodeTy>
struct ilist_traits : public ilist_node_traits<NodeTy> {};
/// Const traits should never be instantiated.
template <typename Ty> struct ilist_traits<const Ty> {};
namespace ilist_detail {
template <class T> T &make();
/// Type trait to check for a traits class that has a getNext member (as a
/// canary for any of the ilist_nextprev_traits API).
template <class TraitsT, class NodeT> struct HasGetNext {
typedef char Yes[1];
typedef char No[2];
template <size_t N> struct SFINAE {};
template <class U>
static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = nullptr);
template <class> static No &test(...);
public:
static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
};
/// Type trait to check for a traits class that has a createSentinel member (as
/// a canary for any of the ilist_sentinel_traits API).
template <class TraitsT> struct HasCreateSentinel {
typedef char Yes[1];
typedef char No[2];
template <class U>
static Yes &test(U *I, decltype(I->createSentinel()) * = nullptr);
template <class> static No &test(...);
public:
static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
};
/// Type trait to check for a traits class that has a createNode member.
/// Allocation should be managed in a wrapper class, instead of in
/// ilist_traits.
template <class TraitsT, class NodeT> struct HasCreateNode {
typedef char Yes[1];
typedef char No[2];
template <size_t N> struct SFINAE {};
template <class U>
static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0);
template <class> static No &test(...);
public:
static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes);
};
template <class TraitsT, class NodeT> struct HasObsoleteCustomization {
static const bool value = HasGetNext<TraitsT, NodeT>::value ||
HasCreateSentinel<TraitsT>::value ||
HasCreateNode<TraitsT, NodeT>::value;
};
} // end namespace ilist_detail
//===----------------------------------------------------------------------===//
//
/// A wrapper around an intrusive list with callbacks and non-intrusive
/// ownership.
///
/// This wraps a purely intrusive list (like simple_ilist) with a configurable
/// traits class. The traits can implement callbacks and customize the
/// ownership semantics.
///
/// This is a subset of ilist functionality that can safely be used on nodes of
/// polymorphic types, i.e. a heterogeneous list with a common base class that
/// holds the next/prev pointers. The only state of the list itself is an
/// ilist_sentinel, which holds pointers to the first and last nodes in the
/// list.
template <class IntrusiveListT, class TraitsT>
class iplist_impl : public TraitsT, IntrusiveListT {
typedef IntrusiveListT base_list_type;
public:
typedef typename base_list_type::pointer pointer;
typedef typename base_list_type::const_pointer const_pointer;
typedef typename base_list_type::reference reference;
typedef typename base_list_type::const_reference const_reference;
typedef typename base_list_type::value_type value_type;
typedef typename base_list_type::size_type size_type;
typedef typename base_list_type::difference_type difference_type;
typedef typename base_list_type::iterator iterator;
typedef typename base_list_type::const_iterator const_iterator;
typedef typename base_list_type::reverse_iterator reverse_iterator;
typedef
typename base_list_type::const_reverse_iterator const_reverse_iterator;
private:
// TODO: Drop this assertion and the transitive type traits anytime after
// v4.0 is branched (i.e,. keep them for one release to help out-of-tree code
// update).
static_assert(
!ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value,
"ilist customization points have changed!");
static bool op_less(const_reference L, const_reference R) { return L < R; }
static bool op_equal(const_reference L, const_reference R) { return L == R; }
public:
iplist_impl() = default;
iplist_impl(const iplist_impl &) = delete;
iplist_impl &operator=(const iplist_impl &) = delete;
iplist_impl(iplist_impl &&X)
: TraitsT(std::move(static_cast<TraitsT &>(X))),
IntrusiveListT(std::move(static_cast<IntrusiveListT &>(X))) {}
iplist_impl &operator=(iplist_impl &&X) {
*static_cast<TraitsT *>(this) = std::move(static_cast<TraitsT &>(X));
*static_cast<IntrusiveListT *>(this) =
std::move(static_cast<IntrusiveListT &>(X));
return *this;
}
~iplist_impl() { clear(); }
// Miscellaneous inspection routines.
size_type max_size() const { return size_type(-1); }
using base_list_type::begin;
using base_list_type::end;
using base_list_type::rbegin;
using base_list_type::rend;
using base_list_type::empty;
using base_list_type::front;
using base_list_type::back;
void swap(iplist_impl &RHS) {
assert(0 && "Swap does not use list traits callback correctly yet!");
base_list_type::swap(RHS);
}
iterator insert(iterator where, pointer New) {
this->addNodeToList(New); // Notify traits that we added a node...
return base_list_type::insert(where, *New);
}
iterator insert(iterator where, const_reference New) {
return this->insert(where, new value_type(New));
}
iterator insertAfter(iterator where, pointer New) {
if (empty())
return insert(begin(), New);
else
return insert(++where, New);
}
/// Clone another list.
template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) {
clear();
for (const_reference V : L2)
push_back(clone(V));
}
pointer remove(iterator &IT) {
pointer Node = &*IT++;
this->removeNodeFromList(Node); // Notify traits that we removed a node...
base_list_type::remove(*Node);
return Node;
}
pointer remove(const iterator &IT) {
iterator MutIt = IT;
return remove(MutIt);
}
pointer remove(pointer IT) { return remove(iterator(IT)); }
pointer remove(reference IT) { return remove(iterator(IT)); }
// erase - remove a node from the controlled sequence... and delete it.
iterator erase(iterator where) {
this->deleteNode(remove(where));
return where;
}
iterator erase(pointer IT) { return erase(iterator(IT)); }
iterator erase(reference IT) { return erase(iterator(IT)); }
/// Remove all nodes from the list like clear(), but do not call
/// removeNodeFromList() or deleteNode().
///
/// This should only be used immediately before freeing nodes in bulk to
/// avoid traversing the list and bringing all the nodes into cache.
void clearAndLeakNodesUnsafely() { base_list_type::clear(); }
private:
// transfer - The heart of the splice function. Move linked list nodes from
// [first, last) into position.
//
void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) {
if (position == last)
return;
// Notify traits we moved the nodes...
this->transferNodesFromList(L2, first, last);
base_list_type::splice(position, L2, first, last);
}
public:
//===----------------------------------------------------------------------===
// Functionality derived from other functions defined above...
//
using base_list_type::size;
iterator erase(iterator first, iterator last) {
while (first != last)
first = erase(first);
return last;
}
void clear() { erase(begin(), end()); }
// Front and back inserters...
void push_front(pointer val) { insert(begin(), val); }
void push_back(pointer val) { insert(end(), val); }
void pop_front() {
assert(!empty() && "pop_front() on empty list!");
erase(begin());
}
void pop_back() {
assert(!empty() && "pop_back() on empty list!");
iterator t = end(); erase(--t);
}
// Special forms of insert...
template<class InIt> void insert(iterator where, InIt first, InIt last) {
for (; first != last; ++first) insert(where, *first);
}
// Splice members - defined in terms of transfer...
void splice(iterator where, iplist_impl &L2) {
if (!L2.empty())
transfer(where, L2, L2.begin(), L2.end());
}
void splice(iterator where, iplist_impl &L2, iterator first) {
iterator last = first; ++last;
if (where == first || where == last) return; // No change
transfer(where, L2, first, last);
}
void splice(iterator where, iplist_impl &L2, iterator first, iterator last) {
if (first != last) transfer(where, L2, first, last);
}
void splice(iterator where, iplist_impl &L2, reference N) {
splice(where, L2, iterator(N));
}
void splice(iterator where, iplist_impl &L2, pointer N) {
splice(where, L2, iterator(N));
}
template <class Compare>
void merge(iplist_impl &Right, Compare comp) {
if (this == &Right)
return;
this->transferNodesFromList(Right, Right.begin(), Right.end());
base_list_type::merge(Right, comp);
}
void merge(iplist_impl &Right) { return merge(Right, op_less); }
using base_list_type::sort;
/// Get the previous node, or \c nullptr for the list head.
pointer getPrevNode(reference N) const {
auto I = N.getIterator();
if (I == begin())
return nullptr;
return &*std::prev(I);
}
/// Get the previous node, or \c nullptr for the list head.
const_pointer getPrevNode(const_reference N) const {
return getPrevNode(const_cast<reference >(N));
}
/// Get the next node, or \c nullptr for the list tail.
pointer getNextNode(reference N) const {
auto Next = std::next(N.getIterator());
if (Next == end())
return nullptr;
return &*Next;
}
/// Get the next node, or \c nullptr for the list tail.
const_pointer getNextNode(const_reference N) const {
return getNextNode(const_cast<reference >(N));
}
};
/// An intrusive list with ownership and callbacks specified/controlled by
/// ilist_traits, only with API safe for polymorphic types.
///
/// The \p Options parameters are the same as those for \a simple_ilist. See
/// there for a description of what's available.
template <class T, class... Options>
class iplist
: public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
using iplist_impl_type = typename iplist::iplist_impl;
public:
iplist() = default;
iplist(const iplist &X) = delete;
iplist &operator=(const iplist &X) = delete;
iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
iplist &operator=(iplist &&X) {
*static_cast<iplist_impl_type *>(this) = std::move(X);
return *this;
}
};
template <class T, class... Options> using ilist = iplist<T, Options...>;
} // end namespace llvm
namespace std {
// Ensure that swap uses the fast list swap...
template<class Ty>
void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) {
Left.swap(Right);
}
} // end namespace std
#endif // LLVM_ADT_ILIST_H