Tuesday, October 20, 2009

Comparing XML payloads during testing (Java)

Update: This solution assumes both payloads have same (deep) order of attributes and elements.

Writing tests often requires XML payloads to be compared for equality. As such, XML payloads cannot be compared using String.equals() method due to possible differences in canonical representations of similar payloads.

For an example, these are equal XML payloads but not equal strings:


<person>
<name>Neil</name>
<age>31</age>
</person>

<person><name>Neil</name><age>31</age></person>


In this post I am listing a solution I wrote some time ago to compare XML payloads.

import java.io.IOException;
import java.io.StringReader;

import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.SAXParseException;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.DefaultHandler;
import org.xml.sax.helpers.XMLReaderFactory;

public class XMLCompare extends DefaultHandler {

private StringBuilder accumulator = new StringBuilder();

public static boolean equal(String xml1, String xml2)
throws SAXException, IOException {
return new XMLCompare().compareEqual(xml1, xml2);
}

private boolean compareEqual(String actualXML, String expectedXML)
throws IOException {

XMLReader xr = null;
try {
xr = XMLReaderFactory.createXMLReader();
} catch (SAXException e) {
throw new IllegalStateException("Unable to get XMLReader object");
}
xr.setContentHandler(this);
xr.setErrorHandler(this);

accumulator = new StringBuilder("");
try {
xr.parse(new InputSource(new StringReader(actualXML)));
} catch (SAXException e) {
throw new IllegalStateException(getInvalidXMLExceptionMessage(
"ActualXML", actualXML));
}
String xmlString1 = accumulator.toString();
accumulator = new StringBuilder("");
try {
xr.parse(new InputSource(new StringReader(expectedXML)));
} catch (SAXException e) {
throw new IllegalStateException(getInvalidXMLExceptionMessage(
"ExpectedXML", expectedXML));
}
String xmlString2 = accumulator.toString();
return xmlString1.equals(xmlString2);
}

private String getInvalidXMLExceptionMessage(String prefix, String xml) {
return "" + prefix + " is not valid XML: **" + xml + "**";
}

/* --- Event handlers --- */

@Override
public void startDocument () { }

@Override
public void endDocument () { }

// Every time the parser encounters the beginning of a new element, it
// calls this method, which resets the string buffer
@Override
public void startElement (String uri, String name,
String qName, Attributes atts) {
appendStartElement(accumulator, uri, name, qName, atts);
}

private static void appendStartElement(StringBuilder string,
String uri, String name, String qName,
Attributes attributes) {
if ("".equals(uri)) {
string.append("<" + qName);
} else {
string.append("<{" + uri + "}" + name);
}
for (int i=0; i < attributes.getLength(); i++) {
string.append(" " + attributes.getLocalName(i) + "=\"" +
attributes.getValue(i) + "\"");
}
string.append(">");
}

// When the parser encounters the end of an element, it calls this method
@Override
public void endElement (String uri, String name, String qName) {
accumulator.append("</");
if ("".equals (uri)) {
accumulator.append(qName);
} else {
accumulator.append("{" + uri + "}" + name);
}
accumulator.append(">");
}

// When the parser encounters plain text (not XML elements), it calls
// this method, which accumulates them in a string buffer
@Override
public void characters (char ch[], int start, int length) {
for (int i = start; i < start + length; i++) {
if (!Character.isWhitespace(ch[i])) {
accumulator.append(ch[i]);
}
}
}

/** This method is called when warnings occur */
@Override
public void warning(SAXParseException exception) throws SAXException {
System.err.println("WARNING: line " + exception.getLineNumber() + ": "+
exception.getMessage());
throw(exception);
}

/** This method is called when errors occur */
@Override
public void error(SAXParseException exception) throws SAXException {
System.err.println("ERROR: line " + exception.getLineNumber() + ": " +
exception.getMessage());
throw(exception);
}

/** This method is called when non-recoverable errors occur. */
@Override
public void fatalError(SAXParseException exception) throws SAXException {
System.err.println("FATAL: line " + exception.getLineNumber() + ": " +
exception.getMessage());
throw(exception);
}

}



Thanks for reading through here -- your feedback is most welcome.

Saturday, October 17, 2009

Collections.synchronizedXxx() methods are bad for concurrent scenarios (Java)

The java.util.Collections class provides easy factory methods for collections and maps. In this post, I am trying to highlight why the synchronizedXxx() methods are bad for concurrent scenarios. If you look at the source code of Sun JDK and IBM JDK (I haven't checked Oracle/BEA's) for these methods:


Collections.synchronizedList
Collections.synchronizedSet
Collections.synchronizedMap


you will find they essentially maintain a storage-object-level mutex -- every access obtains a lock upon that mutex to maintain thread-safety before going ahead with the operation. For concurrent scenarios, this is a disaster because you can only invoke one operation at a time.

Fortunately, there are few alternatives you can look at right inside the JDK. For maps, you can use:


