1//===- AddressRanges.cpp ----------------------------------------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include "llvm/ADT/AddressRanges.h" 10#include "llvm/ADT/STLExtras.h" 11#include <inttypes.h> 12 13using namespace llvm; 14 15AddressRanges::Collection::const_iterator 16AddressRanges::insert(AddressRange Range) { 17 if (Range.size() == 0) 18 return Ranges.end(); 19 20 auto It = llvm::upper_bound(Ranges, Range); 21 auto It2 = It; 22 while (It2 != Ranges.end() && It2->start() <= Range.end()) 23 ++It2; 24 if (It != It2) { 25 Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())}; 26 It = Ranges.erase(It, It2); 27 } 28 if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) { 29 --It; 30 *It = {It->start(), std::max(It->end(), Range.end())}; 31 return It; 32 } 33 34 return Ranges.insert(It, Range); 35} 36 37AddressRanges::Collection::const_iterator 38AddressRanges::find(uint64_t Addr) const { 39 auto It = std::partition_point( 40 Ranges.begin(), Ranges.end(), 41 [=](const AddressRange &R) { return R.start() <= Addr; }); 42 43 if (It == Ranges.begin()) 44 return Ranges.end(); 45 46 --It; 47 if (Addr >= It->end()) 48 return Ranges.end(); 49 50 return It; 51} 52 53AddressRanges::Collection::const_iterator 54AddressRanges::find(AddressRange Range) const { 55 if (Range.size() == 0) 56 return Ranges.end(); 57 58 auto It = std::partition_point( 59 Ranges.begin(), Ranges.end(), 60 [=](const AddressRange &R) { return R.start() <= Range.start(); }); 61 62 if (It == Ranges.begin()) 63 return Ranges.end(); 64 65 --It; 66 if (Range.end() > It->end()) 67 return Ranges.end(); 68 69 return It; 70} 71