Semaphores and Synchronization Patterns

Semaphores as we know is a mechanism that is used to solve the issue of synchronization . The concept and use of semaphores is a bit more than what you normally call ' tricky ' .Here we try and analyze a basic synchronization pattern and solve the issue with semaphores .

Have a look into the pattern given below .

statements in THREAD A

strcpy(a , "Hello ");   -  A1
printf("%s\n" ,b);      -    B2

statements in THREAD B

strcpy(b , "World")  - B1
printf("%s\n" ,a);    -  A2

Here we have two threads which consists of two statements each .
Constraint :
What we need to ensure is that the statements suffixed A1 & B1 are executed before the statements suffixed A2 & B2  execute. Here the two threads 'rendezvous ' at a point of execution and is not allowed to proceed until both have arrived .

Without using a mechanism like semaphore , no way is it possible to ensure such a constraint due to the scheduling mechanism that cannot be predicted . Hence we use semaphores to solve this issue .

To ensure that it works according to wish  , we do this :

THREAD A

strcpy(a , "Hello ");  - A1
up(sem1);
down(sem2);
printf("%s\n" ,b);   - B2

THREAD B

strcpy(b , "World");  - B1
up(sem2);
down(sem1);
printf("%s\n" ,a);   - A1

Now we need to give a thought on how this works .
Here we have two semaphores ,sem1 and sem2 as we have two critical sections

Now , how is the synchronization issue solved .?
The 'down ' operation just before the two statements suffixed '2' ensures that the two statements are not executed until the 'up' operation on the corresponding semaphore is not invoked . Hence whichever be the order of scheduling , both the threads rendezvous at a point and will not proceed ( as a result of the 'down' operation )until the next thread arrives (and the corresponding 'up' operation is performed ).

This synchronization pattern as been solved using semaphores .

You could find the solution to these and more such patterns from here .

Memcheck : A Memory Error Detection Tool

Linux distros provide a  tool suite called 'Valgrind' that consists of a number of tools that help you make your programs faster and more correct . The most popular tool out of this is called is memcheck that is used to detect memory related errors in C and C++ programs that can lead to serious issues like  segfaults and even more grevious issues like unpredictable behaviours .

Lets take a look into how we use the tool 'memcheck' so that we detect , try and avoid the memory related issues in our program.

First of all we need to create a memory leak so that we have something to detect .

We write a program that consists of a memory leak . Here is one such in a file ' pgm.c'

1 #include <stdlib.h>
2 #include <string.h>
3 void f(char *s)
4 {
5 char *x = malloc(strlen(s));
6 x[7] = 0;
7 }

8 int  main()
9 {
10 char *s="Hello";
11 f(s);
12 }

As you could see , there are two major memory related bugs in this code:

1) Trying to write in the location x[7] which is out of the allocated memory space .This will lead to what is called a 'heap block overrun' .

2) The memory that is allocated to x remains unused . This memory becomes garbage on returning from the function . In short , you have seen a 'memory leak '.

Now lets try and detect the two problems using memcheck :

You need to have valgrind installed in your system .
$ : apt-get install valgrind
if you don't have it already .

Do

$: cc -g pgm.c

We  compile the program using the -g option so that the line number informations are displayed when using memcheck .

Do

$: valgrind  --leak-check = yes a.out

the option  ' --leak-check ' being set equal to yes displays the informations on memory leak issues .

Now lets look out what are the informations that are being displayed when the memcheck tool is used .

First lets have a look into the 'heap block overrun' problem :

==3350== Invalid write of size 1
==3350==    at 0x80483F6: f (pgm.c:6)
==3350==    by 0x804841D: main (pgm.c:11)
==3350==  Address 0x419102f is 2 bytes after a block of size 5 alloc'd
==3350==    at 0x4023D6E: malloc (vg_replace_malloc.c:207)
==3350==    by 0x80483EC: f (pgm.c:5)
==3350==    by 0x804841D: main (pgm.c:11)

The above few lines is the code that was generated by memcheck  .

