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(
+    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;
+
+  GetChildSetForKernel(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++;
+      GetChildSetForKernel(trans, *it, &child_sets);
+    }
+  }
+
+  return count;
+}
+
+void Directory::GetChildSetForKernel(
+    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