Codingfreak

Death of Google Reader - Journey towards alternatives

noreply@blogger.com (Ajith Adapa) — Fri, 15 Mar 2013 23:14:00 PDT

Flashback

Long Long ago when INTERNET is booming up with so many websites its really hard to follow the interesting one. Its quite clumsy to go around miliions of sites to check for new posts.

Am I Doomed ?

No, you are not. RSS feed mechanism is the answer.

Just follow the RSS feed of your favourite site and the RSS reader will maintain the unread articles, favourite articles and so on. Voilla simple and effective solution to follow various sites.

Which RSS reader to use ?

I started my journey with Google Reader just because

Service from GOOGLE (Truly .. those were the days everyone crazy to use Google Services. Even having a GMAIL account is symbol of techy saviness.)
Simplicity
Cleaner interface
Meets all my basic needs like tagging, starring, sharing
No extra signup trash (Just use your google account)

I am already using it for last 6 years and I simply love it. I have around 1000+ subscriptions on various topics in it.

Present

As part of cleanup process which GOOGLE follows for its services they decided to ditch Google reader with only reason saying - it doesnt meets their expectation. Being a Loyal user of Google from last 6 years I have really lost my trust on them when they scrapped Google Reader. I really need to think alternatives for their services.

Uproar started every where as users backlashed at google's decision in various popular social networking sites. Even I am one among them. Nothing can be done but looking for alternatives.

Future

Before I really jump into alternatives for Google reader I decided to sort down my requirements.

Web based RSS reader like Google Reader not a application only one. Its main advantage is I can read from anywhere from browser.
Simple, Cleaner Interface.
Support 1000+ subscriptions.
Tagging of Feeds.
Support for various views like List view, Expanded view, Full view so on.
Automatic marking of items as read as they are scrolled past. This option really helps in marking posts as read the moment we scroll past them.
Sharing options with various social networking sites (Not so mandatory).
Free Service.
Extra goodies

Alternatives I am gonna try

1. Feedly

Quite popular among the alternatives I decided to start with Feedly. Feedly already started to face huge traffic from users migrating from Google Reader as they promise to provide seamless migration for Google Reader users. Just signup with your google account and all your feeds are imported automatically.

Important Tips for users migrating from Google Reader to Feedly is shared in their Blog Link. These tips are really helpful.Even though initial look is clumsy we can customize it in preferences tab making it look simple and cleaner as shown below.

Pros:

Simple, Cleaner Interface
Transition from Google Reader is very simple.
Meets all my requirements mentioned above.
Web Based RSS reader and even supports apps for various platforms.
Support cleaner background themes option.
Save option is really helpful to check the old and interesting articles later.

Cons:

None currently.

I would highly recommend this service for google readers as you gonna feel back home.I would call Feedly as Google Reader on steroids.

Eventhough I am very happy with Feedly I decided to try other popular services available.

2. Bloglovin

A simple signup procedure which accepts your Facebook account or Email sign-up. Once sign-up is done it asks for importing feeds from Google reader making transition from Google Reader very simple.

Pros:

Simple, Cleaner interface.
Transition from Google Reader is very simple.
Creates personal profile.

Cons:

Only supports magazine view.
No support for automatic marking of items as read as they are scrolled past.
No Tagging option.
Very basic sorting option.

3. Netvibes

Netvibes is a personalized dashboard publishing platform like iGoogle. It provides simple signup procedure which accepts your Facebook account or Email sign-up. Once signed-in initial feel is just like iGoogle service with its widgets look of various sites.

Steps for importing feeds from Google Reader to netvibes is shared in their blog link.

Pros:

Simple, Cleaner Interface.
Support various options like iGoogle service.

Cons:

Its a dashboard publishing service. I just need a RSS reader.
Free edition doesn't support automatic marking of items as read as they are scrolled past.
Premium Services at whopping 499$/month. Are you kidding me lol.

4. Feedspot

After simple signup procedure users are provided with a link to transition feeds from Google Reader.

Pros:

Simple, Cleaner interface.
Easy transition of feeds from Google Reader.

Cons:

Doesn't support automatic marking of items as read as they are scrolled past.

Divide a number by 3 without using any arithmetic operators

noreply@blogger.com (Ajith Adapa) — Wed, 13 Mar 2013 21:35:00 PDT

How to divide a number by 3 without using + - / * %

NOTE: I am just trying to collect various answers down in this post available across multiple sites in internet as mentioned in references.

Solution 01:

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

int main()
{
    FILE *fp=fopen("temp.dat","w+b");
    int number=12346;
    int divisor=3;
    char *buf = calloc(number,1);
    fwrite(buf,number,1,fp);
    rewind(fp);
    int result=fread(buf,divisor,number,fp);
    printf("%d / %d = %d", number, divisor, result);
    free(buf);
    fclose(fp);
    return 0;
}

Explanation of how it works

The fwrite writes number bytes (number being 123456 in the example above).
rewind resets the file pointer to the front of the file.
fread reads a maximum of number "records" that are divisor in length from the file, and returns the number of elements it read.

If you write 30 bytes then read back the file in units of 3, you get 10 "units". 30 / 3 = 10

Solution 02:

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

int main(int argc, char *argv[])
{
    int num = 1234567;
    int den = 3;
    div_t r = div(num,den); // div() is a standard C function.
    printf("%dn", r.quot);

    return 0;
}

Solution 03:

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

int add(int x, int y) {
  int a, b;
  do {
    a = x & y;
    b = x ^ y;
    x = a << 1;
    y = b;
  } while (a);
  return b;
}

int divideby3 (int num) {
  int sum = 0;
  while (num > 3) {
    sum = add(num >> 2, sum);
    num = add(num >> 2, num & 3);
  }
  if (num == 3)
    sum = add(sum, 1);
  return sum;   
}

int main()
{
  int number=30;

  printf("%d n", divideby3(number));
  return 0;
}

References:

Stackoverflow.

Deleting a Node from a Singly Linked List

noreply@blogger.com (Ajith Adapa) — Tue, 25 Dec 2012 04:55:00 PST

This article is part of article series - "Datastructures"

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Deletion of a Node from a Singly Linked List
Similar to insertion we have three cases for deleting a Node from a Singly Linked List.

Deleting First Node in Singly Linked List

To complete deletion of firstNode in the list we have to change Head pointing to Next of firstNode.

Pseudocode:

firstNode = Head

Head = firstNode->Next

free firstNode

Complexity:
Time Complexity: O(1)
Space Complexity: O(1)

Sourcecode:

 int delNodeData(int num)
 {
    struct Node *prev_ptr, *cur_ptr;

    cur_ptr=Head;

    while(cur_ptr != NULL)
    {
       if(cur_ptr->Data == num)
       {
          if(cur_ptr==Head)
          {
             Head=cur_ptr->Next;
             free(cur_ptr);
             return 0;
          }
          else
          {
             prev_ptr->Next=cur_ptr->Next;
             free(cur_ptr);
             return 0;
          }
       }
       else
       {
          prev_ptr=cur_ptr;
          cur_ptr=cur_ptr->Next;
       }
    }

    printf("\nElement %d is not found in the List", num);
    return 1;
 }

Deleting Last Node in the Singly Linked List

Traverse to Last Node in the List using two pointers namely prevNode and curNode. Once curNode reaches the last Node in the list point Next in prevNode to NULL and free the curNode.

Pseudocode:
```
curNode = head

forever:

 if curNode->Next == NULL
 break

 prevNode = curNode
 curNode = curNode->Next

prevNode->Next = NULL

free curNode
```
Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

Deleting Node from position 'p' in the List

To delete a Node at the position 'p' we have to first traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to curNode Next and free curNode.

Pseudocode:

curNode = head
curPos = 1

forever:

 if curPos == P || curNode == NULL
 break

 prevNode = curNode
 curNode = curNode->Next
 curPos++

if curNode != NULL:
 
 prevNode->Next = curNode->Next
 free curNode

Complexity:
Time Complexity: O(n) worst case
Space Complexity: O(3)

Sourcecode:

int delNodeLoc(int loc)
 {
    struct Node *prev_ptr, *cur_ptr;
    int i;

    cur_ptr=Head;

    if(loc > (length()) || loc <= 0)
    {
        printf("\nDeletion of Node at given location is not possible\n ");
    }
    else
    {
        // If the location is starting of the list
        if (loc == 1)
        {
            Head=cur_ptr->Next;
            free(cur_ptr);
            return 0;
        }
        else
        {
            for(i=1;i<loc;i++)
            {
                prev_ptr=cur_ptr;
                cur_ptr=cur_ptr->Next;
            }

            prev_ptr->Next=cur_ptr->Next;
            free(cur_ptr);
        }
    }
    return 1;
 }

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Detecting First Node in a Loop in the List

noreply@blogger.com (Ajith Adapa) — Tue, 25 Dec 2012 01:06:00 PST

This article is part of article series - "Datastructures"

Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

Once we confirm that there is a Loop in a Singly Linked List we will see how to determine first node of the loop.

Figure-1: Singly Linked list with a loop which we have detected using Floyd's Cycle Detection Algorithm

NOTE: Example in Figure-1 is the output of Floyd's Cycle detection Algorithm which we have seen in Floyd's Cycle Detection Algorithm. We are not randomly choosing Hare and Tortoise at Node-6.

Solution 01: Brute-force Approach

