Data Structures - C Programming

The Below Programs had written based upon my knowledge and not considered any rainy day scenarios(Negative/performance Issues). Please let me know if you find any discrepancy in the content. 


C Programs on Double Pointers
----------------------------- 

Double Pointer means it points the address of the pointer as shown below.

int **p; 

int *a;

int j=9;

 // Double Pointer points to the address of the pointer

p = &a  

// pointer holds the address of variable.

a = &j

p       =  Gives the address of pointer (&a) = 500 

*p     =  Gives the value present in the address of 500 which is 399 (a or &j). 

**p   =  Gives the value present in the address of 399 which is 4 (j).

 

#include<stdio.h>
#include<stdlib.h>
int main()
{
   int **i, *u, j=3;

   /* Double Pointer Points to address of the pointer */
   u = &j;
   /* Pointer Holds the address of the variable */
   i = &u;

  printf("The value of i:%u\n",  i);
  printf("The value of u:%u\n", &u);
  printf("The value of u:%u\n",  u);
  printf("The value of *i:%u\n", *i);
  printf("The value of &j:%u\n", &j);
  printf("The value of j:%u\n",   j);
}
output
====
[~]# gcc double_sample.c -o test.exe
[~]# ./test.exe
The value of i:3214414668
The value of u:3214414668
The value of u:3214414664
The value of *i:3214414664
The value of &j:3214414664
The value of j:3

Program for Double Pointers Memory Allocation
=============================================

#include<stdio.h>
#include<stdlib.h>
int main()
{
   int **p= NULL;
 
   /* Allocate the Memory for the Double Pointer */
   p = (int **)malloc(sizeof(int));
  /* Allocate the memory for the pointer which points by the 
   * Double pointer 
   */
  *p = (int *)malloc(sizeof(int));
 
  printf("The value of  p:%u\n",  p);
  printf("The value of *p:%u\n", *p);
  printf("The value of &p:%u\n", &p);
  
  /* Store the value in the Double Pointer */
  **p = 9;

  printf("The value of **p:%d\n", **p);
}

[~]# ./test.exe
The value of  p:134520840
The value of *p:134520856
The value of &p:3218864012
The value of **p:9

C Program for Double Link list 
-------------------------------

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

#define EXIT 10

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

NODE *head, *tail;

/* 
 * Create Linklist
 */ 
NODE *createLinkList(int data)
{
   NODE *newNode = NULL;

   newNode = (NODE *)malloc(sizeof(NODE *));
   newNode->prev = NULL;
   newNode->next = NULL;
   newNode->data = data;

   return newNode;
}
/*
 * InsertLinkList()
 */
void insertLinkList()
{
  NODE *new, *temp;
  int k=1;

  int data, pos;

  printf(" Enter the Data to be inserted in Linklist\n");
  scanf("%d", &data);
           
  new = createLinkList(data);

  if(head == NULL)
  {
    head = new;
    return;
  }
  printf(" Enter the Position of Linklist\n");
  scanf("%d", &pos);
 
  /* Insert front of the Node */
  if(pos ==1)
  {
    new->next = head;
    head->prev = new;
    head = new;
    return;
  }
  temp = head;

  while ((k< pos-1) && (temp->next != NULL))
  {
    temp = temp->next;
    k++;
  }
  /* Insert Last of the Node */
  if(temp->next == NULL)
  {
    temp->next = new;
    new->prev = temp;
  }
  /* Insert Middle Of the Node */
  else      
  {
     new->prev = temp;
     new->next = temp->next;
     temp->next->prev = new; 
     temp->next = new;
  }
}
/*
 * Delete
 */
