contrib/llvm/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, unsigned Alignment)
  20     : K(K), Alignment(Alignment) {
  21   // Account for leading bytes in table so that offsets returned from add are
  22   // correct.
  23   switch (K) {
  24   case RAW:
  25     Size = 0;
  26     break;
  27   case MachO:
  28   case ELF:
  29     Size = 1;
  30     break;
  31   case WinCOFF:
  32     Size = 4;
  33     break;
  34   }
  35 }
  36
  37 typedef std::pair<CachedHash<StringRef>, size_t> StringPair;
  38
  39 // Returns the character at Pos from end of a string.
  40 static int charTailAt(StringPair *P, size_t Pos) {
  41   StringRef S = P->first.Val;
  42   if (Pos >= S.size())
  43     return -1;
  44   return (unsigned char)S[S.size() - Pos - 1];
  45 }
  46
  47 // Three-way radix quicksort. This is much faster than std::sort with strcmp
  48 // because it does not compare characters that we already know the same.
  49 static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
  50 tailcall:
  51   if (End - Begin <= 1)
  52     return;
  53
  54   // Partition items. Items in [Begin, P) are greater than the pivot,
  55   // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
  56   int Pivot = charTailAt(*Begin, Pos);
  57   StringPair **P = Begin;
  58   StringPair **Q = End;
  59   for (StringPair **R = Begin + 1; R < Q;) {
  60     int C = charTailAt(*R, Pos);
  61     if (C > Pivot)
  62       std::swap(*P++, *R++);
  63     else if (C < Pivot)
  64       std::swap(*--Q, *R);
  65     else
  66       R++;
  67   }
  68
  69   multikey_qsort(Begin, P, Pos);
  70   multikey_qsort(Q, End, Pos);
  71   if (Pivot != -1) {
  72     // qsort(P, Q, Pos + 1), but with tail call optimization.
  73     Begin = P;
  74     End = Q;
  75     ++Pos;
  76     goto tailcall;
  77   }
  78 }
  79
  80 void StringTableBuilder::finalize() {
  81   finalizeStringTable(/*Optimize=*/true);
  82 }
  83
  84 void StringTableBuilder::finalizeInOrder() {
  85   finalizeStringTable(/*Optimize=*/false);
  86 }
  87
  88 void StringTableBuilder::finalizeStringTable(bool Optimize) {
  89   typedef std::pair<CachedHash<StringRef>, size_t> StringOffsetPair;
  90   std::vector<StringOffsetPair *> Strings;
  91   Strings.reserve(StringIndexMap.size());
  92   for (StringOffsetPair &P : StringIndexMap)
  93     Strings.push_back(&P);
  94
  95   if (!Strings.empty()) {
  96     // If we're optimizing, sort by name. If not, sort by previously assigned
  97     // offset.
  98     if (Optimize) {
  99       multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
 100     } else {
 101       std::sort(Strings.begin(), Strings.end(),
 102                 [](const StringOffsetPair *LHS, const StringOffsetPair *RHS) {
 103                   return LHS->second < RHS->second;
 104                 });
 105     }
 106   }
 107
 108   switch (K) {
 109   case RAW:
 110     break;
 111   case ELF:
 112   case MachO:
 113     // Start the table with a NUL byte.
 114     StringTable += '\x00';
 115     break;
 116   case WinCOFF:
 117     // Make room to write the table size later.
 118     StringTable.append(4, '\x00');
 119     break;
 120   }
 121
 122   StringRef Previous;
 123   for (StringOffsetPair *P : Strings) {
 124     StringRef S = P->first.Val;
 125     if (K == WinCOFF)
 126       assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
 127
 128     if (Optimize && Previous.endswith(S)) {
 129       size_t Pos = StringTable.size() - S.size() - (K != RAW);
 130       if (!(Pos & (Alignment - 1))) {
 131         P->second = Pos;
 132         continue;
 133       }
 134     }
 135
 136     if (Optimize) {
 137       size_t Start = alignTo(StringTable.size(), Alignment);
 138       P->second = Start;
 139       StringTable.append(Start - StringTable.size(), '\0');
 140     } else {
 141       assert(P->second == StringTable.size() &&
 142              "different strtab offset after finalization");
 143     }
 144
 145     StringTable += S;
 146     if (K != RAW)
 147       StringTable += '\x00';
 148     Previous = S;
 149   }
 150
 151   switch (K) {
 152   case RAW:
 153   case ELF:
 154     break;
 155   case MachO:
 156     // Pad to multiple of 4.
 157     while (StringTable.size() % 4)
 158       StringTable += '\x00';
 159     break;
 160   case WinCOFF:
 161     // Write the table size in the first word.
 162     assert(StringTable.size() <= std::numeric_limits<uint32_t>::max());
 163     uint32_t Size = static_cast<uint32_t>(StringTable.size());
 164     support::endian::write<uint32_t, support::little, support::unaligned>(
 165         StringTable.data(), Size);
 166     break;
 167   }
 168
 169   Size = StringTable.size();
 170 }
 171
 172 void StringTableBuilder::clear() {
 173   StringTable.clear();
 174   StringIndexMap.clear();
 175 }
 176
 177 size_t StringTableBuilder::getOffset(StringRef S) const {
 178   assert(isFinalized());
 179   auto I = StringIndexMap.find(S);
 180   assert(I != StringIndexMap.end() && "String is not in table!");
 181   return I->second;
 182 }
 183
 184 size_t StringTableBuilder::add(StringRef S) {
 185   assert(!isFinalized());
 186   size_t Start = alignTo(Size, Alignment);
 187   auto P = StringIndexMap.insert(std::make_pair(S, Start));
 188   if (P.second)
 189     Size = Start + S.size() + (K != RAW);
 190   return P.first->second;
 191 }