1 //===-- StringTableBuilder.cpp - String table building utility ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/MC/StringTableBuilder.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/Support/COFF.h"
13 #include "llvm/Support/Endian.h"
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
37 typedef std::pair<CachedHash<StringRef>, size_t> StringPair;
39 // Returns the character at Pos from end of a string.
40 static int charTailAt(StringPair *P, size_t Pos) {
41 StringRef S = P->first.Val;
44 return (unsigned char)S[S.size() - Pos - 1];
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.
49 static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
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;
59 for (StringPair **R = Begin + 1; R < Q;) {
60 int C = charTailAt(*R, Pos);
62 std::swap(*P++, *R++);
69 multikey_qsort(Begin, P, Pos);
70 multikey_qsort(Q, End, Pos);
72 // qsort(P, Q, Pos + 1), but with tail call optimization.
80 void StringTableBuilder::finalize() {
81 finalizeStringTable(/*Optimize=*/true);
84 void StringTableBuilder::finalizeInOrder() {
85 finalizeStringTable(/*Optimize=*/false);
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);
95 if (!Strings.empty()) {
96 // If we're optimizing, sort by name. If not, sort by previously assigned
99 multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
101 std::sort(Strings.begin(), Strings.end(),
102 [](const StringOffsetPair *LHS, const StringOffsetPair *RHS) {
103 return LHS->second < RHS->second;
113 // Start the table with a NUL byte.
114 StringTable += '\x00';
117 // Make room to write the table size later.
118 StringTable.append(4, '\x00');
123 for (StringOffsetPair *P : Strings) {
124 StringRef S = P->first.Val;
126 assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
128 if (Optimize && Previous.endswith(S)) {
129 size_t Pos = StringTable.size() - S.size() - (K != RAW);
130 if (!(Pos & (Alignment - 1))) {
137 size_t Start = alignTo(StringTable.size(), Alignment);
139 StringTable.append(Start - StringTable.size(), '\0');
141 assert(P->second == StringTable.size() &&
142 "different strtab offset after finalization");
147 StringTable += '\x00';
156 // Pad to multiple of 4.
157 while (StringTable.size() % 4)
158 StringTable += '\x00';
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);
169 Size = StringTable.size();
172 void StringTableBuilder::clear() {
174 StringIndexMap.clear();
177 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!");
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));
189 Size = Start + S.size() + (K != RAW);
190 return P.first->second;