'3350' is the process id .

The actual error is seen right at the first line .

'Invalid write  of size 1' .

You get a stack trace right after this line , that

the invalid write has occured at the 6th line as a result of the 12th line . You could see what line numbers '6' and '11' do by having a look into our code , its the point of occurence of the error and the function call respectively.

A line showing the the fact that the location you are trying to access ( x[7] ) is 2 bytes after the allocated area can also be seen added with lines that contain information about the main and the function .These lines provide great help to the programmer especially when the case becomes a lot more complicated .

Now the informations that are displayed about the 'memory leak problem' can also be looked into .

==3350== LEAK SUMMARY:
==3350== definitely lost: 5 bytes in 1 blocks.
==3350== possibly lost: 0 bytes in 0 blocks.
==3350== still reachable: 0 bytes in 0 blocks.
==3350== suppressed: 0 bytes in 0 blocks.

You could view the lines that provide information about the memory leak problem .
The first line of the 'LEAK SUMMARY ' is the most significant to us . It shows the amount of memory definitely lost ( 5 Bytes ). Changes need to be made in the program so that the memory leak is prevented .

Memcheck produces these result which helps the programmer so as to view and correct the memory related issues rather convincingly . It needs to be noted that Memcheck is a 'dynamic instrumentation tool ' and not a static tool like 'lint ' . Hence to detect the memory leaks in a program , the control actually needs to get transferred to that segment of the program where the issues occur . In short you need to invoke the function 'f' from your 'main' so that Memcheck could detect those memory related issues that exists within the function 'f' .

Common Subexpression elimination ( CSE) by the GCC Compiler

Common subexpression elimination (CSE) is a compiler optimization technique of finding redundant expression evaluations, and replacing them with a single computation . This saves the time overhead resulted by evaluating the expression for more than once . We will have a look into this phenomenon by considering a simple code and again taking a walk through its assembly code .

Consider the code that we have written and saved in file ' pgm.c '

main(){
int i, j, k, r;
scanf("%d%d", &i, &j);
k = i + j + 10;
r = i + j + 30;
printf("%d %d\n", k, r);
}

Do :

$ : cc -S pgm.c

$ : less pgm.s

Read the assembly code ' pgm.s '

Scan the assembly code and find out the call to the function 'scanf()' . This is where our area of interest begins . This is because its after calling 'scanf ' that we load the value of the input variables into the registers .

Right after the call to 'scanf ' , i have this in my assembly code ,

movl    -16(%ebp), %edx
movl    -20(%ebp), %eax .

Here we move the values of the two variables 'i ' and 'j ' into registers 'edx ' and 'eax ' .

Now just have a look into our C code and you will see the two expressions as follows :

k = i + j + 10;
r = i + j + 30;

Looking at the two expressions , you would find out the redundant part in the two expressions .

Its that 'i+j' is calculated twice .

Now lets find out what happens in the assembly code :

I had these statements in your assembly code :

movl    -16(%ebp), %edx

movl    -20(%ebp), %eax ----------> We had mentioned these two statements  above .

leal   (%edx,%eax), %eax -------->  values in edx and eax are added and loaded into eax

addl    $10, %eax -------------------->  the constant 10 is added with the value in eax

leal   (%edx,%eax), %eax --------->   values in edx and eax are added and loaded into eax

addl    $30, %eax -------------------->  the constant 30 is added with the value in eax

You could see that there is redundancy in the assembly code .

The statement ' leal(%edx,%eax), %eax ' performs the evaluation of the subexpression ( ' i + j ' ) which is done twice thereby throwing in redundancy and hence creating unnecessary overheads .

Obviously our compiler when asked to perform optimization would avoid this redundancy .This is what is termed as Common Subexpression Elimination ,i.e , the subexpression that is common( ' i + j ' ) in the two expressions is evaluated only once , in essence the second evaluation is eliminated .  Lets have a look into CSE by again peeping into our assembly code  .

Do

$ : cc - S - O3 pgm .c

$ : less pgm.s

Take a look into your assembly code  .

