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