LLVM  6.0.0svn
StringTableBuilder.cpp
Go to the documentation of this file.
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 
12 #include "llvm/ADT/SmallString.h"
13 #include "llvm/ADT/StringRef.h"
14 #include "llvm/BinaryFormat/COFF.h"
15 #include "llvm/Support/Endian.h"
18 #include <cassert>
19 #include <cstddef>
20 #include <cstdint>
21 #include <cstring>
22 #include <utility>
23 #include <vector>
24 
25 using namespace llvm;
26 
28 
29 void StringTableBuilder::initSize() {
30  // Account for leading bytes in table so that offsets returned from add are
31  // correct.
32  switch (K) {
33  case RAW:
34  Size = 0;
35  break;
36  case MachO:
37  case ELF:
38  // Start the table with a NUL byte.
39  Size = 1;
40  break;
41  case WinCOFF:
42  // Make room to write the table size later.
43  Size = 4;
44  break;
45  }
46 }
47 
49  : K(K), Alignment(Alignment) {
50  initSize();
51 }
52 
54  assert(isFinalized());
56  Data.resize(getSize());
57  write((uint8_t *)Data.data());
58  OS << Data;
59 }
60 
61 using StringPair = std::pair<CachedHashStringRef, size_t>;
62 
63 void StringTableBuilder::write(uint8_t *Buf) const {
64  assert(isFinalized());
65  for (const StringPair &P : StringIndexMap) {
66  StringRef Data = P.first.val();
67  if (!Data.empty())
68  memcpy(Buf + P.second, Data.data(), Data.size());
69  }
70  if (K != WinCOFF)
71  return;
72  support::endian::write32le(Buf, Size);
73 }
74 
75 // Returns the character at Pos from end of a string.
76 static int charTailAt(StringPair *P, size_t Pos) {
77  StringRef S = P->first.val();
78  if (Pos >= S.size())
79  return -1;
80  return (unsigned char)S[S.size() - Pos - 1];
81 }
82 
83 // Three-way radix quicksort. This is much faster than std::sort with strcmp
84 // because it does not compare characters that we already know the same.
85 static void multikeySort(MutableArrayRef<StringPair *> Vec, int Pos) {
86 tailcall:
87  if (Vec.size() <= 1)
88  return;
89 
90  // Partition items so that items in [0, I) are greater than the pivot,
91  // [I, J) are the same as the pivot, and [J, Vec.size()) are less than
92  // the pivot.
93  int Pivot = charTailAt(Vec[0], Pos);
94  size_t I = 0;
95  size_t J = Vec.size();
96  for (size_t K = 1; K < J;) {
97  int C = charTailAt(Vec[K], Pos);
98  if (C > Pivot)
99  std::swap(Vec[I++], Vec[K++]);
100  else if (C < Pivot)
101  std::swap(Vec[--J], Vec[K]);
102  else
103  K++;
104  }
105 
106  multikeySort(Vec.slice(0, I), Pos);
107  multikeySort(Vec.slice(J), Pos);
108 
109  // multikeySort(Vec.slice(I, J - I), Pos + 1), but with
110  // tail call optimization.
111  if (Pivot != -1) {
112  Vec = Vec.slice(I, J - I);
113  ++Pos;
114  goto tailcall;
115  }
116 }
117 
119  finalizeStringTable(/*Optimize=*/true);
120 }
121 
123  finalizeStringTable(/*Optimize=*/false);
124 }
125 
126 void StringTableBuilder::finalizeStringTable(bool Optimize) {
127  Finalized = true;
128 
129  if (Optimize) {
130  std::vector<StringPair *> Strings;
131  Strings.reserve(StringIndexMap.size());
132  for (StringPair &P : StringIndexMap)
133  Strings.push_back(&P);
134 
135  multikeySort(Strings, 0);
136  initSize();
137 
138  StringRef Previous;
139  for (StringPair *P : Strings) {
140  StringRef S = P->first.val();
141  if (Previous.endswith(S)) {
142  size_t Pos = Size - S.size() - (K != RAW);
143  if (!(Pos & (Alignment - 1))) {
144  P->second = Pos;
145  continue;
146  }
147  }
148 
149  Size = alignTo(Size, Alignment);
150  P->second = Size;
151 
152  Size += S.size();
153  if (K != RAW)
154  ++Size;
155  Previous = S;
156  }
157  }
158 
159  if (K == MachO)
160  Size = alignTo(Size, 4); // Pad to multiple of 4.
161 }
162 
164  Finalized = false;
165  StringIndexMap.clear();
166 }
167 
169  assert(isFinalized());
170  auto I = StringIndexMap.find(S);
171  assert(I != StringIndexMap.end() && "String is not in table!");
172  return I->second;
173 }
174 
176  if (K == WinCOFF)
177  assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
178 
179  assert(!isFinalized());
180  auto P = StringIndexMap.insert(std::make_pair(S, 0));
181  if (P.second) {
182  size_t Start = alignTo(Size, Alignment);
183  P.first->second = Start;
184  Size = Start + S.size() + (K != RAW);
185  }
186  return P.first->second;
187 }
uint64_t CallInst * C
MutableArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array...
Definition: ArrayRef.h:351
A container which contains a StringRef plus a precomputed hash.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const
size - Get the string size.
Definition: StringRef.h:138
void write32le(void *P, uint32_t V)
Definition: Endian.h:404
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:677
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool endswith(StringRef Suffix) const
Check if this string ends with the given Suffix.
Definition: StringRef.h:279
void write(raw_ostream &OS) const
size_t add(CachedHashStringRef S)
Add a string to the builder.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool empty() const
empty - Check if the string is empty.
Definition: StringRef.h:133
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
Definition: SmallString.h:26
static int charTailAt(StringPair *P, size_t Pos)
#define P(N)
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
Definition: ArrayRef.h:291
void finalizeInOrder()
Finalize the string table without reording it.
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
void finalize()
Analyze the strings and build the final table.
size_t getOffset(CachedHashStringRef S) const
Get the offest of a string in the string table.
StringTableBuilder(Kind K, unsigned Alignment=1)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:923
pointer data()
Return a pointer to the vector&#39;s buffer, even if empty().
Definition: SmallVector.h:143
#define I(x, y, z)
Definition: MD5.cpp:58
std::pair< CachedHashStringRef, size_t > StringPair
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void multikeySort(MutableArrayRef< StringPair *> Vec, int Pos)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
void resize(size_type N)
Definition: SmallVector.h:355