src/chrome/browser/sync_file_system/subtree_set.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "chrome/browser/sync_file_system/subtree_set.h"
   6
   7 #include "base/logging.h"
   8 #include "base/stl_util.h"
   9 #include "storage/common/fileapi/file_system_util.h"
  10
  11 namespace sync_file_system {
  12
  13 SubtreeSet::Node::Node()
  14     : contained_as_subtree_root(false),
  15       number_of_subtrees_below(0) {
  16 }
  17
  18 SubtreeSet::Node::Node(bool contained_as_subtree_root,
  19                        size_t number_of_subtrees_below)
  20     : contained_as_subtree_root(contained_as_subtree_root),
  21       number_of_subtrees_below(number_of_subtrees_below) {
  22 }
  23
  24 SubtreeSet::SubtreeSet() {}
  25 SubtreeSet::~SubtreeSet() {}
  26
  27 bool SubtreeSet::IsDisjointWith(const base::FilePath& subtree_root) const {
  28   base::FilePath::StringType normalized_subtree_root =
  29       storage::VirtualPath::GetNormalizedFilePath(subtree_root);
  30
  31   // Check if |subtree_root| contains any of subtrees in the container.
  32   if (ContainsKey(inclusive_ancestors_of_subtree_roots_,
  33                   normalized_subtree_root))
  34     return false;
  35
  36   base::FilePath path(normalized_subtree_root);
  37   while (!storage::VirtualPath::IsRootPath(path)) {
  38     path = storage::VirtualPath::DirName(path);
  39
  40     Subtrees::const_iterator found =
  41         inclusive_ancestors_of_subtree_roots_.find(path.value());
  42     if (found != inclusive_ancestors_of_subtree_roots_.end())
  43       return !found->second.contained_as_subtree_root;
  44   }
  45
  46   return true;
  47 }
  48
  49 bool SubtreeSet::insert(const base::FilePath& subtree_root) {
  50   base::FilePath::StringType normalized_subtree_root =
  51       storage::VirtualPath::GetNormalizedFilePath(subtree_root);
  52
  53   if (!IsDisjointWith(subtree_root))
  54     return false;
  55   inclusive_ancestors_of_subtree_roots_[normalized_subtree_root]
  56       = Node(true, 1);
  57
  58   base::FilePath path(normalized_subtree_root);
  59   while (!storage::VirtualPath::IsRootPath(path)) {
  60     path = storage::VirtualPath::DirName(path);
  61     DCHECK(!inclusive_ancestors_of_subtree_roots_[path.value()]
  62                 .contained_as_subtree_root);
  63     ++(inclusive_ancestors_of_subtree_roots_[path.value()]
  64            .number_of_subtrees_below);
  65   }
  66
  67   return true;
  68 }
  69
  70 bool SubtreeSet::erase(const base::FilePath& subtree_root) {
  71   base::FilePath::StringType normalized_subtree_root =
  72       storage::VirtualPath::GetNormalizedFilePath(subtree_root);
  73
  74   {
  75     Subtrees::iterator found =
  76         inclusive_ancestors_of_subtree_roots_.find(normalized_subtree_root);
  77     if (found == inclusive_ancestors_of_subtree_roots_.end() ||
  78         !found->second.contained_as_subtree_root)
  79       return false;
  80
  81     DCHECK_EQ(1u, found->second.number_of_subtrees_below);
  82     inclusive_ancestors_of_subtree_roots_.erase(found);
  83   }
  84
  85   base::FilePath path(normalized_subtree_root);
  86   while (!storage::VirtualPath::IsRootPath(path)) {
  87     path = storage::VirtualPath::DirName(path);
  88
  89     Subtrees::iterator found =
  90         inclusive_ancestors_of_subtree_roots_.find(path.value());
  91     if (found == inclusive_ancestors_of_subtree_roots_.end()) {
  92       NOTREACHED();
  93       continue;
  94     }
  95
  96     DCHECK(!found->second.contained_as_subtree_root);
  97     if (!--(found->second.number_of_subtrees_below))
  98       inclusive_ancestors_of_subtree_roots_.erase(found);
  99   }
 100
 101   return true;
 102 }
 103
 104 size_t SubtreeSet::size() const {
 105   Subtrees::const_iterator found =
 106       inclusive_ancestors_of_subtree_roots_.find(storage::VirtualPath::kRoot);
 107   if (found == inclusive_ancestors_of_subtree_roots_.end())
 108     return 0;
 109   return found->second.number_of_subtrees_below;
 110 }
 111
 112 }  // namespace sync_file_system