Start at the Head of the Singly Linked List (i.e. curNode).

If Tortoise and Hare are at the same Node move the curNode forward by one position.

If Tortoise and curNode are at the same Node return, we have found first Node in the loop.

Move Tortoise forward by one position and start with STEP-2.

Pseudocode:

curNode = head

forever:

  if tortoise == hare
    tortoise = tortoise.next
    curNode = curNode.next

  if tortoise == curNode
    return curNode

  tortoise = tortoise.next

Complexity:

Time Complexity: O(n*p) - where 'p' is the length of the loop and 'n' is the length of the List.
Space Complexity: O(1)

Example:

Let us try above algorithm on example in Figure-1.The pattern for Hare, Tortoise and Culprit is given below

Hare Tortoise Culprit
7        7            HEAD
7          8            1
7          3            1
7          4            1
7          5            1
7          6            1
7          7            1
7          8            2
7          3            2
7          4            2
7          5            2
7          6            2
7          7            2
7          8            3
7          3            3

Solution 02:

Let use see how to improve the Time Complexity of the solution 01.

But before we go into the solution I would like to mention that the below solution can be used only after detecting a loop in the singly linked list. As mentioned Figure-1 is the output of Floyd's cycle detection algorithm and we havent randomly choosen Node-7. As pointed out many users if we start from Node-6 we might end up in loop.

Start Tortoise at first node.

Move Hare and Tortoise by one position.

If Hare and Tortoise points to same node then return (its the first Node in the loop)

Start again from STEP-2

Pseudocode:

tortoise := firstNode

forever:

  if tortoise == hare
    return tortoise

  tortoise := tortoise.next
  hare := hare.next

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Example:

Let us try above algorithm on same example in Figure-1. Now let us start the Tortoise from the first node in the list.

The pattern for Hare and Tortoise is given below

Hare Tortoise
7        1
8          2
3          3

Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

Finding Nth node from end of a Singly Linked List

noreply@blogger.com (Ajith Adapa) — Tue, 13 Nov 2012 20:17:00 PST

This article is part of article series - "Datastructures"

Previous Article: Finding first node in a Loop in Singly Linked List.

Figure 1: Singly Linked List

Solution 01 - Brute Force Approach:

Start at First Node of the List (call it curNodePtr).
Assign curNodePtr to tmpPtr and count number of nodes after the curNodePtr.
If number of nodes after curNodePtr are equal to N nodes or tmpPtr reaches END then break. If tmPtr reaches END but count not equal to N then return since we can't find the Nth node from the end of the Singly Linked List.
Move the curNodePtr one step forward in the Linked List i.e curNodePtr now points to its next node in the list and start again from STEP-2.

Pseudocode:

curNodePtr := FirstNode

if curNodePtr == NULL
  return 'Less Nodes in the List'

forever:

  tmpPtr := curNodePtr
  count := 0

  forever:

    if tmpPtr == NULL || count == N
      break

    tmpPtr := tmpPtr.NEXT
    count++

  if tmpPtr == NULL
    if count == n
      return curNodePtr
    else
      return 'Less Nodes in the List'

  curNodePtr := curNodePtr.NEXT

Complexity:

Time Complexity: O(n^2) - For traversing each node after curNode.
Space Complexity: O(1)

Example:

Let us try above brute-force approach on example in Figure-1

Find 2nd Node: It returns Node 4.

curNode tmpNode Count
01    01    0
01    02    1
01                    03            2
02    02    0
02    03    1
02    04    2
03    03    0
03    04    1
03    05    2
04                    04            0
04                    05            1
04    NULL     2

Find 6th Node: It returns 'Less Nodes in the List'

curNode tmpNode Count
01    01    0
01    02    1
01    03    2
01    04    3
01    05    4
01    NULL     5

Solution 02:

Let us improve the time complexity when compared to Solution-01.

Find the length of the Singly Linked List (Let us say P).
If Length of the Singly linked List (P) is lesser than N return, since we can't find the Nth node from the end of the Singly Linked List.
If Length of the Singly Linked List (P) greater than N then compute (P-N+1) value, which points to Nth node from the end of Singly Linked List.
Traverse to (P-N+1)th Node in the Singly Linked List.

Pseudocode:

curNodePtr := FirstNode
P = 0

forever:

  if curNodePtr == NULL
    break

  P++
  curNodePtr := curNodePtr.NEXT

if P < N
  return 'Less Nodes in the List'

curNodePtr := FirstNode
count = 1

forever:

  if count == (P-N+1)
    return curNodePtr

  count++
  curNodePtr = curNodePtr.NEXT

Complexity:

Time Complexity: O(n) - Time for finding the length of a Singly Linked List O(n) + Time for finding (P-N+1) node in the List O(n) = O(n)
Space Complexity: O(1)

Solution 03:

Let us see one more simple and cleaner approach when compared to Solution 02 which doesn't need to traverse all nodes in the list twice to find the Nth node from the end of a Singly Linked List.

Let us take two pointers tmpPtr and nthNodePtr starting at the First Node of the Singly Linked List.
tmpPtr will start first by traversing N positions in the list. If it doesn't reach N positions from start of the singly linked list it means list is small. Return as we can't find the Nth node from the end of the list.
Once tmpPtr traverses N positions successfully nthNodePtr starts traversing along with tmpPtr one position forward until tmpPtr reaches the end of the List.
Once tmpPtr reaches end of the Singly Linked List nthNodePtr will be pointing to Nth node from the end of the Singly Linked List

Pseudocode:

tmpPtr := FirstNode
nthNodePtr := FirstNode
count := 1

forever:
  
  if count == N || tmpPtr == NULL
    break

  tmpPtr := tmpPtr.NEXT
  count++

if tmpPtr == NULL && count < N
  return 'Cannot find Nth element in the list'

tmpPtr := tmpPtr.NEXT

forever:

  if tmpPtr == NULL
    return nthNodePtr

  tmpPtr := tmpPtr.NEXT
  nthNodePtr := nthNodePtr.NEXT

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Example:

Let us try the above solution on example in Figure-1

Find 2nd Node from end of the List

tmpPtr nthNodePtr count
    1     1 1
    2     1 2
    3     1 -
    4     2 -
    5     3 -
    NULL    4 -

Reversing a Singly Linked List

noreply@blogger.com (Ajith Adapa) — Tue, 06 Nov 2012 20:24:00 PST

This article is part of article series - "Datastructures"

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Let us see how to reverse a Singly Linked List.

Figure-1: Singly Linked List

Pseudocode:

cur_ptr = HEAD->NEXT
prev_ptr = NULL

forever:

   if cur_ptr == NULL
   break

   tmp_ptr  = prev_ptr
   prev_ptr = cur_ptr
   cur_ptr  = cur_ptr->NEXT
   
   prev_ptr->NEXT = tmp_ptr

HEAD->NEXT = prev_ptr

Complexity:
Time Complexity: O(n)
Space Complexity: O(3)

If we try on the example in Figure-1 we get the output as shown below

Figure-2: After reversing the Singly Linked List

Previous Article: Deleting a Node from a Singly Linked List.
Next Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.

Detecting a Loop in Singly Linked List - Tortoise & Hare

noreply@blogger.com (Ajith Adapa) — Fri, 21 Sep 2012 23:07:00 PDT

This article is part of article series - "Datastructures"

Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.

Eventhough there are multiple algorithms available we start with

Floyd's Cycle-Finding Algorithm
In simple terms it is also known as "Tortoise and Hare Algorithm" or "Floyd's Cycle Detection Algorithm" named after its inventor Robert Floyd. It is one of the simple cycle detection algorithm. It's a simple pointers based approach.

Robert Floyd

Let us take 2 pointers namely slow Pointer and fast Pointer to traverse a Singly Linked List at different speeds. A slow Pointer (Also called Tortoise) moves one step forward while fast Pointer (Also called Hare) moves 2 steps forward

Start Tortoise and Hare at the first node of the List.
If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare one step forward.
If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare and Tortoise one step forward.
If Hare and Tortoise pointing to same Node return, we found loop in the List.
Else start with STEP-2.

Pseudocode:

tortoise := firstNode
hare := firstNode

forever:

  if hare == end 
    return 'No Loop Found'

  hare := hare.next

  if hare == end
    return 'No Loop Found'

  hare = hare.next
  tortoise = tortoise.next

  if hare == tortoise
    return 'Loop Found'

Why can't we let the Hare go by itself like Tortoise ?
If there is a loop, Hare would just go forever. Tortoise ensures that you will only take 'n' steps atmost.

How to find the length of the Loop ?
Once Hare and Tortoise finds the loop in a Singly linked List move Tortoise one step forward everytime maintaining the count of the nodes until it reaches the Hare again.

Example:

Singly Linked List with a Loop

Both Tortoise and Hare starts at First node of the list and Tortoise moves 1 step forward while Hare moves 2 steps forward.

Hare and Tortoise starts at First Node of the List

The pattern of Hare and Tortoise movements are shown below.

Hare   Tortoise
1          1
3          2
5          3
7          4
3          5
5          6
7          7

Both Hare and Tortoise meet up at Node 7. That proves there is a loop in the list

Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

To calculate the Time Complexity the shape of the cycle doesn't matter. It can have a long tail, and a loop towards the end or just a loop from the beginning to the end without a tail. Irrespective of the shape of the cycle, one thing is clear - that the Tortoise can never catch up with the Hare. If the two has to meet, the Hare has to catch up with the Tortoise from behind.

