Any type can be qualified by the type qualifiers const or volatile.In simple declarations, the type qualifier is simply another keyword in the type name, along with the basic type and the storage class.

Syntax for the const and volatile keywords

int * volatile x;    /* x is a volatile pointer to an int */
int * const y = &z;  /* y is a const pointer to the int variable z */

For a pointer to a volatile or const data object, the type specifier, qualifier, and storage class specifier can be in any order. For example:

volatile int *x;         /* x is a pointer to a volatile int
    or                                                      */
int volatile *x;         /* x is a pointer to a volatile int*/
 
const int *y;            /* y is a pointer to a const int
    or                                                      */
int const *y;            /* y is a pointer to a const int   */

In the following example, the pointer to y is a constant. You can change the value that y points to, but you cannot change the value of y:

int * const y

In the following example, the value that y points to is a constant integer and cannot be changed. However, you can change the value of y:

const int * y

For other types of volatile and const variables, the position of the keyword within the definition (or declaration) is less important. For example:

volatile struct omega 
{
  int limit;
  char code;
} group;

provides the same storage as:

struct omega 
{
  int limit;
  char code;
} volatile group;

In both examples, only the structure variable group receives the volatile qualifier. Similarly, if you specified the const keyword instead of volatile, only the structure variable group receives the const qualifier. The const and volatile qualifiers when applied to a structure, union, or class also apply to the members of the structure, union, or class.

Although enumeration, class, structure, and union variables can receive the volatile or const qualifier.enumeration, class, structure, and union tags do not carry the volatile or const qualifier. For example, the blue structure variable does not carry the volatile qualifier:

volatile struct whale 
{
  int weight;
  char name[8];
} green;
struct whale blue;

The keywords volatile and const cannot separate the keywords enum, class, struct, and union from their tags. i.e

struct volatile whale //compiler gives error
{
  //.....
}blue; 
 
Struct const whale   //compiler gives error
{  
  //......
}blue;

An item can be both const and volatile. In this case the item cannot be legitimately modified by its own program but can be modified by some asynchronous process.

extern const volatile int real_time_clock;

may be modifiable by hardware(because of volatile), but cannot be assigned to, incremented, or decremented(because of const).

Constant as a promise:

Const is a promise that you make to the compiler not to modify. The compiler may therefore be able to make certain optimizations, such as placing a const-qualified variable in read-only memory.

C and C++ permit certain conversions between similar pointer types that differ only in their use of const. For example, given:

T *p;
...
void f(T const *qc);

a program can call f(p). In passing p to f, the program converts p’s value from “pointer to T” into “pointer to const T.” This is a valid conversion.
In contrast, given:

 
T const *pc;
...
void g(T *q);

calling g(pc) produces a compile-time error. The compiler rejects the attempt to convert pc’s value from “pointer to const T” into “pointer to T.”

It’s easy to see the rationale for these conversion rules once you start to think of const as a promise. you need not make any promises, but once you make one, you must keep it. Here’s how it applies.
The presence of const in a declaration such as:

int const *p;

is effectively a promise that the program will not use a value obtained directly or indirectly from p to modify any int objects. The compiler enforces the promise by rejecting any operation that attempts to modify an object accessed as *p, as in:

*p += 3;	// error
++(*p);     // error

Neither expression will compile.

The declaration for p is not a promise that p will point only to constant objects. In fact, p can point to either const or nonconst objects. It’s just that p promises to treat any objects it might point to as if they all were constant.

For example, the Standard C function strlen is declared as:

size_t strlen(char const *s);

In effect, strlen promises not to alter the characters of any array passed to it. Calling strlen(buf), where buf is some character array, doesn’t promise that the characters in buf won’t change. It only promises that strlen won’t be the one to change them.

Once you understand const as a promise, it’s easy to see why, given:

T const *pc;
...	
void g(T *q);

you can’t call g(pc). The declaration of pc promises that the program won’t use the value in pc to modify any T objects. However, the declaration for g’s parameter q makes no such promise. This doesn’t mean that function g will necessarily change the value that q points to, but it does mean that g is leaving that option open. Therefore, the compiler can’t entrust q with a copy of pc, because g might then use q to violate the promise in pc’s declaration.
On the other hand, given:

 
T *p;
...
void f(T const *qc);

