Inline Function

In C, if a particular function used has only a few lines in its body, and if the optimization level is set to 03 (preferably), some unexpected changes can be observed about how gcc handles this function.

What the compiler will do is that it replaces the call for this function, with the actual code of the function, called inlining.

The limit on the number of lines below which inlining is performed, strictly depends upon the gcc heuristics.

This is not all. In  the extreme case, if the small function mentioned above only does something like calculating a value after taking an input, then gcc will evaluate the function call, calculate the value, and directly paste it in the program instead of the function call itself.

Sweet, isn’t it?  

Test Program



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

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

    less opt1.s


The assembly code is:
    sqr:
            subl    $16, %esp
            movl    20(%esp), %eax
            imull   20(%esp), %eax
            addl    $16, %esp
            ret
          
    main:
            pushl   %ebp
            movl    %esp, %ebp
            andl    $-16, %esp
            subl    $16, %esp
            movl    $10, (%esp)
            call    sqr
            movl    %eax, 4(%esp)
            movl    $.LC0, (%esp)
            call    printf
            leave
            ret
          
On optimization,



The new code is:

    sqr:
            movl    4(%esp), %eax
            imull   %eax, %eax
            ret
    main:
            pushl   %ebp
            movl    %esp, %ebp
            andl    $-16, %esp
            subl    $16, %esp
            movl    $100, 4(%esp)
            movl    $.LC0, (%esp)
            call    printf
            leave
            ret

Linux From Scratch

“Linux From Scratch (LFS) is a project that provides you with step-by-step instructions for building your own custom Linux system, entirely from source code.”

Homepage is : http://www.linuxfromscratch.org/ .

BINARY TREE

A binary tree is a tree data structure in which each node has atmost two child nodes. The child nodes may contain references to their parent nodes. There is a root node, which has atmost two children but no parent.

According to Graph Theory, a binary tree can be also said to be a connected, acyclic graph data structure, with a maximum degree of three for each vertex.

TERMS ASSOCIATED WITH A BINARY TREE

• The root node of a tree is the node with no parents. There is at most one root node in a rooted tree.
• A node with no children is called leaf node.
• The depth of a node is the length of the path from the node to the root. All nodes at the same depth are said to be in the same level. The root node is at level 0.
• The height of a tree is the length of the path from the node which has the highest depth, to the root node.
• The children of the same parent are called siblings.
• A node is an ancestor of another node, if it comes in the path traced from the other node to the root.
• A node is the descendant of another node, if it is the child of the other node, at some level from it.
• The size of a node is the number of descendants it has including itself.

1. A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. (This is ambiguously also called a complete binary tree.)
2. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
3. A balanced binary tree is where the depth of all the leaves differs by at most 1. This depth is equal to the integer part of log2(n) where n is the number of nodes on the balanced tree.

BINARY SEARCH TREE

A binary search tree is a binary tree in which the numerical value of the data field of the left child is lesser than that of the parent, which is in turn lesser than that of the right child. In short,
(data of left child) < (data of parent) < (data of right child) [numerical value of data is taken]
For example,

Here, in both the trees, data is input in the same order, i.e, 34, 43, 56, 21. Searching in the binary tree is evidently very easier in the BST, hence the name binary search tree.

Each node in a binary search tree can be represented by a structure in C, created with the ‘struct’ keyword, typically named ‘node’. In the most simple case, the data field is taken as an integer. There are three pointers associated with each node, whose typical names can be parent, lchild and rchild, of type ‘struct node’ itself. These three pointers also make the structure ‘node’ a self-referential data structure. Obviously, the parent pointer in the structure representing the root node, will be NULL.

The definition for each node will be:
struct node {
int data;
struct node *parent;
struct node *lchild;
struct node *rchild;
};

The names for the fields are self explanatory, and arbitrarily taken.
(The ‘parent’ pointer points to the parent of a node. It is necessary in an AVL tree only.)

BASIC FUNCTIONS FOR THE BST

Since the binary search tree is a dynamic data structure, the malloc() and free() C standard library functions are used to allocate memory for new nodes while insertion, and to deallocate memory while deleting nodes, respectively. Only the following basic functions are needed to implement the full functionalities associated with a BST.

Constructor -> For creating a new node in the BST
Insert -> For inserting the new node into the BST and
                                           setting up the links
Traverse Inorder -> For inorder traversal through the BST
                                           (for each node, print LnR)
Traverse Preorder -> For preorder traversal through the BST
                                           (for each node, print nLR)
