Program for putting bits into buffer. This is useful in compression of data, avoide wastage of bits. This program will work for any 32-bits integers.

1:  /******************************************************************************  
2:   *         Include Files  
3:   * ***************************************************************************/  
4:  #include <stdio.h>  
5:  #include <stdlib.h>  
6:  #include <string.h>  
7:  /******************************************************************************  
8:   *         Macros  
9:   * ***************************************************************************/  
10:  #define UINT_64 unsigned long long int  
11:  #define UCHAR unsigned char  
12:  #define OCTET 8  
13:  /******************************************************************************  
14:   *         Global Variables  
15:   * ***************************************************************************/  
16:  /*  
17:   * Remaining Bits give information about empty bits left in one octet  
18:   */  
19:  static int remaining_bits = 8;  
20:  /*  
21:   * Global Index for Octet shifting  
22:   */  
23:  static int idx;  
24:  /*  
25:   * Offset for last set bit from LSB  
26:   */  
27:  static int offset = 0;  
28:  /******************************************************************************  
29:   * This function used to calculate offset length for given Decimal number  
30:   ******************************************************************************/  
31:  int find_offset(UINT_64 num)  
32:  {  
33:    int offset = 0;  
34:    UINT_64 mask = 1<<31;  
35:    while(mask)  
36:    {  
37:      if (num & mask)  
38:      {  
39:        return (32-offset);  
40:      }  
41:      offset++;  
42:      mask >>= 1;  
43:    }  
44:    return 0;  
45:  }  
46:  /*******************************************************************************  
47:   * This function used to fill bits into 2MB buffer  
48:   * ****************************************************************************/  
49:  void put_bits(UCHAR *buf, UINT_64 num)  
50:  {  
51:    int temp = 0;  
52:    /*  
53:     * Checking For OFFSET length  
54:     */  
55:    if ( offset < OCTET )  
56:    {  
57:      /*  
58:       * OFFSET Less than an OCTET means bit patter will fit into single index  
59:       */  
60:      if ( offset < remaining_bits )  
61:      {  
62:        remaining_bits -= offset;  
63:        *(buf + idx) |= num << remaining_bits;  
64:      } else {  
65:        /*  
66:         * This condition executes when bit patter is less than one octet  
67:         * but it entire octet is not available  
68:         */  
69:        *(buf + idx) |= num >> (offset - remaining_bits);  
70:        idx++;  
71:        temp = offset - remaining_bits;  
72:        *(buf + idx) |= num << (OCTET - temp);  
73:        remaining_bits = OCTET - temp;  
74:      }  
75:      return;  
76:    } else {  
77:      /*  
78:       * This condition executes when offset is larger than one octet  
79:       */  
80:      if ( remaining_bits < OCTET)  
81:      {  
82:        /*  
83:         * If last octet is not filled completely, this condition will   
84:         * execute  
85:         */  
86:        offset -= remaining_bits;  
87:        *(buf + idx) |= num >> offset;  
88:        idx++;  
89:        remaining_bits = OCTET;  
90:        if ( offset > 0)  
91:        {  
92:          /*  
93:           * If still offset is there, then start filling form begining  
94:           */  
95:          put_bits(buf,num);  
96:        }  
97:      } else {  
98:        /*  
99:         * This condition will execute when offset is larger than one octet  
100:         */  
101:        *(buf + idx) |= num >> (offset - OCTET);  
102:        idx++;  
103:        offset -= OCTET;  
104:        /*  
105:         * Continue with patter filling process if still offset is still  
106:         * there  
107:         */  
108:        put_bits(buf,num);  
109:      }  
110:    }  
111:  }  
112:  /******************************************************************************  
113:   * Main function  
114:   * ****************************************************************************/  
115:  main()  
116:  {  
117:    int i=0;  
118:    UINT_64 num = 0;  
119:    UCHAR *buff = NULL;  
120:    buff = (char *)malloc(2*1024*1024*sizeof(char));  
121:    if ( NULL == buff)  
122:    {  
123:      printf("failed to allocate memory\n");  
124:      exit(1);  
125:    }  
126:    memset(buff,0,2*1024*1024*sizeof(char));  
127:    do {  
128:      printf("\nEnter any Number or Zero to exit:");  
129:      scanf("%lld",&num);  
130:      /*  
131:       * Finding Last Enabled bit position from LSB  
132:       */  
133:      offset = find_offset(num);  
134:      /*  
135:       * Putting Bit patter into Buffer  
136:       */  
137:      put_bits(buff,num);  
138:      /*  
139:       * Display buffer status  
140:       */  
141:      for (i = 0; i <= idx; i++)  
142:      {  
143:        printf("%4X", buff[i]);  
144:      }  
145:    }while(num != 0);  
146:    printf("\n");  
147:  }  
148:  /******************************* End of File *********************************/  

Write your own strcat function