then calling f(p) poses no problem. In this case, p’s declaration makes no promises, so calling f(p) can’t violate any promise. However, the declaration for f’s parameter qc makes a promise that f won’t use the pointer value in qc to modify any T objects. The compiler will enforce this promise when it compiles the body of f. This means, for example, that f must not call g(qc), because g’s parameter q doesn’t keep the promise.

Volatile as a promise:

A const object is one whose value the program can’t change, a volatile object is one whose value might change spontaneously and unexpectedly. That is, when you declare an object to be volatile, you’re telling the compiler that the object might change state even though no statements in the program appear to change it.

This situation generally only arises when you’re directly accessing special hardware registers, usually when writing device drivers. The compiler should not assume that a volatile-qualified variable contains the last value that was written to it, or that reading it again would yield the same result that reading it last time did. The compiler should therefore avoid making any optimizations which would suppress seemingly-redundant accesses to a volatile-qualified variable. Examples of volatile locations would be a clock register (which always gave an up-to-date time value each time you read it), or a device control/status register, which caused some peripheral device to perform an action each time the register was written to.
Most processors can perform operations faster when the operands reside in CPU registers rather than in ordinary memory. Compilers can optimize operations on nonvolatile objects by reading an object’s value into a CPU register, working with that register for a while, and eventually writing the value in the register back to the object. Compilers can’t do this sort of optimization with volatile objects. Every time the source program says to read from or write to a volatile object, the compiled code must do so.
Even though volatile has a different meaning from const, you can still regard volatile as a promise. The presence of volatile in a declaration such as:

T volatile *pv;

is effectively a promise that the compiler won’t try to optimize the accesses to or from any T object referenced via a value obtained directly or indirectly from pv. By analogy with const, this is not a promise that pv will point only to volatile T objects; pv can point to either volatile or nonvolatile T objects. It’s just that pv promises to treat any T objects it might point to as if they all were volatile.
Once you understand volatile as a promise, it’s no surprise that the conversion rules regarding “pointer to volatile” are identical to those regarding “pointer to const.” For example, given:

T volatile *pv;
...
void g(T *q);

you can’t call g(pv). The declaration of pv promises that the program will treat whatever pv points to as if it were volatile. However, the declaration for g’s parameter q makes no such promise. Therefore, the compiler can’t entrust q with a copy of pv, because q might violate the promise.
On the other hand, given:

T *p;
...
void h(T volatile *qv);

then calling f(p) compiles without complaint. In this case, p’s declaration makes no promises, so calling h(p) can’t violate anything. However, the declaration for h’s parameter qv makes a promise that the compiler won’t optimize the accesses to any T objects accessed via pv. The code generated for h’s function body might be less than optimal, but it won’t mistreat any T objects.

Who?s making the promise?

If const and volatile are indeed promises, who’s really making those promises?
Const is a promise that you make to the compiler. When you declare p as a “pointer to const T,” you’re promising the compiler that you (or your program, if you prefer) will treat *p as a nonmodifiable object. Moreover, you’re enlisting the compiler’s aid in helping you keep that promise, something it’s more than happy to do.

On the other hand, volatile is a promise that you elicit from the compiler. When you declare p as a “pointer to volatile T,” you’re asking the compiler to promise you that it won’t optimize any accesses to *p. In response, the compiler demands that you help it keep that promise by obeying certain conversion rules.

Popularity: 11%

Expressions that refer to memory locations are called “l-value” expressions. An l-value represents a storage region’s “locator” value,
or a “left” value, implying that it can appear on the left of the equal sign (=). L-values are often identifiers.

Expressions referring to modifiable locations are called “modifiable l-values.” A modifiable l-value cannot have an array type, an incomplete type, or a type
with the const attribute. For structures and unions to be modifiable l-values, they must not have any members with the const
attribute. The name of the identifier denotes a storage location, while the value of the variable is the value stored at that location.

An identifier is a modifiable l-value if it refers to a memory location and if its type is arithmetic, structure, union, or pointer. For
example, if ptr is a pointer to a storage region, then *ptr is a modifiable l-value that designates the storage region to which ptr points.

