Friday, August 20, 2010

Thread-safe Generic Class in Java

Assuming that you are a Java Developer, I can say that you have at some point or the other must have used Generics in your code, be it using a Generic Collection (if you have worked with Java5+) or in any other way. Even if you are not a Java developer, you must have played with Templates (in C++) in your school/college days.

Today, we are going to do something similar in Java. We are going to create a Generic Stack class in Java, which you can use to create a Stack of Integers, Floating Point Numbers, or a Stack of Students or any custom type that you have. Just to make code a bit more interesting and tough, I have also made it thread-safe so that multiple threads can use this stack without leaving it in an inconsistent state.

public class GenericStack<T> {

private List<T> items;
private int top;
private int size;
private static final int INIT_SIZE = 100;

public GenericStack(){
size = INIT_SIZE;
items = new ArrayList<T>(INIT_SIZE);
top = -1;
}

public GenericStack(int size){
this.size = size;
items = new ArrayList<T>(size);
top = -1;
}

private boolean isEmpty(){
return (top==-1);
}

private boolean isFull(){
return (top == size-1);
}

// Push an Item in Stack
public void push(T item){
synchronized(items){
// While stack is Full
while(isFull()){
try{
// Wait till Stack is Full
items.wait();
}
catch(InterruptedException e){
e.printStackTrace();
}
}
// Produce Item
items.add(++top, item);
// Notify other threads
items.notify();
}
}

// Pop an item out of stack
public T pop(){
T item = null;
synchronized(items){
// While Stack is Empty
while(isEmpty()){
try{
// Wait if its empty
items.wait();
}
catch(InterruptedException e){
e.printStackTrace();
}
}
// Consume an item
item = items.get(top--);
// Notify other threads
items.notify();
}
return item;
}
}

Most of the above code is self-explanatory but lets highlight some of the major concepts used here:
  • To create a Generic class, one must specify the Type along with the class name (as done using T).
  • When you initialize it, all the occurrences of T will be replaced by that particular type.
  • We have also made the above Stack class thread-safe, i.e. it can be shared and updated by multiple threads in a consistent manner using synchronized blocks.
  • We have checked before pushing for a Full Stack and we also check for an Empty Stack before popping an element
  • We have not made the isFull() and isEmpty() methods as synchronized as they are private (hence not visible to clients) and are always called from an synchronized context from within the class.
  • If you need isFull() and isEmpty() to be public then make them also synchronized to make them thread-safe
  • It is always better to have synchronized blocks rather than synchronized methods as it is always better to synchronize as less code as possible. Although, here we could not make much use of this concept but rather than obtaining the lock on the calling object, we obtain a lock on the shared list of items.
  • Calling synchronized(items) means if some other thread has not yet acquired a lock on items (By the way, each Object in Java has an associated Lock with it), then this current thread acquires the associated lock and proceeds. Otherwise if some other thread has currently acquired the synchronized block, then it must wait in the wait list of the object (items) in question. The thread then waits until it receives a notification that the lock has become available for acquisition and then it competes with other waiting threads to acquire the lock.
  • Calling items.wait() results in the current thread being placed in the wait list of items after releasing the lock. You can only call object.wait() after you have acquired the lock on the object.
  • Calling items.notify() results in sending the notification to one of the threads in the wait pool of threads which can then compete for the lock.
  • Note that items.notify() does NOT releases the lock. Only exiting the synchronized block/method releases the lock that was acquired when the thread entered the synchronized block/method.

You can easily create two or more threads (viz. Producer and Consumer) and pass them the same Stack and play with them to randomly create and consume data and check that you Stack class is indeed thread-safe.

Generic Methods

Talking more about generics, you can also make a method accept Generic parameters without the enclosing class declaring the Generic type as done in the following example:

public <T> List<T> createArrayList(T t){
List<T> arr = new ArrayList<T>();
return arr;
}

