| 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 |