First-time sync: asymptotic running time improvement

chrome/browser/sync/syncable/syncable_id.h

 // Copyright (c) 2009 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_ID_H_
 #define CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_ID_H_
 #pragma once
 
 #include <iosfwd>
 #include <limits>
@@ skipping 61 matching lines @@
   // fix this, this is madness :)
   inline bool IsNull() const {
     return IsRoot();
   }
   inline void Clear() {
     s_ = "r";
   }
   inline int compare(const Id& that) const {
     return s_.compare(that.s_);
   }
-  // Must never allow id == 0 or id < 0 to compile.
   inline bool operator == (const Id& that) const {
     return s_ == that.s_;
   }
   inline bool operator != (const Id& that) const {
     return s_ != that.s_;
   }
   inline bool operator < (const Id& that) const {
     return s_ < that.s_;
   }
   inline bool operator > (const Id& that) const {
     return s_ > that.s_;
   }
+  // Return the next highest ID in the lexicographic ordering.  This is
+  // useful for computing upper bounds on std::sets that are ordered
+  // by operator<.
+  Id GetLexicographicSuccessor() const;
 
   // Three functions are used to work with our proto buffers.
   std::string GetServerId() const;
   static Id CreateFromServerId(const std::string& server_id);
   // This should only be used if you get back a reference to a local
   // id from the server. Returns a client only opaque id.
   static Id CreateFromClientString(const std::string& local_id);
 
- protected:
+  // This method returns an ID that will compare less than any valid ID.
+  // The returned ID is not a valid ID itself.  This is useful for
+  // computing lower bounds on std::sets that are ordered by operator<.
+  static Id GetLeastIdForLexicographicComparison();
+
+ private:
   std::string s_;
 };
 
 extern const Id kNullId;
 
 }  // namespace syncable
 
 #endif  // CHROME_BROWSER_SYNC_SYNCABLE_SYNCABLE_ID_H_