1 files changed, 68 insertions, 1 deletions

diff --git a/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp b/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
index f17b00e5605..dbe6fe52407 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp
@@ -12,7 +12,6 @@
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
-#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
 #include "llvm/DebugInfo/DWARF/DWARFRelocMap.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Format.h"
@@ -52,6 +51,7 @@ bool DWARFAcceleratorTable::extract() {
     HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
   }
 
+  IsValid = true;
   return true;
 }
 
@@ -109,6 +109,9 @@ DWARFAcceleratorTable::readAtoms(uint32_t &HashDataOffset) {
 }
 
 LLVM_DUMP_METHOD void DWARFAcceleratorTable::dump(raw_ostream &OS) const {
+  if (!IsValid)
+    return;
+
   // Dump the header.
   OS << "Magic = " << format("0x%08x", Hdr.Magic) << '\n'
      << "Version = " << format("0x%04x", Hdr.Version) << '\n'
@@ -190,3 +193,67 @@ LLVM_DUMP_METHOD void DWARFAcceleratorTable::dump(raw_ostream &OS) const {
     }
   }
 }
+
+DWARFAcceleratorTable::ValueIterator::ValueIterator(
+    const DWARFAcceleratorTable &AccelTable, unsigned Offset)
+    : AccelTable(&AccelTable), DataOffset(Offset) {
+  if (!AccelTable.AccelSection.isValidOffsetForDataOfSize(DataOffset, 4))
+    return;
+
+  for (const auto &Atom : AccelTable.HdrData.Atoms)
+    AtomForms.push_back(DWARFFormValue(Atom.second));
+
+  // Read the first entry.
+  NumData = AccelTable.AccelSection.getU32(&DataOffset);
+  Next();
+}
+
+void DWARFAcceleratorTable::ValueIterator::Next() {
+  assert(NumData > 0 && "attempted to increment iterator past the end");
+  auto &AccelSection = AccelTable->AccelSection;
+  if (Data >= NumData ||
+      !AccelSection.isValidOffsetForDataOfSize(DataOffset, 4)) {
+    NumData = 0;
+    return;
+  }
+  for (auto &Atom : AtomForms)
+    Atom.extractValue(AccelSection, &DataOffset, nullptr);
+  ++Data;
+}
+
+iterator_range<DWARFAcceleratorTable::ValueIterator>
+DWARFAcceleratorTable::equal_range(StringRef Key) const {
+  if (!IsValid)
+    return make_range(ValueIterator(), ValueIterator());
+
+  // Find the bucket.
+  unsigned HashValue = dwarf::djbHash(Key);
+  unsigned Bucket = HashValue % Hdr.NumBuckets;
+  unsigned BucketBase = sizeof(Hdr) + Hdr.HeaderDataLength;
+  unsigned HashesBase = BucketBase + Hdr.NumBuckets * 4;
+  unsigned OffsetsBase = HashesBase + Hdr.NumHashes * 4;
+
+  unsigned BucketOffset = BucketBase + Bucket * 4;
+  unsigned Index = AccelSection.getU32(&BucketOffset);
+
+  // Search through all hashes in the bucket.
+  for (unsigned HashIdx = Index; HashIdx < Hdr.NumHashes; ++HashIdx) {
+    unsigned HashOffset = HashesBase + HashIdx * 4;
+    unsigned OffsetsOffset = OffsetsBase + HashIdx * 4;
+    uint32_t Hash = AccelSection.getU32(&HashOffset);
+
+    if (Hash % Hdr.NumBuckets != Bucket)
+      // We are already in the next bucket.
+      break;
+
+    unsigned DataOffset = AccelSection.getU32(&OffsetsOffset);
+    unsigned StringOffset = AccelSection.getRelocatedValue(4, &DataOffset);
+    if (!StringOffset)
+      break;
+
+    // Finally, compare the key.
+    if (Key == StringSection.getCStr(&StringOffset))
+      return make_range({*this, DataOffset}, ValueIterator());
+  }
+  return make_range(ValueIterator(), ValueIterator());
+}