java.util.concurrent.ConcurrentHashMap


and for lists or sets, you can look at these:


java.util.concurrent.CopyOnWriteArrayList
java.util.concurrent.CopyOnWriteArraySet


Java 6 users can also use these (Note: they are not O(1), but rather O(log(n)) operations):


java.util.concurrent.ConcurrentSkipListMap
java.util.concurrent.ConcurrentSkipListSet


However, there are few points worth knowing:

1. CopyOnWriteXxx collections are suited only for those scenarios where the read operations hugely outnumber the write operations.

2. Concurrent scenarios are better dealt with a strategy at application architecture level rather than brute force use of concurrency-optimized collections.

3. For concurrent scenarios, isolate operations with lifecycle-managed threads each dealing with immutable objects and/or small concurrent datasets rather than giant thread-safe ones. Minimize obtaining of locks rather than making everything thread-safe.

Please let me know what you think.

Friday, October 9, 2009

Detecting NullPointerException with Transparent checks (Java)

NullPointerException is a bane of programming in pointer or reference based programming languages. In this post I am suggesting a way to transparently detect NPEs at a very early stage in a less verbose manner, which should help minimize their occurrence.

Rule #1: Go for immutable references -- use "final" while declaring data members as much as you can.

Rule #2: Use transparent (and less verbose) NPE checks

For example, do NOT do this:


if (x == null) {
throw new IllegalArgumentException("'x' is null");
}
x.doSomething();


Rather define a static method like this:


public static <T>T assertNotNull(final T object, final String errorMsg) {
if (object == null) {
throw new IllegalArgumentException(errorMsg);
}
return object;
}


and use it in a fluent style:


assertNotNull(x, "'x' is null").doSomething();


You can probably put the validating method in a utility class to reuse it everywhere. The good thing about this style is this can be used for cases other than NPEs -- for example you can use it to validate other things as well.

Wednesday, October 7, 2009

Thread-safe Time vs Frequency keeper (Java)

This post is to discuss the approach for counting operation frequency across time units. For example:

Question: How many stock prices were updated in the last 10 seconds (per second count)?

Answer: [6, 3, 0, 5, 2, 1, 4, 0, 9]

After 1 second: [4, 6, 3, 0, 5, 2, 1, 4, 0]
After 2 second: [7, 4, 6, 3, 0, 5, 2, 1, 4]

The answer varies depending on when the question is asked. To answer such questions at any point of time, we need a collector that would record the operation frequency per time unit, and slide the counter windows at the end of each time unit.

One solution is shown below: TimeVersusCountKeeper -- compile and run the class to see it in action.

Update: I have re-posted the code without line numbers. I am using this code in a highly multi-threaded message queuing (multiple queues) scenario, and it works fantastically -- there is one counter per queue and I display the live traffic for about 15-16 queues on a webpage that refreshes every second. But again, this may not be a use-case for every need.

import java.util.Arrays;
import java.util.Formatter;

/**
* Keeps count across time slabs.
*/

