sync: Count nodes more efficiently

sync/syncable/directory.cc

 // Copyright 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "sync/syncable/directory.h"
 
 #include "base/base64.h"
 #include "base/debug/trace_event.h"
 #include "base/stl_util.h"
 #include "base/string_number_conversions.h"
@@ skipping 303 matching lines @@
 
   ScopedKernelLock lock(this);
   EntryKernel* kernel = GetEntryByHandle(handle, &lock);
   if (!kernel)
     return true;
 
   AppendChildHandles(lock, kernel->ref(ID), result);
   return true;
 }
 
+int Directory::GetTotalNodeCount(

[Nicolas Zea, 2013/05/28 22:12:39]

this seems complex enough to warrant a unit test, or are there existing ones
that cover this?

[rlarocque, 2013/05/29 19:01:13]

There are some existing tests.  See SyncApiTest.GetTotalNodeCount*.

+    BaseTransaction* trans,
+    EntryKernel* kernel) const {
+  if (!SyncAssert(this == trans->directory(), FROM_HERE,
+                  "Directories don't match", trans))
+    return false;
+
+  int count = 1;
+  std::deque<const OrderedChildSet*> child_sets;
+
+  GetTotalNodeCountImpl(trans, kernel, &child_sets);
+  while (!child_sets.empty()) {
+    const OrderedChildSet* set = child_sets.front();
+    child_sets.pop_front();
+    for (OrderedChildSet::const_iterator it = set->begin();
+         it != set->end(); ++it) {
+      count++;
+      GetTotalNodeCountImpl(trans, *it, &child_sets);
+    }
+  }
+
+  return count;
+}
+
+void Directory::GetTotalNodeCountImpl(

[rlarocque, 2013/05/21 00:09:07]

This is the main reason I wanted to use recursion.  I'm not sure how to name
this function.  If I use recursion, then this function is no longer necessary,
and the naming problem disappears.

[Nicolas Zea, 2013/05/28 22:12:39]

Seems like it's just a child grabber right? Maybe something like
GetChildrenForKernel?

That said, this method seems like it's just a wrapper for GetChildren, and isn't
used anywhere else. Given that GetTotalNodeCount isn't doing much to being with,
you could just inline this logic, and avoid the naming issue altogether.

[rlarocque, 2013/05/29 19:01:13]

I like that general idea.  I decided to go with GetChildSetForKernel.
It would have to be inlined at both line 334 and line 341.  I'd prefer to avoid
that.

+    BaseTransaction* trans,
+    EntryKernel* kernel,
+    std::deque<const OrderedChildSet*>* child_sets) const {
+  if (!kernel->ref(IS_DIR))
+    return;  // Not a directory => no children.
+
+  const OrderedChildSet* descendants =
+      kernel_->parent_child_index->GetChildren(kernel->ref(ID));
+  if (!descendants)
+    return;  // This directory has no children.
+
+  // Add our children to the list of items to be traversed.
+  child_sets->push_back(descendants);
+}
+
 EntryKernel* Directory::GetRootEntry() {
   return GetEntryById(Id());
 }
 
 bool Directory::InsertEntry(WriteTransaction* trans, EntryKernel* entry) {
   ScopedKernelLock lock(this);
   return InsertEntry(trans, entry, &lock);
 }
 
 bool Directory::InsertEntry(WriteTransaction* trans,
@@ skipping 838 matching lines @@
     result->push_back((*i)->ref(META_HANDLE));
   }
 }
 
 ScopedKernelLock::ScopedKernelLock(const Directory* dir)
   :  scoped_lock_(dir->kernel_->mutex), dir_(const_cast<Directory*>(dir)) {
 }
 
 }  // namespace syncable
 }  // namespace syncer