Similarities and differences between Java and C

As almost everybody knows Java was intended to be sort of C without pointers and to be used in smart home appliances. And then Gosling and his co-workers were drinking too much coffee and it come out more like C++ without pointers, resource management and multiple inheritance. So, how really different can be coding the same task in C and Java. Practically we are addressing just resource management part, we will not try to go OO in C. We implement fast Fibonacci algorithm in Java.

import java.math.BigInteger; public class Example { /* |1 1| <- we are using this row |1 0| */ static BigInteger[] Q = {BigInteger.ONE, BigInteger.ONE}; static BigInteger[] I = {BigInteger.ONE, BigInteger.ZERO}; /* F(2n+1) = F(n+1)^2+F(n)^2 F(2n) = F(n)*(2*F(n+1)−F(n)) */ static BigInteger[] squareIt(int n) { if (n == 0) return I; if (n == 1) return Q; BigInteger[] t = squareIt(n / 2); BigInteger[] res = {t[0].multiply(t[0]).add(t[1].multiply(t[1])), t[1].multiply(t[0].shiftLeft(1).subtract(t[1]))}; if(n%2==1) return new BigInteger[]{res[0].add(res[1]), res[0]}; return res; } public static void main(String[] env) { for(int i = 0; i<1000; i++) System.out.println("F("+i+") = "+squareIt(i)[1]); } }

It is really very fast, logarithmic fast. Now we try to do the same in C, we will skip BigInteger and use long. The first thing which wont work in C is array allocation, declaring them like that will create local variable. So we create function to allocate our arrays in order to return them to caller:

long * allocate(){ return (long*)malloc(2 * sizeof(long)); }

Those Q and I arrays can be global variables and we are ready to go, almost. We can not declare t as array since initializer can't be function call. Not big deal, we will use pointer to long but that introduces another problem. That pointer may point to global variables Q and I or allocated variables. Again we can check to what it points and if it doesn't point to Q or I we can call free. Already we have feeling that those arrays returned by squaring function are somehow polymorphic and in Java they were not like that. Allocating and freeing arrays on every step of recursion and checking should we free or not doesn't look right. Attempt to literally translate Java code may look something like this:

long * recurse(int i){ if(i==0) return I; if(i==1) return Q; long * t = recurse(i/2); long * r = allocate(); r[0] = t[0]*t[0]+t[1]*t[1]; r[1] = t[1]*((t[0]<<1)-t[1]); checknfree(t); if(i%2){ long * odd = allocate(); odd[0] = r[0]+r[1]; odd[1] = r[0]; free(r); return odd; } return r; }

If Q and I arrays are created using malloc we could do reassignments of initial array and free it at the end of calculation. So no global Q and I but they will be allocated on the heap and serve all recursive calls.

#include <stdio.h> #include <stdlib.h> long * allocate(int i){ long* res = (long*)malloc(2 * sizeof(long)); res[0] = 1; res[1] = i; return res; } long * recurse(int i){ if(i<2) return allocate(i); long * t = recurse(i/2); long t0 = t[0]*t[0]+t[1]*t[1]; t[1] = t[1]*((t[0]<<1)-t[1]); t[0] = t0; if(i%2){ t0 = t[0]+t[1]; t[1] = t[0]; t[0] = t0; } return t; } long square(int n){ long * result = recurse(n); long r = result[1]; free(result); return r; } int main(){ int i; for(i=0; i<93; i++) printf("F(%d) = %ld\n", i, square(i)); return 0; }

Now if we run valgrind on our program it will report:

==18896== HEAP SUMMARY:
==18896==     in use at exit: 0 bytes in 0 blocks
==18896==   total heap usage: 93 allocs, 93 frees, 1,488 bytes allocated
==18896== 
==18896== All heap blocks were freed -- no leaks are possible

Looking now at initial Java solution, it also could benefit from array reuse instead of allocating new ones on every step. Garbage collector is nice thing but not thinking at all about resource management may result in lower quality of code.

Recursive Squaring

This one neatly solves problem of log n multiplications to calculate nth power of of some number. It goes in two stages, calls self recursively with half power until it reaches power 0 or 1 and then squares results. If power was not even correction is required, additional multiplication with base.

static long pow(long base, int n){ if(n==0) return 1; if(n==1) return base; long acc = pow(base, n/2); acc *= acc; if(n%2 == 0) return acc; return base * acc; }

If we want to see how it works and how many times it calls self we can insert debug code:

static long powDbg(long base, int n, int depth){ for(int i = 0; i < depth; i++) System.out.print("-"); System.out.println(n); if(n==0) return 1; if(n==1) return base; long acc = powDbg(base, n/2,depth+1); acc *= acc; for(int i = 0; i < depth; i++) System.out.print("-"); System.out.println(n); if(n%2==0) return acc; return base * acc; }

Should have been included it in previous blog entries about recursion but better late than never.

Recursion and optimizations

As seen in last instalment calculating Fibonacci numbers using naïve implementation creates binary tree of calls and the same subtrees are calculated over and over again what has huge impact on performance. One of ways to improve performance is caching previous results and that is called memoization. In old Java we will do something like this:

private static final Map<Long, Long> memo = new HashMap<>(); static { memo.put(0L, 0L); memo.put(1L, 1L); } public static void main(String[] args) { System.out.println(fibonacci(0)); System.out.println(fibonacci(43)); System.out.println(fibonacci(92)); } static long fibonacci(long n) { if (memo.get(n) == null) { memo.put(n, fibonacci(n - 1) + fibonacci(n - 2)); } return memo.get(n); }

We initialize map container with result for first two cases, to avoid if statements, and later if there is mapping for input, we return it and if there is no mapping for input we calculate it. Without help from memoization naïve implementation will choke and die on input 92. Using Java 8 it becomes even shorter, here is just fibonacci method, everything else is the same:

public static long fibonacci(long n) { return memo.computeIfAbsent(n, m -> fibonacci(m - 1) + fibonacci(m - 2)); }

Signature of computeIfAbsent is the following:

default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

where n is key and function is interface Function, we defined it recursively and compiler was not upset. Memoization brings speed but takes space.
How do we turn tail call version into lambda. We can do this for example:

