1// Copyright (c) 2011 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/profiles/profile_dependency_manager.h"
6
7#include <algorithm>
8#include <deque>
9#include <iterator>
10
11#include "chrome/browser/profiles/profile_keyed_service.h"
12#include "chrome/browser/profiles/profile_keyed_service_factory.h"
13#include "content/common/notification_service.h"
14
15class Profile;
16
17void ProfileDependencyManager::AddComponent(
18    ProfileKeyedServiceFactory* component) {
19  all_components_.push_back(component);
20  destruction_order_.clear();
21}
22
23void ProfileDependencyManager::RemoveComponent(
24    ProfileKeyedServiceFactory* component) {
25  all_components_.erase(std::remove(all_components_.begin(),
26                                    all_components_.end(),
27                                    component),
28                        all_components_.end());
29
30  // Remove all dependency edges that contain this component.
31  EdgeMap::iterator it = edges_.begin();
32  while (it != edges_.end()) {
33    EdgeMap::iterator temp = it;
34    ++it;
35
36    if (temp->first == component || temp->second == component)
37      edges_.erase(temp);
38  }
39
40  destruction_order_.clear();
41}
42
43void ProfileDependencyManager::AddEdge(ProfileKeyedServiceFactory* depended,
44                                       ProfileKeyedServiceFactory* dependee) {
45  edges_.insert(std::make_pair(depended, dependee));
46  destruction_order_.clear();
47}
48
49void ProfileDependencyManager::DestroyProfileServices(Profile* profile) {
50  if (destruction_order_.empty())
51    BuildDestructionOrder();
52
53  for (std::vector<ProfileKeyedServiceFactory*>::const_iterator it =
54           destruction_order_.begin(); it != destruction_order_.end(); ++it) {
55    (*it)->ProfileShutdown(profile);
56  }
57
58  for (std::vector<ProfileKeyedServiceFactory*>::const_iterator it =
59           destruction_order_.begin(); it != destruction_order_.end(); ++it) {
60    (*it)->ProfileDestroyed(profile);
61  }
62}
63
64// static
65ProfileDependencyManager* ProfileDependencyManager::GetInstance() {
66  return Singleton<ProfileDependencyManager>::get();
67}
68
69ProfileDependencyManager::ProfileDependencyManager() {}
70
71ProfileDependencyManager::~ProfileDependencyManager() {}
72
73void ProfileDependencyManager::BuildDestructionOrder() {
74  // Step 1: Build a set of nodes with no incoming edges.
75  std::deque<ProfileKeyedServiceFactory*> queue;
76  std::copy(all_components_.begin(),
77            all_components_.end(),
78            std::back_inserter(queue));
79
80  std::deque<ProfileKeyedServiceFactory*>::iterator queue_end = queue.end();
81  for (EdgeMap::const_iterator it = edges_.begin();
82       it != edges_.end(); ++it) {
83    queue_end = std::remove(queue.begin(), queue_end, it->second);
84  }
85  queue.erase(queue_end, queue.end());
86
87  // Step 2: Do the Kahn topological sort.
88  std::vector<ProfileKeyedServiceFactory*> output;
89  EdgeMap edges(edges_);
90  while (!queue.empty()) {
91    ProfileKeyedServiceFactory* node = queue.front();
92    queue.pop_front();
93    output.push_back(node);
94
95    std::pair<EdgeMap::iterator, EdgeMap::iterator> range =
96        edges.equal_range(node);
97    EdgeMap::iterator it = range.first;
98    while (it != range.second) {
99      ProfileKeyedServiceFactory* dest = it->second;
100      EdgeMap::iterator temp = it;
101      it++;
102      edges.erase(temp);
103
104      bool has_incoming_edges = false;
105      for (EdgeMap::iterator jt = edges.begin(); jt != edges.end(); ++jt) {
106        if (jt->second == dest) {
107          has_incoming_edges = true;
108          break;
109        }
110      }
111
112      if (!has_incoming_edges)
113        queue.push_back(dest);
114    }
115  }
116
117  if (edges.size()) {
118    NOTREACHED() << "Dependency graph has a cycle. We are doomed.";
119  }
120
121  std::reverse(output.begin(), output.end());
122  destruction_order_ = output;
123}
124