Traverse Postorder -> For postorder traversal through the BST
                                           (for each node, print LRn)
Find                        -> For returning the node whose data field is the
                                            given numerical value
Delete -> For deleting a node from the BST.

where ’n’ denotes the current node, ’L’ the left child, and ’R’ the right child. (thanks to Shijith for this one …)

N.B. For deletion, if the node is a leaf, just delete it. Otherwise, if the node
         has a right child, replace the node with its successor node in the
         inorder representation of the BST. Else, replace the node with its
         predecessor in the same inorder representation.

BALANCING A BST

The BST seems efficient in searching for a particular data. But it is not so always. When there are large number of nodes, there is the possibility that a devastating situation, as shown below, may occur.

In the second BST, data was input in the order 21, 20, 34, 37, 43, 56. Hence, the structure. According to the BST terminology, a structure like this is said to be unbalanced.

N.B. A BST is said to be balanced, when the depth of any two leaves in
         the BST differs atmost by 1. Also, a balanced tree will be
         theoretically more efficient in all situations, while an unbalanced tree
         will be not.

Why is an unbalanced BST inefficient? For mainly two reasons.
1) The time complexity for searching some data values becomes much
    greater than expected. For example, in the first BST, 43 can be found in
    two steps of traversal. In the second one, it takes an unexpected 4 steps.
    For very large BSTs, the time complexity increases drastically.
2) The lesser the number of levels in the tree, the more efficient the storage.
    When operations like deletion are performed on large BSTs, there is
    a high possibility that the actual addresses of the nodes are spread out
    over a large area of the storage memory (secondary memory).

How to balance a BST?
There are many techniques available, but in all of them, the simple rule is to keep the difference between the depth of any two leaves atmost 1. The BST can be balanced at a particular point in time as desired, or it can be done while insertion into and deletion from the BST. Such BSTs that do “balanced” insertion and “balanced” deletion are called self-balancing binary search trees.

THE AVL TREE

The AVL tree is one of the many kinds of a self-balancing binary search tree. It was invented by G. M. Adelson-Velskii amd E. M. Landis.

Short Bio of the Inventors
G. M. Adelson-Velskii
Georgy Maximovich Adelson-Velskii, was born on 8 January, 1922 in Samara, Russia. He is a Soviet mathematician and computer scientist. Along with E.M. Landis, he invented the AVL tree (“AV” in “AVL” tree stands for Adelson-Velskii) in 1962.
In 1965, he headed the development of a computer chess program, which evolved into Kaissa, the first world computer chess champion.
He currently resides in Ashdod, Israel.

E. M. Landis
Evgenii Mikhailovich Landis, was born on October 6, 1921, in Kharkiv, Ukrainian SSR, Soviet Union. He was a Soviet mathematician who worked mainly on partial differential equations.  He studied and worked at the Moscow State University.
With Georgy Adelson-Velsky, he invented the AVL tree datastructure (“L” in “AVL” stands for Landis).
He died in Moscow on December 12, 1997.

The Technique

The BST can be easily remodelled into an AVL tree by adding some extra functions that perform balanced insertion and balanced deletion. Some other helper functions that perform some trivial tasks are also needed. The balancing is done by a technique called “rotation”.

What is rotation?
It can be best illustrated only pictorially. There are two ways to rotate.

i. Right Rotation                    

What happened simply looks as if:
1) node 34 was kept fixed as a “pivot”.
2) 34’s right child was rotated clockwise about the pivot (node 34 here).
3) there is a change in some links of 34 and 43.

On generalising,

ii.Left Rotation                    

What happened simply looks as if:
1) node 37 was kept fixed as a “pivot”.
2) 37’s left child was rotated anti-clockwise about the pivot (node 37 here).
3) there is a change in some links of 21 and 37.

On generalising,

N.B. In both cases, the structure of the original BST will be changed to
         that after the rotation. The rule for a balanced tree will be obeyed
         in both the new structures.

Above mentioned are the two ways to perform rotation. When and how many times to perform them depend on the actual arrangement of the nodes in the BST. There are four distinguishable imbalance patterns which occur repeatedly in a BST strucuture. These four patterns are recognized by finding out the “balancing factor” for each node. According to the balancing factor thus obtained, the proper sequence of rotations can be initiated.

What is the balancing factor?
For any node in the BST, its balancing factor is given as:
BF (node) = (height of its left subtree) - (height of its right subtree)

