OLD | NEW |
1 // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef COMPONENTS_VISITEDLINK_COMMON_VISITEDLINK_COMMON_H_ | 5 #ifndef COMPONENTS_VISITEDLINK_COMMON_VISITEDLINK_COMMON_H_ |
6 #define COMPONENTS_VISITEDLINK_COMMON_VISITEDLINK_COMMON_H_ | 6 #define COMPONENTS_VISITEDLINK_COMMON_VISITEDLINK_COMMON_H_ |
7 | 7 |
| 8 #include <stddef.h> |
| 9 #include <stdint.h> |
| 10 |
8 #include <vector> | 11 #include <vector> |
9 | 12 |
10 #include "base/basictypes.h" | 13 #include "base/macros.h" |
11 | 14 |
12 class GURL; | 15 class GURL; |
13 | 16 |
14 namespace visitedlink { | 17 namespace visitedlink { |
15 | 18 |
16 // number of bytes in the salt | 19 // number of bytes in the salt |
17 #define LINK_SALT_LENGTH 8 | 20 #define LINK_SALT_LENGTH 8 |
18 | 21 |
19 // A multiprocess-safe database of the visited links for the browser. There | 22 // A multiprocess-safe database of the visited links for the browser. There |
20 // should be exactly one process that has write access (implemented by | 23 // should be exactly one process that has write access (implemented by |
(...skipping 17 matching lines...) Expand all Loading... |
38 // To ask whether a page is in history, we compute a 64-bit fingerprint of the | 41 // To ask whether a page is in history, we compute a 64-bit fingerprint of the |
39 // URL. This URL is hashed and we see if it is in the URL hashtable. If it is, | 42 // URL. This URL is hashed and we see if it is in the URL hashtable. If it is, |
40 // we consider it visited. Otherwise, it is unvisited. Note that it is possible | 43 // we consider it visited. Otherwise, it is unvisited. Note that it is possible |
41 // to get collisions, which is the penalty for not storing all URL strings in | 44 // to get collisions, which is the penalty for not storing all URL strings in |
42 // memory (which could get to be more than we want to have in memory). We use | 45 // memory (which could get to be more than we want to have in memory). We use |
43 // a salt value for the links on one computer so that an attacker can not | 46 // a salt value for the links on one computer so that an attacker can not |
44 // manually create a link that causes a collision. | 47 // manually create a link that causes a collision. |
45 class VisitedLinkCommon { | 48 class VisitedLinkCommon { |
46 public: | 49 public: |
47 // A number that identifies the URL. | 50 // A number that identifies the URL. |
48 typedef uint64 Fingerprint; | 51 typedef uint64_t Fingerprint; |
49 typedef std::vector<Fingerprint> Fingerprints; | 52 typedef std::vector<Fingerprint> Fingerprints; |
50 | 53 |
51 // A hash value of a fingerprint | 54 // A hash value of a fingerprint |
52 typedef int32 Hash; | 55 typedef int32_t Hash; |
53 | 56 |
54 // A fingerprint or hash value that does not exist | 57 // A fingerprint or hash value that does not exist |
55 static const Fingerprint null_fingerprint_; | 58 static const Fingerprint null_fingerprint_; |
56 static const Hash null_hash_; | 59 static const Hash null_hash_; |
57 | 60 |
58 VisitedLinkCommon(); | 61 VisitedLinkCommon(); |
59 virtual ~VisitedLinkCommon(); | 62 virtual ~VisitedLinkCommon(); |
60 | 63 |
61 // Returns the fingerprint for the given URL. | 64 // Returns the fingerprint for the given URL. |
62 Fingerprint ComputeURLFingerprint(const char* canonical_url, | 65 Fingerprint ComputeURLFingerprint(const char* canonical_url, |
63 size_t url_len) const { | 66 size_t url_len) const { |
64 return ComputeURLFingerprint(canonical_url, url_len, salt_); | 67 return ComputeURLFingerprint(canonical_url, url_len, salt_); |
65 } | 68 } |
66 | 69 |
67 // Looks up the given key in the table. The fingerprint for the URL is | 70 // Looks up the given key in the table. The fingerprint for the URL is |
68 // computed if you call one with the string argument. Returns true if found. | 71 // computed if you call one with the string argument. Returns true if found. |
69 // Does not modify the hastable. | 72 // Does not modify the hastable. |
70 bool IsVisited(const char* canonical_url, size_t url_len) const; | 73 bool IsVisited(const char* canonical_url, size_t url_len) const; |
71 bool IsVisited(const GURL& url) const; | 74 bool IsVisited(const GURL& url) const; |
72 bool IsVisited(Fingerprint fingerprint) const; | 75 bool IsVisited(Fingerprint fingerprint) const; |
73 | 76 |
74 #ifdef UNIT_TEST | 77 #ifdef UNIT_TEST |
75 // Returns statistics about DB usage | 78 // Returns statistics about DB usage |
76 void GetUsageStatistics(int32* table_size, | 79 void GetUsageStatistics(int32_t* table_size, |
77 VisitedLinkCommon::Fingerprint** fingerprints) { | 80 VisitedLinkCommon::Fingerprint** fingerprints) { |
78 *table_size = table_length_; | 81 *table_size = table_length_; |
79 *fingerprints = hash_table_; | 82 *fingerprints = hash_table_; |
80 } | 83 } |
81 #endif | 84 #endif |
82 | 85 |
83 protected: | 86 protected: |
84 // This structure is at the beginning of the shared memory so that the slaves | 87 // This structure is at the beginning of the shared memory so that the slaves |
85 // can get stats on the table | 88 // can get stats on the table |
86 struct SharedHeader { | 89 struct SharedHeader { |
87 // see goes into table_length_ | 90 // see goes into table_length_ |
88 uint32 length; | 91 uint32_t length; |
89 | 92 |
90 // goes into salt_ | 93 // goes into salt_ |
91 uint8 salt[LINK_SALT_LENGTH]; | 94 uint8_t salt[LINK_SALT_LENGTH]; |
92 }; | 95 }; |
93 | 96 |
94 // Returns the fingerprint at the given index into the URL table. This | 97 // Returns the fingerprint at the given index into the URL table. This |
95 // function should be called instead of accessing the table directly to | 98 // function should be called instead of accessing the table directly to |
96 // contain endian issues. | 99 // contain endian issues. |
97 Fingerprint FingerprintAt(int32 table_offset) const { | 100 Fingerprint FingerprintAt(int32_t table_offset) const { |
98 if (!hash_table_) | 101 if (!hash_table_) |
99 return null_fingerprint_; | 102 return null_fingerprint_; |
100 return hash_table_[table_offset]; | 103 return hash_table_[table_offset]; |
101 } | 104 } |
102 | 105 |
103 // Computes the fingerprint of the given canonical URL. It is static so the | 106 // Computes the fingerprint of the given canonical URL. It is static so the |
104 // same algorithm can be re-used by the table rebuilder, so you will have to | 107 // same algorithm can be re-used by the table rebuilder, so you will have to |
105 // pass the salt as a parameter. See the non-static version above if you | 108 // pass the salt as a parameter. See the non-static version above if you |
106 // want to use the current class' salt. | 109 // want to use the current class' salt. |
107 static Fingerprint ComputeURLFingerprint(const char* canonical_url, | 110 static Fingerprint ComputeURLFingerprint( |
108 size_t url_len, | 111 const char* canonical_url, |
109 const uint8 salt[LINK_SALT_LENGTH]); | 112 size_t url_len, |
| 113 const uint8_t salt[LINK_SALT_LENGTH]); |
110 | 114 |
111 // Computes the hash value of the given fingerprint, this is used as a lookup | 115 // Computes the hash value of the given fingerprint, this is used as a lookup |
112 // into the hashtable. | 116 // into the hashtable. |
113 static Hash HashFingerprint(Fingerprint fingerprint, int32 table_length) { | 117 static Hash HashFingerprint(Fingerprint fingerprint, int32_t table_length) { |
114 if (table_length == 0) | 118 if (table_length == 0) |
115 return null_hash_; | 119 return null_hash_; |
116 return static_cast<Hash>(fingerprint % table_length); | 120 return static_cast<Hash>(fingerprint % table_length); |
117 } | 121 } |
118 // Uses the current hashtable. | 122 // Uses the current hashtable. |
119 Hash HashFingerprint(Fingerprint fingerprint) const { | 123 Hash HashFingerprint(Fingerprint fingerprint) const { |
120 return HashFingerprint(fingerprint, table_length_); | 124 return HashFingerprint(fingerprint, table_length_); |
121 } | 125 } |
122 | 126 |
123 // pointer to the first item | 127 // pointer to the first item |
124 VisitedLinkCommon::Fingerprint* hash_table_; | 128 VisitedLinkCommon::Fingerprint* hash_table_; |
125 | 129 |
126 // the number of items in the hash table | 130 // the number of items in the hash table |
127 int32 table_length_; | 131 int32_t table_length_; |
128 | 132 |
129 // salt used for each URL when computing the fingerprint | 133 // salt used for each URL when computing the fingerprint |
130 uint8 salt_[LINK_SALT_LENGTH]; | 134 uint8_t salt_[LINK_SALT_LENGTH]; |
131 | 135 |
132 private: | 136 private: |
133 DISALLOW_COPY_AND_ASSIGN(VisitedLinkCommon); | 137 DISALLOW_COPY_AND_ASSIGN(VisitedLinkCommon); |
134 }; | 138 }; |
135 | 139 |
136 } // namespace visitedlink | 140 } // namespace visitedlink |
137 | 141 |
138 #endif // COMPONENTS_VISITEDLINK_COMMON_VISITEDLINK_COMMON_H_ | 142 #endif // COMPONENTS_VISITEDLINK_COMMON_VISITEDLINK_COMMON_H_ |
OLD | NEW |