void deleteLinkList(void)
{
  NODE *temp, *temp2;

  int k=1;

  int pos;

  printf(" Enter the Position of Node to be Deleted\n");
  scanf("%d", &pos);

  if(head !=NULL)
  {
    /* Delete Start */
    if(pos == 1)
    {
      temp = head;
      head = head->next;
     
      if(head != NULL)
        head->prev = NULL;

      free(temp);
      return;
    }
    temp = head;
    while((k< pos) && (temp->next!= NULL))
    {
      temp = temp->next;
      k++;
    }
    /* Delete Last Node */
    if(temp->next == NULL)
    {
       temp2= temp;
       if(temp->prev != NULL)
          temp->prev->next = NULL;
       free(temp2);
    }
    /* Delete Middle */
    else
    {
       temp2= temp;
       temp->prev->next = temp->next;
       temp->next->prev = temp->prev;
       free(temp2);
    }
   }
   else
   {
     printf("Nodes Are Empty \n");
     return;
   }
}
/*
 * Display()
 */

void display()
{
  NODE *temp;

  temp = head;

  printf("The Data is \n");
  while(temp!= NULL)
  {
    printf("%d\n", temp->data);
    temp = temp->next;
  }
}
/*
 * Main()
 */
int main()
{
   int ch, data, pos;
   do
   {
     ch=0;
     printf("\n Enter the Choice \n");
     printf("1. Insert \n");
     printf("2. Delete \n");
     printf("3. Display \n");
     printf("Enter 10 for EXIT \n");
     scanf("%d", &ch);
     switch(ch)
     {
        case 1:
             insertLinkList();
             break;
        case 2:
             deleteLinkList();
             break;
        case 3: display();
             break;
        default:
             printf("Invalid Choice \n");
             break;
      };
   }while(ch!=EXIT);
   return 0;
}

C Program for Circular Link list 
---------------------------------

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

#define EXIT 10

typedef struct node
{
   int data;
   struct node *next;
}NODE;

NODE *head, *last;

NODE *createLinkList(int data)
{
   NODE *newNode = NULL;

   newNode = (NODE *)malloc(sizeof(NODE *));
  
   newNode->next = NULL;
   newNode->data = data;

   return newNode;
}
/*
 * InsertLinkList()
 */
void insertLinkList()
{
  NODE *new, *temp;
  int k=1;

  int data, pos;

  printf(" Enter the Data to be inserted in Linklist\n");
  scanf("%d", &data);
            
  new = createLinkList(data);

  if(head == NULL)
  {
    head = new;
    head->next = head;
    last = head;
    return;
  }
  printf(" Enter the Position of Linklist\n");
  scanf("%d", &pos);

  if(pos ==1)
  {
    new->next = last->next;
    last->next = new;
    head = new;
    return;
  }
  temp = head;

  while ((k< pos-1) && (temp->next != head))
  {
    temp = temp->next;
    k++;
  }
  if(temp->next == head)
  {
    new->next = temp->next;
    temp->next = new;
    last = new;
  }
  else
  {
     new->next = temp->next;
     temp->next = new;
  }
}
/*
 * Delete
 */
void deleteLinkList(void)
{
  NODE *temp, *temp2;

  int k=1;

  int pos;

  printf(" Enter the Position of Node to be Deleted\n");
  scanf("%d", &pos);

  if(head !=NULL)
  {
    if(pos == 1)
    {
      if(head->next == head)
      {
         free(head);
         head= NULL;
      }
      else
      {
        temp2 = head;
        temp  = head->next;
        head->next = 0;
        head = temp;
        last->next = head;

        free(temp2);
        temp2= NULL;
      }
      return;
    }

    temp = head;
    while((k< pos-1) && (temp->next!= head))
    {
      temp = temp->next;
      k++;
    }
    if(temp->next == head)
    {
       temp2 = last->next;
       last->next = 0;
       temp->next = temp2;

       temp2 = last;
       last = temp;

       free(temp2);
       temp2 = NULL;
    }
    else
    {
       temp2= temp->next;
       temp->next = temp->next->next;
       free(temp2);
       temp2=NULL;
    }
   }
   else
   {
     printf("Nodes Are Empty \n");
     return;
   }
}
/*
 * Display()
 */