With that established, consider the two possibilities

Hare is one step behind Tortoise
Hare is two step behind Tortoise

All greater distances will reduce to One or Two. Let us assume always Tortoise moves first (it could be even other way).

In the first case were the distance between Hare and Tortoise is one step. Tortoise moves one step forward and the distance between Hare and Tortoise becomes 2. Now Hare moves 2 steps forward meeting up with Tortoise.

In the second case were the distance between Hare and Tortoise is two steps. Tortoise moves one step forward and the distance between Hare and Tortoise becomes 3. Now Hare moved 2 steps forward which makes the distance between Hare and Tortoise as 1. It is similar to first case which we already proved that both Hare and Tortoise will meet up in next step.

Let the length of the loop be 'n' and there are 'p' variables before the loop. Hare traverses the loop twice in 'n' moves, they are guaranteed to meet in O(n).

Previous Article: Reversing a Singly Linked List.
Next Article: Finding first node in a Loop in Singly Linked List.

Write a C Program without main function

noreply@blogger.com (Ajith Adapa) — Thu, 23 Aug 2012 08:19:00 PDT

In a C program main function is the entry point so it is mandatory to have a main function.

But let us see how can we write a program without main (Kind of hiding main in some obfuscated code). This post is purely out of interest to know that we can do something weird like this, just for learning.

Solution 01: Using simple macro substitution

#include <stdio.h>

#define START main

int START()
{
   printf("HELLO WORLD");
}

During the preprocessing stage of compilation of above code, HELLO is replaced with main.

Solution 02: Using Token Merging Operator

## is a Token merging operator. It can merge two or more characters.

#include <stdio.h>

#define START m##a##i##n

int START()
{
   printf("HELLO WORLD");
}

Solution 03: Using Argumented Macro

#include <stdio.h>

#define decode(l,i,g,h,t) h##l##g##i
#define START decode(a,n,i,m,e)

int START()
{
   printf("HELLO WORLD");
}

During the preprocessing stage START is replaced with decode which takes 5 arguments namely a n i m e and then decode is replaced h##l##g##i which means main.

Implementing ls command in C

noreply@blogger.com (Ajith Adapa) — Thu, 09 Aug 2012 08:14:00 PDT

We know that ls command in unix displays the list of files in a directory. It has various options to display the data in various styles and formats.

By default its implementation is part of Coreutils package, which is default package in all Linux flavours.

I want to see how we can implement its basic functionality with a simple C program.

/*Listing the Files in a directory */

#include <sys/types.h>
#include <sys/dir.h>
#include <sys/param.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <dirent.h>
#include <pwd.h>
#include <grp.h>
#include <time.h>
#include <locale.h>
#include <langinfo.h>
#include <stdint.h>
#include <fcntl.h>

static char perms_buff[30];

const char *get_perms(mode_t mode)
{
  char ftype = '?';

  if (S_ISREG(mode)) ftype = '-';
  if (S_ISLNK(mode)) ftype = 'l';
  if (S_ISDIR(mode)) ftype = 'd';
  if (S_ISBLK(mode)) ftype = 'b';
  if (S_ISCHR(mode)) ftype = 'c';
  if (S_ISFIFO(mode)) ftype = '|';

  sprintf(perms_buff, "%c%c%c%c%c%c%c%c%c%c %c%c%c", ftype,
  mode & S_IRUSR ? 'r' : '-',
  mode & S_IWUSR ? 'w' : '-',
  mode & S_IXUSR ? 'x' : '-',
  mode & S_IRGRP ? 'r' : '-',
  mode & S_IWGRP ? 'w' : '-',
  mode & S_IXGRP ? 'x' : '-',
  mode & S_IROTH ? 'r' : '-',
  mode & S_IWOTH ? 'w' : '-',
  mode & S_IXOTH ? 'x' : '-',
  mode & S_ISUID ? 'U' : '-',
  mode & S_ISGID ? 'G' : '-',
  mode & S_ISVTX ? 'S' : '-');

  return (const char *)perms_buff;
}

char pathname[MAXPATHLEN];

void die(char *msg)
{
  perror(msg);
  exit(0);
}

static int
one (const struct dirent *unused)
{
  return 1;
}

int main()
{
  int count,i;
  struct direct **files;
  struct stat statbuf;
  char datestring[256];
  struct passwd pwent;
  struct passwd *pwentp;
  struct group grp;
  struct group *grpt;
  struct tm time;
  char buf[1024];

  if(!getcwd(pathname, sizeof(pathname)))
    die("Error getting pathnamen");

  count = scandir(pathname, &files, one, alphasort);

  if(count > 0)
  {
    printf("total %dn",count);

    for (i=0; i<count; ++i)
    {
      if (stat(files[i]->d_name, &statbuf) == 0)
      {
        /* Print out type, permissions, and number of links. */
        printf("%10.10s", get_perms(statbuf.st_mode));
        printf(" %d", statbuf.st_nlink);

        if (!getpwuid_r(statbuf.st_uid, &pwent, buf, sizeof(buf), &pwentp))
          printf(" %s", pwent.pw_name);
        else
          printf(" %d", statbuf.st_uid);

        if (!getgrgid_r (statbuf.st_gid, &grp, buf, sizeof(buf), &grpt))
          printf(" %s", grp.gr_name);
        else
          printf(" %d", statbuf.st_gid);

        /* Print size of file. */
        printf(" %5d", (int)statbuf.st_size);

        localtime_r(&statbuf.st_mtime, &time);
        /* Get localized date string. */
        strftime(datestring, sizeof(datestring), "%F %T", &time);

        printf(" %s %sn", datestring, files[i]->d_name);
      }

      free (files[i]);
    }

    free(files);
  }
}

GIT - Adding diffmerge as visual merge in git

noreply@blogger.com (Ajith Adapa) — Wed, 11 Jul 2012 23:45:00 PDT

GIT is one of the popular distributed code repositories in opensource community, especially with developers working on opensource projects like linux kernel and others.

Operations like Merge and Diff are the most irritating & tricky tasks via command line when working on large code changes. So let us see how can we add some graphical stuff for these operations when using on GIT so that we can do merging and other options very easily.

By following below steps you can install and configure diffmerge tool for git.

Based on the operating system you are using download respective diffmerge tool.

Now go to the source code directory which have been cloned from a git repository. Add the following commands to make git support diffmerge in diff and merge operations.

git config --global diff.tool diffmerge
git config --global difftool.diffmerge.cmd 'diffmerge "$LOCAL" "$REMOTE"'
git config --global merge.tool diffmerge
git config --global mergetool.diffmerge.cmd 'diffmerge --merge --result="$MERGED" "$LOCAL" "$(if test -f "$BASE"; then echo "$BASE"; else echo "$LOCAL"; fi)" "$REMOTE"'
git config --global mergetool.diffmerge.trustExitCode true

Configuration is done.

Now let us see how can we use the diffmerge tool.

Whenever you want to launch diff use difftool and similarly mergetool to launch merge as shown below.

# To diff a local file against the checked-in version
git difftool file

# to diff the local file against the version in some-feature-branch
git difftool some-feature-branch file

# to diff the file under the Build-54 tag to the Build-55 tag
git difftool Build-54..Build-55 file

# to do merge operations and resolve conflicts via diffmerge tool use below command.
git mergetool

Start using it now.

References

1. Twobit Labs

TCPDUMP cheat sheet

noreply@blogger.com (Ajith Adapa) — Thu, 14 Jun 2012 02:29:00 PDT

Listing possible network interfaces on the system

tcpdump -D

E.g.
$ tcpdump -D
1.eth0
2.eth1
3.usbmon1 (USB bus number 1)
4.eth2
Capture packets from a particular interface

tcpdump -i interface-name

E.g. To capture packets from interface eth1 - tcpdump -i eth1
Capture only N number of packets

tcpdump -c N

E.g. To capture 10 packets from interface eth1 - tcpdump -i eth1 -c 10
Capture the packets and write into a file

tcpdump -w file.pcap

E.g. tcpdump -i eth1 -w tmp.pcap
To capture and store network frames full-length

tcpdump -s 0

E.g. tcpdump -i eth1 -w tmp.pcap -s 0
Reading the packets from a saved file

tcpdump -r file.pcap

E.g.tcpdump -tttt -r tmp.pcap
Capture packets with proper readable timestamp

tcpdump -tttt

E.g. tcpdump -i eth1 -tttt

Filter Options

type

dir

proto

Read packets longer than N bytes

tcpdump greater N

E.g. tcpdump -i eth1 -w tmp.pcap greater 1024
Receive only the packets of a specific protocol type - fddi, tr, wlan, ip, ip6, arp, rarp, decnet, tcp and udp

E.g tcpdump -i eth1 arp
Receive packets flows on a particular port

tcpdump port PORT_NO

E.g. tcpdump -i eth1 port 22
Capture packets for particular destination IP and Port

tcpdump dst IPADDRESS and port PORT-NO

E.g. tcpdump -i eth1 dst 10.181.140.216 and port 22

Display options

Display more packet information

tcpdump -vvv

E.g. tcpdump -i eth1 -vvv
Display link level header of every packet: -e

tcpdump -e

E.g.

