Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily, r=mak
authorMilindL <i.milind.luthra@gmail.com>
Thu, 08 Jun 2017 20:51:51 +0530
changeset 365783 87b2b354ed01650863638342d58a8d2496f4797a
parent 365782 c0772946156f06a6d8fd6748a4f28b14b6855181
child 365784 8bfdb27038606dce09409dd5721ab009b8f701f7
push id32089
push usercbook@mozilla.com
push dateMon, 26 Jun 2017 11:24:06 +0000
treeherdermozilla-central@42593af5ec7e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersmak
bugs1107364
milestone56.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1107364 - remove findNodeByDetails and maintain a map to fetch a node by details speedily, r=mak This patch removes the interface/header/implementation. This adds a Map to PlacesTreeView to maintain the relation between node details and the nodes, based on changes in `this._rows` or on node details changed events. The Map exists from node details to nodes (not rows). MozReview-Commit-ID: EUNiXNIB5rN
browser/components/places/content/treeView.js
toolkit/components/places/nsINavHistoryService.idl
toolkit/components/places/nsNavHistoryResult.cpp
toolkit/components/places/nsNavHistoryResult.h
--- a/browser/components/places/content/treeView.js
+++ b/browser/components/places/content/treeView.js
@@ -5,23 +5,49 @@
 Components.utils.import("resource://gre/modules/XPCOMUtils.jsm");
 Components.utils.import("resource://gre/modules/Services.jsm");
 
 const PTV_interfaces = [Ci.nsITreeView,
                         Ci.nsINavHistoryResultObserver,
                         Ci.nsINavHistoryResultTreeViewer,
                         Ci.nsISupportsWeakReference];
 
+/**
+ * This returns the key for any node/details object.
+ *
+ * @param nodeOrDetails
+ *        A node, or an object containing the following properties:
+ *        - uri
+ *        - time
+ *        - itemId
+ *        In case any of these is missing, an empty string will be returned. This is
+ *        to facilitate easy delete statements which occur due to assignment to items in `this._rows`,
+ *        since the item we are deleting may be undefined in the array.
+ *
+ * @return key or empty string.
+ */
+function makeNodeDetailsKey(nodeOrDetails) {
+  if (nodeOrDetails &&
+      typeof nodeOrDetails === "object" &&
+      "uri" in nodeOrDetails &&
+      "time" in nodeOrDetails &&
+      "itemId" in nodeOrDetails) {
+    return `${nodeOrDetails.uri}*${nodeOrDetails.time}*${nodeOrDetails.itemId}`;
+  }
+  return "";
+}
+
 function PlacesTreeView(aFlatList, aOnOpenFlatContainer, aController) {
   this._tree = null;
   this._result = null;
   this._selection = null;
   this._rootNode = null;
   this._rows = [];
   this._flatList = aFlatList;
+  this._nodeDetails = new Map();
   this._openContainerCallback = aOnOpenFlatContainer;
   this._controller = aController;
 }
 
 PlacesTreeView.prototype = {
   get wrappedJSObject() {
     return this;
   },
@@ -182,18 +208,21 @@ PlacesTreeView.prototype = {
       row = this._rows.indexOf(aNode, aParentRow);
       if (row == -1 && aForceBuild) {
         let parentRow = typeof(aParentRow) == "number" ? aParentRow
                                                        : this._getRowForNode(parent);
         row = parentRow + parent.getChildIndex(aNode) + 1;
       }
     }
 
-    if (row != -1)
+    if (row != -1) {
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[row]));
+      this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
       this._rows[row] = aNode;
