Wednesday, May 19, 2010

How to use <conio.h> with GCC

This article will teach you how to use <conio.h> header file while programming in C under linux environment with GCC, and getting unbuffered input from the user.

Most of the students are taught C/C++ with Turbo C/C++ IDE in schools. Turbo C has a header file(unspecified in ANSI standard) <conio.h> with which programmer can program for unbuffered input using functions like getch(). Also there are other functions like gotoxy() etc. which work perfect in DOS environment with Turbo C.
After they learn about linux, and then GCC they start practicing in linux. If you are such an student, read on. This will be handy for you.
At some point of time you will write a program in which you want interactive user input from the user. Interactive in the sense that you want an action to be performed as soon as a key is pressed. But since standard library function getchar() buffers the input until ENTER key is pressed, it will be quite irritating for you. So, you'll miss your <conio.h> header file that you used in Turbo. Don't worry. I faced the same problem and I ran around like everything to find a soluion. And finally, I found a solution!!!

Solution
Just download the libconioh from this link
Install it. Here are the steps(I'm considering Ubuntu as the example):
1. Copy the downloaded archive to your home folder
2. Open the terminal, by pressing Alt+F2 and typing xterm and pressing enter.
3. Become root by typing
sudo -s
and supplying your password.
4. Type

tar -zxvf libconio-1.0.0.tar.gz
and press enter to extract the archive. To make the typing easy you may press the <tab> key on your keyboard after typing l of libconio-1.0.0.tar.gz for autocompletion of filename.
5. Now enter into the extracted directory by typing
cd libconio-1.0.0
and pressing enter.
6. Install the library by typing these commands one after another's execution.
./configure

make

make install 
 Now the library has been installed. How to use it for programming?
Just #include <conio.h> in your program. And when compiling your program(eg. myprogram.c in current working directory) using gcc give the library's detail to the linker like this:
gcc myprogram.c -lconio
You will get the a.out file if your program doesn't have any errors.
Execute it and enjoy!
./a.out
But what did that -lconio did? See, in gcc the source files and object library files can be linked by specifying them back to back. Like:
gcc file1.c file2.c lib1.a lib2.a
In linux the library files are with .a extension and they are stored in /usr/lib/ directory with the name format lib<library_name>.a . So when you installed libconioh it copied a file, named libconio.la to the /usr/lib directory. Now you can compile and link your program that uses conio.h by this command
gcc myprogram.c /usr/lib/libconio.a
The -l switch has been provided as a shortcut for your convenience. This -l makes conio to be read as /usr/lib/libconio.a hence when yo typed gcc myprogram.c -lconio it was interpreted as gcc myprogram.c /usr/lib/libconio.a . Now thats sweet! Isn't it?
   
Here is a sample program that reads characters from the keyboard, displays the character just next to it(for example, if u enter b it will display c)  and exits only when you press the small a key.

#include <conio.h>
int main(){
char c;
while((c=getch())!='a'){
putchar(c+1);
}
putchar('\n');
return 0;

Sunday, May 16, 2010

Implementing a list data structure using an array, in C


Long time since I interacted with C. I thought IIIT-A interviews are coming closer and they also have a coding test in which they ask to write programs, so I went off to revise data structures with C. I planned to study lists, linked lists, stacks, queues, trees and graphs and implement them all using C.
The first one on the target was lists. So I started off and wrote a lists demo program. I'm posting the program below. It may come handy to you if you are a student searching something for your assignment.
Compile it in GCC. You may also compile on Windoze but I haven't tested on Windoze.
The program allows to:
  1. Print all the values stored
  2. Insert a new value at specified position
  3. Insert a value at the end of the list(append)
  4. Delete a value at specified position
  5. Delete all occurences of a value from the list
  6. Find all occurences of an item
  7. Empty the list
I've also made the text colourful using the escape sequences for colours. Those \33[31m things are for colouring the text displayed while executing the program.

Here's the program.


#include <stdio.h>
#define SIZE 65536
#define ENDMARKER -65535

int data[SIZE];

int print_all();
int add(int pos, int datum);
int delete(int pos);
int append(int datum);
int delall(int datum);
int find(int datum);
int print(int pos);
int empty();

int main(){
int pos, datum;
int option;
data[0]=ENDMARKER;
printf("\n\33[36mWelcome to the list data structure demonstration program! The program starts with a list of integers(initially empty). Through this program's interface, you can insert items into the list at desired positions, or at the end; delete an item from the list from an specific position, or all occurences of an item from the list; find the position(s) of an item in the list; view all the items of the list; view an item stored at a particular position; or you may also empty the list.\n");
while(option!='9'){
printf("\n\33[32mMenu\n----\n");
printf("1. View all the items");
printf("\n2. Add an item at a given position");
printf("\n3. Add an item at the end of the list");
printf("\n4. Delete an item at a given position");
printf("\n5. Delete all occurences of an item value");
printf("\n6. Print an item at the given position");
printf("\n7. Find all the occurances of an item");
printf("\n8. Empty the list.");
printf("\n9. Exit\nEnter your choice and hit the enter key:");
scanf("%d",&option);
switch(option){
case 1:
print_all();
break;
case 2:
printf("\n\33[33mPlease enter the position where item should be inserted: ");
scanf("%d",&pos);
printf("Please enter the item value to be inserted: ");
scanf("%d",&datum);
add(pos, datum);
break;
case 3:
printf("\n\33[33mPlease enter the item value to be inserted at the end of the list: ");
scanf("%d",&datum);
append(datum);
break;

case 4:
printf("\n\33[33mPlease enter the position of the item to be deleted: ");
scanf("%d",&pos);
delete(pos);
break;
case 5:
printf("\n\33[33mPlease enter the item to be deleted from the list: ");
scanf("%d",&datum);
delall(datum);
break;
case 6:
printf("\n\33[33mPlease enter the position of the item whose value is to be printed: ");
scanf("%d",&pos);
print(pos);
break;
case 7:
printf("\n\33[33mPlease enter the item value whose position is to be found: ");
scanf("%d",&datum);
find(datum);
break;
case 8:
empty();
break;
case 9:
printf("\n\33[34mThank you for using this program. Have a nice time!\n\33[37m");
return(1);
break;
default:
printf("\n\33[31mInvalid use. Please retry.\n");
break;
}
}
printf("\33[37m");
return (0);
}

int num_items(){
int num=0;
int i;
for(i=0;data[i]!=ENDMARKER;i++);
return i;
}

int print_all(){
if(data[0]==ENDMARKER){
printf("\n\33[31mNo items could be found in the list.\nYou may insert some data first, before experimenting.\n");
return 0;
}
printf("\nFollowing items were found in the list:\n\n");
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
int i;
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int add(int pos, int datum){
if((pos>num_items()) || pos<0){
printf("\n\33[31mYou can't enter an item at this location because the list is full upto %d position. You can enter items from 0th position upto %dth position.\n",num_items(),num_items());
return (0);
}
data[num_items()+1]=ENDMARKER;
int i;
for(i=num_items();i>=pos;i--){
data[i]=data[i-1];
}
data[pos]=datum;
printf("\nThe item %d has been successfully inserted at the position %d.\nThe modified list is as follows.\n\n",datum,pos);
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int append(int datum){
data[num_items()+1]=ENDMARKER;
data[num_items()]=datum;
printf("\nThe item %d has been successfully appended to the list.\n The modified list is as follows.\n\n",datum);
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
int i;
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int delete(int pos){
if((pos>num_items()) || pos<0){
printf("\n\33[31mThat location doesn't hold any data value. Please enter a location that contains a value. Locations from 0 up to %d hold data values.\n",num_items());
return (0);
}
if(num_items()==0){
printf("\n\33[31mThe list is empty. No deletion possible.\n");
return 0;
}
int i;
for(i=pos;i<=num_items();i++){
data[i]=data[i+1];
}
data[num_items()]=ENDMARKER;
printf("\nThe item stored at the position %d has been successfully deleted.\n The modified list is as follows.\n\n",pos);
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int delall(int datum){
int i;
if(num_items()==0){
printf("\n\33[31mThe list is empty. No deletion possible.\n");
return 0;
}
int found=0;
for(i=0;i<=num_items();i++){
if(data[i]==datum){
found=1;
break;
}
}
if(found==0){
printf("\n\33[31mThe requested item wasn't found in the list. Deletion not possible.\n");
return (0);
}
for(i=0;data[i]!=ENDMARKER;i++){
if(data[i]==datum){
int j;
for(j=i;data[j+1]!=ENDMARKER;j++){
data[j]=data[j+1];
}
data[j]=ENDMARKER;
i--;
}
}
printf("\nAll the occurences of %d have been deleted from the list. The modified list is as follows:\n\n",datum); 
printf("\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;data[i]!=ENDMARKER;i++){
printf("%8d\t%4d\n",i,data[i]);
}
printf("\n");
return 1;
}

int find(int datum){
int i;
if(num_items()==0){
printf("\n\33[31mThe list is empty.\n");
return 0;
}
int found=0;
for(i=0;i<=num_items();i++){
if(data[i]==datum){
found=1;
break;
}
}
if(found==0){
printf("\n\33[31mThe requested item wasn't found in the list.\n");
return (0);
}
printf("\n\33[35mPosition\tItem\n");
printf("--------\t----\n");
for(i=0;i<=num_items();i++){
if(data[i]==datum)printf("%8d\t%4d\n",i,data[i]);
}
return 1;
}

int print(int pos){
if(num_items()==0){
printf("\n\33[31mThe list is empty.\n");
return 0;
}
if(pos<0 || pos>=num_items()){
printf("\n\33[31mThats an invalid location.\n");
return 0;
}
printf("\n\33[35mPosition\tItem\n");
printf("--------\t----\n");
printf("%8d\t%4d\n",pos,data[pos]);
return 1;
}

int empty(){
if(num_items()==0){
printf("\n\33[31mThe list is already empty.\n");
return 0;
}
data[0]=ENDMARKER;
printf("\nThe list has been successfully emptied.\n");
return 1;
}

Tuesday, May 11, 2010

Internet Connection Sharing through WiFi with Ubuntu PC as a gateway

The Problem

I have Ubuntu installed on my notebook computer(from now onwards, I will call it host computer in this post) which has a wired ethernet connection to a broadband internet service provider. I want to have a WiFi network broadcast in my room using my host computer so that any other notebook(guest) or smart phone with WiFi capability in the vicinity can connect to the broadband internet with host notebook working as a gateway.

The solution 

I had this problem from long ago since I wanted my broadband to be shared on my Sony Ericsson P1i. and I searched whole of the internet to find a solution but none actually worked.
Today after some fiddling I finally made my P1i to hook to the broadband with Ubuntu notebook working as a gateway.

This tutorial I am presenting has been tested on Ubuntu 10.04 Lucid Lynx and works perfectly fine. I can't guarantee it to work on earlier distributions because I myself had seen funny characters in WiFi network search list in P1i on 9.10 Karmic Koala and it never worked for me.

So, lets proceed.

1. Turn on your notebook's WiFi if there's a dedicated switch to turn it on. On my Fujitsu Siemens Amilo Si 3655 notebook, WiFi can be turned on using Fn+F1 key combination.

2. Click on the Network Manager icon(which looks like ) in the notification area and click Create New Wireless Network...

3. In the dialog box that pops up, put the network name as anything(I put WLAN). Set Wireles Security as WEP 40/128-bit key. In the Key box, enter any five digit number(I entered 31323). Click Create.


4. Now right click on the Network Manager icon and click Edit Connections... In the Network Connections dialog box that pops up, go to the Wireless tab. Click WLAN(or the network name you had provided) and click Edit.


5. In the Edit WLAN dialog box that opens up, set the Mode as Ad-hoc. Make sure the Connect Automatically checkbox is checked and in the IPv4 Settings tab, and Method is set to Shared to other computers. Now click Apply.

Your network is ready!!! Congrats!!! But thats only 50 percent of the hurdle complete. You might have reached this far several times using other tutorials and how tos available on the net. Lets proceed through to get the configuration details for the client pc/notebook/smart phone.

6. Open a terminal(for eg. by pressing Alt+F2 then typing xterm and pressing enter). In the terminal type ifconfig and press enter. Scroll down tothe place where wlan0 is written. Beside that, in the second line you will see three things viz. inet addr, Bcast and Mask. Note these things somewhere safely. In my case inet addr is 10.42.43.1 and Mask is 255.255.255.0. No need to note Bcast.

7. Use the following manual configuration details for the client system:

IPv4 Addr: 10.42.43.2(for a yet another machine use 10.42.43.3 and so on...)
Subnet Mask: 255.255.255.0
DNS Address1: 208.67.222.222
DNS Address2: 208.67.220.220

After doing all this above you may notice that the client computer connects to net successfully but the host computer isn't able to access any website. Thats because the network manager blanks the DNS records set in /etc/resolv.conf

To solve this, type

sudo gedit /etc/resolv.conf

in any terminal and there append

nameserver 208.67.220.220
nameserver 208.67.222.222

and save the file. Afterwards you will be able to surf the web on gateway computer as well, normally.

You may notice that the network manager blanks out /etc/resolv.conf every now and then and you've to manually edit it and add nameservers. This is a very common problem faced by GNOME users. To get rid of this just type the following command in terminal and press enter.

chattr +i /etc/resolv.conf



Now I am going to explain how did I connect my P1i to this network to use the broadband internet.

1. Turn on Wireless LAN 

2. Touch Scan for scanning for new networks You will see the newly created network WLAN listed there with a lock icon.

3. Now go to Internet Accounts by tapping More in the WLAN page and tapping Internet Accounts.

4. There tap More>New account>WLAN

5. Fill in the details as shown in the screenshot and create the connection.



6. Now in the Internet Accounts tab highlight WLAN and tap Edit, then tap More>TCP/IP>IP Config and fill in the details as shown in the screenshot. Similarly fill in the details for the DNS address. Press Done and come back to Wireless LAN. There scan for networks. You will notice a yellow star beside th network name WLAN. Hit the Connect button after highlighting WLAN.
7. Cheers!!! You are now connected to the internet. Open web browser and test your connectivity and enjoy.

Sunday, May 9, 2010

Bug in MySQL Subqueries with IN Operator

While developing an application with MySQL at the backend I happened to write a query containing a subquery with the IN operator. I was surprised to see that the query crashed MySQL daemon on Windows! On Linux, it was taking ages and I had to abort it. After lots of tests I concluded that MySQL has a limited support for subqueries. I browsed their site for help and found out that they were working on it and it will be fixed in the 6th version.

Similarly I also found that Self-Joins have problems too, for tables with large number of entries.
Here are the queries. If you wanna experiment then download the table structure from here

The query with subquery(takes infinite time):
SELECT DISTINCT(uid) FROM ip WHERE ip IN(SELECT ip FROM ip WHERE uid=3) ORDER BY uid; 

The alternate solution using self-join(takes 5.30 seconds on my notebook):
SELECT DISTINCT(a.uid) FROM ip a, ip b WHERE a.ip=b.ip AND b.uid=3 ORDER BY a.uid;

Another solution using an inner join to an inline view(takes 2.55 seconds on my notebook):
SELECT DISTINCT(a.uid) FROM ip a, (SELECT ip FROM ip WHERE uid=3) b WHERE a.ip=b.ip ORDER BY a.uid;

or in ANSI style using the INNER JOIN keyword


SELECT DISTINCT(a.uid) FROM ip a INNER JOIN (SELECT ip FROM ip WHERE uid=3) b ON a.ip=b.ip ORDER BY a.uid;



The penultimate solution I used was through PHP by splitting the query in parts and processing through PHP. It takes 1.99 seconds to vomit the result:
<?php
$time = microtime();
$time = explode(" ", $time);
$time = $time[1] + $time[0];
$start = $time;
$sql=mysql_query("SELECT ip FROM ip WHERE uid=3");
$condition="";
while($tmp=mysql_fetch_array($sql)){
$condition.=" ip='$tmp[0]' OR";
}
$len=strlen($condition);
$condition=substr($condition,0,len-3);
$sql=mysql_query("SELECT DISTINCT(uid) FROM ip WHERE".$condition);
          if ($sql){
  $i=0;
  while ($sqls=mysql_fetch_array($sql)){
  $iarray[$i++]=$sqls[0];
  }
  }
$time = microtime();
$time = explode(" ", $time);
$time = $time[1] + $time[0];
$finish = $time;
$totaltime = ($finish - $start);
echo count($iarray)." rows in $totaltime seconds
";
print_r($iarray);
?>

The final solution that I implemented take 0.035 seconds!

<?php
$time = microtime();
$time = explode(" ", $time);
$time = $time[1] + $time[0];
$start = $time;
$sql=mysql_query("SELECT ip FROM ip WHERE uid=3");
$condition="";
while($tmp=mysql_fetch_array($sql)){
$condition.="'$tmp[0]',";
}
$len=strlen($condition);
$condition=substr($condition,0,len-1);
$query="SELECT DISTINCT(uid) FROM ip WHERE ip IN(".$condition.")";
$sql=mysql_query($query);
          if ($sql){
 $i=0;
 while ($sqls=mysql_fetch_array($sql)){
 $iarray[$i++]=$sqls[0];
 }
 }
$time = microtime();
$time = explode(" ", $time);
$time = $time[1] + $time[0];
$finish = $time;
$totaltime = ($finish - $start);
echo count($iarray)." rows in $totaltime seconds
";
print_r($iarray);
?>

Friday, May 7, 2010

IIIT-B Interview

If you are just preparing for GATE, you should solve more and more questions. And for that I would recommend GKP Publisher's Question Bank. Although there are some mistakes in the book for solutions to some problems, but I recommend this book solely for the huge collection of problems it has.

On the destined date I reached Bangalore for my IIIT-B interview. Bangalore is quite a happening city. Contrary to the fact pointed out by my acquaintances that you will have language problems in Bangalore, everyone seemed to understand Hindi and English. On 5th morning at 7AM I boarded a bus from Majestic for Electronics City. It took around 45 minutes for the AC Volvo called Vayu Vajra by BMTC, to churn out 15KMs, traffic being a bottleneck. I was greeted by the Electronics City flagship Infosys campus. It is very huge and a live example of engineering and architectural excellence. After asking a few passers-by about the where-abouts of IIIT-B we finally found the campus which has an HP go-down(housed in Infosys campus) in its front, Siemens to the left, Infosys to the front right. As I entered the campus I noticed a gathering of several GATE qualified padhaku students. I took an stroll around the campus with inquisitive eyes, and then entered into the academic block from the rear!!! As I entered inside, I was awestruck at the beauty of the interior. After I detected my goof, I went to the main entrance and got my attendance marked. Then I was directed to head towards Main Class Room 106. There, lots of students and their guardians were seated, and catered by the student volunteers. The main class room had four large projected screens and the student volunteers were running presentations about the college on them and helping the candidates with the interview process. They were all very co-operative. Some YouTube videos were also being played. The internet connectivity through WiFi was extremely fast there and I saw a 4 minute video getting buffered in less than 30 seconds.
At around 12 I went for my documents verification and was then carried to the interview place. There were around 20 cabins in which 20 people were interviewing the candidates. After a couple of minutes I was directed towards a cabin. I asked for the permission to enter and went into the chamber. The man inside offered me a seat, I thanked and seated myself onto the chair.
My interview session lasted for around 15-20 minutes. The first thing he asked me was: Tell me about yourself for three minutes. I started off with the by hearted answer that consisted of Name, Location, Schooling, Current activity, Hobbies and Interests in that order. Instead of 3 minutes, I ran out of data in 1 minute only!!!
Then he asked me about my blog, about which I had stated in the hobbies category. I spoke. He cross-questioned, how many followers do you have? I said two, as of now, but I receive 100+ unique visitors per day according to log stats. He asked me why don't you concentrate on converting visitors to followers? I said, I didn't have this idea earlier, my main motto was to acquaint people with my experiences with computers, but now as you have told me I'll concentrate on this thing too.
Then he asked me. Ok, start with the technical topic you have prepared and continue for five minutes. I started off with my Socket Communication topic and explained things bringing everything down to basic level. During the course of describing the UDP server I forgot something and stopped, then asked him for a few seconds to recall and reorganize all the data inside my brain. He gave me time and after 3 seconds I resumed.
After I finished, he said you can communicate well, but not because you have a very good command over spoken english but because you have a deep understanding of the topic you are explaining. I said yes sir, my mothertongue is not english and I have spoken english very little so I don't have very good command over spoken english. He told, who says you can't speak? You spoke perfectly well. Communication means when you speak socket, I should hear it as socket not ice cream! I agreed!
Then he started looking at my academics. He said you're having nice academics. Your GATE score of 614 and marks 42.33 is very high and you're probably in the 98th percentile. I said yes, 98.59 to be precise. He said, it is a very good score. I replied, not very good but it is just fine, I could have scored 60+ if only I hadn't made those silly mistakes which I realized while matching the solutions on v-day evening. Then he said, which subjects you were most excited about in your B.Tech. I replied DBMS and Networking. He said, ok you've been given a table, can you say whether it is in third normal form and if it is not, then can you convert it in 3NF? Backed with my expertise in Functional Dependencies & Normalization I said, yeah with hundred percent surety, and proceeded ahead.
After this he asked me, how do you spend your time. I said, I am not into arts so no music, no singing. But I play chess, do some photography and most of the extra time I spend managing my site. Then he asked me about the site. I explained about IndiFun using the word Mobile Social Networking. He stressed on the phrase and said me to explain it. I explained about GPRS and tiny browsers and mobile markup languages. He said, how does this site connect people. I narrated all the features of IndiFun like an advertiser!!!!
Then he said, according to your academics and your extra-curricular activities you are a very deserving candidate. I would love to have you here. But the interview is a very tiny part of the whole selection process. My best wishes for you.
And said, if you have any questions then ask me. I asked, please tell me about yourself. He said, I run a company called Radix Learning which works with IIIT-B and also I teach here data structures in PGDSD course, not in M.Tech course. I said, I would like to keep in touch with you after I get selected. He said no! I don't interact with M.Tech students!
After that he said go happy, you seem to be a very promising candidate. I thanked him, shook hands and left the cabin.
Some photos that I took, follow: