Skip Lists Algorithm and Runtime Profiling

Skip List Runtime on dictionay operation compared to Splay Trees and Hash Tables. (Coded in Java)

Skip lists are a relatively new data structure. This is an ordered list where the nodes are connected together at multiple levels. Different levels of connected nodes need not be uniform. This allows the skip list to skip items during a search. Each level is an ordered list in itself.  Every node has a level and is connected to different nodes in the same level. This allows data structure operations to skip through the list. Example is the following list where there are two levels.

Level 1 connections                  E ----------> X
Level 0 connections A ->; B -> E -> F -> G->X -> Y -> Z

Level 0 list is the same as a linked list. E has connections has two levels. If a search was for say 'G'. The algorithms is as follows Start at Level 1, X > F so we move down at 'E' and then proceed at level 0 from E till G is found. Nodes A and B were skipped.

SkipList Search Algorithm:
1) Start from the top level proceed until level 0
    a) Move to the right until a node with node Key < search Key
    b) Jump to the next lower level.
2)  If 1a resulted in an exit in level 0, the next node could be the search node. else it is absent.

Here is a skip list implementation holding values A to Z. The nodes encountered during the search for H and M are shown.

Level 2 Skip List. 

Level 6 Skip List

In order for the list to be helpful level at each node needs to be decided at Random during the insert operation of that node. The maximum level that is useful in a skip list is ln N -1 where N is the number of items expected to go into the skip list. 

Algorithm Inserting in to the Skip List

1 Find the node as in search. This will return the node that will be to the left of the new node (L).

   a) While dropping down to the lower levels maintain the nodes in an update List.

2 Create the new node with a random level. 

3 Adjust the pointers from the existing L node to the new node.If the new level is greater than the existing level of the list, then the head of the list should be adjusted to point to the new node at the new level.

4 Set the next pointers of the new node to next pointers of L

5 Set next pointers of L to the new node at that level. This is done for each node where level was changed in step 1.

For example in the case of 

Level 1 connections                  E ----------> X
Level 0 connections A -> B -> E -> G->X -> Y -> Z. We need to insert H with level 3 then, at level 1 we drop down at E and also at G in level 0. So, G->next = H at level 0, E-> next = H at level 1, F -> next = X at level 1 and at level 2 H is linked to head and tail of the list.


Level 2 connections                                  *<-H->*
Level 1 connections                  E ----------->H-> X
Level 0 connections A -> B -> E -> F -> G->H->X -> Y -> Z

Runtime of Skip Lists: Dictionary operations on skip lists take O(Log(n)) time. Finding each new node's level is done in random as follows














Comparison of Skip List, Splay Binary Search Trees and Hash Table

For a serious input of 56000 word dictionary, the search operations on Skip lists, Splay Trees and Hash Table is as follows. Skip list took 40 comparisons at 11 levels to find the word 'Skip' in the dictionary.

Splay tree took less time than the skip list at

Hash Table left the above two way behind in run time

Result: In general skip lists and splay trees can't hold candle to hash tables. 

Ant Power : Build Automation

Ant is helpful in any java project involving large number of resources. Ant based on xml and java itself can help to compile java classes, put the classes in a jar or war, create file folders before building projects and interfacing with servers like tomcat to perform application installation. This is useful in java enterprise web applications and enterprise applications. Ant ships with popular IDEs like eclipse and Rational Application Developer.

Ant manual webpage  provides a sample build.xml file that can be customized by developers instead of writing it from scratch. This is a modification of that, file with modifications pertaining to ; building webapps for tomcat 7.0.26. For example a change is the compilations of classes and creating a war using war rather than jar (purpose!). Some changes were needed for tomcat 7.0.26 for example the manager url.

The sample folder structure used for eclipse dynamic web application is shown here.

The project tag is here. Base dir is .. since the ant build.xml is in 'Ant' folder. Multiple ant files can be grouped in this folder in a huge project.

The properties declaration that I use

The compile element with changes

The dist element which creates the distribution war file in the dist folder.

New elements to stop, remove, compile, install and start the web application.

The resulting WAR file contents

Java Authentication and Authorization Service JAAS - Java Security- Create a Login

How to create a custom Jaas Login Module?

Java Authentication and Authorization service allows applications to authenticate subjects independant of the underlying authentication mechanism. This is done by standard interfaces defined in the JAAS architecture. Any authentication mechanism that, conforms to these interfaces can be used by the application through JAAS without getting entangled in the fine details of the mechanism. This is typically used when applications need to authenticate subjects using a different mechanism than provided as part of an application framework. For example, custom database lookup to autheticate users rather than FORM authentication in a webapp under tomcat.

The LoginContext allows applications to login and out i.e authenticate(and also authorize). Applications don't interact with the security mechanism that provides the authentication mechanism. It may be a kerberos login or a login mechanism where you deal the user name and password. When you initialise the context you specify the LoginModule_Configuration you will use to login. You also specify the callback handlers which gets the information from the user(or someother place) and puts it in callbacks. Callback has the info needed by application. Callbackhandler implements interfaces which allow the application classes to get the information from the authentication mechanism. While the application is executing the login() method of the underlying
authentication mechanism, the handlers get the credentials and puts them in the callback. In the login() method the call backs can be polled to get the information they have.

Handler's handle method sample.

Login method in a class that extends LoginModule interface.

Loginmodule is an implementation of the jaas compatible security mechanism that, performs the authentication. A custome module can be coded by implementing the interface.The modules available are specified in a jaas configuration file and that module classes/jars should be available for the application to load.

Jaas configuration file.

You mention the options to be used with a loginmodule in the jaas configuration file. For example, do you want the loginmodule to be a mandatory success thing for applications to go through? requisite? failing ok? you mention the location of the jaas configuration file in  your java.security file. The java.security file is located in your_jre/lib/security/java.security. This is underlying login.config.url.= your_jaas_config_file here. if nothing is mentioned here it will look in you home folder for .java.login.config file. Sometimes a
behaviour noted is that, if you are running as a root user this will be accessed irrespective of anything else!!. This is the case when you run from eclipse as a root user. Simply put, this is the name of the class that implements the LoginModule interface. Standard providers like kerberos do this. You can also implement the
interface and put it here. The name at the top of the {} brackets is the 'name of the login configuration' you will refer to in your application.

Example jaas configuration specification in Java.Security file