Algorithms and Data Structures : Sorting

1) Bubble Sort 

5,4,19,3,0,2,7

Theory : 1) Start from LHS and compare each number to its adjacent number.  Exchange
               the two numbers if LHS number is bigger than RHS.
             
               2) If N is number of value to be sorted, then doing  Step 1) for N times will sort the values.

Time Complexity : N^2.
Space Complexity : No additional space is required.

Easy to code and better approach when sorting N < 50.

Optimization : We can check if at same stage , the number of exchanges are zero we can stop at that point.

2) Counting Sort

5,4,19,3,0,2,7

Theory:  1) For each number store , how many times that number is coming in new array

count[0]=1;   count[7]=1;
count[1]=0;   count[8]  till count[18]  is 0;
count[2]=1;   count[19]=1;
count[3]=1;
count[4]=1;
count[5]=1;
count[6]=0;

now since we know, how many times a particular number is coming. We can now output sorted number based on count values.
0,2,3,4,5,7,19

Time complexity is 0(K)  where K is the largest number.
Space Complexity is 0(K) where K is largest number.

This approach can be used , when the diff between smallest and largest number is small.

Ex:  100,50,4,1

now to sort these 4 numbers : Bubble sort will have at max - 16 sec, if we assume 1 sec for each compare.
But Counting sort will take 100 sec, since we have to fill count array.

but for  10,6,4,1,2,8,9,5,3,7

bubble sort  100 sec.
count 10 sec.


But since in real life we seldom knows the input values, we take approach which doesn't fluctuates much.

3) Selection Sort

In this sort, select the biggest element / smallest element and place at the end/front.
Continue to this for N times and array will be sorted.

Time Complexity : O(N^2)
Space Complexity: None , no additional space needed.

It is never used, as it doesn't provide any improvement over bubble sort

4) Quick Sort

69 10 30 2 16 8 31 22

The strategy behind this is to divide select a pivot( one element). In logN time we can find pivot correct value.
Doing this for each N element we can place it in correct place.

Select one element ( we select the middle element of given numbers). Then check its LHS to number greater than this. If we find such number, stop at that.

Then at RHS of this element , find number smaller than this.  If such number exist, swap them.

Else we will continue to do this, untill we reach same number from both LHS and RHS.
The position of this number is the correct position of our PIVOT element.

We will exchange PIVOT number with this, after that , we will do same process for our left subset and right subset , w.r.t to out PIVOT ELEMENT.

Time Complexity : O(nlogn)
Space Complexity : Since we use recursion for this, lot of space will be used by system.

This can be used when there is less constraint on memory and more constraint on time.

But the process of merge sort can be used to find  correct location of some person or how many students have marks more than a particular marks or less than that when marks are given in unsorted manner.


Timing Difference :
> For a random input of size 124 inetgers.

bubble sort on average : 120 * 10^(-6) sec
merge  sort on average : 45 * 10^(-6) sec

merge sort is 3 times faster. 

5) Insertion Sort

There isn't much difference between Selection Sort and Insertion Sort.
 In selection sort, we select smallest number and place it at the front and then from N-1 numbers, we can select the smallest.

In insertion sort, we grow our list by 1 number at each step.
In 1st step, we have only 1 element and it is sorted, as it is only element.
In second step our list size is 2 , and we find correct position of 2nd element.
In third step our list size is 3, and now we find correct position of 3rd element.

Time complexity is O(n^2).
Space Complexity : No additional space is needed, operation is done on same input array.

Quicksort can be run parallel, as after each step, we have two subset which we have to sort.
Whereas in all the others Sorting so far, we cannot divide our input.

 
Bubble sort goes well with ARRAY. In LL, it will be difficult to traverse LL.
Insertion sort goes well with LINKED LIST, it will be overhead to move array elements to make space for each insertion.
Selection Sort again is better with Array, as with LL have to break and make connection.
QuickSort is better with Array.

OS : Multithread

Recently, I have one doubt over process.  I tried to understand it, but as it mostly happens to understand it I had to check something else.


https://computing.llnl.gov/tutorials/pthreads/


When we run a program, a PROCESS is created. Now each PROCESS is actually a default THREAD, which requires ONE CORE of CPU.

All this doubts came since now CPU are multiprocessor and multicore.

So when we have octa-core CPU, that means it has 8 cores. Now on this CPU we can run 8 threads at same time.

Now if no PROCESS is creating any threads, then we have 8 PROCESS running at same time on this CPU.

Now each PROCESS has its own ADDRESS SPACE.  But THREADS of same PROCESS share the ADDRESS SPACE of default THREAD of the PROCESS.


But with SINGLE CORE CPU, even when we have multiple THREADED program written, THREADS will be running one after another.

Now if we have put our THREAD into sleep or if it is waiting for some resource, then CPU will process some other THREAD based on PRIORITY.


Also please note, when you are making a multithreaded program, then you divide your FUNCTIONALITY into SUB-FUNCTIONALITY and assigns each SUB_F  to threads.

Each THREAD entry point is call to that FUNCTION.


Use Case :

1) You have to guess a word which is 4 letter and starts with W and ends with R.  Now I will give you one such word with all four letters. You have to see how fast you can reach it.

Now with multi-core CPU, we can use both CORE to work parallely to guess words.

This is when you have MULTICORE processor

2) In case of SINGLE PROCESS which has two parts, one BACKGROUND/DATA PROCESSING and ONE FOREGROUND. In this case we don't want our FOREGROUND process to be slow because of BACKGROUND.

This is use case when you have SINGLE CORE processor.

Make a program in which one THREAD writes data to text file and one THREAD is printing loop count, and one thread is calculating fibonacci series.  See when you perform READ/WRITE operation does fibonacci program runs.



-----------------------------------------------------------------------------------------------------------------------

How does THREADS get scheduled ?

Can we call some THREAD from other task ? We have thread id, but is there any API to call THREAD from the thread id.

Does Modem uses THREAD ? if yes where and why

Algorithms and Data Structures : Index

The way you should go about learning algorithms ( IMO) is like below


Stage 1) Basic Data Structures

These are basic structures and used to store data. Not much operation can be done on these

Linked List
Array
Structures
Matrix ; N-D array

Circular Linked List
Double Linked List
String


Stage 2)  Advanced Data Structures

I have name them advanced, since these uses basic data structures and on top of that one these are built. Also algorithm/ predefined operations are associated with them.

Queue
Stack
Circular Queue
Priority Queue

Tree
Binary Tree
Bianry Search Tree
Huffman Tree
Parent Array
Heap

Set
Adjacency List
Adjacency Matrix

Suffix Tree and LCS array


Stage 3) Algorithms

