Line data Source code
1 : //* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #include "ChunkSet.h"
7 :
8 : namespace mozilla {
9 : namespace safebrowsing {
10 :
11 : const size_t ChunkSet::IO_BUFFER_SIZE;
12 :
13 : nsresult
14 12 : ChunkSet::Serialize(nsACString& aChunkStr)
15 : {
16 12 : aChunkStr.Truncate();
17 24 : for (const Range& range : mRanges) {
18 12 : if (&range != &mRanges[0]) {
19 0 : aChunkStr.Append(',');
20 : }
21 :
22 12 : aChunkStr.AppendInt((int32_t)range.Begin());
23 12 : if (range.Begin() != range.End()) {
24 2 : aChunkStr.Append('-');
25 2 : aChunkStr.AppendInt((int32_t)range.End());
26 : }
27 : }
28 :
29 12 : return NS_OK;
30 : }
31 :
32 : nsresult
33 48 : ChunkSet::Set(uint32_t aChunk)
34 : {
35 48 : if (!Has(aChunk)) {
36 48 : Range chunkRange(aChunk, aChunk);
37 :
38 48 : if (mRanges.Length() == 0) {
39 42 : if (!mRanges.AppendElement(chunkRange, fallible)) {
40 42 : return NS_ERROR_OUT_OF_MEMORY;
41 : }
42 42 : return NS_OK;
43 : }
44 :
45 6 : if (mRanges.LastElement().Precedes(chunkRange)) {
46 6 : mRanges.LastElement().End(aChunk);
47 0 : } else if (chunkRange.Precedes(mRanges[0])) {
48 0 : mRanges[0].Begin(aChunk);
49 : } else {
50 0 : ChunkSet tmp;
51 0 : if (!tmp.mRanges.AppendElement(chunkRange, fallible)) {
52 0 : return NS_ERROR_OUT_OF_MEMORY;
53 : }
54 :
55 0 : return Merge(tmp);
56 : }
57 : }
58 :
59 6 : return NS_OK;
60 : }
61 :
62 : bool
63 62 : ChunkSet::Has(uint32_t aChunk) const
64 : {
65 : size_t idx;
66 62 : return BinarySearchIf(mRanges, 0, mRanges.Length(),
67 124 : Range::IntersectionComparator(Range(aChunk, aChunk)),
68 124 : &idx);
69 : // IntersectionComparator works because we create a
70 : // single-chunk range.
71 : }
72 :
73 : nsresult
74 36 : ChunkSet::Merge(const ChunkSet& aOther)
75 : {
76 36 : size_t oldLen = mRanges.Length();
77 :
78 54 : for (const Range& mergeRange : aOther.mRanges) {
79 18 : if (!HasSubrange(mergeRange)) {
80 12 : if (!mRanges.InsertElementSorted(mergeRange, fallible)) {
81 0 : return NS_ERROR_OUT_OF_MEMORY;
82 : }
83 : }
84 : }
85 :
86 36 : if (oldLen < mRanges.Length()) {
87 12 : for (size_t i = 1; i < mRanges.Length(); i++) {
88 1 : while (mRanges[i - 1].FoldLeft(mRanges[i])) {
89 1 : mRanges.RemoveElementAt(i);
90 :
91 1 : if (i == mRanges.Length()) {
92 1 : return NS_OK;
93 : }
94 : }
95 : }
96 : }
97 :
98 35 : return NS_OK;
99 : }
100 :
101 : uint32_t
102 182 : ChunkSet::Length() const
103 : {
104 182 : uint32_t len = 0;
105 284 : for (const Range& range : mRanges) {
106 102 : len += range.Length();
107 : }
108 :
109 182 : return len;
110 : }
111 :
112 : nsresult
113 12 : ChunkSet::Remove(const ChunkSet& aOther)
114 : {
115 18 : for (const Range& removalRange : aOther.mRanges) {
116 :
117 6 : if (mRanges.Length() == 0) {
118 0 : return NS_OK;
119 : }
120 :
121 12 : if (mRanges.LastElement().End() < removalRange.Begin() ||
122 6 : aOther.mRanges.LastElement().End() < mRanges[0].Begin()) {
123 0 : return NS_OK;
124 : }
125 :
126 : size_t intersectionIdx;
127 30 : while (BinarySearchIf(mRanges, 0, mRanges.Length(),
128 24 : Range::IntersectionComparator(removalRange), &intersectionIdx)) {
129 :
130 12 : ChunkSet remains;
131 6 : nsresult rv = mRanges[intersectionIdx].Remove(removalRange, remains);
132 :
133 6 : if (NS_FAILED(rv)) {
134 0 : return rv;
135 : }
136 :
137 6 : mRanges.RemoveElementAt(intersectionIdx);
138 6 : if (!mRanges.InsertElementsAt(intersectionIdx, remains.mRanges,
139 : fallible)) {
140 0 : return NS_ERROR_OUT_OF_MEMORY;
141 : }
142 : }
143 : }
144 :
145 12 : return NS_OK;
146 : }
147 :
148 : void
149 12 : ChunkSet::Clear()
150 : {
151 12 : mRanges.Clear();
152 12 : }
153 :
154 : nsresult
155 12 : ChunkSet::Write(nsIOutputStream* aOut)
156 : {
157 24 : nsTArray<uint32_t> chunks(IO_BUFFER_SIZE);
158 :
159 18 : for (const Range& range : mRanges) {
160 13 : for (uint32_t chunk = range.Begin(); chunk <= range.End(); chunk++) {
161 7 : chunks.AppendElement(chunk);
162 :
163 7 : if (chunks.Length() == chunks.Capacity()) {
164 0 : nsresult rv = WriteTArray(aOut, chunks);
165 :
166 0 : if (NS_FAILED(rv)) {
167 0 : return rv;
168 : }
169 :
170 0 : chunks.Clear();
171 : }
172 : }
173 : }
174 :
175 12 : nsresult rv = WriteTArray(aOut, chunks);
176 :
177 12 : if (NS_FAILED(rv)) {
178 0 : return rv;
179 : }
180 :
181 12 : return NS_OK;
182 : }
183 :
184 : nsresult
185 60 : ChunkSet::Read(nsIInputStream* aIn, uint32_t aNumElements)
186 : {
187 120 : nsTArray<uint32_t> chunks(IO_BUFFER_SIZE);
188 :
189 120 : while (aNumElements != 0) {
190 30 : chunks.Clear();
191 :
192 30 : uint32_t numToRead = aNumElements > IO_BUFFER_SIZE ? IO_BUFFER_SIZE : aNumElements;
193 :
194 30 : nsresult rv = ReadTArray(aIn, &chunks, numToRead);
195 :
196 30 : if (NS_FAILED(rv)) {
197 0 : return rv;
198 : }
199 :
200 30 : aNumElements -= numToRead;
201 :
202 65 : for (uint32_t c : chunks) {
203 35 : rv = Set(c);
204 :
205 35 : if (NS_FAILED(rv)) {
206 0 : return rv;
207 : }
208 : }
209 : }
210 :
211 60 : return NS_OK;
212 : }
213 :
214 : bool
215 18 : ChunkSet::HasSubrange(const Range& aSubrange) const
216 : {
217 18 : for (const Range& range : mRanges) {
218 7 : if (range.Contains(aSubrange)) {
219 13 : return true;
220 2 : } else if (!(aSubrange.Begin() > range.End() ||
221 1 : range.Begin() > aSubrange.End())) {
222 : // In this case, aSubrange overlaps this range but is not a subrange.
223 : // because the ChunkSet implementation ensures that there are no
224 : // overlapping ranges, this means that aSubrange cannot be a subrange of
225 : // any of the following ranges
226 1 : return false;
227 : }
228 : }
229 :
230 11 : return false;
231 : }
232 :
233 : uint32_t
234 102 : ChunkSet::Range::Length() const
235 : {
236 102 : return mEnd - mBegin + 1;
237 : }
238 :
239 : nsresult
240 6 : ChunkSet::Range::Remove(const Range& aRange, ChunkSet& aRemainderSet) const
241 : {
242 6 : if (mBegin < aRange.mBegin && aRange.mBegin <= mEnd) {
243 : // aRange overlaps & follows this range
244 1 : Range range(mBegin, aRange.mBegin - 1);
245 1 : if (!aRemainderSet.mRanges.AppendElement(range, fallible)) {
246 0 : return NS_ERROR_OUT_OF_MEMORY;
247 : }
248 : }
249 :
250 6 : if (mBegin <= aRange.mEnd && aRange.mEnd < mEnd) {
251 : // aRange overlaps & precedes this range
252 0 : Range range(aRange.mEnd + 1, mEnd);
253 0 : if (!aRemainderSet.mRanges.AppendElement(range, fallible)) {
254 0 : return NS_ERROR_OUT_OF_MEMORY;
255 : }
256 : }
257 :
258 6 : return NS_OK;
259 : }
260 :
261 : bool
262 1 : ChunkSet::Range::FoldLeft(const Range& aRange)
263 : {
264 1 : if (Contains(aRange)) {
265 0 : return true;
266 3 : } else if (Precedes(aRange) ||
267 2 : (mBegin <= aRange.mBegin && aRange.mBegin <= mEnd)) {
268 1 : mEnd = aRange.mEnd;
269 1 : return true;
270 : }
271 :
272 0 : return false;
273 : }
274 :
275 : } // namespace safebrowsing
276 : } // namespace mozilla
|
