• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
StringTableBuilder(Kind K,unsigned Alignment)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.
charTailAt(StringPair * P,size_t Pos)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.
multikey_qsort(StringPair ** Begin,StringPair ** End,int Pos)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 
finalize()80 void StringTableBuilder::finalize() {
81   finalizeStringTable(/*Optimize=*/true);
82 }
83 
finalizeInOrder()84 void StringTableBuilder::finalizeInOrder() {
85   finalizeStringTable(/*Optimize=*/false);
86 }
87 
finalizeStringTable(bool Optimize)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 
clear()172 void StringTableBuilder::clear() {
173   StringTable.clear();
174   StringIndexMap.clear();
175 }
176 
getOffset(StringRef S) const177 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 
add(StringRef S)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 }
192