1:  int my_strcat(char *dst,char *src)  
2:  {  
3:    while(*dst != '\0')  
4:      dst++;  
5:    while(*src != '\0')  
6:      *dst++ = *src++;  
7:    *(dst+1) = '\0';  
8:  }  
9:  main()  
10:  {  
11:    char str1[100] = "hello";  
12:    char str2[100] = "world";  
13:    my_strcat(str1,str2);  
14:    printf("%s\n",str1);  
15:  }  

Write your own strcmp function.

1:  int my_strcmp(const char *str1,const char *str2)  
2:  {  
3:    while(1)  
4:    {  
5:      if ( *str1 != *str2)  
6:        return *str1 > *str2 ? 1:-1;  
7:      if(!*str1)  
8:        break;  
9:      str1++;  
10:      str2++;  
11:    }  
12:    return 0;  
13:  }  
14:  main()  
15:  {  
16:    char *str1 = "Hello";  
17:    char *str2 = "Hello";  
18:    printf("%d\n",my_strcmp(str1,str2));  
19:  }  

Tree Insertion, Traversing , deletion and searching

1:  /**************************  
2:  * Headers includes  
3:  ***************************/  
4:  #include <stdio.h>  
5:  #include <stdlib.h>  
6:  /**************************  
7:  * Structure for tree  
8:   ***************************/  
9:  typedef struct node_  
10:  {  
11:    struct node_ *right;  
12:    struct node_ *left;  
13:    int i;  
14:  }node_t;  
15:  /**************************  
16:  * Global tree root  
17:  ***************************/  
18:  node_t *root = NULL;  
19:  /**************************  
20:  * Preorder tree display  
21:  ***************************/  
22:  void preorder(node_t *node)  
23:  {  
24:    if ( node == NULL)  
25:    {  
26:      return;  
27:    }  
28:    printf("%d\t",node->i);  
29:    preorder(node->left);  
30:    preorder(node->right);  
31:  }  
32:  /**************************  
33:  * Inorder tree display  
34:  ***************************/  
35:  void inorder(node_t *node)  
36:  {  
37:    if ( node == NULL)  
38:    {  
39:      return;  
40:    }  
41:    inorder(node->left);  
42:    printf("%d\t",node->i);  
43:    inorder(node->right);  
44:  }  
45:  /**************************  
46:  * Postorder tree display  
47:  ***************************/  
48:  void postorder(node_t *node)  
49:  {  
50:    if ( node == NULL)  
51:    {  
52:      return;  
53:    }  
54:    postorder(node->left);  
55:    postorder(node->right);  
56:    printf("%d\t",node->i);  
57:  }  
58:  /**************************  
59:  * Options for tree traversing  
60:  ***************************/  
61:  void display_tree()  
62:  {  
63:    int choice = 0;  
64:    printf("1.Preorder\n2.Inorder\n3.Postorder\nEnter choice or 0:");  
65:    scanf("%d",&choice);  
66:    switch(choice)  
67:    {  
68:      case 1:  
69:        preorder(root);  
70:        break;  
71:      case 2:  
72:        inorder(root);  
73:        break;  
74:      case 3:  
75:        postorder(root);  
76:        break;  
77:      default:  
78:        printf("wrong Choice\n");  
79:    }  
80:  }  
81:  /**************************  
82:  * Function to Insert data into tree  
83:  ***************************/  
84:  node_t *add_node(node_t *node,int data)  
85:  {  
86:    if( NULL == node )  
87:    {  
88:      node_t *node = (node_t *) malloc(sizeof(node_t));  
89:      node->left = NULL;  
90:      node->right = NULL;  
91:      node->i = data;  
92:      if ( NULL == root )  
93:      {  
94:        root = node;  
95:      }  
96:      return node;  
97:    } else {  
98:      if ( data > node->i)  
99:      {  
100:        node->right = add_node(node->right,data);  
101:      } else if ( data < node->i)  
102:      {  
103:        node->left = add_node(node->left,data);  
104:      }  
105:    }  
106:  }  
107:  /**************************  
108:  * Option to Insert data  
109:  ***************************/  
110:  void make_tree()  
111:  {  
112:    int data = 0;  
113:    do {  
114:      printf("Enter Data or '0' to Exit:");  
115:      scanf("%d",&data);  
116:      if ( data != 0 )  
117:      {  
118:        add_node(root,data);  
119:      }  
120:    }while(data != 0);  
121:  }  
122:  /**************************  
123:  * Delete Tree nodes  
124:  ***************************/  
125:  node_t *delete_tree(node_t *node,int data)  
126:  {  
127:    static node_t *cur = NULL;  
128:    node_t *temp1 = NULL,*temp2 = NULL;  
129:    if ( NULL == root )  
130:    {  
131:      printf("Tree is empty\n");  
132:      return NULL;  
133:    }  
134:    if ( NULL == node)  
135:    {  
136:      printf("Data %d Not found for delete\n",data);  
137:      return root;  
138:    }  
139:    /**  
140:     * Deleting root node  
141:     */  
142:    if ( data == root->i)  
143:    {  
144:      /*  
145:       * No chiled in root  
146:       */  
147:      if ( NULL == root->left && NULL == root->right)  
148:      {  
149:        free(root);  
150:        root = NULL;  
151:        return NULL;  
152:      }  
153:      /*  
154:       * Only right chiled in root  
155:       */  
156:      if ( NULL == root->left && NULL != root->right)  
157:      {  
158:        temp1 = root;  
159:        root = root->right;  
160:        temp1->right = NULL;  
161:        free(temp1);  
162:        temp1 = NULL;  
163:        return root;  
164:      }  
165:      /*  
166:       * Only Left chiled in root  
167:       */  
168:      if ( NULL != root->left && NULL == root->right)  
169:      {  
170:        temp1 = root;  
171:        root = root->left;  
172:        temp1->left = NULL;  
173:        free(temp1);  
174:        temp1 = NULL;  
175:        return root;  
176:      }  
177:      /*  
178:       * Both left and right child present in root  
179:       */  
180:      if ( NULL != root->left && NULL != root->right )  
181:      {  
182:        temp2 = root;  
183:        temp1 = root->right;  
184:        while(temp1->left != NULL)  
185:        {  
186:          cur = temp1;  
187:          temp1 = temp1->left;  
188:        }  
189:        if ( NULL == cur)  
190:        {  
191:          temp1->left = temp2->left;  
192:          root = temp1;  
193:          temp2->left = temp2->right = NULL;  
194:          free(temp2);  
195:          temp2 = NULL;  
196:          return root;  
197:        } else {  
198:          cur->left = temp1->right;  
199:          temp1->left = temp2->left;  
200:          temp1->right = temp2->right;  
201:          root = temp1;  
202:          temp2->left = temp2->right = NULL;  
203:          free(temp2);  
204:          temp2 = NULL;  
205:          return root;  
206:        }  
207:      }  
208:    }  
209:    /**  
210:     * Deleting any data from tree except root  
211:     */  
212:    if ( data > node->i)  
213:    {  
214:      cur = node;  
215:      delete_tree(node->right,data);  
216:    } else if ( data < node->i )  
217:    {  
218:      cur = node;  
219:      delete_tree(node->left,data);  
220:    } else if ( data == node->i)  
221:    {  
222:      /*  
223:       * Data found now delete the node  
224:       */  
225:      if ( node->left == NULL && node->right == NULL && cur == node)  
226:      {  
227:        free(node);  
228:        node = NULL;  
229:        return NULL;  
230:      }  
231:      if ( cur->i < node->i)  
232:      {  
233:        temp1 = node->left;  
234:        if ( NULL != temp1)  
235:        {  
236:          cur->right = node->left;  
237:          while(temp1->right != NULL)  
238:          {  
239:            temp1 = temp1->right;  
240:          }  
241:          temp1->right = node->right;  
242:        } else {  
243:          cur->right = node->right;  
244:        }  
245:      }  
246:      if ( cur->i > node->i)  
247:      {  
248:        temp1 = node->right;  
249:        if ( NULL != temp1)  
250:        {  
251:          cur->left = node->right;  
252:          while(temp1->left != NULL)  
253:          {  
254:            temp1 = temp1->left;  
255:          }  
256:          temp1->left = node->left;  
257:        } else {  
258:          cur->left = node->left;  
259:        }  
260:      }  
261:      node->left = node->right = NULL;  
262:      free(node);  
263:      node = NULL;  
264:    }  
265:    return root;  
266:  }  
267:  /**************************  
268:  * Search function  
269:  ***************************/  
270:  node_t *search_tree(int data)  
271:  {  
272:    node_t *temp = root;  
273:    while(temp != NULL && temp->i != data )  
274:    {  
275:      temp = (data > temp->i) ? temp->right : temp->left;  
276:    }  
277:    if ( NULL == temp)  
278:      return NULL;  
279:    return temp;  
280:  }  
281:  /**************************  
282:  * Main function to display tree options  
283:  ***************************/  
284:  main()  
285:  {  
286:    int choice = 0,data = 0;  
287:    node_t *node = NULL;  
288:    do {  
289:      printf("\n************* Tree ************\n1.Add\n2.Display\n3.Delete\n4.Search\nEnter Your Choice or Zero to exit:");  
290:      scanf("%d",&choice);  
291:      switch(choice)  
292:      {  
293:        case 1:  
294:          make_tree();  
295:          break;  
296:        case 2:  
297:          display_tree();  
298:          break;  
299:        case 3:  
300:          printf("Enter Data to delete:");  
301:          scanf("%d",&data);  
302:          root = delete_tree(root,data);  
303:          break;  
304:        case 4:  
305:          printf("Enter Data to Search:");  
306:          scanf("%d",&data);  
307:          node = search_tree(data);  
308:          if ( NULL == node)  
309:            printf("Data Not fount\n");  
310:          else  
311:            printf("Data Found :: %d\n",node->i);  
312:          break;  
313:        default:  
314:          printf("Wrong Choice\n");  
315:      }  
316:    }while(choice != 0);  
317:  }  

