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) : K(K) {} 20 21 static int compareBySuffix(std::pair<StringRef, size_t> *const *AP, 22 std::pair<StringRef, size_t> *const *BP) { 23 StringRef A = (*AP)->first; 24 StringRef B = (*BP)->first; 25 size_t SizeA = A.size(); 26 size_t SizeB = B.size(); 27 size_t Len = std::min(SizeA, SizeB); 28 for (size_t I = 0; I < Len; ++I) { 29 char CA = A[SizeA - I - 1]; 30 char CB = B[SizeB - I - 1]; 31 if (CA != CB) 32 return CB - CA; 33 } 34 return SizeB - SizeA; 35 } 36 37 void StringTableBuilder::finalize() { 38 std::vector<std::pair<StringRef, size_t> *> Strings; 39 Strings.reserve(StringIndexMap.size()); 40 for (std::pair<StringRef, size_t> &P : StringIndexMap) 41 Strings.push_back(&P); 42 43 array_pod_sort(Strings.begin(), Strings.end(), compareBySuffix); 44 45 switch (K) { 46 case RAW: 47 break; 48 case ELF: 49 case MachO: 50 // Start the table with a NUL byte. 51 StringTable += '\x00'; 52 break; 53 case WinCOFF: 54 // Make room to write the table size later. 55 StringTable.append(4, '\x00'); 56 break; 57 } 58 59 StringRef Previous; 60 for (std::pair<StringRef, size_t> *P : Strings) { 61 StringRef S = P->first; 62 if (K == WinCOFF) 63 assert(S.size() > COFF::NameSize && "Short string in COFF string table!"); 64 65 if (Previous.endswith(S)) { 66 P->second = StringTable.size() - S.size() - (K != RAW); 67 continue; 68 } 69 70 P->second = StringTable.size(); 71 StringTable += S; 72 if (K != RAW) 73 StringTable += '\x00'; 74 Previous = S; 75 } 76 77 switch (K) { 78 case RAW: 79 case ELF: 80 break; 81 case MachO: 82 // Pad to multiple of 4. 83 while (StringTable.size() % 4) 84 StringTable += '\x00'; 85 break; 86 case WinCOFF: 87 // Write the table size in the first word. 88 assert(StringTable.size() <= std::numeric_limits<uint32_t>::max()); 89 uint32_t Size = static_cast<uint32_t>(StringTable.size()); 90 support::endian::write<uint32_t, support::little, support::unaligned>( 91 StringTable.data(), Size); 92 break; 93 } 94 95 Size = StringTable.size(); 96 } 97 98 void StringTableBuilder::clear() { 99 StringTable.clear(); 100 StringIndexMap.clear(); 101 } 102 103 size_t StringTableBuilder::getOffset(StringRef S) const { 104 assert(isFinalized()); 105 auto I = StringIndexMap.find(S); 106 assert(I != StringIndexMap.end() && "String is not in table!"); 107 return I->second; 108 } 109 110 size_t StringTableBuilder::add(StringRef S) { 111 assert(!isFinalized()); 112 auto P = StringIndexMap.insert(std::make_pair(S, Size)); 113 if (P.second) 114 Size += S.size() + (K != RAW); 115 return P.first->second; 116 } 117