static Function<Long, Long> y = new Function<Long, Long>() { private long tailRecursive(long a, long b, long n) { if (n > 0) { return tailRecursive(b, a + b, n - 1); } return a; } public Long apply(Long x) { return tailRecursive(0, 1, x); } }; public static long fibonacciFunctional(long n) { return y.apply(n); }

what does not look very functional and very Java 8 because it is anonymous class. Another more Java 8 option is declaring functional interface with sufficient number of arguments:

interface FewArgs<T, U, V, R> { public R apply(T t, U u, V v); } static FewArgs<Long, Long, Long, Long> tailRecursive; static { tailRecursive = (a, b, n) -> { if (n > 0) return tailRecursive.apply(b, a + b, n - 1); return a; }; }

We also can not initialize it in one go, declare class field and initialize it, it must be done from some of host class methods.
Remaining optimization ideas are strictly related to Fibonacci numbers and not applicable to most other recursions. There is not so obvious way to generate Fibonacci numbers:

| 1 1 | n      | F(n+1) F(n)   |
| 1 0 |    =   | F(n)   F(n-1) |

If we rise matrix on the left, lets call it A, to power of n-1 its A[0][0] is Fn. We can prove it using induction. For n=1 our claim obviously holds, now

| F(n+1) F(n)   |   | 1 1 |
| F(n)   F(n-1) | x | 1 0 | =

|F(n+1)+F(n) F(n+1)+0|   |F(n+2) F(n+1)|
|F(n)+F(n−1) F(n)+0  | = |F(n+1) F(n)  |

Instead of doing chain multiplication we can do squaring and reduce number of multiplications to log(n) multiplications.

| F(n+1) F(n)   |2
| F(n)   F(n-1) | =

| F(n+1)^2+F(n)^2         F(n+1)*F(n)+F(n)*F(n−1)|
| F(n)*F(n+1)+F(n−1)*F(n) F(n)^2+F(n−1)^2        |

From where one can pull more interesting relations.
Here is illustrative implementation of this idea:

private static long square(long n) { if(n==0) return n; long test = n-1; ArrayList<long> arr = new ArrayList<>(); long[] A = new long[]{ 1, 1, 1, 0 }; long[] result = new long[4]; System.arraycopy(A, 0, result, 0, 4); while(test>1){ if(test%2!=0) arr.add(1L); else arr.add(0L); test/=2; } for(int i=arr.size()-1;i>-1;i--){ result=multiply(result,result); if(arr.get(i)==1) result=multiply(result,A); } return result[0]; } private static long[] multiply(long[] a, long[] b) { long[] result = new long[]{ a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3], a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3] }; return result; } public static void main(String[] arg) { for (int i = 0; i < 93; i++) { System.out.println("F(" + i + ") = " + square(i)); } }

That ArrayList is mapper, consumes some additional space but makes things easier to debug.

Recursion

Got recently homework to do as part of interview process, already described it here. After providing them with working solution, thoroughly tested, they decided not to speak with me. My conclusion is that was not so bad outcome.
While searching web for clues I discovered this Find all paths from source to destination.
Guy submits his code, peers do review, everything sounds nice.
I will refrain from reviewing particular solution but after looking at it I decided to write about recursion. My impression is that young generations of programmers are putting great effort into mastering frameworks and new features of programming languages but in the same time somehow missing basics. It also coincides with my exploration of new functional features of Java 8.
Recursion is when method, in Java, or function, in C, calls itself during execution. Execution of caller is suspended until callee finishes, then it proceeds. So, there must be some natural way for recursive calls to stop propagating themselves into infinity. If we are not traversing some kind of tree structure, or marking vertices as visited when traversing graph, we typically passing variable to control depth of recursion. Trivial example of recursion is calculation of factorial:

n! = n*(n-1)*(n-2)*...*2*1

It is defined for positive integers. Here is natural and naive implementation together with test:

public static void main(String[] args) { System.out.println("9! = "+factorial(9)); } static long factorial(long n){ if(n<0) return 0; if(n<2) return 1; return n*factorial(n-1); }

I could throw exception on negative n and assert is 9! equal to 362880. What stops recursion here from proceeding forever is that if statement in combination with decreasing n in recursive calls. Now in order to visualize how execution looks like we will add some debugging code.

public static void main(String[] args) { System.out.println("9! = " + factorial(9, 9)); } static long factorial(long n, long m) { for (int i = 0; i < m - n; i++) { System.out.print("-"); } System.out.println(n); if (n < 0) return 0; if (n < 2) return 1; long result = n * factorial(n - 1, m); for (int i = 0; i < m - n; i++) { System.out.print("-"); } System.out.println(n); return result; }

Code now prints current value of n and number of dashes is how deep we are into recursion. We can see how stack of frames is growing in debugger as well but this is nicer. Output of execution is:

9
-8
--7
---6
----5
-----4
------3
-------2
--------1
-------2
------3
-----4
----5
---6
--7
-8
9
9! = 362880

As expected it behaves in linear fashion. It can be much more interesting than linear, for that we will calculate Fibonacci numbers. In the case of Fibonacci numbers we have the following recursive definition:

Fn = Fn-1 + Fn-2

Trivial and naive implementation looks like this:

public static void main(String[] args) { System.out.println("F42 = " + fibonacci(42)); } static long fibonacci(long n) { if (n < 1) return 0; if (n < 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); }

Execution of this code will take  about second or two. Using 42 as function argument illustrates point that naïve implementation is not really most efficient. Mechanics of stopping recursive calls is identical to one in the case of factorial. Let us insert debugging code and see what is going on.

static int indent = 0; public static void main(String[] args) { System.out.println("F5 = " + fibonacci(5, 5)); } static long fibonacci(long n, long m) { for (int i = 0; i < m - n + indent; i++) { System.out.print("-"); } System.out.println(n); if (n < 1) return 0; if (n < 2) return 1; long result = fibonacci(n - 1, m); for (int i = 0; i < m - n + indent; i++) { System.out.print("-"); } System.out.println(n); indent--; result = result + fibonacci(n - 2, m); indent++; for (int i = 0; i < m - n + indent; i++) { System.out.print("-"); } System.out.println(n); return result; }