As mentioned above , our area of interest starts from the call to 'scanf ()' .

Instead of those 6 statements that were used to evaluate those two expressions ,

i + j + 10 & i + j + 30 ,

you would find this ,

movl    -12(%ebp), %eax ---------------->  move the value of the variable 'i' into eax

addl    -8(%ebp), %eax -------------------> add the value of the variable 'j' with 'i' stored in eax .

leal    30(%eax), %edx -------------------> adds 30 with eax ( contains the sum of i & j ) and stores in edx

addl    $10, %eax ---------------------------> adds 10 with eax ( contains the sum of i & j ) and stores in eax .

Here the second statement performs the evaluation of the subexpression , ' i + j ' . You could get it quite clearly from the code segment that the redundancy that was found in the unoptimized assembly code has been eliminated by the compiler .

The later 2 statements perform the evaluation of the expressions

( i + j + 30 )   and    ( i + j + 10 ) respectively .

We have just used a very simple case of CSE , but this optimization technique could be used in even more useful cases . Consider :

k = f() + g() + 30

r = f() + g() + 10

where f() and g() are functions . In an unoptimized code , the technique of CSE wouldn't be used and hence there would be overhead due to the redundancy added with the more serious problem of having to call each function twice . The technique of Common Subexpression Elimination avoids this very redundancy  .

Function inlining

Function inlining is performed when a request has been made to the compiler to perform optimization on the code . The compiler will try (its important to remember that ,it is a request made to the compiler, not an order) and insert the complete body of the function in every place in the code where that function is used so as to eliminate the time overhead when the function is called . We could get an idea of function inlining by peeping into the assembly code generated by the compiler .

We do this with the help of a small program :

int sqr(int x)
{
return x*x;
}

main()
{
printf("%d\n", sqr(10));
}

We have the program written in a file  'pgm.c'

Do :

$: cc -S pgm.c

We could now view the assembly code generated by the compiler

Do:

$: less pgm.s

I found out the following lines in the 'main' function of ' pgm.s '

movl    $10, (%esp)
call    sqr

You would have the idea cleared up

The constant '10 '  is stored in the stack , and the call to the function 'sqr ' is made . The result of squaring up 10 is performed in the function 'sqr' . This obviously would create overheads for invoking the function .

Now consider the case where you have requested the compiler to perform all optimizations on your code .

$ :cc -S -O3 pgm.c

Now have a look into your assembly code .

$ :less pgm.s


Now just have a look into the your 'main' function and find out what you see where you had seen the previous two lines that i did mention above .

You would just find a singe line corresponding to those two lines which you had found in your assembly code that was not optimized .

This is what i found ,

movl    $100, 4(%esp)


The final value that you obtain after finding the square of 10 ( i.e 100 ) is has been moved into the stack , but where is the call to the function 'sqr' ?

You have just seen ' function inlining '. The function body had been inserted at the point where the function was used and the value '100 ' calculated at compile time instead of performing the calculation at run time .This saves a lot of time that would have been required to calculate the value of '100' by making a call to the function at run time .Performing function inlining avoids this .

Python DB-API

Python is one of the more popular Open Source programming languages, owing largely to its own native expressiveness as well as to the variety of support modules that are available to extend its capabilities. One of these modules is DB-API, which, as the name implies, provides a database application programming interface. We will have a discussion about how to connect and use a General purpose database system like Mysql with Python. The DB API provides a minimal standard for working with databases, using Python structures and syntax wherever possible .

4 Steps of the Python DB-API includes the following:

1) Importing the API module. 

2) Acquiring a connection with the database.

3) Issuing SQL statements and stored procedures.

4) Closing the connection

There are lots of database systems that are available .Here we use Mysql as our database system .You could also use database systems like PostgreSQL, SQL Server etc. Python's DB-API uses a two-level architecture in which the top level provides an abstract interface that is similar for all supported database engines, and a lower level consisting of drivers for specific engines that handle engine-dependent details. This means, of course, that to use DB-API for writing Python scripts, you must have a driver for your particular database system. Since we have fixed our database system as MySQL, DB-API provides database access by means of the MySQLdb driver . Therefore we need a module MySQLdb in Python '' .