WAP to display all set bit position in a given 32-bits number

1:  main()  
2:  {  
3:    int i = 0x1234,pos = 1;  
4:    while(i)  
5:    {  
6:      if ( i & 0x01)  
7:      {  
8:        printf("%d\n",pos);  
9:      }  
10:      i = i>>1;  
11:      pos++;  
12:    }  
13:  }   

WAP to shift all one's at one side in a given 32-bits number. i.e num = 0xcccccccc o/p - 0xffff0000

1:  main()  
2:  {  
3:    unsigned int num = 0xcccccccc;  
4:    unsigned int res = 0,b1= 0,count=0;  
5:    printf("Num : 0x%x\n",num);  
6:    while(num)  
7:    {  
8:      if(num & 1)  
9:      {  
10:        b1 = (b1 << 1) | 1;  
11:        count++;  
12:      }  
13:      num >>= 1;   
14:    }  
15:    num = b1 << count;  
16:    printf("Result : 0x%x\n",num);  
17:  }   

WAP to swap adjacent bits in a given 32-bits number

1:  main()  
2:  {  
3:    int num;  
4:    printf("Enter No:");  
5:    scanf("%d",&num);  
6:    printf("rev = %d\n",(num>>1 & 0x55555555 | num<<1 & 0xaaaaaaaa));  
7:  }  

