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