At first , we need to get Mysql installed in our system.

$: apt-get install mysql-server-5.0

Just try and enter into the interactive prompt of mysql .

$: mysql -u 'user' -p

You will get your mysql interactive prompt where you could just brush up your sql knowledge.

Step 1) Importing the API module.

You need to make sure that you that have MySQLdb installed on your machine.

Do this:

$: python

>>>import MySQLdb

Obviously if you dont have it installed , you would be getting this :

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ImportError: No module named MySQLdb

To install MySQLdb module, download it from MySQLdb Download page and proceed as follows:

$ gunzip MySQL-python-1.2.2.tar.gz
$ tar -xvf MySQL-python-1.2.2.tar
$ cd MySQL-python-1.2.2
$ python setup.py build
$ python setup.py install

Now do

$ : python

>>>import MySQLdb

>>>

We have done with Step 1) out of the 4 steps of the Python DB-API .

Now we move into step 2). The prerequisite for performing step 2) of the DB-API is that you need to create a database ( 'Persons' in our examples to follow ) in mysql .

You could do this by :

$: mysql -u 'user' -p

Enter mysql .

Do :

mysql>CREATE DATABASE Persons;

mysql>Query OK, 1 row affected (0.03 sec)

Once you have done with this

Step 2 ) Acquiring a connection with the database.

 

conn = MySQLdb.connect (host = "localhost",

user = "user",

passwd = "asdfgh",

db = "Persons")

Here we open a database connection using the 'connect' function of the MySQLdb module.

The four parameters that are passed to the function 'connect' are :

host --      the system in which the database is created

user --      the user who is trying to acquire a connection with the database ( the user must be authenticated with mysql if the attempt to create a connection needs to be successful.

passwd --      the password of the mysql database system .

db --      the name of the database created using mysql .

If the 'connect()' call succeeds, it returns a connection object that serves as the basis for further interaction with MySQL( here 'conn'). If the call fails, it raises an exception .Therefore you better perform exception handling so that you get to know more about the root cause of the error.

try:

conn = MySQLdb.connect (host = "localhost",

user = "root",

passwd = "asdfgh",

db = "Persons")

except MySQLdb.Error,e:

print "Error occured ",e.args[0],e.args[1]

sys.exit (1)




Here on an unsuccessful attempt to make a connection , an exception is raised ( MySQLdb.Error ) , the information about the error is stored in e.args[1] .

 

Step 3) Issuing SQL statements and stored procedures.

Now we need to create a cursor object for the connection between Python and mysql so that all the functions performed by sql are performed within from Python now . We create a cursor object using the ' cursor()' method .

We are all set to execute sql statements in an Object oriented environment , and thats using the 'execute()' function . Any sql statement can be called in from Python using the 'execute()' function.

Consider you want to create a new table in our database 'Persons' .

cursor.execute("""

CREATE TABLE PERSON

(

ID int,

lastname CHAR(40),

firstname CHAR(40),

City CHAR(40)

)

""")

You have created a table named 'PERSON ' with fields as mentioned above .

As you would imagine , any other statements could be performed as such , for eg.

cursor.execute ("""

INSERT INTO PERSON (ID, lastname,firstname,City)

VALUES

(1,'KUMAR','SUNIL','KANNUR'),

(2,'JOHN','HARI','KOTTAYAM')

""")

or

cursor.execute ("SELECT * FROM PERSON WHERE City like 'K%'")

and any of the sql statements .

Step 4) Closing the connection

conn.close()

Here we have terminated the connection after all our need with the DB-API has been done with . The DB-API allows us to update , insert , retrieve and modify within a database in a simple and elegant way .

We have tried and demonstrated a simple example of how to use the Python DB-API .

