subtree_set.h revision a1401311d1ab56c4ed0a474bd38c108f75cb0cd9 
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
11namespace base {
12class FilePath;
13}  // namespace base
14
15namespace sync_file_system {
16
17// Stores disjoint subtrees of a directory tree.
18class 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_
59