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 #ifndef CHROME_BROWSER_SYNC_FILE_SYSTEM_SUBTREE_SET_H_ 6 #define CHROME_BROWSER_SYNC_FILE_SYSTEM_SUBTREE_SET_H_ 7 8 #include "base/containers/hash_tables.h" 9 #include "base/files/file_path.h" 10 11 namespace base { 12 class FilePath; 13 } // namespace base 14 15 namespace sync_file_system { 16 17 // Stores disjoint subtrees of a directory tree. 18 class SubtreeSet { 19 public: 20 SubtreeSet(); 21 ~SubtreeSet(); 22 23 // Returns true if the subtree induced by |subtree_root| is disjoint with 24 // all subtrees in the container. 25 bool IsDisjointWith(const base::FilePath& subtree_root) const; 26 27 // Returns true and inserts the subtree induced by |subtree_root| if the 28 // subtree is disjoint with all subtrees in the container. 29 bool insert(const base::FilePath& subtree_root); 30 31 // Erases the subtree induced by |subtree_root| from the container. 32 // Returns true if this erases the subtree. 33 bool erase(const base::FilePath& subtree_root); 34 35 size_t size() const; empty()36 bool empty() const { return inclusive_ancestors_of_subtree_roots_.empty(); } 37 38 private: 39 struct Node { 40 bool contained_as_subtree_root; 41 size_t number_of_subtrees_below; 42 43 Node(); 44 Node(bool contained_as_subtree_root, 45 size_t number_of_subtrees_below); 46 }; 47 48 typedef base::FilePath::StringType StringType; 49 typedef base::hash_map<StringType, Node> Subtrees; 50 51 // Contains the root of subtrees and all upward node to root. 52 // Each subtree root has |contained_as_subtree_root| flag true. 53 Subtrees inclusive_ancestors_of_subtree_roots_; 54 }; 55 56 } // namespace sync_file_system 57 58 #endif // CHROME_BROWSER_SYNC_FILE_SYSTEM_SUBTREE_SET_H_ 59