Using Python with Sql,we have found an object-relational mapping where the object-oriented programming paradigm of Python meets the relational paradigm of Sql. An object-relational mapping is a bridge between the two worlds. As we saw , it lets us define classes that correspond to the tables of a database. Later , we use methods on those classes and their instances to interact with the database .

Implementing the Avl Tree

AVL Tree is a self-balancing binary search tree and it was the first such structure to be invented. The tree is said to be balanced because the difference in the heights of the child subtrees differ by atmost one. The operations Insertion, Deletion and Lookup on an Avl tree is of the order of  Log n because of this balancing act. Here we take a look into the implementation of an AVL tree .

First we need to give a thought on the term 'balance Factor' and on the major operations that are involved in the making of such a tree.

Balance Factor:Balance factor is associated with each node of the Avl tree. Its the difference between the heights of the left subtree and right subtree of that particular node.

Balance factor = height of left subtree – height of right subtree.

A balance Factor of 0 , +1 or -1 for each and every node of the tree indicates that its balanced. Whenever the balance Factor of any of the nodes equals – or + 2 , the tree becomes unbalanced and needs to undergo balancing.

Now lets just peep into the major operations that are involved in the build up of the tree.

There are 3 of them

1) Insertion:2) Deletion:3) Rotation:

Insertion is the usual process. There is nothing special in inserting a node into an Avl tree than in inserting it to a normal binary search tree.

Deletion is again the same with a minor difference which we will look in to as we continue.

Rotation is the balancing act- The operation that distinguishes an Avl tree from the normal binary search tree. Rotation needs to be performed whenever the tree goes out of balance – this could happen as a result of the first two operations ( Insertion and Deletion ). The Balance factor may go beyond 1 and hence the tree will have to be balanced so that it remains as an Avl tree. Each of the three operations , specially that of rotation will have to be given due care in building up an Avl tree.

You could sum it up this way :

Each insertion in an Avl tree is a combination of normal insertion into a binary search tree added  with finding out whether the tree is unbalanced or not followed by rotation if necessary.

Each deletion in an Avl tree is a combination of normal deletion into a binary search tree added with  finding out whether the tree is unbalanced or not followed by rotation if necessary.

Before we get into more details of each of them , we will have a look into the way each node is implemented in the Avl tree.

Each and every node in the Avl tree is implemented as a structure .This is same as what is done in an ordinary BST , since Avl tree is itself a BST.

struct node{

int data;

struct node *parent,*left,*right;

}*p,*root=0;

The field 'data' contains the actual data that is to be stored in the node .There are three pointers of the type 'struct node*'.

*left –> points to the left child of the node

*right –> points to the right child.

*parent –> points to the parent node .



Now lets get into the details of the different operations performed on the Avl tree.

Inserting into an Avl Tree can pictorially be represented as follows:



Obviously , there are other functions that are involved in the process, but the ones shown in figure are the significant ones.

avl_insert : As discussed earlier insertion into an avl tree consists of the normal insertion followed by the checks for balancing and rotation if necessary. Normal insertion is performed first . Then the function self_bal() is called :

self_bal() : The newly inserted node would obviously be balanced since it wont have any children. Therefore the balance factors of the nodes that come above the inserted node in the tree ( starting from the parent ,right upto the root ) is to be checked. The function 'self_bal' invoked 'balance()' which performs the further tasks. Again, since a newly created tree is always balanced and since parent of the root points to NULL , the function 'balance()' should not be called if the newly inserted node is the root itself.

balance() : Invokes the function bal_fac() and checks if the balance factor is equal to +or- 2 . If yes , calls the appropriate rotate function.

bal_fac() : Finds out the balance factor for each node.

rotate() : Here rotate() is the just the cohesive name for the two types of rotate functions . According to the balance factor , the appropriate 'rotate' functions are called. We will discuss them in detail later.

The pictorial representation of 'delete()' would be no different.



By now you would have understood that the central aspect in building up the whole Avl tree is the rotate() function, but before we get into implementing the 'rotate()' function , its of prime importance that we give a little more thought into implementing the 'delete()' function in the Avl tree. As mentioned above , there is just a minor change that needs to be made , due to the self balancing nature of the Avl tree.

