001: /*
002: * Written by Dawid Kurzyniec, based on code written by Doug Lea with assistance
003: * from members of JCP JSR-166 Expert Group. Released to the public domain,
004: * as explained at http://creativecommons.org/licenses/publicdomain.
005: *
006: * Thanks to Craig Mattocks for suggesting to use <code>sun.misc.Perf</code>.
007: */
008:
009: package org.drools.util.concurrent.locks;
010:
011: import java.security.AccessController;
012: import java.security.PrivilegedAction;
013: import java.lang.reflect.Array;
014: import java.util.Iterator;
015: import java.util.Collection;
016:
017: import org.drools.util.ArrayUtils;
018:
019: /**
020: * <p>
021: * This class groups together the functionality of java.util.concurrent that
022: * cannot be fully and reliably implemented in backport, but for which some
023: * form of emulation is possible.
024: * <p>
025: * Currently, this class contains methods related to nanosecond-precision
026: * timing, particularly via the {@link #nanoTime} method. To measure time
027: * accurately, this method by default uses <code>java.sun.Perf</code> on
028: * JDK1.4.2 and it falls back to <code>System.currentTimeMillis</code>
029: * on earlier JDKs.
030: *
031: * @author Dawid Kurzyniec
032: * @version 1.0
033: */
034: public final class Utils {
035:
036: private final static NanoTimer nanoTimer;
037: private final static String providerProp = "edu.emory.mathcs.backport.java.util.concurrent.NanoTimerProvider";
038:
039: static {
040: NanoTimer timer = null;
041: try {
042: String nanoTimerClassName = (String) AccessController
043: .doPrivileged(new PrivilegedAction() {
044: public Object run() {
045: return System.getProperty(providerProp);
046: }
047: });
048: if (nanoTimerClassName != null) {
049: Class cls = Class.forName(nanoTimerClassName);
050: timer = (NanoTimer) cls.newInstance();
051: }
052: } catch (Exception e) {
053: System.err
054: .println("WARNING: unable to load the system-property-defined "
055: + "nanotime provider; switching to the default");
056: e.printStackTrace();
057: }
058:
059: if (timer == null) {
060: try {
061: timer = new SunPerfProvider();
062: } catch (Throwable e) {
063: }
064: }
065:
066: if (timer == null) {
067: timer = new MillisProvider();
068: }
069:
070: nanoTimer = timer;
071: }
072:
073: private Utils() {
074: }
075:
076: /**
077: * Returns the current value of the most precise available system timer,
078: * in nanoseconds. This method can only be used to measure elapsed time and
079: * is not related to any other notion of system or wall-clock time. The
080: * value returned represents nanoseconds since some fixed but arbitrary
081: * time (perhaps in the future, so values may be negative). This method
082: * provides nanosecond precision, but not necessarily nanosecond accuracy.
083: * No guarantees are made about how frequently values change. Differences
084: * in successive calls that span greater than approximately 292 years
085: * (2^63 nanoseconds) will not accurately compute elapsed time due to
086: * numerical overflow.
087: * <p>
088: * <em>Implementation note:</em>By default, this method uses
089: * <code>sun.misc.Perf</code> on Java 1.4.2, and falls back to
090: * System.currentTimeMillis() emulation on earlier JDKs. Custom
091: * timer can be provided via the system property
092: * <code>edu.emory.mathcs.backport.java.util.concurrent.NanoTimerProvider</code>.
093: * The value of the property should name a class implementing
094: * {@link NanoTimer} interface.
095: * <p>
096: * Note: on JDK 1.4.2, <code>sun.misc.Perf</code> timer seems to have
097: * resolution of the order of 1 microsecond, measured on Linux.
098: *
099: * @return The current value of the system timer, in nanoseconds.
100: */
101: public static long nanoTime() {
102: return nanoTimer.nanoTime();
103: }
104:
105: private static final class SunPerfProvider implements NanoTimer {
106: final sun.misc.Perf perf;
107: final long multiplier, divisor;
108:
109: SunPerfProvider() {
110: perf = (sun.misc.Perf) AccessController
111: .doPrivileged(new PrivilegedAction() {
112: public Object run() {
113: return sun.misc.Perf.getPerf();
114: }
115: });
116: // trying to avoid BOTH overflow and rounding errors
117: long numerator = 1000000000;
118: long denominator = perf.highResFrequency();
119: long gcd = gcd(numerator, denominator);
120: this .multiplier = numerator / gcd;
121: this .divisor = denominator / gcd;
122: }
123:
124: public long nanoTime() {
125: long ctr = perf.highResCounter();
126:
127: // anything less sophisticated suffers either from rounding errors
128: // (FP arithmetics, backport v1.0) or overflow, when gcd is small
129: // (a bug in backport v1.0_01 reported by Ramesh Nethi)
130:
131: return ((ctr / divisor) * multiplier) + (ctr % divisor)
132: * multiplier / divisor;
133:
134: // even the above can theoretically cause problems if your JVM is
135: // running for sufficiently long time, but "sufficiently" means 292
136: // years (worst case), or 30,000 years (common case).
137:
138: // Details: when the ticks ctr overflows, there is no way to avoid
139: // discontinuity in computed nanos, even in infinite arithmetics,
140: // unless we count number of overflows that the ctr went through
141: // since the JVM started. This follows from the fact that
142: // (2^64*multiplier/divisor) mod (2^64) > 0 in general case.
143: // Theoretically we could find out the number of overflows by
144: // checking System.currentTimeMillis(), but this is unreliable
145: // since the system time can unpredictably change during the JVM
146: // lifetime.
147: // The time to overflow is 2^63 / ticks frequency. With current
148: // ticks frequencies of several MHz, it gives about 30,000 years
149: // before the problem happens. If ticks frequency reaches 1 GHz, the
150: // time to overflow is 292 years. It is unlikely that the frequency
151: // ever exceeds 1 GHz. We could double the time to overflow
152: // (to 2^64 / frequency) by using unsigned arithmetics, e.g. by
153: // adding the following correction whenever the ticks is negative:
154: // -2*((Long.MIN_VALUE / divisor) * multiplier +
155: // (Long.MIN_VALUE % divisor) * multiplier / divisor)
156: // But, with the worst case of as much as 292 years, it does not
157: // seem justified.
158: }
159: }
160:
161: private static final class MillisProvider implements NanoTimer {
162: MillisProvider() {
163: }
164:
165: public long nanoTime() {
166: return System.currentTimeMillis() * 1000000;
167: }
168: }
169:
170: private static long gcd(long a, long b) {
171: long r;
172: while (b > 0) {
173: r = a % b;
174: a = b;
175: b = r;
176: }
177: return a;
178: }
179:
180: public static Object[] collectionToArray(Collection c) {
181: // guess the array size; expect to possibly be different
182: int len = c.size();
183: Object[] arr = new Object[len];
184: Iterator itr = c.iterator();
185: int idx = 0;
186: while (true) {
187: while (idx < len && itr.hasNext()) {
188: arr[idx++] = itr.next();
189: }
190: if (!itr.hasNext()) {
191: if (idx == len)
192: return arr;
193: // otherwise have to trim
194: return ArrayUtils.copyOf(arr, idx, Object[].class);
195: }
196: // otherwise, have to grow
197: int newcap = ((arr.length / 2) + 1) * 3;
198: if (newcap < arr.length) {
199: // overflow
200: if (arr.length < Integer.MAX_VALUE) {
201: newcap = Integer.MAX_VALUE;
202: } else {
203: throw new OutOfMemoryError(
204: "required array size too large");
205: }
206: }
207: arr = ArrayUtils.copyOf(arr, newcap, Object[].class);
208: len = newcap;
209: }
210: }
211:
212: public static Object[] collectionToArray(Collection c, Object[] a) {
213: Class aType = a.getClass();
214: // guess the array size; expect to possibly be different
215: int len = c.size();
216: Object[] arr = (a.length >= len ? a : (Object[]) Array
217: .newInstance(aType.getComponentType(), len));
218: Iterator itr = c.iterator();
219: int idx = 0;
220: while (true) {
221: while (idx < len && itr.hasNext()) {
222: arr[idx++] = itr.next();
223: }
224: if (!itr.hasNext()) {
225: if (idx == len)
226: return arr;
227: if (arr == a) {
228: // orig array -> null terminate
229: a[idx] = null;
230: return a;
231: } else {
232: // have to trim
233: return ArrayUtils.copyOf(arr, idx, aType);
234: }
235: }
236: // otherwise, have to grow
237: int newcap = ((arr.length / 2) + 1) * 3;
238: if (newcap < arr.length) {
239: // overflow
240: if (arr.length < Integer.MAX_VALUE) {
241: newcap = Integer.MAX_VALUE;
242: } else {
243: throw new OutOfMemoryError(
244: "required array size too large");
245: }
246: }
247: arr = ArrayUtils.copyOf(arr, newcap, aType);
248: len = newcap;
249: }
250: }
251: }
|