For reasonably sized argument of 2 we have this output:

2
-1
2
-0
2
F2 = 1

Argument 2 is decreased and recursive call is made with argument 1. When it returns to level 0 with result 1 next recursive call is made with argument 0. The second call also returns with result 0 to level 0 and we have 1+0=1 as result.
We try now 3 as argument:

3
-2
--1
-2
--0
-2
3
-1
3
F3 = 2

We start on level 0 with 3-1 call, then we have pattern from last run elevated for one level up, return to level 0 with result 1 and finally 3-2 recursive call and its return with result 1 to level 0. We can make conclusion that recursive calls are building binary tree. We can try argument 4 to recognize patterns for 3 and 2 and so on.
We could achieve the same on the factorial if we were splitting chain multiplication in half, I was writing about that here.
Recursive call does not have to return anything, work can be performed on one of function arguments. For example we can reverse array by swapping elements.

public static void main(String[] args) { String r = "Hello World!"; char[] arr = r.toCharArray(); reverse(arr, r.length()-1, 0); System.out.println(arr); } public static void reverse(char[] array, int hi, int lo) { if(lo>hi) return; char tmp = array[hi]; array[hi] = array[lo]; array[lo] = tmp; reverse(array, hi - 1, lo + 1); }

Here recursion stops when lo is bigger than hi.

Optimization

We can improve on naïve implementation using tail call elimination. We write method in such way that return statement is pure function call and that allows compiler to perform optimization and practically discard frames without placing them onto the stack. For example factorial can be rewritten like this:

static long tailRecursive(long acc, long n) { if (n == 0) return acc; return tailRecursive(n * acc, n - 1); }

We provide 1 as initial value for accumulator, n is the same as before. For Fibonacci we will need two accumulators:

static long tailRecursive(long a, long b, long n) { if (n > 0) return tailRecursive(b, a + b, n - 1); return a; }

Initial values are a = 0, b = 1 and n as before. From this form is quite easy to switch to iterative form.

static long notRecursive(long n) { if(n == 0) return 0; long a = 0; long b = 1; long c; do { c = b; b = a + b; a = c; --n; } while (n > 0); return a; }

About other forms of optimization like memoization, repeated squaring and lambdas, next time.

Scheduling and Johnson's Algorithm

There is actually paper available on the web where Johnson's scheduling algorithm is nicely described. You can find it here.
So that is not all-pairs shortest paths but scheduling one. For those who are lazy to read it, here is the story. We have programming task paired with testing task. We have one programmer and one tester, tester can test only what is coded, must wait for programmer to finish. In which order jobs should be executed so that whole bunch is finished in shortest time?
Now Johnson's algorithm in plain English:

1. For each task T1, T2, ..., Tn, determine the P1 and P2 times.
2. Establish two queues, Q1 at the beginning of the schedule and Q2 at the end of the schedule.
3. Examine all the P1 and P2 times, and determine the smallest.
4. If the smallest time is P1, then insert the corresponding task at the end of Q1. Otherwise, the smallest time is P2, and the corresponding task is inserted at the beginning of Q2. In case of a tie between a P1 and P2 time, use the P1 time.
5. Delete that task from further consideration.
6. Repeat steps 3 – 5 until all tasks have been assigned.

Very simple. Here is the code:

import java.util.ArrayDeque; import java.util.Deque; public class JavaApplication18 { public static void main(String[] args) { Tasks[] t = new Tasks[6]; for (int i = 0; i < 6; i++) { t[i] = new Tasks(); } t[0].programming = 15; t[0].testing = 4; t[1].programming = 22; t[1].testing = 10; t[2].programming = 3; t[2].testing = 6; t[3].programming = 12; t[3].testing = 8; t[4].programming = 9; t[4].testing = 6; t[5].programming = 12; t[5].testing = 9; executeAll(6, t); } static void executeAll(int n, Tasks[] t) { int[] order = getSchedule(n, t); System.out.println("order of execution is:"); for (int i = 0; i < n; i++) { System.out.println((char)(65+order[i]) + " " + t[order[i]].programming + " -> " + t[order[i]].testing); } System.out.println("Complete duration is " + calculateDuration(n, order, t)); } static int calculateDuration(int n, int[] order, Tasks[] t) { int max = 0, programmingTime = 0; int testingTime = 0, carry; for (int i = 0; i < n; i++) { programmingTime += t[order[i]].programming; carry = 0; if (testingTime > programmingTime) carry = testingTime - programmingTime; testingTime = programmingTime + t[order[i]].testing + carry; if (testingTime > max) max = testingTime; } return testingTime; } static int[] getSchedule(int n, Tasks[] t) { int[] order = new int[n]; int counter = 0, taskIndex = -1, min; Deque<integer> programmingDeque = new ArrayDeque<>(); Deque<integer> testingDeque = new ArrayDeque<>(); for (int j = 0; j < n; j++) { min = 2 ^ 16; kind task = null; for (int i = 0; i < n; i++) { if (!t[i].removed) { if (t[i].programming < min) { min = t[i].programming; task = kind.programming; taskIndex = i; } if (t[i].testing < min) { min = t[i].testing; task = kind.testing; taskIndex = i; } } } if (task == kind.programming) { programmingDeque.addLast(taskIndex); t[taskIndex].removed = true; } if (task == kind.testing) { testingDeque.addFirst(taskIndex); t[taskIndex].removed = true; } } while (programmingDeque.size() > 0) { order[counter++] = programmingDeque.removeFirst(); } while (testingDeque.size() > 0) { order[counter++] = testingDeque.removeFirst(); } return order; } enum kind { programming, testing }; static class Tasks { public int programming; public int testing; public boolean removed; } }

I think that code is self-explanatory and I will not bother you with explanation.
I also had a look at C++ code written by riteshkumargupta here it is slight modification of problem mentioned in paper. If you prefer C++ to Java take a look.

Using POSIX MQ from Java - another part