This weird looking syntax has a meaning:

  • This method basically lets you create an arraylist of any type, type is passed to it as an argument.
  • Since you are not defining the type at Class-level, then there must be a place where you should define the type of your method and distinguish it from other non-generic methods for the compiler.
  • So, we declare the type <T> immediately after public modifier to say that we use a Generic Type T in this method, which like others will be replaced at runtime with any real type. (just like in case of Generic classes)
  • We call this method passing to it a valid reference to any Object of any type (Integer, Float, or you own custom class Student). For example, we can do:
Integer i = 23;
List<Integer> intList = createList(i);

or

Student st = new Student();
// Do anything with st here
List<Student> students = createList(st);

Ok, I agree this is not one of really useful examples for showcasing the power of a generic method but I hope that the intent is clear and so is the syntax. As always, your valuable comments are welcome and desired. Any corrections must also found place in comments. Sayonara :-)

Sunday, August 15, 2010

Mixing Generic & Non-generic code in Java

Can you spot the error in the following code:

public class MixingGenerics{

public static void main(String[] args){
List<Integer> arr = new ArrayList<Integer>();
arr.add("String 1");
arr.add("String 2");

// add something more
addToList(arr);
}

public static void addToList(List arr){
arr.add(new Integer(1));
}
}

I’m sure you are able to point out the mistake that we are adding an Integer to an ArrayList of Strings. That’s definitely not done. But can you tell without compiling this code that we get an error at compile-time or at run-time ?

Unfortunately and even more surprisingly, this code doesn’t give any compilation error or runtime exception. Everything works fine and an Integer is added into your ArrayList (of Strings) !! Yes, you do get a compiler warning that says something about Type Safety of your code. We will get back to this point later on.

But first examine how is possible that you can actually store an Integer in a String Arraylist? Actually, it is an unfortunate outcome of mixing Generic & Non-generic code. The reason why we get no error is due to a property of Generics called Type-Erasure. We’ll get to it soon but first lets see when the previous code will throw an Error/Exception. This code will explode as soon as you would try and iterate the ArrayList of Strings, in which you have put an Integer unknowingly as shown below:

public class MixingGenerics{

public static void main(String[] args){
List<Integer> arr = new ArrayList<Integer>();
arr.add("String 1");
arr.add("String 2");

// add something more
addToList(arr);

// print the list
printMyList(arr);
}

public static void addToList(List arr){
arr.add(new Integer(1));
}

public static void printMyList(List<String> arr){
for(String s:arr){
System.out.println("String : "+s);
}
}
}

So we get a runtime exception now on iterating the list. It prints the first two strings and then throws ClassCastException as we are trying to cast an Integer into a String s. That’s okay but why does it allows you to add an Integer into List of Strings.

Type-Erasure

Generic code in Java exhibit a very important property: Type-erasure. What it means is that the so-called type-safe collection of yours (the generic collection here: ArrayList<String>) loses its type information at run-time and acts as if its just a List (like pre-Java 5 lists, the non-generic list). This has been made such so that we can integrate pre-Java 5 (the non-generic code) with newly written Generic code (Java 5 or later), but then while mixing them, you must be careful. Very careful indeed, else you could happen to write a code that will explode unpredictably.

So the answer to our question that why it allows an Integer to a list of Strings is because at runtime we only have a list, just like we had a list in pre-Java 5 days. Without generics, we had to take care while taking object out of the list and casting them but with Java 5 and above code, that casting is implicitly inserted by the compiler. So when we say

String s = arr.get(0) gets converted into String s = (String) arr.get(0)

Doing exactly the same with our list, it gives an error when we try and cast an Integer into a String and hence the error: java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String

Apart from giving the error, the compiler does his best and warns you when you are trying to mix Generic code with Non-Generic Code. If you are very sure about your code and do not want any compiler warning, then you can do by using following Annotation (valid with Java5+ code)

@SuppressWarnings("unchecked")
public static void addToList(List arr){
arr.add(new Integer(1));
}

This lets the compiler know that you are pretty sure about the code that you have written and do not give me any warnings with this method. Generally, it is not recommended to use such Annotations and if you really need to use one, you must do proper documentation of your code.

Any comments and corrections are welcome :-)