Line data    Source code

       1             : //===- llvm/ADT/SmallVector.cpp - 'Normally small' vectors ----------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file implements the SmallVector class.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/ADT/SmallVector.h"
      15             : using namespace llvm;
      16             : 
      17             : // Check that no bytes are wasted and everything is well-aligned.
      18             : namespace {
      19             : struct Struct16B {
      20             :   alignas(16) void *X;
      21             : };
      22             : struct Struct32B {
      23             :   alignas(32) void *X;
      24             : };
      25             : }
      26             : static_assert(sizeof(SmallVector<void *, 0>) ==
      27             :                   sizeof(unsigned) * 2 + sizeof(void *),
      28             :               "wasted space in SmallVector size 0");
      29             : static_assert(alignof(SmallVector<Struct16B, 0>) >= alignof(Struct16B),
      30             :               "wrong alignment for 16-byte aligned T");
      31             : static_assert(alignof(SmallVector<Struct32B, 0>) >= alignof(Struct32B),
      32             :               "wrong alignment for 32-byte aligned T");
      33             : static_assert(sizeof(SmallVector<Struct16B, 0>) >= alignof(Struct16B),
      34             :               "missing padding for 16-byte aligned T");
      35             : static_assert(sizeof(SmallVector<Struct32B, 0>) >= alignof(Struct32B),
      36             :               "missing padding for 32-byte aligned T");
      37             : static_assert(sizeof(SmallVector<void *, 1>) ==
      38             :                   sizeof(unsigned) * 2 + sizeof(void *) * 2,
      39             :               "wasted space in SmallVector size 1");
      40             : 
      41             : /// grow_pod - This is an implementation of the grow() method which only works
      42             : /// on POD-like datatypes and is out of line to reduce code duplication.
      43   146939342 : void SmallVectorBase::grow_pod(void *FirstEl, size_t MinCapacity,
      44             :                                size_t TSize) {
      45             :   // Ensure we can fit the new capacity in 32 bits.
      46   146939342 :   if (MinCapacity > UINT32_MAX)
      47           0 :     report_bad_alloc_error("SmallVector capacity overflow during allocation");
      48             : 
      49   146939342 :   size_t NewCapacity = 2 * capacity() + 1; // Always grow.
      50   146939342 :   NewCapacity =
      51   146939342 :       std::min(std::max(NewCapacity, MinCapacity), size_t(UINT32_MAX));
      52             : 
      53             :   void *NewElts;
      54   146939342 :   if (BeginX == FirstEl) {
      55    97733223 :     NewElts = safe_malloc(NewCapacity * TSize);
      56             : 
      57             :     // Copy the elements over.  No need to run dtors on PODs.
      58   195466444 :     memcpy(NewElts, this->BeginX, size() * TSize);
      59             :   } else {
      60             :     // If this wasn't grown from the inline copy, grow the allocated space.
      61    49206119 :     NewElts = safe_realloc(this->BeginX, NewCapacity * TSize);
      62             :   }
      63             : 
      64   146939336 :   this->BeginX = NewElts;
      65   146939336 :   this->Capacity = NewCapacity;
      66   146939336 : }