diff options
| -rw-r--r-- | libbase/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | libbase/src/core/adt/SmallVector.cpp | 234 |
2 files changed, 235 insertions, 0 deletions
diff --git a/libbase/CMakeLists.txt b/libbase/CMakeLists.txt index 798c850..461c02f 100644 --- a/libbase/CMakeLists.txt +++ b/libbase/CMakeLists.txt @@ -39,6 +39,7 @@ configure_file( "${LIBBASE_BINARY_INCLUDE_DIR}/core/config/libbase-config.h") add_library(RCCCore + src/core/adt/SmallVector.cpp src/core/math/MathExtras.cc src/core/memory/MemAlloc.cpp src/core/error/Errno.cc diff --git a/libbase/src/core/adt/SmallVector.cpp b/libbase/src/core/adt/SmallVector.cpp new file mode 100644 index 0000000..c28680c --- /dev/null +++ b/libbase/src/core/adt/SmallVector.cpp @@ -0,0 +1,234 @@ +/* + 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/SmallVector.cpp - 'Normally small' vectors ----------------===// +// +// 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 implements the SmallVector class. +// +//===----------------------------------------------------------------------===// + +#include "core/adt/SmallVector.h" +#include "core/adt/Twine.h" +#include "core/memory/MemAlloc.h" +#include <cstdint> +#if LIBBASE_ENABLE_EXCEPTIONS +#include <stdexcept> +#endif +using namespace libbase; + +// Check that no bytes are wasted and everything is well-aligned. +namespace +{ +// These structures may cause binary compat warnings on AIX. Suppress the +// warning since we are only using these types for the static assertions below. +#if defined(_AIX) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Waix-compat" +#endif +struct Struct16B +{ + alignas (16) void *X; +}; +struct Struct32B +{ + alignas (32) void *X; +}; +#if defined(_AIX) +#pragma GCC diagnostic pop +#endif +} // namespace +static_assert (sizeof (SmallVector<void *, 0>) == + sizeof (unsigned) * 2 + sizeof (void *), + "wasted space in SmallVector size 0"); +static_assert (alignof (SmallVector<Struct16B, 0>) >= alignof (Struct16B), + "wrong alignment for 16-byte aligned T"); +static_assert (alignof (SmallVector<Struct32B, 0>) >= alignof (Struct32B), + "wrong alignment for 32-byte aligned T"); +static_assert (sizeof (SmallVector<Struct16B, 0>) >= alignof (Struct16B), + "missing padding for 16-byte aligned T"); +static_assert (sizeof (SmallVector<Struct32B, 0>) >= alignof (Struct32B), + "missing padding for 32-byte aligned T"); +static_assert (sizeof (SmallVector<void *, 1>) == + sizeof (unsigned) * 2 + sizeof (void *) * 2, + "wasted space in SmallVector size 1"); + +static_assert (sizeof (SmallVector<char, 0>) == + sizeof (void *) * 2 + sizeof (void *), + "1 byte elements have word-sized type for size and capacity"); + +/// Report that MinSize doesn't fit into this vector's size type. Throws +/// std::length_error or calls report_fatal_error. +[[noreturn]] static void +report_size_overflow (size_t MinSize, size_t MaxSize); +static void +report_size_overflow (size_t MinSize, size_t MaxSize) +{ + std::string Reason = "SmallVector unable to grow. Requested capacity (" + + std::to_string (MinSize) + + ") is larger than maximum value for size type (" + + std::to_string (MaxSize) + ")"; +#if LIBBASE_ENABLE_EXCEPTIONS + throw std::length_error (Reason); +#else + report_fatal_error (Twine (Reason)); +#endif +} + +/// Report that this vector is already at maximum capacity. Throws +/// std::length_error or calls report_fatal_error. +[[noreturn]] static void +report_at_maximum_capacity (size_t MaxSize); +static void +report_at_maximum_capacity (size_t MaxSize) +{ + std::string Reason = + "SmallVector capacity unable to grow. Already at maximum size " + + std::to_string (MaxSize); +#ifdef LIBBASE_ENABLE_EXCEPTIONS + throw std::length_error (Reason); +#else + report_fatal_error (Twine (Reason)); +#endif +} + +// Note: Moving this function into the header may cause performance regression. +template <class Size_T> +static size_t +getNewCapacity (size_t MinSize, size_t TSize, size_t OldCapacity) +{ + constexpr size_t MaxSize = std::numeric_limits<Size_T>::max (); + + // Ensure we can fit the new capacity. + // This is only going to be applicable when the capacity is 32 bit. + if (MinSize > MaxSize) + { + report_size_overflow (MinSize, MaxSize); + } + + // Ensure we can meet the guarantee of space for at least one more element. + // The above check alone will not catch the case where grow is called with a + // default MinSize of 0, but the current capacity cannot be increased. + // This is only going to be applicable when the capacity is 32 bit. + if (OldCapacity == MaxSize) + { + report_at_maximum_capacity (MaxSize); + } + + // In theory 2*capacity can overflow if the capacity is 64 bit, but the + // original capacity would never be large enough for this to be a problem. + size_t NewCapacity = 2 * OldCapacity + 1; // Always grow. + return std::clamp (NewCapacity, MinSize, MaxSize); +} + +/// If vector was first created with capacity 0, getFirstEl() points to the +/// memory right after, an area unallocated. If a subsequent allocation, +/// that grows the vector, happens to return the same pointer as getFirstEl(), +/// get a new allocation, otherwise isSmall() will falsely return that no +/// allocation was done (true) and the memory will not be freed in the +/// destructor. If a VSize is given (vector size), also copy that many +/// elements to the new allocation - used if realloca fails to increase +/// space, and happens to allocate precisely at BeginX. +/// This is unlikely to be called often, but resolves a memory leak when the +/// situation does occur. +static void * +replaceAllocation (void *NewElts, size_t TSize, size_t NewCapacity, + size_t VSize = 0) +{ + void *NewEltsReplace = libbase::safe_malloc (NewCapacity * TSize); + if (VSize) + { + memcpy (NewEltsReplace, NewElts, VSize * TSize); + } + free (NewElts); + return NewEltsReplace; +} + +// Note: Moving this function into the header may cause performance regression. +template <class Size_T> +void * +SmallVectorBase<Size_T>::mallocForGrow (void *FirstEl, size_t MinSize, + size_t TSize, size_t &NewCapacity) +{ + NewCapacity = getNewCapacity<Size_T> (MinSize, TSize, this->capacity ()); + // Even if capacity is not 0 now, if the vector was originally created with + // capacity 0, it's possible for the malloc to return FirstEl. + void *NewElts = libbase::safe_malloc (NewCapacity * TSize); + if (NewElts == FirstEl) + { + NewElts = replaceAllocation (NewElts, TSize, NewCapacity); + } + return NewElts; +} + +// Note: Moving this function into the header may cause performance regression. +template <class Size_T> +void +SmallVectorBase<Size_T>::grow_pod (void *FirstEl, size_t MinSize, size_t TSize) +{ + size_t NewCapacity = + getNewCapacity<Size_T> (MinSize, TSize, this->capacity ()); + void *NewElts; + if (BeginX == FirstEl) + { + NewElts = libbase::safe_malloc (NewCapacity * TSize); + if (NewElts == FirstEl) + { + NewElts = replaceAllocation (NewElts, TSize, NewCapacity); + } + + // Copy the elements over. No need to run dtors on PODs. + memcpy (NewElts, this->BeginX, size () * TSize); + } + else + { + // If this wasn't grown from the inline copy, grow the allocated space. + NewElts = libbase::safe_realloc (this->BeginX, NewCapacity * TSize); + if (NewElts == FirstEl) + { + NewElts = replaceAllocation (NewElts, TSize, NewCapacity, size ()); + } + } + + this->set_allocation_range (NewElts, NewCapacity); +} + +template class libbase::SmallVectorBase<uint32_t>; + +// Disable the uint64_t instantiation for 32-bit builds. +// Both uint32_t and uint64_t instantiations are needed for 64-bit builds. +// This instantiation will never be used in 32-bit builds, and will cause +// warnings when sizeof(Size_T) > sizeof(size_t). +#if SIZE_MAX > UINT32_MAX +template class libbase::SmallVectorBase<uint64_t>; + +// Assertions to ensure this #if stays in sync with SmallVectorSizeType. +static_assert (sizeof (SmallVectorSizeType<char>) == sizeof (uint64_t), + "Expected SmallVectorBase<uint64_t> variant to be in use."); +#else +static_assert (sizeof (SmallVectorSizeType<char>) == sizeof (uint32_t), + "Expected SmallVectorBase<uint32_t> variant to be in use."); +#endif |