MutableRangeList.h [plain text]
#pragma once
#include "MutableRange.h"
#if ENABLE(CONTENT_EXTENSIONS)
namespace WebCore {
namespace ContentExtensions {
template <typename CharacterType, typename DataType, unsigned inlineCapacity = 0>
class MutableRangeList {
typedef MutableRange<CharacterType, DataType> TypedMutableRange;
public:
class ConstIterator {
public:
const MutableRangeList& rangeList;
uint32_t index;
bool atEnd;
const TypedMutableRange& operator*() const { return rangeList.m_ranges[index]; }
const TypedMutableRange* operator->() const { return &rangeList.m_ranges[index]; }
CharacterType first() const { return rangeList.m_ranges[index].first; }
CharacterType last() const { return rangeList.m_ranges[index].last; }
CharacterType data() const { return rangeList.m_ranges[index].data; }
bool operator==(const ConstIterator& other) const
{
ASSERT(&rangeList == &other.rangeList);
if (atEnd || other.atEnd)
return atEnd == other.atEnd;
return index == other.index;
}
bool operator!=(const ConstIterator& other) const { return !(*this == other); }
ConstIterator& operator++()
{
ASSERT(!atEnd);
index = rangeList.m_ranges[index].nextRangeIndex;
if (!index)
atEnd = true;
return *this;
}
};
ConstIterator begin() const { return ConstIterator { *this, 0, m_ranges.isEmpty() }; }
ConstIterator end() const { return ConstIterator { *this, 0, true }; }
uint32_t appendRange(uint32_t lastRangeIndex, CharacterType first, CharacterType last, const DataType& data)
{
uint32_t newRangeIndex = m_ranges.size();
m_ranges.append(TypedMutableRange(data, 0, first, last));
if (!newRangeIndex)
return 0;
ASSERT(!m_ranges[lastRangeIndex].nextRangeIndex);
ASSERT(m_ranges[lastRangeIndex].last < first);
m_ranges[lastRangeIndex].nextRangeIndex = newRangeIndex;
return newRangeIndex;
}
template <typename RangeIterator, typename DataConverter>
void extend(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
{
if (otherIterator == otherEnd)
return;
if (m_ranges.isEmpty()) {
initializeFrom(otherIterator, otherEnd, dataConverter);
return;
}
bool reachedSelfEnd = false;
uint32_t lastSelfRangeIndex = 0;
uint32_t selfRangeIndex = 0;
auto otherRangeOffset = otherIterator.first(); otherRangeOffset = 0;
do {
TypedMutableRange* activeSelfRange = &m_ranges[selfRangeIndex];
if (activeSelfRange->last < otherIterator.first() + otherRangeOffset) {
lastSelfRangeIndex = selfRangeIndex;
selfRangeIndex = activeSelfRange->nextRangeIndex;
reachedSelfEnd = !selfRangeIndex;
continue;
}
if (otherIterator.last() < activeSelfRange->first) {
insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
++otherIterator;
otherRangeOffset = 0;
continue;
}
if (activeSelfRange->first < otherIterator.first() + otherRangeOffset) {
DataType copiedData = activeSelfRange->data;
CharacterType newRangeFirstCharacter = activeSelfRange->first;
activeSelfRange->first = otherIterator.first() + otherRangeOffset;
insertBetween(lastSelfRangeIndex, selfRangeIndex, newRangeFirstCharacter, otherIterator.first() + otherRangeOffset - 1, WTFMove(copiedData));
activeSelfRange = &m_ranges[selfRangeIndex];
} else if (otherIterator.first() + otherRangeOffset < activeSelfRange->first) {
insertBetween(lastSelfRangeIndex, selfRangeIndex, otherIterator.first() + otherRangeOffset, activeSelfRange->first - 1, dataConverter.convert(otherIterator.data()));
activeSelfRange = &m_ranges[selfRangeIndex];
ASSERT_WITH_MESSAGE(otherRangeOffset < activeSelfRange->first - otherIterator.first(), "The offset must move forward or we could get stuck on this operation.");
otherRangeOffset = activeSelfRange->first - otherIterator.first();
}
if (activeSelfRange->last == otherIterator.last()) {
dataConverter.extend(activeSelfRange->data, otherIterator.data());
lastSelfRangeIndex = selfRangeIndex;
selfRangeIndex = activeSelfRange->nextRangeIndex;
reachedSelfEnd = !selfRangeIndex;
++otherIterator;
otherRangeOffset = 0;
continue;
}
if (activeSelfRange->last > otherIterator.last()) {
CharacterType combinedPartStart = activeSelfRange->first;
activeSelfRange->first = otherIterator.last() + 1;
DataType combinedData = activeSelfRange->data;
dataConverter.extend(combinedData, otherIterator.data());
insertBetween(lastSelfRangeIndex, selfRangeIndex, combinedPartStart, otherIterator.last(), WTFMove(combinedData));
++otherIterator;
otherRangeOffset = 0;
continue;
}
ASSERT(otherIterator.last() > activeSelfRange->last);
dataConverter.extend(activeSelfRange->data, otherIterator.data());
otherRangeOffset = activeSelfRange->last - otherIterator.first() + 1;
lastSelfRangeIndex = selfRangeIndex;
selfRangeIndex = activeSelfRange->nextRangeIndex;
reachedSelfEnd = !selfRangeIndex;
} while (!reachedSelfEnd && otherIterator != otherEnd);
while (otherIterator != otherEnd) {
lastSelfRangeIndex = appendRange(lastSelfRangeIndex, otherIterator.first() + otherRangeOffset, otherIterator.last(), dataConverter.convert(otherIterator.data()));
otherRangeOffset = 0;
++otherIterator;
}
}
unsigned size() const
{
return m_ranges.size();
}
bool isEmpty() const
{
return m_ranges.isEmpty();
}
void clear()
{
m_ranges.clear();
}
#if CONTENT_EXTENSIONS_STATE_MACHINE_DEBUGGING
void debugPrint() const
{
for (const TypedMutableRange& range : *this)
WTFLogAlways(" %d-%d", range.first, range.last);
}
#endif
Vector<MutableRange<CharacterType, DataType>, inlineCapacity, ContentExtensionsOverflowHandler> m_ranges;
private:
void insertBetween(uint32_t& leftRangeIndex, uint32_t& rightRangeIndex, CharacterType first, CharacterType last, DataType&& data)
{
ASSERT(m_ranges[rightRangeIndex].first > last);
if (!rightRangeIndex) {
uint32_t movedRangeIndex = m_ranges.size();
m_ranges.append(WTFMove(m_ranges.first()));
m_ranges[0] = TypedMutableRange(WTFMove(data), movedRangeIndex, first, last);
leftRangeIndex = 0;
rightRangeIndex = movedRangeIndex;
return;
}
ASSERT(m_ranges[leftRangeIndex].nextRangeIndex == rightRangeIndex);
ASSERT(m_ranges[leftRangeIndex].last < first);
uint32_t newRangeIndex = m_ranges.size();
m_ranges.append(TypedMutableRange(WTFMove(data), rightRangeIndex, first, last));
m_ranges[leftRangeIndex].nextRangeIndex = newRangeIndex;
leftRangeIndex = newRangeIndex;
}
template <typename RangeIterator, typename DataConverter>
void initializeFrom(RangeIterator otherIterator, RangeIterator otherEnd, DataConverter dataConverter)
{
ASSERT_WITH_MESSAGE(otherIterator != otherEnd, "We should never do anything when extending with a null range.");
ASSERT_WITH_MESSAGE(m_ranges.isEmpty(), "This code does not handle splitting, it can only be used on empty RangeList.");
uint32_t loopCounter = 0;
do {
m_ranges.append(TypedMutableRange(dataConverter.convert(otherIterator.data()),
loopCounter + 1,
otherIterator.first(),
otherIterator.last()));
++loopCounter;
++otherIterator;
} while (otherIterator != otherEnd);
if (!m_ranges.isEmpty())
m_ranges.last().nextRangeIndex = 0;
}
};
} }
#endif // ENABLE(CONTENT_EXTENSIONS)