In introduction we managed to create our message queue and to close it. Only thing which is unclear is where is it? Message queue is maintained by kernel and it is created in virtual file system. If we execute in terminal:

cat /proc/filesystems

we will see entry:

nodev    mqueue

If we want to take a closer look at our JNIMQ_1 we will have to mount mqueue. It is nicely described in man pages, just look for mq_overview entry. For lazy people here are commands for mounting message queue, you must do that as root:

# mkdir /dev/mqueue
# mount -t mqueue none /dev/mqueue

After this we should exit root level. Again using man pages we find out that second line is standard form for mount and looks like this mount -t type device dir. Once mounted we can use our standard set of tools for examining file content on Linux, for example:

ls -l /dev/mqueue
cat /dev/mqueue/JNIMQ_1

Now we can go on sending and receiving messages. If we do not specify time-out, those messages and queues will be persisted until system reboots.
Since we have functional message queue, we can nicely start chat. For that reason we will send some messages. We already have queue from last time and we will not create it:

public class SendMessage{ public native int send(String name, int flags, String text); public static void main(String[] args) { int status = new SendMessage().send("/JNIMQ_1",1,"Hello World!"); if(status!=-1) System.out.println("Message dispatched."); else System.out.println("Sending message failed."); } static { System.loadLibrary("SendMessage"); } }

That flags = 1 is open in write only mode. Boring part with javah we are skipping and here is implementation:

#include "SendMessage.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #include <unistd.h> #include <sys/stat.h> #include <sys/types.h> #include <mqueue.h> JNIEXPORT jint JNICALL Java_SendMessage_send (JNIEnv *env, jobject obj, jstring name, jint flags, jstring text){ mqd_t mq; const char *cstr = (*env)->GetStringUTFChars(env, name, 0); mq = mq_open(cstr, flags); if((mqd_t)-1 == mq){ (*env)->ReleaseStringUTFChars(env, name, cstr); perror("mq_open"); return -1; } const char *ctxt = (*env)->GetStringUTFChars(env, text, 0); int res = mq_send(mq, ctxt, strlen(ctxt)+1, 0); if(res==-1){ perror("mq_send"); return -1; } if((mqd_t)-1 == mq_close(mq)){ perror("mq_close"); return -1; } (*env)->ReleaseStringUTFChars(env, name, cstr); (*env)->ReleaseStringUTFChars(env, text, ctxt); return 0; }

We compile it as described in previous blog entry and send some messages. If we cat /dev/mqueue/JNIMQ_1 we will see that it is growing.
Receiving is equally simple, here is the Java code:

public class GetMessage{ public native String getMessage(String name, int flags, int priority); public static void main(String[] args) { System.out.println(new GetMessage().getMessage("/JNIMQ_1",0,0)); } static { System.loadLibrary("GetMessage"); } }

We want queue opened as read only and we want messages with priority 0. After applying javac and javah we write implementation:

#include "GetMessage.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #include <unistd.h> #include <sys/stat.h> #include <sys/types.h> #include <mqueue.h> JNIEXPORT jstring JNICALL Java_GetMessage_getMessage (JNIEnv *env, jobject obj, jstring name, jint flags, jint priority){ unsigned int up = priority; char ret[1025]; const char *cstr = (*env)->GetStringUTFChars(env, name, 0); mqd_t mq; mq = mq_open(cstr, flags); if((mqd_t)-1 == mq){ (*env)->ReleaseStringUTFChars(env, name, cstr); perror("mq_open"); return (*env)->NewStringUTF(env,"dud"); } ssize_t bytes_read = mq_receive(mq, ret, 1024, &up); if(bytes_read==-1){ perror("mq_receive"); return (*env)->NewStringUTF(env,"dud"); } ret[bytes_read] = '\0'; if((mqd_t)-1 == mq_close(mq)){ perror("mq_close"); return (*env)->NewStringUTF(env,"dud"); } (*env)->ReleaseStringUTFChars(env, name, cstr); return (*env)->NewStringUTF(env,ret); }

This 1024 should be retrieved from mq attributes, but I am lazy to do that and I still remember how it was created.
In this two examples I deviated from passing mq descriptor to Java, that is what jtux does. Not sure what is more expensive, crossing managed-native border or opening file, so do not ask.

Using POSIX MQ from Java - Introduction

All this is taking place on Linux Mint but should work on any other Linux. JDK is Oracle JDK, I am doing Android programming and it requires Oracle JDK, OpenJDK should do fine but path will differ. Goal of this introduction is to create new message queue and to close it - nothing else.
As usually in JNI workflow we write Java code:

public class PosixMQ { public native long mq_open(String name, int flags); public native int mq_close(long desc); public static void main(String[] args) { PosixMQ pmq = new PosixMQ(); long desc = pmq.mq_open("/JNIMQ_1",64); if(desc!=-1L){ System.out.println("We have MQ open."); System.out.println("Close returned " + pmq.mq_close(desc)); }else{ System.out.println("Open failed."); } } static { System.loadLibrary("PosixMQ"); } }

Idea about storing pointer to data structure into long is from jtux project, otherwise it should be message queue descriptor or (mqd_t)-1 in case of failure. Queue name must start with slash and 64 is O_CREAT | O_RDONLY we want queue to be created and to be read only for us. Now we compile PosixMQ.java and we run javah on class to get header for C implementation. On my box it looks like this:

/usr/lib/jvm/java-7-oracle/bin/javah -jni PosixMQ

Interesting part of PosixMQ.h looks like this:

/* * Class: PosixMQ * Method: mq_open * Signature: (Ljava/lang/String;I)J */ JNIEXPORT jlong JNICALL Java_PosixMQ_mq_1open (JNIEnv *, jobject, jstring, jint); /* * Class: PosixMQ * Method: mq_close * Signature: (J)I */ JNIEXPORT jint JNICALL Java_PosixMQ_mq_1close (JNIEnv *, jobject, jlong);

Finally we write trivial C implementation, being careful to include all required imports:

