src/kits/debugger/util/RangeList.cpp

   1 /*
   2  * Copyright 2013, Rene Gollent, rene@gollent.com.
   3  * Distributed under the terms of the MIT License.
   4  */
   5
   6
   7 #include "RangeList.h"
   8
   9 #include <AutoDeleter.h>
  10
  11
  12 RangeList::RangeList()
  13         : BObjectList<Range>(20, true)
  14 {
  15 }
  16
  17
  18 RangeList::~RangeList()
  19 {
  20 }
  21
  22
  23 status_t
  24 RangeList::AddRange(int32 lowValue, int32 highValue)
  25 {
  26         if (lowValue > highValue)
  27                 return B_BAD_VALUE;
  28
  29         int32 i = 0;
  30         if (CountItems() != 0) {
  31                 for (; i < CountItems(); i++) {
  32                         Range* range = ItemAt(i);
  33                         if (lowValue < range->lowerBound) {
  34                                 if (highValue < range->lowerBound) {
  35                                         // the new range is completely below the bounds
  36                                         // of the ranges we currently contain,
  37                                         // insert it here.
  38                                         break;
  39                                 } else if (highValue <= range->upperBound) {
  40                                         // the new range partly overlaps the lower
  41                                         // current range
  42                                         range->lowerBound = lowValue;
  43                                         return B_OK;
  44                                 } else {
  45                                         // the new range completely encompasses
  46                                         // the current range
  47                                         range->lowerBound = lowValue;
  48                                         range->upperBound = highValue;
  49                                         _CollapseOverlappingRanges(i +1, highValue);
  50                                 }
  51
  52                         } else if (lowValue < range->upperBound) {
  53                                 if (highValue <= range->upperBound) {
  54                                         // the requested range is already completely contained
  55                                         // within our existing range list
  56                                         return B_OK;
  57                                 } else {
  58                                         range->upperBound = highValue;
  59                                         _CollapseOverlappingRanges(i + 1, highValue);
  60                                         return B_OK;
  61                                 }
  62                         }
  63                 }
  64         }
  65
  66         Range* range = new(std::nothrow) Range(lowValue, highValue);
  67         if (range == NULL)
  68                 return B_NO_MEMORY;
  69
  70         BPrivate::ObjectDeleter<Range> rangeDeleter(range);
  71         if (!AddItem(range, i))
  72                 return B_NO_MEMORY;
  73
  74         rangeDeleter.Detach();
  75         return B_OK;
  76 }
  77
  78
  79 status_t
  80 RangeList::AddRange(const Range& range)
  81 {
  82         return AddRange(range.lowerBound, range.upperBound);
  83 }
  84
  85
  86 void
  87 RangeList::RemoveRangeAt(int32 index)
  88 {
  89         if (index < 0 || index >= CountItems())
  90                 return;
  91
  92         RemoveItem(ItemAt(index));
  93 }
  94
  95
  96 bool
  97 RangeList::Contains(int32 value) const
  98 {
  99         for (int32 i = 0; i < CountItems(); i++) {
 100                 const Range* range = ItemAt(i);
 101                 if (value < range->lowerBound || value > range->upperBound)
 102                         break;
 103                 else if (value >= range->lowerBound && value <= range->upperBound)
 104                         return true;
 105         }
 106
 107         return false;
 108 }
 109
 110
 111 int32
 112 RangeList::CountRanges() const
 113 {
 114         return CountItems();
 115 }
 116
 117
 118 const Range*
 119 RangeList::RangeAt(int32 index) const
 120 {
 121         return ItemAt(index);
 122 }
 123
 124
 125 void
 126 RangeList::_CollapseOverlappingRanges(int32 startIndex, int32 highValue)
 127 {
 128         for (int32 i = startIndex; i < CountItems();) {
 129                 // check if it also overlaps any of the following
 130                 // ranges.
 131                 Range* nextRange = ItemAt(i);
 132                 if (nextRange->lowerBound > highValue)
 133                         return;
 134                 else if (nextRange->upperBound < highValue) {
 135                         RemoveItem(nextRange);
 136                         continue;
 137                 } else {
 138                         nextRange->lowerBound = highValue + 1;
 139                         return;
 140                 }
 141         }
 142 }