Boyer Moore Algorithm
KMP Algorithm
Karp Robin Algorithm
String Compression : Brute Force and Huffman Tree
Dijkstra , Bellman-Ford , Floyd-Marshall
Subset, Permutation,Combination Generation - Brute-Force and Backtracking
Sorting Algorithm
Tree Traversal - Pre-order, Post-order, In-order
Graph Traversal - DFS , BFS
Prim , Krushal
String reversal

Stage 4) Solving Methods

Back tracking
Recursion
Iteration
Greedy Approach
How machine stores data
Maths
Time Complexity and Space Complexity
Memorization

C language : Index

I am realizing now the importance of Index, when I myself has to check which topics are covered and which not.


1.  Extern
2.  Static
3.  Memory Layout
4.  malloc, free, realloc
5. mulititasking, multithreading,multiprocessing
6. Pointers : function and void
7. File I/O.
8. Storage of unsigned and signed
9. Bits operation

LTE : Part 1 : Connection with the Network

How does UE remains connected to the Network in LTE


APN : Access Point Name

It identifies the PDN ( the packet data network ) to which UE will communicate .
APN also helps in identifying the type of service. ( default, mms, internet etc).

Check the APN settings of your phone, you will see in APN
 > type
 > IPv4/Ipv6

APN name will be  like  airtel.mnc078.mcc405.gprs


PDN is packet data network , which will provide that type of service ....MMS , internet , IMS

P-GW  is PDN gateway, which is last node of LTE network, it is gateway/server/computer which will provide the service promised by the APN which UE used.


PDN address : It is the IP address which UE has to get identity in the PDN network.


Now since LTE is only PS network, so you should always need connection with the some PDN.
Hence when we attach with LTE network for the first time, we will be activating some APN.

That APN is known as default APN.

Bearer :  It is name given to identify two end points in LTE network.

 EPS bearer : Between  UE and P-GW
 S5/S8 bearer : Between S-GW and P-GW
 E-RAB : Between UE and S-GW
 Radio Bearer : Between UE and eNB
 S1 Bearer : Between eNB and S-GW.


So now in brief, when you bootup

You will try to attach to network, and also try to get the default APN up.
Now when these two things are done , we are connected to network.

but as cellular technologies are mainly for moving devices, we will face problem, when our device has moved to other location.

Hence when we focus on LTE we focus on two parts.  SIGNALLING : this helps in keeping both UE and Network in contact.

Then is DATA part, which helps in moving packets from UE to Network and vice-versa.

We will see first SIGNALLING and then DATA part.

LTE : Part 0

LTE is  technology which provides more data speed then 3G and 2G. Also known as 4G.

Unlike 3G, it is only PS network.


Now any user who has used phone uses it mainly for

CALL, SMS , SS , DATA.

Now CALL is mostly CS. And since we were using LTE and it is only PS , we have IMS which provides CALL facility to user.

Now using IMS we can have SMS, and RCS ( RCS is rich communication service (like whatsapp))


So if you have a IMS module and PS connection ( LTE mobile phone, desktop, laptop) you can connect to the outer world easily.

One more important thing is needed, which is SIM , this is simply needed so that OPERATOR can provide us secure service and offcourse they will earn money.


Now in following post we will try to see  how PS connection is provided using LTE. 

Things we will cover will be

1) APN
2) Security
3) Lower Layer working
4) Connection with Network

Tizen : Will i be able to make some App :)

Pheww.....Now I have also started to learn Tizen ..because all the DS and algos I am learning where to put them ...let see if i can get something good from the TIZEN.


It is OS from my own company .....yippy    Happiness ends there only, since I don;t get a chance to work on it.

Now at very basic level Tizen apps are divided into two parts

1) Web App : which can be developed using JavaScript and doesn't needs telephony functionality
2) Native App : which are much stronger and uses C++. These app uses telephony functionality


We will start with basic app, since as I heard it is easier to make.

The most basic app is the one which displays time ...you can find it in tizen SDK when you will start your first project.


Basically for WEB APP,

we have  JS folder in which our javascripts will go
then we have image folder in which all the images which we want to use in our app will be kept
then we have one index.html  in which we can define basic of app.

We will need some basic of html,JS to work.


In next post , we will try to develop some  WEB APP.

Algorithms and Data Structures : Part 4.3 String : Substring : Subset : Permutation : Combination

For the set {1,2,3,4}  if we have to select 3 elements , we can proceed as below


1)   Select the left most 3 elements . 1,2,3
      Then move the right most elements till we reach SET end  1,2,4
      Once the right most element is reached, then move the second element from right 1,3,4
      2,3,4

  Select 2 elements
     1,2
         1,3
             1,4
     2,3
          2,4
     3,4


Now as we can see in   nCr , if r value changes then number of FOR loop will also changes, So in this situation we have to use RECURSION.

2) Now in RECURSION we use SYSTEM STACK, but we can use our STACK using DFS

1-->2-->3-->4

insert 1 in stack , then insert 2 without poping 1  ..Now if  r value is 2 ....print all elements in stack 1,2

now since R is reached , pop stack ...so we poped 2 , now from 2 we can go to 3...so insert 3....again r value is reached so print 1,3

similarly  1,4 will be printed


Now once SET end is reached pop two elements from stack  , and insert next element  and repeat process.

2,3  2,4

then 3,4

For    say 5 elements  1,2,3,4,5    we have to get all 3 elements ...the stack method will be

1,2,3     r value is reached , pop only 1 element and insert next element
1,2,4
1,2,5
        // here SET last element is reached, pop out that and also the next element
1
       // Now insert the next element
1,3  // now keep inserting till we reach r value
1,3,4
1,3,5
1
1,4
1,4,5
1
1,5  SET end reached, pop top and also next element
empty stack
2
2,3    keep inserting till R value reached
2,3,4
2,3,5
2,4,5
2,5   pop one more
3,4,5
3,5 pop one more


Below is the code snapshot.


Here obj1  is STACK object , whose SIZE is R.

