| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2012 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 // A read-only set implementation for |SBPrefix| items. Prefixes are | 5 // A read-only set implementation for |SBPrefix| items. Prefixes are |
| 6 // sorted and stored as 16-bit deltas from the previous prefix. An | 6 // sorted and stored as 16-bit deltas from the previous prefix. An |
| 7 // index structure provides quick random access, and also handles | 7 // index structure provides quick random access, and also handles |
| 8 // cases where 16 bits cannot encode a delta. | 8 // cases where 16 bits cannot encode a delta. |
| 9 // | 9 // |
| 10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would | 10 // For example, the sequence {20, 25, 41, 65432, 150000, 160000} would |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 42 // 4 byte version number | 42 // 4 byte version number |
| 43 // 4 byte |index_.size()| | 43 // 4 byte |index_.size()| |
| 44 // 4 byte |deltas_.size()| | 44 // 4 byte |deltas_.size()| |
| 45 // n * 8 byte |&index_[0]..&index_[n]| | 45 // n * 8 byte |&index_[0]..&index_[n]| |
| 46 // m * 2 byte |&deltas_[0]..&deltas_[m]| | 46 // m * 2 byte |&deltas_[0]..&deltas_[m]| |
| 47 // 16 byte digest | 47 // 16 byte digest |
| 48 | 48 |
| 49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ | 49 #ifndef COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ |
| 50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ | 50 #define COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ |
| 51 | 51 |
| 52 #include <stddef.h> |
| 53 #include <stdint.h> |
| 54 |
| 52 #include <utility> | 55 #include <utility> |
| 53 #include <vector> | 56 #include <vector> |
| 54 | 57 |
| 55 #include "base/gtest_prod_util.h" | 58 #include "base/gtest_prod_util.h" |
| 56 #include "base/macros.h" | 59 #include "base/macros.h" |
| 57 #include "base/memory/scoped_ptr.h" | 60 #include "base/memory/scoped_ptr.h" |
| 58 #include "components/safe_browsing_db/util.h" | 61 #include "components/safe_browsing_db/util.h" |
| 59 | 62 |
| 60 namespace base { | 63 namespace base { |
| 61 class FilePath; | 64 class FilePath; |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); | 101 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); |
| 99 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); | 102 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); |
| 100 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); | 103 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); |
| 101 | 104 |
| 102 // Maximum number of consecutive deltas to encode before generating | 105 // Maximum number of consecutive deltas to encode before generating |
| 103 // a new index entry. This helps keep the worst-case performance | 106 // a new index entry. This helps keep the worst-case performance |
| 104 // for |Exists()| under control. | 107 // for |Exists()| under control. |
| 105 static const size_t kMaxRun = 100; | 108 static const size_t kMaxRun = 100; |
| 106 | 109 |
| 107 // Helpers to make |index_| easier to deal with. | 110 // Helpers to make |index_| easier to deal with. |
| 108 typedef std::pair<SBPrefix, uint32> IndexPair; | 111 typedef std::pair<SBPrefix, uint32_t> IndexPair; |
| 109 typedef std::vector<IndexPair> IndexVector; | 112 typedef std::vector<IndexPair> IndexVector; |
| 110 static bool PrefixLess(const IndexPair& a, const IndexPair& b); | 113 static bool PrefixLess(const IndexPair& a, const IndexPair& b); |
| 111 | 114 |
| 112 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is | 115 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is |
| 113 // added to |index_|, with the other elements added into |deltas_|. | 116 // added to |index_|, with the other elements added into |deltas_|. |
| 114 void AddRun(SBPrefix index_prefix, | 117 void AddRun(SBPrefix index_prefix, |
| 115 const uint16* run_begin, const uint16* run_end); | 118 const uint16_t* run_begin, |
| 119 const uint16_t* run_end); |
| 116 | 120 |
| 117 // |true| if |prefix| is one of the prefixes passed to the set's builder. | 121 // |true| if |prefix| is one of the prefixes passed to the set's builder. |
| 118 // Provided for testing purposes. | 122 // Provided for testing purposes. |
| 119 bool PrefixExists(SBPrefix prefix) const; | 123 bool PrefixExists(SBPrefix prefix) const; |
| 120 | 124 |
| 121 // Regenerate the vector of prefixes passed to the constructor into | 125 // Regenerate the vector of prefixes passed to the constructor into |
| 122 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. | 126 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. |
| 123 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; | 127 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; |
| 124 | 128 |
| 125 // Used by |PrefixSetBuilder|. | 129 // Used by |PrefixSetBuilder|. |
| 126 PrefixSet(); | 130 PrefixSet(); |
| 127 | 131 |
| 128 // Helper for |LoadFile()|. Steals vector contents using |swap()|. | 132 // Helper for |LoadFile()|. Steals vector contents using |swap()|. |
| 129 PrefixSet(IndexVector* index, | 133 PrefixSet(IndexVector* index, |
| 130 std::vector<uint16>* deltas, | 134 std::vector<uint16_t>* deltas, |
| 131 std::vector<SBFullHash>* full_hashes); | 135 std::vector<SBFullHash>* full_hashes); |
| 132 | 136 |
| 133 // Top-level index of prefix to offset in |deltas_|. Each pair | 137 // Top-level index of prefix to offset in |deltas_|. Each pair |
| 134 // indicates a base prefix and where the deltas from that prefix | 138 // indicates a base prefix and where the deltas from that prefix |
| 135 // begin in |deltas_|. The deltas for a pair end at the next pair's | 139 // begin in |deltas_|. The deltas for a pair end at the next pair's |
| 136 // index into |deltas_|. | 140 // index into |deltas_|. |
| 137 IndexVector index_; | 141 IndexVector index_; |
| 138 | 142 |
| 139 // Deltas which are added to the prefix in |index_| to generate | 143 // Deltas which are added to the prefix in |index_| to generate |
| 140 // prefixes. Deltas are only valid between consecutive items from | 144 // prefixes. Deltas are only valid between consecutive items from |
| 141 // |index_|, or the end of |deltas_| for the last |index_| pair. | 145 // |index_|, or the end of |deltas_| for the last |index_| pair. |
| 142 std::vector<uint16> deltas_; | 146 std::vector<uint16_t> deltas_; |
| 143 | 147 |
| 144 // Full hashes ordered by SBFullHashLess. | 148 // Full hashes ordered by SBFullHashLess. |
| 145 std::vector<SBFullHash> full_hashes_; | 149 std::vector<SBFullHash> full_hashes_; |
| 146 | 150 |
| 147 DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 151 DISALLOW_COPY_AND_ASSIGN(PrefixSet); |
| 148 }; | 152 }; |
| 149 | 153 |
| 150 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes. | 154 // Helper to incrementally build a PrefixSet from a stream of sorted prefixes. |
| 151 class PrefixSetBuilder { | 155 class PrefixSetBuilder { |
| 152 public: | 156 public: |
| (...skipping 25 matching lines...) Expand all Loading... |
| 178 // Buffers prefixes until enough are avaliable to emit a run. | 182 // Buffers prefixes until enough are avaliable to emit a run. |
| 179 std::vector<SBPrefix> buffer_; | 183 std::vector<SBPrefix> buffer_; |
| 180 | 184 |
| 181 // The PrefixSet being built. | 185 // The PrefixSet being built. |
| 182 scoped_ptr<PrefixSet> prefix_set_; | 186 scoped_ptr<PrefixSet> prefix_set_; |
| 183 }; | 187 }; |
| 184 | 188 |
| 185 } // namespace safe_browsing | 189 } // namespace safe_browsing |
| 186 | 190 |
| 187 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ | 191 #endif // COMPONENTS_SAFE_BROWSING_DB_PREFIX_SET_H_ |
| OLD | NEW |