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