While performing a 'delete()' function in a normal BST, we need to look into 5 different cases of how a particular node could be deleted and replaced with another one. Just peeping into them:

1)The victim node being a leaf node.

2)The victim node having a right child.

2.1) The victim node having a right child with a left subtree.

2.2) The victim node having a right child with no left subtree.

3)The victim node not having a right child.

3.1) The victim node having a left child with a right subtree.

3.2) The victim node having a left-child with no right subtree.

Certainly , from what we have discussed until now, its clear that one of these conditions never happens. You might have guessed it by now.

Case 3.1) would never happen in an Avl tree. This could be explained with the following figure.

Consider you want to delete the node '10' after adding '9' to the tree , but adding '9' to the tree would leave it unbalanced.



Hence the tree will be rotated so that it becomes balanced ( how?, we will come to know shortly) before you could delete '10' . Hence there will never be a case of a victim node have a 'left child with a right subtree' and does not have a right child of its own.

Now , its time that we move into the  in the creation of an Avl Tree, the 'rotate() ' function.

Rotation ,as mentioned ,follows up a deletion from or an insertion into an Avl tree in such a way that it destroys the balanced nature of the Tree.

There are 4 kinds of rotation which are implemented using 2 different rotation functions.

Its crucial at this stage that the following points are understood.

Balance factor of a node = +2 implies that the node ( and ultimately the tree) is unbalanced because of the left subtree of the node and there will be one right rotation for sure.

Balance factor of a node = -2 implies that the node ( and ultimately the tree) is unbalanced because of the right subtree of the node and there will be one left rotation for sure.

Whether a single rotation needs to be done or whether the tree needs to be rotated twice depends upon the balance factor of the child of the root of the subtree that is unbalanced. You needn't scratch your head on this , stuffs that follow would lighten up things.

Let 'point' be the root of the subtree which has made the tree go out of balance . The 4 kinds of rotation are:

1)left – left rotation: If balance factor(BF) of point is 2 and the BF of the left child is > 0 , then a single 'right' rotation would do it for you.

2)left – right rotation: If BF of point is 2 and the BF of the left child is < 0 , then a 'left' rotation followed by a 'right' rotation would do it for you.

3)right – left rotation: If BF of point is -2 and the BF of the left child is > 0 , then a 'right' rotation followed by a 'left' rotation makes the tree balanced.

4)right – right rotation: If BF of point is -2 and the BF of the left child is < 0 , then a single 'left' rotation would be enough.

We will discuss rotation which happens as a result of the tree being unbalanced after an insertion or a deletion has been performed. The 'rotation' function is independent of whether the previous function was a deletion or an insertion , it depends only on the current structure of the tree.

Left-Right Rotation & Left-Left Rotation

Consider the figure :

Here the point of imbalance is '23' and the reason for imbalance is the left subtree of '23'. Hence performing a 'right' rotation is essential . Now the left child of '23' has a BF of -1 ( < 0 ) . Hence a left rotation also needs to be performed. This leads to a left-right rotation .

left rotation : Left rotation is performed by invoking the rotate_left() function. The two parameters that are to passed to the function are 'root' and 'pivot' .

Root ---> point of imbalance , I.e '17'

Pivot ---> right-child of the point of imbalance I.e '19'.

 

The left rotation has been performed.

Now our problem has been reduced to performing a left-left rotation , you could see that from the figure .That is ,we need to perform a single 'right rotation':

right rotation : The right rotation is performed by invoking the rotate_right() function. The two parameters would be :

Root ---> point of imbalance : I.e 23

Pivot ---> left-child of the point of imbalance I.e '19'.

 

 

 

The right rotation also has been performed. Now you may have a look at the tree and would find out that its balanced .

Right-Left Rotation & Right-Right Rotation.

Consider the figure above :

Here the point of imbalance is '17' and the reason for imbalance is the right subtree of '17'. Hence performing a 'left' rotation is essential . Now the right child of '17' has a BF of 1( > 0 ) . Hence a 'right' rotation also needs to be performed. This leads to a right-left rotation .