(It can be taken the other way round too, but appropriate sign changes have to be made in the balancing factor of nodes.)  
BF (node 43) = +2
BF (node 34) = +1
BF (node 21) = +1
BF (node 20) = 0 (leaf)

The balancing factor of any node in a balnced BST will be an integer, in the range -1 to +1, including them. If the balancing factor of a node is found to be -2 or +2, it indicates that the BST is unbalanced at that node.
Next, the proper imbalance pattern is identified. Once it is done, the appropriate sequence of rotations are performed.  

THE FOUR CASES OF IMBALANCE

For any number of nodes in a BST, only 4 patterns occur repeatedly. They are classified as the four cases according to which different sequences of left or right rotation or both must be performed. The four cases are:

    LEGEND:
1 - node with BF +2 or -2, indicating need for rotation
parent              - the parent link of node 1
lroot and rroot - the nodes which get “rotated” during each of the left
                             or right rotations respectively
pivot                 - the pivot node in a rotation

From the above figure,
LEFT - LEFT CASE : BF of a node is +2, BF of its left child is +1 or 0
LEFT - RIGHT CASE : BF of a node is +2, BF of its left child is -1
RIGHT - RIGHT CASE : BF of a node is -2, BF of its right child is 0 or -1
RIGHT - LEFT CASE : BF of a node is -2, BF of its right child is +1

Also,
LEFT - LEFT CASE : 1 right rotation
LEFT - RIGHT CASE : 1 left rotation, then 1 right rotation
RIGHT - RIGHT CASE : 1 left rotation
RIGHT - LEFT CASE : 1 right rotation, then 1 left rotation

AVL-SPECIFIC FUNCTIONS

Balancing Factor -> Finds the balancing factor for the given node.
Left Rotation -> Perform left rotation, given a “pivot” and “lroot”.
Right Rotation -> Perform right rotation, given a “pivot” and “rroot”.
Balance -> Check balancing factor of given node. If the tree is
                                       unbalanced at this node, identify the imbalance
                                       pattern and perform rotation.
Balanced Insert -> Insert a new node, then travel from its parent to the
                                       root, calling Balance() for each node in the path.
Balanced Delete -> Delete the node, then travel from its parent to the
                                       root, calling Balance() for each node in the path.
                                       If the deleted node was not a leaf, the path starts
                                       from the replaced node itself.
                                    
Special Conditions to be Checked while Retracing in Balanced Deletion

If at some node, its BF is:
+1 or -1 : it indicates that the height of the subtree has remained unchanged,
                and retracing can stop.
0            : height of the subtree has decreased by 1, and retracing needs to
                continue.
+2 or -2 : needs rotation.
                If BF of the node after rotation is 0, continue retracing since
                height of this subtree has again decreased by 1.
N.B. In insertion, if the BF of a node after rotation is 0, it indicates that the
         height of that subtree has remained unchanged, contrary to the similar
         situation while deletion.

CONCLUSION
Once the above extra functions are defined, the BST will be remodelled into an AVL tree.

Computers are very fast machines. But the computation time
also depend on the algorithm we choose. It can happen that
if a proper algorithm is not chosen, it may take a very long
time for execution.

On writing a simple recursive fibonacci generator function for
the nth element, fib(n), we will get fine results, but only for low
values of n. This is because fib(n) has exponential complexity.
Such functions grow very fast, so fast that even for small
values of `n’ (where `n’ is the size of the input), our program
will take a long time to finish.

Memoization is the process by which we speed up the situation.
The underlying principle is to create an associative array, say  
dict, which contain keys = n, and values = fib(n). Each time a
fib(n) is called, the associative array will be checked whether it
contain the key ‘n’. If yes, just return dict[n]. Otherwise, create
a new key: value pair for dict. Thus, the number of recursion will
be drastically reduced, with this look-in-the-lookup-table policy.

Ofcourse, memoization is an upgrade to time compplexity, but
will consume space.
The implementation in Python looked like:

def memoized_fib(x):
if dict.has_key(x):
return dict[x]
else:
dict[x] = fib(x)
return dict[x]

def fib(n):
if n == 0: return 0
elif n == 1: return 1
else: return memoized_fib(n-2) + memoized_fib(n-1)

 dict = {0: 0, 1: 1}


In Python, the recursion limit is fixed by the interpreter itself. It can
be found in:
sys.setrecursionlimit(<limit>)

