1 //===- PDBStringTableBuilder.cpp - PDB String Table -------------*- C++ -*-===//
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/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/DebugInfo/MSF/MappedBlockStream.h"
14 #include "llvm/DebugInfo/PDB/Native/Hash.h"
15 #include "llvm/DebugInfo/PDB/Native/PDBFileBuilder.h"
16 #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
17 #include "llvm/Support/BinaryStreamWriter.h"
18 #include "llvm/Support/Endian.h"
21 using namespace llvm::msf;
22 using namespace llvm::support;
23 using namespace llvm::support::endian;
24 using namespace llvm::pdb;
26 uint32_t PDBStringTableBuilder::insert(StringRef S) {
27 return Strings.insert(S);
30 static uint32_t computeBucketCount(uint32_t NumStrings) {
31 // The /names stream is basically an on-disk open-addressing hash table.
32 // Hash collisions are resolved by linear probing. We cannot make
33 // utilization 100% because it will make the linear probing extremely
34 // slow. But lower utilization wastes disk space. As a reasonable
35 // load factor, we choose 80%. We need +1 because slot 0 is reserved.
36 return (NumStrings + 1) * 1.25;
39 uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
40 uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
41 Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
46 uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
48 Size += sizeof(PDBStringTableHeader);
49 Size += Strings.calculateSerializedSize();
50 Size += calculateHashTableSize();
51 Size += sizeof(uint32_t); // The /names stream ends with the string count.
55 void PDBStringTableBuilder::setStrings(
56 const codeview::DebugStringTableSubsection &Strings) {
57 this->Strings = Strings;
60 Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
62 PDBStringTableHeader H;
63 H.Signature = PDBStringTableSignature;
65 H.ByteSize = Strings.calculateSerializedSize();
66 if (auto EC = Writer.writeObject(H))
68 assert(Writer.bytesRemaining() == 0);
69 return Error::success();
72 Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
73 if (auto EC = Strings.commit(Writer))
76 assert(Writer.bytesRemaining() == 0);
77 return Error::success();
80 Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
81 // Write a hash table.
82 uint32_t BucketCount = computeBucketCount(Strings.size());
83 if (auto EC = Writer.writeInteger(BucketCount))
85 std::vector<ulittle32_t> Buckets(BucketCount);
87 for (auto &Pair : Strings) {
88 StringRef S = Pair.getKey();
89 uint32_t Offset = Pair.getValue();
90 uint32_t Hash = hashStringV1(S);
92 for (uint32_t I = 0; I != BucketCount; ++I) {
93 uint32_t Slot = (Hash + I) % BucketCount;
95 continue; // Skip reserved slot
96 if (Buckets[Slot] != 0)
98 Buckets[Slot] = Offset;
103 if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
106 assert(Writer.bytesRemaining() == 0);
107 return Error::success();
110 Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
111 if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
113 assert(Writer.bytesRemaining() == 0);
114 return Error::success();
117 Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
118 BinaryStreamWriter SectionWriter;
120 std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
121 if (auto EC = writeHeader(SectionWriter))
124 std::tie(SectionWriter, Writer) =
125 Writer.split(Strings.calculateSerializedSize());
126 if (auto EC = writeStrings(SectionWriter))
129 std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
130 if (auto EC = writeHashTable(SectionWriter))
133 std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
134 if (auto EC = writeEpilogue(SectionWriter))
137 return Error::success();