StringTableBuilder.cpp revision 296417 
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
17using namespace llvm;
18
19StringTableBuilder::StringTableBuilder(Kind K) : K(K) {}
20
21typedef std::pair<StringRef, size_t> StringPair;
22
23// Returns the character at Pos from end of a string.
24static int charTailAt(StringPair *P, size_t Pos) {
25  StringRef S = P->first;
26  if (Pos >= S.size())
27    return -1;
28  return (unsigned char)S[S.size() - Pos - 1];
29}
30
31// Three-way radix quicksort. This is much faster than std::sort with strcmp
32// because it does not compare characters that we already know the same.
33static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
34tailcall:
35  if (End - Begin <= 1)
36    return;
37
38  // Partition items. Items in [Begin, P) are greater than the pivot,
39  // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
40  int Pivot = charTailAt(*Begin, Pos);
41  StringPair **P = Begin;
42  StringPair **Q = End;
43  for (StringPair **R = Begin + 1; R < Q;) {
44    int C = charTailAt(*R, Pos);
45    if (C > Pivot)
46      std::swap(*P++, *R++);
47    else if (C < Pivot)
48      std::swap(*--Q, *R);
49    else
50      R++;
51  }
52
53  multikey_qsort(Begin, P, Pos);
54  multikey_qsort(Q, End, Pos);
55  if (Pivot != -1) {
56    // qsort(P, Q, Pos + 1), but with tail call optimization.
57    Begin = P;
58    End = Q;
59    ++Pos;
60    goto tailcall;
61  }
62}
63
64void StringTableBuilder::finalize() {
65  std::vector<std::pair<StringRef, size_t> *> Strings;
66  Strings.reserve(StringIndexMap.size());
67  for (std::pair<StringRef, size_t> &P : StringIndexMap)
68    Strings.push_back(&P);
69
70  if (!Strings.empty())
71    multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
72
73  switch (K) {
74  case RAW:
75    break;
76  case ELF:
77  case MachO:
78    // Start the table with a NUL byte.
79    StringTable += '\x00';
80    break;
81  case WinCOFF:
82    // Make room to write the table size later.
83    StringTable.append(4, '\x00');
84    break;
85  }
86
87  StringRef Previous;
88  for (std::pair<StringRef, size_t> *P : Strings) {
89    StringRef S = P->first;
90    if (K == WinCOFF)
91      assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
92
93    if (Previous.endswith(S)) {
94      P->second = StringTable.size() - S.size() - (K != RAW);
95      continue;
96    }
97
98    P->second = StringTable.size();
99    StringTable += S;
100    if (K != RAW)
101      StringTable += '\x00';
102    Previous = S;
103  }
104
105  switch (K) {
106  case RAW:
107  case ELF:
108    break;
109  case MachO:
110    // Pad to multiple of 4.
111    while (StringTable.size() % 4)
112      StringTable += '\x00';
113    break;
114  case WinCOFF:
115    // Write the table size in the first word.
116    assert(StringTable.size() <= std::numeric_limits<uint32_t>::max());
117    uint32_t Size = static_cast<uint32_t>(StringTable.size());
118    support::endian::write<uint32_t, support::little, support::unaligned>(
119        StringTable.data(), Size);
120    break;
121  }
122
123  Size = StringTable.size();
124}
125
126void StringTableBuilder::clear() {
127  StringTable.clear();
128  StringIndexMap.clear();
129}
130
131size_t StringTableBuilder::getOffset(StringRef S) const {
132  assert(isFinalized());
133  auto I = StringIndexMap.find(S);
134  assert(I != StringIndexMap.end() && "String is not in table!");
135  return I->second;
136}
137
138size_t StringTableBuilder::add(StringRef S) {
139  assert(!isFinalized());
140  auto P = StringIndexMap.insert(std::make_pair(S, Size));
141  if (P.second)
142    Size += S.size() + (K != RAW);
143  return P.first->second;
144}
145