You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by ps...@apache.org on 2005/09/19 00:31:52 UTC
svn commit: r289992 - in /jakarta/commons/sandbox/id/trunk: project.xml
src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
Author: psteitz
Date: Sun Sep 18 15:31:47 2005
New Revision: 289992
URL: http://svn.apache.org/viewcvs?rev=289992&view=rev
Log:
Added TimeBasedAlphanumericIdentifierGenerator
PR# 36683
Contributed by Jorg Schaible
Added:
jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java (with props)
jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java (with props)
Modified:
jakarta/commons/sandbox/id/trunk/project.xml
Modified: jakarta/commons/sandbox/id/trunk/project.xml
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/id/trunk/project.xml?rev=289992&r1=289991&r2=289992&view=diff
==============================================================================
--- jakarta/commons/sandbox/id/trunk/project.xml (original)
+++ jakarta/commons/sandbox/id/trunk/project.xml Sun Sep 18 15:31:47 2005
@@ -119,6 +119,9 @@
<email>rwinston@eircom.net</email>
<organization></organization>
</contributor>
+ <contributor>
+ <name>Jörg Schaible</name>
+ </contributor>
<contributor>
<name>Jukka Zitting</name>
</contributor>
Added: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java?rev=289992&view=auto
==============================================================================
--- jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java (added)
+++ jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java Sun Sep 18 15:31:47 2005
@@ -0,0 +1,172 @@
+/*
+ * Copyright 2005 The Apache Software Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.id.serial;
+
+import java.util.Arrays;
+import java.util.Calendar;
+import java.util.TimeZone;
+
+import org.apache.commons.id.AbstractStringIdentifierGenerator;
+
+
+/**
+ * <p>
+ * <code>TimeBasedAlphanumericIdentifierGenerator</code> is an Identifier Generator that generates an alphanumeric
+ * identifier in base 36 as a String object from the current UTC time and an internal counter.
+ * </p>
+ * <p>
+ * The generator guarantees that all generated ids have an increasing natural sort order (even if the time internally
+ * has an overflow). The implementation additionally guarantees, that all instances within the same process do generate
+ * unique ids. All generated ids have the same length (padding with 0's on the left), which is determined by the maximum
+ * size of a long value and the <code>postfixSize</code> parameter passed to the constructor.
+ * </p>
+ * <p>
+ * Note: To ensure unique ids that are created within the same millisecond (or maximum time resolution of the system),
+ * the implementation uses an internal counter. The maximum value of this counter is determined by the
+ * <code>postfixSize</code> parameter i.e. the largest value that can be represented in base 36. If the counter
+ * exceeds this value, an IllegalStateException is thrown.
+ * </p>
+ * <p>
+ * Note: The uniqueness of the generated ids cannot be guaranteed if the system performs time shifts, that affect the
+ * running processes.
+ * </p>
+ * @author Commons-Id team
+ * @version $Id$
+ */
+public class TimeBasedAlphanumericIdentifierGenerator extends AbstractStringIdentifierGenerator {
+
+ final private static char[] padding;
+ static {
+ padding = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH];
+ Arrays.fill(padding, '0');
+ }
+ final private static TimeZone UTC = TimeZone.getTimeZone("UTC");
+ private static long last = 0;
+ private static long counter = 0;
+ final private int postfixSize;
+ private final long offset;
+
+ /**
+ * Construct a TimeBasedAlphanumericIdentifierGenerator with a defined size of the postfix and an offset for the
+ * time value. The offset can be used to manipulate the representation of the time value in the generated id. If a
+ * TimeBasedAlphanumericIdentifierGenerator is constructed with an offset of the current number of milliseconds
+ * since 1st Jan 1970 the first generated id in the same millisecond will have an id consisting of a sequence of '0'
+ * characters.
+ * @param postfixSize the size of the postfix
+ * @param offset the offset taken into account for the time value
+ * @throws IllegalArgumentException if <code>postfixSize</code> is negative or exceeds the maximum size for
+ * representing {@link Long#MAX_VALUE} in base 36
+ */
+ public TimeBasedAlphanumericIdentifierGenerator(final int postfixSize, final long offset) {
+ if (postfixSize < 0 || postfixSize > MAX_LONG_ALPHANUMERIC_VALUE_LENGTH) {
+ throw new IllegalArgumentException("Invalid size for postfix");
+ }
+ this.postfixSize = postfixSize;
+ this.offset = offset;
+ }
+
+ /**
+ * Construct a TimeBasedAlphanumericIdentifierGenerator with a defined size of the postfix.
+ * @param postfixSize the size of the postfix defining the maximum number of possible ids generated within the same
+ * millisecond (depending on the time resolution of the running system)
+ * @throws IllegalArgumentException if <code>postfixSize</code> is negative or exceeds the maximum size for
+ * representing {@link Long#MAX_VALUE} in base 36
+ */
+ public TimeBasedAlphanumericIdentifierGenerator(final int postfixSize) {
+ this(postfixSize, 0);
+ }
+
+ /**
+ * Construct a TimeBasedAlphanumericIdentifierGenerator with a default size of the postfix of 3.
+ */
+ public TimeBasedAlphanumericIdentifierGenerator() {
+ this(3);
+ }
+
+ public long maxLength() {
+ return MAX_LONG_ALPHANUMERIC_VALUE_LENGTH + postfixSize;
+ }
+
+ public long minLength() {
+ return maxLength();
+ }
+
+ public String nextStringIdentifier() {
+ final long now;
+ synchronized (this) {
+ now = Calendar.getInstance(UTC).getTime().getTime(); // JDK 1.3 compatibility
+ if (now != last) {
+ last = now;
+ counter = 0;
+ } else {
+ ++counter;
+ }
+ }
+ final String postfix = counter > 0 ? Long.toString(counter, ALPHA_NUMERIC_CHARSET_SIZE) : "";
+ if (postfix.length() > postfixSize) {
+ throw new IllegalStateException("The maximum number of identifiers in this millisecond has been reached");
+ }
+ // ensure, that no negative value is used and values stay increasing
+ long base = now - offset;
+ long value = base < 0 ? base + Long.MAX_VALUE + 1 : base;
+ final String time = Long.toString(value, ALPHA_NUMERIC_CHARSET_SIZE);
+ final char[] buffer = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH + postfixSize];
+ int i = 0;
+ int maxPad = MAX_LONG_ALPHANUMERIC_VALUE_LENGTH - time.length();
+ if (maxPad > 0) {
+ System.arraycopy(padding, 0, buffer, 0, maxPad);
+ }
+ System.arraycopy(time.toCharArray(), 0, buffer, maxPad, time.length());
+ if (base < 0) {
+ // Representation of Long.MAX_VALUE starts with '1', negative 'base' means higher value in time
+ buffer[0] += 2;
+ }
+ i += time.length() + maxPad;
+ if (postfixSize > 0) {
+ maxPad = postfixSize - postfix.length();
+ if (maxPad > 0) {
+ System.arraycopy(padding, 0, buffer, i, maxPad);
+ i += maxPad;
+ }
+ System.arraycopy(postfix.toCharArray(), 0, buffer, i, postfix.length());
+ }
+ return new String(buffer);
+ }
+
+ /**
+ * Retrieve the number of milliseconds since 1st Jan 1970 that were the base for the given id.
+ * @param id the id to use
+ * @param offset the offset used to create the id
+ * @return the number of milliseconds
+ * @throws IllegalArgumentException if <code>id</code> is not a valid id from this type of generator
+ */
+ public long getMillisecondsFromId(final Object id, final long offset) {
+ if (id instanceof String && id.toString().length() >= MAX_LONG_ALPHANUMERIC_VALUE_LENGTH) {
+ final char[] buffer = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH];
+ System.arraycopy(id.toString().toCharArray(), 0, buffer, 0, MAX_LONG_ALPHANUMERIC_VALUE_LENGTH);
+ final boolean overflow = buffer[0] > '1';
+ if (overflow) {
+ buffer[0] -= 2;
+ }
+ long value = Long.parseLong(new String(buffer), ALPHA_NUMERIC_CHARSET_SIZE);
+ if (overflow) {
+ value -= Long.MAX_VALUE + 1;
+ }
+ return value + offset;
+ }
+ throw new IllegalArgumentException("'" + id + "' is not an id from this generator");
+ }
+}
Propchange: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/id/trunk/src/java/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGenerator.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
Added: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
URL: http://svn.apache.org/viewcvs/jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java?rev=289992&view=auto
==============================================================================
--- jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java (added)
+++ jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java Sun Sep 18 15:31:47 2005
@@ -0,0 +1,218 @@
+/*
+ * Copyright 2005 The Apache Software Foundation.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.id.serial;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Calendar;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.TimeZone;
+
+import org.apache.commons.id.IdentifierGenerator;
+import org.apache.commons.id.StringIdentifierGenerator;
+
+import junit.framework.TestCase;
+
+
+/**
+ * @author Jörg Schaible
+ */
+public class TimeBasedAlphanumericIdentifierGeneratorTest extends TestCase {
+
+ protected void setUp() throws Exception {
+ super.setUp();
+ Thread.sleep(50); // Ensure no side-effect with previous tests (depends on timer resolution)
+ }
+
+ /**
+ * Test constant size of generated identifier.
+ */
+ public void testIdentifierSizeIsConstant() {
+ final int maxSize = Long.toString(Long.MAX_VALUE, 36).length();
+ StringIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(0);
+ assertEquals(maxSize, idGenerator.nextStringIdentifier().length());
+ assertEquals(maxSize, idGenerator.maxLength());
+ assertEquals(maxSize, idGenerator.minLength());
+ idGenerator = new TimeBasedAlphanumericIdentifierGenerator(1);
+ assertEquals(maxSize + 1, idGenerator.nextStringIdentifier().length());
+ assertEquals(maxSize + 1, idGenerator.maxLength());
+ assertEquals(maxSize + 1, idGenerator.minLength());
+ idGenerator = new TimeBasedAlphanumericIdentifierGenerator(10);
+ assertEquals(maxSize + 10, idGenerator.nextStringIdentifier().length());
+ assertEquals(maxSize + 10, idGenerator.maxLength());
+ assertEquals(maxSize + 10, idGenerator.minLength());
+ }
+
+ /**
+ * Test illegal values for the postfix size.
+ */
+ public void testIllegalPostfixSize() {
+ try {
+ new TimeBasedAlphanumericIdentifierGenerator(-1);
+ fail("Thrown " + IllegalArgumentException.class.getName() + " expected");
+ } catch (final IllegalArgumentException e) {
+ // OK
+ }
+ final int maxSize = Long.toString(Long.MAX_VALUE, 36).length();
+ try {
+ new TimeBasedAlphanumericIdentifierGenerator(maxSize + 1);
+ fail("Thrown " + IllegalArgumentException.class.getName() + " expected");
+ } catch (final IllegalArgumentException e) {
+ // OK
+ }
+ }
+
+ /**
+ * Test that an IllegalStateException is thrown if no more unique identifiers can be generated.
+ */
+ public void testIllegalStateWhenTooManyIdentifiersGenerated() {
+ final IdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(0);
+ idGenerator.nextIdentifier();
+ try {
+ idGenerator.nextIdentifier();
+ // ensure exception even if a new time slice has been started between the last two calls
+ idGenerator.nextIdentifier();
+ fail("Thrown " + IllegalStateException.class.getName() + " expected");
+ } catch (final IllegalStateException e) {
+ // OK
+ }
+ }
+
+ /**
+ * Test that the generator can be tweaked to start with '0'.
+ */
+ public void testMayStartWithIdentifierOfZeros() {
+ final int maxSize = Long.toString(Long.MAX_VALUE, 36).length();
+ final char[] zeros = new char[maxSize];
+ Arrays.fill(zeros, '0');
+
+ // synchronize with current time slice ...
+ final long waitForNextPeriod = System.currentTimeMillis();
+ long next = waitForNextPeriod;
+ while (next == waitForNextPeriod) {
+ next = System.currentTimeMillis();
+ }
+
+ // ... next id should be in same time slice if it is used as current offset
+ final StringIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(0, next);
+
+ assertEquals(new String(zeros), idGenerator.nextStringIdentifier());
+ }
+
+ /**
+ * Ensure that the default postfix size is big enough for a lot faster computers.
+ */
+ public void testDefaultPostfixSizeIsGoodEnough() {
+ final List idList = new ArrayList();
+
+ final IdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator();
+
+ // synchronize with current time slice ...
+ long waitForNextPeriod = System.currentTimeMillis();
+ long next = waitForNextPeriod;
+ while (next == waitForNextPeriod) {
+ next = System.currentTimeMillis();
+ }
+
+ // ... and now generate in the current one as much as possible
+ waitForNextPeriod = next;
+ while (next == waitForNextPeriod) {
+ idList.add(idGenerator.nextIdentifier());
+ next = System.currentTimeMillis();
+ }
+
+ // should not exceed the 10th number of possible values
+ assertTrue(idList.size() < (36 * 36 * 36) / 10);
+ }
+
+ /**
+ * Test if generator can handle an internal overflow as it may happen for time values and still delivers increasing
+ * ids.
+ */
+ public void testInternalOverflowStillIncreasesIds() {
+ final List idList = new ArrayList();
+ final TimeZone utc = TimeZone.getTimeZone("UTC");
+ final long first = Calendar.getInstance(utc).getTime().getTime();
+ final long offset = first < 0 ? 0 : -(Long.MAX_VALUE - first - 100); // 100 ms before internal overflow
+ final IdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(3, offset);
+ while (Calendar.getInstance(utc).getTime().getTime() - first < 200) {
+ idList.add(idGenerator.nextIdentifier());
+ }
+ final List sorted = new ArrayList(idList);
+ Collections.sort(sorted);
+ assertEquals(idList, sorted);
+ }
+
+ /**
+ * Test ensures, that generator can recalculate the time from the id if internally no overflow had happened.
+ */
+ public void testCanRetrieveTimeFromIdWithoutInternalOverflow() {
+ // synchronize with current time slice ...
+ final long waitForNextPeriod = System.currentTimeMillis();
+ final TimeBasedAlphanumericIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(
+ 4, waitForNextPeriod - 1000);
+
+ long next = waitForNextPeriod;
+ while (next == waitForNextPeriod) {
+ next = System.currentTimeMillis();
+ }
+
+ final String id = idGenerator.nextStringIdentifier();
+ assertEquals(next, idGenerator.getMillisecondsFromId(id, waitForNextPeriod - 1000));
+ }
+
+ /**
+ * Test ensures, that generator can recalculate the time from the id even if internally an overflow had happened.
+ */
+ public void testCanRetrieveTimeFromIdWithInternalOverflow() {
+ // synchronize with current time slice ...
+ final long waitForNextPeriod = System.currentTimeMillis();
+ final TimeBasedAlphanumericIdentifierGenerator idGenerator = new TimeBasedAlphanumericIdentifierGenerator(
+ 4, waitForNextPeriod + 1000);
+
+ long next = waitForNextPeriod;
+ while (next == waitForNextPeriod) {
+ next = System.currentTimeMillis();
+ }
+
+ final String id = idGenerator.nextStringIdentifier();
+ assertEquals(next, idGenerator.getMillisecondsFromId(id, waitForNextPeriod + 1000));
+ }
+
+ /**
+ * Test if different instances of the generator still deliver unique ids.
+ */
+ public void testDifferentGeneratorInstancesWillProduceStillUniqueIds() {
+ final IdentifierGenerator idGenerators[] = new IdentifierGenerator[] {
+ new TimeBasedAlphanumericIdentifierGenerator(),
+ new TimeBasedAlphanumericIdentifierGenerator(),
+ new TimeBasedAlphanumericIdentifierGenerator(),
+ };
+
+ final int loop = 1000;
+ final List idList = new ArrayList();
+ for(int i = loop; i-- > 0; ) {
+ for (int j = 0; j < idGenerators.length; ++j) {
+ idList.add(idGenerators[j].nextIdentifier());
+ }
+ }
+
+ assertEquals(loop * idGenerators.length, idList.size());
+ assertEquals(loop * idGenerators.length, new HashSet(idList).size());
+ }
+}
Propchange: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
------------------------------------------------------------------------------
svn:eol-style = native
Propchange: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
------------------------------------------------------------------------------
svn:keywords = Date Author Id Revision HeadURL
Propchange: jakarta/commons/sandbox/id/trunk/src/test/org/apache/commons/id/serial/TimeBasedAlphanumericIdentifierGeneratorTest.java
------------------------------------------------------------------------------
svn:mime-type = text/plain
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org