lib/MC/StringTableBuilder.cpp

   1 //===-- StringTableBuilder.cpp - String table building utility ------------===//
   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 #include "llvm/MC/StringTableBuilder.h"
  11 #include "llvm/ADT/STLExtras.h"
  12 #include "llvm/Support/COFF.h"
  13 #include "llvm/Support/Endian.h"
  14
  15 #include <vector>
  16
  17 using namespace llvm;
  18
  19 StringTableBuilder::StringTableBuilder(Kind K) : K(K) {}
  20
  21 static int compareBySuffix(std::pair<StringRef, size_t> *const *AP,
  22                            std::pair<StringRef, size_t> *const *BP) {
  23   StringRef A = (*AP)->first;
  24   StringRef B = (*BP)->first;
  25   size_t SizeA = A.size();
  26   size_t SizeB = B.size();
  27   size_t Len = std::min(SizeA, SizeB);
  28   for (size_t I = 0; I < Len; ++I) {
  29     char CA = A[SizeA - I - 1];
  30     char CB = B[SizeB - I - 1];
  31     if (CA != CB)
  32       return CB - CA;
  33   }
  34   return SizeB - SizeA;
  35 }
  36
  37 void StringTableBuilder::finalize() {
  38   std::vector<std::pair<StringRef, size_t> *> Strings;
  39   Strings.reserve(StringIndexMap.size());
  40   for (std::pair<StringRef, size_t> &P : StringIndexMap)
  41     Strings.push_back(&P);
  42
  43   array_pod_sort(Strings.begin(), Strings.end(), compareBySuffix);
  44
  45   switch (K) {
  46   case RAW:
  47     break;
  48   case ELF:
  49   case MachO:
  50     // Start the table with a NUL byte.
  51     StringTable += '\x00';
  52     break;
  53   case WinCOFF:
  54     // Make room to write the table size later.
  55     StringTable.append(4, '\x00');
  56     break;
  57   }
  58
  59   StringRef Previous;
  60   for (std::pair<StringRef, size_t> *P : Strings) {
  61     StringRef S = P->first;
  62     if (K == WinCOFF)
  63       assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
  64
  65     if (Previous.endswith(S)) {
  66       P->second = StringTable.size() - S.size() - (K != RAW);
  67       continue;
  68     }
  69
  70     P->second = StringTable.size();
  71     StringTable += S;
  72     if (K != RAW)
  73       StringTable += '\x00';
  74     Previous = S;
  75   }
  76
  77   switch (K) {
  78   case RAW:
  79   case ELF:
  80     break;
  81   case MachO:
  82     // Pad to multiple of 4.
  83     while (StringTable.size() % 4)
  84       StringTable += '\x00';
  85     break;
  86   case WinCOFF:
  87     // Write the table size in the first word.
  88     assert(StringTable.size() <= std::numeric_limits<uint32_t>::max());
  89     uint32_t Size = static_cast<uint32_t>(StringTable.size());
  90     support::endian::write<uint32_t, support::little, support::unaligned>(
  91         StringTable.data(), Size);
  92     break;
  93   }
  94
  95   Size = StringTable.size();
  96 }
  97
  98 void StringTableBuilder::clear() {
  99   StringTable.clear();
 100   StringIndexMap.clear();
 101 }
 102
 103 size_t StringTableBuilder::getOffset(StringRef S) const {
 104   assert(isFinalized());
 105   auto I = StringIndexMap.find(S);
 106   assert(I != StringIndexMap.end() && "String is not in table!");
 107   return I->second;
 108 }
 109
 110 size_t StringTableBuilder::add(StringRef S) {
 111   assert(!isFinalized());
 112   auto P = StringIndexMap.insert(std::make_pair(S, Size));
 113   if (P.second)
 114     Size += S.size() + (K != RAW);
 115   return P.first->second;
 116 }