container_of()

/**
 * container_of - cast a member of a structure out to the containing
 * struct
 * @ptr: the pointer to the member.
 * @type: the type of the container struct this is embedded in.
 * @member: the name of the member within the struct.
 *
 */

Simple Version:

#define container_of(ptr, type, member) ({ \
 (type *)( (char *)(ptr) - offsetof(type,member) );})


Linux Version with type safety:

#define container_of(ptr, type, member) ({ \
 const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 
(type *)( (char *)__mptr - offsetof(type,member) );})

Lets first analyse simple version with an Example:

struct student {
    char name[20];
    int roll_no;
    int course_code;
    int marks;
    struct list_head student_list;
};

struct student stu;
uint32_t *pMarks = &stu.marks;
struct student *pStu = container_of(pMarks, struct student, marks);
if (pStu == &stu) // True

Can you get address of stu variable using pMarks ?

Yes, Just subtract distance between start of struct to marks variable(20 + 4 + 4) from
pMarks : pMarks – (20 + 4 + 4) is equal to &stu
if we ignore padding and alignment. This explains the subtraction operation in

(type *)( (char *)(ptr) - offsetof(type,member) .

offsetof()

So now we have to find a way to calculate the offset of a variable in struct.
You must have known that every process has its own address space and starting address of
this address space starts with 0.

Process Address Space Example.

As you know we can type cast any address without caring what is stored inside. For example.

char buffer[20];
struct student * pStu = (struct student *)buffer; //valid

Zero Pointer Derefrence.

if base address of buffer is starting with 0x0000 then the address of marks will be equal to (0 + offset) => offset. so &marks is equal to offset of marks in the struct student. But no buffer can start with 0 address that is reserved for code. But we can typecast constants also same as buffer so there is no problem in typecasting 0 itself.

This offsetof macro does same thing as we discussed to calculate offset of a member variable in 
 struct.

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

offsetof(struct student, marks) => &(((size_t)(struct student *)0)->marks)

 

Now Lets Focus on Linux version of container_of():

why do we need an extra complicated line if this simple version works fine. Lets first discuss about compilation warning about incompatible pointer assignment.

 

int a;
char *str = &a; //This line will give compilation warning.

 

So If someone passes mismatched type and members in container_of(ptr, type, member) Compiler

 

will give warning and people can correct it at compile time otherwise such mistakes can create bugs.

typeof()

type x; typeof(x) gets replaced with type. For example :

int a;

typeof(a) b = 10; //Equivalent to int b = 10;

Conclusion

#define container_of(ptr, type, member) ({ \
            const typeof( ((type *)0)->member ) *__mptr = (ptr);

            (type *)( (char *)__mptr - offsetof(type,member) );})

conainer_of(pMarks, struct student, marks)

=>

const typeof(((struct student *)0)->marks) *__mptr = (pMarks);

(struct student *) ((char *) __mtr - offsetof(struct student, marks));

=>

const struct student * __mptr = (pMarks);

(struct student *) ((char *) __mtr - offsetof(struct student, marks));

If you have doubt about there two lines in macro with semicolons so which one will be

returned.

int a = ({int x = 4; 5;});
printf("a == %d", a);

Output: a == 5

Red Black Tree

Difference of height of leftSubtree and rightSubtree should not be more than 1 for each node in the tree.

Pseudo Code: 
LeftRotate(node x) 
1   y = right[x]                   //Set y 
2   right[x] = left[y]           //Turn y's left subtree into x's right subtree. 
3   if left[y] != NIL: 
4        then parent[left[y]] = x 
5   parent[y] = parent[x]     // Link x's parent to y. 
6   if parent[x] == NIL: 
7        then root = y 
8   else if x == left[parent[x]] 
9        then left[parent[x]] = y 
10 else 
11     right[parent[x]] = y 
11 left[y] = x                       //Put x on y's left. 
12 parent[x] = y

Pseudo Code: 
RightRotate(node x) 
1   y = left[x]                    //Set y 
2   left[x] = right[y]            //Turn y's right subtree into x's right subtree. 
3   if right[y] != NIL: 
4        then parent[right[y]] = x 
5   parent[y] = parent[x]     // Link x's parent to y. 
6   if parent[x] == NIL: 
7        then root = y 
8   else if x == left[parent[x]] 
9        then left[parent[x]] = y 
10 else 
11     right[parent[x]] = y 
11 right[y] = x                    //Put x on y's right. 
12 parent[x] = y

Gnome Sort

Logic of this sorting algo same as insertion sort, array at left hand of current position during sorting
is sorted and if element at current position violating sorted order then swap it with
next element on left side and keep on doing till it reaches its correct place.

In insertion sort we use two loops, but here with simple trick we avoided inner loop.
Here this single loop increments and decrements “i” based on the current element is in expected
order or not, and achieves same functionality and behavior as insertion sort.

Cons: In insertion sort after putting current element at proper place in left side sorted array outer
loop start from where it left, but in gnome there is only one iteration variable so it has to increment
i as many times as it decreased to come back again at position from where i started decreasing.

