1// Copyright (c) 2006-2008 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/history/visit_tracker.h"
6
7#include "base/stl_util.h"
8
9namespace history {
10
11// When the list gets longer than 'MaxItems', CleanupTransitionList will resize
12// the list down to 'ResizeTo' size. This is so we only do few block moves of
13// the data rather than constantly shuffle stuff around in the vector.
14static const size_t kMaxItemsInTransitionList = 96;
15static const size_t kResizeBigTransitionListTo = 64;
16COMPILE_ASSERT(kResizeBigTransitionListTo < kMaxItemsInTransitionList,
17               max_items_must_be_larger_than_resize_to);
18
19VisitTracker::VisitTracker() {
20}
21
22VisitTracker::~VisitTracker() {
23  STLDeleteContainerPairSecondPointers(contexts_.begin(), contexts_.end());
24}
25
26// This function is potentially slow because it may do up to two brute-force
27// searches of the transitions list. This transitions list is kept to a
28// relatively small number by CleanupTransitionList so it shouldn't be a big
29// deal. However, if this ends up being noticable for performance, we may want
30// to optimize lookup.
31VisitID VisitTracker::GetLastVisit(ContextID context_id,
32                                   int32 page_id,
33                                   const GURL& referrer) {
34  if (referrer.is_empty() || !context_id)
35    return 0;
36
37  ContextList::iterator i = contexts_.find(context_id);
38  if (i == contexts_.end())
39    return 0;  // We don't have any entries for this context.
40  TransitionList& transitions = *i->second;
41
42  // Recall that a page ID is associated with a single session history entry.
43  // In the case of automatically loaded iframes, many visits/URLs can have the
44  // same page ID.
45  //
46  // We search backwards, starting at the current page ID, for the referring
47  // URL. This won't always be correct. For example, if a render process has
48  // the same page open in two different tabs, or even in two different frames,
49  // we can get confused about which was which. We can have the renderer
50  // report more precise referrer information in the future, but this is a
51  // hard problem and doesn't affect much in terms of real-world issues.
52  //
53  // We assume that the page IDs are increasing over time, so larger IDs than
54  // the current input ID happened in the future (this will occur if the user
55  // goes back). We can ignore future transitions because if you navigate, go
56  // back, and navigate some more, we'd like to have one node with two out
57  // edges in our visit graph.
58  for (int i = static_cast<int>(transitions.size()) - 1; i >= 0; i--) {
59    if (transitions[i].page_id <= page_id && transitions[i].url == referrer) {
60      // Found it.
61      return transitions[i].visit_id;
62    }
63  }
64
65  // We can't find the referrer.
66  return 0;
67}
68
69void VisitTracker::AddVisit(ContextID context_id,
70                            int32 page_id,
71                            const GURL& url,
72                            VisitID visit_id) {
73  TransitionList* transitions = contexts_[context_id];
74  if (!transitions) {
75    transitions = new TransitionList;
76    contexts_[context_id] = transitions;
77  }
78
79  Transition t;
80  t.url = url;
81  t.page_id = page_id;
82  t.visit_id = visit_id;
83  transitions->push_back(t);
84
85  CleanupTransitionList(transitions);
86}
87
88void VisitTracker::ClearCachedDataForContextID(ContextID context_id) {
89  ContextList::iterator i = contexts_.find(context_id);
90  if (i == contexts_.end())
91    return;  // We don't have any entries for this context.
92
93  delete i->second;
94  contexts_.erase(i);
95}
96
97
98void VisitTracker::CleanupTransitionList(TransitionList* transitions) {
99  if (transitions->size() <= kMaxItemsInTransitionList)
100    return;  // Nothing to do.
101
102  transitions->erase(transitions->begin(),
103                     transitions->begin() + kResizeBigTransitionListTo);
104}
105
106}  // namespace history
107