layout/generic/nsIntervalSet.cpp@b8a032363ba2 (annotated)
layout/generic/nsIntervalSet.cpp
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
| michael@0 | 1 | /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ |
| michael@0 | 2 | // vim:cindent:ts=8:et:sw=4: |
| michael@0 | 3 | /* This Source Code Form is subject to the terms of the Mozilla Public |
| michael@0 | 4 | * License, v. 2.0. If a copy of the MPL was not distributed with this |
| michael@0 | 5 | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
| michael@0 | 6 | |
| michael@0 | 7 | /* a set of ranges on a number-line */ |
| michael@0 | 8 | |
| michael@0 | 9 | #include "nsIntervalSet.h" |
| michael@0 | 10 | #include <new> |
| michael@0 | 11 | #include <algorithm> |
| michael@0 | 12 | |
| michael@0 | 13 | nsIntervalSet::nsIntervalSet(IntervalSetAlloc aAlloc, IntervalSetFree aFree, |
| michael@0 | 14 | void* aAllocatorClosure) |
| michael@0 | 15 | : mList(nullptr), |
| michael@0 | 16 | mAlloc(aAlloc), |
| michael@0 | 17 | mFree(aFree), |
| michael@0 | 18 | mAllocatorClosure(aAllocatorClosure) |
| michael@0 | 19 | { |
| michael@0 | 20 | NS_ASSERTION(mAlloc && mFree, "null callback params"); |
| michael@0 | 21 | } |
| michael@0 | 22 | |
| michael@0 | 23 | nsIntervalSet::~nsIntervalSet() |
| michael@0 | 24 | { |
| michael@0 | 25 | Interval *current = mList; |
| michael@0 | 26 | while (current) { |
| michael@0 | 27 | Interval *trash = current; |
| michael@0 | 28 | current = current->mNext; |
| michael@0 | 29 | FreeInterval(trash); |
| michael@0 | 30 | } |
| michael@0 | 31 | } |
| michael@0 | 32 | |
| michael@0 | 33 | void nsIntervalSet::FreeInterval(nsIntervalSet::Interval *aInterval) |
| michael@0 | 34 | { |
| michael@0 | 35 | NS_ASSERTION(aInterval, "null interval"); |
| michael@0 | 36 | |
| michael@0 | 37 | aInterval->Interval::~Interval(); |
| michael@0 | 38 | (*mFree)(sizeof(Interval), aInterval, mAllocatorClosure); |
| michael@0 | 39 | } |
| michael@0 | 40 | |
| michael@0 | 41 | void nsIntervalSet::IncludeInterval(coord_type aBegin, coord_type aEnd) |
| michael@0 | 42 | { |
| michael@0 | 43 | Interval *newInterval = static_cast<Interval*> |
| michael@0 | 44 | ((*mAlloc)(sizeof(Interval), mAllocatorClosure)); |
| michael@0 | 45 | if (!newInterval) { |
| michael@0 | 46 | NS_NOTREACHED("allocation failure"); |
| michael@0 | 47 | return; |
| michael@0 | 48 | } |
| michael@0 | 49 | new(newInterval) Interval(aBegin, aEnd); |
| michael@0 | 50 | |
| michael@0 | 51 | Interval **current = &mList; |
| michael@0 | 52 | while (*current && (*current)->mEnd < aBegin) |
| michael@0 | 53 | current = &(*current)->mNext; |
| michael@0 | 54 | |
| michael@0 | 55 | newInterval->mNext = *current; |
| michael@0 | 56 | *current = newInterval; |
| michael@0 | 57 | |
| michael@0 | 58 | Interval *subsumed = newInterval->mNext; |
| michael@0 | 59 | while (subsumed && subsumed->mBegin <= aEnd) { |
| michael@0 | 60 | newInterval->mBegin = std::min(newInterval->mBegin, subsumed->mBegin); |
| michael@0 | 61 | newInterval->mEnd = std::max(newInterval->mEnd, subsumed->mEnd); |
| michael@0 | 62 | newInterval->mNext = subsumed->mNext; |
| michael@0 | 63 | FreeInterval(subsumed); |
| michael@0 | 64 | subsumed = newInterval->mNext; |
| michael@0 | 65 | } |
| michael@0 | 66 | } |
| michael@0 | 67 | |
| michael@0 | 68 | bool nsIntervalSet::Intersects(coord_type aBegin, coord_type aEnd) const |
| michael@0 | 69 | { |
| michael@0 | 70 | Interval *current = mList; |
| michael@0 | 71 | while (current && current->mBegin <= aEnd) { |
| michael@0 | 72 | if (current->mEnd >= aBegin) |
| michael@0 | 73 | return true; |
| michael@0 | 74 | current = current->mNext; |
| michael@0 | 75 | } |
| michael@0 | 76 | return false; |
| michael@0 | 77 | } |
| michael@0 | 78 | |
| michael@0 | 79 | bool nsIntervalSet::Contains(coord_type aBegin, coord_type aEnd) const |
| michael@0 | 80 | { |
| michael@0 | 81 | Interval *current = mList; |
| michael@0 | 82 | while (current && current->mBegin <= aBegin) { |
| michael@0 | 83 | if (current->mEnd >= aEnd) |
| michael@0 | 84 | return true; |
| michael@0 | 85 | current = current->mNext; |
| michael@0 | 86 | } |
| michael@0 | 87 | return false; |
| michael@0 | 88 | } |
