You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@qpid.apache.org by ar...@apache.org on 2008/03/26 10:05:59 UTC
svn commit: r641212 - in /incubator/qpid/trunk/qpid/java/common/src:
main/java/org/apache/qpid/SerialException.java
main/java/org/apache/qpid/util/Serial.java
test/java/org/apache/qpid/util/SerialTest.java
Author: arnaudsimon
Date: Wed Mar 26 02:05:57 2008
New Revision: 641212
URL: http://svn.apache.org/viewvc?rev=641212&view=rev
Log:
Qpid-861: Java RFC 1982 implementation + Junit tests
Added:
incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/SerialException.java
incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/util/Serial.java
incubator/qpid/trunk/qpid/java/common/src/test/java/org/apache/qpid/util/SerialTest.java
Added: incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/SerialException.java
URL: http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/SerialException.java?rev=641212&view=auto
==============================================================================
--- incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/SerialException.java (added)
+++ incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/SerialException.java Wed Mar 26 02:05:57 2008
@@ -0,0 +1,19 @@
+package org.apache.qpid;
+
+/**
+ * This exception is used by the serial class (imp RFC 1982)
+ *
+ */
+public class SerialException extends ArithmeticException
+{
+ /**
+ * Constructs an <code>SerialException</code> with the specified
+ * detail message.
+ *
+ * @param message The exception message.
+ */
+ public SerialException(String message)
+ {
+ super(message);
+ }
+}
Added: incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/util/Serial.java
URL: http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/util/Serial.java?rev=641212&view=auto
==============================================================================
--- incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/util/Serial.java (added)
+++ incubator/qpid/trunk/qpid/java/common/src/main/java/org/apache/qpid/util/Serial.java Wed Mar 26 02:05:57 2008
@@ -0,0 +1,121 @@
+package org.apache.qpid.util;
+
+import org.apache.qpid.SerialException;
+
+/**
+ * This class provides basic
+ * serial number arithmetic as defined in RFC 1982.
+ */
+
+public class Serial
+{
+ private long _maxIncrement;
+ private long _max;
+ private long _maxComparison;
+
+ public Serial(double serialbits)
+ {
+ if( serialbits < 2)
+ {
+ throw new IllegalArgumentException("Meaningful serial number space has SERIAL_BITS >= 2, wrong value "
+ + serialbits);
+ }
+ _max = (long) Math.pow(2.0 , serialbits) - 1;
+ _maxIncrement = (long) Math.pow(2.0, serialbits - 1) - 1;
+ _maxComparison = (long) Math.pow(2.0, serialbits -1);
+ }
+
+ /**
+ * Compares two numbers using serial arithmetic.
+ *
+ * @param serial1 The first serial number
+ * @param serial2 The second serial number
+ * @return 0 if the 2 serials numbers are equal, a positive number if serial1 is greater
+ * than serial2, and a negative number if serial2 is greater than serial1.
+ * @throws IllegalArgumentException serial1 or serial2 is out of range
+ * @throws SerialException serial1 and serial2 are not comparable.
+ */
+ public int compare(long serial1, long serial2) throws IllegalArgumentException, SerialException
+ {
+ int result;
+ if (serial1 < 0 || serial1 > _max)
+ {
+ throw new IllegalArgumentException(serial1 + " out of range");
+ }
+ if (serial2 < 0 || serial2 > _max)
+ {
+ throw new IllegalArgumentException(serial2 + " out of range");
+ }
+ double diff;
+ if( serial1 < serial2 )
+ {
+ diff = serial2 - serial1;
+ if( diff < _maxComparison )
+ {
+ result = -1;
+ }
+ else if ( diff > _maxComparison )
+ {
+ result = 1;
+ }
+ else
+ {
+ throw new SerialException("Cannot compare " + serial1 + " and " + serial2);
+ }
+ }
+ else if( serial1 > serial2 )
+ {
+ diff = serial1 - serial2;
+ if( diff > _maxComparison )
+ {
+ result = -1;
+ }
+ else if( diff < _maxComparison )
+ {
+ result = 1;
+ }
+ else
+ {
+ throw new SerialException("Cannot compare " + serial1 + " and " + serial2);
+ }
+ }
+ else
+ {
+ result = 0;
+ }
+ return result;
+ }
+
+
+ /**
+ * Increments a serial numbers by the addition of a positive integer n,
+ * Serial numbers may be incremented by the addition of a positive
+ * integer n, where n is taken from the range of integers
+ * [0 .. (2^(SERIAL_BITS - 1) - 1)]. For a sequence number s, the
+ * result of such an addition, s', is defined as
+ * s' = (s + n) modulo (2 ^ SERIAL_BITS)
+ * @param serial The serila number to be incremented
+ * @param n The integer to be added to the serial number
+ * @return The incremented serial number
+ * @throws IllegalArgumentException serial number or n is out of range
+ */
+ public long increment(long serial, long n) throws IllegalArgumentException
+ {
+ if (serial < 0 || serial > _max)
+ {
+ throw new IllegalArgumentException("Serial number: " + serial + " is out of range");
+ }
+ if( n < 0 || n > _maxIncrement )
+ {
+ throw new IllegalArgumentException("Increment: " + n + " is out of range");
+ }
+ long result = serial + n;
+ // apply modulo (2 ^ SERIAL_BITS)
+ if(result > _max)
+ {
+ result = result - _max - 1;
+ }
+ return result;
+ }
+
+}
Added: incubator/qpid/trunk/qpid/java/common/src/test/java/org/apache/qpid/util/SerialTest.java
URL: http://svn.apache.org/viewvc/incubator/qpid/trunk/qpid/java/common/src/test/java/org/apache/qpid/util/SerialTest.java?rev=641212&view=auto
==============================================================================
--- incubator/qpid/trunk/qpid/java/common/src/test/java/org/apache/qpid/util/SerialTest.java (added)
+++ incubator/qpid/trunk/qpid/java/common/src/test/java/org/apache/qpid/util/SerialTest.java Wed Mar 26 02:05:57 2008
@@ -0,0 +1,135 @@
+package org.apache.qpid.util;
+
+import junit.framework.TestCase;
+
+import java.util.Random;
+
+import org.apache.qpid.SerialException;
+
+/**
+ *Junit tests for the Serial class
+ */
+public class SerialTest extends TestCase
+{
+
+ /**
+ * The simplest meaningful serial number space has SERIAL_BITS == 2. In
+ * this space, the integers that make up the serial number space are 0,
+ * 1, 2, and 3. That is, 3 == 2^SERIAL_BITS - 1.
+ *
+ * In this space, the largest integer that it is meaningful to add to a
+ * sequence number is 2^(SERIAL_BITS - 1) - 1, or 1.
+ *
+ * Then, as defined 0+1 == 1, 1+1 == 2, 2+1 == 3, and 3+1 == 0.
+ * Further, 1 > 0, 2 > 1, 3 > 2, and 0 > 3. It is undefined whether
+ * 2 > 0 or 0 > 2, and whether 1 > 3 or 3 > 1.
+ */
+ public void testTrivialSample()
+ {
+ Serial serial = new Serial(2);
+ assertEquals( serial.increment(0, 1), 1);
+ assertEquals( serial.increment(1, 1), 2);
+ assertEquals( serial.increment(2, 1), 3);
+ assertEquals( serial.increment(3, 1), 0);
+ try
+ {
+ serial.increment(4, 1);
+ fail("IllegalArgumentException was not trhown");
+ }
+ catch (IllegalArgumentException e)
+ {
+ // expected
+ }
+ try
+ {
+ assertTrue( serial.compare(1, 0) > 0);
+ assertTrue( serial.compare(2, 1) > 0);
+ assertTrue( serial.compare(3, 2) > 0);
+ assertTrue( serial.compare(0, 3) > 0);
+ assertTrue( serial.compare(0, 1) < 0);
+ assertTrue( serial.compare(1, 2) < 0);
+ assertTrue( serial.compare(2, 3) < 0);
+ assertTrue( serial.compare(3, 0) < 0);
+ }
+ catch (SerialException e)
+ {
+ fail("Unexpected exception " + e);
+ }
+ try
+ {
+ serial.compare(2, 0);
+ fail("AMQSerialException not thrown as expected");
+ }
+ catch (SerialException e)
+ {
+ // expected
+ }
+ try
+ {
+ serial.compare(0, 2);
+ fail("AMQSerialException not thrown as expected");
+ }
+ catch (SerialException e)
+ {
+ // expected
+ }
+ try
+ {
+ serial.compare(3, 1);
+ fail("AMQSerialException not thrown as expected");
+ }
+ catch (SerialException e)
+ {
+ // expected
+ }
+ try
+ {
+ serial.compare(3, 1);
+ fail("AMQSerialException not thrown as expected");
+ }
+ catch (SerialException e)
+ {
+ // expected
+ }
+ }
+
+ /**
+ * Test the first Corollary of RFC 1982
+ * For any sequence number s and any integer n such that addition of n
+ * to s is well defined, (s + n) >= s. Further (s + n) == s only when
+ * n == 0, in all other defined cases, (s + n) > s.
+ * strategy:
+ * Create a serial number with 32 bits and check in a loop that adding integers
+ * respect the corollary
+ */
+ public void testCorollary1()
+ {
+ Serial serial = new Serial(32);
+ Random random = new Random();
+ long number = random.nextInt((int) Math.pow(2.0 , 32.0) - 1);
+ for(int i = 1; i<= 10000; i++ )
+ {
+ long nextInt = random.nextInt((int) Math.pow(2.0 , 32.0) - 1);
+ long inc = serial.increment(number, nextInt);
+ int res =0;
+ try
+ {
+ res=serial.compare(inc, number);
+ }
+ catch (SerialException e)
+ {
+ fail("un-expected exception " + e);
+ }
+ if( res < 1 )
+ {
+ fail("Corollary 1 violated " + number + " + " + nextInt + " < " + number);
+ }
+ else if( res == 0 && nextInt > 0)
+ {
+ fail("Corollary 1 violated " + number + " + " + nextInt + " = " + number);
+ }
+ }
+ }
+
+
+}