Now, set a very high limit, and run the code. If its high enough, u will
deplete the stack memory size (8 MB) of the C backend of your Python
virtual machine, leading to a segmentation fault there, which is
propagated back to your Python interpreter, crashing Python itself!

Well, I must say, simplicity and brilliance is what a FOSS meet will be
all about, if you watch the proper people. For the National Conference
on Free Software And Education, September 10-12, 2010, me and
my four friends Prasanth, Remya, Sumith and Sunil geared up with a handy electronic instrument called the Phoenix(aptly named), and barged in
through the front gates. We came to know about the Phoenix from our
teacher, Mr. Pramode C. E., and beacme interested. This interest made
us to take it to the FOSS meet and do a few tricks with it, with guidance
from Pramode Sir. Some mistakes and pitfalls happened too.

First of all, whats ’Phoenix’? Its an electronic gadget with an Atmel
ATmega16 mcu inside it, with hardware peripherals including a DAC, ADC,
digital I/O pins, comparator, waveform generator, amplifier, etc,
necessray to build a simple circuit. The point? The whole Phoenix board
is set up such that a large variety of experiments from Physics can be
conducted with ease. Highly accurate measurements are thus possible.
Experiments include a simple charging-discharging cycle of a capacitor,
to alpha particle radiation measurement from a radiative source. Plus,
the board runs in C, with the computer front-end being Python. Hows
that? An ‘open hardware’, it may be called, maybe the first of its kind.

Coming back, the first day was at Tagore Centinery Hall, Calicut Town.
A banner highlighted by the face of Richard Mathew Stallman a.k.a
R. M. S. greeted us. Volunteeers and coordinators from NIT Calicut, gave
a brief picture of the schedule. Understood that, only the inaugral
ceremony with a keynote address from R. M. S. will be arranged that day.
At the far end, some tables were set up, and many free software users
were vigorously working with their laptops.

We were to see Mr. Sasikumar, the ‘R. M. S.’ of Kerala. Till then, we
were just standing their groping with our belongings, not knowing what
to do. Once we met him, the situation changed abruptly. We were greeted
with a warm, enthusiastic, polite smile, and ushered to the expo area.
The volunteers were asked to allot a table for us. Then, we became a
part of the event.

Till the original R. M. S. arrived on the scene, the expo continued. A
few people came to visit the ‘stalls’. There were students, enthusiasts,
Physics teachers, and others who came to see what Phoenix was. There
were Phoenix users among them too, who wanted to see if any newer
features have been developed for the Phoenix.

Finally, I learned that R. M. S. had arrived, and has gone inside the
Hall, while my back was turned. Soon, everyone got inside, and I saw
the guy for the first time. I was seeing a cute-in-an-odd-kind-of-way,
big, living genius. I stared at him for long, with only one thought in
mind. I had to hear his voice too. Meanwhile the guest were asked to
get on stage. R. M. S. chose a side chair, but was ushered to the
center of the dias. Later, I saw him, kneeled down on his left leg,
drinking water from a bottle, kept on a table infrot of him. Well,
everything he did seemed cute and nice. A few moments later, he simply
yawned, and I couldnt help but smile.

There were to be about 8 more felicitations before the keynote address
from R. M. S. We couldnt wait that long, we had to get to our staying
places. We reached NIT Calicut, next day by noon. We arrived before for
the lunch session and quickly set up the table. Many people came to us
during the break, to know about Phoenix. There was a Physics teacher,
who believed Physics has to be ‘touched and learned’. But i had a
counter-point that Phoenix could do things otherwise impossible in a
lab. One particular student was so excited to hear about Phoenix,
because he had been looking around for such a low cost instrument for
obvious purposes. There was a table for IIT Bombay, who had come with
their project to create spoken-tutorials for all the major free
software applications available now. Shortly after the lunch session
was over, we packed our things and got out, because we had to reach
our shelters in the same day itself.

Mistakes:
1. I didnt take photographs all through the event.
2. Didnt bring a banner or charts (showing the details of Phoenix) for
    display purposes.
3. Didnt bring a better experiment apparatus, perhaps it could have
    gained more attention.

Pitfalls:
1. We totally lost control of time. We were running for shelter to
    sleep, running to be present at the meet.
    In a nutshell, we couldnt sit for a single talk.

What we learned:
1. What to expect and what not to in a FOSS meet.
2. The feeling when someone like Dr. Prabhu Ramachandran whizzes past
    you, and you continue to stare blankly, unable to utter a single word.