WAP to find number of set bits in a given 32-bits number

1:  main()  
2:  {  
3:    int num = 0x1fa12cde,count = 0;  
4:    while(num)  
5:    {  
6:      if(num & 1)  
7:      {  
8:        count++;  
9:      }  
10:      num = num >>1;  
11:    }  
12:    printf("Number of set bits = %d\n",count);  
13:  }  

WAP to swap two nibbles in a given number

1:  main()  
2:  {  
3:    unsigned int num = 0xfc;  
4:    num = (num>>4 & 0x0f) | (num<<4 & 0xf0);  
5:    printf("Result = 0x%x\n",num);  
6:  }   

WAP to toggle all bits in a given 32-bits number

1:  main()  
2:  {  
3:    unsigned int num = 0x4532fc1a; // Any 32-bits integer  
4:    unsigned int inv = i ^ 0xffffffff;  
5:    printf("inv = %x\n",inv);  
6:  }   

WAP to overlap the bits from one number to another given number if the overlapping bit position is given

1:  main()  
2:  {  
3:    int num1 = 0xffffffff;  
4:    int num2 = 0x12345678,c = 0;  
5:    int p1=0,p2=0;  
6:    int mask = 0;  
7:    // Enter the overlapping bits position  
8:    printf("Enter first overlapping bit position:");  
9:    scanf("%d",&p1);  
10:    printf("Enter second overlapping bit position:");  
11:    scanf("%d",&p2);  
12:    mask |= (1 << p1-1);  
13:    mask |= (1 << p2-1);  
14:    c = num2 & mask;  
15:    num1 |= c;  
16:    printf("After overlapping = %d\n",num1);  
17:  }  

WAP to toggle a bit at given position in given 32-bits number

1:  main()  
2:  {  
3:    int num = 0xfcd78f11;  
4:    int pos = 10;  
5:    num = num ^ (1<< pos-1);  
6:    printf("res = %d\n",res);  
7:  }   

WAP to increment a given number by one using bitwise operators

1:  main()  
2:  {  
3:    int num = 0,res = 0;  
4:    printf("Enter number\n");  
5:    scanf("%d",&num);  
6:    res = ~num;  
7:    num ^= (num & ~-~num)| (~num & -~num);  
8:    printf("Inc Num : %d\n",num);  
9:  }   

WAP to detect loop in a singly linked list

1:  void loop_detection()  
2:  {  
3:    list_t *slow = start;  
4:    list_t *fast = start;  
5:    while(slow != NULL && fast != NULL && fast->next != NULL)  
6:    {  
7:      slow = slow->next;  
8:      fast = fast->next->next;  
9:      if ( slow == fast)  
10:      {  
11:        printf("Loop detected\n");  
12:        return;  
13:      }  
14:    }  
15:    printf("No loop\n");  
16:    return;  
17:  }  

Find middle node of given singly linked list

1:  list_t * middle_node()  
2:  {  
3:    list_t *slow = start;  
4:    list_t *fast = start;  
5:    while(fast != NULL && fast->next != NULL)  
6:    {  
7:      slow = slow->next;  
8:      fast = fast->next->next;  
9:    }  
10:    printf("Middle Node is : %d\n",slow->data);  
11:    return slow;  
12:  }  