tcpdump -i eth1 -e -t
listening on eth2, link-type EN10MB (Ethernet), capture size 65535 bytes
52:54:00:e1:1c:10 (oui Unknown) > 01:80:c2:00:00:00 (oui Unknown), 802.3, length 60: LLC, dsap STP (0x42) Individual, ssap STP (0x42) Command, ctrl 0x03: STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
52:54:00:e1:1c:10 (oui Unknown) > 01:80:c2:00:00:00 (oui Unknown), 802.3, length 60: LLC, dsap STP (0x42) Individual, ssap STP (0x42) Command, ctrl 0x03: STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
Don’t print a timestamp on each dump line: -t

tcpdump -t

E.g.

Without using -t option we can see the below output timestamp is dumped (In bold letters).

tcpdump -i eth2

listening on eth2, link-type EN10MB (Ethernet), capture size 65535 bytes
08:44:51.295229 STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
08:44:53.296795 STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43

tcpdump -i eth2 -t

listening on eth2, link-type EN10MB (Ethernet), capture size 65535 bytes
STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
STP 802.1d, Config, Flags [none], bridge-id 8000.52:54:00:e1:1c:10.8003, length 43
Display packets with IP address instead of DNS names: -n

Basically tcpdump converts the plain address to DNS names. Using n option we can make tcpdump to display ip address.

tcpdump -n

E.g. tcpdump -i eth1 -n
Display Captured Packets in ASCII

tcpdump -A

E.g. tcpdump -i eth1 -A
Display Captured Packets in HEX and ASCII

tcpdump -XX

Decoding hardware information of a PC

noreply@blogger.com (Ajith Adapa) — Wed, 02 May 2012 02:47:00 PDT

Checking out machine hardware information is no more a geeky thing of olden days where you need to go through the hardware specification documents or to open up a physical machine to find out the hardware details if the specification documents are missing. Now we have some really cool handy software tools to help us out.

I thought to make a page with some important tools which help us in decoding the hardware related information on a Linux Box. Feel free to drop a comment with the tool names I missed out in this post.

NOTE: All of them are ordered in alphabetical order and I am trying these tools on a Ubuntu machine running in virtual box. So some of the tool outputs might be displaying names likes VirtualBox and Oracle Corporation.

biosdecode
Also known as BIOS Information Decoder is one of the best tools to check the BIOS information. It parses the BIOS memory and displays the info about your system BIOS. For more detailed info checkout man-page.

ACPI 2.0 present.
 OEM Identifier: VBOX  
 RSD Table 32-bit Address: 0x33FF0000
 XSD Table 64-bit Address: 0x0000000033FF0030
BIOS32 Service Directory present.
 Revision: 0
 Calling Interface Address: 0x000FDA00
PCI Interrupt Routing 1.0 present.
 Router ID: 00:01.0
 Exclusive IRQs: None
 Compatible Router: 8086:7000
.
.
SMBIOS 2.5 present.
 Structure Table Length: 352 bytes
 Structure Table Address: 0x000E1000
 Number Of Structures: 5
 Maximum Structure Size: 255 bytes

dmidecode
Also known as DMI Table Decoder. It just dumps the DMI or SMBIOS information, to screen, in a human-readable format. Quite verbose with the information it provides but this tool seems to be unreliable as per its users in some case. For more detailed info checkout man-page.

# dmidecode
# dmidecode 2.9
SMBIOS 2.5 present.
5 structures occupying 352 bytes.
Table at 0x000E1000.

Handle 0x0000, DMI type 0, 20 bytes
BIOS Information
 Vendor: innotek GmbH
 Version: VirtualBox
 Release Date: 12/01/2006
.
Handle 0x0001, DMI type 1, 27 bytes
System Information
 Manufacturer: innotek GmbH
 Product Name: VirtualBox
 Version: 1.2
 Serial Number: 0
 UUID: B220160E-6104-4C00-B1B4-D00F6384DD24

lspci
It displays complete information about all the PCI buses in the system and the devices connected to them. As you can see in below output we can see about type of ethernet nic cards being used and other stuff. For more detailed info checkout man-page.

# lspci
00:00.0 Host bridge: Intel Corporation 440FX - 82441FX PMC [Natoma] (rev 02)
00:01.0 ISA bridge: Intel Corporation 82371SB PIIX3 ISA [Natoma/Triton II]
00:01.1 IDE interface: Intel Corporation 82371AB/EB/MB PIIX4 IDE (rev 01)
00:02.0 VGA compatible controller: InnoTek Systemberatung GmbH VirtualBox Graphics Adapter
00:03.0 Ethernet controller: Intel Corporation 82540EM Gigabit Ethernet Controller (rev 02)
00:04.0 System peripheral: InnoTek Systemberatung GmbH VirtualBox Guest Service
00:06.0 USB Controller: Apple Computer Inc. KeyLargo/Intrepid USB
00:07.0 Bridge: Intel Corporation 82371AB/EB/MB PIIX4 ACPI (rev 08)
00:08.0 Ethernet controller: Intel Corporation 82540EM Gigabit Ethernet Controller (rev 02)
00:0d.0 SATA controller: Intel Corporation 82801HBM/HEM (ICH8M/ICH8M-E) SATA AHCI Controller (rev 02)

Uli Drepper - Basics you should know about buffer overflow

noreply@blogger.com (Ajith Adapa) — Thu, 19 Apr 2012 05:18:00 PDT

Part 1: Buffer Overflows

Part 2: Buffer overflow and libc attacks

Part 3: Memory allocation errors

Part 4: SELinux

Part 5: Preventing exploits

For direct REDHAT videos checkout this link.

Connecting via SSH without password prompt

noreply@blogger.com (Ajith Adapa) — Thu, 05 Apr 2012 22:49:00 PDT

SSH is the common way to connect remote machines these days. Almost all kinds of applications use SSH in background for communicating with end machines.

But sometimes typing password repeatedly for establishing a SSH connection with the trusted end machine is quite daunting task.

Let us see how to automate the things in 3 simple steps where we can ssh to "user@host" without asking a password every time. Replace user with the username and host with the remote machine ip-address or hostname. For E.g. john@192.168.245.129

NOTE: Only do this with trusted machines.

cd ~/.ssh

Check if you have a 'id_rsa.pub' (or 'id_dsa.pub') file in .ssh folder. If not, try below command:

ssh-keygen -t rsa

Run ssh-copy-id

ssh-copy-id -i id_rsa.pub user@host

Its done .. Now you can ssh to user@host without being prompted for password.

Daemon-izing a Process in Linux

noreply@blogger.com (Ajith Adapa) — Tue, 13 Mar 2012 06:44:00 PDT

A Linux process works either in foreground or background.

A process running in foreground can interact with the user in front of the terminal. To run a.out in foreground we execute as shown below.

./a.out

When a process runs as background process then it runs by itself without any user interaction. The user can check its status but he doesn't (need to) know what it is doing. To run a.out in background we execute as shown below.

$ ./a.out &
[1] 3665

As shown above when we run a process with & at the end then the process runs in background and returns the process id (3665 in above example).

what is a DAEMON Process?
A 'daemon' process is a process that runs in background, begins execution at startup
(not neccessarily), runs forever, usually do not die or get restarted, waits for requests to arrive and respond to them and frequently spawn other processes to handle these requests.

So running a process in BACKGROUND with a while loop logic in code to loop forever makes a Daemon ? Yes and also No. But there are certain things to be considered when we create a daemon process. We follow a step-by-step procedure as shown below to create a daemon process.

1. Create a separate child process - fork() it.
Using fork() system call create a copy of our process(child), then let the parent process exit. Once the parent process exits the Orphaned child process will become the child of init process (this is the initial system process, in other words the parent of all processes). As a result our process will be completely detached from its parent and start operating in background.

pid=fork();

if (pid<0) exit(1); /* fork error */

if (pid>0) exit(0); /* parent exits */

/* child (daemon) continues */

2. Make child process In-dependent - setsid()

Before we see how we gonna make a child process independent let us talk Process group and Session ID.

A process group denotes a collection of one or more processes. Process groups are used to control the distribution of signals. A signal directed to a process group is delivered individually to all of the processes that are members of the group.

Process groups are themselves grouped into sessions. Process groups are not permitted to migrate from one session to another, and a process may only create new process groups belonging to the same session as it itself belongs to. Processes are not permitted to join process groups that are not in the same session as they themselves are.

New process images created by a call to a function of the exec family and fork() inherit the process group membership and the session membership of the parent process image.

A process receives signals from the terminal that it is connected to, and each process inherits its parent's controlling tty. A daemon process should not receive signals from the process that started it, so it must detach itself from its controlling tty.

In Unix systems, processes operates within a process group, so that all processes within a group is treated as a single entity. Process group or session is also inherited. A daemon process should operate independently from other processes.

setsid();

setsid() system call is used to create a new session containing a single (new) process group, with the current process as both the session leader and the process group leader of that single process group. (setpgrp() is an alternative for this).

NOTE: We have to create a child process and use setsid() to make it independent. Trying on a parent process returns error saying EPERM.

3. Change current Running Directory - chdir()

A daemon process should run in a known directory. There are many advantages, in fact the opposite has many disadvantages: suppose that our daemon process is started in a user's home directory, it will not be able to find some input and output files. If the home directory is a mounted filesystem then it will even create many issues if the filesystem is accidentally un-mounted.

chdir("/server/");

The root "/" directory may not be appropriate for every server, it should be chosen carefully depending on the type of the server.

