Initial UniquePositions implementation

sync/internal_api/public/base/unique_position.h

Index: sync/internal_api/public/base/unique_position.h
diff --git a/sync/internal_api/public/base/unique_position.h b/sync/internal_api/public/base/unique_position.h
new file mode 100644
index 0000000000000000000000000000000000000000..959164f403cfa5af9cf4ac8db44696c4476de1f4
--- /dev/null
+++ b/sync/internal_api/public/base/unique_position.h
@@ -0,0 +1,118 @@
+// Copyright (c) 2012 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 SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
+#define SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_
+
+#include <string>
+
+#include "base/basictypes.h"
+
+namespace syncer {
+
+// A class to represent positions.
+//
+// By relying on the existence of unique suffixes, this class can ensure that it
+// is always possible to create a new position between any two existing
+// positions.  It can also create new positions before or after any other
+// position, which makes it easier to support insertion at the head or tail of a
+// list.
+//
+// Note that these unique suffixes must be exactly |kSuffixLength| bytes long.
+//
+// The cost for all these features is potentially unbounded space usage.  In
+// practice, however, most ordinals should be not much longer than the suffix.
+//
+// This class currently has several bookmarks-related assumptions built in,
+// though it could be adapted to be more generally useful.
+class UniquePosition {
+ public:
+  static const size_t kSuffixLength = (64 + 128) / 8;
+  static const char kTerminatorByte = kuint8max;
+
+  static bool IsValidSuffix(const std::string& suffix);
+  static bool IsValidBytes(const std::string& bytes);
+
+  // Returns an invalid position.
+  static UniquePosition CreateInvalid();
+
+  // Converts bytes from 'ToInternalValue()' back into a UniquePosition.
+  static UniquePosition FromBytes(const std::string& bytes);
+
+  // Creates a position with the given suffix.  Ordering among positions created
+  // from this function is the same as that of the integer parameters that were
+  // passed in.
+  static UniquePosition FromInt64(int64 i, const std::string& suffix);
+
+  // Returns a valid position.  Its ordering is not defined.
+  static UniquePosition InitialPosition(const std::string& suffix);
+
+  // Returns positions compare smaller than, greater than, or between the input
+  // positions.
+  static UniquePosition Before(const UniquePosition& x,
+                               const std::string& suffix);
+  static UniquePosition After(const UniquePosition& x,
+                              const std::string& suffix);
+  static UniquePosition Between(const UniquePosition& before,
+                                const UniquePosition& after,
+                                const std::string& suffix);
+
+  // Create a random suffix.  Should be used only as a last resort.
+  static const std::string GenerateUniqueSuffix();
+
+  // Create a unique suffix based on the input parameters.  The parameters are
+  // sufficient to uniquely identify any bookmark within the database.
+  static const std::string GenerateBookmarkSuffix(
+      const std::string& decoded_originator_cache_guid,
+      int64 numeric_originator_item_id);
+
+  UniquePosition();
+
+  bool LessThan(const UniquePosition& other) const;
+  bool Equals(const UniquePosition& other) const;
+
+  // Serializes the position's internal state.  To be used with FromBytes().
+  const std::string& ToInternalValue() const;
+
+  // Returns a human-readable representation of this item's internal state.
+  std::string ToDebugString() const;
+
+  // Performs a lossy conversion to an int64 position.  Positions converted to
+  // and from int64s using this and the FromInt64 function should maintain their
+  // relative orderings unless the int64 values conflict.
+  int64 ToInt64() const;
+
+  bool IsValid() const;
+
+ private:
+  friend class UniquePositionTest;
+
+  // Returns a string X such that (X ++ |suffix| ++ |kTerminatorByte|) < |str|.
+  // |str| must be a trailing substring of a valid ordinal.
+  // |suffix| must be a valid unique suffix.
+  static std::string FindSmallerWithSuffix(const std::string& str,
+                                           const std::string& suffix);
+  // Returns a string X such that (X ++ |suffix| ++ |kTerminatorByte|) > |str|.
+  // |str| must be a trailing substring of a valid ordinal.
+  // |suffix| must be a valid unique suffix.
+  static std::string FindGreaterWithSuffix(const std::string& str,
+                                           const std::string& suffix);
+  // Returns a string X such that
+  // |before| < (X ++ |suffix| ++ |kTerminatorByte|) < |after|.
+  // |before| and after must be a trailing substrings of valid ordinals.
+  // |suffix| must be a valid unique suffix.
+  static std::string FindBetweenWithSuffix(const std::string& before,
+                                           const std::string& after,
+                                           const std::string& suffix);
+
+  explicit UniquePosition(const std::string& internal_rep);
+  UniquePosition(const std::string& prefix, const std::string& suffix);
+
+  std::string bytes_;
+  bool is_valid_;
+};
+
+}  // namespace syncer;
+
+#endif  // SYNC_INTERNAL_API_PUBLIC_BASE_UNIQUE_POSITION_H_