WAP to find common data position in two different given Singly Linked lists.

1:  void find_common_nodes_position(list_t *list1,list_t *list2)  
2:  {  
3:    int pos1=0,pos2=0;  
4:    list_t *temp1 = NULL;  
5:    list_t *temp2 = NULL;  
6:    for(pos1=1,temp1=list1;temp1;temp1=temp1->next,pos1++)  
7:    {  
8:      for(pos2=1,temp2 = list2;temp2;temp2 = temp2->next,pos2++)  
9:      {  
10:        if ( temp1->data == temp2->data)  
11:        {  
12:          printf("Data %d common at %d in list1 and %d at list2\n",  
13:                          temp1->data,pos1,pos2);  
14:        }  
15:      }  
16:    }  
17:    return;  
18:  }  

WAP to add all nodes value in a given SLL between the range from last i.e add all nodes form 2nd to 4th position from last.

1:  int sum_of_nodes_from_last(int pos1,int pos2)  
2:  {  
3:    int sum = 0;  
4:    int i;  
5:    list_t *temp = NULL;  
6:    for(i=1,temp = start;temp;temp = temp->next,i++);  
7:    pos1 = i-pos1;  
8:    pos2 = i-pos2;  
9:    printf("i = %d\n",i);  
10:    for(i=1,temp = start;temp;temp = temp->next,i++)  
11:    {  
12:      if ( i >= pos2 && i <= pos1)  
13:      {  
14:        sum += temp->data;  
15:      }  
16:    }  
17:    return sum;  
18:  }  

WAP to add all node value within a given range in SLL

1:  int sum_of_nodes(int pos1,int pos2)  
2:  {  
3:    int sum = 0;  
4:    int i;  
5:    list_t *temp = NULL;  
6:    for(i=1,temp = start;temp;temp = temp->next,i++)  
7:    {  
8:      if ( i >= pos1 && i <= pos2)  
9:      {  
10:        sum += temp->data;  
11:      }  
12:    }  
13:    return sum;  
14:  }  

WAP to find nth node from the last in a singly linked list

list_t *nth_node_from_last(int pos_from_last)
{
    int len_of_ll = 0;
    list_t *temp = NULL;
    for(len_of_ll = 0,temp = start;temp;temp=temp->next,len_of_ll++);
    // Length of LL is obtained
    len_of_ll -= pos_from_last;
    if ( len_of_ll <= 0)
    {
        printf("Position from last is out side the linked list range");
        return NULL;
    }
    for(temp = start;len_of_ll;temp=temp->next,len_of_ll--);
    return temp;
}

WAP to delete a node of singly linked list if only address on that node is given

1:  void delete_node(list_t *node)  
2:  {  
3:    list_t *temp = node;  
4:    if (NULL == temp->next)  
5:    {  
6:      // Last node  
7:      free(temp);  
8:      return;  
9:    }  
10:    // Any node other than last  
11:    temp = temp->next;  
12:    node->data = temp->data;  
13:    node->next = temp->next;  
14:    free(temp);  
15:    return;  
16:  }  

WAP to delete node in singly linked list when position and start pointer is given. Without using extra pointer

1:  typedef struct list_  
2:  {  
3:     struct list_ *next;  
4:     int data;  
5:  }list_t;  
6:  void delete_list(int pos,list_t *node)  
7:  {  
8:    if ( NULL == node)  
9:    {  
10:      printf("Position not found\n");  
11:      return;  
12:    }  
13:    if ( pos == 1)  
14:    {  
15:      while ( node->next->next != NULL )  
16:      {  
17:        node->data = node->next->data;  
18:        node=node->next;  
19:      }  
20:      node->data = node->next->data;  
21:      free(node->next);  
22:      node->next = NULL;  
23:      return;  
24:    }  
25:    delete_list(--pos,node->next);  
26:    return;  
27:  }  
28:  main()  
29:  {  
30:      delete_list(pos,start);  
31:  }   

WAP to reverse a singly linked list

1:  typedef struct abc  
2:  {  
3:    int a;  
4:    struct abc *next;  
5:  }abc;  
6:  M-1 : Using three pointers  
7:  void revrse_list()  
8:  {  
9:    abc *temp = NULL,*temp1 = NULL, *temp2 = NULL;  
10:    temp = start;  
11:    temp1 = temp->next;  
12:    temp2 = temp1->next;  
13:    temp->next = NULL;  
14:    while(temp1->next != NULL)  
15:    {  
16:      temp = temp1;  
17:      temp1 = temp2;  
18:      temp2 = temp2->next;  
19:      temp1->next = temp;  
20:    }  
21:    start = temp1;  
22:  }  
23:  M-2 : Using recursive  
24:  abc *reverse_list(abc *node)  
25:  {  
26:    abc *temp = NULL;  
27:    if ( node->next == NULL)  
28:    {  
29:      start = node;  
30:      return node;  
31:    }  
32:    temp = reverse_list(node->next);  
33:    temp->next = node;  
34:    return node;  
35:  }  
36:  main()  
37:  {  
38:    abc *temp = NULL;  
39:    temp = reverse_list(start);  
40:    temp->next = NULL;  
41:  }   