#include "PosixMQ.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #include <unistd.h> #include <sys/stat.h> #include <sys/types.h> #include <mqueue.h> JNIEXPORT jlong JNICALL Java_PosixMQ_mq_1open (JNIEnv *env, jobject obj, jstring name, jint flags){ struct mq_attr attr; attr.mq_flags = 0; attr.mq_maxmsg = 10; attr.mq_msgsize = 1024; attr.mq_curmsgs = 0; const char *str = (*env)->GetStringUTFChars(env, name, 0); mqd_t desc; desc = mq_open(str, flags, 0644, &attr); (*env)->ReleaseStringUTFChars(env, name, str); return (intptr_t)desc; } JNIEXPORT jint JNICALL Java_PosixMQ_mq_1close (JNIEnv *env, jobject obj, jlong desc){ return mq_close((mqd_t)(intptr_t)desc); }

I was too lazy to pass attributes around, it should be done at later stage. Permissions are also conveniently hardcoded, though passing octal through parameter list is not difficult. To compile this I used:

gcc -I/usr/lib/jvm/java-7-oracle/include -I/usr/lib/jvm/java-7-oracle/include/linux -o libPosixMQ.so -shared -fPIC PosixMQ.c -lrt

Switch -fPIC will not be required on 32 bit Linux and -lrt instruction to link against the real-time is required everywhere. To run it we do:

java -Djava.library.path=. PosixMQ

in directory where are binaries and we see:

We have MQ open.
Close returned 0

Not very impressive but again very simple. Maybe next time we send and receive some messages, who knows.

Java writes to named pipe

I did while ago article where Java talks to C++ using standard input/output, now this is just addition to it. As in last example all that happens on Linux and we are using named pipe or FIFO. Need to transfer result of some periodic operation to remote listener and do not want to block process with network transfer. It slows it down and also introduces new opportunities for failure. In original problem that process is written in some funny functional language where many things may go wrong. Naturally I will not bother you with networking or what is being processed. It will be just small IPC example.
So here is C++ listener:

#include <iostream> #include <sys/stat.h> #include <stdio.h> #include <fcntl.h> using namespace std; int main() { char fifo_name[] = "MYFIFO"; char buf[100]; int fifo_handle; int size; mknod(fifo_name, S_IFIFO | 0666, 0); cout << "client is ready" << endl; if ((fifo_handle = open(fifo_name, O_RDONLY)) < 0) { perror("open failed"); return -1; } do{ size = read(fifo_handle, buf, 100); if(size<0) perror("read failed"); else if(size==0) cout<<"server left us"; else{ buf[size] = '\0'; cout<<"message is "<<buf<<endl; } }while(size>0); close(fifo_handle); return 0; }

We run it the first, to create MYFIFO. BTW on Ubuntu 12.10 it will fail to compile, to remedy that add unistd.h to includes. Then comes Java class which is talking to C++ listener:

import java.io.*; public class Orator { public static void main(String[] args) throws IOException { //Runtime.getRuntime().exec("mkfifo MYFIFO"); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedOutputStream out = new BufferedOutputStream(new FileOutputStream("MYFIFO")); String s; while ((s = in.readLine()) != null && s.length() != 0){ byte[] arr = s.getBytes(); out.write(arr,0,arr.length); out.flush(); } } }

We run listener in terminal, then Orator class in different terminal and type short messages. When we hit enter message goes through pipe and appears in terminal. If you didn’t know how to turn string into byte array and write it to buffer now you know. Only tricky point is that you need to flush output stream to go through pipe, it’s all about plumbing.

Homework: Towers of Hanoi

This puzzle was popularised in Europe by French mathematician Edouard Lucas. There are three poles, 64 disks of different sizes and number of monks trying to move those disks from first to third pole, respecting the following rules:
1) You can move only one disk at the time.
2) You can pick only top disk and place it on top of other disks on different pole.
3) You can place disk only on bigger disk.
When monks finish moving those 64 disks and puzzle is solved, end of the world will come. According to Lucas all that takes place in Vietnam. Now, this puzzle is known in India as Towers of Brahma and there could be other versions of it, for example Chinese, over last seven thousands years they invented many puzzles. One may be under impression that end of the world is near but to solve 64 disk puzzle, 2^64-1 moves are required and that is quite big number 18446744073709551615. Though end of the world may come before puzzle is solved for many other reasons.
Puzzle is quite interesting because it allows to develop simple algorithm. Now we will name poles start, aux and end. With single disk, we take it from start and place on end. With two disks, we take small to aux, big to end and finally smal from aux to end. Now with three disks we already see that we should move top two to aux, big disk to end and after that top two to end. So, moving top two to aux is like previous case, but aux and end are swapping places. Moving top two from aux to end is again the same as previous case, but start and aux are swapping places. We can even write moves, so it is easy to see what is going on:

One disk: start to end
Two disks: start to aux, start to end, aux to end
Three disks: (start to end, start to aux, end to aux), start to end, (aux to start, aux to end, start to end)

We can generalize and say that solution is moving n-1 disks to aux, moving bottom disk to end and moving n-1 disks from aux to end. So we got self algorithm for solving puzzle. Turning it into code is more than simple:

def towers(n, start, aux, end): if n>1 : towers(n-1, start, end, aux) print 'moving disk {} from {} to {}'.format( n, start, end ) towers(n-1, aux, start, end) elif n==1 : print 'moving disk {} from {} to {}'.format( n, start, end )

That was Python implementation. If you do not know Python, here is Java implementation:

public class Towers { public static void main(String[] args) { towers(5,1,2,3); } static void towers(int n, int start, int aux, int end){ if(n>1){ towers(n-1, start, end, aux); System.out.println("moving disk "+n+" from "+start+" to "+end); towers(n-1, aux, start, end); }else System.out.println("moving disk "+n+" from "+start+" to "+end); } }

Very simple. There are many other ways to solve this puzzle but recursion is simplest and most logical. Also excellent interview question, if candidate is not capable of developing simple algorithm and understanding recursion, then candidate is not really programmer.

How Java and C or C++ can talk on Linux

Linux is all about interoperability. That is more of IPC stuff. Without any type safety we can open pipe and pass arbitrary chunk of data between native process and Java process. No need for JNI, let the data flow. Secret of our success is function popen(), for more info invoke man popen from terminal. All actions are initiated from native code, so here is declaratively C++ native code to start Java listener and send chunk of data to it:

