CPPUtil/UtilAbsInterval.cpp

   1 //
   2 //  UtilAbsInterval.cpp
   3 //  CPPUtil
   4 //
   5 //  Created by James McIlree on 9/8/13.
   6 //  Copyright (c) 2013 Apple. All rights reserved.
   7 //
   8
   9 #include "CPPUtil.h"
  10
  11 BEGIN_UTIL_NAMESPACE
  12
  13 const AbsInterval* interval_beginning_timespan(const std::vector<AbsInterval>& intervals, AbsInterval timespan) {
  14         auto it = std::upper_bound(intervals.begin(), intervals.end(), timespan.location(), AbsIntervalMaxVsAbsTimeComparator());
  15
  16         //
  17         // For a beginning interval, there is no possible match if timespan.location() > intervals.back().max()
  18         //
  19         if (it != intervals.end()) {
  20                 //
  21                 // We found something. Does it contain the search point?
  22                 //
  23                 if (it->contains(timespan.location())) {
  24                         return &*it;
  25                 }
  26
  27                 //
  28                 // If the AbsInterval found intersects the timespan, its still the first valid vm_fault in
  29                 // the given timespan, so return it anyway.
  30                 //
  31                 if (it->intersects(timespan)) {
  32                         return &*it;
  33                 }
  34         }
  35
  36         return NULL;
  37 }
  38
  39 const AbsInterval* interval_ending_timespan(const std::vector<AbsInterval>& intervals, AbsInterval timespan) {
  40
  41         // We could do this as timespan.max() and use lower_bound(...) to save the subtraction.
  42         // But we need the max()-1 value later for the contains() test anyway, so might as well calculate
  43         // it here.
  44         AbsTime max = timespan.max() - AbsTime(1);
  45         auto it = std::upper_bound(intervals.begin(), intervals.end(), max, AbsIntervalMaxVsAbsTimeComparator());
  46
  47         // Did we find something?
  48         if (it != intervals.end()) {
  49
  50                 if (it->contains(max)) {
  51                         return &*it;
  52                 }
  53
  54                 // Okay, the matched interval is to the "right" of us on the
  55                 // timeline. Is there a previous interval that might work?
  56                 if (it != intervals.begin()) {
  57                         if ((--it)->intersects(timespan)) {
  58                                 return &*it;
  59                         }
  60                 }
  61         } else {
  62                 // Okay, we're off the end of the timeline. There still might
  63                 // be a previous interval that would match.
  64                 if (!intervals.empty()) {
  65                         if ((--it)->intersects(timespan)) {
  66                                 return &*it;
  67                         }
  68                 }
  69         }
  70
  71         return NULL;
  72 }
  73
  74 END_UTIL_NAMESPACE