Pros: Less number of line, easy to remember and easy to write.
So complexity is also same as insertion sort: best case O(n) Worst case: O(n^2).

public class Main {

1    public static void gnomeSort(int[] arr) {
2        for (int i = 1; i < arr.length; ) {
3            if (0 == i || arr[i - 1] <= arr[i]) { //in expected order.
4                i++;
5            } else {
6                //swap
7                int temp = arr[i - 1];
8                arr[i - 1] = arr[i];
9                arr[i] = temp;
10               i--;
11            }
12        }
13    }

    public static void main(String[] args) {
        int[] arr = {4, 6, 3, 7, 89, 2, 4, 12, 34, 90, 100, -1, 0};
        gnomeSort(arr);
        for (int x : arr) {
            System.out.print(" " + x);
        }
    }
}

Output:

-1 0 2 3 4 4 6 7 12 34 89 90 100

This Trie has Three words, BUDDHA, SUN and SUPER.

public classtrieNode
{
     trieNode[] childrenArr;
     Boolean isEndOfWord;
     trieNode()
     {
          childrenArr = new trieNode[26];
     }
     //methods ...
}

eg:
Considering Trie represented in Figure.
contains("sun")
  root   if (null != childrenArr[indexOf('s')]) True
   |
   s     if (null != childrenArr[indexOf('u')]) True
   |
   u     if (null != childrenArr[indexOf('n')]) True
   |
   n     if (True == isEndOfWord) True

  return True

contains("song")
 root   if (null != childrenArr[indexOf('s')]) True
  |
  s     if (null != childrenArr[indexOf('o')]) False
return False  

insert("buddy")
root              if (null != childrenArr[indexOf('b')]) True
/ \
b  s   at b node: if (null != childrenArr[indexOf('u')]) True
|  .
u  .              if (null != childrenArr[indexOf('d')]) True
|
d                 if (null != childrenArr[indexOf('d')]) True
|
d                 if (null != childrenArr[indexOf('y')]) False
|\
| \       y child is not present so add it.
h  y   ---added a y child at indexOf('y') with isEndOfWord True
|
a

insert("bud")
root              if (null != childrenArr[indexOf('b')]) True
/ \
b  s   at b node: if (null != childrenArr[indexOf('u')]) True
|  .
u  .              if (null != childrenArr[indexOf('d')]) True
|
d                 set isEndOfWord True

void delete(String str)

                  root
                    / \
                    b  s
                    |  |
                    u  u
                    |  |\
     end of word ---d  n p
                    |    |
                    d    e
                    |\   |
                    h y  r
                    |
                    a

Lets understand expected behavior of delete().

 contains("buddy") True contains("bud") True
 delete("bud")      This will set isEndOfWord False in in b->u->(d).
 contains("bud")    False
 contains("buddy")  True
 delete("buddy")    This will remove y node and free memory of node.
 contains("buddy")  False
 contains("buddy")  False
 contains("buddha") True
 delete("buddha")   It will remove all nodes from b->u->d->d->h->a.
 contains("buddha") False

Delete operation is tricky one and there are Three scenarios:

First Scenario: Deleting a word which is a prefix of other existing longer words.
eg: deletion of bud.
In this case we need to set isEndOfWord to Flase only.

Second Scenario: Deleting a word which shares a part of it with other words and one part is not shared by any other words.
eg: deletion of buddy, “y” is not shared with anyone so node “y” will be deleted.

Third Scenario: Deleting a word which does not share any char with other words in trie.
eg: we have deleted bud and buddy now buddha is not shared with any word.
delete(“buddha”) This will delete all nodes b to a.

Continue reading “Trie : Data Structure” →

Precise Square Root using Newton Raphson Method.

We want to calculate square root n.

Lets find derivative of our equation.
f ‘(x) = 2x

Simplify the Equation:

Xn+1 = Xn – (Xn^2 – n) / 2Xn

Xn+1 = (2Xn^2 – Xn^2 + n) / 2Xn

Xn+1 = (Xn^2 + n) / 2Xn

Xn+1 = (Xn + n/Xn)/2

take guess value of Xn lets say 1,
and keep iterating to calculate Xn+1
and stop when (Xn+1 – Xn) <= required precision.

Pseudo Code:

float square_root(int n)
{
    float x = 1; //guess value.
    while (true)
    {
        float lastX = x;
        x = (x + n/x) /  2;
        if (abs(x - lastX) <= 0.00001)
        {
            break;
        }
    }
    return x;
}

public class Solution {
    public static double squareRoot(int n) {
        final double precison = 0.0000001;
        final double guess = 1;
        double x = guess;
        double lastX;
        do {
            System.out.println(x);
            lastX = x;
            x = (x + n/x)/2;
        } while ((Math.abs(x - lastX)) > precison);
        return x;
    }

    public static void main(string[] args) {
        System.out.println(squareRoot(2));
    }
}

Output:

1.0
1.5
1.4166666666666665
1.4142156862745097
1.4142135623746899
1.414213562373095