#include <cstdio> int main() { FILE* fp = popen("java SomeOtherClass", "w"); if (fp == NULL) return -1; char buf[] = "Hello World from C++"; fwrite(buf, 1, 21, fp); if (fp != NULL) pclose(fp); return 0; }

Without that C++ include statement it would look like plain C. It will create process java SomeOtherClass and open pipe to it for writing. Naturally before we run native part of system we should compile Java code. Here is Java listener:

import java.io.BufferedInputStream;

class SomeOtherClass {
    public static void main(String args[]) throws Exception {
        BufferedInputStream bis = new BufferedInputStream(System.in, 132);
        StringBuffer sb = new StringBuffer();
        int i;
        while ((i = bis.read()) != -1) {
            sb.append((char) i);
        }
        System.out.println("SomeOtherClass got message : " + sb.toString());
    }
}

When we run native binary it will start Java class and send to it message. In its turn Java class will use BufferedInputStream to read standard input and turn stream of integers into String. If we want we can make C++ listening and Java talking. Here is the now really C++ code:

#include <iostream> #include <sstream> #include <cstdio> using namespace std; int main() { ostringstream out; int size; FILE* fp = popen("java SomeClass", "r"); if (fp == NULL) return -1; do { char buf[132]; size = fread(buf, 1, 132, fp); out.write(buf, size); } while (size > 0); if (fp != NULL) pclose(fp); cout << "java SomeClass says" << endl << out.str() << endl; return 0; }

As last time Java code must be compiled prior to executing native one. Here is Java code:

public class SomeClass {
    public static void main(String[] args) {
        String msg = "Greetings from Java no: ";
        for (int i = 0; i < 10; i++) {
            System.out.println(msg + i);
        }
    }
}

We have less code but more output, obvious rise in productivity due to OO approach.
Not very useful, but things could be done this way.

Nostalgic moments

While trying to do:

ifstream ins(fileno(popen("ls -l","r"))); string s; while (!ins.eof()){ getline(ins,s); output<<s<<endl; }

I was greeted with error message:

invalid conversion from ‘int’ to ‘const char*’

C FILE* was expelled from ISO/ANSI C++ streams. Luckily there is workaround, one can subclass std::streambuf as described here. Sometimes one can find useful things on StackOverflow ;-)

More C++ and JNI on Linux Mint

In last JNI tutorial we learned how to compile Java code, generate header and implement and compile native code. JNI declares two main groups of commonly used types. Primitive types, which are int, boolean, float and so on, and they are user friendly, no need to do cast to native types. Other group are reference types, like String, arrays or proper Java classes, and they all inherit from jobject and require special handling to map them to native types. So here is the simple example to illustrate different parameter type handling:

public class MultiCall{
    public native int add(int a, int b);
    public native boolean isOdd(long a);
    public native int sum(int[] arr);
    public native String add(String a, String b);
    static
    {
        System.loadLibrary("MultiCall");
    }
    public static void main(String[] args)
    {
        MultiCall m = new MultiCall();
        System.out.println(m.add(1, 2));
        System.out.println(m.add("Hello", "World"));
        System.out.println(m.sum(new int[]{1,2,3,4}));
        System.out.println(m.isOdd(6L));
    }
}

After we compile it and run javah tool on resulting class, we have the following method definitions:

/* DO NOT EDIT THIS FILE - it is machine generated */ #include <jni.h> /* Header for class MultiCall */ #ifndef _Included_MultiCall #define _Included_MultiCall #ifdef __cplusplus extern "C" { #endif /* * Class: MultiCall * Method: add * Signature: (II)I */ JNIEXPORT jint JNICALL Java_MultiCall_add__II (JNIEnv *, jobject, jint, jint); /* * Class: MultiCall * Method: isOdd * Signature: (J)Z */ JNIEXPORT jboolean JNICALL Java_MultiCall_isOdd (JNIEnv *, jobject, jlong); /* * Class: MultiCall * Method: sum * Signature: ([I)I */ JNIEXPORT jint JNICALL Java_MultiCall_sum (JNIEnv *, jobject, jintArray); /* * Class: MultiCall * Method: add * Signature: (Ljava/lang/String;Ljava/lang/String;)Ljava/lang/String; */ JNIEXPORT jstring JNICALL Java_MultiCall_add__Ljava_lang_String_2Ljava_lang_String_2 (JNIEnv *, jobject, jstring, jstring); #ifdef __cplusplus } #endif #endif

Implementation looks like this:

#include "MultiCall.h" #include <string> using namespace std; JNIEXPORT jint JNICALL Java_MultiCall_add__II(JNIEnv *env, jobject obj, jint a, jint b){ return a+b; } JNIEXPORT jboolean JNICALL Java_MultiCall_isOdd(JNIEnv *env, jobject obj, jlong l){ jboolean res = JNI_TRUE; if(l%2 == 0) res = JNI_FALSE; return res; } JNIEXPORT jint JNICALL Java_MultiCall_sum(JNIEnv *env, jobject obj, jintArray arr){ int res = 0; jsize length = env->GetArrayLength(arr); jint *array = env->GetIntArrayElements(arr, 0); for (int i=0; i<length; i++) res+=array[i]; env->ReleaseIntArrayElements(arr, array, 0); return res; } JNIEXPORT jstring JNICALL Java_MultiCall_add__Ljava_lang_String_2Ljava_lang_String_2(JNIEnv *env, jobject obj, jstring a, jstring b){ const char* ca = env->GetStringUTFChars(a, 0); string na(ca); env->ReleaseStringUTFChars(a, ca); na+=" "; const char* cb = env->GetStringUTFChars(b, 0); string nb(cb); env->ReleaseStringUTFChars(b, cb); string res = na+nb; return env->NewStringUTF(res.c_str()); }

Reference types require significant work to use them from native code. Also if we want to return reference type it needs to be constructed. I am using std::string because it will do deep copy of character array, at least if you are using gcc/g++, and allows me to easily manipulate strings. Code is easy to understand and doesn’t deserve further comments.
The second example is illustration how to throw exception from native code and catch it in Java code.

