4 files changed, 473 insertions, 0 deletions
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
diff --git a/libbase/src/core/error/Errno.cc b/libbase/src/core/error/Errno.cc
new file mode 100644
index 0000000..c861e46
--- /dev/null
+++ b/libbase/src/core/error/Errno.cc
@@ -0,0 +1,79 @@
+/*
+ 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/>.
+*/
+
+// This implementation is based on llvm/lib/Support/Errno.cpp.
+
+#include "core/error/Errno.h"
+#include "core/config/config.h"
+
+#include <cstring>
+#include <errno.h>
+
+namespace libbase
+{
+namespace sys
+{
+
+std::string
+StrError ()
+{
+  return StrError (errno);
+}
+
+std::string
+StrError (int errnum)
+{
+  std::string str;
+  if (errnum == 0)
+  {
+    return str;
+  }
+
+#if defined(HAVE_STRERROR_R) || HAVE_DECL_STRERROR_S
+  const int maxErrStrLen = 2000;
+  char buffer[maxErrStrLen];
+  buffer[0] = '\0';
+#endif
+
+#ifdef HAVE_STRERROR_R
+  // strerror_r is thread-safe.
+#if defined(__GLIBC__) && defined(_GNU_SOURCE)
+  // glibc defines its own incompatible version of strerror_r which may not
+  // use the buffer supplied.
+  str = strerror_r (errnum, buffer, maxErrStrLen - 1);
+#else
+  strerror_r (errnum, buffer, maxErrStrLen - 1);
+  str = buffer;
+#endif
+#elif HAVE_DECL_STRERROR_S
+  // Windows Secure API.
+  strerror_s (buffer, maxErrStrLen - 1, errnum);
+  str = buffer;
+#else
+  // Copy the thread-unsafe result of strerror into the buffer as fast as
+  // possible to minimize the impact of collisions in multiple threads.
+  str = strerror (errnum);
+#endif
+  return str;
+}
+
+} // namespace sys
+} // namespace libbase
diff --git a/libbase/src/core/math/MathExtras.cc b/libbase/src/core/math/MathExtras.cc
new file mode 100644
index 0000000..e691a3c
--- /dev/null
+++ b/libbase/src/core/math/MathExtras.cc
@@ -0,0 +1,97 @@
+/*
+ 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/>.
+*/
+
+//===-- MathExtras.cpp - Implement the MathExtras header --------------===//
+//
+// 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 MathExtras.h header
+//
+//===----------------------------------------------------------------------===//
+
+#include "core/math/MathExtras.h"
+
+#ifdef _MSC_VER
+#include <limits>
+#else
+#include <cmath>
+#endif
+
+namespace libbase
+{
+
+#if defined(_MSC_VER)
+// Visual Studio defines the HUGE_VAL class of macros using purposeful
+// constant arithmetic overflow, which it then warns on when encountered.
+const float huge_valf = std::numeric_limits<float>::infinity ();
+#else
+const float huge_valf = HUGE_VALF;
+#endif
+
+/// Returns the number of digits in the given integer.
+int
+NumDigitsBase10 (uint64_t X)
+{
+  static constexpr struct ConstexprData
+  {
+    uint8_t AtLeast[65] = {};
+    uint64_t Boundaries[20] = {};
+    static constexpr int
+    NumDigitsConstexpr (uint64_t N)
+    {
+      int res = 1;
+      while (N >= 10)
+      {
+        res++;
+        N /= 10;
+      }
+      return res;
+    }
+    constexpr ConstexprData ()
+    {
+      uint64_t Val = ~0ull;
+      for (uint64_t i = 0; i <= 64; i++)
+      {
+        uint64_t Digits = NumDigitsConstexpr (Val) - 1;
+        AtLeast[i] = Digits;
+        Val >>= 1;
+      }
+      // Special case because X=0 should return 1 and not 0
+      Boundaries[0] = 0;
+      Val = 10;
+      for (uint64_t i = 1; i < 20; i++)
+      {
+        Boundaries[i] = Val;
+        Val *= 10;
+      }
+    }
+  } Data;
+
+  uint64_t Base2 = X ? std::countl_zero (X) : 64;
+  uint64_t Digits = Data.AtLeast[Base2];
+  return Digits + (X >= Data.Boundaries[Digits]);
+}
+
+} // namespace libbase
diff --git a/libbase/src/core/memory/MemAlloc.cpp b/libbase/src/core/memory/MemAlloc.cpp
new file mode 100644
index 0000000..38e3bfd
--- /dev/null
+++ b/libbase/src/core/memory/MemAlloc.cpp
@@ -0,0 +1,63 @@
+/*
+ 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/>.
+ */
+
+//===- MemAlloc.cpp - Memory allocation functions -------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "core/memory/MemAlloc.h"
+#include <new>
+
+// These are out of line to have __cpp_aligned_new not affect ABI.
+
+LIBBASE_ATTRIBUTE_RETURNS_NONNULL LIBBASE_ATTRIBUTE_RETURNS_NOALIAS void *
+libbase::allocate_buffer (size_t Size, size_t Alignment)
+{
+  void *Result = ::operator new (Size,
+#ifdef __cpp_aligned_new
+                                 std::align_val_t (Alignment),
+#endif
+                                 std::nothrow);
+  if (Result == nullptr)
+  {
+    report_bad_alloc_error ("Buffer allocation failed");
+  }
+  return Result;
+}
+
+void
+libbase::deallocate_buffer (void *Ptr, size_t Size, size_t Alignment)
+{
+  ::operator delete (Ptr
+#ifdef __cpp_sized_deallocation
+                     ,
+                     Size
+#endif
+#ifdef __cpp_aligned_new
+                     ,
+                     std::align_val_t (Alignment)
+#endif
+  );
+}