Changeset 254483 in webkit


Ignore:
Timestamp:
Jan 13, 2020 7:18:09 PM (4 years ago)
Author:
Darin Adler
Message:

Remove the "needsFullOrderingComparisons" feature from PODRedBlackTree
​https://bugs.webkit.org/show_bug.cgi?id=205238

Reviewed by Sam Weinig.

  • html/HTMLMediaElement.cpp:

(WebCore::HTMLMediaElement::updateActiveTextTrackCues): Simplified code and
eliminate uses of the createInterval function to construct PODInterval objects.
(WebCore::HTMLMediaElement::textTrackAddCue): Ditto.
(WebCore::HTMLMediaElement::textTrackRemoveCue): Ditto.

  • html/HTMLMediaElement.h: Removed unnecessary include of PODInterval.h.
  • html/shadow/MediaControlElements.cpp: Added include of PODInterval.h.
  • platform/PODInterval.h: Changed operator< to compare low, high, and user

data, not just low and high so it's consistent with operator== and we
can use it to search a tree. Added a partial specialization for WeakPtr
since a WeakPtr's value can change (to null) so it can't be used for
ordering and equality checks; luckily the clients don't need to use it
that way; they build an interval tree but never search for anything or
remove anything from the tree.

  • platform/PODIntervalTree.h: Make the search adapter used to find overlaps

a member class instead of a top level class template and simplified it a bit.
Removed the unneeded createInterval function. Stopped passing true for
"needsFullOrderingComparisons" since it's not needed any more due to the
changes to PODInterval.

  • platform/PODRedBlackTree.h: Removed the "needsFullOrderingComparisons"

template argument for the PODRedBlackTree class template.
(WebCore::PODRedBlackTree::Node::moveDataFrom): Take a reference (why not,
since this always requires a non-null pointer).
(WebCore::PODRedBlackTree::updateNode): Ditto.
(WebCore::PODRedBlackTree::treeSearch const): Merged the three search
functions into a single one since we don't need the peculiar
"full comparisons" mode.
(WebCore::PODRedBlackTree::propagateUpdates): Simplified logic to remove
the boolean local variable.
(WebCore::PODRedBlackTree::dumpSubtree const): Renamed from dumpFromNode
since the comment said "dumps the subtree". Also removed the comment now
that the function name says what it said.

  • rendering/FloatingObjects.h: Removed unnecessary include of PODInterval.h.
Location:
trunk/Source/WebCore
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r254481 r254483  
     12019-12-14  Darin Adler  <darin@apple.com>
     2
     3        Remove the "needsFullOrderingComparisons" feature from PODRedBlackTree
     4        https://bugs.webkit.org/show_bug.cgi?id=205238
     5
     6        Reviewed by Sam Weinig.
     7
     8        * html/HTMLMediaElement.cpp:
     9        (WebCore::HTMLMediaElement::updateActiveTextTrackCues): Simplified code and
     10        eliminate uses of the createInterval function to construct PODInterval objects.
     11        (WebCore::HTMLMediaElement::textTrackAddCue): Ditto.
     12        (WebCore::HTMLMediaElement::textTrackRemoveCue): Ditto.
     13
     14        * html/HTMLMediaElement.h: Removed unnecessary include of PODInterval.h.
     15
     16        * html/shadow/MediaControlElements.cpp: Added include of PODInterval.h.
     17
     18        * platform/PODInterval.h: Changed operator< to compare low, high, and user
     19        data, not just low and high so it's consistent with operator== and we
     20        can use it to search a tree. Added a partial specialization for WeakPtr
     21        since a WeakPtr's value can change (to null) so it can't be used for
     22        ordering and equality checks; luckily the clients don't need to use it
     23        that way; they build an interval tree but never search for anything or
     24        remove anything from the tree.
     25
     26        * platform/PODIntervalTree.h: Make the search adapter used to find overlaps
     27        a member class instead of a top level class template and simplified it a bit.
     28        Removed the unneeded createInterval function. Stopped passing true for
     29        "needsFullOrderingComparisons" since it's not needed any more due to the
     30        changes to PODInterval.
     31
     32        * platform/PODRedBlackTree.h: Removed the "needsFullOrderingComparisons"
     33        template argument for the PODRedBlackTree class template.
     34        (WebCore::PODRedBlackTree::Node::moveDataFrom): Take a reference (why not,
     35        since this always requires a non-null pointer).
     36        (WebCore::PODRedBlackTree::updateNode): Ditto.
     37        (WebCore::PODRedBlackTree::treeSearch const): Merged the three search
     38        functions into a single one since we don't need the peculiar
     39        "full comparisons" mode.
     40        (WebCore::PODRedBlackTree::propagateUpdates): Simplified logic to remove
     41        the boolean local variable.
     42        (WebCore::PODRedBlackTree::dumpSubtree const): Renamed from dumpFromNode
     43        since the comment said "dumps the subtree". Also removed the comment now
     44        that the function name says what it said.
     45
     46        * rendering/FloatingObjects.h: Removed unnecessary include of PODInterval.h.
     47
    1482020-01-13  Justin Fan  <justin_fan@apple.com>
    249

  • trunk/Source/WebCore/html/HTMLMediaElement.cpp

    r253923 r254483  
    16361636    // The user agent must synchronously unset [the text track cue active] flag
    16371637    // whenever ... the media element's readyState is changed back to HAVE_NOTHING.
    1638     auto movieTimeInterval = m_cueData->cueTree.createInterval(movieTime, movieTime);
    16391638    if (m_readyState != HAVE_NOTHING && m_player) {
    1640         currentCues = m_cueData->cueTree.allOverlaps(movieTimeInterval);
     1639        currentCues = m_cueData->cueTree.allOverlaps({ movieTime, movieTime });
    16411640        if (currentCues.size() > 1)
    16421641            std::sort(currentCues.begin(), currentCues.end(), &compareCueInterval);
    … …  
    17081707        nextInterestingTime = nearestEndingCue->data()->endMediaTime();
    17091708
    1710     Optional<CueInterval> nextCue = m_cueData->cueTree.nextIntervalAfter(movieTimeInterval.high());
     1709    Optional<CueInterval> nextCue = m_cueData->cueTree.nextIntervalAfter(movieTime);
    17111710    if (nextCue)
    17121711        nextInterestingTime = std::min(nextInterestingTime, nextCue->low());
    … …  
    19971996    MediaTime endTime = std::max(cue.startMediaTime(), cue.endMediaTime());
    19981997
    1999     CueInterval interval = m_cueData->cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
     1998    CueInterval interval(cue.startMediaTime(), endTime, &cue);
    20001999    if (!m_cueData->cueTree.contains(interval))
    20012000        m_cueData->cueTree.add(interval);
    … …  
    20122011    MediaTime endTime = std::max(cue.startMediaTime(), cue.endMediaTime());
    20132012
    2014     CueInterval interval = m_cueData->cueTree.createInterval(cue.startMediaTime(), endTime, &cue);
     2013    CueInterval interval(cue.startMediaTime(), endTime, &cue);
    20152014    m_cueData->cueTree.remove(interval);
    20162015

  • trunk/Source/WebCore/html/HTMLMediaElement.h

    r253923 r254483  
    4747#include "AudioTrack.h"
    4848#include "CaptionUserPreferences.h"
    49 #include "PODInterval.h"
    5049#include "TextTrack.h"
    5150#include "TextTrackCue.h"
    … …  
    106105
    107106template<typename> class DOMPromiseDeferred;
     107template<typename, typename> class PODInterval;
    108108
    109109#if ENABLE(WIRELESS_PLAYBACK_TARGET)

  • trunk/Source/WebCore/html/shadow/MediaControlElements.cpp

    r252392 r254483  
    4949#include "MediaControls.h"
    5050#include "MouseEvent.h"
     51#include "PODInterval.h"
    5152#include "Page.h"
    5253#include "PageGroup.h"

  • trunk/Source/WebCore/platform/PODInterval.h

    r253290 r254483  
    11/*
    22 * Copyright (C) 2010 Google Inc. All rights reserved.
     3 * Copyright (C) 2020 Apple Inc. All rights reserved.
    34 *
    45 * Redistribution and use in source and binary forms, with or without
    … …  
    3233namespace WebCore {
    3334
    34 // Class representing a closed interval which can hold arbitrary
    35 // endpoints and a piece of user
    36 // data. An important characteristic for the algorithms we use is that
    37 // if two intervals have identical endpoints but different user data,
    38 // they are not considered to be equal. This situation can arise when
    39 // representing the vertical extents of bounding boxes of overlapping
    40 // triangles, where the pointer to the triangle is the user data of
    41 // the interval.
     35// Class template representing a closed interval which can hold arbitrary
     36// endpoints and a piece of user data. Ordering and equality are defined
     37// including the UserData, except in the special case of WeakPtr.
    4238//
    43 // *Note* that the destructors of type T and UserData will *not* be
    44 // called by this class. They must not allocate any memory that is
    45 // required to be cleaned up in their destructors.
    46 //
    47 // The following constructors and operators must be implemented on
    48 // type T:
    49 //
    50 //   - Copy constructor
    51 //   - operator<
    52 //   - operator==
    53 //   - operator=
    54 //
    55 // The UserData type must support a copy constructor and assignment
    56 // operator.
     39// Both the T and UserData types must support a copy constructor, operator<,
     40// operator==, and operator=, except that this does not depend on operator<
     41// or operator== for WeakPtr.
    5742//
    5843// In debug mode, printing of intervals and the data they contain is
    5944// enabled. This uses WTF::TextStream.
    6045//
    61 // Note that this class requires a copy constructor and assignment
    62 // operator in order to be stored in the red-black tree.
     46// Note that this class supplies a copy constructor and assignment
     47// operator in order so it can be stored in the red-black tree.
    6348
    6449// FIXME: The prefix "POD" here isn't correct; this works with non-POD types.
    6550
    66 template<class T, class UserData>
    67 class PODInterval {
     51template<class T, class UserData> class PODIntervalBase {
    6852public:
    69     PODInterval(const T& low, const T& high)
    70         : m_low(low)
    71         , m_high(high)
    72         , m_maxHigh(high)
     53    const T& low() const { return m_low; }
     54    const T& high() const { return m_high; }
     55    const UserData& data() const { return m_data; }
     56
     57    bool overlaps(const T& low, const T& high) const
    7358    {
     59        return !(m_high < low || high < m_low);
    7460    }
    7561
    76     PODInterval(const T& low, const T& high, const UserData& data)
    77         : m_low(low)
    78         , m_high(high)
    79         , m_data(data)
    80         , m_maxHigh(high)
     62    bool overlaps(const PODIntervalBase& other) const
    8163    {
     64        return overlaps(other.m_low, other.m_high);
    8265    }
    8366
    84     PODInterval(const T& low, const T& high, UserData&& data)
     67    const T& maxHigh() const { return m_maxHigh; }
     68    void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
     69
     70protected:
     71    PODIntervalBase(const T& low, const T& high, UserData&& data)
    8572        : m_low(low)
    8673        , m_high(high)
    … …  
    9077    }
    9178
    92     const T& low() const { return m_low; }
    93     const T& high() const { return m_high; }
    94     const UserData& data() const { return m_data; }
    95 
    96     bool overlaps(const T& low, const T& high) const
     79#if COMPILER(MSVC)
     80    // Work around an MSVC bug.
     81    PODIntervalBase(const T& low, const T& high, const UserData& data)
     82        : m_low(low)
     83        , m_high(high)
     84        , m_data(data)
     85        , m_maxHigh(high)
    9786    {
    98         if (this->high() < low)
    99             return false;
    100         if (high < this->low())
    101             return false;
    102         return true;
    10387    }
    104 
    105     bool overlaps(const PODInterval& other) const
    106     {
    107         return overlaps(other.low(), other.high());
    108     }
    109 
    110     // Returns true if this interval is "less" than the other. The
    111     // comparison is performed on the low endpoints of the intervals.
    112     bool operator<(const PODInterval& other) const
    113     {
    114         return low() < other.low();
    115     }
    116 
    117     // Returns true if this interval is strictly equal to the other,
    118     // including comparison of the user data.
    119     bool operator==(const PODInterval& other) const
    120     {
    121         return (low() == other.low()
    122                 && high() == other.high()
    123                 && data() == other.data());
    124     }
    125 
    126     const T& maxHigh() const { return m_maxHigh; }
    127     void setMaxHigh(const T& maxHigh) { m_maxHigh = maxHigh; }
     88#endif
    12889
    12990private:
    … …  
    13293    UserData m_data { };
    13394    T m_maxHigh;
     95};
     96
     97template<class T, class UserData> class PODInterval : public PODIntervalBase<T, UserData> {
     98public:
     99    PODInterval(const T& low, const T& high, UserData&& data = { })
     100        : PODIntervalBase<T, UserData>(low, high, WTFMove(data))
     101    {
     102    }
     103
     104    PODInterval(const T& low, const T& high, const UserData& data)
     105        : PODIntervalBase<T, UserData>(low, high, UserData { data })
     106    {
     107    }
     108
     109    bool operator<(const PODInterval& other) const
     110    {
     111        if (Base::low() < other.Base::low())
     112            return true;
     113        if (other.Base::low() < Base::low())
     114            return false;
     115        if (Base::high() < other.Base::high())
     116            return true;
     117        if (other.Base::high() < Base::high())
     118            return false;
     119        return Base::data() < other.Base::data();
     120    }
     121
     122    bool operator==(const PODInterval& other) const
     123    {
     124        return Base::low() == other.Base::low()
     125            && Base::high() == other.Base::high()
     126            && Base::data() == other.Base::data();
     127    }
     128
     129private:
     130    using Base = PODIntervalBase<T, UserData>;
     131};
     132
     133template<class T, class U> class PODInterval<T, WTF::WeakPtr<U>> : public PODIntervalBase<T, WTF::WeakPtr<U>> {
     134public:
     135    PODInterval(const T& low, const T& high, WTF::WeakPtr<U>&& data)
     136        : PODIntervalBase<T, WTF::WeakPtr<U>>(low, high, WTFMove(data))
     137    {
     138    }
     139
     140    bool operator<(const PODInterval& other) const
     141    {
     142        if (Base::low() < other.Base::low())
     143            return true;
     144        if (other.Base::low() < Base::low())
     145            return false;
     146        return Base::high() < other.Base::high();
     147    }
     148
     149private:
     150    using Base = PODIntervalBase<T, WTF::WeakPtr<U>>;
    134151};
    135152

  • trunk/Source/WebCore/platform/PODIntervalTree.h

    r253290 r254483  
    11/*
    22 * Copyright (C) 2010 Google Inc. All rights reserved.
    3  * Copyright (C) 2019 Apple Inc. All rights reserved.
     3 * Copyright (C) 2019-2020 Apple Inc. All rights reserved.
    44 *
    55 * Redistribution and use in source and binary forms, with or without
    … …  
    3636namespace WebCore {
    3737
    38 template <class T, class UserData>
    39 class PODIntervalSearchAdapter {
    40 public:
    41     typedef PODInterval<T, UserData> IntervalType;
    42    
    43     PODIntervalSearchAdapter(Vector<IntervalType>& result, const T& lowValue, const T& highValue)
    44         : m_result(result)
    45         , m_lowValue(lowValue)
    46         , m_highValue(highValue)
    47     {
    48     }
    49    
    50     const T& lowValue() const { return m_lowValue; }
    51     const T& highValue() const { return m_highValue; }
    52     void collectIfNeeded(const IntervalType& data) const
    53     {
    54         if (data.overlaps(m_lowValue, m_highValue))
    55             m_result.append(data);
    56     }
    57 
    58 private:
    59     Vector<IntervalType>& m_result;
    60     T m_lowValue;
    61     T m_highValue;
    62 };
    63 
    6438struct PODIntervalNodeUpdater;
    6539
    … …  
    6741// supports efficient (O(lg n)) insertion, removal and querying of
    6842// intervals in the tree.
    69 template<class T, class UserData>
    70 class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true> {
     43template<typename T, typename UserData> class PODIntervalTree final : public PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater> {
    7144    WTF_MAKE_FAST_ALLOCATED;
    7245public:
    73     // Typedef to reduce typing when declaring intervals to be stored in
    74     // this tree.
    75     typedef PODInterval<T, UserData> IntervalType;
    76     typedef PODIntervalSearchAdapter<T, UserData> IntervalSearchAdapterType;
    77 
    78     // Returns all intervals in the tree which overlap the given query
    79     // interval. The returned intervals are sorted by increasing low
    80     // endpoint.
     46    using IntervalType = PODInterval<T, UserData>;
     47    class OverlapsSearchAdapter;
     48
     49    // Returns all intervals in the tree which overlap the given query interval, sorted by the < operator.
    8150    Vector<IntervalType> allOverlaps(const IntervalType& interval) const
    8251    {
    8352        Vector<IntervalType> result;
    84         IntervalSearchAdapterType adapter(result, interval.low(), interval.high());
    85         allOverlapsWithAdapter<IntervalSearchAdapterType>(adapter);
     53        OverlapsSearchAdapter adapter(result, interval);
     54        allOverlapsWithAdapter(adapter);
    8655        return result;
    8756    }
    8857
    89     template <class AdapterType>
    90     void allOverlapsWithAdapter(AdapterType& adapter) const
    91     {
    92         // Explicit dereference of "this" required because of
    93         // inheritance rules in template classes.
    94         searchForOverlapsFrom<AdapterType>(this->root(), adapter);
    95     }
    96 
    97     // Helper to create interval objects.
    98     static IntervalType createInterval(const T& low, const T& high, UserData&& data = { })
    99     {
    100         return IntervalType(low, high, WTFMove(data));
     58    template<typename AdapterType> void allOverlapsWithAdapter(AdapterType& adapter) const
     59    {
     60        searchForOverlapsFrom(this->root(), adapter);
    10161    }
    10262
    … …  
    11777        if (!this->root())
    11878            return true;
    119         return checkInvariantsFromNode(this->root(), 0);
     79        return checkInvariantsFromNode(this->root(), nullptr);
    12080    }
    12181
    … …  
    12383
    12484private:
    125     using Base = PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater, true>;
    126     typedef typename Base::Node IntervalNode;
     85    using Base = PODRedBlackTree<PODInterval<T, UserData>, PODIntervalNodeUpdater>;
     86    using IntervalNode = typename Base::Node;
    12787
    12888    // Starting from the given node, adds all overlaps with the given
    12989    // interval to the result vector. The intervals are sorted by
    13090    // increasing low endpoint.
    131     template <class AdapterType>
    132     void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
     91    template<typename AdapterType> void searchForOverlapsFrom(IntervalNode* node, AdapterType& adapter) const
    13392    {
    13493        if (!node)
    … …  
    220179};
    221180
     181template<typename T, typename UserData> class PODIntervalTree<T, UserData>::OverlapsSearchAdapter {
     182public:
     183    using IntervalType = PODInterval<T, UserData>;
     184
     185    OverlapsSearchAdapter(Vector<IntervalType>& result, const IntervalType& interval)
     186        : m_result(result)
     187        , m_interval(interval)
     188    {
     189    }
     190
     191    const T& lowValue() const { return m_interval.low(); }
     192    const T& highValue() const { return m_interval.high(); }
     193    void collectIfNeeded(const IntervalType& data) const
     194    {
     195        if (data.overlaps(m_interval))
     196            m_result.append(data);
     197    }
     198
     199private:
     200    Vector<IntervalType>& m_result;
     201    const IntervalType& m_interval;
     202};
     203
    222204struct PODIntervalNodeUpdater {
    223205    template<typename Node> static bool update(Node& node)

  • trunk/Source/WebCore/platform/PODRedBlackTree.h

    r253290 r254483  
    11/*
    22 * Copyright (C) 2010 Google Inc. All rights reserved.
    3  * Copyright (C) 2019 Apple Inc. All rights reserved.
     3 * Copyright (C) 2019-2020 Apple Inc. All rights reserved.
    44 *
    55 * Redistribution and use in source and binary forms, with or without
    … …  
    4040// enabled. This makes use of WTF::TextStream.
    4141//
    42 // Note that when complex types are stored in this red/black tree, it
    43 // is possible that single invocations of the "<" and "==" operators
    44 // will be insufficient to describe the ordering of elements in the
    45 // tree during queries. As a concrete example, consider the case where
    46 // intervals are stored in the tree sorted by low endpoint. The "<"
    47 // operator on the Interval class only compares the low endpoint, but
    48 // the "==" operator takes into account the high endpoint as well.
    49 // This makes the necessary logic for querying and deletion somewhat
    50 // more complex. In order to properly handle such situations, the
    51 // template argument "needsFullOrderingComparisons" must be true.
    52 //
    5342// This red-black tree is designed to be _augmented_; subclasses can
    5443// add additional and summary information to each node to efficiently
    … …  
    7160
    7261// FIXME: The prefix "POD" here isn't correct; this tree works with non-POD types too.
    73 // FIXME: Remove the unusual needsFullOrderingComparisons feature by changing the interval tree to use full ordering, sorting based on low, high, and data.
    74 // FIXME: Would be worthwhile to implement this on top of WTF::RedBlackTree rather than keeping two separate class templates around.
     62// FIXME: Extend WTF::RedBlackTree and implement this on top of it rather than keeping two quite similar class templates around.
    7563
    7664namespace WebCore {
    7765
    78 template<typename T, typename NodeUpdaterType, bool needsFullOrderingComparisons>
    79 class PODRedBlackTree {
     66template<typename T, typename NodeUpdaterType> class PODRedBlackTree {
    8067    WTF_MAKE_NONCOPYABLE(PODRedBlackTree);
    8168public:
    … …  
    8774    }
    8875
    89     // Clearing will delete the contents of the tree.
    9076    void clear()
    9177    {
    … …  
    10288    void add(const T& data)
    10389    {
    104         insertNode(new Node(T { data }));
     90        add(T { data });
    10591    }
    10692
    … …  
    136122    {
    137123        int blackCount;
    138         return checkInvariantsFromNode(m_root, &blackCount);
    139     }
    140 
    141     // Dumps the tree's contents to the logging info stream for
    142     // debugging purposes.
     124        return checkInvariantsFromNode(m_root, blackCount);
     125    }
     126
     127    // Dumps the tree's contents to the logging info stream for debugging purposes.
    143128    void dump() const
    144129    {
    145         dumpFromNode(m_root, 0);
     130        dumpSubtree(m_root, 0);
    146131    }
    147132
    … …  
    159144    enum Color { Red, Black };
    160145
    161     // The base Node class which is stored in the tree. Nodes are only
    162     // an internal concept; users of the tree deal only with the data
    163     // they store in it.
    164146    class Node {
    165147        WTF_MAKE_FAST_ALLOCATED;
    166148        WTF_MAKE_NONCOPYABLE(Node);
    167149    public:
    168         // Constructor. Newly-created nodes are colored red.
    169150        explicit Node(T&& data)
    170151            : m_data(WTFMove(data))
    … …  
    177158        T& data() { return m_data; }
    178159
    179         void moveDataFrom(Node* src) { m_data = WTFMove(src->m_data); }
     160        void moveDataFrom(Node& src) { m_data = WTFMove(src.m_data); }
    180161
    181162        Node* left() const { return m_left; }
    … …  
    200181
    201182private:
    202     // This is the hook that subclasses should use when
     183    // The update function is the hook that subclasses should use when
    203184    // augmenting the red-black tree with additional per-node summary
    204185    // information. For example, in the case of an interval tree, this
    … …  
    207188    // is guaranteed that this will be called in the correct order to
    208189    // properly update such summary information based only on the values
    209     // in the left and right children. This method should return true if
     190    // in the left and right children. The function should return true if
    210191    // the node's summary information changed.
    211     bool updateNode(Node* node)
    212     {
    213         return NodeUpdaterType::update(*node);
    214     }
    215 
    216     //----------------------------------------------------------------------
    217     // Generic binary search tree operations
    218     //
    219 
    220     // Searches the tree for the given datum.
     192    static bool updateNode(Node& node)
     193    {
     194        return NodeUpdaterType::update(node);
     195    }
     196
    221197    Node* treeSearch(const T& data) const
    222198    {
    223         if (needsFullOrderingComparisons)
    224             return treeSearchFullComparisons(m_root, data);
    225 
    226         return treeSearchNormal(m_root, data);
    227     }
    228 
    229     // Searches the tree using the normal comparison operations,
    230     // suitable for simple data types such as numbers.
    231     Node* treeSearchNormal(Node* current, const T& data) const
    232     {
    233         while (current) {
     199        for (auto* current = m_root; current; ) {
    234200            if (current->data() == data)
    235201                return current;
    … …  
    239205                current = current->right();
    240206        }
    241         return 0;
    242     }
    243 
    244     // Searches the tree using multiple comparison operations, required
    245     // for data types with more complex behavior such as intervals.
    246     Node* treeSearchFullComparisons(Node* current, const T& data) const
    247     {
    248         if (!current)
    249             return 0;
    250         if (data < current->data())
    251             return treeSearchFullComparisons(current->left(), data);
    252         if (current->data() < data)
    253             return treeSearchFullComparisons(current->right(), data);
    254         if (data == current->data())
    255             return current;
    256 
    257         // We may need to traverse both the left and right subtrees.
    258         Node* result = treeSearchFullComparisons(current->left(), data);
    259         if (!result)
    260             result = treeSearchFullComparisons(current->right(), data);
    261         return result;
     207        return nullptr;
    262208    }
    263209
    264210    void treeInsert(Node* z)
    265211    {
    266         Node* y = 0;
     212        Node* y = nullptr;
    267213        Node* x = m_root;
    268214        while (x) {
    … …  
    298244    }
    299245
    300     // Finds the minimum element in the sub-tree rooted at the given
    301     // node.
     246    // Finds the minimum element in the sub-tree rooted at the given node.
    302247    static Node* treeMinimum(Node* x)
    303248    {
    … …  
    313258            return treeMinimum(y->right());
    314259        return y;
    315     }
    316 
    317     // Helper for maintaining the augmented red-black tree.
    318     void propagateUpdates(Node* start)
    319     {
    320         bool shouldContinue = true;
    321         while (start && shouldContinue) {
    322             shouldContinue = updateNode(start);
    323             start = start->parent();
    324         }
    325260    }
    326261
    … …  
    357292
    358293        // Update nodes lowest to highest.
    359         updateNode(x);
    360         updateNode(y);
     294        updateNode(*x);
     295        updateNode(*y);
    361296        return y;
     297    }
     298
     299    static void propagateUpdates(Node* start)
     300    {
     301        while (start && updateNode(*start))
     302            start = start->parent();
    362303    }
    363304
    … …  
    390331
    391332        // Update nodes lowest to highest.
    392         updateNode(y);
    393         updateNode(x);
     333        updateNode(*y);
     334        updateNode(*x);
    394335        return x;
    395336    }
    … …  
    400341        treeInsert(x);
    401342        x->setColor(Red);
    402         updateNode(x);
     343        updateNode(*x);
    403344
    404345        logIfVerbose("  PODRedBlackTree::InsertNode");
    … …  
    416357                    y->setColor(Black);
    417358                    x->parent()->parent()->setColor(Red);
    418                     updateNode(x->parent());
     359                    updateNode(*x->parent());
    419360                    x = x->parent()->parent();
    420                     updateNode(x);
     361                    updateNode(*x);
    421362                    updateStart = x->parent();
    422363                } else {
    … …  
    443384                    y->setColor(Black);
    444385                    x->parent()->parent()->setColor(Red);
    445                     updateNode(x->parent());
     386                    updateNode(*x->parent());
    446387                    x = x->parent()->parent();
    447                     updateNode(x);
     388                    updateNode(*x);
    448389                    updateStart = x->parent();
    449390                } else {
    … …  
    470411
    471412    // Restores the red-black property to the tree after splicing out
    472     // a node. Note that x may be null, which is why xParent must be
    473     // supplied.
     413    // a node. Note that x may be null, which is why xParent must be supplied.
    474414    void deleteFixup(Node* x, Node* xParent)
    475415    {
    … …  
    595535        }
    596536        if (y != z) {
    597             z->moveDataFrom(y);
     537            z->moveDataFrom(*y);
    598538            // This node has changed location in the tree and must be updated.
    599             updateNode(z);
     539            updateNode(*z);
    600540            // The parent and its parents may now be out of date.
    601541            propagateUpdates(z->parent());
    … …  
    619559    // Returns in the "blackCount" parameter the number of black
    620560    // children along all paths to all leaves of the given node.
    621     bool checkInvariantsFromNode(Node* node, int* blackCount) const
     561    bool checkInvariantsFromNode(Node* node, int& blackCount) const
    622562    {
    623563        // Base case is a leaf node.
    624564        if (!node) {
    625             *blackCount = 1;
     565            blackCount = 1;
    626566            return true;
    627567        }
    … …  
    641581        }
    642582
    643         // Every simple path to a leaf node contains the same number of
    644         // black nodes.
     583        // Every simple path to a leaf node contains the same number of black nodes.
    645584        int leftCount = 0, rightCount = 0;
    646         bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
    647         bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
     585        bool leftValid = checkInvariantsFromNode(node->left(), leftCount);
     586        bool rightValid = checkInvariantsFromNode(node->right(), rightCount);
    648587        if (!leftValid || !rightValid)
    649588            return false;
    650         *blackCount = leftCount + (node->color() == Black ? 1 : 0);
     589        blackCount = leftCount + (node->color() == Black ? 1 : 0);
    651590        return leftCount == rightCount;
    652591    }
    … …  
    666605#ifndef NDEBUG
    667606
    668     // Dumps the subtree rooted at the given node.
    669     void dumpFromNode(Node* node, int indentation) const
     607    void dumpSubtree(Node* node, int indentation) const
    670608    {
    671609        StringBuilder builder;
    … …  
    682620        LOG_ERROR("%s", builder.toString().utf8().data());
    683621        if (node) {
    684             dumpFromNode(node->left(), indentation + 2);
    685             dumpFromNode(node->right(), indentation + 2);
     622            dumpSubtree(node->left(), indentation + 2);
     623            dumpSubtree(node->right(), indentation + 2);
    686624        }
    687625    }
    688626
    689627#endif
    690 
    691     //----------------------------------------------------------------------
    692     // Data members
    693628
    694629    Node* m_root { nullptr };

  • trunk/Source/WebCore/rendering/FloatingObjects.h

    r254087 r254483  
    2424#pragma once
    2525
    26 #include "PODInterval.h"
    2726#include "RootInlineBox.h"
    2827#include <wtf/ListHashSet.h>
    … …  
    3433class RenderBox;
    3534
     35template<typename, typename> class PODInterval;
    3636template<typename, typename> class PODIntervalTree;
    3737
Note: See TracChangeset for help on using the changeset viewer.