public class NativeException{
    public native int divide(int a, int b) throws IllegalArgumentException;
    static
    {
        System.loadLibrary("NativeException");
    }
    public static void main(String[] args)
    {
        NativeException n = new NativeException();
        try{
            System.out.println(n.divide(12, 3));
            n.divide(12, 0);
        }catch(Exception e){
            System.out.println(e.getMessage());
        }
    }
}

Even if we marked native method with throws, javac will not complain if we try to call it out of try-catch block. One of reasons why pure Java is preferred to JNI. Also in header file, that throws is just ignored.

/* DO NOT EDIT THIS FILE - it is machine generated */ #include <jni.h> /* Header for class NativeException */ #ifndef _Included_NativeException #define _Included_NativeException #ifdef __cplusplus extern "C" { #endif /* * Class: NativeException * Method: divide * Signature: (II)I */ JNIEXPORT jint JNICALL Java_NativeException_divide (JNIEnv *, jobject, jint, jint); #ifdef __cplusplus } #endif #endif

In implementation we do sanity check and if second parameter is zero we try to throw IllegalArgumentException.

#include "NativeException.h" #include <string> using namespace std; JNIEXPORT jint JNICALL Java_NativeException_divide(JNIEnv *env, jobject obj, jint a, jint b){ int res = 0; if(b==0){ jclass exception = env->FindClass("java/lang/IllegalArgumentException"); if (exception == NULL) { return res; } env->ThrowNew(exception, "division with zero attempted"); return res; } res = a/b; return res; }

If env fails to find IllegalArgumentException, we just return zero.

JNI Hello World on Linux Mint

I wrote similar tutorial for www.linux.com about four years ago. The motivation is the same as then, in then Sun and today Oracle documentation only Solaris and Windows are treated, Linux is omitted. Also there are slight differences in compilation process on 32 bit Ubuntu 9.04 then and 64 bit Linux Mint 13 today. Otherwise there is increase in popularity of JNI thanks to Android NDK. To do native Android development one should be familiar with C, C++, JNI and Java. As in that old article I will use C++ to create shared library.
We start with Java class:

class YAHelloWorld
{
    public native void sayHi(String name);
    static
    {
        System.loadLibrary("YAHelloWorld");
    }
    public static void main(String[] args)
    {
        YAHelloWorld h = new YAHelloWorld();
        h.sayHi("World");
    }
}

Beside normal Java stuff we have request to load native library and forward declaration of native method. We save it as YAHelloWorld.java and compile it

javac YAHelloWorld.java

After that we invoke javah to create native header:

/usr/lib/jvm/java-7-oracle/bin/javah -jni YAHelloWorld

I was lazy to export path, so that is a reason for full path to javah. If you try without full path you may get following suggestion:

The program 'javah' can be found in the following packages: * gcj-4.6-jdk * openjdk-6-jdk * gcj-4.5-jdk * openjdk-7-jdk Try: sudo apt-get install <selected package>

what is not really necessary.  Content of generated YAHelloWorld.h is:

/* DO NOT EDIT THIS FILE - it is machine generated */ #include <jni.h> /* Header for class YAHelloWorld */ #ifndef _Included_YAHelloWorld #define _Included_YAHelloWorld #ifdef __cplusplus extern "C" { #endif /* * Class: YAHelloWorld * Method: sayHi * Signature: (Ljava/lang/String;)V */ JNIEXPORT void JNICALL Java_YAHelloWorld_sayHi (JNIEnv *, jobject, jstring); #ifdef __cplusplus } #endif #endif

The first parameter, JNIEnv * is pointer to array of pointers of JNI functions, jobject is sort of this pointer and jstring is Java String. Now when we know all that we can write C++ implementation:

#include <iostream> #include "YAHelloWorld.h" using namespace std; JNIEXPORT void JNICALL Java_YAHelloWorld_sayHi (JNIEnv *env, jobject o, jstring s) { const char *str = env->GetStringUTFChars(s, 0); cout << "Hello " << str << "!" << endl; env->ReleaseStringUTFChars(s, str); }

Beside normal C++ stuff we convert Java String to C++ string at the beginning and at the end we release both of them. Compilation looks like this:

g++ -shared -fPIC -I/usr/lib/jvm/java-7-oracle/include -I/usr/lib/jvm/java-7-oracle/include/linux YAHelloWorld.cpp -o libYAHelloWorld.so

and finally we execute our Hello World example like this:

java -Djava.library.path=. YAHelloWorld

That should produce familiar Hello World output. Not too difficult.

Image upload via RESTful web service

During some project I had to write Android client for RESTful web service where between other things, image upload was goal. Server was handled by Zaries http://zaries.wordpress.com/ so it was Lisp on Hunchentoot. I didn’t want to start with two unknowns, implementing problematic multipart/form-data on Android and writing from the scratch Lisp web service, so I started searching for simple Java example of upload RESTful web service. I expected something on NetBeans but closest what I managed to find was Jersey hello world example http://www.mkyong.com/webservices/jax-rs/jersey-hello-world-example/ done using Maven. So, here I am writing user friendly tutorial for user friendly NetBeans for millions of prospective Android developers which are not quite comfortable with Java EE development, yet. Android client will be separate article.
This was done on LinuxMint Maya, IDE is NetBeans 7.2 and deployment target is Tomcat 7.0.27.
We start from New Project dialog where from group Java Web we select Web Application. With exception of Server and Settings where we want to target Apache Tomcat during all other steps we accept defaults. If we downloaded bundle, Glassfish is default target.

Now we want to add RESTful web service. We right click on project icon in left pane and select New -> RESTful Web Services from Patterns ...
Again we accept default values with exception of package name where we type in za.org.droid. Before we start coding we add two libraries, those are Jersey 1.8 and JAX-WS 2.2.6. Inside Projects pane we right click on Libraries folder and select Add Library ...

Now we can delete useless GET and PUT Hello World methods generated by IDE and copy and paste this