right rotation : right rotation, as mentioned above is performed by invoking the rotate_right() function. The two parameters that are to passed to the function are 'root' and 'pivot' .

Root ---> point of imbalance , I.e '23'

Pivot ---> left-child of the point of imbalance I.e '19'.

The right rotation has been performed.

Now our problem has been reduced to performing a right-right rotation .That is ,we need to perform a single 'left rotation':

left rotation : We have seen that left rotation is performed by invoking the rotate_left() function. The two parameters would be :

Root ---> point of imbalance : I.e '17'

Pivot ---> right-child of the point of imbalance I.e '23'.

The left rotation also has been performed. The tree has been balanced .We have found out how a tree could be balanced through rotation.

There is another issue that we need to deal with while performing rotation. Two questions that we need to consider here are...

1)What happens to the left node of the pivot during a left rotation.?

2)What happens to the right node of the pivot during the right rotation.?

Consider the following figure .

The tree as you could see is unbalanced with the root ('23') being the point of imbalance, the left subtree being the reason for the imbalance.. Since the BF of the left child of the root = -1 ( < 0 ) , we need to perform a left – right rotation . I.e a left rotation followed by a right rotation . For performing the left rotation , the root is '17' and the pivot is '19'. As you could see from the figure ,the left child of the pivot is marked 'L' . Our question is what exactly happens to this 'L' after the left rotation has been performed. ? The answer is right there in our next figure .

L has become the right child of '17 ' . To be more precise ,after a left rotation, 'L'( the left child of the pivot) has become the 'right child' of the node which was the parent of the 'pivot' before the rotation was performed.

As you could see, the tree still remains unbalanced as we have not performed the 2^nd phase of our left-right rotation . We perform the right rotation and make the tree balanced .

I think , by now you would be able to guess out the solution for the second question that we had asked .

What happens to the right node of the pivot during the right rotation.?

The answer is certain , this is exactly the complement of what happens after a left rotation that we have just seen . After performing a right rotation , the right child of the pivot becomes the left child of the node that was its parent before the rotation was performed.

Here , I have tried and dealt with almost all issues that come up in the implementation of an Avl tree. You could download the complete source code here

GNU make

The make utility determines which pieces of the program needs to be recompiled and issues instructions to recompile them.GNU make is the most popular make available. Lets get into the working of make with a simple example but please do read THIS before moving into further details.

By reading that, you would have understood that our ultimate aim is to produce a file '_avl.so' so that the C module 'avl.c' could be extended into Python.
Lets check what exactly do we need to do here.

We begin with 2 files namely 'avl.c' and 'avl.i'. We need to create a wrapper file at first . This is done by:

$: swig -python avl.i

Next what we need to do is that we need to create 2 object files for the respective C files- i.e we need to produce 'avl.o' and 'avl_wrap.o' from 'avl.c' and 'avl_wrap.c' respectively.
We do this by:

$: gcc -c avl.c avl_wrap.c -I /usr/include/python2.5/

The last and final step is to create '_avl.so' from the 2 object files.

$: ld -shared avl.o avl_wrap.o -o _avl.so

The dependencies and actions are quite clear now.


Typing in these commands time and again would be a tedious and ineffective job for anyone. We could automate the whole process by writing a file called Makefile and use the 'make' utility.

The Makefile for performing the above steps would be as follows:



A Makefile has the following format.



Its important to note that the 'ACTIONS' line begins with a TAB as it is a part of the syntax of a Makefile. Anything other than TAB would be harmful.

Lets check out how things work out.

$: make

This would cause GNU make to start executing the commands in Makefile.GNU make starts from the very beginning of the Makefile. The first set of 'TARGET-DEPENDENCIES-ACTIONS are checked in.

The TARGET is '_avl.so' : The DEPENDENCIES are 'avl.o and avl_wrap.o' and the ACTION that needs to be performed is

ld -shared avl.o avl_wrap.o -o _avl.so