1. while(obj1.empty)
2. {
3. if(n==N && obj1.push(n)==-1 ) obj1.print();
4. if(n==N) { obj1.pop();n=obj1.pop(); }
5. else if(obj1.push(n)==-1)
6. {
7. obj1.print();
8. n=obj1.pop();
9.  
10. }
11. ++n;

Algorithms and Data Structures : Part 4.2 String : Substring : Subset : Permutation : Combination

So in the last post we have seen , how to generate all possible substring for a given string.


That  will solve lot of question on string.


Here we will see how to generate all possible SUBSETS, since a lot of questions, where we have to pick for N numbers ...any combination such that it satisfies a given condition can be solved using this.




Ex : Given 6 coins of different denomination, find how we can have 3 coins where sum of these 3 is 20 bucks.


or any number of coins such that sum is 15 bucks.


In case of SUBSTRING, maximum possible SUBSTRING where for STRING of length N is N*(N+1)/2


In case of SUBSETS, it is 2^N....since either a element is in subset or not in subset.


so given {1,2,3}  ...we can have  {}, {1},{2}, {3},{1,2},{2,3},{1,3},{1,2,3}.....2^3 = 8 elements.


So if we assign 1 bit to each element, we can see that for  8 elements ...the binary representation will be (starting from 0)


0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1


Now if you pay close attention we can see , if we think of these bits are element position, and treat 1 as including that element in subset and 0 as not....we can have all the elements


So


0 0 0
0 0 3
0 2 0
0 2 3
1 0 0
1 0 3
1 2 0
1 2 3


So in our algorithm , if we have 3 elements we have to run a loop from  index=0 till index < 2^3


and take binary representation of index...and then see at which position we have 1 , then include those in our sets.


Code :  https://ideone.com/0WQgqM




Now lets see some time complexity and other points


1) When I run the above code for SET of length  < 12, it is fast...but for set values more than 12 , you can see it started to take more time.


2) We are running our loop  less than 2^N....NEED TO TAKE CARE, that the  index type satisfy such a big number...whether you will take INT or LONG.


3) What if our question says SET of 3 numbers or set of 4 numbers.


So now even if from a given set of  say  6 numbers, we have to select 3 numbers satisfying some condition. What is much better running loop till 2^6  and then selecting all subset having 3 numbers  or directly generating set of 3 numbers.


To select 3 numbers from 6 numbers, we have  6C3 =  6!/3!*3! =  20


So if we can generate combination directly we can solve this problem in 20 iteration , whereas with SUBSET we have to go for 64 iteration.


So now we see how to generate combination in next post.

Algorithms and Data Structures : Part 4.1 String : Substring : Subset : Permutation : Combination

A lot of questions comes on string or sets. 

But if we now the basics , then we can solve most of the problems.

For strings, we should know how to find SUBSTRINGS.

For Sets, we should know how to find  SUBSETS, PERMUTATIONS, COMBINATIONS. 

Lets see one problem on  STRING. 

 Given a string, find all the possible palindrome in it. 

Now if you know how you can find all the substring, then you can check each for the palindrome test. 

Now you can find all the substring using 3 loops.

Code is here :  http://ideone.com/3W9mCl

Now we can use this code to work on variety of question, but if someone ask to provide 6th substring in hexa order, then first finding total substring and then sorting them, will consume space and increase complexity.....a better way is SUFFIX TREE.

The funda behind SUFFIX TREE is that , for a given string you find all the suffixes and then arrange them in ascending order.  Now you store this order only.

Ex : For string  "tree", we have

0 1 2 3
t  r e e

suffixes :
0 tree
1 ree
2 ee
3 e

On arranging as per lexicographical order, we have
 3 e
 2 ee
 1 ree
 0 tree

So suffix array will be
0 1 2 3
3 2 1 0

How we read suffix array is like this : Suppose we have to find suffix whose order is 3rd in lexicographic order, in suffix array what index is at 3rd position, it is 0.

No in given string start from 0th index and go till the end of string...we have tree :)


Now suppose you have suffix array and you want to find  5th SUBSTRING.


Now what are possible substring of tree

tree,tre,ree,tr,re,ee,t,r,e,e

Now the suffix we have are   tree,ree,ee,e ,

Now to get substring from suffix array, we find prefixes of each suffix , so

from tree we have     tree,tre,tr,t
from ree                    ree,re,r
from ee                     ee,e
from e                       e

if you see we have all SUBSTRING.

Further if you NOTE , all substring derived from  REE will have order greater than TREE.

So I know that my suffix order is

e      from this I can have 1 substring
ee    from this  2 substring
ree   from this 3 substring
tree  from this 4 substring


Now for the 5th substring we will have it in 1+2+3...so in 3rd suffix substrings

We have to also pay attention to DUPLICATE, for that we have LCS matrix. It value is derived by checking how many characters of two adjacent suffix in suffix array matches from start.

Ex for
               LCS
0  3 e        0
1  2 ee      1          // this means 1 substring will be common in e and ee
2  1 ree     0
3  0 tree    0

Other example  for  "chtch"
                          LCS                         SUBSTRING
0   ch                 0                               ch,c
1   chtch            2                               chtch,chtc,cht,ch,c          See TWO common SUBSTRING
2   h                   0                               h
3   htch              1                               htch,htc,ht,h                    SEE ONE common SUBSTRING
4   tch                0                               tch,tc,t

chtch :  chtch , htch, tch, ch, h

So substring in lexicographic order is

c,ch,cht,chtc,chtch,h,ht,htc,htch,t,tc,tch   12 SUBSTRING

possible are  5*6/2   : since STRING LENGTH is 5 , so  n(n+1)/2 ...but as you see 3 are duplicates

Algorithms and Data Structure : revise

This post if not revising about things learned in previous 3 post, but more about revising what I have learned till now




knowing algos and applying in daily life is entirely different thing.  Lots of us know how to put algos if given a question that you have to visit N places in a city and discount varies on number of places visited.


But in real life , if we have to plan such a trip, we all will go with paper and pen calculation.  :D



So this is how I see big picture ( which will change as per learning).




          Structure                                                                                                Algorithms            
 
 Linear Storage                                                                                         Iteration
   > list                                                                                                       Recursive  
   > array                                                                                             Traversal
   > adj list                                                                                                > DFS (Back Tracking)
  > parent list                                                                                            > BFS
  > Stack                                                                                             Sorting
  > Queue                                                                                           Searching
  > Hash table                                                                                      > Binary search
  > String                                                                                             > Hashing


Structure                                                                                             All SubString     
  > Tree


Matrix






Questions:


Traversal related ( Maze , Tree , Graph)
Permutations related
Subset related
Combination related
Substring related

Algorithms and Data Structure : part 3 Back tracking

Back Tracking  and  DFS






Back Tracking is travelling a path in a matrix/graph/tree using DFS and checking if this is required solution.


If not, we can PRUNE that path and use DFS on other path.


DFS uses STACK.




As I am solving some questions, the best way to apply back track is think


1) Can you have the problem statement expressed in terms of matrix.
2) IF yes, you will be apply to easily visualize how you can apply back tracking .


Since in matrix , you will be apply to move in 4 directions at max, so at each node you can save node data of possible movements in STACK. Once you see your solution is not met, with the direction you are moving, you will start popping the elements.


This is basic skeleton of back tracking , but you will have to add conditions of movement depending on question and solution you want.


For ex : Suppose given a  Set of   6 elements { 1,2,3,4,5,6}  you have to find all possible permutation of  3 element subset.


