1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.id.serial;
18
19 import java.io.Serializable;
20 import java.util.Arrays;
21 import java.util.Calendar;
22 import java.util.TimeZone;
23
24 import org.apache.commons.id.AbstractStringIdentifierGenerator;
25
26
27 /**
28 * <code>TimeBasedAlphanumericIdentifierGenerator</code> is an identifier generator that generates
29 * an alphanumeric identifier in base 36 as a String object from the current UTC time and an
30 * internal counter.
31 * <p>
32 * The generator guarantees that all generated ids have an increasing natural sort order (even if
33 * the time internally has an overflow). The implementation additionally guarantees, that all
34 * instances within the same process do generate unique ids. All generated ids have the same length
35 * (padding with 0's on the left), which is determined by the maximum size of a long value and the
36 * <code>postfixSize</code> parameter passed to the constructor.
37 * </p>
38 * <p>
39 * Note: To ensure unique ids that are created within the same millisecond (or maximum time
40 * resolution of the system), the implementation uses an internal counter. The maximum value of this
41 * counter is determined by the <code>postfixSize</code> parameter i.e. the largest value that can
42 * be represented in base 36. If the counter exceeds this value, an IllegalStateException is thrown.
43 * </p>
44 * <p>
45 * Note: The uniqueness of the generated ids cannot be guaranteed if the system performs time shifts
46 * of more than a second, that affect the running processes.
47 * </p>
48 *
49 * @author Commons-Id team
50 * @version $Id: TimeBasedAlphanumericIdentifierGenerator.java 480488 2006-11-29 08:57:26Z bayard $
51 */
52 public class TimeBasedAlphanumericIdentifierGenerator extends AbstractStringIdentifierGenerator
53 implements Serializable {
54
55 /**
56 * <code>serialVersionUID</code> is the serializable UID for the binary version of the class.
57 */
58 private static final long serialVersionUID = 20060116L;
59 /**
60 * <code>padding</code> an array of '0' for improved padding performance.
61 */
62 private static final char[] padding;
63 static {
64 padding = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH];
65 Arrays.fill(padding, '0');
66 }
67 /**
68 * <code>UTC</code> is the UTC {@link TimeZone} instance.
69 */
70 private static final TimeZone UTC = TimeZone.getTimeZone("UTC");
71 /**
72 * <code>last</code> is the marker, when the counter was resetted the last time.
73 */
74 private static long last = 0;
75 /**
76 * <code>counter</code> counts the number of generated identifiers since the last reset.
77 */
78 private static long counter = 0;
79 /**
80 * <code>postfixSize</code> size of the postfix, that contains the padded counter in base 36.
81 */
82 private final int postfixSize;
83 private final long offset;
84
85 /**
86 * Construct a TimeBasedAlphanumericIdentifierGenerator with a defined size of the postfix and
87 * an offset for the time value. The offset can be used to manipulate the representation of the
88 * time value in the generated id. If a TimeBasedAlphanumericIdentifierGenerator is constructed
89 * with an offset of the current number of milliseconds since 1st Jan 1970 the first generated
90 * id in the same millisecond will have an id consisting of a sequence of '0' characters.
91 *
92 * @param postfixSize the size of the postfix
93 * @param offset the offset taken into account for the time value
94 * @throws IllegalArgumentException if <code>postfixSize</code> is negative or exceeds the
95 * maximum size for representing {@link Long#MAX_VALUE} in base 36
96 */
97 public TimeBasedAlphanumericIdentifierGenerator(final int postfixSize, final long offset) {
98 if (postfixSize < 0 || postfixSize > MAX_LONG_ALPHANUMERIC_VALUE_LENGTH) {
99 throw new IllegalArgumentException("Invalid size for postfix");
100 }
101 this.postfixSize = postfixSize;
102 this.offset = offset;
103 }
104
105 /**
106 * Construct a TimeBasedAlphanumericIdentifierGenerator with a defined size of the postfix.
107 *
108 * @param postfixSize the size of the postfix defining the maximum number of possible ids
109 * generated within the same millisecond (depending on the time resolution of the
110 * running system)
111 * @throws IllegalArgumentException if <code>postfixSize</code> is negative or exceeds the
112 * maximum size for representing {@link Long#MAX_VALUE} in base 36
113 */
114 public TimeBasedAlphanumericIdentifierGenerator(final int postfixSize) {
115 this(postfixSize, 0);
116 }
117
118 /**
119 * Construct a TimeBasedAlphanumericIdentifierGenerator with a default size of the postfix of 3.
120 */
121 public TimeBasedAlphanumericIdentifierGenerator() {
122 this(3);
123 }
124
125 public long maxLength() {
126 return MAX_LONG_ALPHANUMERIC_VALUE_LENGTH + postfixSize;
127 }
128
129 public long minLength() {
130 return maxLength();
131 }
132
133 public String nextStringIdentifier() {
134 long now;
135 synchronized (this) {
136 now = Calendar.getInstance(UTC).getTime().getTime(); // JDK 1.3 compatibility
137 final long diff = now - last;
138 // external time correction of more than a second or overflow
139 if (diff > 0 || diff < -1000) {
140 last = now;
141 counter = 0;
142 } else {
143 if (diff != 0) {
144 now = last; // ignore time shift
145 }
146 ++counter;
147 }
148 }
149 final String postfix = counter > 0
150 ? Long.toString(counter, ALPHA_NUMERIC_CHARSET_SIZE) : "";
151 if (postfix.length() > postfixSize) {
152 throw new IllegalStateException(
153 "The maximum number of identifiers in this millisecond has been reached");
154 }
155 // ensure, that no negative value is used and values stay increasing
156 long base = now - offset;
157 long value = base < 0 ? base + Long.MAX_VALUE + 1 : base;
158 final String time = Long.toString(value, ALPHA_NUMERIC_CHARSET_SIZE);
159 final char[] buffer = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH + postfixSize];
160 int i = 0;
161 int maxPad = MAX_LONG_ALPHANUMERIC_VALUE_LENGTH - time.length();
162 if (maxPad > 0) {
163 System.arraycopy(padding, 0, buffer, 0, maxPad);
164 }
165 System.arraycopy(time.toCharArray(), 0, buffer, maxPad, time.length());
166 if (base < 0) {
167 // Representation of Long.MAX_VALUE starts with '1', negative 'base' means higher value
168 // in time
169 buffer[0] += 2;
170 }
171 i += time.length() + maxPad;
172 if (postfixSize > 0) {
173 maxPad = postfixSize - postfix.length();
174 if (maxPad > 0) {
175 System.arraycopy(padding, 0, buffer, i, maxPad);
176 i += maxPad;
177 }
178 System.arraycopy(postfix.toCharArray(), 0, buffer, i, postfix.length());
179 }
180 return new String(buffer);
181 }
182
183 /**
184 * Retrieve the number of milliseconds since 1st Jan 1970 that were the base for the given id.
185 *
186 * @param id the id to use
187 * @param offset the offset used to create the id
188 * @return the number of milliseconds
189 * @throws IllegalArgumentException if <code>id</code> is not a valid id from this type of
190 * generator
191 */
192 public long getMillisecondsFromId(final Object id, final long offset) {
193 if (id instanceof String && id.toString().length() >= MAX_LONG_ALPHANUMERIC_VALUE_LENGTH) {
194 final char[] buffer = new char[MAX_LONG_ALPHANUMERIC_VALUE_LENGTH];
195 System.arraycopy(
196 id.toString().toCharArray(), 0, buffer, 0, MAX_LONG_ALPHANUMERIC_VALUE_LENGTH);
197 final boolean overflow = buffer[0] > '1';
198 if (overflow) {
199 buffer[0] -= 2;
200 }
201 long value = Long.parseLong(new String(buffer), ALPHA_NUMERIC_CHARSET_SIZE);
202 if (overflow) {
203 value -= Long.MAX_VALUE + 1;
204 }
205 return value + offset;
206 }
207 throw new IllegalArgumentException("'" + id + "' is not an id from this generator");
208 }
209 }