void display()
{
  NODE *temp;

  temp = head;
 
  printf("The Data is \n");
 
  if(temp != NULL)
  {
    if(temp == head)
      printf("%d\n", temp->data);

    temp = temp->next;

    while(temp!= head)
    {
      printf("%d\n", temp->data);
      temp = temp->next;
    }
  }
  else
  {
     printf(" Nodes are Empty \n");
  }
}
/*
 * Main()
 */
int main()
{
   int ch, data, pos;
   do
   {
     ch=0;
     printf("\n Enter the Choice \n");
     printf("1. Insert \n");
     printf("2. Delete \n");
     printf("3. Display \n");
     scanf("%d", &ch);
   
     switch(ch)
     {
        case 1:
              insertLinkList();
              break;
        case 2:
              deleteLinkList();
              break;
        case 3: display();
             break;

        default:
          printf("Invalid Choice \n");
          break;
      };
   }while(ch!=EXIT);
   return 0;
}

Finite State Machine Implementation in C for Real Time Applications

 

Dear Reader,

  In this post, you can find the Finite state Machine Implementation in C useful for real time applications.

Please refer my earlier blog post "Simple finite state Machine for Beginners" to get basics of FSM.

The current implementation of FSM contains three states as STATE_1, STATE_2 and STATE_3 and three events as EVENT_1, EVENT_2, EVENT_3.

FSM works based on the events which are been triggered during at point of time. 

e.g:

Case 1 : If the FSM is in STATE_1 and FSM receives an EVENT_2 then it shall call the respective action function and change it next state as  STATE_2.

 Case 2: If the FSM is in STATE_2 and FSM receives an EVENT_2 then it remains in the same state as STATE_2.

 

 

 Finite State Machine Implementation In C

 ================================

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

/* This program Implements the Finite state Machine which contains
 * 3 states as STATE_1, STATE_2, STATE_3 and 3 EVENTS
 * EVENT_1, EVENT_2, EVENT_3 as depicted below

 STATES/EVENTS  | EVENT_1 | EVENT_2 | EVENT_3 | EVENT_4  
 ======================================================
 STATE_1        |
 ----------------
 STATE_2        |
 ----------------
 STATE_3        |
 ----------------
*/

/*
 * Declare states
 */
typedef enum states
{
   INVALID_STATE = 0,
   STATE_1,
   STATE_2,
   STATE_3,
   MAX_STATES
}FSMStates;

/*
 * Declare Events
 */
typedef enum events
{
   INVALID_EVENT = 0,
   EVENT_1,
   EVENT_2,
   EVENT_3,
   MAX_EVENTS
}FSMEvents;

/* Call back Function */
typedef void (*FSMActionFunc)(void *data1);

/* =========================
 * Declaration of FSMStruct
 * =========================
 * FSM Struct should contain
 * ACTION function and Next State
 */
typedef struct FSM
{
   /* Action Function */
   FSMActionFunc  actionFunc;
   /* Next State */
   FSMStates      nextState;
}FSMStruct;


/* Declare FSMStruct Variable */
FSMStruct FSMArray[MAX_STATES][MAX_EVENTS];

/* The Handle Functions are declared Here */
unsigned char currentState;

void processFSMEvent(unsigned int event);
void handle_FSM_EVENT_1(void *data1);
void handle_FSM_EVENT_2(void *data1);
void handle_FSM_EVENT_3(void *data1);

