| 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 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 76 private: | 76 private: |
| 77 friend class PrefixSetBuilder; | 77 friend class PrefixSetBuilder; |
| 78 | 78 |
| 79 friend class PrefixSetTest; | 79 friend class PrefixSetTest; |
| 80 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, AllBig); | 80 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, AllBig); |
| 81 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, EdgeCases); | 81 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, EdgeCases); |
| 82 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Empty); | 82 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Empty); |
| 83 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, FullHashBuild); | 83 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, FullHashBuild); |
| 84 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, IntMinMax); | 84 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, IntMinMax); |
| 85 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, OneElement); | 85 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, OneElement); |
| 86 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWrite); |
| 86 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWriteSigned); | 87 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, ReadWriteSigned); |
| 88 FRIEND_TEST_ALL_PREFIXES(PrefixSetTest, Version3); |
| 87 | 89 |
| 88 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, BasicStore); | 90 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, BasicStore); |
| 89 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks); | 91 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DeleteChunks); |
| 90 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption); | 92 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, DetectsCorruption); |
| 91 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty); | 93 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Empty); |
| 92 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax); | 94 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, PrefixMinMax); |
| 93 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); | 95 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); |
| 94 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); | 96 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); |
| 95 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); | 97 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); |
| 96 | 98 |
| (...skipping 16 matching lines...) Expand all Loading... |
| 113 // Provided for testing purposes. | 115 // Provided for testing purposes. |
| 114 bool PrefixExists(SBPrefix prefix) const; | 116 bool PrefixExists(SBPrefix prefix) const; |
| 115 | 117 |
| 116 // Regenerate the vector of prefixes passed to the constructor into | 118 // Regenerate the vector of prefixes passed to the constructor into |
| 117 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. | 119 // |prefixes|. Prefixes will be added in sorted order. Useful for testing. |
| 118 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; | 120 void GetPrefixes(std::vector<SBPrefix>* prefixes) const; |
| 119 | 121 |
| 120 // Used by |PrefixSetBuilder|. | 122 // Used by |PrefixSetBuilder|. |
| 121 PrefixSet(); | 123 PrefixSet(); |
| 122 | 124 |
| 123 // Helper for |LoadFile()|. Steals the contents of |index| and | 125 // Helper for |LoadFile()|. Steals vector contents using |swap()|. |
| 124 // |deltas| using |swap()|. | 126 PrefixSet(IndexVector* index, |
| 125 PrefixSet(IndexVector* index, std::vector<uint16>* deltas); | 127 std::vector<uint16>* deltas, |
| 128 std::vector<SBFullHash>* full_hashes); |
| 126 | 129 |
| 127 // Top-level index of prefix to offset in |deltas_|. Each pair | 130 // Top-level index of prefix to offset in |deltas_|. Each pair |
| 128 // indicates a base prefix and where the deltas from that prefix | 131 // indicates a base prefix and where the deltas from that prefix |
| 129 // begin in |deltas_|. The deltas for a pair end at the next pair's | 132 // begin in |deltas_|. The deltas for a pair end at the next pair's |
| 130 // index into |deltas_|. | 133 // index into |deltas_|. |
| 131 IndexVector index_; | 134 IndexVector index_; |
| 132 | 135 |
| 133 // Deltas which are added to the prefix in |index_| to generate | 136 // Deltas which are added to the prefix in |index_| to generate |
| 134 // prefixes. Deltas are only valid between consecutive items from | 137 // prefixes. Deltas are only valid between consecutive items from |
| 135 // |index_|, or the end of |deltas_| for the last |index_| pair. | 138 // |index_|, or the end of |deltas_| for the last |index_| pair. |
| (...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 171 // Buffers prefixes until enough are avaliable to emit a run. | 174 // Buffers prefixes until enough are avaliable to emit a run. |
| 172 std::vector<SBPrefix> buffer_; | 175 std::vector<SBPrefix> buffer_; |
| 173 | 176 |
| 174 // The PrefixSet being built. | 177 // The PrefixSet being built. |
| 175 scoped_ptr<PrefixSet> prefix_set_; | 178 scoped_ptr<PrefixSet> prefix_set_; |
| 176 }; | 179 }; |
| 177 | 180 |
| 178 } // namespace safe_browsing | 181 } // namespace safe_browsing |
| 179 | 182 |
| 180 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 183 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
| OLD | NEW |