Ways to solve problem.
1) generate all subsets and select only those whose size is 3 : Brute Force
2) Second Use 3 for loops and select different elements in each loop : Iterative solution
3) Rather than for loops , use recursion : Recursive solution
4) Think all 6 number as graph nodes, interconnected to each other, so in you matrix you can move in any direction for a given node. Now apply DFS+BackTracking , as soon you have 3 elements in your stack, you will stop that route. Then you will pop out one element and move to next element.


Now  for this particular problem, recursive will give the simplest code. 


So many a times you have to see , which approach will work out the best.




Suppose in some other example you have a matrix with 0 and 1.  In that case you have to move from 0,0 position to 7,7 position and you can move only where 0 are present.  And now you have to find the route.


In that case back tracking will give simplest code. ( NOTE SIMPLEST Doesn't MEANS FASTEST, but since those problems when we visualize , we can easily map them to back tracking, so you can make the code easily)




Some problems you can work on


1)  Given {1,2,3,4,5,6,7,8,9,10}  find all subsets whose sum is 10.
        try  back tracking and some other approach, and see advantages of one over other.


2) Take a matrix composed of  0 and 1 , with 0 as path and have multiple paths from topmost-left corner to bottommost-right corner , now PRINT all the possible paths.

Algorithms and Data Structure : Part 2

Q1) Given  two 1-D array.


One array has  consecutive odd numbers.
One array has consecutive even numbers.


Now  you have to sum each array and find the difference between these arrays.


How much space and time will be needed ? 


The input will be given in text file.


Ex : In you text file you will have


8 10 12 14
11 13 15 17 19


So you have to do :


Sum of even = 44
Sum of odd : 75


diff : 31 ,  even negative diff print if allowed.








Read Once you have working code:


If you use mathematical formula of  sum of N numbers, then you can do this operation in O(1) time, constant time.


And space you have two define just  THREE/FOUR INTS in you code.


Two ints to take start and end value of array, and  Two ints to save the sum, ( we can reuse one of previous int here) .


Now but if you would have read the full arrays and stored them and then find sum using for loop


then


TIME : O(n)
Space : 2N + some ints.


I have to start working on Arduino , that will be better for checking Memory and Execution Time.




Complexities:


O(1) >> O(logn) >> O(n) >> O(nlogn)


After this  O(n2) and above are just bad.... Try to keep  time complexity  =< O(n2)


Time Taken


When I run some basic loops on my Virtual machine having one CPU, below is time I got


linear loop with 10^5  close to 2 sec.
10^4 * log(10^4)  close to 1.5 sec.


So you can see once you have rough idea about how your machine will behave for MAX size of input, you need to change your ALGO and DATA STRUCTURE.


If data size is less than 100,  lot of time the difference in DATA STRUCTURE and ALGO is not visible.

Algorithms and Data Structures : Part 1

Pheww....we all would have read this topics a lot of time.


But still with every new question, we get something new to work with.


I think Algorithms and Data Structures increase human Intelligence, because everytime you get a new way to solve some problem.




Now whenever you are coding next time, please pay attention to below topics.


1) Space complexity of your algorithm
     > rather than how much size is needed, focus on how you can reduce the size which is currently used.
      i.e Can you change the DATA STRUTURE you are using to store things.


Ex: 1) A lot of people uses matrix array to solve graph problem, even though adjacency list might be better choice.
2) When sorting data, a lot of people creates duplicate of original data given, which sometimes is not necessary.


Or take an example, that you have string array and you have to sort it, but have to keep original data also.


In that case, rather than having two STRING array, just have one string array, and create a STRING position array to keep original string places, in this case you have INT array, rather than STRING array solving the same thing.



2) Time complexity of your algorithm
  > For this you need to focus on
     1) Standard algorithm used for that type of problem.
     2) Type of data structure used,  when you have space vs time constraint.


3) Try to use more maths.
   > Standard formulas, SET theory, Matrix property :  If you know what happens when you run transpose on matrix, or union of two sets. You will have better ALGORITHMS and it will be easy to prove them.


4) COMPUTER STORAGE: Many of use when coding write program as we are writing on piece of paper. But we have to understand how our data is saved in computer. Ex : How many bits , whether INTEGER will be converted to CHAR easily.


This way you can use bitwise operation and other properties to get faster ALGORITHMS.
Also amount of DATA storage can be reduced


Thinking about these points everytime you code , will help in getting better solution

C language : bitwise operator

This post is more like patchwork.

Even though most of the things has been covered, but still we can have some questions  about known things, which if not working regularly can put us in doubt.

1) Right Shift on Signed type

int a= 0x80;

a= a>>1;

// Main thing is what will happen to MSB , will it be substituted by 0 or 1.

The sign bit on right shift retains it original value , so if it was 0 , it will remain so. If it was 1 , it will remain so. 

int  a=-0x80;

a = a>>1;

2) Right Shift on Unsigned type


The MSB will be replaced by 0.

3) Left Shift on Signed Type or unsigned type

It doesn't have any effect.  Only thing to note is if for SIGNED MSB becomes 1 due to left shift, then while printing its value we should not be surprised by its negative value.


Difference between + and &. 

+ is same as &, only thing is in case of + , we carry forward .

Ex :  0011 + 0010  , in this case when we came to 2nd LSB 1+1 will give as 0 and we will carry forward the 1, In case of & NO.


While making program, I am bit surprised to see one thing.

Try to run below program and see if you can get it.

unsigned int a= -0x80;

printf("%d",a);

a = a<<1;

printf("%d",a);


When you will run this program, you will notice NEGATIVE value. But a is UNSIGNED then WHY ??


It is due to %d argument,   In C , SIGNED is default. Same was %d is for signed int, but we are accustomed to us it everywhere.

The correct format type is %u. 

C language : Memory Layout 2

Well ...I thought that the first post would be enough for this thing, but it turns out that still more is needed.


My friend was asked one question : Will the executable build on windows will work on Linux.


Offcourse the answer is NO, as we have seen many a times practically. But Why Not ?


The C code which we write is same for both, we can use the .C file and work on both the system.


So where does the difference occurs.  Is it due to Compilers  GCC vs Visual Studio.  ?


OS  Windows vs Linux ? 


So again I am trying to find out what could be the reason.




So starting first, the basic steps involved in  C code to Executable are




1)  Preprocessing :  Can I use preprocessed file or one system to another ?

2) C code to Assembly Code : Done by Compiler  :  Can I use  this code file across system ?
 
3) Assembly Code to Object Code : Done by Linker : Same question

4) Object Code to Executable : Done by Loader :




Now the first thing I will do , is have GCC on Windows , so that atleast we have same file extension .


 I installed MinGW, 