public class TimeVersusCountKeeper {

private final long[] UNITS;
private final long UNIT_DURATION_MILLIS;
private final String UNIT_DURATION_NAME;

private volatile long till = System.currentTimeMillis();
private final String TILL_LOCK = new String("LOCK");

private String getDurationName(final long unitDurationMillis) {
final int unitCount = UNITS.length;
final String s;
String unitName;
if (unitCount <= 1) {
s = "";
unitName = "unit of duration " + UNIT_DURATION_MILLIS + "ms";
} else {
s = "s";
unitName = "unit(s) of duration " + UNIT_DURATION_MILLIS + "ms each";
}
if (UNIT_DURATION_MILLIS == 1000L) { unitName = "sec"; }
else if (UNIT_DURATION_MILLIS == 60 * 1000L) { unitName = "min"; }
else if (UNIT_DURATION_MILLIS == 60 * 60 * 1000L) { unitName = "hr"; }
else if (UNIT_DURATION_MILLIS == 24 * 60 * 60 * 1000L) { unitName = "day" + s; }
else if (UNIT_DURATION_MILLIS == 7 * 24 * 60 * 60 * 1000L) { unitName = "week" + s; }
return unitName;
}

private synchronized void update() {
long diff = 0;
synchronized (TILL_LOCK) {
diff = System.currentTimeMillis() - till;
}

if (diff > UNIT_DURATION_MILLIS) {
final long TRUNCATE_UNITS_COUNT = diff / UNIT_DURATION_MILLIS;
synchronized (UNITS) {
if (TRUNCATE_UNITS_COUNT >= UNITS.length) {
Arrays.fill(UNITS, 0L);
} else {
System.arraycopy(UNITS, 0, UNITS, (int) TRUNCATE_UNITS_COUNT,
UNITS.length - (int) TRUNCATE_UNITS_COUNT);
for (int i = 0; i < TRUNCATE_UNITS_COUNT; i++) {
UNITS[i] = 0;
}
}
}
synchronized (TILL_LOCK) {
till += TRUNCATE_UNITS_COUNT * UNIT_DURATION_MILLIS;
//till = System.currentTimeMillis();
}
}
}

public TimeVersusCountKeeper() {
UNITS = new long[10]; // last 10
UNIT_DURATION_MILLIS = 1000L; // seconds
UNIT_DURATION_NAME = getDurationName(UNIT_DURATION_MILLIS);
}

public TimeVersusCountKeeper(final int maxUnitsCount,
final long unitLengthMillis) {
this.UNITS = new long[maxUnitsCount];
this.UNIT_DURATION_MILLIS = unitLengthMillis;
UNIT_DURATION_NAME = getDurationName(UNIT_DURATION_MILLIS);
}

public void incrementBy(final long count) {
update();
synchronized (UNITS) {
UNITS[0] += count;
}
}

public void setCount(final long count) {
update();
synchronized (UNITS) {
UNITS[0] = count;
}
}

public long[] getElements() {
update();
synchronized (UNITS) {
return UNITS.clone();
}
}

@Override
public String toString() {
int unitsCount = 0;
synchronized (UNITS) {
unitsCount = UNITS.length;
}
return new StringBuilder()
.append(unitsCount)
.append(' ')
.append(UNIT_DURATION_NAME)
.append(": ")
.append(getElementsAsString(1) /*Arrays.toString(units)*/)
.toString();
}

public String getElementsAsString(final int minElementWidth) {
final StringBuilder sb = new StringBuilder();
final Formatter numFormatter = new Formatter(sb);
final String format = "%" + minElementWidth + "d";
final long[] array = getElements();
long totalSum = 0;
String delim = "";
sb.append('[');
for (int i = 0; array != null && i < array.length; i++) {
numFormatter.format(delim + format, array[i]);
totalSum += array[i];
delim = ", ";
}
sb.append("](Avg:");
numFormatter.format(format, (long) (totalSum / array.length));
sb.append(')');
return sb.toString();
}

public static void main(String[] args) {
final TimeVersusCountKeeper keeper = new TimeVersusCountKeeper();
for (int i = 0; i < 100; i++) {
try {
Thread.sleep(500);
} catch (InterruptedException e) {}
keeper.incrementBy(i);
for (int j = 0; j < 100; j++) {
keeper.incrementBy(1);
}
System.out.println(keeper.toString());
}
}

}

Thursday, October 1, 2009

Fun with Iterators - UnionIterator

The problem
You want to create an iterator for a union of iterators. For example, you have 5 iterators and you want to create an iterator so that it represents elements in all 5 of them in linear fashion.

Solution
(For brevity and simplicity, the UnionIterator is a readonly iterator.)


1 import java.util.ArrayList;
2 import java.util.Arrays;
3 import java.util.Iterator;
4 import java.util.List;
5 import java.util.NoSuchElementException;
6
7 public class ReadonlyUnionIterator<E> implements Iterator<E> {
8
9 private final Iterator<? extends Iterator<E>> parts;
10
11 private Iterator<E> current = null;
12
13 public ReadonlyUnionIterator(final Iterator<? extends Iterator<E>> parts) {
14 this.parts = parts;
15 alignForwardCurrent();
16 }
17
18 public static <E>ReadonlyUnionIterator<E> fromIterables(
19 final Iterable<? extends Iterable<E>> iterableParts) {
20 final List<Iterator<E>> itlist = new ArrayList<Iterator<E>>();
21 for (final Iterable<E> each: iterableParts) {
22 itlist.add(each.iterator());
23 }
24 return new ReadonlyUnionIterator<E>(itlist.iterator());
25 }
26
27 public static <E>ReadonlyUnionIterator<E> fromIterables(
28 final Iterable<E>... parts) {
29 return fromIterables(Arrays.asList(parts));
30 }
31
32 /**
33 * Aligns 'current' by advancing to a non-empty element.
34 * @return true if current has next element, false otherwise
35 */

36 private synchronized boolean alignForwardCurrent() {
37 while (parts.hasNext()) { // parts has next, but they may be empty!
38 current = parts.next();
39 if (current.hasNext()) { return true; }
40 }
41 current = null;
42 return false;
43 }
44
45 public synchronized boolean hasNext() {
46 // NULL is end-of-union marker for 'current'
47 if (current == null) { return false; }
48 if (current.hasNext()) { return true; }
49 // control reached here means current does not have next
50 return alignForwardCurrent();
51 }
52
53 public synchronized E next() {
54 if (hasNext()) { return current.next(); }
55 throw new NoSuchElementException("No more element available");
56 }
57
58 public void remove() {
59 throw new UnsupportedOperationException(
60 "Readonly iterator -- remove() is not supported");
61 }
62
63 }

Disqus for Char Sequence