3. How it is to bring ‘something’ to the meet and to bring ‘some real
    thing’ to the meet, from the fact that, we had also brought along an
    elementary study report on the TinyPy Virtual Machine v1.1.

In Python, ”classes are objects too”. Let me clarify.

Let me define a sample class.
>>> class abc: pass
>>> abc
<class__main__.abc at 0xb76e341c>
It indicates that in Python, classes are not abstract!
They too take memory space.


Lets explore further.
>>> m = abc
>>> m
<class__main__.abc at 0xb76e341c>
>>> m = abc( )
>>> m
<__main__.abc instance at 0xb76e298c>
i.e, in Python, both classes and their objects are concrete.

Now,
>>> abc.p = 10
>>> abc.p
10
Classes can act as objects, as already told above!


Still further,
>>> m = abc()
>>> m.p
10
>>> m.q = 20
>>> abc.q
20
What exactly happened here?


Things to understand:
1. Here, “.” works as a search operator 
2. On querying m.p, first checks if there’s a p attribute in m
3. If not, automatically finds out type of m, then searches for p there.
4. The p attribute here, actually belongs to abc, not m.

1. Data Types
    Python is a good example for a dynamically typed programming
    language. It means that, there are no need for type declarations. Any data
    can be initialized directly and the corresponding type will be automatically
    assigned and understood by the Python interpreter.
    >>>a = 12
    >>>c = ‘hello’
    
    C is a statically typed language. We need to first declare the variable.
    Only then are we allowed to define it. The C compiler will understand
    the type of the data and assign suitable storage space only when we
    declare it.
    $ int a, b=2;
    $ char c = ‘h’;
    $ a=10;

2. Array Indexing
    The mechanism of array indexing in C is as follows:
    array index is given by ’base address + offset’
    Therefore, how large be the array length, C compiler only needs to add
    the offset to the base address to access the required array location.

    In Python, the situation is different. It is compulsory for its interpreter to
    follow 2 rules:
    i. check whether current array index is out of bound
    ii. access that index location

    In short, its even possible to go out of bound in C. Garbage values in
    that locations will be returned. Thats all. But Python is very
    conservative. You specify an array length, you better stay inside it. No
    bending rules.

    Finally, the outcome. As you can guess, array indexing in C is blazing
    fast. If we work on the same array in Python, we may have to wait.
    Maybe really long.

3. Dynamic Allocations
    On the outset, i take the privilege to assume you know what dynamic
    allocations are.

    They are very troublesome in C. Simply speaking, if you do an  
    malloc(), then use the same pointer to do another malloc(), you will
    lose control of the firstly allocated memory block forever. You can’t
    use it anymore. So be wary. Thats all you can do.

    For this matter, Python is awesome. It will take care of such
    unhandled allocations of memory automatically. Its called garbage 
    collection or automatic memory management. We can say that, each
    allocated block has a reference count, which has the value of the
    number of pointers currently pointing to that particular block. This
    count, is incremented or decremented automatically and accurately.
    There is one consequence, though. The compilation time will be 
    non-deterministic because we cant predict when and how Python
    attempts this.

4. Indentation
    In short, indentation is compulsory in Python. The intermezzo coding
    style proposes 4 spaces. While the Google coders are seen to be using
    only 2.
  
    In C, it is just the other way. Here, it is only a matter of user 
    readability. The C compiler doesn’t care.

5. Functions
    In Python, all the functions, both built-in and user-defined, are first 
    class. A function is said to be first class, if it can be treated just as a
    variable. It means that, in Python, functions can be passed as
    parameters, and returned too. Coool, eh? If so, how about knowing
    that this concept can be extended to creating higher order functions?
    They are functions which operate on other functions, e.g. integration,
    differentiation. Three built-in higher order functions in Python are
    map, filter and reduce.

    In C, its just the contradictory. Functions are functions, variables are
    variables. No mixing up.

6. Pointers
    They are the most awesome weapon in C. You can do powerful things
    with them, that can be either only dreamed of or very hard to
    accomplish in other languages. But as powerful they are, be very
    careful with the memory manipulations you can do with them, or else
    you are a goner.

    They are not as such implemented in Python. But some similarity can be
    felt in some operations that can be performed. For a brief idea, refer to
    “Pointers” in Python.

7. Assignments in Expressions
    In C its possible to write,
    $ int a, b=1;
    $ if ((a=12)>b)
    $         print (” %d \n”, a+b);

    Well, its not possible in Python. Only logical equality (==) can occur
    inside an expression.