Step 1)  Install MinGW from its website. Choose only C and C++ option.
Step 2) http://stackoverflow.com/questions/25542055/mingw-c-compiler-zlib1-dll-missing-error/25542347   :  Apply changes as per 2nd option
Step 3)  C:/MinGW/bin should be present in your environmental variables.






Now once this much is done,so lets dig deeper.




On Windows , I made a small program


main.c


void main()
{
}


and  compiled using




gcc -o check main.c --save-temps   // This will save the  .I , .S , .O  and .EXE file.

Same I will be compiling on Linux,

Now it turns out thing are not so easy as I was expecting.

I will be uploading the FILES later.

The window/mingw   .I extension which is for preprocessed file differs slightly from the Linux generated preprocessed file for same code.

Even though the diff was minimal, later I can see how much difference was present.

Now the assembler file of both were different, the main difference was the function call.

In winodws  it was _main  in Linux  main.


So I copied the windows preprocessed file to Linux , and generated assembly code there.

--------Some extension and command-----------

To generated preprocessed file

gcc -E main.c -o main.i   // I is extension

To generate assembly code

gcc -S main.i -o main.s  // S is extension

To generate object code

gcc -c  main.s -o main.o  // O is extension

To generate executable

gcc -o main.o  outfile.out  // .out is extension

---------------------------------------------------------------

now when I used Windows preprocessed file and generated assembly code in Linux, the file generated was same as the assembly code file for linux.

But when I generated the object code file, it differs hugely.

WHY??????  Not having the faintest idea.

Hence I am stopping this post here, until me or someone else do further debugging.

-----------------------------------------------------------------------------------------------------------------

Some question to answer .

What is assembler ?
Difference between assembly and object code ?

there was pretty interesting post I found out.

http://stackoverflow.com/questions/28490124/reverse-engineer-assembly-code-to-c-code

C language : Bits SIGNED , UNSIGNED and thier storage.

Now we have covered most of the things related to C, but still some interviewer can surprise us by asking some question , which sometimes can confused us.




For ex : One of my friend was asked.




char C = 1;   // whether 1 will be stored or 0x31 ( ascii value of 1)


One more question was


char c=30;


for ( ; c<300;c++)
{
  printf("%d",c);
}


// What will be the output.


Now in both of these question, we have to understand how  number is stored and difference between SIGNED and UNSIGNED number storage.


First we will take only CHAR and INT, since they are easy to understand than FLOAT.


Now , when we do


char c=1;
char c='1';
int c=1;
int c='1';


We have to understand that compiler takes the hexa decimal representation of that number on RHS and then stores it.  So irrespective of int or char ,  1 will be 0x01  and '1' will be 0x31.


And again while printing the values , convert the binary number representation to hexa-decimal.
And depending on %d or %c, check the  int or character representation of the stored hexa number.




So for


char a=1;
char b='1';
int c=1;
int d='1';


printf ("%d %d %d %d",a,b,c,d); // will give  1 49  1 49




Coming to second part.  SIGNED vs UNSIGNED.


SIGNED means + and - .  By DEFAULT every  char and int which we mentioned is SIGNED.


Now taking a machine which stores  CHAR in 8 bits and INT in 32 bits.


For UNSIGNED we will have 32 bits for INT...so max value can be from 0  to 2^32  -1 , for CHAR 0 to 2^8 -1.


So what if we store some number in unsigned CHAR which is greater than  255.


Then in that case, the last 8 bits of RHS representation of number will be taking into consideration,


So  if we have   unsigned char c=256;  On printing its value we will see 0 is stored in it.


Since the number 256 binary will be


0001 0000 0000 ,  and CHAR will consider only last 8 bits we have 0 in there.


You will get WARNING at compile time though, and you can use -Werror option on compilation time, so that you don't skip the warning and get unwanted behavior in your program.


So




unsigned char c=30;


for(;c<300;c+=30)
{
printf("%d",c);
}




// This will give infinite loop, since c value at max can be 255, and once it reaches 270, the actual number stored in C will be


270  =  1 0000 1110    // taking last 8 bits   =  14 , so again the loop will run.




Now what if we assign some negative number to unsigned type.


Ex :


char c = -1;


Compiler will first convert -1 to binary, using 2's complement .
After that it will take the last 8 bits of RHS and convert back to char/int representation.


Note while printing the value the 8th bit will not be taking as SIGNED bit.
It will be treated as UNSIGNED only.




SO  printf("%d",c)    will give us  255.


------------------------------------------------------------------------------------------------------------------


2's  complement   :


-1 


1) remove the negative sign
2) convert the number to binary representation
   So   we have  0000 0001
3) Apply NOT operation.
   1111 1110
4) Add 1 now
   1111 1111
------------------------------------------------------------------------------------------------------------------
Now this number will be stored , 0xFF   will be stored in UNSIGNED CHAR, since we have defined c as UNSIGNED.






So  we are done with the UNSIGNED INT and CHAR.




Now coming to SIGNED ones, In case of SIGNED types the first LHS bit is treated as signed flag,


So


1)signed char c=0x80;
2) unsigned char c=0x80;


%d of both will give as


1)  -128
2)  128     // this is quite evident


So how  1) answer came to -128.


Now 0x80 was stored as    1000 0000
When we are doing printf,  compiler sees that this is signed bit, so it prints its two complement


number              1000 0000     // first bit is 1 , append - flag when printing
 Not operation  :0111 1111
add                                    1
                           1000 0000   = 128 




Run this program and see if you can understand the output which came.


#include<stdio.h>
int main()
{
signed char c;
c= 0x80;
printf("%d\n",c);
c= 8;
printf("%d\n",c);

c= -8;
printf("%d\n",c);

c= 511;
printf("%d\n",c);
c= 255;
printf("%d\n",c);
c= -255;
printf("%d\n",c);
}




Note when dealing with SIGNED number , remember


1) Irrespective of signed or unsigned, every negative number will be stored as 2's complement.
2) While printing, if
      the number MSB is 1 and the type is SIGNED.  2's complement will be printed with negative sign


So with SIGNED types,  storage and printing values are different, which can be highlighted with below program.






One more interesting question:


#include<stdio.h>
int main()
{
unsigned char c= -8;
signed char d = 0x80;


printf("%d \n",c);
printf("%d \n",d);


signed char e = (char) c&d;
unsigned char f = c&d;


printf("%d\n",c&d);
printf("%d \n ",e);
printf("%d \n ",f);
}


Now the output will be


248
-128
128
128
128


Exp :


in C , we will have 8 complement  since it is negative ,
 8  =  0000 1000
NOT operation :  1111 0111


Now add 1
                         1111 1000  = 248 , since it is unsigned, 248 will be printed, which is also which is in STORAGE at memory for this


In d we have  1000 0000  ( In STORAGE)
when it is printed,  since MSB is 1 , its 2 complement is taken as it is SINGED.


