llvm/llvm/include/llvm/ADT/simple_ilist.h

//===- llvm/ADT/simple_ilist.h - Simple Intrusive 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_SIMPLE_ILIST_H
#define LLVM_ADT_SIMPLE_ILIST_H

#include "llvm/ADT/ilist_base.h"
#include "llvm/ADT/ilist_iterator.h"
#include "llvm/ADT/ilist_node.h"
#include "llvm/ADT/ilist_node_options.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <utility>

namespace llvm {

/// A simple intrusive list implementation.
///
/// This is a simple intrusive list for a \c T that inherits from \c
/// ilist_node<T>.  The list never takes ownership of anything inserted in it.
///
/// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never deletes
/// values, and has no callback traits.
///
/// The API for adding nodes include \a push_front(), \a push_back(), and \a
/// insert().  These all take values by reference (not by pointer), except for
/// the range version of \a insert().
///
/// There are three sets of API for discarding nodes from the list: \a
/// remove(), which takes a reference to the node to remove, \a erase(), which
/// takes an iterator or iterator range and returns the next one, and \a
/// clear(), which empties out the container.  All three are constant time
/// operations.  None of these deletes any nodes; in particular, if there is a
/// single node in the list, then these have identical semantics:
/// \li \c L.remove(L.front());
/// \li \c L.erase(L.begin());
/// \li \c L.clear();
///
/// As a convenience for callers, there are parallel APIs that take a \c
/// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a
/// eraseAndDispose(), and \a clearAndDispose().  These have different names
/// because the extra semantic is otherwise non-obvious.  They are equivalent
/// to calling \a std::for_each() on the range to be discarded.
///
/// The currently available \p Options customize the nodes in the list.  The
/// same options must be specified in the \a ilist_node instantiation for
/// compatibility (although the order is irrelevant).
/// \li Use \a ilist_tag to designate which ilist_node for a given \p T this
/// list should use.  This is useful if a type \p T is part of multiple,
/// independent lists simultaneously.
/// \li Use \a ilist_sentinel_tracking to always (or never) track whether a
/// node is a sentinel.  Specifying \c true enables the \a
/// ilist_node::isSentinel() API.  Unlike \a ilist_node::isKnownSentinel(),
/// which is only appropriate for assertions, \a ilist_node::isSentinel() is
/// appropriate for real logic.
///
/// Here are examples of \p Options usage:
/// \li \c simple_ilist<T> gives the defaults.  \li \c
/// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a
/// ilist_node::isSentinel() API.
/// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>>
/// specifies a tag of A and that tracking should be off (even when
/// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled).
/// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is
/// equivalent to the last.
///
/// See \a is_valid_option for steps on adding a new option.
template <typename T, class... Options>
class simple_ilist
    : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
      ilist_detail::SpecificNodeAccess<
          typename ilist_detail::compute_node_options<T, Options...>::type> { … };

template <class T, class... Options>
template <class Compare>
void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { … }

template <class T, class... Options>
template <class Compare>
void simple_ilist<T, Options...>::sort(Compare comp) { … }

} // end namespace llvm

#endif // LLVM_ADT_SIMPLE_ILIST_H