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/CachedHashString.h"
12 #include "llvm/ADT/SmallString.h"
13 #include "llvm/ADT/StringRef.h"
14 #include "llvm/BinaryFormat/COFF.h"
15 #include "llvm/Support/Endian.h"
16 #include "llvm/Support/MathExtras.h"
17 #include "llvm/Support/raw_ostream.h"
18 #include <cassert>
19 #include <cstddef>
20 #include <cstdint>
21 #include <cstring>
22 #include <utility>
23 #include <vector>
24
25 using namespace llvm;
26
27 StringTableBuilder::~StringTableBuilder() = default;
28
initSize()29 void StringTableBuilder::initSize() {
30 // Account for leading bytes in table so that offsets returned from add are
31 // correct.
32 switch (K) {
33 case RAW:
34 case DWARF:
35 Size = 0;
36 break;
37 case MachO:
38 case ELF:
39 // Start the table with a NUL byte.
40 Size = 1;
41 break;
42 case WinCOFF:
43 // Make room to write the table size later.
44 Size = 4;
45 break;
46 }
47 }
48
StringTableBuilder(Kind K,unsigned Alignment)49 StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
50 : K(K), Alignment(Alignment) {
51 initSize();
52 }
53
write(raw_ostream & OS) const54 void StringTableBuilder::write(raw_ostream &OS) const {
55 assert(isFinalized());
56 SmallString<0> Data;
57 Data.resize(getSize());
58 write((uint8_t *)Data.data());
59 OS << Data;
60 }
61
62 using StringPair = std::pair<CachedHashStringRef, size_t>;
63
write(uint8_t * Buf) const64 void StringTableBuilder::write(uint8_t *Buf) const {
65 assert(isFinalized());
66 for (const StringPair &P : StringIndexMap) {
67 StringRef Data = P.first.val();
68 if (!Data.empty())
69 memcpy(Buf + P.second, Data.data(), Data.size());
70 }
71 if (K != WinCOFF)
72 return;
73 support::endian::write32le(Buf, Size);
74 }
75
76 // Returns the character at Pos from end of a string.
charTailAt(StringPair * P,size_t Pos)77 static int charTailAt(StringPair *P, size_t Pos) {
78 StringRef S = P->first.val();
79 if (Pos >= S.size())
80 return -1;
81 return (unsigned char)S[S.size() - Pos - 1];
82 }
83
84 // Three-way radix quicksort. This is much faster than std::sort with strcmp
85 // because it does not compare characters that we already know the same.
multikeySort(MutableArrayRef<StringPair * > Vec,int Pos)86 static void multikeySort(MutableArrayRef<StringPair *> Vec, int Pos) {
87 tailcall:
88 if (Vec.size() <= 1)
89 return;
90
91 // Partition items so that items in [0, I) are greater than the pivot,
92 // [I, J) are the same as the pivot, and [J, Vec.size()) are less than
93 // the pivot.
94 int Pivot = charTailAt(Vec[0], Pos);
95 size_t I = 0;
96 size_t J = Vec.size();
97 for (size_t K = 1; K < J;) {
98 int C = charTailAt(Vec[K], Pos);
99 if (C > Pivot)
100 std::swap(Vec[I++], Vec[K++]);
101 else if (C < Pivot)
102 std::swap(Vec[--J], Vec[K]);
103 else
104 K++;
105 }
106
107 multikeySort(Vec.slice(0, I), Pos);
108 multikeySort(Vec.slice(J), Pos);
109
110 // multikeySort(Vec.slice(I, J - I), Pos + 1), but with
111 // tail call optimization.
112 if (Pivot != -1) {
113 Vec = Vec.slice(I, J - I);
114 ++Pos;
115 goto tailcall;
116 }
117 }
118
finalize()119 void StringTableBuilder::finalize() {
120 assert(K != DWARF);
121 finalizeStringTable(/*Optimize=*/true);
122 }
123
finalizeInOrder()124 void StringTableBuilder::finalizeInOrder() {
125 finalizeStringTable(/*Optimize=*/false);
126 }
127
finalizeStringTable(bool Optimize)128 void StringTableBuilder::finalizeStringTable(bool Optimize) {
129 Finalized = true;
130
131 if (Optimize) {
132 std::vector<StringPair *> Strings;
133 Strings.reserve(StringIndexMap.size());
134 for (StringPair &P : StringIndexMap)
135 Strings.push_back(&P);
136
137 multikeySort(Strings, 0);
138 initSize();
139
140 StringRef Previous;
141 for (StringPair *P : Strings) {
142 StringRef S = P->first.val();
143 if (Previous.endswith(S)) {
144 size_t Pos = Size - S.size() - (K != RAW);
145 if (!(Pos & (Alignment - 1))) {
146 P->second = Pos;
147 continue;
148 }
149 }
150
151 Size = alignTo(Size, Alignment);
152 P->second = Size;
153
154 Size += S.size();
155 if (K != RAW)
156 ++Size;
157 Previous = S;
158 }
159 }
160
161 if (K == MachO)
162 Size = alignTo(Size, 4); // Pad to multiple of 4.
163 }
164
clear()165 void StringTableBuilder::clear() {
166 Finalized = false;
167 StringIndexMap.clear();
168 }
169
getOffset(CachedHashStringRef S) const170 size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
171 assert(isFinalized());
172 auto I = StringIndexMap.find(S);
173 assert(I != StringIndexMap.end() && "String is not in table!");
174 return I->second;
175 }
176
add(CachedHashStringRef S)177 size_t StringTableBuilder::add(CachedHashStringRef S) {
178 if (K == WinCOFF)
179 assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
180
181 assert(!isFinalized());
182 auto P = StringIndexMap.insert(std::make_pair(S, 0));
183 if (P.second) {
184 size_t Start = alignTo(Size, Alignment);
185 P.first->second = Start;
186 Size = Start + S.size() + (K != RAW);
187 }
188 return P.first->second;
189 }
190