1 //===- Range.cpp ------------------------------------------------*- 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/GSYM/Range.h"
11 #include "llvm/DebugInfo/GSYM/FileWriter.h"
12 #include "llvm/Support/DataExtractor.h"
13 #include <algorithm>
14 #include <inttypes.h>
15 
16 using namespace llvm;
17 using namespace gsym;
18 
19 
20 void AddressRanges::insert(AddressRange Range) {
21   if (Range.size() == 0)
22     return;
23 
24   auto It = llvm::upper_bound(Ranges, Range);
25   auto It2 = It;
26   while (It2 != Ranges.end() && It2->Start < Range.End)
27     ++It2;
28   if (It != It2) {
29     Range.End = std::max(Range.End, It2[-1].End);
30     It = Ranges.erase(It, It2);
31   }
32   if (It != Ranges.begin() && Range.Start < It[-1].End)
33     It[-1].End = std::max(It[-1].End, Range.End);
34   else
35     Ranges.insert(It, Range);
36 }
37 
38 bool AddressRanges::contains(uint64_t Addr) const {
39   auto It = std::partition_point(
40       Ranges.begin(), Ranges.end(),
41       [=](const AddressRange &R) { return R.Start <= Addr; });
42   return It != Ranges.begin() && Addr < It[-1].End;
43 }
44 
45 bool AddressRanges::contains(AddressRange Range) const {
46   if (Range.size() == 0)
47     return false;
48   auto It = std::partition_point(
49       Ranges.begin(), Ranges.end(),
50       [=](const AddressRange &R) { return R.Start <= Range.Start; });
51   if (It == Ranges.begin())
52     return false;
53   return Range.End <= It[-1].End;
54 }
55 
56 Optional<AddressRange>
57 AddressRanges::getRangeThatContains(uint64_t Addr) const {
58   auto It = std::partition_point(
59       Ranges.begin(), Ranges.end(),
60       [=](const AddressRange &R) { return R.Start <= Addr; });
61   if (It != Ranges.begin() && Addr < It[-1].End)
62     return It[-1];
63   return llvm::None;
64 }
65 
66 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRange &R) {
67   return OS << '[' << HEX64(R.Start) << " - " << HEX64(R.End) << ")";
68 }
69 
70 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRanges &AR) {
71   size_t Size = AR.size();
72   for (size_t I = 0; I < Size; ++I) {
73     if (I)
74       OS << ' ';
75     OS << AR[I];
76   }
77   return OS;
78 }
79 
80 void AddressRange::encode(FileWriter &O, uint64_t BaseAddr) const {
81   assert(Start >= BaseAddr);
82   O.writeULEB(Start - BaseAddr);
83   O.writeULEB(size());
84 }
85 
86 void AddressRange::decode(DataExtractor &Data, uint64_t BaseAddr,
87                           uint64_t &Offset) {
88   const uint64_t AddrOffset = Data.getULEB128(&Offset);
89   const uint64_t Size = Data.getULEB128(&Offset);
90   const uint64_t StartAddr = BaseAddr + AddrOffset;
91   Start = StartAddr;
92   End = StartAddr + Size;
93 }
94 
95 void AddressRanges::encode(FileWriter &O, uint64_t BaseAddr) const {
96   O.writeULEB(Ranges.size());
97   if (Ranges.empty())
98     return;
99   for (auto Range : Ranges)
100     Range.encode(O, BaseAddr);
101 }
102 
103 void AddressRanges::decode(DataExtractor &Data, uint64_t BaseAddr,
104                            uint64_t &Offset) {
105   clear();
106   uint64_t NumRanges = Data.getULEB128(&Offset);
107   if (NumRanges == 0)
108     return;
109   Ranges.resize(NumRanges);
110   for (auto &Range : Ranges)
111     Range.decode(Data, BaseAddr, Offset);
112 }
113 
114 void AddressRange::skip(DataExtractor &Data, uint64_t &Offset) {
115   Data.getULEB128(&Offset);
116   Data.getULEB128(&Offset);
117 }
118 
119 uint64_t AddressRanges::skip(DataExtractor &Data, uint64_t &Offset) {
120   uint64_t NumRanges = Data.getULEB128(&Offset);
121   for (uint64_t I=0; I<NumRanges; ++I)
122     AddressRange::skip(Data, Offset);
123   return NumRanges;
124 }
125