Any of the following C expressions can be l-value expressions:
      ->An identifier of integral, floating, pointer, structure, or union type
     ->A subscript ([ ]) expression that does not evaluate to an array
     ->A member-selection expression (–> or .)
     ->A unary-indirection (*) expression that does not refer to an array
     ->An l-value expression in parentheses
     ->A const object (a nonmodifiable l-value)

The term “r-value” is sometimes used to describe the value of an expression and to distinguish it from an l-value. All l-values are
r-values but not all r-values are l-values.

Some examples of correct and incorrect usages are:
i = 7;            // Correct. A variable name, i, is an l-value.
7 = i;            // Error. A constant, 7, is an r-value.
j * 4 = 7;        // Error. The expression j * 4 yields an r-value.
*p = i;           // Correct. A dereferenced pointer is an l-value.
const int ci = 7; // Declare a const variable.
ci = 9;           // ci is a nonmodifiable l-value, so the
                  //  assignment causes an error message to
                  //  be generated.
((i < 3) ? i : j) = 7; // Correct. Conditional operator (? :)
                       //  returns an l-value.

Popularity: 7%

A reentrant function is one that can be used by more than one task concurrently without fear of data corruption.Whereas, a non-reentrant function is one that cannot be shared by more than one task unless mutual exclusion to the function is ensured either by using a semaphore or by disabling interrupts during critical sections of code.A reentrant function can be interrupted at any time and resumed at a later time without loss of data. Reentrant functions either use local variables or protect their data when global variables are used.

In the early days of programming, non-reentrancy was not a threat to programmers; functions did not have concurrent access and there were no interrupts. In many older implementations of the C language, functions were expected to work in an environment of single-threaded processes.However, now concurrent programming is common practice and one should be aware of the pitfalls.It will be very difficult to figure out the bug caused when a signal handling functions triggers a non-reentrant function.

Typically a reentrant function does not hold static data over successive calls, does not return a pointer to static data,should not call any non-reentrant functions, uses local data or protection of global data by taking a local copy of the variable.

Typically a non-reentrant function calls a malloc or free, uses the static data structures, will be a part of input-output operations.

Popularity: 13%

Please visit my earlier post linked lists for basics of linked lists. Visit this post for circular double linked lists

What is circular linked list?

Circular Linked lists are chain of records/nodes, one record/node points to the next, and last node/record pointing to the first node instead of pointing to a sentinel. Record/node holds the data.

Why circular linked lists?

Circular linked lists can be traversed from anywhere (given any node) in the list, which gives flexibility and it also enahnces efficiencies of some operations however it complicates operations by inducing special cases to deal with circularity of list

How circular linked lists look like?

Operations On Circular Linked Lists:

Inserting a Node:

//insert after a known node and return the inserted node
Node *insert(Node *after, void *data)
{
  Node* n;
  n = (Node *) malloc (sizeof(Node));
  n->info = data;

  //incase header node is not created
  if (!after)
  {
    n->next = n;
    return n;
  }

  n->next = after->next;
  after->next = n;

  return n;
}

Deleting a Node:

//delete after a known node and return the node after deleted node
Node *delete(Node *after)
{
  Node* tmp;

  if (!after || (after == after->next))
  {
    return NULL;
  }

  tmp = after->next;

  after->next = tmp->next;
  free(tmp);

  return after->next;

}

Printing Circular list:

//given a node in list, prints entire list after the node
int printlist(Node *h)
{
  Node* t = h;
 
  while(t)
  {
    printf(" %d <->", t->info);
    t = t->next;
    if (t == h)
    {
      printf(" Circular\n");
      return 0;
    }
  }
 
  printf(" NULL\n");
  return 0;
}

Searching Circular List:

//given any node in list, search entire list
Node *searchlist(Node *h, void *info)
{
  Node* after = h;
 
  //search all nodes after n (if any)
  while(after)
  {
    if (after->info == info)
    {
      return after;
    }
    after = after->next;
    if (after == after->next)
    {
      break;
    }
  }
 
 
  return NULL;
}

Destroy Circular List

