Thursday, December 3, 2009

Thread, semaphore, signals example in C

I got this question by chance. It was about creating 2 threads that would run in such a way that if one thread prints a value i, the next thread should print a value i+1.

The pthread_create() function is used to create a new thread, with attributes specified by attr, within a process. If attr is NULL, the default attributes are used. If the attributes specified by attr are modified later, the thread's attributes are not affected. Upon successful completion, pthread_create() stores the ID of the created thread in the location referenced by thread.

The pthread_join() function suspends the execution of the calling thread until the thread identified by the thread identifier terminates, either by calling pthread_exit() or by being canceled.

For our given problem we need the increment and print action for each thread to be done as atomic actions. No context switch should happen these operations. If that happens we may not get the desired result. In case a context switch happens after a read in thread one, then thread 2 might print the incremented value and thread 1 will print the old value, and there are other possibilities as well.Hence the use of semaphore cannot be avoided.

Use of SIGINT (Cntr+C) is used to quit the program.


#include < stdio.h >
#include < pthread.h >
#include < semaphore.h >
#include < signal.h >

sem_t semname;
int qval=1;

void *func1(void *arg) {
while(qval) {
sem_wait(&semname);
printf("Thread one prints # %d\n",(*(int *)(arg))++);
sem_post(&semname);
sleep(1);
}
}
void *func2(void *arg) {
while(qval) {
sem_wait(&semname);
printf("Thread two prints # %d\n",(*(int *)(arg))++);
sem_post(&semname);
sleep(1);
}
}
void quit() {
qval=0;
}


main() {
signal(SIGINT,quit);
sem_init(&semname,0,1);
int i=0;
pthread_t thread1,thread2;
pthread_create(&thread1,NULL,func1,&i);
pthread_create(&thread2,NULL,func2,&i);
pthread_join(thread1,&i);
pthread_join(thread2,&i);
printf("\nQuiting...\n");
return 0;
}

Thanks
Layman

Wednesday, December 2, 2009

Trie datastructure C example

This post is about the trie datastructure. Here we are trying to do a lexicographic trie. It can store all the words of a dictionary in an efficient manner. In the lexicographic trie datastructure each node has 26 pointers. Each pointers represent a letter. So to store "lay" , the system will first create a path from pointer for letter l to a new node(call it ptr). Then it makes a new node and makes the ptr's pointer for letter a point to this new node and so on. The advantage is that many words start with the same substring (eg new and neo). So here the common part "n" & "e" is stored only once. Hence lesser storage space and efficiency. In terms of computational speed searching is much faster as each time we can eliminate 25 links and hence it must be log n to the base 26. This is used commonly to implement dictionaries etc.
See the code now.

CODE

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

struct diction
{
struct diction *alpha[26];
int flag;
};
typedef struct diction dic;

dic *root;
int maptoptr(char a)
{
char j='a';
int i;
for(i=0; i<26 a="'a';" root="(dic" i="0;i<26;i++,a++)" t="maptoptr(a);">alpha[t]=NULL;
}
}


void insert(char ip[])
{
dic *ptr=root;
int t;
int f=0;//false
int i=0;

t=maptoptr(ip[i]);
while(ptr->alpha[t]!=NULL && f==0) //not finished searchin and if there is a path with current letter
{
if(ip[i]=='\0' && ptr->flag==1)
{
f=1;//true
}
else
{
ptr=ptr->alpha[t];
i++;
}
t=maptoptr(ip[i]);
}
if(f==1)
{
printf("Already exists\n");
}
else
{
dic *ptr1=NULL;
char temp='a';
int j;
while(ip[i]!='\0')
{
temp='a';
ptr1=(dic *)malloc(sizeof(dic));
for(j=0;j<26;j++,temp++) t="maptoptr(temp);">alpha[t]=NULL;
}
ptr1->flag=0;
t=maptoptr(ip[i]);
ptr->alpha[t]=ptr1;
ptr=ptr1;
i++;
}
ptr->flag=1;
}
}
void search(char ip[])
{
int i=0,f=1;
int t;
dic *ptr=root;
while(ip[i]!='\0'&& f==1)
{
t=maptoptr(ip[i]);
if(ptr->alpha[t]==NULL)
{
f=0;
i++;
break;
}
ptr=ptr->alpha[t];
i++;
}
if(f==1 && ip[i]=='\0' && ptr->flag==1)
printf("\nFound\n");
else
printf("\nNot found\n");
}

void bt_free(dic *ptr)
{
int i=0,t;
char a='a';
if(ptr==NULL)
return;
for(i=0;i<26;i++,a++) t="maptoptr(a);">alpha[t]!=NULL)
{
bt_free((ptr->alpha[t]));
}
}
free(ptr);
}
main()
{
char a[25];
printf("Enter the word to insert : ");
gets(a);
createroot();
insert(a);
printf("Enter another word to insert : ");
gets(a);
insert(a);
printf("Enter the word to be searched : ");
gets(a);
search(a);
bt_free(root);
}




OUTPUT

$ ./a.exe
Enter the word to insert : layman
Enter another word to insert : laymansviews
Enter the word to be searched : layman

Found