Behaviour of malloc() and free() functions

malloc() is vastly used in real time programing due to its contiguous allocation
of memory. So that fragmentation can be minimized.
But malloc() allocation itself causes sever of exception for programmer without showing significance error sometime.

1) Boundary of malloc()
int *ptr = (int *)malloc(sizeof(int)*10);

Above syntex of memory allocation represents that we are allocating 40 bytes of
contiguous memory to integer pointer ptr. as an result a size of 40 bytes chunk
is reserverd in heap to provide data read/write for pointer ptr.

A programmer can write data upto 40 byte of boundary legally. But
case 1: Legal writing
   
    for(i = 0 ; i<10 ; i++)
    {
        ptr[i] = i;
    }
   
    This legal writing will not cause any error or fault. Allowed by compiler
   
case 2: Illegal writing
   
    for(i = 0; i < 20 ; i++)
    {
        ptr[i] = i;
    }
   
    This writing is illegal. because it writes beyond the boundary of malloc.
But is still allowed by compiler.

2) Role of free() function in exceptional cases

Free function frees the memory allocated by the malloc() or calloc() or
realloc() functions. And makes it reusable for further memory allocation.
In above example free() functions play a different role

case 1: Legal writing
   
    for(i = 0 ; i<10 ; i++)
    {
        ptr[i] = i;
    }
    free(ptr);

    In this case free() will simply free the memory without any exception.
case 2: Illegal writing
   
    for(i = 0; i<20 ; i++)
    {
        ptr[i] = i;
    }
    free(ptr);
   
    In this example free() function will lead to an exception i.e SIGABRT. This
happens because free() function detects the extra byte has been written beyond
the boundry.

Observation : Here one thing is need to observe that using malloc() is a good
programing practice but in some of cases programmer probably does not notice on
the writing limit of malloc() and eventually ends with SIGABRT. If programmer
debugging the code they will cross check the memory allocation and double free()
scenario. It seems all right because code looks healthy. this kind of logical
issue resolved by examine writing limitation of malloc().

3) Does free() function really frees the memory
To better understand free() function once need to know how malloc() allocates
the memory. malloc() function passes the size of memory to allocate to the
system where kernel allocates required block for data. but kernel adds one
additional block of information before each allocation. That block called
meta-data and it contains mainly information about size of data that is
allocated free flag(0 = used, 1= free) and address of next meta-data.
    Whenever free() functions tries to free a memory block it Enables the free
flag in meta-data structure. That means block of specific size is freed and
available for next time of allocation. Here the question is what happen next to
the data block can be easily understood by following examples.
case 1:
    int *ptr = (int *)malloc(sizeof(int)*5);
    int i = 0;
    for(i = 0; i<5 ; i++)
    {
        ptr[i] = i;
    }
    for(i = 0; i<5 ; i++)
    {
        printf("%d\t",ptr[i]);
    }
    printf("\n");
    free(ptr);
    for(i = 0; i<5 ; i++)
    {
        printf("%d\t",ptr[i]);
    }
    Output -
   
    0    1    2    3    4   
    0    0    2    3    4
[NOTE : This out may vary compiler wise]   
    free() function does not affect the data block. It simply makes it
available for next allocation.

This happens because of enabling free flag in meta-data. But what does it
really means enabling and disabling a flag. Whenever free() called to free a
dynamic memory it checks the meta data status and size of memory allocation.

Memory allocation happens by two mechanism in kernal space. if malloc is
allocating memory less then 135168 bytes ( approx figure, may vary), then it
uses sbrk() function to allocate memory. This allocated memory does not free
completely. programmer should assign NULL to the pointer after freeing it.
though this type of memory boundary is not well defined so sometime it is
observed that program can write beyond of allocation without showing any fault.
free happens only enabling the free flags in meta data.
But if memory to be allocated accedes 135168 bytes , system uses mmap() to
allocate memory. This kind of memory allocation very constrain to its boundary.
user can not write of use these memory after freeing it. because munmap is used
to free  these memory.
To check memory allocation region by malloc we have one command in gdb.

(gdb) print or p malloc_stats(<address or pointer variable >)

output:
(gdb) p malloc_stats (0x7ffff7a9ea70)
Arena 0:
system bytes     =     135168
in use bytes     =          0
Total (incl. mmap):
system bytes     =     135168
in use bytes     =          0
max mmap regions =          0
max mmap bytes   =          0
$2 = -136494720
(gdb)

