//===- llvm/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 "llvm/ADT/SmallVector.h"

#include <cstdint>

using namespace llvm;

// Check that no bytes are wasted and everything is well-aligned.

namespace {

struct Struct16B {

  alignas(16) void *X;

};

struct Struct32B {

  alignas(32) void *X;

};

}

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");

// 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 MinCapacity,

                                       size_t TSize) {

  // Ensure we can fit the new capacity.

  // This is only going to be applicable when the capacity is 32 bit.

  if (MinCapacity > SizeTypeMax())

    report_bad_alloc_error("SmallVector capacity overflow during allocation");

  // 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 MinCapacity of 0, but the current capacity cannot be increased.

  // This is only going to be applicable when the capacity is 32 bit.

  if (capacity() == SizeTypeMax())

    report_bad_alloc_error("SmallVector capacity unable to grow");

  // 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 * capacity() + 1; // Always grow.

  NewCapacity = std::min(std::max(NewCapacity, MinCapacity), SizeTypeMax());

  void *NewElts;

  if (BeginX == FirstEl) {

    NewElts = safe_malloc(NewCapacity * TSize);

    // 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 = safe_realloc(this->BeginX, NewCapacity * TSize);

  }

  this->BeginX = NewElts;

  this->Capacity = NewCapacity;

}

_ZN4llvm15SmallVectorBaseIjE8grow_podEPvmm

Line

Count

Source

48

131

                                       size_t TSize) {

49

131

  // Ensure we can fit the new capacity.

50

131

  // This is only going to be applicable when the capacity is 32 bit.

51

131

  if (MinCapacity > SizeTypeMax())

52

0

    report_bad_alloc_error("SmallVector capacity overflow during allocation");

53

131

54

131

  // Ensure we can meet the guarantee of space for at least one more element.

55

131

  // The above check alone will not catch the case where grow is called with a

56

131

  // default MinCapacity of 0, but the current capacity cannot be increased.

57

131

  // This is only going to be applicable when the capacity is 32 bit.

58

131

  if (capacity() == SizeTypeMax())

59

0

    report_bad_alloc_error("SmallVector capacity unable to grow");

60

131

61

131

  // In theory 2*capacity can overflow if the capacity is 64 bit, but the

62

131

  // original capacity would never be large enough for this to be a problem.

63

131

  size_t NewCapacity = 2 * capacity() + 1; // Always grow.

64

131

  NewCapacity = std::min(std::max(NewCapacity, MinCapacity), SizeTypeMax());

65

131

66

131

  void *NewElts;

67

131

  if (BeginX == FirstEl) {

68

128

    NewElts = safe_malloc(NewCapacity * TSize);

69

128

70

128

    // Copy the elements over.  No need to run dtors on PODs.

71

128

    memcpy(NewElts, this->BeginX, size() * TSize);

72

128

  } else {

73

3

    // If this wasn't grown from the inline copy, grow the allocated space.

74

3

    NewElts = safe_realloc(this->BeginX, NewCapacity * TSize);

75

3

  }

76

131

77

131

  this->BeginX = NewElts;

78

131

  this->Capacity = NewCapacity;

79

131

}

Unexecuted instantiation: _ZN4llvm15SmallVectorBaseImE8grow_podEPvmm

template class llvm::SmallVectorBase<uint32_t>;

// Disable the uint64_t instantiation for 32-bit builds.

// Both uint32_t and uint64_t instantations 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 llvm::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