destroylist(Node **n)
{
  Node *tmp, *h;
 
  if (!n || !*n)
  {
    return;
  }
 
  h = *n;
 
  while(*n)
  {
    tmp = (*n)->next;  
    free(*n);
    *n = tmp;
    if (*n == h)
    {
      break;
    }
  }
 
  *n = NULL;
}

Reverse Circular List:

void reverse(Node** headRef)
{
  Node* result = NULL;
  Node* current = *headRef;
  Node* next;
 
  while (current != NULL)
  {
    next = current->next; // tricky: note the next node
    current->next = result; // move the node onto the result
    result = current;
    current = next;
    if (current == *headRef)
    {
      break;
    }
  }
  (*headRef)->next = result;
  *headRef = result;
}

Download full source code here

Popularity: 43%

Download [C++ Reference Card]

Popularity: 11%

Printing a linked list in reverse order without actually reversing the linked list can be done by a recursive routine or using a stack.

Lets us see a recursive routine first…

In recursive routine go to the end then print the nodes, i.e. recursive call comes before printing the node… Here is the function…

void printreverse(Node *node)
{
  if (node)
  {
    printreverse(node->next);
    printf("%d -> ",node->info);
  }
}

Reversing the list using stack:
Push all the nodes, pop one by one and print them… Here is the program for this..

void printreverse(Node* node)
{
  Node *tmpnode;
 
  Stack *stack = CreateStack();
 
  while(node)
  {
    Push(stack, node);
    node = node->next;
  }
 
  tmpnode = Pop(stack);
 
  while(tmpnode)
  {
    tmpnode = Pop(stack);
    printf("%d -> ", tmpnode->info);
  }
 
  DestroyStack(stack);
}

Popularity: 38%

Q:Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 40 soldiers surrounded by romans. The legend has it that preferring suicide to capture, the Jews decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. Josephus, not keen to die, quickly found the safe spot in the circle and thus stayed alive.

Requirements:

1. Circular linked list must be used.
2. The sequence starts from 1, therefore you won’t see a 0 appear in the sequence.The number of people and number of skips must be larger than 0
   (>0).

Program:

/*--------------------------------------------
Author : UTSAV CHATURVEDI
utsavchaturvedi [AT] yahoo.com
BHOPAL (M.P).
---------------------------------------------*/
 
#include<stdio.h>
typedef struct node
{
  int soilder;
  struct node * next;
}q;
 
q sol_q;
 
q *current,*head,*save;
int tot_soilders=0;
 
void freelist()
{
  int i;
  current = head;
  for (i=1;i<=tot_soilders;i++);
  {
    current = current->next;
    free(head);
    head = current;
  }
}
 
q * getnode()
{
  q *temp;
  temp = (q *) malloc(sizeof(q));
  if (temp == NULL)
  {
    printf("\n Memory allocation Failure");
    exit(1);
  }
  else
    return(temp);
}
 
void create_list(int n)
 {
   q *temp;
   int i;
   if (n<=1)
   {
     printf("\n There Should be atleast 2 soilders for Jousphs Problem!");
     getch();
     return;
   }
   current = getnode();
   current->soilder = 1;
   current->next = current;
   head = current;
   for (i=2;i<=n;i++)
   {
     temp = getnode();
     current->next = temp;
     current = temp;
     current->soilder = i;
   }
   current->next = head;
   tot_soilders = n;
 }

void display()
{
  if (head == NULL)
  {
    printf("\nNo Soilders in the Queue");
    return;
  }
  printf("%d",head->soilder);
  printf("%c ",2);
  current = head->next;
  while( current != head)
  {
    printf("%d";,current->soilder);
    printf("%c ",2);
    current = current->next;
  }
  return;
}
 
q *tail()
{
  q *temp;
  current = head->next;
  while (current != head)
  {
    temp = current;
    current = current->next;
  }
  return(temp);
}
 
int left_after_sucide(int by_n)
{
  int i=1,j,dead_sol;
  current = head;
  save = tail();
 
  while (i<tot_soilders)
  {
    for (j=1;j<by_n;j++)
    { 
      save = current;
      current = current->next; 
    }
    save->next = current->next;
    if (current == head) head = current->next;
    dead_sol = current->soilder;
    free(current);
    display();
    printf("\n\n%d%c is Dead \n%c RIP",dead_sol,1,5);
    getch();
    current = save->next;
    i++;
  }
  head = current;
  display();
  tot_soilders = 1;
  return(head->soilder);
}

