Changeset 105646 in webkit


Ignore:
Timestamp:
Jan 23, 2012 3:30:57 PM (12 years ago)
Author:
barraclough@apple.com
Message:

​https://bugs.webkit.org/show_bug.cgi?id=76855
Implement a JIT-code aware sampling profiler for JSC

Reviewed by Geoff Garen.

Step 2: generalize RedBlackTree. The profiler is going to want tio use
a RedBlackTree, allow this class to work with subclasses of
RedBlackTree::Node, Node should not need to know the names of the m_key
and m_value fields (the subclass can provide a key() accessor), and
RedBlackTree does not need to know anything about ValueType.

(WTF::MetaAllocator::findAndRemoveFreeSpace):
(WTF::MetaAllocator::debugFreeSpaceSize):
(WTF::MetaAllocator::addFreeSpace):

  • wtf/MetaAllocator.h:

(WTF::MetaAllocator::FreeSpaceNode::FreeSpaceNode):
(WTF::MetaAllocator::FreeSpaceNode::key):

  • wtf/MetaAllocatorHandle.h:

(WTF::MetaAllocatorHandle::key):

  • wtf/RedBlackTree.h:

(WTF::RedBlackTree::Node::successor):
(WTF::RedBlackTree::Node::predecessor):
(WTF::RedBlackTree::Node::parent):
(WTF::RedBlackTree::Node::setParent):
(WTF::RedBlackTree::Node::left):
(WTF::RedBlackTree::Node::setLeft):
(WTF::RedBlackTree::Node::right):
(WTF::RedBlackTree::Node::setRight):
(WTF::RedBlackTree::insert):
(WTF::RedBlackTree::remove):
(WTF::RedBlackTree::findExact):
(WTF::RedBlackTree::findLeastGreaterThanOrEqual):
(WTF::RedBlackTree::findGreatestLessThanOrEqual):
(WTF::RedBlackTree::first):
(WTF::RedBlackTree::last):
(WTF::RedBlackTree::size):
(WTF::RedBlackTree::treeMinimum):
(WTF::RedBlackTree::treeMaximum):
(WTF::RedBlackTree::treeInsert):
(WTF::RedBlackTree::leftRotate):
(WTF::RedBlackTree::rightRotate):
(WTF::RedBlackTree::removeFixup):

