//* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ /* This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #include "ChunkSet.h" namespace mozilla { namespace safebrowsing { const size_t ChunkSet::IO_BUFFER_SIZE; nsresult ChunkSet::Serialize(nsACString& aChunkStr) { aChunkStr.Truncate(); for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) { if (range != mRanges.begin()) { aChunkStr.Append(','); } aChunkStr.AppendInt((int32_t)range->Begin()); if (range->Begin() != range->End()) { aChunkStr.Append('-'); aChunkStr.AppendInt((int32_t)range->End()); } } return NS_OK; } nsresult ChunkSet::Set(uint32_t aChunk) { if (!Has(aChunk)) { Range chunkRange(aChunk, aChunk); if (mRanges.Length() == 0) { if (!mRanges.AppendElement(chunkRange, fallible)) { return NS_ERROR_OUT_OF_MEMORY; } return NS_OK; } if (mRanges.LastElement().Precedes(chunkRange)) { mRanges.LastElement().End(aChunk); } else if (chunkRange.Precedes(mRanges[0])) { mRanges[0].Begin(aChunk); } else { ChunkSet tmp; if (!tmp.mRanges.AppendElement(chunkRange, fallible)) { return NS_ERROR_OUT_OF_MEMORY; } return Merge(tmp); } } return NS_OK; } bool ChunkSet::Has(uint32_t aChunk) const { size_t idx; return BinarySearchIf(mRanges, 0, mRanges.Length(), Range::IntersectionComparator(Range(aChunk, aChunk)), &idx); // IntersectionComparator works because we create a // single-chunk range. } nsresult ChunkSet::Merge(const ChunkSet& aOther) { size_t oldLen = mRanges.Length(); for (const Range* mergeRange = aOther.mRanges.begin(); mergeRange != aOther.mRanges.end(); mergeRange++) { if (!HasSubrange(*mergeRange)) { if (!mRanges.InsertElementSorted(*mergeRange, fallible)) { return NS_ERROR_OUT_OF_MEMORY; } } } if (oldLen < mRanges.Length()) { for (size_t i = 1; i < mRanges.Length(); i++) { while (mRanges[i - 1].FoldLeft(mRanges[i])) { mRanges.RemoveElementAt(i); if (i == mRanges.Length()) { return NS_OK; } } } } return NS_OK; } uint32_t ChunkSet::Length() const { uint32_t len = 0; for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) { len += range->Length(); } return len; } nsresult ChunkSet::Remove(const ChunkSet& aOther) { for (const Range* removalRange = aOther.mRanges.begin(); removalRange != aOther.mRanges.end(); removalRange++) { if (mRanges.Length() == 0) { return NS_OK; } if (mRanges.LastElement().End() < removalRange->Begin() || aOther.mRanges.LastElement().End() < mRanges[0].Begin()) { return NS_OK; } size_t intersectionIdx; while (BinarySearchIf(mRanges, 0, mRanges.Length(), Range::IntersectionComparator(*removalRange), &intersectionIdx)) { ChunkSet remains; nsresult rv = mRanges[intersectionIdx].Remove(*removalRange, remains); if (NS_FAILED(rv)) { return rv; } mRanges.RemoveElementAt(intersectionIdx); if (!mRanges.InsertElementsAt(intersectionIdx, remains.mRanges, fallible)) { return NS_ERROR_OUT_OF_MEMORY; } } } return NS_OK; } void ChunkSet::Clear() { mRanges.Clear(); } nsresult ChunkSet::Write(nsIOutputStream* aOut) { nsTArray<uint32_t> chunks(IO_BUFFER_SIZE); for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) { for (uint32_t chunk = range->Begin(); chunk <= range->End(); chunk++) { chunks.AppendElement(chunk); if (chunks.Length() == chunks.Capacity()) { nsresult rv = WriteTArray(aOut, chunks); if (NS_FAILED(rv)) { return rv; } chunks.Clear(); } } } nsresult rv = WriteTArray(aOut, chunks); if (NS_FAILED(rv)) { return rv; } return NS_OK; } nsresult ChunkSet::Read(nsIInputStream* aIn, uint32_t aNumElements) { nsTArray<uint32_t> chunks(IO_BUFFER_SIZE); while (aNumElements != 0) { chunks.Clear(); uint32_t numToRead = aNumElements > IO_BUFFER_SIZE ? IO_BUFFER_SIZE : aNumElements; nsresult rv = ReadTArray(aIn, &chunks, numToRead); if (NS_FAILED(rv)) { return rv; } aNumElements -= numToRead; for (const uint32_t* c = chunks.begin(); c != chunks.end(); c++) { rv = Set(*c); if (NS_FAILED(rv)) { return rv; } } } return NS_OK; } bool ChunkSet::HasSubrange(const Range& aSubrange) const { for (const Range* range = mRanges.begin(); range != mRanges.end(); range++) { if (range->Contains(aSubrange)) { return true; } else if (!(aSubrange.Begin() > range->End() || range->Begin() > aSubrange.End())) { // In this case, aSubrange overlaps this range but is not a subrange. // because the ChunkSet implementation ensures that there are no // overlapping ranges, this means that aSubrange cannot be a subrange of // any of the following ranges return false; } } return false; } uint32_t ChunkSet::Range::Length() const { return mEnd - mBegin + 1; } nsresult ChunkSet::Range::Remove(const Range& aRange, ChunkSet& aRemainderSet) const { if (mBegin < aRange.mBegin && aRange.mBegin <= mEnd) { // aRange overlaps & follows this range Range range(mBegin, aRange.mBegin - 1); if (!aRemainderSet.mRanges.AppendElement(range, fallible)) { return NS_ERROR_OUT_OF_MEMORY; } } if (mBegin <= aRange.mEnd && aRange.mEnd < mEnd) { // aRange overlaps & precedes this range Range range(aRange.mEnd + 1, mEnd); if (!aRemainderSet.mRanges.AppendElement(range, fallible)) { return NS_ERROR_OUT_OF_MEMORY; } } return NS_OK; } bool ChunkSet::Range::FoldLeft(const Range& aRange) { if (Contains(aRange)) { return true; } else if (Precedes(aRange) || (mBegin <= aRange.mBegin && aRange.mBegin <= mEnd)) { mEnd = aRange.mEnd; return true; } return false; } } // namespace safebrowsing } // namespace mozilla