contrib/llvm/include/llvm/DebugInfo/CodeView/LazyRandomTypeCollection.h

   1 //===- LazyRandomTypeCollection.h ---------------------------- *- 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 #ifndef LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
  11 #define LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H
  12
  13 #include "llvm/DebugInfo/CodeView/TypeCollection.h"
  14 #include "llvm/DebugInfo/CodeView/TypeIndex.h"
  15 #include "llvm/DebugInfo/CodeView/TypeRecord.h"
  16 #include "llvm/Support/Allocator.h"
  17 #include "llvm/Support/Error.h"
  18 #include "llvm/Support/StringSaver.h"
  19
  20 namespace llvm {
  21 namespace codeview {
  22
  23 /// \brief Provides amortized O(1) random access to a CodeView type stream.
  24 /// Normally to access a type from a type stream, you must know its byte
  25 /// offset into the type stream, because type records are variable-lengthed.
  26 /// However, this is not the way we prefer to access them.  For example, given
  27 /// a symbol record one of the fields may be the TypeIndex of the symbol's
  28 /// type record.  Or given a type record such as an array type, there might
  29 /// be a TypeIndex for the element type.  Sequential access is perfect when
  30 /// we're just dumping every entry, but it's very poor for real world usage.
  31 ///
  32 /// Type streams in PDBs contain an additional field which is a list of pairs
  33 /// containing indices and their corresponding offsets, roughly every ~8KB of
  34 /// record data.  This general idea need not be confined to PDBs though.  By
  35 /// supplying such an array, the producer of a type stream can allow the
  36 /// consumer much better access time, because the consumer can find the nearest
  37 /// index in this array, and do a linear scan forward only from there.
  38 ///
  39 /// LazyRandomTypeCollection implements this algorithm, but additionally goes
  40 /// one step further by caching offsets of every record that has been visited at
  41 /// least once.  This way, even repeated visits of the same record will never
  42 /// require more than one linear scan.  For a type stream of N elements divided
  43 /// into M chunks of roughly equal size, this yields a worst case lookup time
  44 /// of O(N/M) and an amortized time of O(1).
  45 class LazyRandomTypeCollection : public TypeCollection {
  46   typedef FixedStreamArray<TypeIndexOffset> PartialOffsetArray;
  47   struct CacheEntry {
  48     CVType Type;
  49     uint32_t Offset;
  50     StringRef Name;
  51   };
  52
  53 public:
  54   explicit LazyRandomTypeCollection(uint32_t RecordCountHint);
  55   LazyRandomTypeCollection(StringRef Data, uint32_t RecordCountHint);
  56   LazyRandomTypeCollection(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
  57   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint,
  58                            PartialOffsetArray PartialOffsets);
  59   LazyRandomTypeCollection(const CVTypeArray &Types, uint32_t RecordCountHint);
  60
  61   void reset(ArrayRef<uint8_t> Data, uint32_t RecordCountHint);
  62   void reset(StringRef Data, uint32_t RecordCountHint);
  63
  64   uint32_t getOffsetOfType(TypeIndex Index);
  65
  66   CVType getType(TypeIndex Index) override;
  67   StringRef getTypeName(TypeIndex Index) override;
  68   bool contains(TypeIndex Index) override;
  69   uint32_t size() override;
  70   uint32_t capacity() override;
  71   Optional<TypeIndex> getFirst() override;
  72   Optional<TypeIndex> getNext(TypeIndex Prev) override;
  73
  74 private:
  75   Error ensureTypeExists(TypeIndex Index);
  76   void ensureCapacityFor(TypeIndex Index);
  77
  78   Error visitRangeForType(TypeIndex TI);
  79   Error fullScanForType(TypeIndex TI);
  80   void visitRange(TypeIndex Begin, uint32_t BeginOffset, TypeIndex End);
  81
  82   /// Number of actual records.
  83   uint32_t Count = 0;
  84
  85   /// The largest type index which we've visited.
  86   TypeIndex LargestTypeIndex = TypeIndex::None();
  87
  88   BumpPtrAllocator Allocator;
  89   StringSaver NameStorage;
  90
  91   /// The type array to allow random access visitation of.
  92   CVTypeArray Types;
  93
  94   std::vector<CacheEntry> Records;
  95
  96   /// An array of index offsets for the given type stream, allowing log(N)
  97   /// lookups of a type record by index.  Similar to KnownOffsets but only
  98   /// contains offsets for some type indices, some of which may not have
  99   /// ever been visited.
 100   PartialOffsetArray PartialOffsets;
 101 };
 102
 103 } // end namespace codeview
 104 } // end namespace llvm
 105
 106 #endif // LLVM_DEBUGINFO_CODEVIEW_LAZYRANDOMTYPECOLLECTION_H