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 Node()13SubtreeSet::Node::Node() 14 : contained_as_subtree_root(false), 15 number_of_subtrees_below(0) { 16 } 17 Node(bool contained_as_subtree_root,size_t number_of_subtrees_below)18SubtreeSet::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 SubtreeSet()24SubtreeSet::SubtreeSet() {} ~SubtreeSet()25SubtreeSet::~SubtreeSet() {} 26 IsDisjointWith(const base::FilePath & subtree_root) const27bool 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 insert(const base::FilePath & subtree_root)49bool 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 erase(const base::FilePath & subtree_root)70bool 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 size() const104size_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 113