+    }
 
     return row;
   },
 
   /**
    * Given a row, finds and returns the parent details of the associated node.
    *
    * @param aChildRow
@@ -228,26 +257,37 @@ PlacesTreeView.prototype = {
     let rowNode, row;
     for (let i = aRow - 1; i >= 0 && rowNode === undefined; i--) {
       rowNode = this._rows[i];
       row = i;
     }
 
     // If there's no container prior to the given row, it's a child of
     // the root node (remember: all containers are listed in the rows array).
-    if (!rowNode)
-      return this._rows[aRow] = this._rootNode.getChild(aRow);
+    if (!rowNode) {
+      let newNode = this._rootNode.getChild(aRow);
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[aRow]));
+      this._nodeDetails.set(makeNodeDetailsKey(newNode), newNode);
+      return this._rows[aRow] = newNode;
+    }
 
     // Unset elements may exist only in plain containers.  Thus, if the nearest
     // node is a container, it's the row's parent, otherwise, it's a sibling.
-    if (rowNode instanceof Ci.nsINavHistoryContainerResultNode)
-      return this._rows[aRow] = rowNode.getChild(aRow - row - 1);
+    if (rowNode instanceof Ci.nsINavHistoryContainerResultNode) {
+      let newNode = rowNode.getChild(aRow - row - 1);
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[aRow]));
+      this._nodeDetails.set(makeNodeDetailsKey(newNode), newNode);
+      return this._rows[aRow] = newNode;
+    }
 
     let [parent, parentRow] = this._getParentByChildRow(row);
-    return this._rows[aRow] = parent.getChild(aRow - parentRow - 1);
+    let newNode = parent.getChild(aRow - parentRow - 1);
+    this._nodeDetails.delete(makeNodeDetailsKey(this._rows[aRow]));
+    this._nodeDetails.set(makeNodeDetailsKey(newNode), newNode);
+    return this._rows[aRow] = newNode;
   },
 
   /**
    * This takes a container and recursively appends our rows array per its
    * contents.  Assumes that the rows arrays has no rows for the given
    * container.
    *
    * @param [in] aContainer
@@ -266,16 +306,20 @@ PlacesTreeView.prototype = {
     if (!aContainer.containerOpen)
       return 0;
 
     // Inserting the new elements into the rows array in one shot (by
     // Array.prototype.concat) is faster than resizing the array (by splice) on each loop
     // iteration.
     let cc = aContainer.childCount;
     let newElements = new Array(cc);
+    // We need to clean up the node details from aFirstChildRow + 1 to the end of rows.
+    for (let i = aFirstChildRow + 1; i < this._rows.length; i++) {
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[i]));
+    }
     this._rows = this._rows.splice(0, aFirstChildRow)
                      .concat(newElements, this._rows);
 
     if (this._isPlainContainer(aContainer))
       return cc;
 
     let sortingMode = this._result.sortingMode;
 
@@ -287,21 +331,24 @@ PlacesTreeView.prototype = {
       let row = aFirstChildRow + rowsInserted;
 
       // Don't display separators when sorted.
       if (curChildType == Ci.nsINavHistoryResultNode.RESULT_TYPE_SEPARATOR) {
         if (sortingMode != Ci.nsINavHistoryQueryOptions.SORT_BY_NONE) {
           // Remove the element for the filtered separator.
           // Notice that the rows array was initially resized to include all
           // children.
+          this._nodeDetails.delete(makeNodeDetailsKey(this._rows[row]));
           this._rows.splice(row, 1);
           continue;
         }
       }
 
+      this._nodeDetails.delete(makeNodeDetailsKey(this._rows[row]));
+      this._nodeDetails.set(makeNodeDetailsKey(curChild), curChild);
       this._rows[row] = curChild;
       rowsInserted++;
 
       // Recursively do containers.
       if (!this._flatList &&
           curChild instanceof Ci.nsINavHistoryContainerResultNode &&
           !this._controller.hasCachedLivemarkInfo(curChild)) {
         let uri = curChild.uri;
@@ -402,32 +449,31 @@ PlacesTreeView.prototype = {
     let parent = aOldNode.parent;
     if (parent) {
       // If the node's parent is still set, the node is not obsolete
       // and we should just find out its new position.
       // However, if any of the node's ancestor is closed, the node is
       // invisible.
       let ancestors = PlacesUtils.nodeAncestors(aOldNode);
       for (let ancestor of ancestors) {
-        if (!ancestor.containerOpen)
+        if (!ancestor.containerOpen) {
           return -1;
+        }
       }
 
       return this._getRowForNode(aOldNode, true);
     }
 
     // There's a broken edge case here.
     // If a visit appears in two queries, and the second one was
     // the old node, we'll select the first one after refresh.  There's
     // nothing we could do about that, because aOldNode.parent is
     // gone by the time invalidateContainer is called.
-    let newNode = aUpdatedContainer.findNodeByDetails(aOldNode.uri,
-                                                      aOldNode.time,
-                                                      aOldNode.itemId,
-                                                      true);
+    let newNode = this._nodeDetails.get(makeNodeDetailsKey(aOldNode));
+
     if (!newNode)
       return -1;
 
     return this._getRowForNode(newNode, true);
   },
 
   /**
    * Restores a given selection state as near as possible to the original
@@ -644,16 +690,17 @@ PlacesTreeView.prototype = {
         // in our list takes up (it could be a container with many children).
         let prevChild = aParentNode.getChild(aNewIndex - 1);
         let prevIndex = this._getRowForNode(prevChild, false, parentRow,
                                             aNewIndex - 1);
         row = prevIndex + this._countVisibleRowsForNodeAtRow(prevIndex);
       }
     }
 
+    this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
     this._rows.splice(row, 0, aNode);
     this._tree.rowCountChanged(row, 1);
 
     if (PlacesUtils.nodeIsContainer(aNode) &&
         PlacesUtils.asContainer(aNode).containerOpen) {
       this.invalidateContainer(aNode);
     }
   },
@@ -695,17 +742,19 @@ PlacesTreeView.prototype = {
       selection.getRangeAt(0, min, max);
       if (min.value == max.value &&
           this.nodeForTreeIndex(min.value) == aNode)
         selectNext = true;
     }
 
     // Remove the node and its children, if any.
     let count = this._countVisibleRowsForNodeAtRow(oldRow);
-    this._rows.splice(oldRow, count);
+    for (let splicedNode of this._rows.splice(oldRow, count)) {
+      this._nodeDetails.delete(makeNodeDetailsKey(splicedNode));
+    }
     this._tree.rowCountChanged(oldRow, -count);
 
     // Redraw the parent if its twisty state has changed.
     if (aParentNode != this._rootNode && !aParentNode.hasChildren) {
       parentRow = oldRow - 1;
       this._tree.invalidateRow(parentRow);
     }
 
@@ -748,17 +797,19 @@ PlacesTreeView.prototype = {
 
     // Redraw the parent if its twisty state has changed.
     if (aOldParent != this._rootNode && !aOldParent.hasChildren) {
       let parentRow = oldRow - 1;
       this._tree.invalidateRow(parentRow);
     }
 
     // Remove node and its children, if any, from the old position.
-    this._rows.splice(oldRow, count);
+    for (let splicedNode of this._rows.splice(oldRow, count)) {
+      this._nodeDetails.delete(makeNodeDetailsKey(splicedNode));
+    }
     this._tree.rowCountChanged(oldRow, -count);
 
     // Insert the node into the new position.
     this.nodeInserted(aNewParent, aNode, aNewIndex);
 
     // Restore selection.
     if (nodesToReselect.length > 0) {
       this._restoreSelection(nodesToReselect, aNewParent);
@@ -812,26 +863,34 @@ PlacesTreeView.prototype = {
       }, Components.utils.reportError);
   },
 
   nodeTitleChanged: function PTV_nodeTitleChanged(aNode, aNewTitle) {
     this._invalidateCellValue(aNode, this.COLUMN_TYPE_TITLE);
   },
 
   nodeURIChanged: function PTV_nodeURIChanged(aNode, aOldURI) {
+    this._nodeDetails.delete(makeNodeDetailsKey({uri: aOldURI,
+                                                 itemId: aNode.itemId,
+                                                 time: aNode.time}));
+    this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
     this._invalidateCellValue(aNode, this.COLUMN_TYPE_URI);
   },
 
   nodeIconChanged: function PTV_nodeIconChanged(aNode) {
     this._invalidateCellValue(aNode, this.COLUMN_TYPE_TITLE);
   },
 
   nodeHistoryDetailsChanged:
   function PTV_nodeHistoryDetailsChanged(aNode, aOldVisitDate,
                                          aOldVisitCount) {
+    this._nodeDetails.delete(makeNodeDetailsKey({uri: aNode.uri,
+                                                 itemId: aNode.itemId,
+                                                 time: aOldVisitDate}));
+    this._nodeDetails.set(makeNodeDetailsKey(aNode), aNode);
     if (aNode.parent && this._controller.hasCachedLivemarkInfo(aNode.parent)) {
       // Find the node in the parent.
       let parentRow = this._flatList ? 0 : this._getRowForNode(aNode.parent);
       for (let i = parentRow; i < this._rows.length; i++) {
         let child = this.nodeForTreeIndex(i);
         if (child.uri == aNode.uri) {
           this._cellProperties.delete(child);
           this._invalidateCellValue(child, this.COLUMN_TYPE_TITLE);
@@ -913,16 +972,17 @@ PlacesTreeView.prototype = {
 
     let startReplacement, replaceCount;
     if (aContainer == this._rootNode) {
       startReplacement = 0;
       replaceCount = this._rows.length;
 
       // If the root node is now closed, the tree is empty.
       if (!this._rootNode.containerOpen) {
+        this._nodeDetails.clear();
         this._rows = [];
         if (replaceCount)
           this._tree.rowCountChanged(startReplacement, -replaceCount);
 
         return;
       }
     } else {
       // Update the twisty state.
@@ -939,17 +999,19 @@ PlacesTreeView.prototype = {
     let nodesToReselect =
       this._getSelectedNodesInRange(startReplacement,
                                     startReplacement + replaceCount);
 
     // Now update the number of elements.
     this.selection.selectEventsSuppressed = true;
 
     // First remove the old elements
-    this._rows.splice(startReplacement, replaceCount);
+    for (let splicedNode of this._rows.splice(startReplacement, replaceCount)) {
+      this._nodeDetails.delete(makeNodeDetailsKey(splicedNode));
+    }
 
     // If the container is now closed, we're done.
     if (!aContainer.containerOpen) {
       let oldSelectionCount = this.selection.count;
       if (replaceCount)
         this._tree.rowCountChanged(startReplacement, -replaceCount);
 
       // Select the row next to the closed container if any of its
--- a/toolkit/components/places/nsINavHistoryService.idl
+++ b/toolkit/components/places/nsINavHistoryService.idl
@@ -248,38 +248,16 @@ interface nsINavHistoryContainerResultNo
    *        a result node.
    *
    * @return aNode's index in this container.
    * @throws NS_ERROR_NOT_AVAILABLE if containerOpen is false.
    * @throws NS_ERROR_INVALID_ARG if aNode isn't a direct child of this
    * container.
    */
   unsigned long getChildIndex(in nsINavHistoryResultNode aNode);