void  initialiseFSM(void)
{
   /* Memset to FSMArray to Zero */
   memset(FSMArray, 0x00,  sizeof(FSMStruct));

   /* Intial State */
   currentState = STATE_1;

   /* STATE_1 Intialisation */
   FSMArray[STATE_1][EVENT_1].actionFunc = handle_FSM_EVENT_1;
   FSMArray[STATE_1][EVENT_1].nextState  = STATE_1;

   FSMArray[STATE_1][EVENT_2].actionFunc = handle_FSM_EVENT_2;
   FSMArray[STATE_1][EVENT_2].nextState  = STATE_2;
 
   FSMArray[STATE_1][EVENT_3].actionFunc = handle_FSM_EVENT_3;
   FSMArray[STATE_1][EVENT_3].nextState  = STATE_3;

   /* STATE 2 */
   FSMArray[STATE_2][EVENT_1].actionFunc = handle_FSM_EVENT_1;
   FSMArray[STATE_2][EVENT_1].nextState  = STATE_1;
  
   FSMArray[STATE_2][EVENT_2].actionFunc = handle_FSM_EVENT_2;
   FSMArray[STATE_2][EVENT_2].nextState  = STATE_2;

   FSMArray[STATE_2][EVENT_3].actionFunc = handle_FSM_EVENT_3;
   FSMArray[STATE_2][EVENT_3].nextState  = STATE_3;
  
   /* STATE 3 */
   FSMArray[STATE_3][EVENT_1].actionFunc = handle_FSM_EVENT_1;
   FSMArray[STATE_3][EVENT_1].nextState  = STATE_1;

   FSMArray[STATE_3][EVENT_2].actionFunc = handle_FSM_EVENT_2;
   FSMArray[STATE_3][EVENT_2].nextState  = STATE_2;
  
   FSMArray[STATE_3][EVENT_3].actionFunc = handle_FSM_EVENT_3;
   FSMArray[STATE_3][EVENT_3].nextState  = STATE_3;
}

/*
 * Handle Event-1  Fn
 */
void handle_FSM_EVENT_1(void *data1)
{
   char *buffer = (char *)data1;
   printf("--------------------------------------------------------------\n");
   printf("OUTPUT OF FSM :In function handle_FSM_EVENT_1 : %s\n", buffer);
   printf("--------------------------------------------------------------\n");
}
/*
 * Handle Event-2  Fn
 */
void handle_FSM_EVENT_2(void *data1)
{
   char *buffer = (char *)data1;
   printf("--------------------------------------------------------------\n");
   printf("OUTPUT OF FSM : In function handle_FSM_EVENT_2 : %s\n", buffer);
   printf("--------------------------------------------------------------\n");
}
/*
 * Handle Event-3  Fn
 */
void handle_FSM_EVENT_3(void *data1)
{
   char *buffer = (char *)data1;

   printf("--------------------------------------------------------------\n");
   printf("OUTPUT OF FSM : In function handle_FSM_EVENT_3 : %s\n", buffer);
   printf("--------------------------------------------------------------\n");
}
/*
 * processFSMEvent()
 */
void processFSMEvent(unsigned int event)
{
  char data1[20];

  if ((event > INVALID_EVENT) && (event < MAX_EVENTS)) 
   {
     if(event == EVENT_1)
     {
       strcpy(data1, "EVENT_1 Data\n");
     }
     else if(event == EVENT_2)
     {
       strcpy(data1, "EVENT_2 Data\n");
     }
     else
     {
       strcpy(data1, "EVENT_3 Data\n");
     }
    
     /* Call the Respective Action Function */
     FSMArray[currentState][event].actionFunc(data1);

     /* Set the Current State */
     currentState =  FSMArray[currentState][event].nextState;
   }
  else
   {
      printf(" Event is Invalid \n");
   }
}
/*
 * Main fn
 */
int main()
{
   unsigned int event; char ch;

   /* Initialise FSM */
   initialiseFSM();

  do
   {     
      printf("Enter the Event(1-3) To be Trigger in FSM STATE Machine \n");
      scanf("%d", &event);

      /* Process FSM Events */
      processFSMEvent(event);

      printf("Do You Want To Run STATE MACHINE Further ....\n");
      printf("For exit enter 100-> Other wise to Continue Enter any  Number\n");
      scanf("%d", &ch);

   }while(ch!= 100);
}

BITMAP Implementation in C

Dear Reader,

    In this post, i would like to bring you about BIT MAP and its implementation in C used for real time applications

What is BIT MAP?
   Bit Maps are also called as " BIT Array".
   Bit array means that store bits.

Why  BIT MAPS are required?
   Using Bit Array, applications achieve bit-level parallelism in hardware to perform operations quickly.

Some more Info..

Each bit array is mapped to some domain, the bit values can be interpreted as