hence,    0111 1111
add 1     1000 0000    128  and add negative sign    -128.


Now when we perform   &  operation,  we are doing operation on


1111 1000   and  1000 0000  , since these values are in storage, so we get


1000 0000  which is 128.


Now when we perform any operation between  SIGNED and UNSINGED , the result is UNSIGNED.


hence we get 128 , but when we cast it to signed variable , again 2's complement of 0x80 will be printed , hence -128.




What if we have used  +  operation instead of  &  operation.  Try to work out.


And also what about the - operation.  HINT : - operation is nothing , but telling compiler that the number is negative, so  a-b  becomes more like   a + (b 2 complement).
----------------------------------------------------------------------------------------------------------


While making - program, I got one thing, which was bit puzzling.


Ex :


unsigned char c = -8;
signed char  d = 0x80;


unsigned char e= c-d;
printf("%d",e);
printf("%d,c-d);


The output were   120  and 376.


120 is quite eveident.


C will be in memory store as 0XF8   .
and D will be  0x80.


Now when we do  c-d ...its like  c+ (d 2 complement) which is again 0x80.


So  e will be   1 0111 1000    , but since e is just 8 bits so we have  0111 1000  = 120.


But when we do printf("%d",c-d),  printf sees %d and treat c-d as SIGNED INT , hence we get 1 0111 1000 value which is 376.


-------------------------------------------------------------------


Similarly ,


signed char d = 0x80;
signed char e = -0x80;


printf("%d", -d );
printf("%d", e );


The value will be different,  try to figure it out.








So to summarize:


Every negative number gets saved as 2 complement.
While printing , it is checked is number is signed or unsigned.
While operations , the value at the storage is taken into consideration.

C language : File Input and output

Here we will see some methods of file input and output. That will help in writing some good code, where we want to process file data.

Everything is type of FILE when we see OS. The stdin,stdout,stderr  all are treated as file.

We will start with the simple C code of our own copy tool.

The functions which we will see are

int putchar(int)  : Its output on stdout file , whatever int we put in it. Also it returns the same int and on error EOF.

int getchar(void) : Its reads from the standard input (stdin) and returns what is the character in integer format.

Now on gcc , if we have to read input from a file, we can use getchar function in case of scanf() and using < we can tell getchar to read data from the input file rather than stdin.

> ./program  < input.txt

Similarly if we have used putchar in our program and want to save data in some file rather then getting displayed on console, we can do

>./program > output.txt

int getc(FILE *) :  This is similar to getchar, only diff it has parameter FILE pointer, in which we can specify our file name.

int putc(int,FILE *) :  same as putchar, only we can specify the file where we want to put data.

Two more function related to File.

1)  File * fopen(filename,mode) : Mode can be "w","r","a".
2) fclose(File *)


One more thing,

till now we were using
int main(),   But what if we want to pass some arguments to main from command line, Then we will use

int main( int argc, char *argv[])

argc is count of how manu arguments were given, every argument which is given is treated as STRING.

so

>./program 1 2 3

will be treated as  4 arguments    ./argument is first  and 1,2,3 next three. We have to take care inside program whether we want to convert them to int or any other type.


Now the file copy program :

#include<stdio.h>

int main(int argc ,char *argv[])
{
   int c;
   FILE *fp1;
   FILE *fp2;
 

   fp1 = fopen(argv[1],"r");
   fp2 = fopen(argv[2],"w");
   while( (c =getc(fp1))!=EOF)
   {
     putc(c,fp2);
   }
     fclose(fp1);fclose(fp2);
}

if we create output file with name copy

> gcc -o copy  program.c

> ./copy program.c dup_copy.c  // will copy program.c  to dup_copy.c


Now we will see the STDERR file, like STDOUT it also prints output onto console. I myself was not able to find good reason for doing this.

Since first of all I am not getting any way where I can use stderr to give additional  compile errors or runtime errors .

Most of the times it works like simple printf or sprintf.

On searching I found a very good blog, which told history and usage of stderrr.

http://www.jstorimer.com/blogs/workingwithcode/7766119-when-to-use-stderr-instead-of-stdout


In case you are not interested in reading it, the brief gist is

> When we are writing programs which doesn't simply involves console output, but some other way there we can clearly see difference between STDERR and STDOUT. Since in those cases we need to analysis errors and output. And if all the output is at same place it will be difficult to separate the two.

So we will not going to go deep in STDERR, untill we get a good case to use it.

Two more ways to output and input data using file.

fprintf and fscanf  , they work same as printf and scanf.

only thing which differs is first parameter of both is FILE pointer.


So now we have seen how to read character by character and also output it to any file.

But sometimes it can be very slow, So there are two more functions provided in C, which reads line by line and also for output we have a function.

char *fgets ( char *, int , FILE *)   and int fputs(char *,File *)

No need to explain FILE pointer,

Char * pointer holds the character array, IN case of  fgets the second parameter specifies the max number of character to be read.

Also the return value of fgets is same as its first parameter. It differs when end of line is encountered.

fputs returns EOF on error , else Zero.

To understand the  return value difference ...lets make a program.

We will test it using below scenarios.

1) When in fgets we have given  numberofcharacters less than in one line.
2) When in fgets we have given numberofcharacters more than in one line.
3) fgets and fputs  return value when FILE don't exist.
4) fgets and fputs  return value when FILE is empty.

Okay , so here is learning from the program about fgets.


#include<stdio.h>

int main()
{

FILE *fp;
char *c;
char c_dup[10]={};

fp = fopen("read.txt","r");

printf("fp value %d\n ",fp);
c = fgets(c_dup,10,fp);

printf("%p \n",c);
printf("%p \n",c_dup);

printf("%s \n",c);
printf("%s \n",c_dup);
return 0;
}



1) If file doesn't exist or can't be read. Then fp will return NULL. AND we should check this value, else we will get runtime error, segmentation fault.

2) The  return value and first parameter of fgets points to same address, if some text is returned and this address is of the CHAR * pointer we passed to fgets.

3) If file is empty, then fgets will return NULL/EOF , whereas char * will be empty string. 

4) If number of characters is more than present in the line, then characters present till the end of line will be returned.

In case of fputs, even if FILE can't be open or doesn't exist, it will return -1 , if write is successful, then 1 is return

In case we want the input file to be STDIN  and output file to be STDOUT,   you can use 

int puts (char *)   and  char *gets(char *)

No need of number of character is needed for gets.

C langauge : Pointers 2

Well, while writing the second way code, I found their was bug in my code and it was very basic error, hence I moved the second way here.

Below is the code with the bug.

Second Way)


int main()
{
int *t;
*t=2;
func(t);
printf("%d",*t);
}


void func(int *t)
{
t = (int *) malloc(sizeof(int));
*t=4;
}