-
-  /**
-   * Look for a node in the container by some of its details.  Does not search
-   * closed containers.
-   *
-   * @param aURI
-   *        the node's uri attribute value
-   * @param aTime
-   *        the node's time attribute value.
-   * @param aItemId
-   *        the node's itemId attribute value.
-   * @param aRecursive
-   *        whether or not to search recursively.
-   *
-   * @throws NS_ERROR_NOT_AVAILABLE if this container is closed.
-   * @return a result node that matches the given details if any, null
-   *         otherwise.
-   */
-  nsINavHistoryResultNode findNodeByDetails(in AUTF8String aURIString,
-                                            in PRTime aTime,
-                                            in long long aItemId,
-                                            in boolean aRecursive);
 };
 
 
 /**
  * Used for places queries and as a base for bookmark folders.
  *
  * Note that if you request places to *not* be expanded in the options that
  * generated this node, this item will report it has no children and never try
--- a/toolkit/components/places/nsNavHistoryResult.cpp
+++ b/toolkit/components/places/nsNavHistoryResult.cpp
@@ -1703,53 +1703,16 @@ nsNavHistoryContainerResultNode::GetChil
   int32_t nodeIndex = FindChild(static_cast<nsNavHistoryResultNode*>(aNode));
   if (nodeIndex == -1)
     return NS_ERROR_INVALID_ARG;
 
   *_retval = nodeIndex;
   return NS_OK;
 }
 
-
-NS_IMETHODIMP
-nsNavHistoryContainerResultNode::FindNodeByDetails(const nsACString& aURIString,
-                                                   PRTime aTime,
-                                                   int64_t aItemId,
-                                                   bool aRecursive,
-                                                   nsINavHistoryResultNode** _retval) {
-  if (!mExpanded)
-    return NS_ERROR_NOT_AVAILABLE;
-
-  *_retval = nullptr;
-  for (int32_t i = 0; i < mChildren.Count(); ++i) {
-    if (mChildren[i]->mURI.Equals(aURIString) &&
-        mChildren[i]->mTime == aTime &&
-        mChildren[i]->mItemId == aItemId) {
-      *_retval = mChildren[i];
-      break;
-    }
-
-    if (aRecursive && mChildren[i]->IsContainer()) {
-      nsNavHistoryContainerResultNode* asContainer =
-        mChildren[i]->GetAsContainer();
-      if (asContainer->mExpanded) {
-        nsresult rv = asContainer->FindNodeByDetails(aURIString, aTime,
-                                                     aItemId,
-                                                     aRecursive,
-                                                     _retval);
-
-        if (NS_SUCCEEDED(rv) && _retval)
-          break;
-      }
-    }
-  }
-  NS_IF_ADDREF(*_retval);
-  return NS_OK;
-}
-
 /**
  * HOW QUERY UPDATING WORKS
  *
  * Queries are different than bookmark folders in that we can not always do
  * dynamic updates (easily) and updates are more expensive.  Therefore, we do
  * NOT query if we are not open and want to see if we have any children (for
  * drawing a twisty) and always assume we will.
  *
--- a/toolkit/components/places/nsNavHistoryResult.h
+++ b/toolkit/components/places/nsNavHistoryResult.h
@@ -414,21 +414,16 @@ NS_DEFINE_STATIC_IID_ACCESSOR(nsNavHisto
   NS_IMETHOD SetContainerOpen(bool aContainerOpen) override \
     { return nsNavHistoryContainerResultNode::SetContainerOpen(aContainerOpen); } \
   NS_IMETHOD GetChildCount(uint32_t *aChildCount) override \
     { return nsNavHistoryContainerResultNode::GetChildCount(aChildCount); } \
   NS_IMETHOD GetChild(uint32_t index, nsINavHistoryResultNode **_retval) override \
     { return nsNavHistoryContainerResultNode::GetChild(index, _retval); } \
   NS_IMETHOD GetChildIndex(nsINavHistoryResultNode* aNode, uint32_t* _retval) override \
     { return nsNavHistoryContainerResultNode::GetChildIndex(aNode, _retval); } \
-  NS_IMETHOD FindNodeByDetails(const nsACString& aURIString, PRTime aTime, \
-                               int64_t aItemId, bool aRecursive, \
-                               nsINavHistoryResultNode** _retval) override \
-    { return nsNavHistoryContainerResultNode::FindNodeByDetails(aURIString, aTime, aItemId, \
-                                                                aRecursive, _retval); }
 
 #define NS_NAVHISTORYCONTAINERRESULTNODE_IID \
   { 0x6e3bf8d3, 0x22aa, 0x4065, { 0x86, 0xbc, 0x37, 0x46, 0xb5, 0xb3, 0x2c, 0xe8 } }
 
 class nsNavHistoryContainerResultNode : public nsNavHistoryResultNode,
                                         public nsINavHistoryContainerResultNode
 {
 public: