LCOV - code coverage report
Current view: top level - lib/DebugInfo/PDB/Native - StringTableBuilder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 43 48 89.6 %
Date: 2017-04-30 16:22:35 Functions: 3 3 100.0 %
Legend: Lines: hit not hit

          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             : }

Generated by: LCOV version 1.13