But at present 'avl.o' and 'avl_wrap.o' are not available. To Generate them the next set of the Makefile is to be checked. The same problem exists there as well . Hence the 3rd set in the Makefile is reached where the DEPENDENCY is 'avl.i' which exists at present. Hence the action

swig -python avl.i

is executed , the target 'avl_wrap.c' is generated .
Now the second set in the Makefile can be compiled followed by the compilation of the first set. The procedure that takes place here is recursive .All the three actions are executed , the TARGETS are generated from the ACTIONS and DEPENDENCIES and finally we obtain '_avl.so'.

You could see another line in the Makefile that has not been mentioned upto now.
make remove
make remove is the TARGET and the ACTION that needs to be performed is
rm avl.o avl_wrap.o avl.py _avl.so avl_wrap.c avl.pyc

$: make remove

will remove all the unnecessary files in the directory when you are planning to start from the beginning.

If you would like to have a test on the intelligence of 'make' , you would be pretty surprised.

Lets deal that case with an example as well.

DO:

$: swig -python avl.i

We have executed the first command manually.
Now do:

$: make

and you will find that make executes only the other two commands that is included in the Makefile.
This again shows the recursive nature of the make process. The Makefile is read from the top. On reaching the second set , GNU make realizes that both the dependencies 'avl.c' and 'avl_wrap.c' are available and executes the ACTION to produce the TARGET 'avl.o' and 'avl_wrap.o'.

Now once again do
$: make

You would get a message as follows:
make: `_avl.so' is up to date.

This again brings to the fort-light the power of make. The final target '_avl.so' has been found to be 'up to date' and hence there is no question of having to execute the commands in the Makefile . GNU make, Richard Stallman and Rolland Mcgrath's creation, has recognized this.

SWIG(Simplified Wrapper and Interface Generator).

Scripting languages like python presents a lot of ease to the programmer while coding , but the fact remains that there are certain tasks that would screw you up when attempted in Python. So the coding is done in a more flexible language like C and the modules are imported in Python. SWIG is a tool that is used for extending your C programs into python and make the functions callable from Python.

Here we discuss how to import a C module into Python using SWIG.
Installing SWIG in your system ,if you haven't already, is the first task.

$:apt-get install swig

would do that for you.

Now its better you create a directory for the entire purpose and setup yourself within it.
Consider you have a C file ,avl.c , as our example (Avl is a height balanced Tree ,avl.c is an implementation of such a tree.) You could download the source code for avl.c here.

Our first step is to create an interface file 'avl.i' for setting up the interface. 'avl.i ' consists of the declarations of the various functions and global variables that are used in the file 'avl.c' and are prefixed with 'extern'.

%module avl

%{

extern struct node *root;

extern struct node *p;

%}


extern void insert(struct node* move,int item);

...
...
...
...

The 'avl.i ' file would like as above:
Now we have two files in our directory ,

avl.c & avl.i

This is all that we have to code for the task of extending a C module in Python. Now its all about SWIG.


Lets move further: Do the following.

$:swig -python avl.i

now have have a look into your directory and you will find two more files there .

avl.py & avl_wrap.c
avl_wrap.c is the wrapper file that has been created for the purpose of extension . Wrapper functions act as a glue layer between languages.

$: gcc -c avl.c avl_wrap.c -I /usr/include/python2.5/

You could now see 2 more files present in your directory.
avl.o & avl_wrap.o

These two are the object files that have been created for avl.c and avl_wrap.c respectively.

$: ld -shared avl.o avl_wrap.o -o _avl.so

This is the last thing you need to do before you could use start using your C module in Python.
Check your directory and you could see a new file , '_avl.so'. This is the shared object file that has been created .
If you create a make file for these , then obviously you wont have to go doing these tasks repeatedly.
Now ,the python module corresponding to the C module avl.c has been created which means that now you could start using it.

$: python

>>>import avl
>>>avl.my_insert(10)
>>>avl.my_insert(20)
>>>avl.traverse(1)

The source code can be downloaded here.