@POST
@Path("/images")
@Consumes(MediaType.MULTIPART_FORM_DATA)
public Response imageUpload(@FormDataParam("image") InputStream hereIsImage, @FormDataParam("image") FormDataContentDisposition hereIsName) {
    String path = System.getenv("HOME")+"/tmp/";
    if(hereIsName.getSize()==0) {
        return Response.status(500).entity("image parameter is missing").build();
    }
    String name = hereIsName.getFileName();
    path += name;

    try {
        OutputStream out = new FileOutputStream(new File(path));
        int read;
        byte[] bytes = new byte[1024];
        while ((read = hereIsImage.read(bytes)) != -1) {
            out.write(bytes, 0, read);
        }
        out.flush();
        out.close();
    } catch (IOException e) {
        return Response.status(500).entity(name + " was not uploaded\n"+e.getMessage()).build();
    }
    return Response.status(200).entity(name + " was uploaded").build();
}

We should create in our $HOME folder tmp folder where images will be saved. We look for image parameter and it will tell us what is image called and also it will contain raw image data. We return response informing client about how successful was upload attempt.
Since we accepted default names for RESTful web service it will have “generic” path assigned, that is important because we use that path to call it.
Only what is left is to do configuration. In WEB-INF folder we create web.xml file and paste the following in:

<?xml version="1.0" encoding="UTF-8"?> <web-app xmlns="http://java.sun.com/xml/ns/javaee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://java.sun.com/xml/ns/javaee http://java.sun.com/xml/ns/javaee/web-app_3_0.xsd" version="3.0"> <display-name>Upload image REST ws</display-name> <servlet> <servlet-name>jersey-serlvet</servlet-name> <servlet-class>com.sun.jersey.spi.container.servlet.ServletContainer</servlet-class> <init-param> <param-name>com.sun.jersey.config.property.packages</param-name> <param-value>za.org.droid</param-value> </init-param> <load-on-startup>1</load-on-startup> </servlet> <servlet-mapping> <servlet-name>jersey-serlvet</servlet-name> <url-pattern>/xyz/*</url-pattern> </servlet-mapping> <session-config> <session-timeout> 30 </session-timeout> </session-config> </web-app>

We can save xml and deploy web application. End-point to call will be http://localhost:8080/WebApplication3/xyz/generic/images, application name WebApplication3 may be different so please change it accordingly. To test upload one can use HttpClient, httpcomponents-client-4.2.1 contains working example. I will add blog about Android client in day or two.

Install Oracle JDK in LinuxMint Maya or Ubuntu 12.04 LTS

This primarily describes setup required for Android development on 64 bit LinuxMint Maya what is very much the same as Ubuntu 12.04 but with usable window manager. For those two popular distros we have OpenJDK in repository and we can easily install it using apt-get from terminal or GUI Software Manager. But for Android development only Oracle JDK is supported and Android SDK is 32 bit what implies:

sudo apt-get install ia32-libs

Otherwise we will get confusing error message that for example adb was not found and we attempted to run it.
Current version of Oracle JDK can be downloaded from here http://www.oracle.com/technetwork/java/javase/downloads/index.html
For example we select jdk-7u7-linux-x64.tar.gz accept license and download it using Firefox. When download finishes we typically check signature of it and that is done from terminal, so cd to Downloads and run:

$ md5sum jdk-7u7-linux-x64.tar.gz
15f4b80901111f002894c33a3d78124c  jdk-7u7-linux-x64.tar.gz

Here I do Google search on md5 to be sure that I downloaded right archive. Then we unpack archive simply right clicking on it and selecting Extract Here. That creates directoru jdk1.7.0_07 in Downloads. JDK should be in /usr/lib/jvm unless we want to specify execution path every time, for example this is how it looks on my box:

/usr/lib/jvm $ ls -l
total 20
lrwxrwxrwx 1 root root   24 Oct 31 15:39 default-java -> java-1.6.0-openjdk-amd64
lrwxrwxrwx 1 root root   24 Oct 31 15:39 java-1.6.0-openjdk -> java-1.6.0-openjdk-amd64
lrwxrwxrwx 1 root root   20 Oct 31 15:39 java-1.6.0-openjdk-amd64 -> java-6-openjdk-amd64
lrwxrwxrwx 1 root root   24 Oct 31 15:39 java-6-openjdk -> java-1.6.0-openjdk-amd64
drwxr-xr-x 7 root root 4096 Nov  4 00:00 java-6-openjdk-amd64
drwxr-xr-x 3 root root 4096 May  3  2012 java-6-openjdk-common
lrwxrwxrwx 1 root root   24 Nov  1 11:26 java-6-oracle -> /usr/lib/jvm/jdk1.6.0_37
drwxr-xr-x 5 root root 4096 May  3  2012 java-7-openjdk-amd64
lrwxrwxrwx 1 root root   24 Oct 31 16:52 java-7-oracle -> /usr/lib/jvm/jdk1.7.0_07
drwxr-xr-x 8 root root 4096 Nov  1 11:22 jdk1.6.0_37
drwxr-xr-x 8 root root 4096 Aug 29 03:12 jdk1.7.0_07

In order to move jdk1.7.0_07 from downloads we can use

sudo mv jdk1.7.0_07 /usr/lib/jvm/

we are doing that from terminal in Downloads, or maybe start caja or gnome as root and do it from GUI. If we are in GUI we recursively change ownership to root using properties and if we are doing it from terminal:

sudo chown -R root:root /usr/lib/jvm/jdk1.7.0_07

Now we need symlink which we use later to switch between different versions of Java:

sudo ln -s /usr/lib/jvm/jdk1.7.0_07 /usr/lib/jvm/java-7-oracle

now we can install runtime and compiler:

sudo update-alternatives --install /usr/bin/java java /usr/lib/jvm/java-7-oracle/jre/bin/java 2
sudo update-alternatives --install /usr/bin/javac javac /usr/lib/jvm/java-7-oracle/bin/javac 1

That allows us to configure runtime and compiler respectively using the following two:

sudo update-alternatives --config java
sudo update-alternatives --config javac

we need simply to type number of desired version and hit enter. To check what we are actually running we can execute:

javac -version
java -version