Make HTMLSlotElement.distributedNodeNextTo&distributedNodePreviousTo faster

third_party/WebKit/Source/core/html/HTMLSlotElement.h

 /*
  * Copyright (C) 2015 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 32 matching lines @@
 public:
     DECLARE_NODE_FACTORY(HTMLSlotElement);
 
     const WillBeHeapVector<RefPtrWillBeMember<Node>>& getAssignedNodes() const { ASSERT(!needsDistributionRecalc()); return m_assignedNodes; }
     const WillBeHeapVector<RefPtrWillBeMember<Node>>& getDistributedNodes();
     const WillBeHeapVector<RefPtrWillBeMember<Node>> getAssignedNodesForBinding(const AssignedNodesOptions&);
 
     Node* firstDistributedNode() const { return m_distributedNodes.isEmpty() ? nullptr : m_distributedNodes.first().get(); }
     Node* lastDistributedNode() const { return m_distributedNodes.isEmpty() ? nullptr : m_distributedNodes.last().get(); }
 
     // TODO(hayato): This takes O(N). Make it O(1) with node-to-index hash table.

[kochi, 2016/01/27 10:53:15]

You should remove this TODO.

[yuzuchan, 2016/02/01 05:40:42]

Done.

     Node* distributedNodeNextTo(const Node&) const;
     Node* distributedNodePreviousTo(const Node&) const;
 
     void appendAssignedNode(Node&);
     void appendDistributedNode(Node&);
     void appendDistributedNodesFrom(const HTMLSlotElement& other);
     void clearDistribution();
 
     void updateDistributedNodesWithFallback();
 
     void attach(const AttachContext& = AttachContext()) override;
     void detach(const AttachContext& = AttachContext()) override;
 
     void attributeChanged(const QualifiedName&, const AtomicString& oldValue, const AtomicString& newValue, AttributeModificationReason = ModifiedDirectly) override;
 
     DECLARE_VIRTUAL_TRACE();
 
 protected:
     void childrenChanged(const ChildrenChange&) override;
     InsertionNotificationRequest insertedInto(ContainerNode*) override;
     void removedFrom(ContainerNode*) override;
 
 private:
     HTMLSlotElement(Document&);
 
     WillBeHeapVector<RefPtrWillBeMember<Node>> m_assignedNodes;
-    // TODO(hayato): Share code with DistributedNode class

[kochi, 2016/01/27 08:29:14]

Does this CL really address this TODO?

[yuzuchan, 2016/02/01 05:40:42]

I have decided to use a hash table here instead of sharing the code with
DistributedNode, since DistributedNode will be discarded anyway.

     WillBeHeapVector<RefPtrWillBeMember<Node>> m_distributedNodes;
+    WillBeHeapHashMap<RawPtrWillBeMember<const Node>, size_t> m_distributedIndices;
 };
 
 } // namespace blink
 
 #endif // HTMLSlotElement_h