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