| 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 55 matching lines...) Expand 10 before | Expand all | Expand 10 after  Loading... | 
| 66   bool Exists(SBPrefix prefix) const; | 66   bool Exists(SBPrefix prefix) const; | 
| 67 | 67 | 
| 68   // Persist the set on disk. | 68   // Persist the set on disk. | 
| 69   static PrefixSet* LoadFile(const FilePath& filter_name); | 69   static PrefixSet* LoadFile(const FilePath& filter_name); | 
| 70   bool WriteFile(const FilePath& filter_name) const; | 70   bool WriteFile(const FilePath& filter_name) const; | 
| 71 | 71 | 
| 72   // Regenerate the vector of prefixes passed to the constructor into | 72   // Regenerate the vector of prefixes passed to the constructor into | 
| 73   // |prefixes|.  Prefixes will be added in sorted order. | 73   // |prefixes|.  Prefixes will be added in sorted order. | 
| 74   void GetPrefixes(std::vector<SBPrefix>* prefixes) const; | 74   void GetPrefixes(std::vector<SBPrefix>* prefixes) const; | 
| 75 | 75 | 
| 76   // TODO(shess): The following are debugging accessors.  Delete once |  | 
| 77   // the encoding problem is figured out. |  | 
| 78 |  | 
| 79   size_t IndexBinFor(size_t target_index) const; |  | 
| 80 |  | 
| 81   // The number of prefixes represented. |  | 
| 82   size_t GetSize() const; |  | 
| 83 |  | 
| 84   // Returns |true| if the element at |target_index| is between items in the |  | 
| 85   // |index_| array. |  | 
| 86   bool IsDeltaAt(size_t target_index) const; |  | 
| 87 |  | 
| 88   // Returns the delta used to calculate the element at |  | 
| 89   // |target_index|.  Only call if |IsDeltaAt()| returned |true|. |  | 
| 90   uint16 DeltaAt(size_t target_index) const; |  | 
| 91 |  | 
| 92   // Check whether |index_| and |deltas_| still match the checksum |  | 
| 93   // generated during construction. |  | 
| 94   bool CheckChecksum() const; |  | 
| 95 |  | 
| 96   // Accumulates xor checksum over what GetPrefixes() would return, |  | 
| 97   // without requiring a large temporary structure. |  | 
| 98   SBPrefix GetPrefixesChecksum() const; |  | 
| 99 |  | 
| 100  private: | 76  private: | 
| 101   // Maximum number of consecutive deltas to encode before generating | 77   // Maximum number of consecutive deltas to encode before generating | 
| 102   // a new index entry.  This helps keep the worst-case performance | 78   // a new index entry.  This helps keep the worst-case performance | 
| 103   // for |Exists()| under control. | 79   // for |Exists()| under control. | 
| 104   static const size_t kMaxRun = 100; | 80   static const size_t kMaxRun = 100; | 
| 105 | 81 | 
| 106   // Helper for |LoadFile()|.  Steals the contents of |index| and | 82   // Helper for |LoadFile()|.  Steals the contents of |index| and | 
| 107   // |deltas| using |swap()|. | 83   // |deltas| using |swap()|. | 
| 108   PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, | 84   PrefixSet(std::vector<std::pair<SBPrefix,size_t> > *index, | 
| 109             std::vector<uint16> *deltas); | 85             std::vector<uint16> *deltas); | 
| 110 | 86 | 
| 111   // Top-level index of prefix to offset in |deltas_|.  Each pair | 87   // Top-level index of prefix to offset in |deltas_|.  Each pair | 
| 112   // indicates a base prefix and where the deltas from that prefix | 88   // indicates a base prefix and where the deltas from that prefix | 
| 113   // begin in |deltas_|.  The deltas for a pair end at the next pair's | 89   // begin in |deltas_|.  The deltas for a pair end at the next pair's | 
| 114   // index into |deltas_|. | 90   // index into |deltas_|. | 
| 115   std::vector<std::pair<SBPrefix,size_t> > index_; | 91   std::vector<std::pair<SBPrefix,size_t> > index_; | 
| 116 | 92 | 
| 117   // Deltas which are added to the prefix in |index_| to generate | 93   // Deltas which are added to the prefix in |index_| to generate | 
| 118   // prefixes.  Deltas are only valid between consecutive items from | 94   // prefixes.  Deltas are only valid between consecutive items from | 
| 119   // |index_|, or the end of |deltas_| for the last |index_| pair. | 95   // |index_|, or the end of |deltas_| for the last |index_| pair. | 
| 120   std::vector<uint16> deltas_; | 96   std::vector<uint16> deltas_; | 
| 121 | 97 | 
| 122   // For debugging, used to verify that |index_| and |deltas| were not |  | 
| 123   // changed after generation during construction.  |checksum_| is |  | 
| 124   // calculated from the data used to construct those vectors. |  | 
| 125   uint32 checksum_; |  | 
| 126 |  | 
| 127   DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 98   DISALLOW_COPY_AND_ASSIGN(PrefixSet); | 
| 128 }; | 99 }; | 
| 129 | 100 | 
| 130 }  // namespace safe_browsing | 101 }  // namespace safe_browsing | 
| 131 | 102 | 
| 132 #endif  // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 103 #endif  // CHROME_BROWSER_SAFE_BROWSING_PREFIX_SET_H_ | 
| OLD | NEW | 
|---|