Adding IdGenerator to generate increasing IDs
This can be extended to allow distributed insertion as well.
Change-Id: If24501523ec68b0f43679dd924c7771fd2758dc4
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMapping.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMapping.java
new file mode 100644
index 0000000..804f1d7
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMapping.java
@@ -0,0 +1,11 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+public interface DigitMapping {
+ char encode(int digit);
+ int decode(char encoded);
+ int radix();
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMappings.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMappings.java
new file mode 100644
index 0000000..925b40e
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitMappings.java
@@ -0,0 +1,88 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+import android.support.annotation.NonNull;
+
+import com.google.common.base.Function;
+import com.google.common.collect.Collections2;
+import com.google.common.collect.ContiguousSet;
+import com.google.common.collect.DiscreteDomain;
+import com.google.common.collect.ImmutableRangeSet;
+import com.google.common.collect.Range;
+import com.google.common.collect.RangeSet;
+
+public final class DigitMappings {
+ private DigitMappings() {
+ }
+
+ public static final DiscreteDomain<Character> DOMAIN = new DiscreteDomain<Character>() {
+ @Override
+ public Character next(@NonNull Character value) {
+ return value == Character.MAX_VALUE ? null : (char) (value + 1);
+ }
+
+ @Override
+ public Character previous(@NonNull Character value) {
+ return value == Character.MIN_VALUE ? null : (char) (value - 1);
+ }
+
+ @Override
+ public long distance(@NonNull Character start, @NonNull Character end) {
+ return end - start;
+ }
+
+ @Override
+ public Character maxValue() {
+ return Character.MAX_VALUE;
+ }
+
+ @Override
+ public Character minValue() {
+ return Character.MIN_VALUE;
+ }
+ };
+
+ public static final DigitMapping ALL = fromRangeSet(Range.<Character>all());
+
+ /**
+ * Constructs a {@link DigitMapping} from the given ranges, where the ranges are given in order
+ * of increasing significance. Although the ranges may jump around in significance, within each
+ * range, characters are still mapped to digits in ascending order. Out-of-order ranges may be
+ * used as well but cannot be optimized in this way.
+ *
+ * @see DigitRangeMapping
+ */
+ public static DigitMapping fromRanges(Iterable<ContiguousSet<Character>> ranges) {
+ return new DigitRangeMapping(ranges);
+ }
+
+ /**
+ * @see #fromRangeSet(RangeSet)
+ */
+ @SafeVarargs
+ public static DigitMapping fromRangeSet(Range<Character>... ranges) {
+ ImmutableRangeSet.Builder<Character> builder = ImmutableRangeSet.builder();
+ for (Range<Character> range : ranges) {
+ builder.add(range);
+ }
+ return fromRangeSet(builder.build());
+ }
+
+ /**
+ * Constructs a {@link DigitMapping} from a {@link RangeSet}, ordering the ranges in ascending
+ * order (regardless of input order). If out-of-order ranges are desired, use the
+ * {@link #fromRanges(Iterable)} factory method instead to provide explicit ordering.
+ */
+ public static DigitMapping fromRangeSet(RangeSet<Character> spec) {
+ return fromRanges(Collections2.transform(spec.asRanges(),
+ new Function<Range<Character>, ContiguousSet<Character>>() {
+ @Override
+ public ContiguousSet<Character> apply(Range<Character> input) {
+ return ContiguousSet.create(input, DOMAIN);
+ }
+ }));
+ }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitRangeMapping.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitRangeMapping.java
new file mode 100644
index 0000000..3f3f140
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/DigitRangeMapping.java
@@ -0,0 +1,57 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+import com.google.common.collect.ContiguousSet;
+import com.google.common.collect.ImmutableList;
+
+/**
+ * A {@link DigitMapping} optimized for mappings where ranges of consecutive characters map to
+ * consecutive values. The overall mapping need not be monotonic to take advantage of this
+ * optimization.
+ */
+public class DigitRangeMapping implements DigitMapping {
+ private final ImmutableList<ContiguousSet<Character>> mRanges;
+ private final int mRadix;
+
+ public DigitRangeMapping(Iterable<ContiguousSet<Character>> ranges) {
+ mRanges = ImmutableList.copyOf(ranges);
+ int size = 0;
+ for (ContiguousSet<Character> range : mRanges) {
+ size += range.size();
+ }
+ mRadix = size;
+ }
+
+ @Override
+ public char encode(int digit) {
+ for (ContiguousSet<Character> range : mRanges) {
+ if (digit < range.size()) {
+ return range.asList().get(digit);
+ } else {
+ digit -= range.size();
+ }
+ }
+ throw new IllegalArgumentException("No encoding for digit " + digit + " (radix " + radix() +
+ ")");
+ }
+
+ @Override
+ public int decode(char encoded) {
+ int digit = 0;
+ for (ContiguousSet<Character> range : mRanges) {
+ if (range.contains(encoded)) {
+ return digit + encoded - range.first();
+ }
+ digit += range.size();
+ }
+ throw new IllegalArgumentException();
+ }
+
+ @Override
+ public int radix() {
+ return mRadix;
+ }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabet.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabet.java
new file mode 100644
index 0000000..a42ef4e
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabet.java
@@ -0,0 +1,16 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+public interface IdAlphabet {
+ char encodeDigit(int digit);
+ int decodeDigit(char encoded);
+
+ char encodeLeadingDigit(int digit);
+ int decodeLeadingDigit(char encoded);
+
+ int radix();
+ int leadingRadix();
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabets.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabets.java
new file mode 100644
index 0000000..673ce4b
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdAlphabets.java
@@ -0,0 +1,63 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+import com.google.common.collect.Range;
+
+public final class IdAlphabets {
+ private IdAlphabets() {
+ }
+
+ public static final IdAlphabet
+ COLLECTION_ID = fromDigitMappings(
+ DigitMappings.fromRangeSet(
+ Range.closed('0', '9'),
+ Range.closed('A', 'Z'),
+ Range.singleton('_'),
+ Range.closed('a', 'z')),
+ DigitMappings.fromRangeSet(
+ Range.closed('A', 'Z'),
+ Range.closed('a', 'z'))),
+ ROW_NAME = fromDigitMapping(DigitMappings.ALL);
+
+ public static IdAlphabet fromDigitMapping(final DigitMapping digitMapping) {
+ return fromDigitMappings(digitMapping, digitMapping);
+ }
+
+ public static IdAlphabet fromDigitMappings(final DigitMapping digitMapping,
+ final DigitMapping leadingDigitMapping) {
+ return new IdAlphabet() {
+ @Override
+ public char encodeDigit(int digit) {
+ return digitMapping.encode(digit);
+ }
+
+ @Override
+ public int decodeDigit(char encoded) {
+ return digitMapping.decode(encoded);
+ }
+
+ @Override
+ public char encodeLeadingDigit(int digit) {
+ return leadingDigitMapping.encode(digit);
+ }
+
+ @Override
+ public int decodeLeadingDigit(char encoded) {
+ return leadingDigitMapping.decode(encoded);
+ }
+
+ @Override
+ public int radix() {
+ return digitMapping.radix();
+ }
+
+ @Override
+ public int leadingRadix() {
+ return leadingDigitMapping.radix();
+ }
+ };
+ }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdGenerator.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdGenerator.java
new file mode 100644
index 0000000..10e77c7
--- /dev/null
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/IdGenerator.java
@@ -0,0 +1,257 @@
+// Copyright 2015 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+import java.util.UUID;
+
+public class IdGenerator {
+ // TODO(rosswang): Escape collection IDs to allow any character. A lot of this logic can be
+ // simplified if we can use any character.
+ // TODO(rosswang): Put this into Syncbase utils.
+
+ private final IdAlphabet mAlphabet;
+
+ /**
+ * the length we *would* need if we could use an underscore for the first character
+ */
+ private final int mLongUniformRadixLength;
+ private final int mLongEncodedLength;
+
+ /**
+ * This is related to unsigned division.
+ * @see #transformToSignedDivision(long)
+ */
+ private final int mMaxSafeMostSignificantDigit;
+ /**
+ * This is related to unsigned division.
+ * @see #transformToSignedDivision(long)
+ */
+ private final long mMostSignificantUnit, mMaxSafeMostSignificantValue;
+
+ private static final double LOG_LONG = Long.SIZE * Math.log(2);
+
+ /**
+ * @param alphabet the alphabet of legal characters for IDs generated by this generator
+ * @param perturb whether or not to perturb generated IDs by a random perturbation to avoid
+ * collisions in distributed key generation. Pass {@code false} if this generator
+ * is used to generate a sort key that is a secondary key where ordering
+ * conflicts can be deterministically resolved by the primary key. This setting
+ * only applies to the {@code generate...} methods.
+ */
+ public IdGenerator(IdAlphabet alphabet, boolean perturb) {
+ mAlphabet = alphabet;
+ mPerturb = perturb;
+
+ // ceil(log_RADIX(Long.MAX + 1))
+ mLongUniformRadixLength = (int)Math.ceil(LOG_LONG / Math.log(alphabet.radix()));
+
+ // int pow, msu = radix ^ url
+ long mostSignificantUnit = alphabet.radix();
+ for (int i = 2; i < mLongUniformRadixLength; i++) {
+ mostSignificantUnit *= alphabet.radix();
+ }
+ mMostSignificantUnit = mostSignificantUnit;
+
+ mMaxSafeMostSignificantDigit = (int)(Long.MAX_VALUE / mMostSignificantUnit);
+ mMaxSafeMostSignificantValue = mMaxSafeMostSignificantDigit * mMostSignificantUnit;
+
+ // The first character may have additional restrictions, so we have less chars to work with
+ // for the first digit. If we still have enough digits, we'll proceed and just use a special
+ // mapping for the leading digit. Otherwise, we'll pad by a leading 0, thus making the
+ // remaining encoding the common case.
+
+ // So, what most-significant digit do we need to encode the max unsigned value?
+ PartialDivisionResult div = transformToSignedDivision(-1);
+ int maxMostSignfiicantDigit = div.partialMostSignificantDigit +
+ (int)(div.partialRemainder / mMostSignificantUnit);
+ mLongEncodedLength = maxMostSignfiicantDigit < alphabet.leadingRadix() ?
+ mLongUniformRadixLength : mLongUniformRadixLength + 1;
+ }
+
+ private static class PartialDivisionResult {
+ public int partialMostSignificantDigit;
+ public long partialRemainder;
+
+ public PartialDivisionResult(int partialMostSignificantDigit, long partialRemainder) {
+ this.partialMostSignificantDigit = partialMostSignificantDigit;
+ this.partialRemainder = partialRemainder;
+ }
+ }
+
+ /**
+ * Performs partial calculation of the most significant digit for the alphabet-radix
+ * representation of {@code unsigned}. To achieve unsigned division, we first assume the
+ * most significant digit is at least as large as the max safe most significant digit for signed
+ * division, add one more if neccessary to push the "remainder" positive, and then do normal
+ * division for the rest.
+ */
+ private PartialDivisionResult transformToSignedDivision(long unsigned) {
+ if (unsigned < 0) {
+ long naiveRemainder = unsigned - mMaxSafeMostSignificantValue;
+ return naiveRemainder < 0 ?
+ // need one more
+ new PartialDivisionResult(mMaxSafeMostSignificantDigit + 1,
+ naiveRemainder - mMostSignificantUnit) :
+ new PartialDivisionResult(mMaxSafeMostSignificantDigit, naiveRemainder);
+ } else {
+ // Already positive; handle with normal arithmetic.
+ return new PartialDivisionResult(0, unsigned);
+ }
+ }
+
+ /**
+ * Converts a signed {@code long} to a {@code String} consistent with the pattern
+ * {@code [0-9A-Za-z][0-9A-Za-z_]*}, required by Syncbase for
+ * {@link io.v.v23.services.syncbase.Id} names, with lexicographic ordering consistent with the
+ * numeric ordering.
+ * <p>
+ * Example transformations using {@link IdAlphabets#COLLECTION_ID}:
+ * <pre>
+ * -9223372036854775808 -> 00000000000
+ * -9223372036854775807 -> 00000000001
+ * -9223372036854775806 -> 00000000002
+ * -1 -> 9MxfBQuKjH7
+ * 0 -> 9MxfBQuKjH8
+ * 1 -> 9MxfBQuKjH9
+ * 9223372036854775805 -> IivLMqoeTYD
+ * 9223372036854775806 -> IivLMqoeTYE
+ * 9223372036854775807 -> IivLMqoeTYF
+ * </pre>
+ */
+ public String longToPaddedIdentifier(long x) {
+ StringBuilder s = new StringBuilder(mLongEncodedLength);
+ long unsignedWithSameOrdering = x - Long.MIN_VALUE;
+ PartialDivisionResult signedSubproblem =
+ transformToSignedDivision(unsignedWithSameOrdering);
+ long leftToEncode = signedSubproblem.partialRemainder;
+
+ for (int placeValue = 0; placeValue < mLongUniformRadixLength - 1; placeValue++) {
+ if (leftToEncode > 0) {
+ s.append(mAlphabet.encodeDigit((int) (leftToEncode % mAlphabet.radix())));
+ leftToEncode /= mAlphabet.radix();
+ } else {
+ s.append(mAlphabet.encodeDigit(0));
+ }
+ }
+
+ // The most-significant digit needs to be handled specially, accounting for the signed
+ // division adjustment and using a possibly different character mapping.
+ int mostSignificantDigit = signedSubproblem.partialMostSignificantDigit + (int)leftToEncode;
+ if (mLongEncodedLength > mLongUniformRadixLength) {
+ // just 0-pad
+ s.append(mAlphabet.encodeDigit(mostSignificantDigit))
+ .append(mAlphabet.encodeLeadingDigit(0));
+ } else {
+ // use the special leading-digit mapping
+ s.append(mAlphabet.encodeLeadingDigit(mostSignificantDigit));
+ }
+
+ return s.reverse().toString();
+ }
+
+ /**
+ * Perturbs IDs to mitigate collision during distributed, eventually consistent insertion.
+ * {@link UUID#randomUUID()} is used for perturbation. The perturbed ID is strictly greater than
+ * the base ID but less than the next increment from the base ID except in the degenerate case
+ * where the base ID must be extended to increment.
+ */
+ public String perturb(String baseId) {
+ UUID uuid = UUID.randomUUID();
+ return baseId +
+ longToPaddedIdentifier(uuid.getMostSignificantBits()) +
+ longToPaddedIdentifier(uuid.getLeastSignificantBits());
+ }
+
+ /**
+ * Increments an ID with a proposed base length. If the increment cannot be done under these
+ * constraints, the ID is extended. The incremented ID is guaranteed to be greater than the
+ * given {@code fullId}.
+ * <p>
+ * Example transformations:
+ * <pre>
+ * 0000 -> 01
+ * AZ00 -> A_
+ * Az00 -> B0
+ * Zz00 -> a0
+ * zz00 -> zz1
+ * zzz0 -> zzz1
+ * zzzz -> zzzz0
+ * </pre>
+ */
+ public String increment(String fullId, int proposedCutoff) {
+ StringBuilder mutable = new StringBuilder(fullId);
+
+ if (proposedCutoff > fullId.length()) {
+ proposedCutoff = fullId.length();
+ }
+
+ // First try normal incrementing
+ for (int i = proposedCutoff - 1; i > 0; i--) {
+ int newValue = mAlphabet.decodeDigit(mutable.charAt(i)) + 1;
+ if (newValue < mAlphabet.radix()) {
+ mutable.setCharAt(i, mAlphabet.encodeDigit(newValue));
+ mutable.setLength(proposedCutoff);
+ return mutable.toString();
+ } else {
+ mutable.setCharAt(i, mAlphabet.encodeDigit(0));
+ }
+ }
+
+ // Process the leading digit specially
+ if (proposedCutoff > 0){
+ int newValue = mAlphabet.decodeLeadingDigit(mutable.charAt(0)) + 1;
+ if (newValue < mAlphabet.leadingRadix()) {
+ mutable.setCharAt(0, mAlphabet.encodeLeadingDigit(newValue));
+ mutable.setLength(proposedCutoff);
+ return mutable.toString();
+ }
+ }
+
+ // If we've gotten to this point, we can't increment the prefix; start looking at the
+ // suffix.
+
+ // Reset mutable
+ mutable.setLength(0);
+ mutable.append(fullId);
+
+ for (int i = proposedCutoff; i < fullId.length(); i++) {
+ int newValue = mAlphabet.decodeDigit(mutable.charAt(i)) + 1;
+ if (newValue < mAlphabet.radix()) {
+ mutable.setCharAt(i, mAlphabet.encodeDigit(newValue));
+ mutable.setLength(i + 1);
+ return mutable.toString();
+ }
+ }
+ // By this point, we just have to extend the string.
+ mutable.append(mAlphabet.encodeDigit(0));
+ return mutable.toString();
+ }
+
+ public String increment(String previous) {
+ return increment(previous, mLongEncodedLength);
+ }
+
+ private final Object mLargestKnownIdMutex = new Object();
+ private String mLargestKnownId;
+ private final boolean mPerturb;
+
+ public String generateTailId() {
+ String candidate = longToPaddedIdentifier(System.currentTimeMillis());
+ synchronized (mLargestKnownIdMutex) {
+ if (mLargestKnownId != null && candidate.compareTo(mLargestKnownId) <= 0) {
+ candidate = increment(mLargestKnownId);
+ }
+ return mLargestKnownId = mPerturb? perturb(candidate) : candidate;
+ }
+ }
+
+ public void registerId(String id) {
+ synchronized (mLargestKnownIdMutex) {
+ if (mLargestKnownId == null || id.compareTo(mLargestKnownId) > 0) {
+ mLargestKnownId = id;
+ }
+ }
+ }
+}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java
index be1f568..11545d3 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/MainListTracker.java
@@ -85,7 +85,7 @@
private void processWatchChange(WatchChange change) {
String rowName = change.getRowName();
- if (rowName.equals(SyncbaseTodoList.LIST_ROW_NAME)) {
+ if (rowName.equals(SyncbaseTodoList.LIST_METADATA_ROW_NAME)) {
mListSpec = SyncbasePersistence.castWatchValue(change.getValue(), ListSpec.class);
} else if (change.getChangeType() == ChangeType.DELETE_CHANGE) {
if (mIsTaskCompleted.remove(rowName)) {
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java
index 8d6b190..9e77ae3 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseMain.java
@@ -45,6 +45,7 @@
TAG = SyncbaseMain.class.getSimpleName(),
LISTS_PREFIX = "lists_";
+ private final IdGenerator mIdGenerator = new IdGenerator(IdAlphabets.COLLECTION_ID, true);
private final Map<String, MainListTracker> mTaskTrackers = new HashMap<>();
/**
@@ -64,6 +65,8 @@
if (change.getChangeType() == ChangeType.DELETE_CHANGE) {
trap(mTaskTrackers.remove(listId).deleteList(mVContext));
} else {
+ mIdGenerator.registerId(change.getRowName().substring(LISTS_PREFIX.length()));
+
MainListTracker listTracker = new MainListTracker(
mVContext, getDatabase(), listId, listener);
if (mTaskTrackers.put(listId, listTracker) != null) {
@@ -82,7 +85,7 @@
@Override
public void addTodoList(final ListSpec listSpec) {
- final String listName = LISTS_PREFIX + randomName();
+ final String listName = LISTS_PREFIX + mIdGenerator.generateTailId();
final Collection listCollection = getDatabase().getCollection(mVContext, listName);
Futures.addCallback(listCollection.create(mVContext, null),
new TrappingCallback<Void>(mActivity) {
@@ -90,8 +93,8 @@
public void onSuccess(@Nullable Void result) {
// These can happen in either order
trap(getUserCollection().put(mVContext, listName, null, VdlAny.class));
- trap(listCollection.put(mVContext, SyncbaseTodoList.LIST_ROW_NAME, listSpec,
- ListSpec.class));
+ trap(listCollection.put(mVContext, SyncbaseTodoList.LIST_METADATA_ROW_NAME,
+ listSpec, ListSpec.class));
}
});
}
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java
index b2b0db9..e475d3d 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbasePersistence.java
@@ -24,7 +24,6 @@
import com.google.common.util.concurrent.SettableFuture;
import java.io.File;
-import java.util.UUID;
import java.util.concurrent.Executors;
import javax.annotation.Nullable;
@@ -186,10 +185,6 @@
return sUserCollection != null;
}
- protected static String randomName() {
- return UUID.randomUUID().toString().replace('-', '_');
- }
-
/**
* A {@link FutureCallback} that reports persistence errors by toasting a short message to the
* user and logging the exception trace and the call stack from where the future was invoked.
diff --git a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java
index 49a4a14..beb8fc5 100644
--- a/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java
+++ b/app/src/syncbase/java/io/v/todos/persistence/syncbase/SyncbaseTodoList.java
@@ -32,7 +32,7 @@
public class SyncbaseTodoList extends SyncbasePersistence implements TodoListPersistence {
public static final String
- LIST_ROW_NAME = "list",
+ LIST_METADATA_ROW_NAME = "list",
TASKS_PREFIX = "tasks_";
private static final String
@@ -40,6 +40,7 @@
private final Collection mList;
private final TodoListListener mListener;
+ private final IdGenerator mIdGenerator = new IdGenerator(IdAlphabets.ROW_NAME, true);
private final Set<String> mTaskIds = new HashSet<>();
/**
@@ -88,7 +89,7 @@
private void processWatchChange(WatchChange change) {
String rowName = change.getRowName();
- if (rowName.equals(SyncbaseTodoList.LIST_ROW_NAME)) {
+ if (rowName.equals(SyncbaseTodoList.LIST_METADATA_ROW_NAME)) {
ListSpec listSpec = SyncbasePersistence.castWatchValue(change.getValue(),
ListSpec.class);
mListener.onUpdate(listSpec);
@@ -96,6 +97,8 @@
mTaskIds.remove(rowName);
mListener.onItemDelete(rowName);
} else {
+ mIdGenerator.registerId(change.getRowName().substring(TASKS_PREFIX.length()));
+
TaskSpec taskSpec = SyncbasePersistence.castWatchValue(change.getValue(),
TaskSpec.class);
Task task = new Task(rowName, taskSpec);
@@ -110,7 +113,7 @@
@Override
public void updateTodoList(ListSpec listSpec) {
- trap(mList.put(mVContext, LIST_ROW_NAME, listSpec, ListSpec.class));
+ trap(mList.put(mVContext, LIST_METADATA_ROW_NAME, listSpec, ListSpec.class));
}
@Override
@@ -121,13 +124,13 @@
public static ListenableFuture<Void> updateListTimestamp(final VContext vContext,
final Collection list) {
- ListenableFuture<Object> get = list.get(vContext, LIST_ROW_NAME, ListSpec.class);
- return Futures.transform(get, new AsyncFunction<Object, Void>() {
+ ListenableFuture<Object> get = list.get(vContext, LIST_METADATA_ROW_NAME, ListSpec.class);
+ return Futures.transformAsync(get, new AsyncFunction<Object, Void>() {
@Override
public ListenableFuture<Void> apply(Object oldValue) throws Exception {
ListSpec listSpec = (ListSpec) oldValue;
listSpec.setUpdatedAt(System.currentTimeMillis());
- return list.put(vContext, LIST_ROW_NAME, listSpec, ListSpec.class);
+ return list.put(vContext, LIST_METADATA_ROW_NAME, listSpec, ListSpec.class);
}
});
}
@@ -138,7 +141,8 @@
@Override
public void addTask(TaskSpec task) {
- trap(mList.put(mVContext, TASKS_PREFIX + randomName(), task, TaskSpec.class));
+ trap(mList.put(mVContext, TASKS_PREFIX + mIdGenerator.generateTailId(), task,
+ TaskSpec.class));
updateListTimestamp();
}
diff --git a/app/src/testSyncbase/java/io/v/todos/persistence/syncbase/IdGeneratorTest.java b/app/src/testSyncbase/java/io/v/todos/persistence/syncbase/IdGeneratorTest.java
new file mode 100644
index 0000000..996db6d
--- /dev/null
+++ b/app/src/testSyncbase/java/io/v/todos/persistence/syncbase/IdGeneratorTest.java
@@ -0,0 +1,100 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package io.v.todos.persistence.syncbase;
+
+import org.junit.Test;
+
+import java.util.Random;
+import java.util.regex.Pattern;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+public class IdGeneratorTest {
+ private static final Pattern COLLECTION_ID_PATTERN = Pattern.compile("[0-9A-Za-z][0-9A-Za-z_]*");
+ private static final Random RANDOM = new Random();
+
+ @Test
+ public void testLongToPaddedIdentifier() {
+ IdGenerator
+ testGeneratorA = new IdGenerator(IdAlphabets.COLLECTION_ID, true),
+ testGeneratorB = new IdGenerator(IdAlphabets.ROW_NAME, true);
+
+ long[] sortedInputs = new long[]{
+ Long.MIN_VALUE,
+ Long.MIN_VALUE + 1,
+ Long.MIN_VALUE + 2,
+ -1,
+ 0,
+ 1,
+ Long.MAX_VALUE - 2,
+ Long.MAX_VALUE - 1,
+ Long.MAX_VALUE
+ };
+ String lastIdA = null, lastIdB = null;
+ for (long input : sortedInputs) {
+ String testId = testGeneratorA.longToPaddedIdentifier(input);
+ if (lastIdA != null) {
+ assertTrue("IdGenerator.longToPaddedIdentifier generates IDs consistent with " +
+ "input ordering", testId.compareTo(lastIdA) > 0);
+ }
+ lastIdA = testId;
+
+ testId = testGeneratorB.longToPaddedIdentifier(input);
+ if (lastIdB != null) {
+ assertTrue("IdGenerator.longToPaddedIdentifier generates IDs consistent with " +
+ "input ordering", testId.compareTo(lastIdB) > 0);
+ }
+ lastIdB = testId;
+ }
+
+ for (int i = 0; i < 50; i++) {
+ // Smoke fuzz test
+ testGeneratorA.longToPaddedIdentifier(RANDOM.nextLong());
+ testGeneratorB.longToPaddedIdentifier(RANDOM.nextLong());
+ }
+ }
+
+ @Test
+ public void testDecodeChar() {
+ for (int i = 0; i < IdAlphabets.COLLECTION_ID.radix(); i++) {
+ char testChar = IdAlphabets.COLLECTION_ID.encodeDigit(i);
+ assertEquals("IdGenerator.decodeChar('" + testChar + "')",
+ i, IdAlphabets.COLLECTION_ID.decodeDigit(testChar));
+ }
+ }
+
+ private void verifyIncrement(String input, String incremented) {
+ String diagnostic = input + " + 1 = " + incremented;
+ assertTrue("IdGenerator.increment generates larger IDs than the input (" + diagnostic + ")",
+ incremented.compareTo(input) > 0);
+ assertTrue("IdGenerator.increment generates legal IDs (" + diagnostic + ")",
+ COLLECTION_ID_PATTERN.matcher(incremented).matches());
+ }
+
+ @Test
+ public void testIncrement() {
+ IdGenerator testGenerator = new IdGenerator(IdAlphabets.COLLECTION_ID, true);
+
+ String[] inputs = new String[]{
+ "0000",
+ "AZ00",
+ "Az00",
+ "Zz00",
+ "zz00",
+ "zzz0",
+ "zzzz"
+ };
+
+ for (String input : inputs) {
+ verifyIncrement(input, testGenerator.increment(input, 2));
+ }
+
+ for (int i = 0; i < 50; i++) {
+ String input = testGenerator.longToPaddedIdentifier(RANDOM.nextLong());
+ verifyIncrement(input, testGenerator.increment(input, RANDOM.nextInt(input.length())));
+ }
+ }
+}
\ No newline at end of file
