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 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. 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. 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 80 void StringTableBuilder::finalize() { 81 finalizeStringTable(/*Optimize=*/true); 82 } 83 84 void StringTableBuilder::finalizeInOrder() { 85 finalizeStringTable(/*Optimize=*/false); 86 } 87 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 172 void StringTableBuilder::clear() { 173 StringTable.clear(); 174 StringIndexMap.clear(); 175 } 176 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!"); 181 return I->second; 182 } 183 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