using dup,fork,exec communicate b/w process

what happens when ls -l | head -5 | wc is issued in shell. the shell creates processes and uses pipes between them to pass the output 2 other process. to implement this programmatically  we need to map the pipe to stdin/stdout .

1) create 2 pipes. say p1 and p2 .
2)create child process using fork . dup the write end of p1 with stdout and exec with ls -l
3)create other child process to receive ouput of ls -l here. we can do this by using dup with read end of p1 with stdin. to send output to wc again we need to dup write end of pipe p2 with stdout. exec with head -5 process
4)in parent process, receive the output from head -5 command. do this by using dup() on read end of pipe p2 with stdin and exec. output will be displayed on screen .

Program to implement  ls –l | head -5 | wc

#include

#include

#include

#include

#include

#include

#define MAXLEN 1024

  int main()

        {

        int p1[2],p2[2];

        int outfd,infd;int old_infd,old_outfd ; // save old descp

        int pid,pid2,pid3,flag;char str[MAXLEN];

        pipe(p1);

         if(pipe(p2) < 0)

        perror("cannot create pipe p2");

        outfd=p2[1];

        infd=p2[0];

        old_infd=dup(0); // save old descriptors

        old_outfd=dup(1);

        switch(pid=fork()) {

        case 0:

                close(1);dup(p1[1]);

                close(p1[0]);

                dup(p1[1]);

                execl("/usr/bin/ls","ls","-l",NULL);

                break;

        case -1:

                perror("cannot create process");

                break;

        default:

                sleep(2);

        }

        switch(pid3=fork()){

        case 0:

                close(0);

                dup(p1[0]);

                close(p1[0]); close(p1[1]);

                dup2(old_outfd,1);

                close(1);

                dup(outfd);

                close(infd); // close pipes

                close(outfd);

                execl("/usr/bin/head","head","-5",NULL);

                break;

        default:

                sleep(2);

                dup2(old_infd,0);

                close(0);

                dup(infd);

                close(outfd);close(infd);

                 execl("/usr/bin/wc","wc",NULL);

        }

        return 1;

        }

binary search tree - eliminate duplicates in array

binary search tree is best algorithm in eleminating duplicates in array.

algorithm:
step 1) construct root node with 1st element in array
step 2) scan next element in array say elem and compare with root node of tree. node=tree
 step 3) if elem < node->data   and there is no left node in tree ,
               then insert elem in left node
              else repeat step3 by node = node -> left ;
step 4)  if elem > node->data  and there is no right node in tree ,

               then insert elem in right node

              else repeat step 4 by node=node->right.

 step 5) if elem == node->data , then there is duplicate in array.

the advantage of this algorithm is no need to traverse through all elements in array, duplicate element can be found once we reach it .

the worst case of this algorithm is when duplicate element is at the end of array.

C program for binary search:


#include "stdafx.h"
#include

typedef struct node{
int data;
node *left;
node *right;
}tree;

tree *t1=NULL,*t2=NULL, *t4=NULL, *root=NULL ;
int i=0;
void construct_tree(int *p,int count);
void insert(tree *t,int data);
//void insert_right(tree *t,int data);

int main(int argc, _TCHAR* argv[])
{
 int a[100]; int count=0;
printf("\n enter how many nodes for numericals");
scanf("%d",&count);
printf("\n enter numericals");
for(int i=0;i < count;i++)
scanf("%d",&a[i]);
construct_tree(a,count);
return 0;
}

void construct_tree(int *p,int count)
{
//printf("%d\t",p[i]);
root=new tree();
root->data=p[0];
root->left=NULL;
root->right=NULL;
for(t4=root,i=1;i
insert(t4,p[i]);
} // end func

void insert(tree *temp,int data){
if(data < temp->data ){
if(temp->left == NULL){
tree *t2=new tree();
t2->data=data;
t2->left=NULL;
t2->right=NULL;
temp->left=t2;
}
else
insert(temp->left,data);
}
else if(data > temp->data){
if(temp->right == NULL){
tree *t2=new tree();
t2->data=data;
t2->left=NULL;
t2->right=NULL;
temp->right=t2;
}
else
insert(temp->right,data);
}
else if(data == temp->data )
printf("\n %d duplicate found",data);
     // end else
}