aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/basetypes
diff options
context:
space:
mode:
Diffstat (limited to 'src/core/basetypes')
-rw-r--r--src/core/basetypes/MCAssert.cc2
-rw-r--r--src/core/basetypes/MCIndexSet.cpp223
-rw-r--r--src/core/basetypes/MCIndexSet.h15
-rw-r--r--src/core/basetypes/MCRange.cc128
-rw-r--r--src/core/basetypes/MCRange.h12
-rw-r--r--src/core/basetypes/MCString.cc2
6 files changed, 323 insertions, 59 deletions
diff --git a/src/core/basetypes/MCAssert.cc b/src/core/basetypes/MCAssert.cc
index afe9bfd5..82b5de26 100644
--- a/src/core/basetypes/MCAssert.cc
+++ b/src/core/basetypes/MCAssert.cc
@@ -1,6 +1,7 @@
#include "MCAssert.h"
#include <stdio.h>
+#include <stdlib.h>
void mailcore::assertInteral(const char * filename, unsigned int line, int cond, const char * condString)
{
@@ -9,4 +10,5 @@ void mailcore::assertInteral(const char * filename, unsigned int line, int cond,
}
fprintf(stderr, "%s:%i: assert %s\n", filename, line, condString);
+ abort();
}
diff --git a/src/core/basetypes/MCIndexSet.cpp b/src/core/basetypes/MCIndexSet.cpp
index 7fd6cd6d..514e9d66 100644
--- a/src/core/basetypes/MCIndexSet.cpp
+++ b/src/core/basetypes/MCIndexSet.cpp
@@ -9,6 +9,9 @@
#include "MCIndexSet.h"
#include "MCString.h"
+#include "MCAssert.h"
+#include "MCRange.h"
+#include "MCLog.h"
using namespace mailcore;
@@ -47,6 +50,22 @@ IndexSet * IndexSet::indexSet()
return result;
}
+IndexSet * IndexSet::indexSetWithRange(Range range)
+{
+ IndexSet * result = new IndexSet();
+ result->autorelease();
+ result->addRange(range);
+ return result;
+}
+
+IndexSet * IndexSet::indexSetWithIndex(uint64_t idx)
+{
+ IndexSet * result = new IndexSet();
+ result->autorelease();
+ result->addIndex(idx);
+ return result;
+}
+
unsigned int IndexSet::count()
{
unsigned int total = 0;
@@ -63,13 +82,13 @@ int IndexSet::rangeIndexForIndexWithBounds(uint64_t idx, unsigned int left, unsi
Range middleRange = mRanges[middle];
if (left == right) {
- if ((idx >= middleRange.location) && (idx <= middleRange.location + middleRange.length)) {
+ if ((idx >= RangeLeftBound(middleRange)) && (idx <= RangeRightBound(middleRange))) {
return left;
}
return -1;
}
- if ((idx >= middleRange.location) && (idx <= middleRange.location + middleRange.length)) {
+ if ((idx >= RangeLeftBound(middleRange)) && (idx <= RangeRightBound(middleRange))) {
return middle;
}
if (idx < middleRange.location) {
@@ -119,6 +138,37 @@ int IndexSet::rightRangeIndexForIndex(uint64_t idx)
return rightRangeIndexForIndexWithBounds(idx, 0, mCount - 1);
}
+int IndexSet::leftRangeIndexForIndexWithBounds(uint64_t idx, unsigned int left, unsigned int right)
+{
+ unsigned int middle = (left + right) / 2;
+
+ Range middleRange = mRanges[middle];
+
+ if (left == right) {
+ if (idx <= middleRange.location) {
+ return left;
+ }
+ else {
+ return left + 1;
+ }
+ }
+
+ if (idx <= middleRange.location) {
+ return leftRangeIndexForIndexWithBounds(idx, left, middle);
+ }
+ else {
+ return leftRangeIndexForIndexWithBounds(idx, middle + 1, right);
+ }
+}
+
+int IndexSet::leftRangeIndexForIndex(uint64_t idx)
+{
+ if (mCount == 0)
+ return 0;
+
+ return leftRangeIndexForIndexWithBounds(idx, 0, mCount - 1);
+}
+
void IndexSet::addRangeIndex(unsigned int rangeIndex)
{
if (mAllocated < mCount + 1) {
@@ -136,96 +186,138 @@ void IndexSet::addRangeIndex(unsigned int rangeIndex)
for(unsigned int i = rangeIndex ; i < mCount ; i ++) {
rangesReplacement[i + 1] = mRanges[i];
}
+ mCount ++;
rangesReplacement[rangeIndex].location = 0;
rangesReplacement[rangeIndex].length = 0;
delete [] mRanges;
mRanges = rangesReplacement;
}
else {
- for(unsigned int i = mCount - 1 ; i >= rangeIndex ; i --) {
- mRanges[i + 1] = mRanges[i];
+ if (mCount > 0) {
+ for(int i = mCount - 1 ; i >= (int) rangeIndex ; i --) {
+ mRanges[i + 1] = mRanges[i];
+ }
}
+ mCount ++;
mRanges[rangeIndex].location = 0;
mRanges[rangeIndex].length = 0;
}
}
-void IndexSet::addIndex(uint64_t idx)
+void IndexSet::addRange(Range range)
{
- int leftRangeIndex;
- int rightRangeIndex;
+ int rangeIndex = leftRangeIndexForIndex(range.location);
+ addRangeIndex(rangeIndex);
+ mRanges[rangeIndex] = range;
- if (rangeIndexForIndex(idx) != -1)
+ mergeRanges(rangeIndex);
+ if (rangeIndex > 0) {
+ tryToMergeAdjacentRanges(rangeIndex - 1);
+ }
+ tryToMergeAdjacentRanges(rangeIndex);
+}
+
+void IndexSet::tryToMergeAdjacentRanges(unsigned int rangeIndex)
+{
+ if (RangeRightBound(mRanges[rangeIndex]) == UINT64_MAX)
return;
- leftRangeIndex = rangeIndexForIndex(idx - 1);
- rightRangeIndex = rangeIndexForIndex(idx + 1);
-
- if ((leftRangeIndex == -1) && (rightRangeIndex == -1)) {
- rightRangeIndex = rightRangeIndexForIndex(idx);
- addRangeIndex(rightRangeIndex);
- mRanges[rightRangeIndex].location = idx;
- mRanges[rightRangeIndex].length = 0;
+ if (RangeRightBound(mRanges[rangeIndex]) + 1 != mRanges[rangeIndex + 1].location) {
+ return;
}
- else if ((leftRangeIndex != -1) && (rightRangeIndex == -1)) {
- if (mRanges[leftRangeIndex].location + mRanges[leftRangeIndex].length + 1 == idx) {
- mRanges[leftRangeIndex].length ++;
+
+ uint64_t right = RangeRightBound(mRanges[rangeIndex + 1]);
+ removeRangeIndex(rangeIndex + 1, 1);
+ mRanges[rangeIndex].length = right - mRanges[rangeIndex].location;
+}
+
+void IndexSet::mergeRanges(unsigned int rangeIndex)
+{
+ int right = rangeIndex;
+
+ for(int i = rangeIndex ; i < mCount ; i ++) {
+ if (RangeHasIntersection(mRanges[rangeIndex], mRanges[i])) {
+ right = i;
}
- }
- else if ((leftRangeIndex == -1) && (rightRangeIndex != -1)) {
- if (mRanges[rightRangeIndex].location - 1 == idx) {
- mRanges[rightRangeIndex].location --;
- mRanges[rightRangeIndex].length ++;
+ else {
+ break;
}
}
+
+ if (right == rangeIndex)
+ return;
+
+ IndexSet * indexSet = RangeUnion(mRanges[rangeIndex], mRanges[right]);
+ MCAssert(indexSet->rangesCount() > 0);
+ Range range = indexSet->allRanges()[0];
+ removeRangeIndex(rangeIndex + 1, right - rangeIndex);
+ mRanges[rangeIndex] = range;
}
-void IndexSet::removeRangeIndex(unsigned int rangeIndex)
+void IndexSet::addIndex(uint64_t idx)
{
- for(unsigned int i = rangeIndex + 1 ; i < mCount ; i --) {
- mRanges[i - 1] = mRanges[i];
+ addRange(RangeMake(idx, 0));
+}
+
+void IndexSet::removeRangeIndex(unsigned int rangeIndex, unsigned int count)
+{
+ for(unsigned int i = rangeIndex + count ; i < mCount ; i ++) {
+ mRanges[i - count] = mRanges[i];
}
- mCount --;
+ mCount -= count;
}
-void IndexSet::removeIndex(uint64_t idx)
+void IndexSet::removeRange(Range range)
{
- int rangeIndex = rangeIndexForIndex(idx);
- if (rangeIndex == -1)
- return;
- if (idx == mRanges[rangeIndex].location) {
- mRanges[rangeIndex].location ++;
- mRanges[rangeIndex].length --;
- if (mRanges[rangeIndex].length == 0) {
- // remove range.
- removeRangeIndex(rangeIndex);
+ int left = -1;
+ int right = -1;
+ int leftRangeIndex = leftRangeIndexForIndex(range.location);
+ for(int i = leftRangeIndex ; i < mCount ; i ++) {
+ if (RangeHasIntersection(mRanges[i], range)) {
+ IndexSet * indexSet = RangeRemoveRange(mRanges[i], range);
+ if (indexSet->rangesCount() == 0) {
+ if (left == -1) {
+ left = i;
+ }
+ right = i;
+ mRanges[i] = RangeEmpty;
+ }
+ else if (indexSet->rangesCount() == 1) {
+ mRanges[i] = indexSet->allRanges()[0];
+ }
+ else {
+ MCAssert(indexSet->rangesCount() == 2);
+ addRangeIndex(i);
+ mRanges[i] = indexSet->allRanges()[0];
+ mRanges[i + 1] = indexSet->allRanges()[1];
+ }
}
- }
- else if (idx == mRanges[rangeIndex].location + mRanges[rangeIndex].length) {
- mRanges[rangeIndex].length --;
- if (mRanges[rangeIndex].length == 0) {
- // remove range.
- removeRangeIndex(rangeIndex);
+ else {
+ break;
}
}
- else {
- // split range.
- addRangeIndex(rangeIndex);
- mRanges[rangeIndex] = mRanges[rangeIndex + 1];
- uint64_t right = mRanges[rangeIndex].location + mRanges[rangeIndex].length;
- mRanges[rangeIndex].location = mRanges[rangeIndex + 1].location;
- mRanges[rangeIndex].length = idx - mRanges[rangeIndex].location;
- mRanges[rangeIndex + 1].location = idx + 1;
- mRanges[rangeIndex + 1].length = right - mRanges[rangeIndex + 1].location;
+
+ if (left != -1) {
+ removeRangeIndex(left, right - left + 1);
}
}
+void IndexSet::removeIndex(uint64_t idx)
+{
+ removeRange(RangeMake(idx, 0));
+}
+
bool IndexSet::containsIndex(uint64_t idx)
{
int rangeIndex = rangeIndexForIndex(idx);
return rangeIndex != -1;
}
+unsigned int IndexSet::rangesCount()
+{
+ return mCount;
+}
+
Range * IndexSet::allRanges()
{
return mRanges;
@@ -248,9 +340,15 @@ String * IndexSet::description()
if (i != 0) {
result->appendUTF8Format(",");
}
- result->appendUTF8Format("%llu-%llu",
- (unsigned long long) mRanges[i].location,
- (unsigned long long) (mRanges[i].location + mRanges[i].length));
+ if (mRanges[i].length == 0) {
+ result->appendUTF8Format("%llu",
+ (unsigned long long) mRanges[i].location);
+ }
+ else {
+ result->appendUTF8Format("%llu-%llu",
+ (unsigned long long) mRanges[i].location,
+ (unsigned long long) (mRanges[i].location + mRanges[i].length));
+ }
}
return result;
}
@@ -259,3 +357,16 @@ Object * IndexSet::copy()
{
return new IndexSet(this);
}
+
+void IndexSet::intersectsRange(Range range)
+{
+ uint64_t right = RangeRightBound(range);
+ if (right == UINT64_MAX) {
+ removeRange(RangeMake(0, range.location - 1));
+ }
+ else {
+ removeRange(RangeMake(0, range.location - 1));
+ removeRange(RangeMake(right, UINT64_MAX));
+ }
+}
+
diff --git a/src/core/basetypes/MCIndexSet.h b/src/core/basetypes/MCIndexSet.h
index 290b9aaa..3d9bdb6c 100644
--- a/src/core/basetypes/MCIndexSet.h
+++ b/src/core/basetypes/MCIndexSet.h
@@ -23,13 +23,20 @@ namespace mailcore {
IndexSet(IndexSet * o);
static IndexSet * indexSet();
+ static IndexSet * indexSetWithRange(Range range);
+ static IndexSet * indexSetWithIndex(uint64_t idx);
virtual unsigned int count();
virtual void addIndex(uint64_t idx);
virtual void removeIndex(uint64_t idx);
virtual bool containsIndex(uint64_t idx);
-
+
+ virtual void addRange(Range range);
+ virtual void removeRange(Range range);
+ virtual void intersectsRange(Range range);
+
virtual Range * allRanges();
+ virtual unsigned int rangesCount();
virtual void removeAllIndexes();
public: // subclass behavior
@@ -45,9 +52,13 @@ namespace mailcore {
int rangeIndexForIndex(uint64_t idx);
int rangeIndexForIndexWithBounds(uint64_t idx, unsigned int left, unsigned int right);
void addRangeIndex(unsigned int rangeIndex);
- void removeRangeIndex(unsigned int rangeIndex);
+ void removeRangeIndex(unsigned int rangeIndex, unsigned int count);
int rightRangeIndexForIndex(uint64_t idx);
int rightRangeIndexForIndexWithBounds(uint64_t idx, unsigned int left, unsigned int right);
+ int leftRangeIndexForIndex(uint64_t idx);
+ int leftRangeIndexForIndexWithBounds(uint64_t idx, unsigned int left, unsigned int right);
+ void mergeRanges(unsigned int rangeIndex);
+ void tryToMergeAdjacentRanges(unsigned int rangeIndex);
};
}
diff --git a/src/core/basetypes/MCRange.cc b/src/core/basetypes/MCRange.cc
index 48bb3d84..243c6a8f 100644
--- a/src/core/basetypes/MCRange.cc
+++ b/src/core/basetypes/MCRange.cc
@@ -1,7 +1,13 @@
#include "MCRange.h"
+#include "MCIndexSet.h"
+
+#include <sys/param.h>
+
using namespace mailcore;
+Range mailcore::RangeEmpty = {UINT64_MAX, 0};
+
Range mailcore::RangeMake(uint64_t location, uint64_t length)
{
Range range;
@@ -10,3 +16,125 @@ Range mailcore::RangeMake(uint64_t location, uint64_t length)
return range;
}
+Range mailcore::RangeIntersection(Range range1, Range range2)
+{
+ if (RangeRightBound(range2) < range1.location) {
+ return RangeEmpty;
+ }
+ else if (RangeRightBound(range1) < range2.location) {
+ return RangeEmpty;
+ }
+ else {
+ uint64_t left1;
+ uint64_t right1;
+ uint64_t left2;
+ uint64_t right2;
+ uint64_t leftResult;
+ uint64_t rightResult;
+
+ left1 = range1.location;
+ right1 = RangeRightBound(range1);
+ left2 = range2.location;
+ right2 = RangeRightBound(range2);
+
+ leftResult = MAX(left1, left2);
+ rightResult = MIN(right1, right2);
+ if (rightResult == UINT64_MAX) {
+ return RangeMake(leftResult, UINT64_MAX);
+ }
+ else {
+ return RangeMake(leftResult, rightResult - leftResult);
+ }
+ }
+}
+
+bool mailcore::RangeHasIntersection(Range range1, Range range2)
+{
+ return RangeIntersection(range1, range2).location != UINT64_MAX;
+}
+
+IndexSet * mailcore::RangeRemoveRange(Range range1, Range range2)
+{
+ uint64_t left1;
+ uint64_t right1;
+ uint64_t left2;
+ uint64_t right2;
+ IndexSet * result;
+
+ if (!RangeHasIntersection(range1, range2))
+ return IndexSet::indexSetWithRange(range1);
+
+ result = IndexSet::indexSet();
+
+ range2 = RangeIntersection(range1, range2);
+
+ left1 = range1.location;
+ right1 = RangeRightBound(range1);
+ left2 = range2.location;
+ right2 = RangeRightBound(range2);
+
+ if (left2 > left1) {
+ result->addRange(RangeMake(left1, left2 - left1 - 1));
+ }
+
+ if (right2 != UINT64_MAX) {
+ if (right1 == UINT64_MAX) {
+ result->addRange(RangeMake(right2 + 1, UINT64_MAX));
+ }
+ else {
+ if (right2 < right1) {
+ result->addRange(RangeMake(right2 + 1, right1 - (right2 + 1)));
+ }
+ }
+ }
+
+ return result;
+}
+
+IndexSet * mailcore::RangeUnion(Range range1, Range range2)
+{
+ if (!RangeHasIntersection(range1, range2)) {
+ IndexSet * result = IndexSet::indexSet();
+
+ result->addRange(range1);
+ result->addRange(range2);
+
+ return result;
+ }
+ else {
+ uint64_t left1;
+ uint64_t right1;
+ uint64_t left2;
+ uint64_t right2;
+ uint64_t resultLeft;
+ uint64_t resultRight;
+
+ left1 = range1.location;
+ right1 = RangeRightBound(range1);
+ left2 = range2.location;
+ right2 = RangeRightBound(range2);
+
+ resultLeft = MIN(left1, left2);
+ resultRight = MAX(right1, right2);
+ if (resultRight == UINT64_MAX) {
+ return IndexSet::indexSetWithRange(RangeMake(resultLeft, UINT64_MAX));
+ }
+ else {
+ return IndexSet::indexSetWithRange(RangeMake(resultLeft, resultRight - resultLeft));
+ }
+ }
+}
+
+uint64_t mailcore::RangeLeftBound(Range range)
+{
+ return range.location;
+}
+
+uint64_t mailcore::RangeRightBound(Range range)
+{
+ if (range.length == UINT64_MAX)
+ return UINT64_MAX;
+ return range.location + range.length;
+}
+
+
diff --git a/src/core/basetypes/MCRange.h b/src/core/basetypes/MCRange.h
index 7b8b497d..2687bcab 100644
--- a/src/core/basetypes/MCRange.h
+++ b/src/core/basetypes/MCRange.h
@@ -8,12 +8,24 @@
namespace mailcore {
+ class IndexSet;
+
+ // infinite length : UINT64_MAX
+ // empty range : location = UINT64_MAX
struct Range {
uint64_t location;
uint64_t length;
};
+ extern Range RangeEmpty;
+
Range RangeMake(uint64_t location, uint64_t length);
+ IndexSet * RangeRemoveRange(Range range1, Range range2);
+ IndexSet * RangeUnion(Range range1, Range range2);
+ Range RangeIntersection(Range range1, Range range2);
+ bool RangeHasIntersection(Range range1, Range range2);
+ uint64_t RangeLeftBound(Range range);
+ uint64_t RangeRightBound(Range range);
}
#endif
diff --git a/src/core/basetypes/MCString.cc b/src/core/basetypes/MCString.cc
index 75765c26..8335e5a4 100644
--- a/src/core/basetypes/MCString.cc
+++ b/src/core/basetypes/MCString.cc
@@ -1943,7 +1943,7 @@ String * String::substringWithRange(Range range)
range.length = length() - range.location;
}
- return stringWithCharacters(unicodeCharacters() + range.location, range.length);
+ return stringWithCharacters(unicodeCharacters() + range.location, (unsigned int) range.length);
}
static chash * uniquedStringHash = NULL;
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-09 19:37:02 +0000