Lets start with smallest code and we will be adding one line after another

Code Sample 1)

#include<stdio.h>

int main()
{
    int *t=2;
    printf("%d",*t);
}

Now ideally this code should give run time error, since we have not malloced T and assigned value to it.  But on GCC no error is coming currently and on VS error comes. 

It is how compiler are written, but SAFE PRACTICE is to malloc it.

Code Sample 2)

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int *t=(int *)malloc(sizeof(int));
    *t=2;
    printf("%d",*t);
    printf("%p",t);    // This will P address
}

This was GCC output

0xa04b008  2

Code Sample 3)

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int *t=(int *)malloc(sizeof(int));
    *t=2;
    printf("%d",*t);
    printf("%p",t);    // This will P address

func(t);

 printf("%d",*t);
    printf("%p",t);    // This will P address

}

void func(int *y)

{

 printf("%d",*y);
    printf("%p",y);  
*y=20;

}

Now many compilers , GCC is one of it throws warning/error  since func()  body is below main function and compiler cannot see it when it encounters func() call inside main. 

Now we can add func() definition in start of main. 

But I more thing which I learned is all you can make warnings into errors in GCC. Bu using     -Werror option. 

> gcc -Werror -o output memory.c    

and all warnings will be converted to errors, so that you don't overlook them.

This is post with more options : https://gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/Warning-Options.html

The output was 

2 0xa04b008 

2 0xa04b008 

20 0xa04b008 

So address location is same inside func and main.

Code Sample 4)

#include<stdio.h>

#include<stdlib.h>

void func(int *y)

{

y=(int *)malloc(sizeof(int));

*y=20;

 printf("%d ",*y);

    printf("%p \n",y);  

}

int main()

{

    int *t=(int *)malloc(sizeof(int));

    *t=2;

    printf("%d ",*t);

    printf("%p \n",t);    // This will P address

func(t);

 printf("%d ",*t);

 printf("%p \n",t);    // This will P address

}

Here the output was

2 0xa04b008 

20 0xa04b018 

2 0xa04b008

Here we see that inside the address and value is different, but after that also in main the new value is not retain.

This is because,  int *y , here Y is pointer and is LOCAL. when we called func(t). It passed the value of t address to Y.  But when we malloc y, its address got changed. NOW HERE WE HAVE TO NOTE THAT CHANGING Y ADDRESS WILL NOT CHANGE T ADDRESS, but if we have not malloced Y, then changing its value changes T value, since both point to same address.

Hence once func()  is exist, T retained its address value and the value at it is still 2. 

So this pops a Q. What if we want to create a code in which process 2 malloc address and passed to process1.  Process1 is caller of Process2.

Then we have to use double pointer.

Code)

#include<stdio.h>

#include<stdlib.h>

void func(int **y)

{

  *y=(int *)malloc(sizeof(int));

    printf("%p ",*y);

    printf("%p \n",y); 

}

int main()

{

    int **t =(int **)malloc(sizeof(int*));

    printf("%p ",*t);

    printf("%p \n",t); 

func(t);

 printf("%p ",*t);

 printf("%p \n",t);    // This will P address

}

Output is 

(nil) 0xa04b008 

0xa04b018 0xa04b008 

0xa04b018 0xa04b008 

As we can see , since we have malloced, only Y in main, it has some address and *y is NIL. 

then when we malloc *y , it has some address and on returning back to main function same is retained, since we have NOT CHANGES Y address, but address Y points to. 

We have not malloced Y in func, since that would have changed the Y address and no Change in T would have happened. 

Now coming back to our problem, HOW can we pass a function pointer to process2 and its return the correct function the pointer should point to.

Code Sample 1)

#include<stdio.h>

#include<stdlib.h>

typedef void(*fp)(int,int);

void add(int a,int b)

{

  printf("%d",a+b);

}

void func(fp y)

{

  y=add;

  y(8,9);

}

int main()

{

    fp f1;

    func(f1);

    f1(2,3);

}

Will this code work. No COMPILE ERROR, BUT RUN TIME ERROR:SEGMENTATION FAULT.

Since like previous code,  when func() is exist and we return back to main, f1 is not pointing to add function.

Here again we have to write code which passes pointer to function pointer and then change the function value.

#include<stdio.h>

#include<stdlib.h>

typedef void(*fp)(int,int);

void add(int a,int b)

{

  printf("%d",a+b);

}

void func(fp* y)

{

  *y=add;

  (*y)(8,9);

}

int main()

{

    fp* f1 = (fp*)malloc(sizeof(fp)) ;

    func(f1);

    (*f1)(2,3);

}

This ends our discussion on pointers

C language : Pointers -1

Everyone knows about pointer. So we are basically going straight into examples are cross checking our knowledge.



int *p;   or int* p;



Which one is better ? The first one for me, as it makes it easy for getting to know whether its int or function pointer.




Now see below

int *func();  int* func(); int (*func)();



here 1 and 2 are same , since C precedence for * is from left to right. hence we have to use brackets when defining function pointer.



So its better to associate * with either data type or function depending on what you are creating, it will help readability of code.




Now see the below code and see if it has any error and try to correct it.




int main()
{

chat **t=func();

printf("%c",*t[3]);
}

char **func()
{

char **p = (char **) malloc(sizeof(char *));
char *t = "icecream";

p = &t;

}





Now see the below code and see if it has any error and try to correct it.

int **func();

int main()
{

int **t=func();

printf("%d",**t);
}

int **func()
{

int **p = (int **) malloc(sizeof(int *));
int *t;
*t = 3;

*p = t;


}





Now see the below code and see if it has any error and try to correct it.

1)

typedef struct point_T{
int **a;
int b;
}point;



int main()
{

point *var;

var = (point *) malloc(sizeof(point));

(*var).b =2;
*var.b=2;        // WHY IS THIS WRONG
var->b=2;

printf("%d",var->b);

}






2)

typedef struct point_T{
int **a;
int b;
}point;



int main()
{

point *var;

var = (point *) malloc(sizeof(point));
       
  // WHICH ONE IS CORRECT : COMPILE WISE   , and WHY THIS PROGRAM GIVE RUNTIME ERROR

**(var->a)=3;
var->**a=3;
(var)->**a=3;
var->(**a)=3;

printf("%d",var->b);
}

3)

typedef struct point_T{
int **a;
int b;
}point;



int main()
{

point *var;
int b=9;
var = (point *) malloc(sizeof(point));
(*var).b =2;
(var->a)=(int **) malloc(sizeof(int *));
**(var->a)=b;     // IS THIS CORRECT  ???

printf("%d",var->b);
printf("%d",**(var->a));
}





4)  The below program is CORRECT

typedef struct point_T{
int **a;
int b;
}point;



