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