Here we can see there are two regions defined in this out put 1. System Bytes
2. mmap regions

Ellipses Operator (. . .)

This operator is used to represent various number of parameters involve. This is mainly used in function arguments , when the number of arguments is not known.

Ex -
int foo(int i, int j, . . .);

But we can use ellipses operator in other part of coding also.

In switch case

main()
{
       --------
       --------
       switch(3)
       {
               case 1 ... 4:
                    printf("Option is between 1 to 4);
                    break;

               case 5 ... 9:

                    printf("Option is between 5 to 9);

                    break;

        }

}

In array

Ellipses operator used in array initialization also. Using this operator we can partially initialize our arrays.

Ex - 

main()

{

         int arr[] = { [0 ... 4] 4, [5 ... 9] 5};

         printf("arr[0] %d\n", arr[0]);

         printf("arr[6] %d\n", arr[6]);

}

o/p - 

arr[0] 4

arr[6] 5

Partially initialize the array 

main()

{

        int arr[10] = { [3]5, [1] = 4, [4] 3, [0] = 0 };

         printf("arr[0] %d\n", arr[0]);

         printf("arr[3] %d\n", arr[3]);

         printf("arr[4] %d\n", arr[4]);

}

o/p - 

arr[0] 0

arr[3] 5

arr[4] 3

Spin locks, Semaphore and Interrupt disabling Protection for kernel Control Paths

For kernel choosing synchronization primitives depends on the kind of kernel control path access the data structure



Kernel control paths accessing 
the data structure                             UP protection              MP further protection

Exceptions                                                Semaphore                            None
Interrupts                                                  Local interrupt disabling        Spin lock
Deferrable functions                                  None                                     None or
                                                                                                               spin lock
Exceptions + Interrupts                            Local interrupt disabling        Spin lock
Exceptions + Deferrable functions            Local softirq disabling           Spin lock
Interrupts + Deferrable functions             Local interrupt disabling        Spin lock
Exceptions + Interrupts +
Deferrable functions                                 Local interrupt disabling         Spin lock

UP - Uni-Processor, MP - Multiprocessor 

Protecting Data Structure from Exception Handler

Protecting Data Structure from Interrupt Handler

Protecting Data Structure from Deferrable Functions

Source : Daniel P. Bovet & Marco Cesati Book

Optimization Techniques that can improve your program performance

Program performance depends basically on two major areas one is memory and another is time. Programmer should aware of writing memory constrain and time constrain programs. Most of the optimization done at compilation level itself and some of the done at running time. Here we discuss on very small areas that really affecting our code performance.
 
    Here i am sharing some of the techniques for beginners, which i learnt on my coding experience and reference taken from other sources. This optimizations techniques

Memory Optimization

• Memory allocation to your variables is a tactic. If memory has to be given to our array or string variables we follow static and dynamic memory allocation techniques. 
• Static memory allocation has many issues , static memory allocate at compile time so we can not control the memory wastage if we were not used this memory efficiently. On the other hand life time of static memory depends on the program and function scope based on the memory allocation area. so before giving static memory to variables you should must have exact calculation of your requirements. 
• Once memory has allocated statically it will occupy stack and other storage area till life time of program. This kind of memory occupancy will lead program in to huge memory wastage it can not provide memory reusability. 
• Whereas Dynamic allocation allows program to allocate memory at run time and it can be freed after using it. Continually allocation of memory and not freeing them lead to code into memory overflow condition. so it is programmer should free dynamic pointers intelligently.
• Dynamic memory allocation where provides exact size of memory on the other hand it make cause memory leak type of serious issues.
• If it is memory allocation for structures or array of structures we should must go for dynamic memory allocation.
• If application sending any packets to network through sockets. they use one buffer to encode the packets into single body. Most of the programmer uses static memory buffers, if they use dynamic also they don't free after sending this on network, that should be freed.
• Be careful on choosing of data types for variables. i.e if variable range is between 0-255 then for this int32 or int64 data type is not required.
• Arrange variables in a certain orders like int, pointer, floating points and so forth. Because some of the compilers provide further level of optimization, it can improve code performance.
• Auto variables are stored in stack, if they are many then programmer has to move some of the auto variables in to different memory areas. by placing them in to global or using register storage class or if possible you can move them into heap.
• As much as try to avoid declaring any variable inside the loop. if it is not essential.

Time optimization 

  Code timing performance is totally depends on how the code is written

• Loop, nested loop they are major factors which causes delay in execution.
• Loop performance depends on the several parameters. Number of iteration, try to avoid infinite loops. Restrict the number of iteration, put exact condition for iteration.    
• put constant calculation out side the loop. 
• use bit-wise operator for certain type of arithmetic operation. ex- divided by two, multiplication of 2.
• Use look-up tables for trigonometric and logarithmic operations.
• try to avoid direct function calling within a loop use call-back functions instead.
• Make the loop blocking type. blocking loops improve the CPU performance.
• Always place data reading at the top of the loop and data writing at the end of the loop.  
• Use inline functions that reduces function calling over head but increases size of code.
• use for, while and do while based on the compiler. because compiler decides the efficiency of loops.        
• if else can be replaced by switch() if four or more than four items are there, then programmer can go for switch().

source: web and own experience 

Volatile keyword in C

Volatile is a type qualifier. It stop compiler to optimize certain area of code and prevent compiler to assume value of a variable hasn't changed. so compiler leave that segment code without optimized.
     here is one example from #http://en.wikipedia.org/wiki/Volatile_variable

Without Volatile

Before compilation

static int foo;
 
void bar(void) {
    foo = 0;
 
    while (foo != 255)
         ;
}

Optimizing compiler observer that there is no other possible to change the value stored in foo. so compiler take the default value 0 and optimize the loop in to infinite .
After compilation

void bar_optimized(void) {
    foo = 0;
 
    while (true)
         ;
}

With Volatile

static volatile int foo;
 
void bar (void) {
    foo = 0;
 
    while (foo != 255)
        ;
}

Here compiler will not assume any value and it will let the foo variable for the system to change the value.

Volatile is a type qualifier not a storage class so it does not change the area of storage

In kernel
Volatile is used in optimization barrier primitives. In Linux barrier() macro is used, which acts as an optimization barrier. barrier() macro defined as-

/* Optimization barrier */
/* The "volatile" is due to gcc bugs */
#define barrier() __asm__ __volatile__("": : :"memory")

The volatile keyword disallow the compiler to reshuffle the asm instruction with the other instructions of the program.
Above example is taken from one of the kernel synchronization so called memory barrier.

Volatile keyword also allow access to memory mapped devices, allow usage of variable between set jump and long jump

Why Virtual Memory ?

Whenever we run several processes simultaneously, they run successfully as long as physical memory addressing all the processes. sometime process size may exceed to the available physical memory limits , then the corresponding process is thrown out from the process queue, that should not happen in real.
       Our physical memory is very limited and of course expensive. so Virtual provides that provision in which we can run multiple process at the same time with being worried about the physical memory size. virtual memory provides a logical layer between memory requested by the Process and Memory Management Unit(MMU). Virtual memory allows each process to use subset of available physical memory.
     This all possible because of paging technique. Paging provides a memory translation between virtual address to physical address.        

Synchronization Techniques Used in kernel

Here are all the synchronization technique used by kernel programmers 

1. Per CPU Variable
2. Atomic Operation
3. Memory Barrier
4. Spin Lock
5. Semaphore
6. Seqlocks
7. Local Interrupt disabling
8. Local Softirq disabling
9. Read-Copy-Update (RCU)

What is dereferencing of a pointer?

Dereference operation means indirect operation. In pointers, pointer variable holds the address of similar kind of variable.
      Ex- int *p;
           'p' is a pointer to integer which holding the address of variable
     int i=10;
         when we want to retrieve value pointed by pointer variable 'p', We use *p to get the value so in this case we are not directly accessing the value of i, but we are indirectly accessing through pointer means dereferencing the pointer.  
      

THREAD PRIORITY

Priority Range in threads

0 to 63 consider as thread priority range. which is used by the system and users.

0- This is reserved for null threads for the idle mode.

1-23 - This range of priority used by kernel thread, user thread and servers.

24-32 - Used by kernel thread and system server. i.e server with portserv capability

32-63 -  Reserved for real-time threads running on the kernel side.

Deadline Range 

Deadline (ms)                                                      Thread Priority

>100                                                                          24 - 26

>20                                                                            27

2 - 20                                                                          28 - 31

KERNEL MEMORY ALLOCATOR (KMA) ALGORITHMS

1) Resource map allocator
2) Power-of-two free list
3) McKusick-Kernel allocator
4) Buddy System
5) Mach's zone allocator
6) Dynix Allocator
7) Solaris's Slab allocator

Softirqs, Tasklets and Work Queue

Both are diferrable functions and they also called software interrupt. softirqs and tasklets are strictly correlated. tasklets are implemented on top of softirqs.

Softirqs are defined at compile time whereas tasklets are initialized and allocated at run time while loading the kernel module.

Softirqs are reentrant functions so it can run concurrently on the several CPUs. Spin loack techniques generally used to protect softirqs data structures. whereas tasklets run under restriction of kernel.

Tasklets schedule task for future purpose

Work Queue is similar to Tasklets, It also schedule task for future purpose. Both are use for the similar purposes, but tasklets are excute in interrupt context whereas work queue executes in process context.
    Work queue allow kernel function to be activated and later executed by the kernel thread(worker thread).      

  

Deferrable Functions

Defferrable function is non-urgent interruptible kernel functions. Softirqs and Taskets are diferrable functions.