int main()
{

point *var;
int b=9;
var = (point *) malloc(sizeof(point));
(*var).b =2;
(var->a)=(int **) malloc(sizeof(int *));
*(var->a)=&b;

printf("%d",var->b);
printf("%d",**(var->a));
}





If you run the above programs, you will see that  when dealing with pointers.

1) If they are not string literals, then  each  pointer has to be malloced, if you want to store some value in it , else segmentation fault.

2) if it is string literal, then by default malloc gets done.

3) if you are just using pointer to point to some address, no need to malloc, BUT IF IT IS DOUBLE POINTER, then INSIDE POINTER has to be malloced.






One last program for struct and pointers.




typedef struct point_T{
int **a;
int b;
}point;



int main()
{

point var;
int b=9;

var.b =2;
**(var.a)=b;  // Will this work, if not how will u correct it

printf("%d",var.b);
printf("%d",**(var.a));
}





Now coming on the  VOID POINTERS.


Lets see why we need them


Scenario 1 )


There are two processes, each one having their own structure or enum. Now when we want to pass some enum or struct to other process, how we will pass it.


Ex:


in process 1  we have  enum  week1  and in process we have enum week2. now process1 calls func()  to pass value to process2.


What will be the function definition


if we use


void func(week2 var1)  // then we get compile error , since week2 enum if not visible to process1.


if we use  func(week var1)  and then in process2 we get a compile error since week is not visible in process 2.


Hence we have to use void pointer, and take care of assigning correct values in each process.


Some things to take care


1) VOID POINTER can't be deference


Ex  :


int main()
{


int *t = (int *)malloc(sizeof(int));
*t=10;


void *y;


*y =10;  // This will give error
y= t;  // This is correct way.


printf("%d",*y) // again will give error


printf("%d",*((int *)y));  // This is correct way
}


As we can see everytime we have to dereference a void pointer, we have to cast it to some DATA TYPE pointer.




Scenario 2)


Function pointer and Void pointer.


Void pointer , you can think as something which provides a limited level of abstraction to C language.


Its a bucket, in which we can put any type of pointer, Only when we are emptying the bucket we should know what was in it actually.


So when we use function pointer and void pointer.  Again most of them are used when we have more than one process.  In that case


1) Sometimes we don't know what type of function needs to be called.


Example : Suppose there are two friends, One writing code for processing details of employee salary depending on it post.


the other friend is writing code of storing employee details and passing it to other friend.


Now if Friend1 has not told or due  to visibility the function name is not known, then we can't call any function.  So in that case we just call a function pointer, and also pass some data to friend2 so in know emp type.


And will call respective function in his code.




Some points to take care when defining Function Pointers are


1) The correct declaration is


return type (*func_pointer_name) (parameters);


2) Also its best practice to typedef this so that it will become easier


typedef   return_type (*typedef_name)(parameters) ;


Yes syntax is almost same, only we have to add typedef in starting.


3) Unlike data types, function name is itself a pointer or address.


for int we have to do like below


int r=8;
int *t;
t=&r;  // Here we are assigning the address


but with function pointers


void func1(int,int);
void (*func_pointer)(int,int);
func_pointer = func1;          //  No & sign was used.


which seems like below declaration


void func_pointer(int,int);


Only thing is here func_pointer is static and can't be used to change function call.


Now when u have typedef


void func1(int,int);
typedef void (*func_pointer)(int,int);


func_pointer f1;


f1=func;


4)  How to dereference a func pointer.


It can become a little tricky when dereferencing a function pointer, since like int,char pointer our tendency can be to use * while dereferencing, but we have to remember that * only means that it is function pointer, apart from that we have to treat it like normal function name.




int func1(int,int);
int (*func_pointer)(int,int);
func_pointer = func1;          //  No & sign was used.




Now here if we want to print return value of  func1, we would have done like below


printf("%d",func1(2,3));


Now if func_pointer is used, even then we will do the same


printf("%d",func_pointer(7,8));


No need to use * while deferencing.




5) How to pass function pointer.


Now with data type we can use pointer in two ways, while passing pointer from function1 to function2  we assign value in function1  or  we can assign value in function2.


First Way)


int main()
{


int *t= (int *) malloc(sizeof(int));
*t=2;
func(t);
}


void func(int *t)
{
int h=*t;
}


With function


typedef  int (*fp)(int,int);


int add(int a ,int b)
{
 printf("%d",a+b);
}


int main()
{
fp f1 = add;
func( f1)
}


void func(fp t)
{
  t(2,3);
}


Now can we use   typedef int (fp) (int,int).
Yes we can , but it is not used much, since whenever u will pass a function, you have to pass function pointer.


typedef int(fp)(int,int);


int add(int,int);


int main()
{
fp t;
t=add;  This will result in compile error, we have to use  


fp *t;  then only it will work, so its better to have * in typedef only.
}




Second Way)




int main()
{
int *t;
*t=2;
func(t);
printf("%d",*t);
}


void func(int *t)
{
t = (int *) malloc(sizeof(int));
*t=4;
}




With function




typedef  int (*fp)(int,int);


int add(int a ,int b)
{
 printf("%d",a+b);
}


int main()
{
fp f1;
func( f1)
f1(2,3);
}


void func(fp t)
{
t=add;
}


We will carry the discussion of 2nd approach in second post.

C language : malloc free realloc and memory

Run this below program

#include<stdio.h>
#include<stdlib.h>



int main()
{

int *p=malloc(sizeof(int)*7);
printf("%d ",p);

free(p);
printf("%d  ",p[2]);


int *m=calloc(8,sizeof(int));
m[2]=100;
printf("%d ",m);
printf("%d  ",m[2]);
m[6]=90;
printf("%d  ",m[6]);

free(m);
realloc(m,4);
printf("%d ",m);
printf("%d  ",m[2]);
printf("%d  ",m[6]);
free(m);

}

First of all it will tell

1) syntax of free, malloc, realloc,calloc

2) If you pay attention we can see even after freeing  p , we can still access p[2].

The reason being " when we malloc or calloc some memory" compiler stores some additional information regarding that memory...size , initial values" , and it returns back actual RAM address.

When free is called, all it does is removing that information.  Then again depending on compiler free can set the pointer to NULL, can all delete the value stored in that RAM address.

But it seems GCC doesn't does that, therefore since we have address of physical address we can still access what is in it.   Therefore  whenever you call free in your code, REMEMBER to MAKE pointer NULL after that, else memory corruption can happen.


This also answers the question which is asked many times in interview , that how does FREE knows how much memory to free , when we don't pass any size to that.


Also the below code will give run-time error. Since with first free we have deleted any information regarding the pointer M. hence at second free compiler returns error.


int main()
{

int *M=(int *)malloc(sizeof(int));
free(M);
free(M);
}