4. Close Inherited Descriptors and Standard I/O Descriptors
A child process inherits default standard I/O descriptors and opened file descriptors from a parent process, this may cause the use of resources un-neccessarily. Unnecessary file descriptors should be closed before fork() system call (so that they are not inherited) or close all open descriptors as soon as the child process starts running as shown below.

for ( i=getdtablesize(); i>=0; --i) 
close(i); /* close all descriptors */

There are three standard I/O descriptors:

standard input 'stdin' (0),
standard output 'stdout' (1),
standard error 'stderr' (2).

For safety, these descriptors should be opened and connected to a harmless I/O device (such as /dev/null).

int fd;

fd = open("/dev/null",O_RDWR, 0);

if (fd != -1) 
{   
  dup2 (fd, STDIN_FILENO);
  dup2 (fd, STDOUT_FILENO);
  dup2 (fd, STDERR_FILENO);
  
  if (fd > 2)
  close (fd);
}

5. Reset File Creation Mask - umask()
Most Daemon processes runs as super-user, for security reasons they should protect files that they create. Setting user mask will prevent unsecure file priviliges that may occur on file creation.

umask(027);

This will restrict file creation mode to 750 (complement of 027).

Let us see a sample 'C' code which creates a daemon.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>

#define EXIT_SUCCESS 0
#define EXIT_FAILURE 1

static void daemonize(void)
{
    pid_t pid, sid;
    int fd; 

    /* already a daemon */
    if ( getppid() == 1 ) return;

    /* Fork off the parent process */
    pid = fork();
    if (pid < 0)  
    {   
        exit(EXIT_FAILURE);
    }   

    if (pid > 0)  
    {   
        exit(EXIT_SUCCESS); /*Killing the Parent Process*/
    }   

    /* At this point we are executing as the child process */

    /* Create a new SID for the child process */
    sid = setsid();
    if (sid < 0)  
    {
        exit(EXIT_FAILURE);
    }

    /* Change the current working directory. */
    if ((chdir("/")) < 0)
    {
        exit(EXIT_FAILURE);
    }


    fd = open("/dev/null",O_RDWR, 0);

    if (fd != -1)
    {
        dup2 (fd, STDIN_FILENO);
        dup2 (fd, STDOUT_FILENO);
        dup2 (fd, STDERR_FILENO);

        if (fd > 2)
        {
            close (fd);
        }
    }

    /*resettign File Creation Mask */
    umask(027);
}

int main( int argc, char *argv[] )
{
    daemonize();

    while(1)
    {
      /* Now we are a daemon -- do the work for which we were paid */

      sleep(10);
    }

    return 0;
}

References

Memory Layout of a C program - Part 2

noreply@blogger.com (Ajith Adapa) — Sun, 04 Mar 2012 03:59:00 PST

Continuation of PART-1

As we have seen so much theory in the PART-1 now let us see a real-time example to understand about these segments. we will use size(1) command to list various section sizes in a C code.

A simple C program is given below

#include <stdio.h>

