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 CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 49 #ifndef CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
50 #define CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 50 #define CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
51 | 51 |
| 52 #include <utility> |
52 #include <vector> | 53 #include <vector> |
53 | 54 |
54 #include "base/gtest_prod_util.h" | 55 #include "base/gtest_prod_util.h" |
55 #include "base/memory/scoped_ptr.h" | 56 #include "base/memory/scoped_ptr.h" |
56 #include "chrome/browser/safe_browsing/safe_browsing_util.h" | 57 #include "chrome/browser/safe_browsing/safe_browsing_util.h" |
57 | 58 |
58 namespace base { | 59 namespace base { |
59 class FilePath; | 60 class FilePath; |
60 } | 61 } |
61 | 62 |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
96 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); | 97 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, SubKnockout); |
97 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); | 98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version7); |
98 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); | 99 FRIEND_TEST_ALL_PREFIXES(SafeBrowsingStoreFileTest, Version8); |
99 | 100 |
100 // Maximum number of consecutive deltas to encode before generating | 101 // Maximum number of consecutive deltas to encode before generating |
101 // a new index entry. This helps keep the worst-case performance | 102 // a new index entry. This helps keep the worst-case performance |
102 // for |Exists()| under control. | 103 // for |Exists()| under control. |
103 static const size_t kMaxRun = 100; | 104 static const size_t kMaxRun = 100; |
104 | 105 |
105 // Helpers to make |index_| easier to deal with. | 106 // Helpers to make |index_| easier to deal with. |
106 typedef std::pair<SBPrefix,uint32> IndexPair; | 107 typedef std::pair<SBPrefix, uint32> IndexPair; |
107 typedef std::vector<IndexPair> IndexVector; | 108 typedef std::vector<IndexPair> IndexVector; |
108 static bool PrefixLess(const IndexPair& a, const IndexPair& b); | 109 static bool PrefixLess(const IndexPair& a, const IndexPair& b); |
109 | 110 |
110 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is | 111 // Helper to let |PrefixSetBuilder| add a run of data. |index_prefix| is |
111 // added to |index_|, with the other elements added into |deltas_|. | 112 // added to |index_|, with the other elements added into |deltas_|. |
112 void AddRun(SBPrefix index_prefix, | 113 void AddRun(SBPrefix index_prefix, |
113 const uint16* run_begin, const uint16* run_end); | 114 const uint16* run_begin, const uint16* run_end); |
114 | 115 |
115 // |true| if |prefix| is one of the prefixes passed to the set's builder. | 116 // |true| if |prefix| is one of the prefixes passed to the set's builder. |
116 // Provided for testing purposes. | 117 // Provided for testing purposes. |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
175 // Buffers prefixes until enough are avaliable to emit a run. | 176 // Buffers prefixes until enough are avaliable to emit a run. |
176 std::vector<SBPrefix> buffer_; | 177 std::vector<SBPrefix> buffer_; |
177 | 178 |
178 // The PrefixSet being built. | 179 // The PrefixSet being built. |
179 scoped_ptr<PrefixSet> prefix_set_; | 180 scoped_ptr<PrefixSet> prefix_set_; |
180 }; | 181 }; |
181 | 182 |
182 } // namespace safe_browsing | 183 } // namespace safe_browsing |
183 | 184 |
184 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 185 #endif // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ |
OLD | NEW |