1 //===-- StringTableBuilder.cpp - String table building utility ------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/MC/StringTableBuilder.h"
11 #include "llvm/ADT/STLExtras.h"
12 #include "llvm/ADT/SmallString.h"
13 #include "llvm/Support/COFF.h"
14 #include "llvm/Support/Endian.h"
15 #include "llvm/Support/raw_ostream.h"
21 StringTableBuilder::~StringTableBuilder() {}
23 void StringTableBuilder::initSize() {
24 // Account for leading bytes in table so that offsets returned from add are
32 // Start the table with a NUL byte.
36 // Make room to write the table size later.
42 StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
43 : K(K), Alignment(Alignment) {
47 void StringTableBuilder::write(raw_ostream &OS) const {
48 assert(isFinalized());
50 Data.resize(getSize());
51 write((uint8_t *)&Data[0]);
55 typedef std::pair<CachedHashStringRef, size_t> StringPair;
57 void StringTableBuilder::write(uint8_t *Buf) const {
58 assert(isFinalized());
59 for (const StringPair &P : StringIndexMap) {
60 StringRef Data = P.first.val();
62 memcpy(Buf + P.second, Data.data(), Data.size());
66 support::endian::write32le(Buf, Size);
69 // Returns the character at Pos from end of a string.
70 static int charTailAt(StringPair *P, size_t Pos) {
71 StringRef S = P->first.val();
74 return (unsigned char)S[S.size() - Pos - 1];
77 // Three-way radix quicksort. This is much faster than std::sort with strcmp
78 // because it does not compare characters that we already know the same.
79 static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
84 // Partition items. Items in [Begin, P) are greater than the pivot,
85 // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
86 int Pivot = charTailAt(*Begin, Pos);
87 StringPair **P = Begin;
89 for (StringPair **R = Begin + 1; R < Q;) {
90 int C = charTailAt(*R, Pos);
92 std::swap(*P++, *R++);
99 multikey_qsort(Begin, P, Pos);
100 multikey_qsort(Q, End, Pos);
102 // qsort(P, Q, Pos + 1), but with tail call optimization.
110 void StringTableBuilder::finalize() {
111 finalizeStringTable(/*Optimize=*/true);
114 void StringTableBuilder::finalizeInOrder() {
115 finalizeStringTable(/*Optimize=*/false);
118 void StringTableBuilder::finalizeStringTable(bool Optimize) {
122 std::vector<StringPair *> Strings;
123 Strings.reserve(StringIndexMap.size());
124 for (StringPair &P : StringIndexMap)
125 Strings.push_back(&P);
127 if (!Strings.empty()) {
128 // If we're optimizing, sort by name. If not, sort by previously assigned
130 multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
136 for (StringPair *P : Strings) {
137 StringRef S = P->first.val();
138 if (Previous.endswith(S)) {
139 size_t Pos = Size - S.size() - (K != RAW);
140 if (!(Pos & (Alignment - 1))) {
146 Size = alignTo(Size, Alignment);
157 Size = alignTo(Size, 4); // Pad to multiple of 4.
160 void StringTableBuilder::clear() {
162 StringIndexMap.clear();
165 size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
166 assert(isFinalized());
167 auto I = StringIndexMap.find(S);
168 assert(I != StringIndexMap.end() && "String is not in table!");
172 size_t StringTableBuilder::add(CachedHashStringRef S) {
174 assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
176 assert(!isFinalized());
177 auto P = StringIndexMap.insert(std::make_pair(S, 0));
179 size_t Start = alignTo(Size, Alignment);
180 P.first->second = Start;
181 Size = Start + S.size() + (K != RAW);
183 return P.first->second;