diff options
Diffstat (limited to 'libbase/include/core/adt')
| -rw-r--r-- | libbase/include/core/adt/PointerIntPair.h | 301 | ||||
| -rw-r--r-- | libbase/include/core/adt/PointerLikeTypeTraits.h | 165 | ||||
| -rw-r--r-- | libbase/include/core/adt/STLFunctionalExtras.h | 112 | ||||
| -rw-r--r-- | libbase/include/core/adt/SmallVector.h | 1926 | ||||
| -rw-r--r-- | libbase/include/core/adt/Twine.h | 679 | ||||
| -rw-r--r-- | libbase/include/core/adt/ilist.h | 546 | ||||
| -rw-r--r-- | libbase/include/core/adt/ilist_base.h | 139 | ||||
| -rw-r--r-- | libbase/include/core/adt/ilist_iterator.h | 591 | ||||
| -rw-r--r-- | libbase/include/core/adt/ilist_node.h | 470 | ||||
| -rw-r--r-- | libbase/include/core/adt/ilist_node_base.h | 167 | ||||
| -rw-r--r-- | libbase/include/core/adt/ilist_node_options.h | 244 | ||||
| -rw-r--r-- | libbase/include/core/adt/simple_ilist.h | 482 |
12 files changed, 5822 insertions, 0 deletions
diff --git a/libbase/include/core/adt/PointerIntPair.h b/libbase/include/core/adt/PointerIntPair.h new file mode 100644 index 0000000..6a7f5db --- /dev/null +++ b/libbase/include/core/adt/PointerIntPair.h @@ -0,0 +1,301 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/PointerIntPair.h - Pair for pointer and int -----*- 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 the PointerIntPair class. +/// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_POINTERINTPAIR_H +#define LIBBASE_ADT_POINTERINTPAIR_H + +#include "core/compiler/Compiler.h" +#include "core/adt/PointerLikeTypeTraits.h" +#include <cassert> +#include <cstdint> +#include <cstring> +#include <limits> +#include <type_traits> + +namespace libbase { + +namespace detail { +template <typename Ptr> struct PunnedPointer { + static_assert(sizeof(Ptr) == sizeof(intptr_t), ""); + + // Asserts that allow us to let the compiler implement the destructor and + // copy/move constructors + static_assert(std::is_trivially_destructible<Ptr>::value, ""); + static_assert(std::is_trivially_copy_constructible<Ptr>::value, ""); + static_assert(std::is_trivially_move_constructible<Ptr>::value, ""); + + explicit constexpr PunnedPointer(intptr_t i = 0) { *this = i; } + + constexpr intptr_t asInt() const { + intptr_t R = 0; + std::memcpy(&R, Data, sizeof(R)); + return R; + } + + constexpr operator intptr_t() const { return asInt(); } + + constexpr PunnedPointer &operator=(intptr_t V) { + std::memcpy(Data, &V, sizeof(Data)); + return *this; + } + + Ptr *getPointerAddress() { return reinterpret_cast<Ptr *>(Data); } + const Ptr *getPointerAddress() const { return reinterpret_cast<Ptr *>(Data); } + +private: + alignas(Ptr) unsigned char Data[sizeof(Ptr)]; +}; +} // namespace detail + +template <typename T, typename Enable> struct DenseMapInfo; +template <typename PointerT, unsigned IntBits, typename PtrTraits> +struct PointerIntPairInfo; + +/// PointerIntPair - This class implements a pair of a pointer and small +/// integer. It is designed to represent this in the space required by one +/// pointer by bitmangling the integer into the low part of the pointer. This +/// can only be done for small integers: typically up to 3 bits, but it depends +/// on the number of bits available according to PointerLikeTypeTraits for the +/// type. +/// +/// Note that PointerIntPair always puts the IntVal part in the highest bits +/// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for +/// the bool into bit #2, not bit #0, which allows the low two bits to be used +/// for something else. For example, this allows: +/// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> +/// ... and the two bools will land in different bits. +template <typename PointerTy, unsigned IntBits, typename IntType = unsigned, + typename PtrTraits = PointerLikeTypeTraits<PointerTy>, + typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>> +class PointerIntPair { + // Used by MSVC visualizer and generally helpful for debugging/visualizing. + using InfoTy = Info; + detail::PunnedPointer<PointerTy> Value; + +public: + constexpr PointerIntPair() = default; + + PointerIntPair(PointerTy PtrVal, IntType IntVal) { + setPointerAndInt(PtrVal, IntVal); + } + + explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); } + + PointerTy getPointer() const { return Info::getPointer(Value); } + + IntType getInt() const { return (IntType)Info::getInt(Value); } + + void setPointer(PointerTy PtrVal) & { + Value = Info::updatePointer(Value, PtrVal); + } + + void setInt(IntType IntVal) & { + Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal)); + } + + void initWithPointer(PointerTy PtrVal) & { + Value = Info::updatePointer(0, PtrVal); + } + + void setPointerAndInt(PointerTy PtrVal, IntType IntVal) & { + Value = Info::updateInt(Info::updatePointer(0, PtrVal), + static_cast<intptr_t>(IntVal)); + } + + PointerTy const *getAddrOfPointer() const { + return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); + } + + PointerTy *getAddrOfPointer() { + assert(Value == reinterpret_cast<intptr_t>(getPointer()) && + "Can only return the address if IntBits is cleared and " + "PtrTraits doesn't change the pointer"); + return Value.getPointerAddress(); + } + + void *getOpaqueValue() const { + return reinterpret_cast<void *>(Value.asInt()); + } + + void setFromOpaqueValue(void *Val) & { + Value = reinterpret_cast<intptr_t>(Val); + } + + static PointerIntPair getFromOpaqueValue(void *V) { + PointerIntPair P; + P.setFromOpaqueValue(V); + return P; + } + + // Allow PointerIntPairs to be created from const void * if and only if the + // pointer type could be created from a const void *. + static PointerIntPair getFromOpaqueValue(const void *V) { + (void)PtrTraits::getFromVoidPointer(V); + return getFromOpaqueValue(const_cast<void *>(V)); + } + + bool operator==(const PointerIntPair &RHS) const { + return Value == RHS.Value; + } + + bool operator!=(const PointerIntPair &RHS) const { + return Value != RHS.Value; + } + + bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; } + bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; } + + bool operator<=(const PointerIntPair &RHS) const { + return Value <= RHS.Value; + } + + bool operator>=(const PointerIntPair &RHS) const { + return Value >= RHS.Value; + } +}; + +template <typename PointerT, unsigned IntBits, typename PtrTraits> +struct PointerIntPairInfo { + static_assert(PtrTraits::NumLowBitsAvailable < + std::numeric_limits<uintptr_t>::digits, + "cannot use a pointer type that has all bits free"); + static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, + "PointerIntPair with integer size too large for pointer"); + enum MaskAndShiftConstants : uintptr_t { + /// PointerBitMask - The bits that come from the pointer. + PointerBitMask = (~(uintptr_t)0) << PtrTraits::NumLowBitsAvailable, + + /// IntShift - The number of low bits that we reserve for other uses, and + /// keep zero. + IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits, + + /// IntMask - This is the unshifted mask for valid bits of the int type. + IntMask = ((uintptr_t)1 << IntBits) - 1, + + // ShiftedIntMask - This is the bits for the integer shifted in place. + ShiftedIntMask = (uintptr_t)(IntMask << IntShift) + }; + + static PointerT getPointer(intptr_t Value) { + return PtrTraits::getFromVoidPointer( + reinterpret_cast<void *>(Value & PointerBitMask)); + } + + static intptr_t getInt(intptr_t Value) { + return (Value >> IntShift) & IntMask; + } + + static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) { + intptr_t PtrWord = + reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); + assert((PtrWord & ~PointerBitMask) == 0 && + "Pointer is not sufficiently aligned"); + // Preserve all low bits, just update the pointer. + return PtrWord | (OrigValue & ~PointerBitMask); + } + + static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) { + assert((Int & ~IntMask) == 0 && "Integer too large for field"); + + // Preserve all bits other than the ones we are updating. + return (OrigValue & ~ShiftedIntMask) | Int << IntShift; + } +}; + +// Provide specialization of DenseMapInfo for PointerIntPair. +template <typename PointerTy, unsigned IntBits, typename IntType> +struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>, void> { + using Ty = PointerIntPair<PointerTy, IntBits, IntType>; + + static unsigned getHashValue(Ty V) { + uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); + return unsigned(IV) ^ unsigned(IV >> 9); + } + + static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } +}; + +// Teach SmallPtrSet that PointerIntPair is "basically a pointer". +template <typename PointerTy, unsigned IntBits, typename IntType, + typename PtrTraits> +struct PointerLikeTypeTraits< + PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> { + static inline void * + getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { + return P.getOpaqueValue(); + } + + static inline PointerIntPair<PointerTy, IntBits, IntType> + getFromVoidPointer(void *P) { + return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); + } + + static inline PointerIntPair<PointerTy, IntBits, IntType> + getFromVoidPointer(const void *P) { + return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); + } + + static constexpr int NumLowBitsAvailable = + PtrTraits::NumLowBitsAvailable - IntBits; +}; + +// Allow structured bindings on PointerIntPair. +template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType, + typename PtrTraits, typename Info> +decltype(auto) +get(const PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info> &Pair) { + static_assert(I < 2); + if constexpr (I == 0) + return Pair.getPointer(); + else + return Pair.getInt(); +} + +} // end namespace libbase + +namespace std { +template <typename PointerTy, unsigned IntBits, typename IntType, + typename PtrTraits, typename Info> +struct tuple_size< + libbase::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> + : std::integral_constant<std::size_t, 2> {}; + +template <std::size_t I, typename PointerTy, unsigned IntBits, typename IntType, + typename PtrTraits, typename Info> +struct tuple_element< + I, libbase::PointerIntPair<PointerTy, IntBits, IntType, PtrTraits, Info>> + : std::conditional<I == 0, PointerTy, IntType> {}; +} // namespace std + +#endif // LIBBASE_ADT_POINTERINTPAIR_H diff --git a/libbase/include/core/adt/PointerLikeTypeTraits.h b/libbase/include/core/adt/PointerLikeTypeTraits.h new file mode 100644 index 0000000..9c1a36f --- /dev/null +++ b/libbase/include/core/adt/PointerLikeTypeTraits.h @@ -0,0 +1,165 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/PointerLikeTypeTraits.h - Pointer Traits ----*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file defines the PointerLikeTypeTraits class. This allows data +// structures to reason about pointers and other things that are pointer sized. +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_POINTERLIKETYPETRAITS_H +#define LIBBASE_ADT_POINTERLIKETYPETRAITS_H + +#include "core/compiler/DataTypes.h" +#include "core/math/MathExtras.h" +#include <cassert> + +namespace libbase { + +/// A traits type that is used to handle pointer types and things that are just +/// wrappers for pointers as a uniform entity. +template <typename T> struct PointerLikeTypeTraits; + +namespace detail { +// Provide a trait to check if T is pointer-like. +template <typename T, typename U = void> struct HasPointerLikeTypeTraits { + static const bool value = false; +}; + +// sizeof(T) is valid only for a complete T. +template <typename T> +struct HasPointerLikeTypeTraits< + T, decltype((sizeof(PointerLikeTypeTraits<T>) + sizeof(T)), void())> { + static const bool value = true; +}; + +template <typename T> struct IsPointerLike { + static const bool value = HasPointerLikeTypeTraits<T>::value; +}; + +template <typename T> struct IsPointerLike<T *> { + static const bool value = true; +}; +} // namespace detail + +// Provide PointerLikeTypeTraits for non-cvr pointers. +template <typename T> struct PointerLikeTypeTraits<T *> { + static inline void *getAsVoidPointer(T *P) { return P; } + static inline T *getFromVoidPointer(void *P) { return static_cast<T *>(P); } + + static constexpr int NumLowBitsAvailable = ConstantLog2<alignof(T)>(); +}; + +template <> struct PointerLikeTypeTraits<void *> { + static inline void *getAsVoidPointer(void *P) { return P; } + static inline void *getFromVoidPointer(void *P) { return P; } + + /// Note, we assume here that void* is related to raw malloc'ed memory and + /// that malloc returns objects at least 4-byte aligned. However, this may be + /// wrong, or pointers may be from something other than malloc. In this case, + /// you should specify a real typed pointer or avoid this template. + /// + /// All clients should use assertions to do a run-time check to ensure that + /// this is actually true. + static constexpr int NumLowBitsAvailable = 2; +}; + +// Provide PointerLikeTypeTraits for const things. +template <typename T> struct PointerLikeTypeTraits<const T> { + using NonConst = PointerLikeTypeTraits<T>; + + static inline const void *getAsVoidPointer(const T P) { + return NonConst::getAsVoidPointer(P); + } + static inline const T getFromVoidPointer(const void *P) { + return NonConst::getFromVoidPointer(const_cast<void *>(P)); + } + static constexpr int NumLowBitsAvailable = NonConst::NumLowBitsAvailable; +}; + +// Provide PointerLikeTypeTraits for const pointers. +template <typename T> struct PointerLikeTypeTraits<const T *> { + using NonConst = PointerLikeTypeTraits<T *>; + + static inline const void *getAsVoidPointer(const T *P) { + return NonConst::getAsVoidPointer(const_cast<T *>(P)); + } + static inline const T *getFromVoidPointer(const void *P) { + return NonConst::getFromVoidPointer(const_cast<void *>(P)); + } + static constexpr int NumLowBitsAvailable = NonConst::NumLowBitsAvailable; +}; + +// Provide PointerLikeTypeTraits for uintptr_t. +template <> struct PointerLikeTypeTraits<uintptr_t> { + static inline void *getAsVoidPointer(uintptr_t P) { + return reinterpret_cast<void *>(P); + } + static inline uintptr_t getFromVoidPointer(void *P) { + return reinterpret_cast<uintptr_t>(P); + } + // No bits are available! + static constexpr int NumLowBitsAvailable = 0; +}; + +/// Provide suitable custom traits struct for function pointers. +/// +/// Function pointers can't be directly given these traits as functions can't +/// have their alignment computed with `alignof` and we need different casting. +/// +/// To rely on higher alignment for a specialized use, you can provide a +/// customized form of this template explicitly with higher alignment, and +/// potentially use alignment attributes on functions to satisfy that. +template <int Alignment, typename FunctionPointerT> +struct FunctionPointerLikeTypeTraits { + static constexpr int NumLowBitsAvailable = ConstantLog2<Alignment>(); + static inline void *getAsVoidPointer(FunctionPointerT P) { + assert((reinterpret_cast<uintptr_t>(P) & + ~((uintptr_t)-1 << NumLowBitsAvailable)) == 0 && + "Alignment not satisfied for an actual function pointer!"); + return reinterpret_cast<void *>(P); + } + static inline FunctionPointerT getFromVoidPointer(void *P) { + return reinterpret_cast<FunctionPointerT>(P); + } +}; + +/// Provide a default specialization for function pointers that assumes 4-byte +/// alignment. +/// +/// We assume here that functions used with this are always at least 4-byte +/// aligned. This means that, for example, thumb functions won't work or systems +/// with weird unaligned function pointers won't work. But all practical systems +/// we support satisfy this requirement. +template <typename ReturnT, typename... ParamTs> +struct PointerLikeTypeTraits<ReturnT (*)(ParamTs...)> + : FunctionPointerLikeTypeTraits<4, ReturnT (*)(ParamTs...)> {}; + +} // end namespace libbase + +#endif diff --git a/libbase/include/core/adt/STLFunctionalExtras.h b/libbase/include/core/adt/STLFunctionalExtras.h new file mode 100644 index 0000000..8c88905 --- /dev/null +++ b/libbase/include/core/adt/STLFunctionalExtras.h @@ -0,0 +1,112 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===- llvm/ADT/STLFunctionalExtras.h - Extras for <functional> -*- 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 +// +//===----------------------------------------------------------------------===// +// +// This file contains some extension to <functional>. +// +// No library is required when using these functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_STLFUNCTIONALEXTRAS_H +#define LIBBASE_ADT_STLFUNCTIONALEXTRAS_H + +#include "core/compiler/Compiler.h" + +#include <cstddef> +#include <cstdint> +#include <type_traits> +#include <utility> + +namespace libbase +{ + +//===----------------------------------------------------------------------===// +// Extra additions to <functional> +//===----------------------------------------------------------------------===// + +/// An efficient, type-erasing, non-owning reference to a callable. This is +/// intended for use as the type of a function parameter that is not used +/// after the function in question returns. +/// +/// This class does not own the callable, so it is not in general safe to store +/// a function_ref. +template <typename Fn> class function_ref; + +template <typename Ret, typename... Params> +class LIBBASE_GSL_POINTER function_ref<Ret (Params...)> +{ + Ret (*callback) (intptr_t callable, Params... params) = nullptr; + intptr_t callable = 0; + + template <typename Callable> + static Ret + callback_fn (intptr_t callable, Params... params) + { + return (*reinterpret_cast<Callable *> (callable)) ( + std::forward<Params> (params)...); + } + +public: + function_ref () = default; + function_ref (std::nullptr_t) + { + } + + template <typename Callable> + function_ref ( + Callable &&callable LIBBASE_LIFETIME_BOUND, + // This is not the copy-constructor. + std::enable_if_t<!std::is_same<std::remove_cvref_t<Callable>, + function_ref>::value> * = nullptr, + // Functor must be callable and return a suitable type. + std::enable_if_t<std::is_void<Ret>::value || + std::is_convertible<decltype (std::declval<Callable> () ( + std::declval<Params> ()...)), + Ret>::value> * = nullptr) + : callback (callback_fn<std::remove_reference_t<Callable>>), + callable (reinterpret_cast<intptr_t> (&callable)) + { + } + + Ret + operator() (Params... params) const + { + return callback (callable, std::forward<Params> (params)...); + } + + explicit + operator bool () const + { + return callback; + } +}; + +} // end namespace libbase + +#endif // LIBBASE_ADT_STLFUNCTIONALEXTRAS_H diff --git a/libbase/include/core/adt/SmallVector.h b/libbase/include/core/adt/SmallVector.h new file mode 100644 index 0000000..37d974a --- /dev/null +++ b/libbase/include/core/adt/SmallVector.h @@ -0,0 +1,1926 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===- rcc/ADT/SmallVector.h - 'Normally small' vectors --------*- 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 the SmallVector class. +/// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_SMALLVECTOR_H +#define LIBBASE_ADT_SMALLVECTOR_H + +#include "core/compiler/Compiler.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <cstdint> +#include <cstdlib> +#include <cstring> +#include <functional> +#include <initializer_list> +#include <iterator> +#include <limits> +#include <memory> +#include <new> +#include <ranges> +#include <type_traits> +#include <utility> + +namespace libbase +{ + +template <typename T> class ArrayRef; + +template <typename IteratorT> class iterator_range; + +template <class Iterator, class Tag> +using HasIteratorTag = std::is_convertible< + typename std::iterator_traits<Iterator>::iterator_category, Tag>; + +template <class Iterator> +using EnableIfConvertibleToInputIterator = + std::enable_if_t<HasIteratorTag<Iterator, std::input_iterator_tag>::value>; + +/// This is all the stuff common to all SmallVectors. +/// +/// The template parameter specifies the type which should be used to hold the +/// Size and Capacity of the SmallVector, so it can be adjusted. +/// Using 32 bit size is desirable to shrink the size of the SmallVector. +/// Using 64 bit size is desirable for cases like SmallVector<char>, where a +/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for +/// buffering bitcode output - which can exceed 4GB. +template <class Size_T> class SmallVectorBase +{ +protected: + void *BeginX; + Size_T Size = 0, Capacity; + + /// The maximum value of the Size_T used. + static constexpr size_t + SizeTypeMax () + { + return std::numeric_limits<Size_T>::max (); + } + + SmallVectorBase () = delete; + SmallVectorBase (void *FirstEl, size_t TotalCapacity) + : BeginX (FirstEl), Capacity (static_cast<Size_T> (TotalCapacity)) + { + } + + /// This is a helper for \a grow() that's out of line to reduce code + /// duplication. This function will report a fatal error if it can't grow at + /// least to \p MinSize. + LIBBASE_ABI void * + mallocForGrow (void *FirstEl, size_t MinSize, size_t TSize, + size_t &NewCapacity); + + /// This is an implementation of the grow() method which only works + /// on POD-like data types and is out of line to reduce code duplication. + /// This function will report a fatal error if it cannot increase capacity. + LIBBASE_ABI void + grow_pod (void *FirstEl, size_t MinSize, size_t TSize); + +public: + size_t + size () const + { + return Size; + } + size_t + capacity () const + { + return Capacity; + } + + [[nodiscard]] bool + empty () const + { + return !Size; + } + +protected: + /// Set the array size to \p N, which the current array must have enough + /// capacity for. + /// + /// This does not construct or destroy any elements in the vector. + void + set_size (size_t N) + { + assert (N <= capacity ()); // implies no overflow in assignment + Size = static_cast<Size_T> (N); + } + + /// Set the array data pointer to \p Begin and capacity to \p N. + /// + /// This does not construct or destroy any elements in the vector. + // This does not clean up any existing allocation. + void + set_allocation_range (void *Begin, size_t N) + { + assert (N <= SizeTypeMax ()); + BeginX = Begin; + Capacity = static_cast<Size_T> (N); + } +}; + +template <class T> +using SmallVectorSizeType = + std::conditional_t<sizeof (T) < 4 && sizeof (void *) >= 8, uint64_t, + uint32_t>; + +/// Figure out the offset of the first element. +template <class T, typename = void> struct SmallVectorAlignmentAndSize +{ + alignas (SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof ( + SmallVectorBase<SmallVectorSizeType<T>>)]; + alignas (T) char FirstEl[sizeof (T)]; +}; + +/// This is the part of SmallVectorTemplateBase which does not depend on whether +/// the type T is a POD. The extra dummy template argument is used by ArrayRef +/// to avoid unnecessarily requiring T to be complete. +template <typename T, typename = void> +class SmallVectorTemplateCommon : public SmallVectorBase<SmallVectorSizeType<T>> +{ + using Base = SmallVectorBase<SmallVectorSizeType<T>>; + +protected: + /// Find the address of the first element. For this pointer math to be valid + /// with small-size of 0 for T with lots of alignment, it's important that + /// SmallVectorStorage is properly-aligned even for small-size of 0. + void * + getFirstEl () const + { + return const_cast<void *> (reinterpret_cast<const void *> ( + reinterpret_cast<const char *> (this) + + offsetof (SmallVectorAlignmentAndSize<T>, FirstEl))); + } + // Space after 'FirstEl' is clobbered, do not add any instance vars after it. + + SmallVectorTemplateCommon (size_t SizeArg) : Base (getFirstEl (), SizeArg) + { + } + + void + grow_pod (size_t MinSize, size_t TSize) + { + Base::grow_pod (getFirstEl (), MinSize, TSize); + } + + /// Return true if this is a smallvector which has not had dynamic + /// memory allocated for it. + bool + isSmall () const + { + return this->BeginX == getFirstEl (); + } + + /// Put this vector in a state of being small. + void + resetToSmall () + { + this->BeginX = getFirstEl (); + // The inline capacity is unknown here. SmallVector restores it when moving + // from the same concrete type; moves through SmallVectorImpl leave it at 0. + this->Size = this->Capacity = 0; + } + + /// Return true if V is an internal reference to the given range. + bool + isReferenceToRange (const void *V, const void *First, const void *Last) const + { + // Use std::less to avoid UB. + std::less<> LessThan; + return !LessThan (V, First) && LessThan (V, Last); + } + + /// Return true if V is an internal reference to this vector. + bool + isReferenceToStorage (const void *V) const + { + return isReferenceToRange (V, this->begin (), this->end ()); + } + + /// Return true if First and Last form a valid (possibly empty) range in this + /// vector's storage. + bool + isRangeInStorage (const void *First, const void *Last) const + { + // Use std::less to avoid UB. + std::less<> LessThan; + return !LessThan (First, this->begin ()) && !LessThan (Last, First) && + !LessThan (this->end (), Last); + } + + /// Return true unless Elt will be invalidated by resizing the vector to + /// NewSize. + bool + isSafeToReferenceAfterResize (const void *Elt, size_t NewSize) + { + // Past the end. + if (LIBBASE_LIKELY (!isReferenceToStorage (Elt))) + { + return true; + } + + // Return false if Elt will be destroyed by shrinking. + if (NewSize <= this->size ()) + { + return Elt < this->begin () + NewSize; + } + + // Return false if we need to grow. + return NewSize <= this->capacity (); + } + + /// Check whether Elt will be invalidated by resizing the vector to NewSize. + void + assertSafeToReferenceAfterResize (const void *Elt, size_t NewSize) + { + assert (isSafeToReferenceAfterResize (Elt, NewSize) && + "Attempting to reference an element of the vector in an operation " + "that invalidates it"); + } + + /// Check whether Elt will be invalidated by increasing the size of the + /// vector by N. + void + assertSafeToAdd (const void *Elt, size_t N = 1) + { + this->assertSafeToReferenceAfterResize (Elt, this->size () + N); + } + + /// Check whether any part of the range will be invalidated by clearing. + template <class ItTy> + void + assertSafeToReferenceAfterClear (ItTy From, ItTy To) + { + if constexpr (std::is_pointer_v<ItTy> && + std::is_same_v< + std::remove_const_t<std::remove_pointer_t<ItTy>>, + std::remove_const_t<T>>) + { + if (From == To) + { + return; + } + this->assertSafeToReferenceAfterResize (From, 0); + this->assertSafeToReferenceAfterResize (To - 1, 0); + } + (void)From; + (void)To; + } + + /// Check whether any part of the range will be invalidated by growing. + template <class ItTy> + void + assertSafeToAddRange (ItTy From, ItTy To) + { + if constexpr (std::is_pointer_v<ItTy> && + std::is_same_v<std::remove_cv_t<std::remove_pointer_t<ItTy>>, + T>) + { + if (From == To) + { + return; + } + this->assertSafeToAdd (From, To - From); + this->assertSafeToAdd (To - 1, To - From); + } + (void)From; + (void)To; + } + + /// Reserve enough space to add one element, and return the updated element + /// pointer in case it was a reference to the storage. + template <class U> + static const T * + reserveForParamAndGetAddressImpl (U *This, const T &Elt, size_t N) + { + size_t NewSize = This->size () + N; + if (LIBBASE_LIKELY (NewSize <= This->capacity ())) + { + return &Elt; + } + + bool ReferencesStorage = false; + int64_t Index = -1; + if (!U::TakesParamByValue) + { + if (LIBBASE_UNLIKELY (This->isReferenceToStorage (&Elt))) + { + ReferencesStorage = true; + Index = &Elt - This->begin (); + } + } + This->grow (NewSize); + return ReferencesStorage ? This->begin () + Index : &Elt; + } + +public: + using size_type = size_t; + using difference_type = ptrdiff_t; + using value_type = T; + using iterator = T *; + using const_iterator = const T *; + + using const_reverse_iterator = std::reverse_iterator<const_iterator>; + using reverse_iterator = std::reverse_iterator<iterator>; + + using reference = T &; + using const_reference = const T &; + using pointer = T *; + using const_pointer = const T *; + + using Base::capacity; + using Base::empty; + using Base::size; + + // forward iterator creation methods. + iterator + begin () + { + return (iterator)this->BeginX; + } + const_iterator + begin () const + { + return (const_iterator)this->BeginX; + } + iterator + end () + { + return begin () + size (); + } + const_iterator + end () const + { + return begin () + size (); + } + + // reverse iterator creation methods. + reverse_iterator + rbegin () + { + return reverse_iterator (end ()); + } + const_reverse_iterator + rbegin () const + { + return const_reverse_iterator (end ()); + } + reverse_iterator + rend () + { + return reverse_iterator (begin ()); + } + const_reverse_iterator + rend () const + { + return const_reverse_iterator (begin ()); + } + + size_type + size_in_bytes () const + { + return size () * sizeof (T); + } + size_type + max_size () const + { + return std::min (this->SizeTypeMax (), size_type (-1) / sizeof (T)); + } + + size_t + capacity_in_bytes () const + { + return capacity () * sizeof (T); + } + + /// Return a pointer to the vector's buffer, even if empty(). + pointer + data () + { + return pointer (begin ()); + } + /// Return a pointer to the vector's buffer, even if empty(). + const_pointer + data () const + { + return const_pointer (begin ()); + } + + reference + operator[] (size_type idx) + { + assert (idx < size ()); + return begin ()[idx]; + } + const_reference + operator[] (size_type idx) const + { + assert (idx < size ()); + return begin ()[idx]; + } + + reference + front () + { + assert (!empty ()); + return begin ()[0]; + } + const_reference + front () const + { + assert (!empty ()); + return begin ()[0]; + } + + reference + back () + { + assert (!empty ()); + return end ()[-1]; + } + const_reference + back () const + { + assert (!empty ()); + return end ()[-1]; + } +}; + +/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put +/// method implementations that are designed to work with non-trivial T's. +/// +/// We approximate is_trivially_copyable with trivial move/copy construction and +/// trivial destruction. While the standard doesn't specify that you're allowed +/// copy these types with memcpy, there is no way for the type to observe this. +/// This catches the important case of std::pair<POD, POD>, which is not +/// trivially assignable. +template <typename T, bool = (std::is_trivially_copy_constructible<T>::value) && + (std::is_trivially_move_constructible<T>::value) && + std::is_trivially_destructible<T>::value> +class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> +{ + friend class SmallVectorTemplateCommon<T>; + +protected: + static constexpr bool TakesParamByValue = false; + using ValueParamT = const T &; + + SmallVectorTemplateBase (size_t SizeArg) + : SmallVectorTemplateCommon<T> (SizeArg) + { + } + + static void + destroy_range (T *S, T *E) + { + while (S != E) + { + --E; + E->~T (); + } + } + + /// Move the range [I, E) into the uninitialized memory starting with "Dest", + /// constructing elements as needed. + template <typename It1, typename It2> + static void + uninitialized_move (It1 I, It1 E, It2 Dest) + { + std::uninitialized_move (I, E, Dest); + } + + /// Copy the range [I, E) onto the uninitialized memory starting with "Dest", + /// constructing elements as needed. + template <typename It1, typename It2> + static void + uninitialized_copy (It1 I, It1 E, It2 Dest) + { + std::uninitialized_copy (I, E, Dest); + } + + /// Grow the allocated memory (without initializing new elements), doubling + /// the size of the allocated memory. Guarantees space for at least one more + /// element, or MinSize more elements if specified. + void + grow (size_t MinSize = 0); + + /// Create a new allocation big enough for \p MinSize and pass back its size + /// in \p NewCapacity. This is the first section of \a grow(). + T * + mallocForGrow (size_t MinSize, size_t &NewCapacity); + + /// Move existing elements over to the new allocation \p NewElts, the middle + /// section of \a grow(). + void + moveElementsForGrow (T *NewElts); + + /// Transfer ownership of the allocation, finishing up \a grow(). + void + takeAllocationForGrow (T *NewElts, size_t NewCapacity); + + /// Reserve enough space to add one element, and return the updated element + /// pointer in case it was a reference to the storage. + const T * + reserveForParamAndGetAddress (const T &Elt, size_t N = 1) + { + return this->reserveForParamAndGetAddressImpl (this, Elt, N); + } + + /// Reserve enough space to add one element, and return the updated element + /// pointer in case it was a reference to the storage. + T * + reserveForParamAndGetAddress (T &Elt, size_t N = 1) + { + return const_cast<T *> ( + this->reserveForParamAndGetAddressImpl (this, Elt, N)); + } + + static T && + forward_value_param (T &&V) + { + return std::move (V); + } + static const T & + forward_value_param (const T &V) + { + return V; + } + + void + growAndAssign (size_t NumElts, const T &Elt) + { + // Grow manually in case Elt is an internal reference. + size_t NewCapacity; + T *NewElts = mallocForGrow (NumElts, NewCapacity); + std::uninitialized_fill_n (NewElts, NumElts, Elt); + this->destroy_range (this->begin (), this->end ()); + takeAllocationForGrow (NewElts, NewCapacity); + this->set_size (NumElts); + } + + template <typename... ArgTypes> + T & + growAndEmplaceBack (ArgTypes &&...Args) + { + // Grow manually in case one of Args is an internal reference. + size_t NewCapacity; + T *NewElts = mallocForGrow (0, NewCapacity); + ::new ((void *)(NewElts + this->size ())) + T (std::forward<ArgTypes> (Args)...); + moveElementsForGrow (NewElts); + takeAllocationForGrow (NewElts, NewCapacity); + this->set_size (this->size () + 1); + return this->back (); + } + +public: + void + push_back (const T &Elt) + { + const T *EltPtr = reserveForParamAndGetAddress (Elt); + ::new ((void *)this->end ()) T (*EltPtr); + this->set_size (this->size () + 1); + } + + void + push_back (T &&Elt) + { + T *EltPtr = reserveForParamAndGetAddress (Elt); + ::new ((void *)this->end ()) T (::std::move (*EltPtr)); + this->set_size (this->size () + 1); + } + + void + pop_back () + { + this->set_size (this->size () - 1); + this->end ()->~T (); + } +}; + +// Define this out-of-line to dissuade the C++ compiler from inlining it. +template <typename T, bool TriviallyCopyable> +void +SmallVectorTemplateBase<T, TriviallyCopyable>::grow (size_t MinSize) +{ + size_t NewCapacity; + T *NewElts = mallocForGrow (MinSize, NewCapacity); + moveElementsForGrow (NewElts); + takeAllocationForGrow (NewElts, NewCapacity); +} + +template <typename T, bool TriviallyCopyable> +T * +SmallVectorTemplateBase<T, TriviallyCopyable>::mallocForGrow ( + size_t MinSize, size_t &NewCapacity) +{ + return static_cast<T *> ( + SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow ( + this->getFirstEl (), MinSize, sizeof (T), NewCapacity)); +} + +// Define this out-of-line to dissuade the C++ compiler from inlining it. +template <typename T, bool TriviallyCopyable> +void +SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow (T *NewElts) +{ + // Move the elements over. + this->uninitialized_move (this->begin (), this->end (), NewElts); + + // Destroy the original elements. + destroy_range (this->begin (), this->end ()); +} + +// Define this out-of-line to dissuade the C++ compiler from inlining it. +template <typename T, bool TriviallyCopyable> +void +SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow ( + T *NewElts, size_t NewCapacity) +{ + // If this wasn't grown from the inline copy, deallocate the old space. + if (!this->isSmall ()) + { + free (this->begin ()); + } + + this->set_allocation_range (NewElts, NewCapacity); +} + +/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put +/// method implementations that are designed to work with trivially copyable +/// T's. This allows using memcpy in place of copy/move construction and +/// skipping destruction. +template <typename T> +class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> +{ + friend class SmallVectorTemplateCommon<T>; + +protected: + /// True if it's cheap enough to take parameters by value. Doing so avoids + /// overhead related to mitigations for reference invalidation. + static constexpr bool TakesParamByValue = sizeof (T) <= 2 * sizeof (void *); + + /// Either const T& or T, depending on whether it's cheap enough to take + /// parameters by value. + using ValueParamT = std::conditional_t<TakesParamByValue, T, const T &>; + + SmallVectorTemplateBase (size_t SizeArg) + : SmallVectorTemplateCommon<T> (SizeArg) + { + } + + // No need to do a destroy loop for POD's. + static void + destroy_range (T *, T *) + { + } + + /// Move the range [I, E) onto the uninitialized memory + /// starting with "Dest", constructing elements into it as needed. + template <typename It1, typename It2> + static void + uninitialized_move (It1 I, It1 E, It2 Dest) + { + // Just do a copy. + uninitialized_copy (I, E, Dest); + } + + /// Copy the range [I, E) onto the uninitialized memory + /// starting with "Dest", constructing elements into it as needed. + template <typename It1, typename It2> + static void + uninitialized_copy (It1 I, It1 E, It2 Dest) + { + if constexpr (std::is_pointer_v<It1> && std::is_pointer_v<It2> && + std::is_same_v< + std::remove_const_t<std::remove_pointer_t<It1>>, + std::remove_pointer_t<It2>>) + { + // Use memcpy for PODs iterated by pointers (which includes SmallVector + // iterators): std::uninitialized_copy optimizes to memmove, but we can + // use memcpy here. Note that I and E are iterators and thus might be + // invalid for memcpy if they are equal. + if (I != E) + { + std::memcpy (reinterpret_cast<void *> (Dest), I, (E - I) * sizeof (T)); + } + } + else + { + // Arbitrary iterator types; just use the basic implementation. + std::uninitialized_copy (I, E, Dest); + } + } + + /// Double the size of the allocated memory, guaranteeing space for at + /// least one more element or MinSize if specified. + void + grow (size_t MinSize = 0) + { + this->grow_pod (MinSize, sizeof (T)); + } + + /// Reserve enough space to add one element, and return the updated element + /// pointer in case it was a reference to the storage. + const T * + reserveForParamAndGetAddress (const T &Elt, size_t N = 1) + { + return this->reserveForParamAndGetAddressImpl (this, Elt, N); + } + + /// Reserve enough space to add one element, and return the updated element + /// pointer in case it was a reference to the storage. + T * + reserveForParamAndGetAddress (T &Elt, size_t N = 1) + { + return const_cast<T *> ( + this->reserveForParamAndGetAddressImpl (this, Elt, N)); + } + + /// Copy \p V or return a reference, depending on \a ValueParamT. + static ValueParamT + forward_value_param (ValueParamT V) + { + return V; + } + + void + growAndAssign (size_t NumElts, T Elt) + { + // Elt has been copied in case it's an internal reference, side-stepping + // reference invalidation problems without losing the realloc optimization. + this->set_size (0); + this->grow (NumElts); + std::uninitialized_fill_n (this->begin (), NumElts, Elt); + this->set_size (NumElts); + } + + template <typename... ArgTypes> + T & + growAndEmplaceBack (ArgTypes &&...Args) + { + // Use push_back with a copy in case Args has an internal reference, + // side-stepping reference invalidation problems without losing the realloc + // optimization. + push_back (T (std::forward<ArgTypes> (Args)...)); + return this->back (); + } + + // Out-of-line slow path so the inline push_back needs no callee-saved + // registers or stack frame on its hot path. + LIBBASE_ATTRIBUTE_NOINLINE void + growAndPushBack (ValueParamT Elt) + { + // Copy in case Elt is an internal reference invalidated by grow. + T Tmp = Elt; + this->grow (this->size () + 1); + std::memcpy (reinterpret_cast<void *> (this->end ()), &Tmp, sizeof (T)); + this->set_size (this->size () + 1); + } + +public: + void + push_back (ValueParamT Elt) + { + if (LIBBASE_UNLIKELY (this->size () >= this->capacity ())) + { + return growAndPushBack (Elt); + } + std::memcpy (reinterpret_cast<void *> (this->end ()), &Elt, sizeof (T)); + this->set_size (this->size () + 1); + } + + void + pop_back () + { + this->set_size (this->size () - 1); + } +}; + +/// This class consists of common code factored out of the SmallVector class to +/// reduce code duplication based on the SmallVector 'N' template parameter. +template <typename T> class SmallVectorImpl : public SmallVectorTemplateBase<T> +{ + using SuperClass = SmallVectorTemplateBase<T>; + +public: + using iterator = typename SuperClass::iterator; + using const_iterator = typename SuperClass::const_iterator; + using reference = typename SuperClass::reference; + using size_type = typename SuperClass::size_type; + +protected: + using SmallVectorTemplateBase<T>::TakesParamByValue; + using ValueParamT = typename SuperClass::ValueParamT; + + // Default ctor - Initialize to empty. + explicit SmallVectorImpl (unsigned N) : SmallVectorTemplateBase<T> (N) + { + } + + void + assignRemote (SmallVectorImpl &&RHS) + { + this->destroy_range (this->begin (), this->end ()); + if (!this->isSmall ()) + { + free (this->begin ()); + } + this->BeginX = RHS.BeginX; + this->Size = RHS.Size; + this->Capacity = RHS.Capacity; + RHS.resetToSmall (); + } + + void + moveConstructFrom (SmallVectorImpl &&RHS) + { + assert (this->empty () && "move construction requires an empty vector"); + if (!RHS.isSmall ()) + { + assignRemote (std::move (RHS)); + return; + } + + // Construct inline elements directly instead of requiring T to be move + // assignable through the general move-assignment implementation. + size_type RHSSize = RHS.size (); + reserve (RHSSize); + this->uninitialized_move (RHS.begin (), RHS.end (), this->begin ()); + this->set_size (RHSSize); + RHS.clear (); + } + + ~SmallVectorImpl () + { + // Subclass has already destructed this vector's elements. + // If this wasn't grown from the inline copy, deallocate the old space. + if (!this->isSmall ()) + { + free (this->begin ()); + } + } + +public: + SmallVectorImpl (const SmallVectorImpl &) = delete; + + void + clear () + { + this->destroy_range (this->begin (), this->end ()); + this->Size = 0; + } + +private: + // Make set_size() private to avoid misuse in subclasses. + using SuperClass::set_size; + + template <bool ForOverwrite> + void + resizeImpl (size_type N) + { + if (N == this->size ()) + { + return; + } + + if (N < this->size ()) + { + this->truncate (N); + return; + } + + this->reserve (N); + for (auto I = this->end (), E = this->begin () + N; I != E; ++I) + { + if (ForOverwrite) + { + new (&*I) T; + } + else + { + new (&*I) T (); + } + } + this->set_size (N); + } + +public: + void + resize (size_type N) + { + resizeImpl<false> (N); + } + + /// Like resize, but \ref T is POD, the new values won't be initialized. + void + resize_for_overwrite (size_type N) + { + resizeImpl<true> (N); + } + + /// Like resize, but requires that \p N is less than \a size(). + void + truncate (size_type N) + { + assert (this->size () >= N && "Cannot increase size with truncate"); + this->destroy_range (this->begin () + N, this->end ()); + this->set_size (N); + } + + void + resize (size_type N, ValueParamT NV) + { + if (N == this->size ()) + { + return; + } + + if (N < this->size ()) + { + this->truncate (N); + return; + } + + // N > this->size(). Defer to append. + this->append (N - this->size (), NV); + } + + void + reserve (size_type N) + { + if (this->capacity () < N) + { + this->grow (N); + } + } + + void + pop_back_n (size_type NumItems) + { + assert (this->size () >= NumItems); + truncate (this->size () - NumItems); + } + + [[nodiscard]] T + pop_back_val () + { + T Result = ::std::move (this->back ()); + this->pop_back (); + return Result; + } + + void + swap (SmallVectorImpl &RHS); + + /// Add the specified range to the end of the SmallVector. + template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> + void + append (ItTy in_start, ItTy in_end) + { + if constexpr (HasIteratorTag<ItTy, std::forward_iterator_tag>::value) + { + this->assertSafeToAddRange (in_start, in_end); + size_type NumInputs = std::distance (in_start, in_end); + this->reserve (this->size () + NumInputs); + this->uninitialized_copy (in_start, in_end, this->end ()); + this->set_size (this->size () + NumInputs); + } + else + { + // Input iterator, we can't know ahead how many elements we'll add. + for (; in_start != in_end; ++in_start) + { + this->emplace_back (*in_start); + } + } + } + + /// Append \p NumInputs copies of \p Elt to the end. + void + append (size_type NumInputs, ValueParamT Elt) + { + const T *EltPtr = this->reserveForParamAndGetAddress (Elt, NumInputs); + std::uninitialized_fill_n (this->end (), NumInputs, *EltPtr); + this->set_size (this->size () + NumInputs); + } + + void + append (std::initializer_list<T> IL) + { + append (IL.begin (), IL.end ()); + } + + void + append (const SmallVectorImpl &RHS) + { + append (RHS.begin (), RHS.end ()); + } + + void + assign (size_type NumElts, ValueParamT Elt) + { + // Note that Elt could be an internal reference. + if (NumElts > this->capacity ()) + { + this->growAndAssign (NumElts, Elt); + return; + } + + // Assign over existing elements. + std::fill_n (this->begin (), std::min (NumElts, this->size ()), Elt); + if (NumElts > this->size ()) + { + std::uninitialized_fill_n (this->end (), NumElts - this->size (), Elt); + } + else if (NumElts < this->size ()) + { + this->destroy_range (this->begin () + NumElts, this->end ()); + } + this->set_size (NumElts); + } + + // FIXME: Consider assigning over existing elements, rather than clearing & + // re-initializing them - for all assign(...) variants. + + template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> + void + assign (ItTy in_start, ItTy in_end) + { + this->assertSafeToReferenceAfterClear (in_start, in_end); + clear (); + append (in_start, in_end); + } + + void + assign (std::initializer_list<T> IL) + { + clear (); + append (IL); + } + + void + assign (const SmallVectorImpl &RHS) + { + assign (RHS.begin (), RHS.end ()); + } + + template <typename U, + typename = std::enable_if_t<std::is_convertible_v<U, T>>> + void + assign (ArrayRef<U> AR) + { + assign (AR.begin (), AR.end ()); + } + + iterator + erase (const_iterator CI) + { + // Just cast away constness because this is a non-const member function. + iterator I = const_cast<iterator> (CI); + + assert (this->isReferenceToStorage (CI) && + "Iterator to erase is out of bounds."); + + iterator N = I; + // Shift all elts down one. + std::move (I + 1, this->end (), I); + // Drop the last elt. + this->pop_back (); + return (N); + } + + iterator + erase (const_iterator CS, const_iterator CE) + { + // Just cast away constness because this is a non-const member function. + iterator S = const_cast<iterator> (CS); + iterator E = const_cast<iterator> (CE); + + assert (this->isRangeInStorage (S, E) && + "Range to erase is out of bounds."); + + iterator N = S; + // Shift all elts down. + iterator I = std::move (E, this->end (), S); + // Drop the last elts. + this->destroy_range (I, this->end ()); + this->set_size (I - this->begin ()); + return (N); + } + +private: + template <class ArgType> + iterator + insert_one_impl (iterator I, ArgType &&Elt) + { + // Callers ensure that ArgType is derived from T. + static_assert ( + std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>, + T>::value, + "ArgType must be derived from T!"); + + if (I == this->end ()) + { // Important special case for empty vector. + this->push_back (::std::forward<ArgType> (Elt)); + return this->end () - 1; + } + + assert (this->isReferenceToStorage (I) && + "Insertion iterator is out of bounds."); + + // Grow if necessary. + size_t Index = I - this->begin (); + std::remove_reference_t<ArgType> *EltPtr = + this->reserveForParamAndGetAddress (Elt); + I = this->begin () + Index; + + ::new ((void *)this->end ()) T (::std::move (this->back ())); + // Push everything else over. + std::move_backward (I, this->end () - 1, this->end ()); + this->set_size (this->size () + 1); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + static_assert (!TakesParamByValue || std::is_same<ArgType, T>::value, + "ArgType must be 'T' when taking by value!"); + if (!TakesParamByValue && + this->isReferenceToRange (EltPtr, I, this->end ())) + { + ++EltPtr; + } + + *I = ::std::forward<ArgType> (*EltPtr); + return I; + } + +public: + iterator + insert (iterator I, T &&Elt) + { + return insert_one_impl (I, this->forward_value_param (std::move (Elt))); + } + + iterator + insert (iterator I, const T &Elt) + { + return insert_one_impl (I, this->forward_value_param (Elt)); + } + + iterator + insert (iterator I, size_type NumToInsert, ValueParamT Elt) + { + // Convert iterator to elt# to avoid invalidating iterator when we reserve() + size_t InsertElt = I - this->begin (); + + if (I == this->end ()) + { // Important special case for empty vector. + append (NumToInsert, Elt); + return this->begin () + InsertElt; + } + + assert (this->isReferenceToStorage (I) && + "Insertion iterator is out of bounds."); + + // Ensure there is enough space, and get the (maybe updated) address of + // Elt. + const T *EltPtr = this->reserveForParamAndGetAddress (Elt, NumToInsert); + + // Uninvalidate the iterator. + I = this->begin () + InsertElt; + + // If there are more elements between the insertion point and the end of the + // range than there are being inserted, we can use a simple approach to + // insertion. Since we already reserved space, we know that this won't + // reallocate the vector. + if (size_t (this->end () - I) >= NumToInsert) + { + T *OldEnd = this->end (); + append (std::move_iterator<iterator> (this->end () - NumToInsert), + std::move_iterator<iterator> (this->end ())); + + // Copy the existing elements that get replaced. + std::move_backward (I, OldEnd - NumToInsert, OldEnd); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end ()) + { + EltPtr += NumToInsert; + } + + std::fill_n (I, NumToInsert, *EltPtr); + return I; + } + + // Otherwise, we're inserting more elements than exist already, and we're + // not inserting at the end. + + // Move over the elements that we're about to overwrite. + T *OldEnd = this->end (); + this->set_size (this->size () + NumToInsert); + size_t NumOverwritten = OldEnd - I; + this->uninitialized_move (I, OldEnd, this->end () - NumOverwritten); + + // If we just moved the element we're inserting, be sure to update + // the reference (never happens if TakesParamByValue). + if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end ()) + { + EltPtr += NumToInsert; + } + + // Replace the overwritten part. + std::fill_n (I, NumOverwritten, *EltPtr); + + // Insert the non-overwritten middle part. + std::uninitialized_fill_n (OldEnd, NumToInsert - NumOverwritten, *EltPtr); + return I; + } + + template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> + iterator + insert (iterator I, ItTy From, ItTy To) + { + // Convert iterator to elt# to avoid invalidating iterator when we reserve() + size_t InsertElt = I - this->begin (); + + if (I == this->end ()) + { // Important special case for empty vector. + append (From, To); + return this->begin () + InsertElt; + } + + if constexpr (!HasIteratorTag<ItTy, std::forward_iterator_tag>::value) + { + // For input iterators, we don't know the number of elements to insert. + size_t OldSize = this->size (); + append (From, To); + I = this->begin () + InsertElt; // Uninvalidate the iterator. + std::rotate (I, this->begin () + OldSize, this->end ()); + return I; + } + + assert (this->isReferenceToStorage (I) && + "Insertion iterator is out of bounds."); + + // Check that the reserve that follows doesn't invalidate the iterators. + this->assertSafeToAddRange (From, To); + + size_t NumToInsert = std::distance (From, To); + + // Ensure there is enough space. + reserve (this->size () + NumToInsert); + + // Uninvalidate the iterator. + I = this->begin () + InsertElt; + + // If there are more elements between the insertion point and the end of the + // range than there are being inserted, we can use a simple approach to + // insertion. Since we already reserved space, we know that this won't + // reallocate the vector. + if (size_t (this->end () - I) >= NumToInsert) + { + T *OldEnd = this->end (); + append (std::move_iterator<iterator> (this->end () - NumToInsert), + std::move_iterator<iterator> (this->end ())); + + // Copy the existing elements that get replaced. + std::move_backward (I, OldEnd - NumToInsert, OldEnd); + + std::copy (From, To, I); + return I; + } + + // Otherwise, we're inserting more elements than exist already, and we're + // not inserting at the end. + + // Move over the elements that we're about to overwrite. + T *OldEnd = this->end (); + this->set_size (this->size () + NumToInsert); + size_t NumOverwritten = OldEnd - I; + this->uninitialized_move (I, OldEnd, this->end () - NumOverwritten); + + // Replace the overwritten part. + for (T *J = I; NumOverwritten > 0; --NumOverwritten) + { + *J = *From; + ++J; + ++From; + } + + // Insert the non-overwritten middle part. + this->uninitialized_copy (From, To, OldEnd); + return I; + } + + void + insert (iterator I, std::initializer_list<T> IL) + { + insert (I, IL.begin (), IL.end ()); + } + + template <typename... ArgTypes> + reference + emplace_back (ArgTypes &&...Args) + { + if (LIBBASE_UNLIKELY (this->size () >= this->capacity ())) + { + return this->growAndEmplaceBack (std::forward<ArgTypes> (Args)...); + } + + ::new ((void *)this->end ()) T (std::forward<ArgTypes> (Args)...); + this->set_size (this->size () + 1); + return this->back (); + } + + SmallVectorImpl & + operator= (const SmallVectorImpl &RHS); + + SmallVectorImpl & + operator= (SmallVectorImpl &&RHS); + + bool + operator== (const SmallVectorImpl &RHS) const + { + if (this->size () != RHS.size ()) + { + return false; + } + return std::equal (this->begin (), this->end (), RHS.begin ()); + } + bool + operator!= (const SmallVectorImpl &RHS) const + { + return !(*this == RHS); + } + + bool + operator< (const SmallVectorImpl &RHS) const + { + return std::lexicographical_compare (this->begin (), this->end (), + RHS.begin (), RHS.end ()); + } + bool + operator> (const SmallVectorImpl &RHS) const + { + return RHS < *this; + } + bool + operator<= (const SmallVectorImpl &RHS) const + { + return !(*this > RHS); + } + bool + operator>= (const SmallVectorImpl &RHS) const + { + return !(*this < RHS); + } +}; + +template <typename T> +void +SmallVectorImpl<T>::swap (SmallVectorImpl<T> &RHS) +{ + if (this == &RHS) + { + return; + } + + // We can only avoid copying elements if neither vector is small. + if (!this->isSmall () && !RHS.isSmall ()) + { + std::swap (this->BeginX, RHS.BeginX); + std::swap (this->Size, RHS.Size); + std::swap (this->Capacity, RHS.Capacity); + return; + } + this->reserve (RHS.size ()); + RHS.reserve (this->size ()); + + // Swap the shared elements. + size_t NumShared = this->size (); + if (NumShared > RHS.size ()) + { + NumShared = RHS.size (); + } + for (size_type i = 0; i != NumShared; ++i) + { + std::swap ((*this)[i], RHS[i]); + } + + // Copy over the extra elts. + if (this->size () > RHS.size ()) + { + size_t EltDiff = this->size () - RHS.size (); + this->uninitialized_copy (this->begin () + NumShared, this->end (), + RHS.end ()); + RHS.set_size (RHS.size () + EltDiff); + this->destroy_range (this->begin () + NumShared, this->end ()); + this->set_size (NumShared); + } + else if (RHS.size () > this->size ()) + { + size_t EltDiff = RHS.size () - this->size (); + this->uninitialized_copy (RHS.begin () + NumShared, RHS.end (), + this->end ()); + this->set_size (this->size () + EltDiff); + this->destroy_range (RHS.begin () + NumShared, RHS.end ()); + RHS.set_size (NumShared); + } +} + +template <typename T> +SmallVectorImpl<T> & +SmallVectorImpl<T>::operator= (const SmallVectorImpl<T> &RHS) +{ + // Avoid self-assignment. + if (this == &RHS) + { + return *this; + } + + // If we already have sufficient space, assign the common elements, then + // destroy any excess. + size_t RHSSize = RHS.size (); + size_t CurSize = this->size (); + if (CurSize >= RHSSize) + { + // Assign common elements. + iterator NewEnd; + if (RHSSize) + { + NewEnd = std::copy (RHS.begin (), RHS.begin () + RHSSize, this->begin ()); + } + else + { + NewEnd = this->begin (); + } + + // Destroy excess elements. + this->destroy_range (NewEnd, this->end ()); + + // Trim. + this->set_size (RHSSize); + return *this; + } + + // If we have to grow to have enough elements, destroy the current elements. + // This allows us to avoid copying them during the grow. + // FIXME: don't do this if they're efficiently moveable. + if (this->capacity () < RHSSize) + { + // Destroy current elements. + this->clear (); + CurSize = 0; + this->grow (RHSSize); + } + else if (CurSize) + { + // Otherwise, use assignment for the already-constructed elements. + std::copy (RHS.begin (), RHS.begin () + CurSize, this->begin ()); + } + + // Copy construct the new elements in place. + this->uninitialized_copy (RHS.begin () + CurSize, RHS.end (), + this->begin () + CurSize); + + // Set end. + this->set_size (RHSSize); + return *this; +} + +template <typename T> +SmallVectorImpl<T> & +SmallVectorImpl<T>::operator= (SmallVectorImpl<T> &&RHS) +{ + // Avoid self-assignment. + if (this == &RHS) + { + return *this; + } + + // If the RHS isn't small, clear this vector and then steal its buffer. + if (!RHS.isSmall ()) + { + this->assignRemote (std::move (RHS)); + return *this; + } + + // If we already have sufficient space, assign the common elements, then + // destroy any excess. + size_t RHSSize = RHS.size (); + size_t CurSize = this->size (); + if (CurSize >= RHSSize) + { + // Assign common elements. + iterator NewEnd = this->begin (); + if (RHSSize) + { + NewEnd = std::move (RHS.begin (), RHS.end (), NewEnd); + } + + // Destroy excess elements and trim the bounds. + this->destroy_range (NewEnd, this->end ()); + this->set_size (RHSSize); + + // Clear the RHS. + RHS.clear (); + + return *this; + } + + // If we have to grow to have enough elements, destroy the current elements. + // This allows us to avoid copying them during the grow. + // FIXME: this may not actually make any sense if we can efficiently move + // elements. + if (this->capacity () < RHSSize) + { + // Destroy current elements. + this->clear (); + CurSize = 0; + this->grow (RHSSize); + } + else if (CurSize) + { + // Otherwise, use assignment for the already-constructed elements. + std::move (RHS.begin (), RHS.begin () + CurSize, this->begin ()); + } + + // Move-construct the new elements in place. + this->uninitialized_move (RHS.begin () + CurSize, RHS.end (), + this->begin () + CurSize); + + // Set end. + this->set_size (RHSSize); + + RHS.clear (); + return *this; +} + +/// Storage for the SmallVector elements. This is specialized for the N=0 case +/// to avoid allocating unnecessary storage. +template <typename T, unsigned N> struct SmallVectorStorage +{ + alignas (T) char InlineElts[N * sizeof (T)]; +}; + +/// We need the storage to be properly aligned even for small-size of 0 so that +/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is +/// well-defined. +template <typename T> struct alignas (T) SmallVectorStorage<T, 0> +{ +}; + +/// Forward declaration of SmallVector so that +/// calculateSmallVectorDefaultInlinedElements can reference +/// `sizeof(SmallVector<T, 0>)`. +template <typename T, unsigned N> class LIBBASE_GSL_OWNER SmallVector; + +/// Helper class for calculating the default number of inline elements for +/// `SmallVector<T>`. +/// +/// This should be migrated to a constexpr function when our minimum +/// compiler support is enough for multi-statement constexpr functions. +template <typename T> struct CalculateSmallVectorDefaultInlinedElements +{ + // Parameter controlling the default number of inlined elements + // for `SmallVector<T>`. + // + // The default number of inlined elements ensures that + // 1. There is at least one inlined element. + // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless + // it contradicts 1. + static constexpr size_t kPreferredSmallVectorSizeof = 64; + + // static_assert that sizeof(T) is not "too big". + // + // Because our policy guarantees at least one inlined element, it is possible + // for an arbitrarily large inlined element to allocate an arbitrarily large + // amount of inline storage. We generally consider it an antipattern for a + // SmallVector to allocate an excessive amount of inline storage, so we want + // to call attention to these cases and make sure that users are making an + // intentional decision if they request a lot of inline storage. + // + // We want this assertion to trigger in pathological cases, but otherwise + // not be too easy to hit. To accomplish that, the cutoff is actually somewhat + // larger than kPreferredSmallVectorSizeof (otherwise, + // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that + // pattern seems useful in practice). + // + // One wrinkle is that this assertion is in theory non-portable, since + // sizeof(T) is in general platform-dependent. However, we don't expect this + // to be much of an issue, because most LLVM development happens on 64-bit + // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for + // 32-bit hosts, dodging the issue. The reverse situation, where development + // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a + // 64-bit host, is expected to be very rare. + static_assert ( + sizeof (T) <= 256, + "You are trying to use a default number of inlined elements for " + "`SmallVector<T>` but `sizeof(T)` is really big! Please use an " + "explicit number of inlined elements with `SmallVector<T, N>` to make " + "sure you really want that much inline storage."); + + // Discount the size of the header itself when calculating the maximum inline + // bytes. + static constexpr size_t PreferredInlineBytes = + kPreferredSmallVectorSizeof - sizeof (SmallVector<T, 0>); + static constexpr size_t NumElementsThatFit = + PreferredInlineBytes / sizeof (T); + static constexpr size_t value = + NumElementsThatFit == 0 ? 1 : NumElementsThatFit; +}; + +/// This is a 'vector' (really, a variable-sized array), optimized +/// for the case when the array is small. It contains some number of elements +/// in-place, which allows it to avoid heap allocation when the actual number of +/// elements is below that threshold. This allows normal "small" cases to be +/// fast without losing generality for large inputs. +/// +/// \note +/// In the absence of a well-motivated choice for the number of inlined +/// elements \p N, it is recommended to use \c SmallVector<T> (that is, +/// omitting the \p N). This will choose a default number of inlined elements +/// reasonable for allocation on the stack (for example, trying to keep \c +/// sizeof(SmallVector<T>) around 64 bytes). +/// +/// \warning This does not attempt to be exception safe. +/// +/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h +template <typename T, + unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value> +class LIBBASE_GSL_OWNER SmallVector : public SmallVectorImpl<T>, + SmallVectorStorage<T, N> +{ +public: + SmallVector () : SmallVectorImpl<T> (N) + { + } + + ~SmallVector () + { + // Destroy the constructed elements in the vector. + this->destroy_range (this->begin (), this->end ()); + } + + explicit SmallVector (size_t SizeArg) : SmallVectorImpl<T> (N) + { + this->resize (SizeArg); + } + + SmallVector (size_t SizeArg, const T &Value) : SmallVectorImpl<T> (N) + { + this->assign (SizeArg, Value); + } + + template <typename ItTy, typename = EnableIfConvertibleToInputIterator<ItTy>> + SmallVector (ItTy S, ItTy E) : SmallVectorImpl<T> (N) + { + this->append (S, E); + } + + template <typename RangeTy> + explicit SmallVector (const iterator_range<RangeTy> &R) + : SmallVectorImpl<T> (N) + { + this->append (R.begin (), R.end ()); + } + + SmallVector (std::initializer_list<T> IL) : SmallVectorImpl<T> (N) + { + this->append (IL); + } + + template <typename U, + typename = std::enable_if_t<std::is_convertible_v<U, T>>> + explicit SmallVector (ArrayRef<U> A) : SmallVectorImpl<T> (N) + { + this->append (A.begin (), A.end ()); + } + + SmallVector (const SmallVector &RHS) : SmallVectorImpl<T> (N) + { + if (!RHS.empty ()) + { + SmallVectorImpl<T>::operator= (RHS); + } + } + + SmallVector & + operator= (const SmallVector &RHS) + { + SmallVectorImpl<T>::operator= (RHS); + return *this; + } + + // Reuse the move-assignment instantiation for trivially move-assignable + // elements. Calling moveConstructFrom unconditionally would emit an + // additional per-T wrapper at -O0, increasing object size. + // std::is_move_assignable_v<T> is too broad: it can be a false positive for + // types with an unconstrained assignment operator whose body is ill-formed. + SmallVector (SmallVector &&RHS) : SmallVectorImpl<T> (N) + { + if (!RHS.empty ()) + { + bool StoleAllocation = N > 0 && !RHS.isSmall (); + if constexpr (std::is_trivially_move_assignable_v<T>) + { + SmallVectorImpl<T>::operator= (::std::move (RHS)); + } + else + { + this->moveConstructFrom (::std::move (RHS)); + } + if constexpr (N > 0) + { + if (StoleAllocation) + { + RHS.set_allocation_range (RHS.begin (), N); + } + } + } + } + + SmallVector (SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T> (N) + { + if (!RHS.empty ()) + { + if constexpr (std::is_trivially_move_assignable_v<T>) + { + SmallVectorImpl<T>::operator= (::std::move (RHS)); + } + else + { + this->moveConstructFrom (::std::move (RHS)); + } + } + } + + SmallVector & + operator= (SmallVector &&RHS) + { + if (N) + { + bool StoleAllocation = this != &RHS && !RHS.isSmall (); + SmallVectorImpl<T>::operator= (::std::move (RHS)); + // Restore the inline capacity after stealing RHS's allocation. + if (StoleAllocation) + { + RHS.set_allocation_range (RHS.begin (), N); + } + return *this; + } + // SmallVectorImpl<T>::operator= does not leverage N==0. Optimize the + // case. + if (this == &RHS) + { + return *this; + } + if (RHS.empty ()) + { + this->destroy_range (this->begin (), this->end ()); + this->Size = 0; + } + else + { + this->assignRemote (std::move (RHS)); + } + return *this; + } + + SmallVector & + operator= (SmallVectorImpl<T> &&RHS) + { + SmallVectorImpl<T>::operator= (::std::move (RHS)); + return *this; + } + + SmallVector & + operator= (std::initializer_list<T> IL) + { + this->assign (IL); + return *this; + } +}; + +template <typename T, unsigned N> +inline size_t +capacity_in_bytes (const SmallVector<T, N> &X) +{ + return X.capacity_in_bytes (); +} + +template <typename RangeType> +using ValueTypeFromRangeType = std::ranges::range_value_t<RangeType>; + +/// Given a range of type R, iterate the entire range and return a +/// SmallVector with elements of the vector. This is useful, for example, +/// when you want to iterate a range and then sort the results. +template <unsigned Size, typename R> +SmallVector<ValueTypeFromRangeType<R>, Size> +to_vector (R &&Range) +{ + return SmallVector<ValueTypeFromRangeType<R>, Size> ( + std::ranges::begin (Range), std::ranges::end (Range)); +} +template <typename R> +SmallVector<ValueTypeFromRangeType<R>> +to_vector (R &&Range) +{ + return SmallVector<ValueTypeFromRangeType<R>> (std::ranges::begin (Range), + std::ranges::end (Range)); +} + +template <typename Out, unsigned Size, typename R> +SmallVector<Out, Size> +to_vector_of (R &&Range) +{ + return SmallVector<Out, Size> (std::ranges::begin (Range), + std::ranges::end (Range)); +} + +template <typename Out, typename R> +SmallVector<Out> +to_vector_of (R &&Range) +{ + return SmallVector<Out> (std::ranges::begin (Range), + std::ranges::end (Range)); +} + +// Explicit instantiations +extern template class libbase::SmallVectorBase<uint32_t>; +#if SIZE_MAX > UINT32_MAX +extern template class libbase::SmallVectorBase<uint64_t>; +#endif + +} // end namespace libbase + +namespace std +{ + +template <typename T, unsigned N> struct hash<libbase::SmallVector<T, N>> +{ + size_t + operator() (const libbase::SmallVector<T, N> &Value) const + { + size_t Seed = 0; + for (const T &Element : Value) + { + size_t ElementHash = std::hash<T>{}(Element); + Seed ^= ElementHash + static_cast<size_t> (0x9e3779b9U) + (Seed << 6) + + (Seed >> 2); + } + return Seed; + } +}; + +/// Implement std::swap in terms of SmallVector swap. +template <typename T> +inline void +swap (libbase::SmallVectorImpl<T> &LHS, libbase::SmallVectorImpl<T> &RHS) +{ + LHS.swap (RHS); +} + +/// Implement std::swap in terms of SmallVector swap. +template <typename T, unsigned N> +inline void +swap (libbase::SmallVector<T, N> &LHS, libbase::SmallVector<T, N> &RHS) +{ + LHS.swap (RHS); +} + +} // end namespace std + +#endif // LIBBASE_ADT_SMALLVECTOR_H diff --git a/libbase/include/core/adt/Twine.h b/libbase/include/core/adt/Twine.h new file mode 100644 index 0000000..66d8264 --- /dev/null +++ b/libbase/include/core/adt/Twine.h @@ -0,0 +1,679 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. + */ + +//===- core/adt/Twine.h - Fast Temporary String Concatenation -*- 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 LIBBASE_ADT_TWINE_H +#define LIBBASE_ADT_TWINE_H + +#include "core/adt/SmallVector.h" +#include "core/compiler/Compiler.h" +#include "core/error/ErrorHandling.h" +#include <cassert> +#include <cstddef> +#include <cstdint> +#include <string> +#include <string_view> + +namespace libbase +{ + +class formatv_object_base; +class raw_ostream; + +/// Twine - A lightweight data structure for efficiently representing the +/// concatenation of temporary values as strings. +/// +/// A Twine is a kind of rope, it represents a concatenated string using a +/// binary-tree, where the string is the preorder of the nodes. Since the +/// Twine can be efficiently rendered into a buffer when its result is used, +/// it avoids the cost of generating temporary values for intermediate string +/// results -- particularly in cases when the Twine result is never +/// required. By explicitly tracking the type of leaf nodes, we can also avoid +/// the creation of temporary strings for conversions operations (such as +/// appending an integer to a string). +/// +/// A Twine is not intended for use directly and should not be stored, its +/// implementation relies on the ability to store pointers to temporary stack +/// objects which may be deallocated at the end of a statement. Twines should +/// only be used as const references in arguments, when an API wishes +/// to accept possibly-concatenated strings. +/// +/// Twines support a special 'null' value, which always concatenates to form +/// itself, and renders as an empty string. This can be returned from APIs to +/// effectively nullify any concatenations performed on the result. +/// +/// \b Implementation +/// +/// Given the nature of a Twine, it is not possible for the Twine's +/// concatenation method to construct interior nodes; the result must be +/// represented inside the returned value. For this reason a Twine object +/// actually holds two values, the left- and right-hand sides of a +/// concatenation. We also have nullary Twine objects, which are effectively +/// sentinel values that represent empty strings. +/// +/// Thus, a Twine can effectively have zero, one, or two children. The \see +/// isNullary(), \see isUnary(), and \see isBinary() predicates exist for +/// testing the number of children. +/// +/// We maintain a number of invariants on Twine objects (FIXME: Why): +/// - Nullary twines are always represented with their Kind on the left-hand +/// side, and the Empty kind on the right-hand side. +/// - Unary twines are always represented with the value on the left-hand +/// side, and the Empty kind on the right-hand side. +/// - If a Twine has another Twine as a child, that child should always be +/// binary (otherwise it could have been folded into the parent). +/// +/// These invariants are check by \see isValid(). +/// +/// \b Efficiency Considerations +/// +/// The Twine is designed to yield efficient and small code for common +/// situations. For this reason, the concat() method is inlined so that +/// concatenations of leaf nodes can be optimized into stores directly into a +/// single stack allocated object. +/// +/// In practice, not all compilers can be trusted to optimize concat() fully, +/// so we provide two additional methods (and accompanying operator+ +/// overloads) to guarantee that particularly important cases (cstring plus +/// string view) codegen as desired. +class Twine +{ + /// NodeKind - Represent the type of an argument. + enum NodeKind : unsigned char + { + /// An empty string; the result of concatenating anything with it is also + /// empty. + NullKind, + + /// The empty string. + EmptyKind, + + /// A pointer to a Twine instance. + TwineKind, + + /// A pointer to a C string instance. + CStringKind, + + /// A pointer to an std::string instance. + StdStringKind, + + /// A pointer and length representation. Used for std::string_view and + /// SmallVector. It stores the pointer and length directly. + PtrAndLengthKind, + + /// A pointer to a formatv_object_base instance. + FormatvObjectKind, + + /// A char value, to render as a character. + CharKind, + + /// An unsigned int value, to render as an unsigned decimal integer. + DecUIKind, + + /// An int value, to render as a signed decimal integer. + DecIKind, + + /// An unsigned long value, to render as an unsigned decimal integer. + DecULKind, + + /// A long value, to render as a signed decimal integer. + DecLKind, + + /// An unsigned long long value, to render as an unsigned decimal integer. + DecULLKind, + + /// A long long value, to render as a signed decimal integer. + DecLLKind, + + /// A uint64_t value, to render as an unsigned hexadecimal integer. + UHexKind + }; + + union Child + { + const Twine *twine; + const char *cString; + const std::string *stdString; + struct + { + const char *ptr; + size_t length; + } ptrAndLength; + const formatv_object_base *formatvObject; + char character; + unsigned int decUI; + int decI; + unsigned long decUL; + long decL; + unsigned long long decULL; + long long decLL; + uint64_t uHex; + }; + + /// LHS - The prefix in the concatenation, which may be uninitialized for + /// Null or Empty kinds. + Child LHS; + + /// RHS - The suffix in the concatenation, which may be uninitialized for + /// Null or Empty kinds. + Child RHS; + + /// LHSKind - The NodeKind of the left hand side, \see getLHSKind(). + NodeKind LHSKind = EmptyKind; + + /// RHSKind - The NodeKind of the right hand side, \see getRHSKind(). + NodeKind RHSKind = EmptyKind; + + /// Construct a nullary twine; the kind must be NullKind or EmptyKind. + explicit Twine (NodeKind Kind) : LHSKind (Kind) + { + assert (isNullary () && "Invalid kind!"); + } + + /// Construct a binary twine. + explicit Twine (const Twine &LHS, const Twine &RHS) + : LHSKind (TwineKind), RHSKind (TwineKind) + { + this->LHS.twine = &LHS; + this->RHS.twine = &RHS; + assert (isValid () && "Invalid twine!"); + } + + /// Construct a twine from explicit values. + explicit Twine (Child LHS, NodeKind LHSKind, Child RHS, NodeKind RHSKind) + : LHS (LHS), RHS (RHS), LHSKind (LHSKind), RHSKind (RHSKind) + { + assert (isValid () && "Invalid twine!"); + } + + /// Check for the null twine. + bool + isNull () const + { + return getLHSKind () == NullKind; + } + + /// Check for the empty twine. + bool + isEmpty () const + { + return getLHSKind () == EmptyKind; + } + + /// Check if this is a nullary twine (null or empty). + bool + isNullary () const + { + return isNull () || isEmpty (); + } + + /// Check if this is a unary twine. + bool + isUnary () const + { + return getRHSKind () == EmptyKind && !isNullary (); + } + + /// Check if this is a binary twine. + bool + isBinary () const + { + return getLHSKind () != NullKind && getRHSKind () != EmptyKind; + } + + /// Check if this is a valid twine (satisfying the invariants on + /// order and number of arguments). + bool + isValid () const + { + // Nullary twines always have Empty on the RHS. + if (isNullary () && getRHSKind () != EmptyKind) + { + return false; + } + + // Null should never appear on the RHS. + if (getRHSKind () == NullKind) + { + return false; + } + + // The RHS cannot be non-empty if the LHS is empty. + if (getRHSKind () != EmptyKind && getLHSKind () == EmptyKind) + { + return false; + } + + // A twine child should always be binary. + if (getLHSKind () == TwineKind && !LHS.twine->isBinary ()) + { + return false; + } + if (getRHSKind () == TwineKind && !RHS.twine->isBinary ()) + { + return false; + } + + return true; + } + + /// Get the NodeKind of the left-hand side. + NodeKind + getLHSKind () const + { + return LHSKind; + } + + /// Get the NodeKind of the right-hand side. + NodeKind + getRHSKind () const + { + return RHSKind; + } + + /// Print one child from a twine. + void + printOneChild (raw_ostream &OS, Child Ptr, NodeKind Kind) const; + + /// Print the representation of one child from a twine. + void + printOneChildRepr (raw_ostream &OS, Child Ptr, NodeKind Kind) const; + +public: + /// @name Constructors + /// @{ + + /// Construct from an empty string. + /*implicit*/ Twine () + { + assert (isValid () && "Invalid twine!"); + } + + Twine (const Twine &) = default; + + /// Construct from a C string. + /// + /// We take care here to optimize "" into the empty twine -- this will be + /// optimized out for string constants. This allows Twine arguments have + /// default "" values, without introducing unnecessary string constants. + /*implicit*/ Twine (const char *Str) + { + if (Str[0] != '\0') + { + LHS.cString = Str; + LHSKind = CStringKind; + } + else + { + LHSKind = EmptyKind; + } + + assert (isValid () && "Invalid twine!"); + } + /// Delete the implicit conversion from nullptr as Twine(const char *) + /// cannot take nullptr. + /*implicit*/ Twine (std::nullptr_t) = delete; + + /// Construct from an std::string. + /*implicit*/ Twine (const std::string &Str) : LHSKind (StdStringKind) + { + LHS.stdString = &Str; + assert (isValid () && "Invalid twine!"); + } + + /// Construct from an std::string_view by converting it to a pointer and + /// length. This handles string_views on a pure API basis, and avoids + /// storing one (or a pointer to one) inside a Twine, which avoids problems + /// when mixing code compiled under various C++ standards. + /*implicit*/ Twine (std::string_view Str) : LHSKind (PtrAndLengthKind) + { + LHS.ptrAndLength.ptr = Str.data (); + LHS.ptrAndLength.length = Str.length (); + assert (isValid () && "Invalid twine!"); + } + + /// Construct from a SmallString. + /*implicit*/ Twine (const SmallVectorImpl<char> &Str) + : LHSKind (PtrAndLengthKind) + { + LHS.ptrAndLength.ptr = Str.data (); + LHS.ptrAndLength.length = Str.size (); + assert (isValid () && "Invalid twine!"); + } + + /// Construct from a formatv_object_base. + /*implicit*/ Twine (const formatv_object_base &Fmt) + : LHSKind (FormatvObjectKind) + { + LHS.formatvObject = &Fmt; + assert (isValid () && "Invalid twine!"); + } + + /// Construct from a char. + explicit Twine (char Val) : LHSKind (CharKind) + { + LHS.character = Val; + } + + /// Construct from a signed char. + explicit Twine (signed char Val) : LHSKind (CharKind) + { + LHS.character = static_cast<char> (Val); + } + + /// Construct from an unsigned char. + explicit Twine (unsigned char Val) : LHSKind (CharKind) + { + LHS.character = static_cast<char> (Val); + } + + /// Construct a twine to print \p Val as an unsigned decimal integer. + explicit Twine (unsigned Val) : LHSKind (DecUIKind) + { + LHS.decUI = Val; + } + + /// Construct a twine to print \p Val as a signed decimal integer. + explicit Twine (int Val) : LHSKind (DecIKind) + { + LHS.decI = Val; + } + + /// Construct a twine to print \p Val as an unsigned decimal integer. + explicit Twine (unsigned long Val) : LHSKind (DecULKind) + { + LHS.decUL = Val; + } + + /// Construct a twine to print \p Val as a signed decimal integer. + explicit Twine (long Val) : LHSKind (DecLKind) + { + LHS.decL = Val; + } + + /// Construct a twine to print \p Val as an unsigned decimal integer. + explicit Twine (unsigned long long Val) : LHSKind (DecULLKind) + { + LHS.decULL = Val; + } + + /// Construct a twine to print \p Val as a signed decimal integer. + explicit Twine (long long Val) : LHSKind (DecLLKind) + { + LHS.decLL = Val; + } + + // FIXME: Unfortunately, to make sure this is as efficient as possible we + // need extra binary constructors from particular types. We can't rely on + // the compiler to be smart enough to fold operator+()/concat() down to the + // right thing. Yet. + + /// Construct as the concatenation of a C string and a string view. + /*implicit*/ Twine (const char *LHS, std::string_view RHS) + : LHSKind (CStringKind), RHSKind (PtrAndLengthKind) + { + this->LHS.cString = LHS; + this->RHS.ptrAndLength.ptr = RHS.data (); + this->RHS.ptrAndLength.length = RHS.size (); + assert (isValid () && "Invalid twine!"); + } + + /// Construct as the concatenation of a string view and a C string. + /*implicit*/ Twine (std::string_view LHS, const char *RHS) + : LHSKind (PtrAndLengthKind), RHSKind (CStringKind) + { + this->LHS.ptrAndLength.ptr = LHS.data (); + this->LHS.ptrAndLength.length = LHS.size (); + this->RHS.cString = RHS; + assert (isValid () && "Invalid twine!"); + } + + /// Since the intended use of twines is as temporary objects, assignments + /// when concatenating might cause undefined behavior or stack corruptions + Twine & + operator= (const Twine &) = delete; + + /// Create a 'null' string, which is an empty string that always + /// concatenates to form another empty string. + static Twine + createNull () + { + return Twine (NullKind); + } + + /// @} + /// @name Numeric Conversions + /// @{ + + // Construct a twine to print \p Val as an unsigned hexadecimal integer. + static Twine + utohexstr (uint64_t Val) + { + Child LHS, RHS; + LHS.uHex = Val; + RHS.twine = nullptr; + return Twine (LHS, UHexKind, RHS, EmptyKind); + } + + /// @} + /// @name Predicate Operations + /// @{ + + /// Check if this twine is trivially empty; a false return value does not + /// necessarily mean the twine is empty. + bool + isTriviallyEmpty () const + { + return isNullary (); + } + + /// Return true if this twine can be dynamically accessed as a single + /// string view with getSingleStringView(). + bool + isSingleStringView () const + { + if (getRHSKind () != EmptyKind) + { + return false; + } + + switch (getLHSKind ()) + { + case EmptyKind: + case CStringKind: + case StdStringKind: + case PtrAndLengthKind: + return true; + default: + return false; + } + } + + /// @} + /// @name String Operations + /// @{ + + Twine + concat (const Twine &Suffix) const; + + /// @} + /// @name Output & Conversion. + /// @{ + + /// Return the twine contents as a std::string. + LIBBASE_ABI std::string + str () const; + + /// Append the concatenated string into the given SmallString or SmallVector. + LIBBASE_ABI void + toVector (SmallVectorImpl<char> &Out) const; + + /// This returns the twine as a single string view. This method is only valid + /// if isSingleStringView() is true. + std::string_view + getSingleStringView () const + { + assert (isSingleStringView () && + "This cannot be had as a single string view!"); + switch (getLHSKind ()) + { + default: + libbase_unreachable ("Out of sync with isSingleStringView"); + case EmptyKind: + return std::string_view (); + case CStringKind: + return std::string_view (LHS.cString); + case StdStringKind: + return std::string_view (*LHS.stdString); + case PtrAndLengthKind: + return std::string_view (LHS.ptrAndLength.ptr, LHS.ptrAndLength.length); + } + } + + /// This returns the twine as a single string view if it can be + /// represented as such. Otherwise the twine is written into the given + /// SmallVector and a string view to the SmallVector's data is returned. + std::string_view + toStringView (SmallVectorImpl<char> &Out) const + { + if (isSingleStringView ()) + { + return getSingleStringView (); + } + toVector (Out); + return std::string_view (Out.data (), Out.size ()); + } + + /// This returns the twine as a single null terminated string view if it + /// can be represented as such. Otherwise the twine is written into the + /// given SmallVector and a string view to the SmallVector's data is returned. + /// + /// The returned string view's size does not include the null terminator. + LIBBASE_ABI std::string_view + toNullTerminatedStringView (SmallVectorImpl<char> &Out) const; + + /// Write the concatenated string represented by this twine to the + /// stream \p OS. + LIBBASE_ABI void + print (raw_ostream &OS) const; + + /// Write the representation of this twine to the stream \p OS. + LIBBASE_ABI void + printRepr (raw_ostream &OS) const; + +#if !defined(NDEBUG) || defined(LIBBASE_ENABLE_DUMP) + /// Dump the concatenated string represented by this twine to stderr. + LIBBASE_DUMP_METHOD void + dump () const; + + /// Dump the representation of this twine to stderr. + LIBBASE_DUMP_METHOD void + dumpRepr () const; +#endif + + /// @} +}; + +/// @name Twine Inline Implementations +/// @{ + +inline Twine +Twine::concat (const Twine &Suffix) const +{ + // Concatenation with null is null. + if (isNull () || Suffix.isNull ()) + { + return Twine (NullKind); + } + + // Concatenation with empty yields the other side. + if (isEmpty ()) + { + return Suffix; + } + if (Suffix.isEmpty ()) + { + return *this; + } + + // Otherwise we need to create a new node, taking care to fold in unary + // twines. + Child NewLHS, NewRHS; + NewLHS.twine = this; + NewRHS.twine = &Suffix; + NodeKind NewLHSKind = TwineKind, NewRHSKind = TwineKind; + if (isUnary ()) + { + NewLHS = LHS; + NewLHSKind = getLHSKind (); + } + if (Suffix.isUnary ()) + { + NewRHS = Suffix.LHS; + NewRHSKind = Suffix.getLHSKind (); + } + + return Twine (NewLHS, NewLHSKind, NewRHS, NewRHSKind); +} + +inline Twine +operator+ (const Twine &LHS, const Twine &RHS) +{ + return LHS.concat (RHS); +} + +/// Additional overload to guarantee simplified codegen; this is equivalent to +/// concat(). + +inline Twine +operator+ (const char *LHS, std::string_view RHS) +{ + return Twine (LHS, RHS); +} + +/// Additional overload to guarantee simplified codegen; this is equivalent to +/// concat(). + +inline Twine +operator+ (std::string_view LHS, const char *RHS) +{ + return Twine (LHS, RHS); +} + +inline raw_ostream & +operator<< (raw_ostream &OS, const Twine &RHS) +{ + RHS.print (OS); + return OS; +} + +/// @} + +} // end namespace libbase + +#endif // LIBBASE_ADT_TWINE_H diff --git a/libbase/include/core/adt/ilist.h b/libbase/include/core/adt/ilist.h new file mode 100644 index 0000000..c3c769a --- /dev/null +++ b/libbase/include/core/adt/ilist.h @@ -0,0 +1,546 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//==-- core/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 LIBBASE_ADT_ILIST_H +#define LIBBASE_ADT_ILIST_H + +#include "core/adt/simple_ilist.h" +#include <cassert> +#include <cstddef> +#include <iterator> + +namespace libbase +{ + +/// 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> +{ +}; + +//===----------------------------------------------------------------------===// +// +/// 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 +{ + using base_list_type = IntrusiveListT; + +public: + using pointer = typename base_list_type::pointer; + using const_pointer = typename base_list_type::const_pointer; + using reference = typename base_list_type::reference; + using const_reference = typename base_list_type::const_reference; + using value_type = typename base_list_type::value_type; + using size_type = typename base_list_type::size_type; + using difference_type = typename base_list_type::difference_type; + using iterator = typename base_list_type::iterator; + using const_iterator = typename base_list_type::const_iterator; + using reverse_iterator = typename base_list_type::reverse_iterator; + using const_reverse_iterator = + typename base_list_type::const_reverse_iterator; + +private: + 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::back; + using base_list_type::begin; + using base_list_type::empty; + using base_list_type::end; + using base_list_type::front; + using base_list_type::rbegin; + using base_list_type::rend; + + 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 libbase + +namespace std +{ + +// Ensure that swap uses the fast list swap... +template <class Ty> +void +swap (libbase::iplist<Ty> &Left, libbase::iplist<Ty> &Right) +{ + Left.swap (Right); +} + +} // end namespace std + +#endif // LIBBASE_ADT_ILIST_H diff --git a/libbase/include/core/adt/ilist_base.h b/libbase/include/core/adt/ilist_base.h new file mode 100644 index 0000000..3aa8d11 --- /dev/null +++ b/libbase/include/core/adt/ilist_base.h @@ -0,0 +1,139 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/ilist_base.h - Intrusive List Base --------------*- 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 LIBBASE_ADT_ILIST_BASE_H +#define LIBBASE_ADT_ILIST_BASE_H + +#include "core/adt/ilist_node_base.h" +#include <cassert> + +namespace libbase +{ + +/// Implementations of list algorithms using ilist_node_base. +template <bool EnableSentinelTracking, class ParentTy> class ilist_base +{ +public: + using node_base_type = ilist_node_base<EnableSentinelTracking, ParentTy>; + + static void + insertBeforeImpl (node_base_type &Next, node_base_type &N) + { + node_base_type &Prev = *Next.getPrev (); + N.setNext (&Next); + N.setPrev (&Prev); + Prev.setNext (&N); + Next.setPrev (&N); + } + + static void + removeImpl (node_base_type &N) + { + node_base_type *Prev = N.getPrev (); + node_base_type *Next = N.getNext (); + Next->setPrev (Prev); + Prev->setNext (Next); + + // Not strictly necessary, but helps catch a class of bugs. + N.setPrev (nullptr); + N.setNext (nullptr); + } + + static void + removeRangeImpl (node_base_type &First, node_base_type &Last) + { + node_base_type *Prev = First.getPrev (); + node_base_type *Final = Last.getPrev (); + Last.setPrev (Prev); + Prev->setNext (&Last); + + // Not strictly necessary, but helps catch a class of bugs. + First.setPrev (nullptr); + Final->setNext (nullptr); + } + + static void + transferBeforeImpl (node_base_type &Next, node_base_type &First, + node_base_type &Last) + { + if (&Next == &Last || &First == &Last) + { + return; + } + + // Position cannot be contained in the range to be transferred. + assert (&Next != &First && + // Check for the most common mistake. + "Insertion point can't be one of the transferred nodes"); + + node_base_type &Final = *Last.getPrev (); + + // Detach from old list/position. + First.getPrev ()->setNext (&Last); + Last.setPrev (First.getPrev ()); + + // Splice [First, Final] into its new list/position. + node_base_type &Prev = *Next.getPrev (); + Final.setNext (&Next); + First.setPrev (&Prev); + Prev.setNext (&First); + Next.setPrev (&Final); + } + + template <class T> + static void + insertBefore (T &Next, T &N) + { + insertBeforeImpl (Next, N); + } + + template <class T> + static void + remove (T &N) + { + removeImpl (N); + } + template <class T> + static void + removeRange (T &First, T &Last) + { + removeRangeImpl (First, Last); + } + + template <class T> + static void + transferBefore (T &Next, T &First, T &Last) + { + transferBeforeImpl (Next, First, Last); + } +}; + +} // end namespace libbase + +#endif // LIBBASE_ADT_ILIST_BASE_H diff --git a/libbase/include/core/adt/ilist_iterator.h b/libbase/include/core/adt/ilist_iterator.h new file mode 100644 index 0000000..90985d8 --- /dev/null +++ b/libbase/include/core/adt/ilist_iterator.h @@ -0,0 +1,591 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/ilist_iterator.h - Intrusive List Iterator ------*- 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 LIBBASE_ADT_ILIST_ITERATOR_H +#define LIBBASE_ADT_ILIST_ITERATOR_H + +#include "core/adt/ilist_node.h" +#include <cassert> +#include <cstddef> +#include <iterator> +#include <type_traits> + +namespace libbase +{ + +namespace ilist_detail +{ + +/// Find const-correct node types. +template <class OptionsT, bool IsConst> struct IteratorTraits; +template <class OptionsT> struct IteratorTraits<OptionsT, false> +{ + using value_type = typename OptionsT::value_type; + using pointer = typename OptionsT::pointer; + using reference = typename OptionsT::reference; + using node_pointer = ilist_node_impl<OptionsT> *; + using node_reference = ilist_node_impl<OptionsT> &; +}; +template <class OptionsT> struct IteratorTraits<OptionsT, true> +{ + using value_type = const typename OptionsT::value_type; + using pointer = typename OptionsT::const_pointer; + using reference = typename OptionsT::const_reference; + using node_pointer = const ilist_node_impl<OptionsT> *; + using node_reference = const ilist_node_impl<OptionsT> &; +}; + +template <bool IsReverse> struct IteratorHelper; +template <> struct IteratorHelper<false> : ilist_detail::NodeAccess +{ + using Access = ilist_detail::NodeAccess; + + template <class T> + static void + increment (T *&I) + { + I = Access::getNext (*I); + } + template <class T> + static void + decrement (T *&I) + { + I = Access::getPrev (*I); + } +}; +template <> struct IteratorHelper<true> : ilist_detail::NodeAccess +{ + using Access = ilist_detail::NodeAccess; + + template <class T> + static void + increment (T *&I) + { + I = Access::getPrev (*I); + } + template <class T> + static void + decrement (T *&I) + { + I = Access::getNext (*I); + } +}; + +/// Mixin class used to add a \a getNodeParent() function to iterators iff the +/// list uses \a ilist_parent, calling through to the node's \a getParent(). For +/// more details see \a ilist_node. +template <class IteratorTy, class ParentTy, bool IsConst> +class iterator_parent_access; +template <class IteratorTy, class ParentTy> +class iterator_parent_access<IteratorTy, ParentTy, true> +{ +public: + inline const ParentTy * + getNodeParent () const + { + return static_cast<const IteratorTy *> (this)->NodePtr->getParent (); + } +}; +template <class IteratorTy, class ParentTy> +class iterator_parent_access<IteratorTy, ParentTy, false> +{ +public: + inline ParentTy * + getNodeParent () const + { + return static_cast<const IteratorTy *> (this)->NodePtr->getParent (); + } +}; +template <class IteratorTy> class iterator_parent_access<IteratorTy, void, true> +{ +}; +template <class IteratorTy> +class iterator_parent_access<IteratorTy, void, false> +{ +}; + +} // end namespace ilist_detail + +/// Iterator for intrusive lists based on ilist_node. +template <class OptionsT, bool IsReverse, bool IsConst> +class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT>, + public ilist_detail::iterator_parent_access< + ilist_iterator<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst> +{ + friend ilist_iterator<OptionsT, IsReverse, !IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; + friend ilist_detail::iterator_parent_access< + ilist_iterator<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst>; + + using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; + using Access = ilist_detail::SpecificNodeAccess<OptionsT>; + +public: + using value_type = typename Traits::value_type; + using pointer = typename Traits::pointer; + using reference = typename Traits::reference; + using difference_type = ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + +private: + using node_pointer = typename Traits::node_pointer; + using node_reference = typename Traits::node_reference; + + node_pointer NodePtr = nullptr; + +public: + /// Create from an ilist_node. + explicit ilist_iterator (node_reference N) : NodePtr (&N) + { + } + + explicit ilist_iterator (pointer NP) : NodePtr (Access::getNodePtr (NP)) + { + } + explicit ilist_iterator (reference NR) : NodePtr (Access::getNodePtr (&NR)) + { + } + ilist_iterator () = default; + + // This is templated so that we can allow constructing a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + ilist_iterator (const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, + std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) + : NodePtr (RHS.NodePtr) + { + } + + // This is templated so that we can allow assigning to a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &> + operator= (const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) + { + NodePtr = RHS.NodePtr; + return *this; + } + + /// Explicit conversion between forward/reverse iterators. + /// + /// Translate between forward and reverse iterators without changing range + /// boundaries. The resulting iterator will dereference (and have a handle) + /// to the previous node, which is somewhat unexpected; but converting the + /// two endpoints in a range will give the same range in reverse. + /// + /// This matches std::reverse_iterator conversions. + explicit ilist_iterator ( + const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) + : ilist_iterator (++RHS.getReverse ()) + { + } + + /// Get a reverse iterator to the same node. + /// + /// Gives a reverse iterator that will dereference (and have a handle) to the + /// same node. Converting the endpoint iterators in a range will give a + /// different range; for range operations, use the explicit conversions. + ilist_iterator<OptionsT, !IsReverse, IsConst> + getReverse () const + { + if (NodePtr) + { + return ilist_iterator<OptionsT, !IsReverse, IsConst> (*NodePtr); + } + return ilist_iterator<OptionsT, !IsReverse, IsConst> (); + } + + /// Const-cast. + ilist_iterator<OptionsT, IsReverse, false> + getNonConst () const + { + if (NodePtr) + { + return ilist_iterator<OptionsT, IsReverse, false> ( + const_cast<typename ilist_iterator<OptionsT, IsReverse, + false>::node_reference> ( + *NodePtr)); + } + return ilist_iterator<OptionsT, IsReverse, false> (); + } + + // Accessors... + reference + operator* () const + { + assert (!NodePtr->isKnownSentinel ()); + return *Access::getValuePtr (NodePtr); + } + pointer + operator->() const + { + return &operator* (); + } + + // Comparison operators + friend bool + operator== (const ilist_iterator &LHS, const ilist_iterator &RHS) + { + return LHS.NodePtr == RHS.NodePtr; + } + friend bool + operator!= (const ilist_iterator &LHS, const ilist_iterator &RHS) + { + return LHS.NodePtr != RHS.NodePtr; + } + + // Increment and decrement operators... + ilist_iterator & + operator-- () + { + NodePtr = IsReverse ? NodePtr->getNext () : NodePtr->getPrev (); + return *this; + } + ilist_iterator & + operator++ () + { + NodePtr = IsReverse ? NodePtr->getPrev () : NodePtr->getNext (); + return *this; + } + ilist_iterator + operator-- (int) + { + ilist_iterator tmp = *this; + --*this; + return tmp; + } + ilist_iterator + operator++ (int) + { + ilist_iterator tmp = *this; + ++*this; + return tmp; + } + + bool + isValid () const + { + return NodePtr; + } + + /// Get the underlying ilist_node. + node_pointer + getNodePtr () const + { + return static_cast<node_pointer> (NodePtr); + } + + /// Check for end. Only valid if ilist_sentinel_tracking<true>. + bool + isEnd () const + { + return NodePtr ? NodePtr->isSentinel () : false; + } +}; + +/// Iterator for intrusive lists based on ilist_node. Much like ilist_iterator, +/// but with the addition of two bits recording whether this position (when in +/// a range) is half or fully open. +template <class OptionsT, bool IsReverse, bool IsConst> +class ilist_iterator_w_bits + : ilist_detail::SpecificNodeAccess<OptionsT>, + public ilist_detail::iterator_parent_access< + ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst> +{ + friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>; + friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; + friend ilist_detail::iterator_parent_access< + ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst>; + + using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; + using Access = ilist_detail::SpecificNodeAccess<OptionsT>; + +public: + using value_type = typename Traits::value_type; + using pointer = typename Traits::pointer; + using reference = typename Traits::reference; + using difference_type = ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + +private: + using node_pointer = typename Traits::node_pointer; + using node_reference = typename Traits::node_reference; + + node_pointer NodePtr = nullptr; + + /// Is this position intended to contain any debug-info immediately before + /// the position? + mutable bool HeadInclusiveBit = false; + /// Is this position intended to contain any debug-info immediately after + /// the position? + mutable bool TailInclusiveBit = false; + +public: + /// Create from an ilist_node. + explicit ilist_iterator_w_bits (node_reference N) : NodePtr (&N) + { + } + + explicit ilist_iterator_w_bits (pointer NP) + : NodePtr (Access::getNodePtr (NP)) + { + } + explicit ilist_iterator_w_bits (reference NR) + : NodePtr (Access::getNodePtr (&NR)) + { + } + ilist_iterator_w_bits () = default; + + // This is templated so that we can allow constructing a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + ilist_iterator_w_bits ( + const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS, + std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) + : NodePtr (RHS.NodePtr) + { + HeadInclusiveBit = RHS.HeadInclusiveBit; + TailInclusiveBit = RHS.TailInclusiveBit; + } + + // This is templated so that we can allow assigning to a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &> + operator= (const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS) + { + NodePtr = RHS.NodePtr; + HeadInclusiveBit = RHS.HeadInclusiveBit; + TailInclusiveBit = RHS.TailInclusiveBit; + return *this; + } + + /// Explicit conversion between forward/reverse iterators. + /// + /// Translate between forward and reverse iterators without changing range + /// boundaries. The resulting iterator will dereference (and have a handle) + /// to the previous node, which is somewhat unexpected; but converting the + /// two endpoints in a range will give the same range in reverse. + /// + /// This matches std::reverse_iterator conversions. + explicit ilist_iterator_w_bits ( + const ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> &RHS) + : ilist_iterator_w_bits (++RHS.getReverse ()) + { + } + + /// Get a reverse iterator to the same node. + /// + /// Gives a reverse iterator that will dereference (and have a handle) to the + /// same node. Converting the endpoint iterators in a range will give a + /// different range; for range operations, use the explicit conversions. + ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> + getReverse () const + { + if (NodePtr) + { + return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> (*NodePtr); + } + return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> (); + } + + /// Const-cast. + ilist_iterator_w_bits<OptionsT, IsReverse, false> + getNonConst () const + { + if (NodePtr) + { + auto New = ilist_iterator_w_bits<OptionsT, IsReverse, false> ( + const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse, + false>::node_reference> ( + *NodePtr)); + New.HeadInclusiveBit = HeadInclusiveBit; + New.TailInclusiveBit = TailInclusiveBit; + return New; + } + return ilist_iterator_w_bits<OptionsT, IsReverse, false> (); + } + + // Accessors... + reference + operator* () const + { + assert (!NodePtr->isKnownSentinel ()); + return *Access::getValuePtr (NodePtr); + } + pointer + operator->() const + { + return &operator* (); + } + + // Comparison operators + friend bool + operator== (const ilist_iterator_w_bits &LHS, + const ilist_iterator_w_bits &RHS) + { + return LHS.NodePtr == RHS.NodePtr; + } + friend bool + operator!= (const ilist_iterator_w_bits &LHS, + const ilist_iterator_w_bits &RHS) + { + return LHS.NodePtr != RHS.NodePtr; + } + + // Increment and decrement operators... + ilist_iterator_w_bits & + operator-- () + { + NodePtr = IsReverse ? NodePtr->getNext () : NodePtr->getPrev (); + HeadInclusiveBit = false; + TailInclusiveBit = false; + return *this; + } + ilist_iterator_w_bits & + operator++ () + { + NodePtr = IsReverse ? NodePtr->getPrev () : NodePtr->getNext (); + HeadInclusiveBit = false; + TailInclusiveBit = false; + return *this; + } + ilist_iterator_w_bits + operator-- (int) + { + ilist_iterator_w_bits tmp = *this; + --*this; + return tmp; + } + ilist_iterator_w_bits + operator++ (int) + { + ilist_iterator_w_bits tmp = *this; + ++*this; + return tmp; + } + + bool + isValid () const + { + return NodePtr; + } + + /// Get the underlying ilist_node. + node_pointer + getNodePtr () const + { + return static_cast<node_pointer> (NodePtr); + } + + /// Check for end. Only valid if ilist_sentinel_tracking<true>. + bool + isEnd () const + { + return NodePtr ? NodePtr->isSentinel () : false; + } + + bool + getHeadBit () const + { + return HeadInclusiveBit; + } + bool + getTailBit () const + { + return TailInclusiveBit; + } + void + setHeadBit (bool SetBit) const + { + HeadInclusiveBit = SetBit; + } + void + setTailBit (bool SetBit) const + { + TailInclusiveBit = SetBit; + } +}; + +template <typename From> struct simplify_type; + +/// Allow ilist_iterators to convert into pointers to a node automatically when +/// used by the dyn_cast, cast, isa mechanisms... +/// +/// FIXME: remove this, since there is no implicit conversion to NodeTy. +template <class OptionsT, bool IsConst> +struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> +{ + using iterator = ilist_iterator<OptionsT, false, IsConst>; + using SimpleType = typename iterator::pointer; + + static SimpleType + getSimplifiedValue (const iterator &Node) + { + return &*Node; + } +}; +template <class OptionsT, bool IsConst> +struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> + : simplify_type<ilist_iterator<OptionsT, false, IsConst>> +{ +}; + +// ilist_iterator_w_bits should also be accessible via isa/dyn_cast. +template <class OptionsT, bool IsConst> +struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> +{ + using iterator = ilist_iterator_w_bits<OptionsT, false, IsConst>; + using SimpleType = typename iterator::pointer; + + static SimpleType + getSimplifiedValue (const iterator &Node) + { + return &*Node; + } +}; +template <class OptionsT, bool IsConst> +struct simplify_type<const ilist_iterator_w_bits<OptionsT, false, IsConst>> + : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> +{ +}; + +} // end namespace libbase + +#endif // LIBBASE_ADT_ILIST_ITERATOR_H diff --git a/libbase/include/core/adt/ilist_node.h b/libbase/include/core/adt/ilist_node.h new file mode 100644 index 0000000..9ca9ed3 --- /dev/null +++ b/libbase/include/core/adt/ilist_node.h @@ -0,0 +1,470 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/ilist_node.h - Intrusive Linked List Helper -----*- 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 the ilist_node class template, which is a convenient +/// base class for creating classes that can be used with ilists. +/// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_ILIST_NODE_H +#define LIBBASE_ADT_ILIST_NODE_H + +#include "core/adt/ilist_node_base.h" +#include "core/adt/ilist_node_options.h" + +#include <type_traits> + +namespace libbase +{ + +namespace ilist_detail +{ + +struct NodeAccess; + +/// Mixin base class that is used to add \a getParent() and +/// \a setParent(ParentTy*) methods to \a ilist_node_impl iff \a ilist_parent +/// has been set in the list options. +template <class NodeTy, class ParentTy> class node_parent_access +{ +public: + inline const ParentTy * + getParent () const + { + return static_cast<const NodeTy *> (this)->getNodeBaseParent (); + } + inline ParentTy * + getParent () + { + return static_cast<NodeTy *> (this)->getNodeBaseParent (); + } + void + setParent (ParentTy *Parent) + { + return static_cast<NodeTy *> (this)->setNodeBaseParent (Parent); + } +}; +template <class NodeTy> class node_parent_access<NodeTy, void> +{ +}; + +} // end namespace ilist_detail + +template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator; +template <class OptionsT, bool IsReverse, bool IsConst> +class ilist_iterator_w_bits; +template <class OptionsT> class ilist_sentinel; + +// Selector for which iterator type to pick given the iterator-bits node option. +template <class OptionsT, bool IsReverse, bool IsConst> +using ilist_select_iterator_type = + std::conditional_t<OptionsT::has_iterator_bits, + ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>, + ilist_iterator<OptionsT, IsReverse, IsConst>>; + +/// Implementation for an ilist node. +/// +/// Templated on an appropriate \a ilist_detail::node_options, usually computed +/// by \a ilist_detail::compute_node_options. +/// +/// This is a wrapper around \a ilist_node_base whose main purpose is to +/// provide type safety: you can't insert nodes of \a ilist_node_impl into the +/// wrong \a simple_ilist or \a iplist. +template <class OptionsT> +class ilist_node_impl + : OptionsT::node_base_type, + public ilist_detail::node_parent_access<ilist_node_impl<OptionsT>, + typename OptionsT::parent_ty> +{ + using value_type = typename OptionsT::value_type; + using node_base_type = typename OptionsT::node_base_type; + using list_base_type = typename OptionsT::list_base_type; + + friend typename OptionsT::list_base_type; + friend struct ilist_detail::NodeAccess; + friend class ilist_sentinel<OptionsT>; + + friend class ilist_detail::node_parent_access<ilist_node_impl<OptionsT>, + typename OptionsT::parent_ty>; + friend class ilist_iterator<OptionsT, false, false>; + friend class ilist_iterator<OptionsT, false, true>; + friend class ilist_iterator<OptionsT, true, false>; + friend class ilist_iterator<OptionsT, true, true>; + friend class ilist_iterator_w_bits<OptionsT, false, false>; + friend class ilist_iterator_w_bits<OptionsT, false, true>; + friend class ilist_iterator_w_bits<OptionsT, true, false>; + friend class ilist_iterator_w_bits<OptionsT, true, true>; + +protected: + using self_iterator = ilist_select_iterator_type<OptionsT, false, false>; + using const_self_iterator = ilist_select_iterator_type<OptionsT, false, true>; + using reverse_self_iterator = + ilist_select_iterator_type<OptionsT, true, false>; + using const_reverse_self_iterator = + ilist_select_iterator_type<OptionsT, true, true>; + + ilist_node_impl () = default; + +private: + ilist_node_impl * + getPrev () + { + return static_cast<ilist_node_impl *> (node_base_type::getPrev ()); + } + + ilist_node_impl * + getNext () + { + return static_cast<ilist_node_impl *> (node_base_type::getNext ()); + } + + const ilist_node_impl * + getPrev () const + { + return static_cast<ilist_node_impl *> (node_base_type::getPrev ()); + } + + const ilist_node_impl * + getNext () const + { + return static_cast<ilist_node_impl *> (node_base_type::getNext ()); + } + + void + setPrev (ilist_node_impl *N) + { + node_base_type::setPrev (N); + } + void + setNext (ilist_node_impl *N) + { + node_base_type::setNext (N); + } + +public: + self_iterator + getIterator () + { + return self_iterator (*this); + } + const_self_iterator + getIterator () const + { + return const_self_iterator (*this); + } + + reverse_self_iterator + getReverseIterator () + { + return reverse_self_iterator (*this); + } + + const_reverse_self_iterator + getReverseIterator () const + { + return const_reverse_self_iterator (*this); + } + + // Under-approximation, but always available for assertions. + using node_base_type::isKnownSentinel; + + /// Check whether this is the sentinel node. + /// + /// This requires sentinel tracking to be explicitly enabled. Use the + /// ilist_sentinel_tracking<true> option to get this API. + /// + /// Rather than using static_assert to enforce the API is not called when + /// configured with is_sentinel_tracking_explicit=false, the method is + /// conditionally provided using std::enable_if. This way, clients of + /// ilist_node_impl can be fully instantiated for DLLExport on Windows. + template <typename T = OptionsT> + std::enable_if_t<T::is_sentinel_tracking_explicit, bool> + isSentinel () const + { + return node_base_type::isSentinel (); + } +}; + +/// An intrusive list node. +/// +/// A base class to enable membership in intrusive lists, including \a +/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the +/// \a value_type for the list. +/// +/// An ilist node can be configured with compile-time options to change +/// behaviour and/or add API. +/// +/// By default, an \a ilist_node does not track whether it is the list sentinel +/// (an instance of \a ilist_sentinel). The function \a isKnownSentinel() always +/// returns \c false tracking is off. Sentinel tracking steals a bit from the +/// "prev" link, which adds a mask operation when decrementing an iterator, but +/// enables bug-finding assertions in \a ilist_iterator. +/// +/// To turn sentinel tracking on all the time, pass in the +/// ilist_sentinel_tracking<true> template parameter. This also enables the \a +/// isSentinel() function. The same option must be passed to the intrusive +/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the +/// time.) +/// +/// A type can inherit from ilist_node multiple times by passing in different +/// \a ilist_tag options. This allows a single instance to be inserted into +/// multiple lists simultaneously, where each list is given the same tag. +/// +/// \example +/// struct A {}; +/// struct B {}; +/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {}; +/// +/// void foo() { +/// simple_ilist<N, ilist_tag<A>> ListA; +/// simple_ilist<N, ilist_tag<B>> ListB; +/// N N1; +/// ListA.push_back(N1); +/// ListB.push_back(N1); +/// } +/// \endexample +/// +/// When the \a ilist_parent<ParentTy> option is passed to an ilist_node and the +/// owning ilist, each node contains a pointer to the ilist's owner. This adds +/// \a getParent() and \a setParent(ParentTy*) methods to the ilist_node, which +/// will be used for node access by the ilist if the node class publicly +/// inherits from \a ilist_node_with_parent. By default, setParent() is not +/// automatically called by the ilist; a SymbolTableList will call setParent() +/// on inserted nodes, but the sentinel must still be manually set after the +/// list is created (e.g. SymTabList.end()->setParent(Parent)). +/// +/// The primary benefit of using ilist_parent is that a parent +/// pointer will be stored in the sentinel, meaning that you can safely use \a +/// ilist_iterator::getNodeParent() to get the node parent from any valid (i.e. +/// non-null) iterator, even one that points to a sentinel value. +/// +/// See \a is_valid_option for steps on adding a new option. +template <class T, class... Options> +class ilist_node + : public ilist_node_impl< + typename ilist_detail::compute_node_options<T, Options...>::type> +{ + static_assert (ilist_detail::check_options<Options...>::value, + "Unrecognized node option!"); +}; + +namespace ilist_detail +{ + +/// An access class for ilist_node private API. +/// +/// This gives access to the private parts of ilist nodes. Nodes for an ilist +/// should friend this class if they inherit privately from ilist_node. +/// +/// Using this class outside of the ilist implementation is unsupported. +struct NodeAccess +{ +protected: + template <class OptionsT> + static ilist_node_impl<OptionsT> * + getNodePtr (typename OptionsT::pointer N) + { + return N; + } + + template <class OptionsT> + static const ilist_node_impl<OptionsT> * + getNodePtr (typename OptionsT::const_pointer N) + { + return N; + } + + template <class OptionsT> + static typename OptionsT::pointer + getValuePtr (ilist_node_impl<OptionsT> *N) + { + return static_cast<typename OptionsT::pointer> (N); + } + + template <class OptionsT> + static typename OptionsT::const_pointer + getValuePtr (const ilist_node_impl<OptionsT> *N) + { + return static_cast<typename OptionsT::const_pointer> (N); + } + + template <class OptionsT> + static ilist_node_impl<OptionsT> * + getPrev (ilist_node_impl<OptionsT> &N) + { + return N.getPrev (); + } + + template <class OptionsT> + static ilist_node_impl<OptionsT> * + getNext (ilist_node_impl<OptionsT> &N) + { + return N.getNext (); + } + + template <class OptionsT> + static const ilist_node_impl<OptionsT> * + getPrev (const ilist_node_impl<OptionsT> &N) + { + return N.getPrev (); + } + + template <class OptionsT> + static const ilist_node_impl<OptionsT> * + getNext (const ilist_node_impl<OptionsT> &N) + { + return N.getNext (); + } +}; + +template <class OptionsT> struct SpecificNodeAccess : NodeAccess +{ +protected: + using pointer = typename OptionsT::pointer; + using const_pointer = typename OptionsT::const_pointer; + using node_type = ilist_node_impl<OptionsT>; + + static node_type * + getNodePtr (pointer N) + { + return NodeAccess::getNodePtr<OptionsT> (N); + } + + static const node_type * + getNodePtr (const_pointer N) + { + return NodeAccess::getNodePtr<OptionsT> (N); + } + + static pointer + getValuePtr (node_type *N) + { + return NodeAccess::getValuePtr<OptionsT> (N); + } + + static const_pointer + getValuePtr (const node_type *N) + { + return NodeAccess::getValuePtr<OptionsT> (N); + } +}; + +} // end namespace ilist_detail + +template <class OptionsT> +class ilist_sentinel : public ilist_node_impl<OptionsT> +{ +public: + ilist_sentinel () + { + this->initializeSentinel (); + reset (); + } + + void + reset () + { + this->setPrev (this); + this->setNext (this); + } + + bool + empty () const + { + return this == this->getPrev (); + } +}; + +/// An ilist node that can access its parent list. +/// +/// Requires \c NodeTy to have \a getParent() to find the parent node, and the +/// \c ParentTy to have \a getSublistAccess() to get a reference to the list. +template <typename NodeTy, typename ParentTy, class... Options> +class ilist_node_with_parent : public ilist_node<NodeTy, Options...> +{ +protected: + ilist_node_with_parent () = default; + +private: + /// Forward to NodeTy::getParent(). + /// + /// Note: do not use the name "getParent()". We want a compile error + /// (instead of recursion) when the subclass fails to implement \a + /// getParent(). + const ParentTy * + getNodeParent () const + { + return static_cast<const NodeTy *> (this)->getParent (); + } + +public: + /// @name Adjacent Node Accessors + /// @{ + /// Get the previous node, or \c nullptr for the list head. + NodeTy * + getPrevNode () + { + // Should be separated to a reused function, but then we couldn't use auto + // (and would need the type of the list). + const auto &List = + getNodeParent ()->*(ParentTy::getSublistAccess ((NodeTy *)nullptr)); + return List.getPrevNode (*static_cast<NodeTy *> (this)); + } + + /// Get the previous node, or \c nullptr for the list head. + const NodeTy * + getPrevNode () const + { + return const_cast<ilist_node_with_parent *> (this)->getPrevNode (); + } + + /// Get the next node, or \c nullptr for the list tail. + NodeTy * + getNextNode () + { + // Should be separated to a reused function, but then we couldn't use auto + // (and would need the type of the list). + const auto &List = + getNodeParent ()->*(ParentTy::getSublistAccess ((NodeTy *)nullptr)); + return List.getNextNode (*static_cast<NodeTy *> (this)); + } + + /// Get the next node, or \c nullptr for the list tail. + const NodeTy * + getNextNode () const + { + return const_cast<ilist_node_with_parent *> (this)->getNextNode (); + } + /// @} +}; + +} // end namespace libbase + +#endif // LIBBASE_ADT_ILIST_NODE_H diff --git a/libbase/include/core/adt/ilist_node_base.h b/libbase/include/core/adt/ilist_node_base.h new file mode 100644 index 0000000..2395efe --- /dev/null +++ b/libbase/include/core/adt/ilist_node_base.h @@ -0,0 +1,167 @@ +//===- core/adt/ilist_node_base.h - Intrusive List Node Base -----*- 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 LIBBASE_ADT_ILIST_NODE_BASE_H +#define LIBBASE_ADT_ILIST_NODE_BASE_H + +#include "core/adt/PointerIntPair.h" + +namespace libbase +{ + +namespace ilist_detail +{ + +template <class NodeBase, bool EnableSentinelTracking> class node_base_prevnext; + +template <class NodeBase> class node_base_prevnext<NodeBase, false> +{ + NodeBase *Prev = nullptr; + NodeBase *Next = nullptr; + +public: + void + setPrev (NodeBase *Prev) + { + this->Prev = Prev; + } + void + setNext (NodeBase *Next) + { + this->Next = Next; + } + NodeBase * + getPrev () const + { + return Prev; + } + NodeBase * + getNext () const + { + return Next; + } + + bool + isKnownSentinel () const + { + return false; + } + void + initializeSentinel () + { + } +}; + +template <class NodeBase> class node_base_prevnext<NodeBase, true> +{ + PointerIntPair<NodeBase *, 1> PrevAndSentinel; + NodeBase *Next = nullptr; + +public: + void + setPrev (NodeBase *Prev) + { + PrevAndSentinel.setPointer (Prev); + } + void + setNext (NodeBase *Next) + { + this->Next = Next; + } + NodeBase * + getPrev () const + { + return PrevAndSentinel.getPointer (); + } + NodeBase * + getNext () const + { + return Next; + } + + bool + isSentinel () const + { + return PrevAndSentinel.getInt (); + } + bool + isKnownSentinel () const + { + return isSentinel (); + } + void + initializeSentinel () + { + PrevAndSentinel.setInt (true); + } +}; + +template <class ParentTy> class node_base_parent +{ + ParentTy *Parent = nullptr; + +public: + void + setNodeBaseParent (ParentTy *Parent) + { + this->Parent = Parent; + } + inline const ParentTy * + getNodeBaseParent () const + { + return Parent; + } + inline ParentTy * + getNodeBaseParent () + { + return Parent; + } +}; +template <> class node_base_parent<void> +{ +}; + +} // end namespace ilist_detail + +/// Base class for ilist nodes. +/// +/// Optionally tracks whether this node is the sentinel. +template <bool EnableSentinelTracking, class ParentTy> +class ilist_node_base : public ilist_detail::node_base_prevnext< + ilist_node_base<EnableSentinelTracking, ParentTy>, + EnableSentinelTracking>, + public ilist_detail::node_base_parent<ParentTy> +{ +}; + +// Specialization implemented in the core LLVM library. +template class LIBBASE_ABI ilist_node_base<true, void>; + +} // end namespace libbase + +#endif // LIBBASE_ADT_ILIST_NODE_BASE_H +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ diff --git a/libbase/include/core/adt/ilist_node_options.h b/libbase/include/core/adt/ilist_node_options.h new file mode 100644 index 0000000..d26a6b8 --- /dev/null +++ b/libbase/include/core/adt/ilist_node_options.h @@ -0,0 +1,244 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/ilist_node_options.h - ilist_node Options -------*- 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 LIBBASE_ADT_ILIST_NODE_OPTIONS_H +#define LIBBASE_ADT_ILIST_NODE_OPTIONS_H + +#include <type_traits> + +namespace libbase +{ + +template <bool EnableSentinelTracking, class ParentTy> class ilist_node_base; +template <bool EnableSentinelTracking, class ParentTy> class ilist_base; + +/// Option to choose whether to track sentinels. +/// +/// This option affects the ABI for the nodes. When not specified explicitly, +/// sentinel tracking is disabled by default. Specify explicitly to +/// enable \a ilist_node::isSentinel(). +template <bool EnableSentinelTracking> struct ilist_sentinel_tracking +{ +}; + +/// Option to specify a tag for the node type. +/// +/// This option allows a single value type to be inserted in multiple lists +/// simultaneously. See \a ilist_node for usage examples. +template <class Tag> struct ilist_tag +{ +}; + +/// Option to add extra bits to the ilist_iterator. +/// +/// Some use-cases (debug-info) need to know whether a position is intended +/// to be half-open or fully open, i.e. whether to include any immediately +/// adjacent debug-info in an operation. This option adds two bits to the +/// iterator class to store that information. +template <bool ExtraIteratorBits> struct ilist_iterator_bits +{ +}; + +/// Option to add a pointer to this list's owner in every node. +/// +/// This option causes the \a ilist_base_node for this list to contain a pointer +/// ParentTy *Parent, returned by \a ilist_base_node::getNodeBaseParent() and +/// set by \a ilist_base_node::setNodeBaseParent(ParentTy *Parent). The parent +/// value is not set automatically; the ilist owner should set itself as the +/// parent of the list sentinel, and the parent should be set on each node +/// inserted into the list. This value is also not used by +/// \a ilist_node_with_parent::getNodeParent(), but is used by \a +/// ilist_iterator::getNodeParent(), which allows the parent to be fetched from +/// any valid (non-null) iterator to this list, including the sentinel. +template <class ParentTy> struct ilist_parent +{ +}; + +namespace ilist_detail +{ + +/// Helper trait for recording whether an option is specified explicitly. +template <bool IsExplicit> struct explicitness +{ + static const bool is_explicit = IsExplicit; +}; +using is_explicit = explicitness<true>; +using is_implicit = explicitness<false>; + +/// Check whether an option is valid. +/// +/// The steps for adding and enabling a new ilist option include: +/// \li define the option, ilist_foo<Bar>, above; +/// \li add new parameters for Bar to \a ilist_detail::node_options; +/// \li add an extraction meta-function, ilist_detail::extract_foo; +/// \li call extract_foo from \a ilist_detail::compute_node_options and pass it +/// into \a ilist_detail::node_options; and +/// \li specialize \c is_valid_option<ilist_foo<Bar>> to inherit from \c +/// std::true_type to get static assertions passing in \a simple_ilist and \a +/// ilist_node. +template <class Option> struct is_valid_option : std::false_type +{ +}; + +/// Extract sentinel tracking option. +/// +/// Look through \p Options for the \a ilist_sentinel_tracking option, with the +/// default disabled. +template <class... Options> struct extract_sentinel_tracking; +template <bool EnableSentinelTracking, class... Options> +struct extract_sentinel_tracking< + ilist_sentinel_tracking<EnableSentinelTracking>, Options...> + : std::bool_constant<EnableSentinelTracking>, is_explicit +{ +}; +template <class Option1, class... Options> +struct extract_sentinel_tracking<Option1, Options...> + : extract_sentinel_tracking<Options...> +{ +}; +template <> struct extract_sentinel_tracking<> : std::false_type, is_implicit +{ +}; +template <bool EnableSentinelTracking> +struct is_valid_option<ilist_sentinel_tracking<EnableSentinelTracking>> + : std::true_type +{ +}; + +/// Extract custom tag option. +/// +/// Look through \p Options for the \a ilist_tag option, pulling out the +/// custom tag type, using void as a default. +template <class... Options> struct extract_tag; +template <class Tag, class... Options> +struct extract_tag<ilist_tag<Tag>, Options...> +{ + using type = Tag; +}; +template <class Option1, class... Options> +struct extract_tag<Option1, Options...> : extract_tag<Options...> +{ +}; +template <> struct extract_tag<> +{ + using type = void; +}; +template <class Tag> struct is_valid_option<ilist_tag<Tag>> : std::true_type +{ +}; + +/// Extract iterator bits option. +/// +/// Look through \p Options for the \a ilist_iterator_bits option. Defaults +/// to false. +template <class... Options> struct extract_iterator_bits; +template <bool IteratorBits, class... Options> +struct extract_iterator_bits<ilist_iterator_bits<IteratorBits>, Options...> + : std::bool_constant<IteratorBits> +{ +}; +template <class Option1, class... Options> +struct extract_iterator_bits<Option1, Options...> + : extract_iterator_bits<Options...> +{ +}; +template <> struct extract_iterator_bits<> : std::false_type, is_implicit +{ +}; +template <bool IteratorBits> +struct is_valid_option<ilist_iterator_bits<IteratorBits>> : std::true_type +{ +}; + +/// Extract node parent option. +/// +/// Look through \p Options for the \a ilist_parent option, pulling out the +/// custom parent type, using void as a default. +template <class... Options> struct extract_parent; +template <class ParentTy, class... Options> +struct extract_parent<ilist_parent<ParentTy>, Options...> +{ + using type = ParentTy; +}; +template <class Option1, class... Options> +struct extract_parent<Option1, Options...> : extract_parent<Options...> +{ +}; +template <> struct extract_parent<> +{ + using type = void; +}; +template <class ParentTy> +struct is_valid_option<ilist_parent<ParentTy>> : std::true_type +{ +}; + +/// Check whether options are valid. +/// +/// The conjunction of \a is_valid_option on each individual option. +template <class... Options> +struct check_options : std::conjunction<is_valid_option<Options>...> +{ +}; + +/// Traits for options for \a ilist_node. +/// +/// This is usually computed via \a compute_node_options. +template <class T, bool EnableSentinelTracking, bool IsSentinelTrackingExplicit, + class TagT, bool HasIteratorBits, class ParentTy> +struct node_options +{ + using value_type = T; + using pointer = T *; + using reference = T &; + using const_pointer = const T *; + using const_reference = const T &; + + static const bool enable_sentinel_tracking = EnableSentinelTracking; + static const bool is_sentinel_tracking_explicit = IsSentinelTrackingExplicit; + static const bool has_iterator_bits = HasIteratorBits; + using tag = TagT; + using parent_ty = ParentTy; + using node_base_type = ilist_node_base<enable_sentinel_tracking, parent_ty>; + using list_base_type = ilist_base<enable_sentinel_tracking, parent_ty>; +}; + +template <class T, class... Options> struct compute_node_options +{ + using type = node_options<T, extract_sentinel_tracking<Options...>::value, + extract_sentinel_tracking<Options...>::is_explicit, + typename extract_tag<Options...>::type, + extract_iterator_bits<Options...>::value, + typename extract_parent<Options...>::type>; +}; + +} // end namespace ilist_detail +} // end namespace libbase + +#endif // LIBBASE_ADT_ILIST_NODE_OPTIONS_H diff --git a/libbase/include/core/adt/simple_ilist.h b/libbase/include/core/adt/simple_ilist.h new file mode 100644 index 0000000..e87f15b --- /dev/null +++ b/libbase/include/core/adt/simple_ilist.h @@ -0,0 +1,482 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/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 LIBBASE_ADT_SIMPLE_ILIST_H +#define LIBBASE_ADT_SIMPLE_ILIST_H + +#include "core/adt/ilist_base.h" +#include "core/adt/ilist_iterator.h" +#include "core/adt/ilist_node.h" +#include "core/adt/ilist_node_options.h" +#include "core/compiler/Compiler.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <functional> +#include <iterator> +#include <utility> + +namespace libbase +{ + +/// 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 (regardless of the +/// default setting). +/// \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> +{ + static_assert (ilist_detail::check_options<Options...>::value, + "Unrecognized node option!"); + using OptionsT = + typename ilist_detail::compute_node_options<T, Options...>::type; + using list_base_type = typename OptionsT::list_base_type; + ilist_sentinel<OptionsT> Sentinel; + +public: + using value_type = typename OptionsT::value_type; + using pointer = typename OptionsT::pointer; + using reference = typename OptionsT::reference; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + using iterator = ilist_select_iterator_type<OptionsT, false, false>; + using const_iterator = ilist_select_iterator_type<OptionsT, false, true>; + using reverse_iterator = ilist_select_iterator_type<OptionsT, true, false>; + using const_reverse_iterator = + ilist_select_iterator_type<OptionsT, true, true>; + using size_type = size_t; + using difference_type = ptrdiff_t; + + simple_ilist () = default; + ~simple_ilist () = default; + + // No copy constructors. + simple_ilist (const simple_ilist &) = delete; + simple_ilist & + operator= (const simple_ilist &) = delete; + + // Move constructors. + simple_ilist (simple_ilist &&X) + { + splice (end (), X); + } + simple_ilist & + operator= (simple_ilist &&X) + { + clear (); + splice (end (), X); + return *this; + } + + iterator + begin () + { + return ++iterator (Sentinel); + } + const_iterator + begin () const + { + return ++const_iterator (Sentinel); + } + iterator + end () + { + return iterator (Sentinel); + } + const_iterator + end () const + { + return const_iterator (Sentinel); + } + reverse_iterator + rbegin () + { + return ++reverse_iterator (Sentinel); + } + const_reverse_iterator + rbegin () const + { + return ++const_reverse_iterator (Sentinel); + } + reverse_iterator + rend () + { + return reverse_iterator (Sentinel); + } + const_reverse_iterator + rend () const + { + return const_reverse_iterator (Sentinel); + } + + /// Check if the list is empty in constant time. + [[nodiscard]] bool + empty () const + { + return Sentinel.empty (); + } + + /// Calculate the size of the list in linear time. + [[nodiscard]] size_type + size () const + { + return std::distance (begin (), end ()); + } + + reference + front () + { + return *begin (); + } + const_reference + front () const + { + return *begin (); + } + reference + back () + { + return *rbegin (); + } + const_reference + back () const + { + return *rbegin (); + } + + /// Insert a node at the front; never copies. + void + push_front (reference Node) + { + insert (begin (), Node); + } + + /// Insert a node at the back; never copies. + void + push_back (reference Node) + { + insert (end (), Node); + } + + /// Remove the node at the front; never deletes. + void + pop_front () + { + erase (begin ()); + } + + /// Remove the node at the back; never deletes. + void + pop_back () + { + erase (--end ()); + } + + /// Swap with another list in place using std::swap. + void + swap (simple_ilist &X) + { + std::swap (*this, X); + } + + /// Insert a node by reference; never copies. + iterator + insert (iterator I, reference Node) + { + list_base_type::insertBefore (*I.getNodePtr (), *this->getNodePtr (&Node)); + return iterator (&Node); + } + + /// Insert a range of nodes; never copies. + template <class Iterator> + void + insert (iterator I, Iterator First, Iterator Last) + { + for (; First != Last; ++First) + { + insert (I, *First); + } + } + + /// Clone another list. + template <class Cloner, class Disposer> + void + cloneFrom (const simple_ilist &L2, Cloner clone, Disposer dispose) + { + clearAndDispose (dispose); + for (const_reference V : L2) + { + push_back (*clone (V)); + } + } + + /// Remove a node by reference; never deletes. + /// + /// \see \a erase() for removing by iterator. + /// \see \a removeAndDispose() if the node should be deleted. + void + remove (reference N) + { + list_base_type::remove (*this->getNodePtr (&N)); + } + + /// Remove a node by reference and dispose of it. + template <class Disposer> + void + removeAndDispose (reference N, Disposer dispose) + { + remove (N); + dispose (&N); + } + + /// Remove a node by iterator; never deletes. + /// + /// \see \a remove() for removing by reference. + /// \see \a eraseAndDispose() it the node should be deleted. + iterator + erase (iterator I) + { + assert (I != end () && "Cannot remove end of list!"); + remove (*I++); + return I; + } + + /// Remove a range of nodes; never deletes. + /// + /// \see \a eraseAndDispose() if the nodes should be deleted. + iterator + erase (iterator First, iterator Last) + { + list_base_type::removeRange (*First.getNodePtr (), *Last.getNodePtr ()); + return Last; + } + + /// Remove a node by iterator and dispose of it. + template <class Disposer> + iterator + eraseAndDispose (iterator I, Disposer dispose) + { + auto Next = std::next (I); + erase (I); + dispose (&*I); + return Next; + } + + /// Remove a range of nodes and dispose of them. + template <class Disposer> + iterator + eraseAndDispose (iterator First, iterator Last, Disposer dispose) + { + while (First != Last) + { + First = eraseAndDispose (First, dispose); + } + return Last; + } + + /// Clear the list; never deletes. + /// + /// \see \a clearAndDispose() if the nodes should be deleted. + void + clear () + { + Sentinel.reset (); + } + + /// Clear the list and dispose of the nodes. + template <class Disposer> + void + clearAndDispose (Disposer dispose) + { + eraseAndDispose (begin (), end (), dispose); + } + + /// Splice in another list. + void + splice (iterator I, simple_ilist &L2) + { + splice (I, L2, L2.begin (), L2.end ()); + } + + /// Splice in a node from another list. + void + splice (iterator I, simple_ilist &L2, iterator Node) + { + splice (I, L2, Node, std::next (Node)); + } + + /// Splice in a range of nodes from another list. + void + splice (iterator I, simple_ilist &, iterator First, iterator Last) + { + list_base_type::transferBefore (*I.getNodePtr (), *First.getNodePtr (), + *Last.getNodePtr ()); + } + + /// Merge in another list. + /// + /// \pre \c this and \p RHS are sorted. + ///@{ + void + merge (simple_ilist &RHS) + { + merge (RHS, std::less<T> ()); + } + template <class Compare> + void + merge (simple_ilist &RHS, Compare comp); + ///@} + + /// Sort the list. + ///@{ + void + sort () + { + sort (std::less<T> ()); + } + template <class Compare> + void + sort (Compare comp); + ///@} +}; + +template <class T, class... Options> +template <class Compare> +void +simple_ilist<T, Options...>::merge (simple_ilist &RHS, Compare comp) +{ + if (this == &RHS || RHS.empty ()) + { + return; + } + iterator LI = begin (), LE = end (); + iterator RI = RHS.begin (), RE = RHS.end (); + while (LI != LE) + { + if (comp (*RI, *LI)) + { + // Transfer a run of at least size 1 from RHS to LHS. + iterator RunStart = RI++; + RI = std::find_if (RI, RE, + [&] (reference RV) + { + return !comp (RV, *LI); + }); + splice (LI, RHS, RunStart, RI); + if (RI == RE) + { + return; + } + } + ++LI; + } + // Transfer the remaining RHS nodes once LHS is finished. + splice (LE, RHS, RI, RE); +} + +template <class T, class... Options> +template <class Compare> +void +simple_ilist<T, Options...>::sort (Compare comp) +{ + // Vacuously sorted. + if (empty () || std::next (begin ()) == end ()) + { + return; + } + + // Split the list in the middle. + iterator Center = begin (), End = begin (); + while (End != end () && ++End != end ()) + { + ++Center; + ++End; + } + simple_ilist RHS; + RHS.splice (RHS.end (), *this, Center, end ()); + + // Sort the sublists and merge back together. + sort (comp); + RHS.sort (comp); + merge (RHS, comp); +} + +} // end namespace libbase + +#endif // LIBBASE_ADT_SIMPLE_ILIST_H |