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#include "chrome/browser/sync_file_system/subtree_set.h"
6
7#include "base/logging.h"
8#include "base/stl_util.h"
9#include "storage/common/fileapi/file_system_util.h"
10
11namespace sync_file_system {
12
13SubtreeSet::Node::Node()
14    : contained_as_subtree_root(false),
15      number_of_subtrees_below(0) {
16}
17
18SubtreeSet::Node::Node(bool contained_as_subtree_root,
19                       size_t number_of_subtrees_below)
20    : contained_as_subtree_root(contained_as_subtree_root),
21      number_of_subtrees_below(number_of_subtrees_below) {
22}
23
24SubtreeSet::SubtreeSet() {}
25SubtreeSet::~SubtreeSet() {}
26
27bool SubtreeSet::IsDisjointWith(const base::FilePath& subtree_root) const {
28  base::FilePath::StringType normalized_subtree_root =
29      storage::VirtualPath::GetNormalizedFilePath(subtree_root);
30
31  // Check if |subtree_root| contains any of subtrees in the container.
32  if (ContainsKey(inclusive_ancestors_of_subtree_roots_,
33                  normalized_subtree_root))
34    return false;
35
36  base::FilePath path(normalized_subtree_root);
37  while (!storage::VirtualPath::IsRootPath(path)) {
38    path = storage::VirtualPath::DirName(path);
39
40    Subtrees::const_iterator found =
41        inclusive_ancestors_of_subtree_roots_.find(path.value());
42    if (found != inclusive_ancestors_of_subtree_roots_.end())
43      return !found->second.contained_as_subtree_root;
44  }
45
46  return true;
47}
48
49bool SubtreeSet::insert(const base::FilePath& subtree_root) {
50  base::FilePath::StringType normalized_subtree_root =
51      storage::VirtualPath::GetNormalizedFilePath(subtree_root);
52
53  if (!IsDisjointWith(subtree_root))
54    return false;
55  inclusive_ancestors_of_subtree_roots_[normalized_subtree_root]
56      = Node(true, 1);
57
58  base::FilePath path(normalized_subtree_root);
59  while (!storage::VirtualPath::IsRootPath(path)) {
60    path = storage::VirtualPath::DirName(path);
61    DCHECK(!inclusive_ancestors_of_subtree_roots_[path.value()]
62                .contained_as_subtree_root);
63    ++(inclusive_ancestors_of_subtree_roots_[path.value()]
64           .number_of_subtrees_below);
65  }
66
67  return true;
68}
69
70bool SubtreeSet::erase(const base::FilePath& subtree_root) {
71  base::FilePath::StringType normalized_subtree_root =
72      storage::VirtualPath::GetNormalizedFilePath(subtree_root);
73
74  {
75    Subtrees::iterator found =
76        inclusive_ancestors_of_subtree_roots_.find(normalized_subtree_root);
77    if (found == inclusive_ancestors_of_subtree_roots_.end() ||
78        !found->second.contained_as_subtree_root)
79      return false;
80
81    DCHECK_EQ(1u, found->second.number_of_subtrees_below);
82    inclusive_ancestors_of_subtree_roots_.erase(found);
83  }
84
85  base::FilePath path(normalized_subtree_root);
86  while (!storage::VirtualPath::IsRootPath(path)) {
87    path = storage::VirtualPath::DirName(path);
88
89    Subtrees::iterator found =
90        inclusive_ancestors_of_subtree_roots_.find(path.value());
91    if (found == inclusive_ancestors_of_subtree_roots_.end()) {
92      NOTREACHED();
93      continue;
94    }
95
96    DCHECK(!found->second.contained_as_subtree_root);
97    if (!--(found->second.number_of_subtrees_below))
98      inclusive_ancestors_of_subtree_roots_.erase(found);
99  }
100
101  return true;
102}
103
104size_t SubtreeSet::size() const {
105  Subtrees::const_iterator found =
106      inclusive_ancestors_of_subtree_roots_.find(storage::VirtualPath::kRoot);
107  if (found == inclusive_ancestors_of_subtree_roots_.end())
108    return 0;
109  return found->second.number_of_subtrees_below;
110}
111
112}  // namespace sync_file_system
113