main()
{
  int ch,n;
  head = NULL;
  do
  {
    printf("\n1. For soilder list creation");
    printf("\n2. For Displaying soilder list");
    printf("\n3. For Sucide");
    printf("\n0. For Exit");
    scanf("%d",&ch);
 
    switch(ch)
    {
    case 1:
      printf("\nEnter the total no. of soilders");
      scanf("%d",&n);
      create_list(n);
      break;
    case 2:
      display();
      getch();
      break;
    case 3:
     if (tot_soilders <= 1)
      printf("There Should Be Atleast 2 Soilders in the List");
     else
     {
       printf("\nEnter the no by which sucide is to be commited");
       scanf("%d",&n);
      if (n<1) printf("\nInvalid Number!");
      else
      printf("\nThe only Soilder left after "
      "sucide session is %d%c",left_after_sucide(n),2);
    }
    getch();
    break;
 
    case 0:
    return;
 
    default :
    printf("\nINVALID CHOICE");
    getch();
    }
  } while (ch!=0);
  freelist();
}

download entire file in C source code…

Popularity: 14%

Quicksort is the fastest known sorting algorithm in practice. Its average running time is O(nlogn). It is based on devide and conquer idea:
partition into two lists and put them back together again. It does more work on the divide side, less on the combine side.

The basic algorithm is
1)pick any element (called as Pivot) in list
2)Partition the list as two parts, first part contains all the elements which are less than pivot, the other contain all the elements which are greater than pivot
3)do quicksort recursively on sub lists

Regarding step1:
Any element can be selected as pivot, but some choices may cause bad performance. Example. first element everytime: this pivot cause bad performance on presorted or lists in reverse sorted order, because all elements go into one sublist. One safe strategy is choosing pivot randomly.

regarding Step2:
As already pointed out quicksort does most of the work while partitioning the lists, so this is the step which is a bit complex..

both step1 and 2 are represented graphically below…

Here is the program to quicksort arrays

void Swap(int *a, int *b)
{
  int tmp;
  tmp = *b;
  *b=*a;
  *a=tmp;
}
 
int SelectPivot(int a[], int left, int right)
{
  int center = (left+right)/2;
  Swap(&a[center], &a[right]);
  return a[right];
}

 
void QSort(int a[], int left, int right)
{
  int i,j;
  int pivot;
 
  if (left >= right)
  {
    return;
  }
 
  pivot = SelectPivot(a, left, right);
  i = left;
  j = right-1;
 
  for(;;)
  {
    //start partitioning the list
    for(;a[i]<pivot;i++);
    for(;a[j]>pivot;j- -);
    if (i<j)
      Swap(&a[i], &a[j]);
    else
      break;
  }
 
  //restore pivot
  Swap(&a[i], &a[right]);
 
  QSort(a, left, i-1);
  QSort(a, i+1, right);
 
  return;
}
 
//usage
int main()
{
  int a[10] = {1,9,10,8,2,7,3,6,4,5};
  QSort(a,0,9);
  return 0;
}

Finally, here is the program for sorting linked list using quicksort, it very simple and esay to understand, if you understand
quicksorting arrays well, then this algo can be easyly interpreted on same lines.

Sorting Linked List using QuickSort

/*the actual quciksort routine for sorting linked list*/
/*the actual quciksort routine*/
Node * quicksort(Node *list, int list_start, int list_end)
{
  Node *pivot, *left=list, *right=list, *tmp;
  int i = list_start, j= list_end-1;

  if (list_start >= list_end)
  {
    return list;
  }

  right = GetNthNode(list, list_end);
  left = GetNthNode(list, list_start);

  //select pivot
  pivot = SelectPivot(left, right);

  right = FindPrev(left, pivot);

  for(;;)
  {
    //now starts partitioning the list
    for(;left->info < pivot->info; left=left->next,i++);

    for(;right->info > pivot->info; right = FindPrev(list,right),j- -);
    if (i < j)
    {
      list = SwapNodes(list, left, right);
      //left, right ptrs got swapped, to continue
      //traversing we need them back at same positions
      tmp = left;
      left = right;
      right = tmp;
    }
    else
      break;
  }

  //restore pivot
  list = SwapNodes(list, left, pivot); 

  //now sort on smaller linked lists
  list = quicksort(list, list_start, i-1);
  list = quicksort(list, i+1, list_end);

  return list;
}

