layout/generic/nsIntervalSet.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   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
  13 nsIntervalSet::nsIntervalSet(IntervalSetAlloc aAlloc, IntervalSetFree aFree,
  14                              void* aAllocatorClosure)
  15     : mList(nullptr),
  16       mAlloc(aAlloc),
  17       mFree(aFree),
  18       mAllocatorClosure(aAllocatorClosure)
  19 {
  20     NS_ASSERTION(mAlloc && mFree, "null callback params");
  21 }
  22
  23 nsIntervalSet::~nsIntervalSet()
  24 {
  25     Interval *current = mList;
  26     while (current) {
  27         Interval *trash = current;
  28         current = current->mNext;
  29         FreeInterval(trash);
  30     }
  31 }
  32
  33 void nsIntervalSet::FreeInterval(nsIntervalSet::Interval *aInterval)
  34 {
  35     NS_ASSERTION(aInterval, "null interval");
  36
  37     aInterval->Interval::~Interval();
  38     (*mFree)(sizeof(Interval), aInterval, mAllocatorClosure);
  39 }
  40
  41 void nsIntervalSet::IncludeInterval(coord_type aBegin, coord_type aEnd)
  42 {
  43     Interval *newInterval = static_cast<Interval*>
  44                                        ((*mAlloc)(sizeof(Interval), mAllocatorClosure));
  45     if (!newInterval) {
  46         NS_NOTREACHED("allocation failure");
  47         return;
  48     }
  49     new(newInterval) Interval(aBegin, aEnd);
  50
  51     Interval **current = &mList;
  52     while (*current && (*current)->mEnd < aBegin)
  53         current = &(*current)->mNext;
  54
  55     newInterval->mNext = *current;
  56     *current = newInterval;
  57
  58     Interval *subsumed = newInterval->mNext;
  59     while (subsumed && subsumed->mBegin <= aEnd) {
  60         newInterval->mBegin = std::min(newInterval->mBegin, subsumed->mBegin);
  61         newInterval->mEnd = std::max(newInterval->mEnd, subsumed->mEnd);
  62         newInterval->mNext = subsumed->mNext;
  63         FreeInterval(subsumed);
  64         subsumed = newInterval->mNext;
  65     }
  66 }
  67
  68 bool nsIntervalSet::Intersects(coord_type aBegin, coord_type aEnd) const
  69 {
  70     Interval *current = mList;
  71     while (current && current->mBegin <= aEnd) {
  72         if (current->mEnd >= aBegin)
  73             return true;
  74         current = current->mNext;
  75     }
  76     return false;
  77 }
  78
  79 bool nsIntervalSet::Contains(coord_type aBegin, coord_type aEnd) const
  80 {
  81     Interval *current = mList;
  82     while (current && current->mBegin <= aBegin) {
  83         if (current->mEnd >= aEnd)
  84             return true;
  85         current = current->mNext;
  86     }
  87     return false;
  88 }