int main()
{
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     260       8    1104     450 a.out

Now add a global variable as shown below

#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main()
{
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     260      12    1108     454 a.out

As you can see BSS is incremented by 4 bytes.

Let us include a static variable as shown below.

#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main()
{
    static int i; /* Uninitialized static variable stored in bss */
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     260      16    1112     458 a.out

As you can see BSS is incremented by 4 bytes.

Now let us initialize the static variable so that it is saved in the initialized data segment.

#include <stdio.h>

int global; /* Uninitialized variable stored in bss*/

int main()
{
    static int i=10; /* Initialized static variable stored in DS*/
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     264      12    1112     458 a.out

Now you can see that data section is incremented by 4 bytes and BSS is decremented by 4 bytes.

Let us even initialize the Global variable which makes it part of Data Segment.

#include <stdio.h>

int global=10; /* Initialized variable stored in DS*/

int main()
{
    static int i=10; /* Initialized static variable stored in DS*/
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    836     268      8    1112     458 a.out

We can see that data section is incremented by 4 bytes and BSS is decremented by 4 bytes.

Let us see what happens when we add a const variable.

#include <stdio.h>

const int i = 1;

int global=10;

int main()
{
    static int i=10;
    return 0;
}

$ gcc test.c 
$ size a.out 
   text    data     bss     dec     hex filename
    840     268       8    1116     45c a.out

Now we can see that TEXT segment is incremented by 4 bytes.

References:
1. Narendra Kangralkar

Memory Layout of a C program - Part 1

noreply@blogger.com (Ajith Adapa) — Sun, 04 Mar 2012 03:10:00 PST

A running program is called a process.

When we run a program, its executable image is loaded into memory area that normally called a process address space in an organized manner. It is organized into following areas of memory, called segments:

text segment
data segment
stack segment
heap segment

Figure 1: Memory layout

text segment

It is also called the code segment.

This is the area where the compiled code of the program itself resides. This is the machine language representation of the program steps to be carried out, including all functions making up the program, both user defined and system.

For example, Linux/Unix arranges things so that multiple running instances of the same program share their code if possible. Only one copy of the instructions for the same program resides in memory at any time and also it is often read-only, to prevent a program from accidentally modifying its instructions.

The portion of the executable file containing the text segment is the text section.

data segment

initialized data
It contains both static and global data that are initialized with non-zero values. Each process running the same program has its own data segment.This segment can be further classified into initialized read-only area and initialized read-write area.

For Eg: The global string defined by char s[] = “hello world” in C and a C statement like int debug=1 outside the main (i.e. global) would be stored in initialized read-write area. And a global C statement like const char* string = “hello world” makes the string literal “hello world” to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.

The portion of the executable file containing the data segment is the data section.

Uninitialized data - bss segment
BSS stands for ‘Block Started by Symbol’ named after an ancient assembler operator that stood for “block started by symbol".uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.

For Eg: A variable declared static int i and a global variable declared int j would be contained in the BSS segment.

Each process running the same program has its own BSS area. When running, the BSS data are placed in the data segment.

For Linux/Unix the format of an executable, only variables that are initialized to a nonzero value occupy space in the executable’s disk file. In the executable file, they are stored in the BSS section.

The remaining two areas of system memory are where storage may be allocated by the compiler for data storage.

heap segment

The heap is where dynamically allocated memory (obtained by malloc(), calloc(), realloc() and new for C++) comes from. As memory is allocated on the heap, the process’s address space grows. Although it is possible to give memory back to the system and shrink a process’s address space, this is almost never done because it will be allocated to other process again.

Freed memory (free() and delete) goes back to the heap. Heap memory does not have to be returned in the same order in which it was acquired (it doesn't have to be returned at all), so unordered malloc/free's eventually cause heap fragmentation. The heap must keep track of different regions, and whether they are in use or available to malloc. One scheme is to have a linked list of available blocks (the "free store"), and each block handed to malloc is preceded by a size count that goes with it. Some people use the term arena to describe the set of blocks managed by a memory allocator (in SunOS, the area between the end of the data segment and the current position of the break).

It is typical for the heap to grow upward. This means that successive items that are added to the heap are added at addresses that are numerically greater than previous items. It is also typical for the heap to start immediately after the BSS area of the data segment. The end of the heap is marked by a pointer known as the "break" (Your programs will "break" if they reference past the break).

When the heap manager needs more memory, it can push the break further away using the system calls brk and sbrk. We don't call brk yourself explicitly, but if we malloc enough memory, brk will eventually be called.

stack segment

The stack segment is where local (automatic) variables are allocated. In C program, local variables are all variables declared inside the opening left curly brace of a function body including the main() or other left curly brace that aren’t defined as static. The data is popped up or pushed into the stack following the Last in First out (LIFO) rule.

On the standard PC x86 computer architecture it grows toward address zero; on some other architectures it grows the opposite direction.

A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack.When a function is called, a stack frame (or a procedure activation record) is created and PUSHed onto the top of the stack. This stack frame contains information such as the address from which the function was called and where to jump back to when the function is finished (return address), parameters, local variables, and any other information needed by the invoked function. The order of the information may vary by system and compiler.

When a function returns, the stack frame is POPped from the stack. Typically the stack grows downward, meaning that items deeper in the call chain are at numerically lower addresses and toward the heap.

Figure 2: Stack layout

When a program begins executing in the function main(), space is allocated on the stack for all variables declared within main(), as seen in Figure (a). If main() calls a function, func1(), additional storage is allocated for the variables in func1() at the top of the stack as shown in Figure (b). Notice that the parameters passed by main() to func1() are also stored on the stack.

If func1() were to call any additional functions, storage would be allocated at the new Top of stack as seen in the figure. When func1() returns, storage for its local variables is deallocated, and the Top of the stack returns to position shown in Figure (c). If main() were to call another function, storage would be allocated for that function at the Top shown in the figure. As can be seen, the memory allocated in the stack area is used and reused during program execution. It should be clear that memory allocated in this area will contain garbage values left over from previous usage.

Although it is theoretically possible for the stack and heap to grow into each other, the operating system prevents that event.

Check the PART-2 for detailed understanding of these sections with examples.

The relationship among the different sections/segments is summarized below.

Figure 3: Relationship between Sections and Segments

Deletion of a Node from Doubly Linked List

noreply@blogger.com (Ajith Adapa) — Thu, 01 Mar 2012 06:49:00 PST

This article is part of article series - "Datastructures".

Previous Article: Inserting a Node in Doubly Linked List.

Deletion of a Node

Let us say our current Doubly Linked List is as shown in Figure-1.

Figure 1: Current Doubly Linked List

Deleting First Node of the List

In HEAD

In NODE-2

Decrement LENGTH variable in HEAD so that it maintains proper count of Nodes in the List.

Pseudocode:

HEAD->FIRST = HEAD->FIRST->NEXT

NODE-2->PREV = NULL

decrement(HEAD->LENGTH)

Output:

Figure 2: After deleting the First Node in the List.

Deleting Middle Node from the List

Using a temporary Node pointer curPtr we have to traverse until NODE-2.

In NODE-1

In NODE-3

Decrement LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.

Pseudocode:

curPtr->PREV->NEXT = curPtr->NEXT

curPtr->NEXT->PREV = curPtr->PREV

decrement(HEAD->LENGTH)

Output:

Figure 3: After Deleting NODE-2 in the List.

Deleting Last Node in the List

Using a temporary Node pointer curPtr we have to traverse until the end Node of the List. So curPtr is now pointing to NODE-3.

In NODE-2

Decrement the LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.

Pseudocode:

curPtr->PREV->NEXT = NULL

decrement(HEAD->LENGTH)

Output:

Figure 4: After Deleting Last Node from the List.

Let us see sample 'C' code to the deletion of a Node operation

retVal
delNodeAtLoc(listHead *head, UINT32 loc)
{
    retVal ret = SUCCESS;
    UINT32 i;

    listNode *curPtr;

    if(head && head->first && loc && loc <= (head->length)) 
    {   
        curPtr = head->first;

        if (loc == 1)
        {   
            head->first = curPtr->next;

            if(head->first)
                head->first->prev = NULL;
        }   
        else 
        {   
            for(i=1; i<loc; i++) 
                curPtr = curPtr->next;

            curPtr->prev->next = curPtr->next;

            if(curPtr->next)
                curPtr->next->prev = curPtr->prev;
        }    

        dlist_freeNode(curPtr);
        head->length--;
    }
    else
        ret = FAILURE;

    return ret;
}

Inserting a Node in Doubly Linked List

noreply@blogger.com (Ajith Adapa) — Mon, 27 Feb 2012 04:30:00 PST

This article is part of article series - "Datastructures"

Previous Article: Doubly Linked List Next Article: Deletion of a Node from Doubly Linked List.

Insertion of a Node

Before we discuss about how to insert a NODE let us discuss few rules to follow at the time of insertion.

Check the location into which the user want to insert a new NODE. The possible locations where an user can insert a new node is in the range of 1 <= loc <= (length of list)+1. Let us say the length of the list is 10 & the user want to insert at location 12 (sounds stupid).

As we know we can traverse Bi-Directional in case of Doubly Linked Lists so we have to take care of PREV and NEXT variables in the NODE structure. We should also update the neighboring Nodes which are affected by this operation. If not we might break up the List somewhere or the other by creating a BROKEN LIST.

We have following scenarios in the case of insertion of a NODE.

Adding a Node at the start of the Empty List

Figure 1: Empty List and the newNode we want to add

NULL

In HEAD

In newNode

NULL

Increment the LENGTH variable in HEAD once insertion is successful to maintain the count of number of Nodes in the List.

Pseudocode:

HEAD->FIRST = newNode

newNode->PREV = NULL

newNode->NEXT = NULL

increment(HEAD->LENGTH)

Output:

Figure 2: After adding newNode in Empty List. (Changes in BLUE)

Adding a Node at the start of the Non-Empty List

Figure 3: A Doubly Linked List of Length 3.

In newNode

In curFirstNode

In HEAD

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

newNode->NEXT = HEAD->FIRST

HEAD->FIRST->PREV = newNode

HEAD->FIRST = newNode

newNode->PREV = NULL

increment(HEAD->LENGTH)

Output:

Figure 4: After adding newNode at location 1. (Changes in BLUE)

Adding a Node at the middle of the list.

Figure 5: Current Preview of the Doubly Linked List.

Traverse the Doubly Linked List until the Location 2. So our curPtr is pointing to Node 2.

In newNode

In NODE3

In NODE2

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

newNode->PREV = curPtr

newNode->NEXT = curPtr->NEXT

newNode->NEXT->PREV = newNode

curPtr->NEXT = newNode

increment(HEAD->LENGTH)

Output:

Figure 6: After adding newNode at Location 3 (Changes in BLUE)

Adding a Node at the End of the List

In Last Node

In newNode

Increment the LENGTH variable in HEAD to maintain the count of number of Nodes in the List.

Pseudocode:

curPtr->NEXT = newNode

newNode->PREV = curPtr

increment(HEAD->LENGTH)

Let us see the preview of the C code which does the insertion of a Node at a particular location.

This code is generic for all the possible scenarios explained above.

addNodeAtLoc(listHead *head, listNode *newNode, UINT32 loc)
{
    UINT32 i;
    retVal ret = SUCCESS;

    listNode *curPtr;

    if(head && newNode && loc && (loc <= (head->length)+1))
    {   
        if(loc == 1)
        {   
            newNode->prev = NULL;
            newNode->next = head->first;
    
            if(head->first)
                head->first->prev = newNode;

            head->first = newNode;
        }   
        else
        {   
            curPtr = head->first;

            for(i=1; i<(loc-1); i++)
                curPtr = curPtr->next;

            newNode->prev = curPtr;
            newNode->next = curPtr->next;

            if(curPtr->next)
                curPtr->next->prev = newNode;

            curPtr->next = newNode;
        } 

        head->length++;
    }
    else
        ret = FAILURE;

    return ret;
}

Previous Article: Doubly Linked List Next Article: Deletion of a Node from Doubly Linked List.

Implementation of Doubly Linked List in C

noreply@blogger.com (Ajith Adapa) — Fri, 24 Feb 2012 19:58:00 PST

In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called Nodes. Each Node contains two fields, called Links, that are references to the Previous and to the Next Node in the sequence of Nodes as well as field named Data.
For every Linked List we have something called Head which marks the starting of a list. So we have two main structures namely

Node
Head

Why we need a new structure for HEAD variable ?
Just for convenience I decided to have HEAD its own structure. You can even use the Node structure.

Node
Every Node in a Doubly Linked List has three main members namely

PREV
DATA
NEXT

As their names say

PREV - holds the memory location of the Previous Node in the List. If there are none we point towards NULL. For the First Node in the List PREV points to NULL.
NEXT - holds the memory location of the Next Node in the List. If there are none we point towards NULL. For the Last Node in the List NEXT points to NULL.
DATA - In simple words it holds Data. In our case it holds the memory location to the actual data to be held by the Node.

typedef struct node
{
    struct node *prev;
    void        *data;
    struct node *next;
}NODE;

Head

Head acts as the "head" of the List. Head structure has two members namely

LENGTH - holds the count of number of Nodes in the List.
FIRST - hold the memory location of the first Node in the List. If the List is EMPTY it points to NULL.

typedef struct head 
{
    unsigned int length;
    struct node  *first;
}HEAD;

NOTE: Our Head structure doesn't contain any pointer to the Tail of the List. Eventhough its a best way to include a pointer to Tail Node we decided to cover that implementation in Circular Doubly Linked List.

Figure 1: Basic structures used for Doubly Linked List Example

Pictorially, a Doubly Linked List can be depicted as shown Figure-2.

Figure 2: Doubly Linked List

In this introductory article let use see very basic operations which we don't discuss much in later articles.

Creating a Node

Whenever we have to add a new Node we have to create one dynamically.So we will have a function called createNode which creates a new Node and returns the pointer to it.

NODE* createNode()
{
    NODE *newNode = (NODE *)calloc(sizeof(NODE));

    return newNode;
}

Creating a Head

Since I have decided to have my own head structure I need to create a HEAD variable for every Doubly Linked List. So we have a to create HEAD variable which acts as the index to which we have add or delete a Node.

HEAD* createHead()
{
    HEAD *head = (HEAD *)calloc(sizeof(HEAD));

    return head;
}

Traversing a Doubly Linked List

Doubly Linked List are more convenient than Singly Linked List since we maintain links for bi-directional traversing. If we are given a pointer to a Node which is at a arbitrary position we can traverse in both directions and display the contents in the whole List.

But in a Singly Linked List we can only traverse in one direction from Head to Tail where as in Doubly Linked List we can traverse from Head to Tail as well as Tail to Head.

As usual the logic would be a simple while loop and traversing using the NEXT and PREV pointers in the Node to traverse to the desired location in the List.

Part-1 : Creating a Node in Doubly Linked List
Part-2 : Deleting a Node in Doubly Linked List

Notification Chains in Linux Kernel - Part 03

noreply@blogger.com (Ajith Adapa) — Sat, 11 Feb 2012 21:44:00 PST

Continuation after PART-2.

Notifying Events on a Chain
Notifications are generated with notifier_call_chain. This function simply invokes, in order of priority, all the callback routines registered against the chain. Note that callback routines are executed in the context of the process that calls notifier_call_chain. A callback routine could, however, be implemented so that it queues the notification somewhere and wakes up a process that will look at it.

NOTE: Similar to register and unregister functions we don't directly call notifier_call_chain function as we have wrapper functions for respective chains.

 <kernel/notifier.c>

 58 static int __kprobes notifier_call_chain(struct notifier_block **nl,
 59                     unsigned long val, void *v,
 60                     int nr_to_call, int *nr_calls)
 61 {
 62     int ret = NOTIFY_DONE;
 63     struct notifier_block *nb, *next_nb;
 64 
 65     nb = rcu_dereference(*nl);
 66 
 67     while (nb && nr_to_call) {
 68         next_nb = rcu_dereference(nb->next);
 69         ret = nb->notifier_call(nb, val, v);
 .
 76         nb = next_nb;
 77         nr_to_call--;
 78     }
 79     return ret;
 80 }

nl
Notification chain.

val
Event type. The chain itself identifies a class of events; val unequivocally identifies an event type (i.e., NETDEV_REGISTER).

v
Input parameter that can be used by the handlers registered by the various clients. This can be used in different ways under different circumstances. For instance, when a new network device is registered with the kernel, the associated notification uses v to identify the net_device data structure.

nr_to_call
Number of notifier functions to be called. Don't care value of this parameter is -1.

nr_calls
Records the number of notifications sent. Don't care value of this field is NULL.

Example of notifier chains in Network Subsystem
Let us see an example of using the notifier chains in bridge subsystem.

<net/bridge/br_notify.c>

 24 struct notifier_block br_device_notifier = {
 25     .notifier_call = br_device_event
 26 };

<net/bridge/br.c>

 30 static int __init br_init(void)
 31 {
 .
 48     err = register_netdevice_notifier(&br_device_notifier);
 .
 72 }

Once we fill the br_device_notifier we are registering to netdevice chain by calling the function register_netdevice_notifier(). netdev_chain is the head of the netdevice chain.

<net/core/dev.c>

245 static RAW_NOTIFIER_HEAD(netdev_chain);
.
1129 int register_netdevice_notifier(struct notifier_block *nb)
1130 {
.
1136     rtnl_lock();
1137     err = raw_notifier_chain_register(&netdev_chain, nb);
1138     if (err)
1139         goto unlock;
.
1177 }

When any events occur we invoke all the registered functions via notifier_call_chain function.

<net/core/dev.c>

1208 int call_netdevice_notifiers(unsigned long val, struct net_device *dev)
1209 {
1210     return raw_notifier_call_chain(&netdev_chain, val, dev);
1211 }

Below is the list of event types supported by netdevice:

<include/linux/notifier.h>

181 /* netdevice notifier chain */
182 #define NETDEV_UP   0x0001  /* For now you can't veto a device up/down */
183 #define NETDEV_DOWN 0x0002
184 #define NETDEV_REBOOT   0x0003  
.
188 #define NETDEV_CHANGE   0x0004  /* Notify device state change */
189 #define NETDEV_REGISTER 0x0005
190 #define NETDEV_UNREGISTER   0x0006
191 #define NETDEV_CHANGEMTU    0x0007
192 #define NETDEV_CHANGEADDR   0x0008
193 #define NETDEV_GOING_DOWN   0x0009
194 #define NETDEV_CHANGENAME   0x000A
195 #define NETDEV_FEAT_CHANGE  0x000B

Now it is upto to the notified to write a switch case to invoke the appropriate internal function in their subsystem for processing the respective event.

 <net/bridge/br_notify.c>

 34 static int br_device_event(struct notifier_block *unused, unsigned long event, void *ptr)
 35 {
 .
 43     /* not a port of a bridge */
 44     if (p == NULL)
 45         return NOTIFY_DONE;
 .
 49     switch (event) {
 50     case NETDEV_CHANGEMTU:
 51         dev_set_mtu(br->dev, br_min_mtu(br));
 52         break;
 53 
 54     case NETDEV_CHANGEADDR:
 55         spin_lock_bh(&br->lock);
 56         br_fdb_changeaddr(p, dev->dev_addr);
 57         br_stp_recalculate_bridge_id(br);
 58         spin_unlock_bh(&br->lock);
 59         break;
 60 
 61     case NETDEV_CHANGE:
 62         br_port_carrier_check(p);
 63         break;
 .
 72     case NETDEV_DOWN:
 73         spin_lock_bh(&br->lock);
 74         if (br->dev->flags & IFF_UP)
 75             br_stp_disable_port(p);
 76         spin_unlock_bh(&br->lock);
 77         break;
 78 
 79     case NETDEV_UP:
 80         if (netif_carrier_ok(dev) && (br->dev->flags & IFF_UP)) {
 81             spin_lock_bh(&br->lock);
 82             br_stp_enable_port(p);
 83             spin_unlock_bh(&br->lock);
 .
 98 }

We can say the whole notification mechanism is much more like call-back functions used to trigger appropriate functions when certain operation or an even happens.

Notification Chains in Linux Kernel - Part 02

noreply@blogger.com (Ajith Adapa) — Mon, 16 Jan 2012 19:32:00 PST

Continuation after PART-1.

Check the PART-3.

Blocking Notifier chains
A blocking notifier chain runs in the process context. The calls in the notification list could be blocked as it runs in the process context. Notifications that are not highly time critical could use blocking notifier chains.

Linux modules use blocking notifier chains to inform the modules on a change in QOS value or the addition of a new device.

<kernel/notifier.c>

186 int blocking_notifier_chain_register(struct blocking_notifier_head *nh,
187         struct notifier_block *n)
188 {
.
199     down_write(&nh->rwsem);
200     ret = notifier_chain_register(&nh->head, n);
201     up_write(&nh->rwsem);
202     return ret;
203 }
204 EXPORT_SYMBOL_GPL(blocking_notifier_chain_register)
.
216 int blocking_notifier_chain_unregister(struct blocking_notifier_head *nh,
217         struct notifier_block *n)
218 {
.
229     down_write(&nh->rwsem);
230     ret = notifier_chain_unregister(&nh->head, n);
231     up_write(&nh->rwsem);
232     return ret;
233 }
234 EXPORT_SYMBOL_GPL(blocking_notifier_chain_unregister);

Raw Notifier chains
A raw notifier chain does not manage the locking and protection of the callers. Also, there are no restrictions on callbacks, registration, or de-registration. It provides flexibility to the user to have individual lock and protection mechanisms.

Linux uses the raw notifier chain in low-level events.

<kernel/notifier.c>

297 int raw_notifier_chain_register(struct raw_notifier_head *nh,
298         struct notifier_block *n)
299 {
300     return notifier_chain_register(&nh->head, n);
301 }
302 EXPORT_SYMBOL_GPL(raw_notifier_chain_register);
.
314 int raw_notifier_chain_unregister(struct raw_notifier_head *nh,
315         struct notifier_block *n)
316 {
317     return notifier_chain_unregister(&nh->head, n);
318 }
319 EXPORT_SYMBOL_GPL(raw_notifier_chain_unregister);

SRCU Notifier chains
Sleepable Read Copy Update (SRCU) notifier chains are similar to the blocking notifier chain and run in the process context. It differs in the way it handles locking and protection. The SRCU methodology brings in less overhead when we notify the registered callers. On the flip side, it consumes more resource while unregistering. So it is advisable to choose this methodology where we use the notifier call often and where there’s very little requirement for removing from the chain.

<kernel/notifier.c>

370 int srcu_notifier_chain_register(struct srcu_notifier_head *nh,
371         struct notifier_block *n)
372 {
.
383     mutex_lock(&nh->mutex);
384     ret = notifier_chain_register(&nh->head, n);
385     mutex_unlock(&nh->mutex);
386     return ret;
387 }
388 EXPORT_SYMBOL_GPL(srcu_notifier_chain_register)
.
400 int srcu_notifier_chain_unregister(struct srcu_notifier_head *nh,
401         struct notifier_block *n)
402 {
.
413     mutex_lock(&nh->mutex);
414     ret = notifier_chain_unregister(&nh->head, n);
415     mutex_unlock(&nh->mutex);
416     synchronize_srcu(&nh->srcu);
417     return ret;
418 }
419 EXPORT_SYMBOL_GPL(srcu_notifier_chain_unregister);

Registering and Un-registering with a Chain
When a kernel component is interested in the events of a given notification chain, it can register it with the general function notifier_chain_register and to unregister we can use the function notifier_chain_unregister.

NOTE: The kernel also provides a set of wrappers around notifier_chain_register. We might have to use those wrapper functions instead of directly using the notification_chain_register.

<kernel/notifier.c>

 20 static int notifier_chain_register(struct notifier_block **nl,
 21         struct notifier_block *n)
 22 {
 23     while ((*nl) != NULL) {
 24         if (n->priority > (*nl)->priority)
 25             break;
 26         nl = &((*nl)->next);
 27     }
 28     n->next = *nl;
 29     rcu_assign_pointer(*nl, n);
 30     return 0;
 31 }

For each chain, the notifier_block instances are inserted into a list, which is sorted by priority. Elements with the same priority are sorted based on insertion time: new ones go to the tail. Accesses to the notification chains are protected by the notifier_lock lock. The use of a single lock for all the notification chains is not a big constraint and does not affect performance, because subsystems usually register their notifier_call functions only at boot time or at module load time, and from that moment on access the lists in a read-only manner (that is, shared).

Because the notifier_chain_register function is called to insert callbacks into all lists, it requires that the list be specified as an input parameter. However, this function is rarely called directly; generic wrappers are used instead.

<kernel/notifier.c>

 33 static int notifier_chain_unregister(struct notifier_block **nl,
 34         struct notifier_block *n)
 35 {
 36     while ((*nl) != NULL) {
 37         if ((*nl) == n) {
 38             rcu_assign_pointer(*nl, n->next);
 39             return 0;
 40         }
 41         nl = &((*nl)->next);
 42     }
 43     return -ENOENT;
 44 }

Notification Chains in Linux Kernel - Part 01

noreply@blogger.com (Ajith Adapa) — Mon, 16 Jan 2012 05:03:00 PST

Linux is a monolithic kernel. Its subsystems or modules help to keep the kernel light by being flexible enough to load and unload at runtime. In most cases, the kernel modules are interconnected to one another. An event captured by a certain module might be of interest to another module.

Typically, communication systems implement request-reply messaging, or polling. In such models, a program that receives a request will have to send the data available since the last transaction. Such methods sometimes require high bandwidth or they waste polling cycles.

To fulfill the need for interaction, Linux uses so called notification chains. These notifier chains work in a Publish-Subscribe model. This model is more effective when compared to polling or the request-reply model.

For each notification chain there is a passive side (the notified) and an active side (the notifier), as in the so-called publish-and-subscribe model:

The notified are the subsystems that ask to be notified about the event and that provide a callback function to invoke.

The notifier is the subsystem that experiences an event and calls the callback function.

NOTE: All the code samples are taken from Linux 2.6.24 kernel.

struct notifier_block
The elements of the notification chain's list are of type notifier_block:

<include/linux/notifier.h>

 50 struct notifier_block {
 51     int (*notifier_call)
(struct notifier_block *, unsigned long, void *);
 52     struct notifier_block *next;
 53     int priority;
 54 };

notifier_call - function to execute.

next - used to link together the elements of the list.

priority - the priority of the function. Functions with higher priority are executed first. But in practice, almost all registrations leave the priority out of the notifier_block definition, which means it gets the default value of 0 and execution order ends up depending only on the registration order (i.e., it is a semirandom order).

The notifier_block data structure is a simple linked list of function pointers. The function pointers are registered with ‘functions’ that are to be called when an event occurs. Each module needs to maintain a notifier list. The functions are registered to this notification list. The notification module (publisher) maintains a list head that is used to manage and traverse the notifier block list. The function that subscribes to a module is added to the head of the module’s list by using the register_xxxxxx_notifier API and deletion from the list is done using unregister_xxxxxx_notifier.

Types of Notifier Chains
Notifier chains are broadly classified based on the context in which they are executed and the lock/protect mechanism of the calling chain. Based on the need of the module, the notifiers can be executed in the process context or interrupt/atomic context. Thus, notifier chains are classified into four types:

Atomic Notifier Chains
As the name indicates, this notifier chain is executed in interrupt or atomic context. Normally, events that are time critical use this notifier. This also means it is a non-blockable call. Linux modules use atomic notifier chains to inform watchdog timers or message handlers.

<kernel/notifier.c>

 96 int atomic_notifier_chain_register(struct atomic_notifier_head *nh,
 97         struct notifier_block *n)
 98 {
.
102     spin_lock_irqsave(&nh->lock, flags);
103     ret = notifier_chain_register(&nh->head, n);
104     spin_unlock_irqrestore(&nh->lock, flags);
105     return ret;
106 }
107 EXPORT_SYMBOL_GPL(atomic_notifier_chain_register);
.
118 int atomic_notifier_chain_unregister(struct atomic_notifier_head *nh,
119         struct notifier_block *n)
120 {
.
124     spin_lock_irqsave(&nh->lock, flags);
125     ret = notifier_chain_unregister(&nh->head, n);
126     spin_unlock_irqrestore(&nh->lock, flags);
127     synchronize_rcu();
128     return ret;
129 }
130 EXPORT_SYMBOL_GPL(atomic_notifier_chain_unregister);

Check the PART-2

Printing logs based on log levels in C

noreply@blogger.com (Ajith Adapa) — Sat, 07 Aug 2010 07:35:00 PDT

LOG LEVELS ??
As per my definition LOG LEVEL means a way to differentiate the importance of logs in our application. We can divide the logs into categories based on their importance and effect for e.g. ERROR logs are more important than DEBUG logs.

Why do we need to print logs based on LOG LEVEL ??
It is really helpful in projects with millions of lines of source code where the user can't use #defines or #ifdef's in order to maintain DEBUG prints. It is really tiresome to maintain #defines and #ifdef atleast for printing logs.

printk which is a part of LINUX KERNEL supports printing logs based on LOG LEVEL and it is really helpful in debugging kernel.

printf or any of its brothers & sisters don't support the option to print logs depending upon the log levels.

I have written a sample program where we can create our own printf function with LOG LEVEL. At present I am just supporting the option to print a character, string and a integer.

#include <stdio.h>
#include <stdarg.h>

//LOG LEVELS
typedef enum
{
  LOG_DEFAULT,
  LOG_INFO,
  LOG_ERROR,
  LOG_DEBUG
}LOG_LEVEL;
 
void LOG_TRACE(LOG_LEVEL lvl, char *fmt, ... );

int main()
{
  int i =10;
  char *string="Hello World";
  char c='a';
       
  LOG_TRACE(LOG_INFO, "String - %s\n", string);
  LOG_TRACE(LOG_DEBUG, "Integer - %d\n", i);
  LOG_TRACE(LOG_INFO, "Character - %c\n", c);
       
  LOG_TRACE(LOG_INFO, "\nTOTAL DATA: %s - %d - %c\n", string, i, c);
  return 1;
}

/* LOG_TRACE(log level, format, args ) */
void LOG_TRACE(LOG_LEVEL lvl, char *fmt, ... )
{
  va_list  list;
  char *s, c;
  int i;

  if( (lvl==LOG_INFO) || (lvl==LOG_ERROR))
  {
     va_start( list, fmt );

     while(*fmt)
     {
        if ( *fmt != '%' )
           putc( *fmt, stdout );
        else
        {
           switch ( *++fmt )
           {
              case 's':
                 /* set r as the next char in list (string) */
                 s = va_arg( list, char * );
                 printf("%s", s);
                 break;

              case 'd':
                 i = va_arg( list, int );
                 printf("%d", i);
                 break;

              case 'c':
                 c = va_arg( list, int);
                 printf("%c",c);
                 break;

              default:
                 putc( *fmt, stdout );
                 break;
           }
        }
        ++fmt;
     }
     va_end( list );
  }
  fflush( stdout );
}

Implementation of Stack using Singly Linked Lists

noreply@blogger.com (Ajith Adapa) — Wed, 07 Jul 2010 00:02:00 PDT

Stacks are linear data structures which means the data is stored in what looks like a line (although vertically). In simple words we can say

A stack is a last in, first out (LIFO) abstract data type and data structure.

Basic usage of stack at the Architecture level is as a means of allocating and accessing memory.

We can only perform two fundamental operations on a stack: push and pop.

The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it.

Let us 'C' code for implementing a stack using Singly Linked Lists.

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

//Structure containing a Data part & a
//Link part to the next node in the List
struct Node
{
int Data;
struct Node *Next;
}*Head;

//Poping from a Stack
void popStack()
{
struct Node *tmp_ptr=NULL, *cur_ptr=Head;

if(cur_ptr)
{
   Head = Head->Next;
   free(cur_ptr);
}     
else  
   printf("\nStack is Empty");
}   

//Pushing into Stack
void pushIntoStack(int num)
{
struct Node *tmp_ptr=NULL;

if((tmp_ptr=(struct Node *)malloc(sizeof(struct Node))) != NULL)
   tmp_ptr->Data=num;
else
   printf("\nMemory Allocation Failed");

if(Head)
{
   tmp_ptr->Next=Head;
   Head=tmp_ptr;
}
else { //List is Empty
   Head=tmp_ptr;
   Head->Next=NULL;
}
}

//Displaying Stack
void displayStack()
{
struct Node *cur_ptr=Head;

if(cur_ptr)
{
    printf("\nElements in Stack:\n");
    while(cur_ptr)
    {
        printf("\t%d\n",cur_ptr->Data);
        cur_ptr=cur_ptr->Next;
    }
    printf("\n");
}
else
   printf("\nStack is Empty");
}

int main(int argc, char *argv[])
{
int i=0;

//Set HEAD as NULL
Head=NULL;

while(1)
{
  printf("\n####################################################\n");
  printf("MAIN MENU\n");
  printf("####################################################\n");
  printf(" \n1. Push into stack");
  printf(" \n2. Pop from Stack");
  printf(" \n3. Display Stack");
  printf(" \n4. Exit\n");
  printf(" \nChoose Option: ");
  scanf("%d",&i);

  switch(i)
  {
    case 1:
    {
        int num;
        printf("\nEnter a Number to push into Stack: ");
        scanf("%d",&num);
        pushIntoStack(num);
        displayStack();
        break;
    }

    case 2:
    {
        popStack();
        displayStack();
        break;
    }

    case 3:
    {
        displayStack();
        break;
    }

    case 4:
    {
        struct Node *temp;

        while(Head!=NULL)
        {
            temp = Head->Next;
            free(Head);
            Head=temp;
        }
        exit(0);
    }

    default:
    {
        printf("\nWrong Option choosen");
    }
  }/* end if switch */
}/* end of while */
}/* end of main */

References:
1. Wikipedia