Location:
trunk/Source/JavaScriptCore
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r105639 r105646  
     12012-01-23  Gavin Barraclough  <barraclough@apple.com>
     2
     3        https://bugs.webkit.org/show_bug.cgi?id=76855
     4        Implement a JIT-code aware sampling profiler for JSC
     5
     6        Reviewed by Geoff Garen.
     7
     8        Step 2: generalize RedBlackTree. The profiler is going to want tio use
     9        a RedBlackTree, allow this class to work with subclasses of
     10        RedBlackTree::Node, Node should not need to know the names of the m_key
     11        and m_value fields (the subclass can provide a key() accessor), and
     12        RedBlackTree does not need to know anything about ValueType.
     13
     14        * JavaScriptCore.exp:
     15        * wtf/MetaAllocator.cpp:
     16        (WTF::MetaAllocator::findAndRemoveFreeSpace):
     17        (WTF::MetaAllocator::debugFreeSpaceSize):
     18        (WTF::MetaAllocator::addFreeSpace):
     19        * wtf/MetaAllocator.h:
     20        (WTF::MetaAllocator::FreeSpaceNode::FreeSpaceNode):
     21        (WTF::MetaAllocator::FreeSpaceNode::key):
     22        * wtf/MetaAllocatorHandle.h:
     23        (WTF::MetaAllocatorHandle::key):
     24        * wtf/RedBlackTree.h:
     25        (WTF::RedBlackTree::Node::successor):
     26        (WTF::RedBlackTree::Node::predecessor):
     27        (WTF::RedBlackTree::Node::parent):
     28        (WTF::RedBlackTree::Node::setParent):
     29        (WTF::RedBlackTree::Node::left):
     30        (WTF::RedBlackTree::Node::setLeft):
     31        (WTF::RedBlackTree::Node::right):
     32        (WTF::RedBlackTree::Node::setRight):
     33        (WTF::RedBlackTree::insert):
     34        (WTF::RedBlackTree::remove):
     35        (WTF::RedBlackTree::findExact):
     36        (WTF::RedBlackTree::findLeastGreaterThanOrEqual):
     37        (WTF::RedBlackTree::findGreatestLessThanOrEqual):
     38        (WTF::RedBlackTree::first):
     39        (WTF::RedBlackTree::last):
     40        (WTF::RedBlackTree::size):
     41        (WTF::RedBlackTree::treeMinimum):
     42        (WTF::RedBlackTree::treeMaximum):
     43        (WTF::RedBlackTree::treeInsert):
     44        (WTF::RedBlackTree::leftRotate):
     45        (WTF::RedBlackTree::rightRotate):
     46        (WTF::RedBlackTree::removeFixup):
     47
    1482012-01-23  Andy Estes  <aestes@apple.com>
    249

  • trunk/Source/JavaScriptCore/JavaScriptCore.exp

    r105639 r105646  
    413413__ZN3WTF12randomNumberEv
    414414__ZN3WTF13MetaAllocator17addFreshFreeSpaceEPvm
    415 __ZN3WTF13MetaAllocator17freeFreeSpaceNodeEPNS_12RedBlackTreeImPvE4NodeE
    416415__ZN3WTF13MetaAllocator18debugFreeSpaceSizeEv
    417416__ZN3WTF13MetaAllocator8allocateEm

  • trunk/Source/JavaScriptCore/wtf/MetaAllocator.cpp

    r103243 r105646  
    179179        return 0;
    180180   
    181     ASSERT(node->m_key >= sizeInBytes);
     181    ASSERT(node->m_sizeInBytes >= sizeInBytes);
    182182   
    183183    m_freeSpaceSizeMap.remove(node);
    … …  
    185185    void* result;
    186186   
    187     if (node->m_key == sizeInBytes) {
     187    if (node->m_sizeInBytes == sizeInBytes) {
    188188        // Easy case: perfect fit, so just remove the node entirely.
    189         result = node->m_value;
    190        
    191         m_freeSpaceStartAddressMap.remove(node->m_value);
    192         m_freeSpaceEndAddressMap.remove(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_value) + node->m_key));
     189        result = node->m_start;
     190       
     191        m_freeSpaceStartAddressMap.remove(node->m_start);
     192        m_freeSpaceEndAddressMap.remove(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes));
    193193        freeFreeSpaceNode(node);
    194194    } else {
    … …  
    200200        // fewer committed pages and fewer failures in general.
    201201       
    202         uintptr_t firstPage = reinterpret_cast<uintptr_t>(node->m_value) >> m_logPageSize;
    203         uintptr_t lastPage = (reinterpret_cast<uintptr_t>(node->m_value) + node->m_key - 1) >> m_logPageSize;
    204    
    205         uintptr_t lastPageForLeftAllocation = (reinterpret_cast<uintptr_t>(node->m_value) + sizeInBytes - 1) >> m_logPageSize;
    206         uintptr_t firstPageForRightAllocation = (reinterpret_cast<uintptr_t>(node->m_value) + node->m_key - sizeInBytes) >> m_logPageSize;
     202        uintptr_t firstPage = reinterpret_cast<uintptr_t>(node->m_start) >> m_logPageSize;
     203        uintptr_t lastPage = (reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes - 1) >> m_logPageSize;
     204   
     205        uintptr_t lastPageForLeftAllocation = (reinterpret_cast<uintptr_t>(node->m_start) + sizeInBytes - 1) >> m_logPageSize;
     206        uintptr_t firstPageForRightAllocation = (reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes - sizeInBytes) >> m_logPageSize;
    207207       
    208208        if (lastPageForLeftAllocation - firstPage + 1 <= lastPage - firstPageForRightAllocation + 1) {
    209209            // Allocate in the left side of the returned chunk, and slide the node to the right.
    210             result = node->m_value;
    211            
    212             m_freeSpaceStartAddressMap.remove(node->m_value);
    213            
    214             node->m_key -= sizeInBytes;
    215             node->m_value = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_value) + sizeInBytes);
     210            result = node->m_start;
     211           
     212            m_freeSpaceStartAddressMap.remove(node->m_start);
     213           
     214            node->m_sizeInBytes -= sizeInBytes;
     215            node->m_start = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + sizeInBytes);
    216216           
    217217            m_freeSpaceSizeMap.insert(node);
    218             m_freeSpaceStartAddressMap.add(node->m_value, node);
     218            m_freeSpaceStartAddressMap.add(node->m_start, node);
    219219        } else {
    220220            // Allocate in the right size of the returned chunk, and slide the node to the left;
    221221           
    222             result = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_value) + node->m_key - sizeInBytes);
    223            
    224             m_freeSpaceEndAddressMap.remove(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_value) + node->m_key));
    225            
    226             node->m_key -= sizeInBytes;
     222            result = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes - sizeInBytes);
     223           
     224            m_freeSpaceEndAddressMap.remove(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(node->m_start) + node->m_sizeInBytes));
     225           
     226            node->m_sizeInBytes -= sizeInBytes;
    227227           
    228228            m_freeSpaceSizeMap.insert(node);
    … …  
    256256    size_t result = 0;
    257257    for (FreeSpaceNode* node = m_freeSpaceSizeMap.first(); node; node = node->successor())
    258         result += node->m_key;
     258        result += node->m_sizeInBytes;
    259259    return result;
    260260#else
    … …  
    275275        // remove its end from the end address map.
    276276       
    277         ASSERT(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(leftNeighbor->second->m_value) + leftNeighbor->second->m_key) == leftNeighbor->first);
     277        ASSERT(reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(leftNeighbor->second->m_start) + leftNeighbor->second->m_sizeInBytes) == leftNeighbor->first);
    278278       
    279279        FreeSpaceNode* leftNode = leftNeighbor->second;
    280280       
    281         void* leftStart = leftNode->m_value;
    282         size_t leftSize = leftNode->m_key;
     281        void* leftStart = leftNode->m_start;
     282        size_t leftSize = leftNode->m_sizeInBytes;
    283283        void* leftEnd = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(leftStart) + leftSize);
    284284       
    … …  
    293293            // right, whilst removing the right neighbor from the maps.
    294294           
    295             ASSERT(rightNeighbor->second->m_value == rightNeighbor->first);
     295            ASSERT(rightNeighbor->second->m_start == rightNeighbor->first);
    296296           
    297297            FreeSpaceNode* rightNode = rightNeighbor->second;
    298298            void* rightStart = rightNeighbor->first;
    299             size_t rightSize = rightNode->m_key;
     299            size_t rightSize = rightNode->m_sizeInBytes;
    300300            void* rightEnd = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(rightStart) + rightSize);
    301301           
    … …  
    309309            freeFreeSpaceNode(rightNode);
    310310           
    311             leftNode->m_key += sizeInBytes + rightSize;
     311            leftNode->m_sizeInBytes += sizeInBytes + rightSize;
    312312           
    313313            m_freeSpaceSizeMap.insert(leftNode);
    314314            m_freeSpaceEndAddressMap.add(rightEnd, leftNode);
    315315        } else {
    316             leftNode->m_key += sizeInBytes;
     316            leftNode->m_sizeInBytes += sizeInBytes;
    317317           
    318318            m_freeSpaceSizeMap.insert(leftNode);
    … …  
    325325            FreeSpaceNode* rightNode = rightNeighbor->second;
    326326            void* rightStart = rightNeighbor->first;
    327             size_t rightSize = rightNode->m_key;
     327            size_t rightSize = rightNode->m_sizeInBytes;
    328328            void* rightEnd = reinterpret_cast<void*>(reinterpret_cast<uintptr_t>(rightStart) + rightSize);
    329329           
    … …  
    334334            m_freeSpaceStartAddressMap.remove(rightStart);
    335335           
    336             rightNode->m_key += sizeInBytes;
    337             rightNode->m_value = start;
     336            rightNode->m_sizeInBytes += sizeInBytes;
     337            rightNode->m_start = start;
    338338           
    339339            m_freeSpaceSizeMap.insert(rightNode);
    … …  
    344344            FreeSpaceNode* node = allocFreeSpaceNode();
    345345           
    346             node->m_key = sizeInBytes;
    347             node->m_value = start;
     346            node->m_sizeInBytes = sizeInBytes;
     347            node->m_start = start;
    348348           
    349349            m_freeSpaceSizeMap.insert(node);

  • trunk/Source/JavaScriptCore/wtf/MetaAllocator.h

    r104900 r105646  
    4646class MetaAllocator {
    4747    WTF_MAKE_NONCOPYABLE(MetaAllocator);
     48
    4849public:
    49    
    5050    WTF_EXPORT_PRIVATE MetaAllocator(size_t allocationGranule);
    5151   
    … …  
    102102    friend class MetaAllocatorHandle;
    103103   
    104     typedef RedBlackTree<size_t, void*> Tree;
    105     typedef Tree::Node FreeSpaceNode;
     104    class FreeSpaceNode : public RedBlackTree<FreeSpaceNode, size_t>::Node {
     105    public:
     106        FreeSpaceNode(void* start, size_t sizeInBytes)
     107            : m_start(start)
     108            , m_sizeInBytes(sizeInBytes)
     109        {
     110        }
     111
     112        size_t key()
     113        {
     114            return m_sizeInBytes;
     115        }
     116
     117        void* m_start;
     118        size_t m_sizeInBytes;
     119    };
     120    typedef RedBlackTree<FreeSpaceNode, size_t> Tree;
    106121   
    107122    // Remove free space from the allocator. This is effectively
    … …  
    122137    void incrementPageOccupancy(void* address, size_t sizeInBytes);
    123138    void decrementPageOccupancy(void* address, size_t sizeInBytes);
    124    
     139
    125140    // Utilities.
    126141   

  • trunk/Source/JavaScriptCore/wtf/RedBlackTree.h

    r95901 r105646  
    4242// - The key type must implement operator< and ==.
    4343
    44 template<typename KeyType, typename ValueType>
     44template<class NodeType, typename KeyType>
    4545class RedBlackTree {
    4646    WTF_MAKE_NONCOPYABLE(RedBlackTree);
    … …  
    5656       
    5757    public:
    58         Node(KeyType key, ValueType value)
    59             : m_key(key)
    60             , m_value(value)
    61         {
    62         }
    63        
    64         const Node* successor() const
     58        const NodeType* successor() const
    6559        {
    6660            const Node* x = this;
    6761            if (x->right())
    6862                return treeMinimum(x->right());
    69             const Node* y = x->parent();
     63            const NodeType* y = x->parent();
    7064            while (y && x == y->right()) {
    7165                x = y;
    … …  
    7569        }
    7670       
    77         const Node* predecessor() const
     71        const NodeType* predecessor() const
    7872        {
    7973            const Node* x = this;
    8074            if (x->left())
    8175                return treeMaximum(x->left());
    82             const Node* y = x->parent();
     76            const NodeType* y = x->parent();
    8377            while (y && x == y->left()) {
    8478                x = y;
    … …  
    8882        }
    8983       
    90         Node* successor()
    91         {
    92             return const_cast<Node*>(const_cast<const Node*>(this)->successor());
    93         }
    94    
    95         Node* predecessor()
    96         {
    97             return const_cast<Node*>(const_cast<const Node*>(this)->predecessor());
    98         }
    99    
    100         KeyType m_key;
    101         ValueType m_value;
     84        NodeType* successor()
     85        {
     86            return const_cast<NodeType*>(const_cast<const Node*>(this)->successor());
     87        }
     88
     89        NodeType* predecessor()
     90        {
     91            return const_cast<NodeType*>(const_cast<const Node*>(this)->predecessor());
     92        }
    10293
    10394    private:
    … …  
    111102        // NOTE: these methods should pack the parent and red into a single
    112103        // word. But doing so appears to reveal a bug in the compiler.
    113         Node* parent() const
    114         {
    115             return reinterpret_cast<Node*>(m_parentAndRed & ~static_cast<uintptr_t>(1));
    116         }
    117        
    118         void setParent(Node* newParent)
     104        NodeType* parent() const
     105        {
     106            return reinterpret_cast<NodeType*>(m_parentAndRed & ~static_cast<uintptr_t>(1));
     107        }
     108       
     109        void setParent(NodeType* newParent)
    119110        {
    120111            m_parentAndRed = reinterpret_cast<uintptr_t>(newParent) | (m_parentAndRed & 1);
    121112        }
    122113       
    123         Node* left() const
     114        NodeType* left() const
    124115        {
    125116            return m_left;
    126117        }
    127118       
    128         void setLeft(Node* node)
     119        void setLeft(NodeType* node)
    129120        {
    130121            m_left = node;
    131122        }
    132123       
    133         Node* right() const
     124        NodeType* right() const
    134125        {
    135126            return m_right;
    136127        }
    137128       
    138         void setRight(Node* node)
     129        void setRight(NodeType* node)
    139130        {
    140131            m_right = node;
    … …  
    156147        }
    157148       
    158         Node* m_left;
    159         Node* m_right;
     149        NodeType* m_left;
     150        NodeType* m_right;
    160151        uintptr_t m_parentAndRed;
    161152    };
    162    
     153
    163154    RedBlackTree()
    164155        : m_root(0)
    … …  
    166157    }
    167158   
    168     void insert(Node* x)
     159    void insert(NodeType* x)
    169160    {
    170161        x->reset();
    … …  
    174165        while (x != m_root && x->parent()->color() == Red) {
    175166            if (x->parent() == x->parent()->parent()->left()) {
    176                 Node* y = x->parent()->parent()->right();
     167                NodeType* y = x->parent()->parent()->right();
    177168                if (y && y->color() == Red) {
    178169                    // Case 1
    … …  
    194185            } else {
    195186                // Same as "then" clause with "right" and "left" exchanged.
    196                 Node* y = x->parent()->parent()->left();
     187                NodeType* y = x->parent()->parent()->left();
    197188                if (y && y->color() == Red) {
    198189                    // Case 1
    … …  
    218209    }
    219210
    220     Node* remove(Node* z)
     211    NodeType* remove(NodeType* z)
    221212    {
    222213        ASSERT(z);
    … …  
    224215       
    225216        // Y is the node to be unlinked from the tree.
    226         Node* y;
     217        NodeType* y;
    227218        if (!z->left() || !z->right())
    228219            y = z;
    … …  
    231222
    232223        // Y is guaranteed to be non-null at this point.
    233         Node* x;
     224        NodeType* x;
    234225        if (y->left())
    235226            x = y->left();
    … …  
    239230        // X is the child of y which might potentially replace y in
    240231        // the tree. X might be null at this point.
    241         Node* xParent;
     232        NodeType* xParent;
    242233        if (x) {
    243234            x->setParent(y->parent());
    … …  
    282273    }
    283274   
    284     Node* remove(const KeyType& key)
    285     {
    286         Node* result = findExact(key);
     275    NodeType* remove(const KeyType& key)
     276    {
     277        NodeType* result = findExact(key);
    287278        if (!result)
    288279            return 0;
    … …  
    290281    }
    291282   
    292     Node* findExact(const KeyType& key) const
    293     {
    294         for (Node* current = m_root; current;) {
    295             if (current->m_key == key)
     283    NodeType* findExact(const KeyType& key) const
     284    {
     285        for (NodeType* current = m_root; current;) {
     286            if (current->key() == key)
    296287                return current;
    297             if (key < current->m_key)
     288            if (key < current->key())
    298289                current = current->left();
    299290            else
    … …  
    303294    }
    304295   
    305     Node* findLeastGreaterThanOrEqual(const KeyType& key) const
    306     {
    307         Node* best = 0;
    308         for (Node* current = m_root; current;) {
    309             if (current->m_key == key)
     296    NodeType* findLeastGreaterThanOrEqual(const KeyType& key) const
     297    {
     298        NodeType* best = 0;
     299        for (NodeType* current = m_root; current;) {
     300            if (current->key() == key)
    310301                return current;
    311             if (current->m_key < key)
     302            if (current->key() < key)
    312303                current = current->right();
    313304            else {
    … …  
    319310    }
    320311   
    321     Node* findGreatestLessThanOrEqual(const KeyType& key) const
    322     {
    323         Node* best = 0;
    324         for (Node* current = m_root; current;) {
    325             if (current->m_key == key)
     312    NodeType* findGreatestLessThanOrEqual(const KeyType& key) const
     313    {
     314        NodeType* best = 0;
     315        for (NodeType* current = m_root; current;) {
     316            if (current->key() == key)
    326317                return current;
    327             if (current->m_key > key)
     318            if (current->key() > key)
    328319                current = current->left();
    329320            else {
    … …  
    335326    }
    336327   
    337     Node* first() const
     328    NodeType* first() const
    338329    {
    339330        if (!m_root)
    … …  
    342333    }
    343334   
    344     Node* last() const
     335    NodeType* last() const
    345336    {
    346337        if (!m_root)
    … …  
    353344    {
    354345        size_t result = 0;
    355         for (Node* current = first(); current; current = current->successor())
     346        for (NodeType* current = first(); current; current = current->successor())
    356347            result++;
    357348        return result;
    … …  
    367358    // Finds the minimum element in the sub-tree rooted at the given
    368359    // node.
    369     static Node* treeMinimum(Node* x)
     360    static NodeType* treeMinimum(NodeType* x)
    370361    {
    371362        while (x->left())
    … …  
    374365    }
    375366   
    376     static Node* treeMaximum(Node* x)
     367    static NodeType* treeMaximum(NodeType* x)
    377368    {
    378369        while (x->right())
    … …  
    381372    }
    382373
    383     static const Node* treeMinimum(const Node* x)
     374    static const NodeType* treeMinimum(const NodeType* x)
    384375    {
    385376        while (x->left())
    … …  
    388379    }
    389380   
    390     static const Node* treeMaximum(const Node* x)
     381    static const NodeType* treeMaximum(const NodeType* x)
    391382    {
    392383        while (x->right())
    … …  
    395386    }
    396387
    397     void treeInsert(Node* z)
     388    void treeInsert(NodeType* z)
    398389    {
    399390        ASSERT(!z->left());
    … …  
    402393        ASSERT(z->color() == Red);
    403394       
    404         Node* y = 0;
    405         Node* x = m_root;
     395        NodeType* y = 0;
     396        NodeType* x = m_root;
    406397        while (x) {
    407398            y = x;
    408             if (z->m_key < x->m_key)
     399            if (z->key() < x->key())
    409400                x = x->left();
    410401            else
    … …  
    415406            m_root = z;
    416407        else {
    417             if (z->m_key < y->m_key)
     408            if (z->key() < y->key())
    418409                y->setLeft(z);
    419410            else
    … …  
    428419    // Left-rotates the subtree rooted at x.
    429420    // Returns the new root of the subtree (x's right child).
    430     Node* leftRotate(Node* x)
     421    NodeType* leftRotate(NodeType* x)
    431422    {
    432423        // Set y.
    433         Node* y = x->right();
     424        NodeType* y = x->right();
    434425
    435426        // Turn y's left subtree into x's right subtree.
    … …  
    458449    // Right-rotates the subtree rooted at y.
    459450    // Returns the new root of the subtree (y's left child).
    460     Node* rightRotate(Node* y)
     451    NodeType* rightRotate(NodeType* y)
    461452    {
    462453        // Set x.
    463         Node* x = y->left();
     454        NodeType* x = y->left();
    464455
    465456        // Turn x's right subtree into y's left subtree.
    … …  
    489480    // a node. Note that x may be null, which is why xParent must be
    490481    // supplied.
    491     void removeFixup(Node* x, Node* xParent)
     482    void removeFixup(NodeType* x, NodeType* xParent)
    492483    {
    493484        while (x != m_root && (!x || x->color() == Black)) {
    … …  
    497488                // the code; it comes about from the properties of the
    498489                // red-black tree.
    499                 Node* w = xParent->right();
     490                NodeType* w = xParent->right();
    500491                ASSERT(w); // x's sibling should not be null.
    501492                if (w->color() == Red) {
    … …  
    537528                // the code; it comes about from the properties of the
    538529                // red-black tree.
    539                 Node* w = xParent->left();
     530                NodeType* w = xParent->left();
    540531                ASSERT(w); // x's sibling should not be null.
    541532                if (w->color() == Red) {
    … …  
    575566    }
    576567
    577     Node* m_root;
     568    NodeType* m_root;
    578569};
    579570
Note: See TracChangeset for help on using the changeset viewer.