1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 // vim:cindent:ts=8:et:sw=4:
3 /* This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 /* a set of ranges on a number-line */
8
9 #include "nsIntervalSet.h"
10 #include <new>
11 #include <algorithm>
12 #include "mozilla/PresShell.h" // for allocation
13
14 using namespace mozilla;
15
nsIntervalSet(PresShell * aPresShell)16 nsIntervalSet::nsIntervalSet(PresShell* aPresShell)
17 : mList(nullptr), mPresShell(aPresShell) {}
18
~nsIntervalSet()19 nsIntervalSet::~nsIntervalSet() {
20 Interval* current = mList;
21 while (current) {
22 Interval* trash = current;
23 current = current->mNext;
24 FreeInterval(trash);
25 }
26 }
27
AllocateInterval()28 void* nsIntervalSet::AllocateInterval() {
29 return mPresShell->AllocateByObjectID(eArenaObjectID_nsIntervalSet_Interval,
30 sizeof(Interval));
31 }
32
FreeInterval(nsIntervalSet::Interval * aInterval)33 void nsIntervalSet::FreeInterval(nsIntervalSet::Interval* aInterval) {
34 NS_ASSERTION(aInterval, "null interval");
35
36 aInterval->Interval::~Interval();
37 mPresShell->FreeByObjectID(eArenaObjectID_nsIntervalSet_Interval, aInterval);
38 }
39
IncludeInterval(coord_type aBegin,coord_type aEnd)40 void nsIntervalSet::IncludeInterval(coord_type aBegin, coord_type aEnd) {
41 auto newInterval = static_cast<Interval*>(AllocateInterval());
42 new (newInterval) Interval(aBegin, aEnd);
43
44 Interval** current = &mList;
45 while (*current && (*current)->mEnd < aBegin) current = &(*current)->mNext;
46
47 newInterval->mNext = *current;
48 *current = newInterval;
49
50 Interval* subsumed = newInterval->mNext;
51 while (subsumed && subsumed->mBegin <= aEnd) {
52 newInterval->mBegin = std::min(newInterval->mBegin, subsumed->mBegin);
53 newInterval->mEnd = std::max(newInterval->mEnd, subsumed->mEnd);
54 newInterval->mNext = subsumed->mNext;
55 FreeInterval(subsumed);
56 subsumed = newInterval->mNext;
57 }
58 }
59
Intersects(coord_type aBegin,coord_type aEnd) const60 bool nsIntervalSet::Intersects(coord_type aBegin, coord_type aEnd) const {
61 Interval* current = mList;
62 while (current && current->mBegin <= aEnd) {
63 if (current->mEnd >= aBegin) return true;
64 current = current->mNext;
65 }
66 return false;
67 }
68
Contains(coord_type aBegin,coord_type aEnd) const69 bool nsIntervalSet::Contains(coord_type aBegin, coord_type aEnd) const {
70 Interval* current = mList;
71 while (current && current->mBegin <= aBegin) {
72 if (current->mEnd >= aEnd) return true;
73 current = current->mNext;
74 }
75 return false;
76 }
77