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     if (!Data.empty())
83       memcpy(Buf + P.second, Data.data(), Data.size());
84   }
85   if (K != WinCOFF)
86     return;
87   support::endian::write32le(Buf, Size);
88 }
89 
90 // Returns the character at Pos from end of a string.
91 static int charTailAt(StringPair *P, size_t Pos) {
92   StringRef S = P->first.val();
93   if (Pos >= S.size())
94     return -1;
95   return (unsigned char)S[S.size() - Pos - 1];
96 }
97 
98 // Three-way radix quicksort. This is much faster than std::sort with strcmp
99 // because it does not compare characters that we already know the same.
100 static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
101 tailcall:
102   if (End - Begin <= 1)
103     return;
104 
105   // Partition items. Items in [Begin, P) are greater than the pivot,
106   // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
107   int Pivot = charTailAt(*Begin, Pos);
108   StringPair **P = Begin;
109   StringPair **Q = End;
110   for (StringPair **R = Begin + 1; R < Q;) {
111     int C = charTailAt(*R, Pos);
112     if (C > Pivot)
113       std::swap(*P++, *R++);
114     else if (C < Pivot)
115       std::swap(*--Q, *R);
116     else
117       R++;
118   }
119 
120   multikey_qsort(Begin, P, Pos);
121   multikey_qsort(Q, End, Pos);
122   if (Pivot != -1) {
123     // qsort(P, Q, Pos + 1), but with tail call optimization.
124     Begin = P;
125     End = Q;
126     ++Pos;
127     goto tailcall;
128   }
129 }
130 
131 void StringTableBuilder::finalize() {
132   finalizeStringTable(/*Optimize=*/true);
133 }
134 
135 void StringTableBuilder::finalizeInOrder() {
136   finalizeStringTable(/*Optimize=*/false);
137 }
138 
139 void StringTableBuilder::finalizeStringTable(bool Optimize) {
140   Finalized = true;
141 
142   if (Optimize) {
143     std::vector<StringPair *> Strings;
144     Strings.reserve(StringIndexMap.size());
145     for (StringPair &P : StringIndexMap)
146       Strings.push_back(&P);
147 
148     if (!Strings.empty()) {
149       // If we're optimizing, sort by name. If not, sort by previously assigned
150       // offset.
151       multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
152     }
153 
154     initSize();
155 
156     StringRef Previous;
157     for (StringPair *P : Strings) {
158       StringRef S = P->first.val();
159       if (Previous.endswith(S)) {
160         size_t Pos = Size - S.size() - (K != RAW);
161         if (!(Pos & (Alignment - 1))) {
162           P->second = Pos;
163           continue;
164         }
165       }
166 
167       Size = alignTo(Size, Alignment);
168       P->second = Size;
169 
170       Size += S.size();
171       if (K != RAW)
172         ++Size;
173       Previous = S;
174     }
175   }
176 
177   if (K == MachO)
178     Size = alignTo(Size, 4); // Pad to multiple of 4.
179 }
180 
181 void StringTableBuilder::clear() {
182   Finalized = false;
183   StringIndexMap.clear();
184 }
185 
186 size_t StringTableBuilder::getOffset(CachedHashString S) const {
187   assert(isFinalized());
188   auto I = StringIndexMap.find(S);
189   assert(I != StringIndexMap.end() && "String is not in table!");
190   return I->second;
191 }
192 
193 size_t StringTableBuilder::add(CachedHashString S) {
194   if (K == WinCOFF)
195     assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
196 
197   assert(!isFinalized());
198   size_t Start = alignTo(Size, Alignment);
199   auto P = StringIndexMap.insert(std::make_pair(S, Start));
200   if (P.second)
201     Size = Start + S.size() + (K != RAW);
202   return P.first->second;
203 }
204