1. Dark/Light  2. Absent/Present   3. Locked/Unlocked    4. Valid/Invalid

In other words, there are only two possible values.

• 1 bit indicates the value is SET in a number
• 0 bit indicates the value is UNSET in a number

For Bit Maps 

•     OR (|)  is used to set the bit (e.g  n |= (1<<x) )
•     AND (&) is used to clear the bit  (e.g   n &= ~(1<<x))

 How to Implement the Bit Maps?

Step 1:  Create a bit Map Array.
             unsigned char bit_map[2];

Step 2: Calculate the Bit Map array Index and shift index (How many bits needs to shift).
            < If the user gives  bit_position  input starts from 1>
            bit_map_array_index = (bit_position - 1) /8   
            shift_Index = (bit_position - 1)%8

           < If the user gives  bit_position  input starts from 0>
            bit_map_array_index = bit_position /8   
            shift_Index = bit_position %8

Step 3: Set the Bit in the Bit Map using
            bit_map[bit_map_array_index] |= (1<<shift_Index)

Step 4: Clear the Bit in the Bit Map using
            bit_map[bit_map_array_index] &=  ~(1<<shift_Index)

 Please find the below program for Better Understanding of Bit Maps in C.

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

#define EXIT 100

#define BITMAP_LEN 2
#define BYTE_LEN   8

/* Debug OutPut */
void printTheDebugOutput(unsigned char *bit_array)
{
   int i, j;

   /* Array is 2 bit_array[0] and [1] */
   for (i=0 ; i<BITMAP_LEN; i++)
   {
     /* Bits 0..7 */
     for(j=1; j<=BYTE_LEN; j++)
     {
        if(bit_array[i] & (1 << (j-1)))
        {
           printf("In BIT_MAP[%d] the position of Bit SET : %d\n",
                                   i, j);
        }
     }
   }
}

/*
 *  Main() function
 */
int main()
{

  unsigned int bit_position, setOrUnsetBit, ch;
  unsigned char bit_Map_array_index, shift_index;

  /* Declare Bit Array and intialised to Zero
   * This BIT_MAP is generally assigned to one domain.
   * Here BIT MAP (Array of Bits) are used for Debugging Mechanism
   */
  unsigned char bit_map[BITMAP_LEN] = { 0 };
 
  /* In Bit- Maps , there are two options,
   * either  Set (OR |) or  Unset (AND &) bit.
   */
 do
 {
    /* Here the Max number of bits is 16 ranging from 1..16 */
    printf("Enter the Bit position (bit starts from 1 and Ends at 16) \n");
    scanf("%d", &bit_position); 

    /*
     * Set/Unset the Bit Map indicates which bits you want to enable 
     */
    printf(" Do you want to set/unset the Bit (1 or 0) \n");
    scanf("%d", &setOrUnsetBit);

    /* LOGIC as follows */
    /* Find Out the Index and and as well as Shift Index */

    /* It Give output as 0 or 1 ( for Bit Position 1..16) */
    bit_Map_array_index = (bit_position-1) / 8;

    /* Always give output as 0...7 ( for Bit Position 1..16)*/
    shift_index =  (bit_position-1) % 8;

    printf("The bit_position : %d shift Index : %d\n", bit_position, shift_index);

    /* If set is true */
    if( setOrUnsetBit)
     {        
       /* Set the Bit Array */
       bit_map[bit_Map_array_index] |= 1<<shift_index;                
     }
    else
     { 
        /* Clear the Bit Array */ 
        bit_map[bit_Map_array_index] &= ~(1<<shift_index);        
     }
    printf(" The Bit MAP Array : %d\n", bit_map[bit_Map_array_index]);
    printTheDebugOutput(bit_map);
   
    printf(" Do You want to Continue then Enter any Number"
           "and for Exit then enter 100\n");
    scanf("%d", &ch);

  }while(ch != 100);
 return 0;
}


Please refer in the blog for DEBUG LOG IMPLEMENTATION USING BIT MAP.