chrome/browser/sync_file_system/subtree_set.h

   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;
  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_