All auxiliary functions

//find previous node of curr node
Node *FindPrev(Node *list, Node *curr)
{
  for(;list && list->next; list=list->next)
  {
    if(curr == list->next)
    {
      break;
    }
  }
 
  if (list->next != curr)
  {
    //not find any element, probably what we are 
    //searching for is the beginning node
    return curr;
  }
 
  return list;
}

/*A complete swap algorithm which cares of 
several scenarios while swapping two nodes in 
a linked list which doesn't have any special nodes
scenarios considered while swapping
1)two nodes which are far away
2)two nodes which are far away, one is node is at 
  beginning of the list
3)two node which are neighbors
4)two nodes which are neibhors, 
  one node is at beginning of the list
*/
Node *SwapNodes(Node *list, Node *node1, Node *node2)
{
  Node *node1prev, *node2prev, *tmp;
 
  node1prev = FindPrev(list, node1);
  node2prev = FindPrev(list, node2);
 
  tmp = node2->next;
 
  //check whether node to swapped is in 
  //beggining (i.e. header node)
  if (node1 != list)
  {
    node1prev->next = node2;
  }
  else
  {
    //as we do not have special header node, 
    //if the first node and some 
    //other node, need to be swapped, 
    //then update the list (makes new min node as 
    //logical header)
    list = node2;
  }
 
  //are nodes to be swapped neibgoring nodes?
  if (node1->next == node2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    node2->next = node1;
    node1->next = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes, 
    //they are apart
    //so, consider all scenarios
    node2->next = node1->next;
 
    node1->next = tmp;
    node2prev->next = node1;
  }
 
  return list;
}

/*an auxiliary routine for getting the Nth 
element in the linked list*/
Node *GetNthNode(Node *list, int n)
{
  int i=1;
  for(i=1;i<n;i++)
  {
    list = list->next;
  }
  return list;
}
 
/*count number of nodes between two nodes 
(including the start, end mentioned)*/
int NumNodes(Node *list, Node *end)
{
  int i;
 
  for(i=1;list && (list!=end);i++)
  {
    list = list->next;
  }
 
  if (list != end)
  {
    return 0;
  }
  return i;
}

 
/*select a pivot, pivot can be selected in any way
randomly, first element, median of left, center, right
elemnts, etc.
Here we have chosen to pick center element as pivot*/
Node *SelectPivot(Node *list, Node *end)
{
  Node *right, *noden;
  int n;
 
  n=NumNodes(list, end);
 
  noden = GetNthNode(list, (float)n/2+0.5);
  //
  right = FindPrev(list, end);
 
  if (noden != right)
  {
    //swap the pivot and right most element in the list
    //later pivot will be restored.
    SwapNodes(list, noden, right->next);
    return noden;
  }
  else
  {
    return noden->next;
  }
}
 
int countnodes(Node *list)
{
  int i = 0;
 
  for (;list; list=list->next)
  {
    i++;
  }
 
  return i;
}

//a wrapper for quicksort
Node *QSort(Node *list)
{
  int n;
 
  n=countnodes(list);
 
  //call the quick sort routine
  //we always number elements in linked list as
  //1,2..n instead of 0, 1.. n-1
  return quicksort(list, 1, n);
}
 
int main()
{
  Node *list2;
  //list2
  list2 = insert(list2, 8);
  insert(list2, 0);
  insert(list2, 7);
  insert(list2, 2);
  insert(list2, 5);
  insert(list2, 3);
  insert(list2, 6);
  insert(list2, 9);
  insert(list2, 4);
  insert(list2, 1);
  printf("unsorted linked list:\n");
  printlist(list2);
 
  printf("sorted linked list:\n");
  list2 = QSort(list2);
  printlist(list2);
  return 0;
}

Download full source code here

If you are interested in more operations on linked list, visit this post

comments are always welcome…

Post any questions for more understanding over here…

Popularity: 97%