Java Data Structures - Contents
A D V E R T I S E M E N T
In Java, as with everything else in this world,
there are additional bells and whistles. They do not restrict us, and offer new ways of
doing things. For the purpose of this tutorial, I've named these bells and whistles the Kitchen
Sink Methods (since they're not directly part of Data Structures, and their inclusion
metaphorically adds a kitchen sink to something which has everything but the
kitchen sink) OK! I admit it, I'm not a creative person when it comes to picking names.
Programs in this section might not be portable nor
implemented in the most efficient way. They serve as guides in introducing some of these
bells and whistles, which might or might not be useful.
We have all heard about the Java Native
Interface (JNI), and about a ton of reasons to not use it. The simple truth, however,
is that at times, Java is not as fast as we would like it to be. It does not offer system
specific features which make other programming languages so powerful.
One might argue that we do not need any system
specific features, and could happily exist in the sandbox that the JavaVM provides. In
some real world applications, however, performance is a requirement. Imagine writing a
full blown game in Java. Without Java3D, you would have quite a headache trying to use
your 3D acceleration hardware. Or imagine writing a disk defragmenter in Java, how would
you go about doing that?
The answer lies in Java Native Interface
(JNI). It allows Java application to access methods written in other programming languages
(most commonly in C/C++). The process goes like this: we write Java code which defines
these native methods, use javac to compile the java code, then
run javah on the resulting class file. That generates the .h
include file (for C/C++). We use the method definition from the .h file to
implement our native version of the method. When done, we compile the C/C++
module into a shared library (DLL under Win32, shared lib under UNIX). We then load
the library from within our Java application, and call the native method just
as if it were a regular Java method. Sounds interesting, doesn't it?
It gets better. Since all we are using is a shared
library, we could theoretically use ANY programming language to write our native code. We
could even use Assembler, COBOL, or any other arcane language. We will not do it in this
tutorial though, and will go with the plain old C.
Here is where the system specific part of this
section creeps in. Under Microsoft Windows, we will use Microsoft Visual C++ v6 Enterprise
Edition to compile our C code (any other compiler capable of generating DLL files should
do). Under UNIX (or more specifically: SunOS v5.7 running on Spark 5), we will use
standard gcc. The generated DLL file, and a Solaris shared lib will be included with the
sources archive for this document)
To get started, lets prepare a few things. Under
Windows, go to your JDK (or Java SDK as they like to call it now a days) directory and
copy all the files from the include directory into your VC++ include directory. Do not
forget the file(s) in the <JDK dir>/include/win32 directory; copy all of them to
your VC++ include directory. Do the same for all the lib file(s) in <JDK dir>/lib
directory; copy those into your VC++ lib directory.
Under Solaris, unless you are the administrator, you
will not be able to write to the gcc standard include directory, so, your best bet is to
copy all the above mentioned to your project directory (that will make it simpler to point
to them). Note that in the JDK 1.2 Solaris version there is no lib file that needs to be
linked into your native code.
Once that is done, you are ready to write code! For
the purpose of illustrating the uses of JNI, we will convert our quicksort method into
native C code. The example is nice enough to illustrate the use of Java arrays in native
code, and is practically useful (the C version is faster than the identical Java version).
Note, that this section will not explain the
workings for Quicksort. You are recommended to go and read the Quicksort section of this
document before continuing. Also realize the the things described in this particular
section are not hard; they're quite easy. As soon as you successfully call your first native
method, everything will be clear.
Continuing from that encouraging sentence, lets get
to writing the code! We will start by implementing our main application code (which will
change later). So far, all we need is this:
import java.lang.*;
import java.io.*;
public class pQuicksortNative{
public static native void qsort(int[] c);
public static void main(String[] args){
int i;
int[] arr = new int[20];
System.out.println("inserting: ");
for(i=0;i<arr.length;i++){
arr[i] = (int)(Math.random()*99);
System.out.print(arr[i]+" ");
}
qsort(arr);
System.out.println("\nsorted: ");
for(i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println("\nDone ;-)");
}
}
This code looks nearly identical to the testing code
in Quicksort section. A thing you should definitely notice is the absence of actual
implementation of qsort() method. The declaration of qsort()
contains a keyword native, which tells the Java compiler that the
implementation will be loaded as a library at runtime. Implementation can be written in
any language, as long as it is a library load-able at runtime. (I'm sure there are many
ways of bending this definition, but that's what is generally assumed by the native
declaration.)
After compiling the above code, run javah
on the resulting class file.
> javac pQuicksortNative.java
> javah pQuicksortNative
This should generate a file named pQuicksortNative.h,
which is your C/C++ include file. It contains the declarations for all the native
methods of a given class. In our simple example, the include file should look something
like:
/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class pQuicksortNative */
#ifndef _Included_pQuicksortNative
#define _Included_pQuicksortNative
#ifdef __cplusplus
extern "C" {
#endif
/*
* Class: pQuicksortNative
* Method: qsort
* Signature: ([I)V
*/
JNIEXPORT void JNICALL Java_pQuicksortNative_qsort
(JNIEnv *, jclass, jintArray);
#ifdef __cplusplus
}
#endif
#endif
The scary message on top doesn't mean much (of
course you can edit the file), but it makes very little point to do so. This generated
file can be used with either C or C++ code. Our example will use plain C, but the few key
differences between C++ will be pointed out.
All we need to do now, is write our C module
containing the implementation of Java_pQuicksortNative_qsort. To make the
process simple, we will simply cut and paste the declaration into a new file, and continue
from there. We then take the Java source which we did in our Quicksort section, convert it
to C, and that's more or less the whole job. The C module (named qsort.c)
follows.
#include "pQuicksortNative.h"
JNIEXPORT void JNICALL
Java_pQuicksortNative_qsort(JNIEnv * jniEnv,
jclass javaClass,jintArray arr){
int i,j,left = 0,right,stack_pointer = -1;
int stack[128];
int swap,temp;
/* get actual array & it's size */
jint* c = (*jniEnv)->GetIntArrayElements(jniEnv,arr,0);
right = (*jniEnv)->GetArrayLength(jniEnv,arr) - 1;
for(;;){
/* see if to do insertion sort or quicksort */
if(right - left <= 7){
/* simple insertion sort */
for(j=left+1;j<=right;j++){
swap = c[j];
i = j-1;
while(i>=left && c[i] > swap)
c[i+1] = c[i--];
c[i+1] = swap;
}
if(stack_pointer == -1)
break;
right = stack[stack_pointer--];
left = stack[stack_pointer--];
}else{
/* quicksort */
/* find the median */
int median = (left + right) >> 1;
i = left + 1;
j = right;
/* swap the median */
c[median] ^= c[i];
c[i] ^= c[median];
c[median] ^= c[i];
/* make sure: c[left] <= c[left+1] <= c[right] */
if(c[left] > c[right]){
c[left] ^= c[right];
c[right] ^= c[left];
c[left] ^= c[right];
}if(c[i] > c[right]){
c[i] ^= c[right];
c[right] ^= c[i];
c[i] ^= c[right];
}if(c[left] > c[i]){
c[i] ^= c[left];
c[left] ^= c[i];
c[i] ^= c[left];
}
temp = c[i];
for(;;){
do i++; while(c[i] < temp);
do j--; while(c[j] > temp);
if(j < i)
break;
c[i] ^= c[j];
c[j] ^= c[i];
c[i] ^= c[j];
}
c[left + 1] = c[j];
c[j] = temp;
if(right-i+1 >= j-left){
stack[++stack_pointer] = i;
stack[++stack_pointer] = right;
right = j-1;
}else{
stack[++stack_pointer] = left;
stack[++stack_pointer] = j-1;
left = i;
}
}
}
/* release array */
(*jniEnv)->ReleaseIntArrayElements(jniEnv,arr,c,0);
}
The code changed only slightly from it's Java
implementation. One thing that should strike you as strange is the use of function
pointers in structures (the GetArrayLength(), etc.). It is correct to assume
that in C++, this code becomes a bit simpler. And something like:
(*jniEnv)->ReleaseIntArrayElements(jniEnv,arr,c,0);
Will reduce to something like the following in C++:
jniEnv->ReleaseIntArrayElements(arr,c,0);
We're not in C++ however. Don't think that the C++
way is faster or more efficient however; it does exactly the same thing as the C method,
and thus, takes exactly the same time to execute.
Now, what are those weird functions which we call?
Why do we need that GetIntArrayElements() or GetArrayLength(),
and why do we need to call ReleaseIntArrayElements() when we are finished
sorting? Good question; the answer is in the way JavaVM works.
In C, we have the good old malloc()
& free() to allocate/free memory. In C++, we have the all versatile new
& delete operators. In Java, we have the new operator and
the good old garbage collector. This fact that memory in Java is not fully controlled by
the programmer, but by the Virtual Machine makes for some interesting issues when letting
C code play around with memory managed by the JavaVM.
The native module expects memory to
stay in one place. It does not want things to be wiped out or garbage collected when it is
using them. The primary reason for calling GetIntArrayElements() method is to
notify the JavaVM that we want to use that block of memory. The JavaVM has several options
at this point. It can pin-down this block of memory (prevent it from being moved), or it
can create a copy of the original data, and let us play around with the copy. No matter
what it does, when we are done using the memory, we have to notify the JavaVM that we are
done using it (so that it can unpin the memory, or copy the new memory block over the old
one).
It is interesting to note that under Microsoft
Windows it primarily seems to give you the pinned down memory, while under Solaris, it
tends to give you a copy to work with. You can tell whether it's a copy or not by passing
the address of a jboolean variable as the fourth parameter to GetIntArrayElements().
I suggest you look though the JDK and JavaVM documentation for a more detailed
explanation.
If you are really into it, you might have noticed
other changes in the code. Some of the swap code now uses XOR instead of a
temporary variable to swap numbers. I think it's kind of cute. (but only works for
numbers, not objects)
Gotten this far, it would be a shame not to compile
it! Using command line options to generate a DLL under Microsoft Windows:
> cl /GD /LD qsort.c
and under UNIX (Solaris):
> gcc -shared -I $HOME/javadata -o qsort.a qsort.c
Assuming you are in the correct directory, your PATH
is setup correctly, and everything else works, you should have a qsort.dll
under Windows, and/or a qsort.a shared lib under UNIX.
Now that you got that done, you can go ahead and
modify your Java application to load the library. The code for a contemporary load()
procedure would look something like this:
static{
System.load("c:/projects/javadata/qsort.dll");
}
Of course, the absolute path to the library will be
different. This System.load() method requires that we pass the complete full
path of the shared library to it. There is another method: System.loadLibrary()
that only requires the name of the library. This loadLibrary() assumes that
the library is inside some system directory, other than that, the idea is the same. And
now, for a paragraph of preferences:
I found it simpler to use the System.load()
as opposed to System.loadLibrary(). In the former one, you specify the full
path, and you're done with. With System.loadLibrary() however, it's not that
simple. For one, you have to specify just the name of the DLL under Windows,
without the actual .DLL extension. This technique obviously doesn't work
under UNIX, where there are no DLL files. Under both systems, the library
loaded by System.loadLibrary() has to be inside some system library
directory. Under Microsoft Windows, it is supposedly the \Windows\System, and
under UNIX, it is supposedly the /lib (among other things). Everything will
still work under Windows if the DLL is not in the system directory, but not
under UNIX. One could argue that you can modify the Properties directly from
within the Java application, and make it think that the current directory is a system's
lib directory, but that's a pain in the neck. Because of these reasons, we will use System.load()
throughout this document.
Modifying the original Java test application gives
us:
import java.lang.*;
import java.io.*;
public class pQuicksortNative{
static{
System.load("c:/projects/javadata/qsort.dll");
}
public static native void qsort(int[] c);
public static void main(String[] args){
int i;
int[] arr = new int[20];
System.out.println("inserting: ");
for(i=0;i<arr.length;i++){
arr[i] = (int)(Math.random()*99);
System.out.print(arr[i]+" ");
}
qsort(arr);
System.out.println("\nsorted: ");
for(i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println("\nDone ;-)");
}
}
Not much change from the original one, huh? This is
obviously a Microsoft Windows version (so much for code portability...) We can just
replace that absolute path with a UNIX path to that of UNIX lib, and it will work there as
well. To make it more portable, we will move the library loading code into the main()
method, and will accept the path to the lib from command line. So, under UNIX, you'll pass
the path to UNIX lib, and under Windows, you'll pass the path to that DLL.
For example:
import java.lang.*;
import java.io.*;
public class pQuicksortNative{
public static native void qsort(int[] c);
public static void main(String[] args){
if(args.length > 0)
try{
System.load(args[0]);
}catch(java.lang.UnsatisfiedLinkError e){
System.out.println("bad lib name: "+args[0]);
return;
}
else{
System.out.println("include lib name as parameter");
return;
}
int i;
int[] arr = new int[20];
System.out.println("inserting: ");
for(i=0;i<arr.length;i++){
arr[i] = (int)(Math.random()*99);
System.out.print(arr[i]+" ");
}
qsort(arr);
System.out.println("\nsorted: ");
for(i=0;i<arr.length;i++)
System.out.print(arr[i]+" ");
System.out.println("\nDone ;-)");
}
}
The output of such a program follows:
C:\projects\javadata>java pQuicksortNative c:\projects\javadata\qsort.dll
inserting:
55 3 46 54 18 89 0 71 89 45 31 81 67 76 57 4 97 48 59 60
sorted:
0 3 4 18 31 45 46 48 54 55 57 59 60 67 71 76 81 89 89 97
Done ;-)
Alternatively, you might have a configuration file
which stores this kind of information (what system it is running on, which lib files to
load, etc.) An ugly thing to do could be to name all libraries the same name, so that the
code always knows what to load. This situation can lead to wrong libraries being loaded,
and other horrible things.
I am guessing that's enough of drilling this stuff
into your mind. If you want to learn more about native methods, you can pick
up a lot from the Java documentation found at Sun's web-site. If you don't want to learn
more, then what you've learned so far, should be more than enough for the purposes of
general knowledge.
Back to Table of Contents
A D V E R T I S E M E N T
|
Subscribe to SourceCodesWorld - Techies Talk |
| 
Add to Favorites
Make Home Page
