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 #include "sync/internal_api/public/base/unique_position.h" | 5 #include "sync/internal_api/public/base/unique_position.h" |
6 | 6 |
7 #include "base/logging.h" | 7 #include "base/logging.h" |
8 #include "base/string_number_conversions.h" | 8 #include "base/string_number_conversions.h" |
9 #include "sync/protocol/unique_position.pb.h" | 9 #include "sync/protocol/unique_position.pb.h" |
10 | 10 |
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
54 bytes[i] = static_cast<uint8>(y); | 54 bytes[i] = static_cast<uint8>(y); |
55 y >>= 8; | 55 y >>= 8; |
56 } | 56 } |
57 return UniquePosition(bytes, suffix); | 57 return UniquePosition(bytes, suffix); |
58 } | 58 } |
59 | 59 |
60 // static. | 60 // static. |
61 UniquePosition UniquePosition::InitialPosition( | 61 UniquePosition UniquePosition::InitialPosition( |
62 const std::string& suffix) { | 62 const std::string& suffix) { |
63 DCHECK(IsValidSuffix(suffix)); | 63 DCHECK(IsValidSuffix(suffix)); |
64 return UniquePosition("", suffix); | 64 return UniquePosition(std::string(), suffix); |
65 } | 65 } |
66 | 66 |
67 // static. | 67 // static. |
68 UniquePosition UniquePosition::Before( | 68 UniquePosition UniquePosition::Before( |
69 const UniquePosition& x, | 69 const UniquePosition& x, |
70 const std::string& suffix) { | 70 const std::string& suffix) { |
71 DCHECK(IsValidSuffix(suffix)); | 71 DCHECK(IsValidSuffix(suffix)); |
72 DCHECK(x.IsValid()); | 72 DCHECK(x.IsValid()); |
73 const std::string& before = FindSmallerWithSuffix(x.bytes_, suffix); | 73 const std::string& before = FindSmallerWithSuffix(x.bytes_, suffix); |
74 return UniquePosition(before, suffix); | 74 return UniquePosition(before, suffix); |
(...skipping 93 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
168 size_t ref_zeroes = reference.find_first_not_of('\0'); | 168 size_t ref_zeroes = reference.find_first_not_of('\0'); |
169 size_t suffix_zeroes = suffix.find_first_not_of('\0'); | 169 size_t suffix_zeroes = suffix.find_first_not_of('\0'); |
170 | 170 |
171 // Neither of our inputs are allowed to have trailing zeroes, so the following | 171 // Neither of our inputs are allowed to have trailing zeroes, so the following |
172 // must be true. | 172 // must be true. |
173 DCHECK_NE(ref_zeroes, std::string::npos); | 173 DCHECK_NE(ref_zeroes, std::string::npos); |
174 DCHECK_NE(suffix_zeroes, std::string::npos); | 174 DCHECK_NE(suffix_zeroes, std::string::npos); |
175 | 175 |
176 if (suffix_zeroes > ref_zeroes) { | 176 if (suffix_zeroes > ref_zeroes) { |
177 // Implies suffix < ref. | 177 // Implies suffix < ref. |
178 return ""; | 178 return std::string(); |
179 } | 179 } |
180 | 180 |
181 if (suffix.substr(suffix_zeroes) < reference.substr(ref_zeroes)) { | 181 if (suffix.substr(suffix_zeroes) < reference.substr(ref_zeroes)) { |
182 // Prepend zeroes so the result has as many zero digits as |reference|. | 182 // Prepend zeroes so the result has as many zero digits as |reference|. |
183 return std::string(ref_zeroes - suffix_zeroes, '\0'); | 183 return std::string(ref_zeroes - suffix_zeroes, '\0'); |
184 } else if (suffix_zeroes > 1) { | 184 } else if (suffix_zeroes > 1) { |
185 // Prepend zeroes so the result has one more zero digit than |reference|. | 185 // Prepend zeroes so the result has one more zero digit than |reference|. |
186 // We could also take the "else" branch below, but taking this branch will | 186 // We could also take the "else" branch below, but taking this branch will |
187 // give us a smaller result. | 187 // give us a smaller result. |
188 return std::string(ref_zeroes - suffix_zeroes + 1, '\0'); | 188 return std::string(ref_zeroes - suffix_zeroes + 1, '\0'); |
(...skipping 14 matching lines...) Expand all Loading... |
203 | 203 |
204 if (ref_FFs == std::string::npos) { | 204 if (ref_FFs == std::string::npos) { |
205 ref_FFs = reference.length(); | 205 ref_FFs = reference.length(); |
206 } | 206 } |
207 if (suffix_FFs == std::string::npos) { | 207 if (suffix_FFs == std::string::npos) { |
208 suffix_FFs = suffix.length(); | 208 suffix_FFs = suffix.length(); |
209 } | 209 } |
210 | 210 |
211 if (suffix_FFs > ref_FFs) { | 211 if (suffix_FFs > ref_FFs) { |
212 // Implies suffix > reference. | 212 // Implies suffix > reference. |
213 return ""; | 213 return std::string(); |
214 } | 214 } |
215 | 215 |
216 if (suffix.substr(suffix_FFs) > reference.substr(ref_FFs)) { | 216 if (suffix.substr(suffix_FFs) > reference.substr(ref_FFs)) { |
217 // Prepend FF digits to match those in |reference|. | 217 // Prepend FF digits to match those in |reference|. |
218 return std::string(ref_FFs - suffix_FFs, kuint8max); | 218 return std::string(ref_FFs - suffix_FFs, kuint8max); |
219 } else if (suffix_FFs > 1) { | 219 } else if (suffix_FFs > 1) { |
220 // Prepend enough leading FF digits so result has one more of them than | 220 // Prepend enough leading FF digits so result has one more of them than |
221 // |reference| does. We could also take the "else" branch below, but this | 221 // |reference| does. We could also take the "else" branch below, but this |
222 // gives us a smaller result. | 222 // gives us a smaller result. |
223 return std::string(ref_FFs - suffix_FFs + 1, kuint8max); | 223 return std::string(ref_FFs - suffix_FFs + 1, kuint8max); |
(...skipping 13 matching lines...) Expand all Loading... |
237 const std::string& after, | 237 const std::string& after, |
238 const std::string& suffix) { | 238 const std::string& suffix) { |
239 DCHECK(IsValidSuffix(suffix)); | 239 DCHECK(IsValidSuffix(suffix)); |
240 DCHECK_NE(before, after); | 240 DCHECK_NE(before, after); |
241 DCHECK_LT(before, after); | 241 DCHECK_LT(before, after); |
242 | 242 |
243 std::string mid; | 243 std::string mid; |
244 | 244 |
245 // Sometimes our suffix puts us where we want to be. | 245 // Sometimes our suffix puts us where we want to be. |
246 if (before < suffix && suffix < after) { | 246 if (before < suffix && suffix < after) { |
247 return ""; | 247 return std::string(); |
248 } | 248 } |
249 | 249 |
250 size_t i = 0; | 250 size_t i = 0; |
251 for ( ; i < std::min(before.length(), after.length()); ++i) { | 251 for ( ; i < std::min(before.length(), after.length()); ++i) { |
252 uint8 a_digit = before[i]; | 252 uint8 a_digit = before[i]; |
253 uint8 b_digit = after[i]; | 253 uint8 b_digit = after[i]; |
254 | 254 |
255 if (b_digit - a_digit >= 2) { | 255 if (b_digit - a_digit >= 2) { |
256 mid.push_back(a_digit + (b_digit - a_digit)/2); | 256 mid.push_back(a_digit + (b_digit - a_digit)/2); |
257 return mid; | 257 return mid; |
(...skipping 61 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
319 UniquePosition::UniquePosition( | 319 UniquePosition::UniquePosition( |
320 const std::string& prefix, | 320 const std::string& prefix, |
321 const std::string& suffix) | 321 const std::string& suffix) |
322 : bytes_(prefix + suffix), | 322 : bytes_(prefix + suffix), |
323 is_valid_(IsValidBytes(bytes_)) { | 323 is_valid_(IsValidBytes(bytes_)) { |
324 DCHECK(IsValidSuffix(suffix)); | 324 DCHECK(IsValidSuffix(suffix)); |
325 DCHECK(IsValid()); | 325 DCHECK(IsValid()); |
326 } | 326 } |
327 | 327 |
328 } // namespace syncer | 328 } // namespace syncer |
OLD | NEW |