Line data Source code
1 : //===- StringTableBuilder.cpp - PDB String Table ----------------*- C++ -*-===//
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/DebugInfo/PDB/Native/StringTableBuilder.h"
11 : #include "llvm/ADT/ArrayRef.h"
12 : #include "llvm/DebugInfo/PDB/Native/Hash.h"
13 : #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
14 : #include "llvm/Support/BinaryStreamWriter.h"
15 : #include "llvm/Support/Endian.h"
16 :
17 : using namespace llvm;
18 : using namespace llvm::support;
19 : using namespace llvm::support::endian;
20 : using namespace llvm::pdb;
21 :
22 7 : uint32_t StringTableBuilder::insert(StringRef S) {
23 21 : auto P = Strings.insert({S, StringSize});
24 :
25 : // If a given string didn't exist in the string table, we want to increment
26 : // the string table size.
27 7 : if (P.second)
28 6 : StringSize += S.size() + 1; // +1 for '\0'
29 7 : return P.first->second;
30 : }
31 :
32 : static uint32_t computeBucketCount(uint32_t NumStrings) {
33 : // The /names stream is basically an on-disk open-addressing hash table.
34 : // Hash collisions are resolved by linear probing. We cannot make
35 : // utilization 100% because it will make the linear probing extremely
36 : // slow. But lower utilization wastes disk space. As a reasonable
37 : // load factor, we choose 80%. We need +1 because slot 0 is reserved.
38 46 : return (NumStrings + 1) * 1.25;
39 : }
40 :
41 23 : uint32_t StringTableBuilder::finalize() {
42 23 : uint32_t Size = 0;
43 23 : Size += sizeof(StringTableHeader);
44 23 : Size += StringSize;
45 23 : Size += sizeof(uint32_t); // Hash table begins with 4-byte size field.
46 :
47 69 : uint32_t BucketCount = computeBucketCount(Strings.size());
48 23 : Size += BucketCount * sizeof(uint32_t);
49 :
50 23 : Size +=
51 : sizeof(uint32_t); // The /names stream ends with the number of strings.
52 23 : return Size;
53 : }
54 :
55 23 : Error StringTableBuilder::commit(BinaryStreamWriter &Writer) const {
56 : // Write a header
57 23 : StringTableHeader H;
58 23 : H.Signature = StringTableSignature;
59 23 : H.HashVersion = 1;
60 46 : H.ByteSize = StringSize;
61 69 : if (auto EC = Writer.writeObject(H))
62 0 : return EC;
63 :
64 : // Write a string table.
65 23 : uint32_t StringStart = Writer.getOffset();
66 46 : for (auto Pair : Strings) {
67 6 : StringRef S = Pair.first;
68 6 : uint32_t Offset = Pair.second;
69 12 : Writer.setOffset(StringStart + Offset);
70 18 : if (auto EC = Writer.writeCString(S))
71 0 : return EC;
72 : }
73 46 : Writer.setOffset(StringStart + StringSize);
74 :
75 : // Write a hash table.
76 69 : uint32_t BucketCount = computeBucketCount(Strings.size());
77 69 : if (auto EC = Writer.writeInteger(BucketCount))
78 0 : return EC;
79 46 : std::vector<ulittle32_t> Buckets(BucketCount);
80 :
81 46 : for (auto Pair : Strings) {
82 6 : StringRef S = Pair.first;
83 6 : uint32_t Offset = Pair.second;
84 6 : uint32_t Hash = hashStringV1(S);
85 :
86 7 : for (uint32_t I = 0; I != BucketCount; ++I) {
87 7 : uint32_t Slot = (Hash + I) % BucketCount;
88 7 : if (Slot == 0)
89 : continue; // Skip reserved slot
90 21 : if (Buckets[Slot] != 0)
91 : continue;
92 6 : Buckets[Slot] = Offset;
93 : break;
94 : }
95 : }
96 :
97 69 : if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
98 0 : return EC;
99 92 : if (auto EC = Writer.writeInteger(static_cast<uint32_t>(Strings.size())))
100 0 : return EC;
101 69 : return Error::success();
102 : }
|