Tag Archives: C++

Headless link list implementation in C

Singly link list

A link list is a non-linear data structure with a head pointer. The rest of the nodes in the list could be accessed by using “next” of head.

The code to create a list of N node involves creating head separately. Rest of the nodes are appended to the head.

That looked ugly to me and so I wrote it in a generic manner. Using a temporary pointer, I wrote a single loop to create N link list nodes, keeping head intact.

Here is the code:

#define NULL (char*)0

typedef struct node_ {
        int n;
        struct node_ *next;
} node;

int main()
{
        int i = 5;
        node *head = NULL;
        node *temp = NULL;

        while (i-- > 0) {
                head = malloc(sizeof(node));
                head->n = i;
                head->next = temp;
                temp = head;
        }

        temp = head;
Advertisements

Pitfall of C array

CODE

int main()
{
int my_array[4] = {11,12,13,14};
int next = 15;
printf("\nSurprise = %d", my_array[4]);
}

What should it print?

Well, although illegal, the above code does legal things. The array “my_array” has four integers allocated on the stack. The next integer “next” is allocated adjacent to the stack memory. So the address of “next” would be (my_array + 5).


-----------------------
11| 12| 13| 14| 15|
-----------------------
^
|
The memory layout on stack is linear and hence our array and the integer are adjacent to each other.

It is a subtle error and you should know it.

Synchronize two threads to print ordered even and odd numbers in C

Problem:You have two threads, that independently print even and odd values. The goal is to synchronize these threads so as to get an non-decreasing ordered set of numbers and order should preserve natural ordering of numbers. So the output should be 1,2,3,4,5,6,7,8…..

It is an interesting problem and could be solved with a conditional variable.

Following is C implementation of the solution:

#include "stdio.h"
#include "stdlib.h"
#include "pthread.h"

pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition_var = PTHREAD_COND_INITIALIZER;
void *functionCount1();
void *functionCount2();
int count = 0;
#define COUNT_DONE 200

void main()
{
 pthread_t thread1, thread2;
 pthread_create( &thread1, NULL, &functionCount1, NULL);
 pthread_create( &thread2, NULL, &functionCount2, NULL);
 pthread_join( thread1, NULL);
 pthread_join( thread2, NULL);
 exit(0);
}

// Print odd numbers
void *functionCount1()
{
  for(;;) {
   // Lock mutex and then wait for signal to relase mutex
   pthread_mutex_lock( &count_mutex );
   if ( count % 2 != 0 ) {
     pthread_cond_wait( &condition_var, &count_mutex );
   }
   count++;
   printf("Counter value functionCount1: %d\n",count);
   pthread_cond_signal( &condition_var );
   if ( count >= COUNT_DONE ) {
     pthread_mutex_unlock( &count_mutex );
     return(NULL);
   }
   pthread_mutex_unlock( &count_mutex );
 }
}

// print even numbers
void *functionCount2()
{
  for(;;) {
  // Lock mutex and then wait for signal to relase mutex
  pthread_mutex_lock( &count_mutex );
  if ( count % 2 == 0 ) {
    pthread_cond_wait( &condition_var, &count_mutex );
  }
  count++;
  printf("Counter value functionCount2: %d\n",count);
  pthread_cond_signal( &condition_var );
  if( count >= COUNT_DONE ) {
    pthread_mutex_unlock( &count_mutex );
    return(NULL);
  }
  pthread_mutex_unlock( &count_mutex );
 }
}

Python goof ups of a C/C++ programmer

Python is a new age language when compared to good old C. Writing code in Python needs a subtle shift from C mindset. Python offers so many things ready-made that make you feel that you wrote very less code. Anyway, I goofed up while using a very common feature of C: pass by reference.

Python too offers it, but with a caveat: you should know mutable and immutable data objects. When you pass a mutable object like list, dictionary; they can be changed. But, if you pass an immutable data object like string, tuple; they are kept unchanged in caller’s scope. This is very similar to passing “references” (C++) or constant pointers.

  1 class Node:
  2     def __init__(self, value, data=[]):
  3         self.char = value
  4         # We intend to keep a list of values for a key
  5         self.data = data
  6         # XXX: List of Node
  7         self.children = []
  8
  9
 10 n = Node('a')
 11 m = Node('b')
 12
 13 (n.data).append("north")
 14 (m.data).append("south")
 15
 16 print n.data
 17 print m.data

The output of the above code is:

ubuntu@ubuntu:~/Desktop/ToKeep/cprogs/pycon$ python pybug.py
['north', 'south']
['north', 'south']

I don’t quite understand why Python keeps a single instance of default argument(list). Nonetheless, it is interesting.

This thread on Stackoverflow is very informational.

  • Omitting “this” pointer

In C++, “this” which is pointer to the object is passed implicitly. Python has similar keyword “self” for this. But, contrary to an implicit understanding, “self” should be an argument to a function, else you would see an error:

NameError: global name ‘self’ is not defined

  1 class pydbg:
  2     def __init__(self, modname=None):
  3         self.level = 0
  4         self.modname = modname
  5
  6     def DLOG(self, lvl=None, fmt=None, *args):
  7         self.level = lvl
  8         print '%s' %self.modname
  9         print fmt
 10         for arg in args:
 11             print arg

So, always add the “self” argument while adding a function in your class.

Potential pitfall of ‘new’ operator in C++: Missing ‘NULL’

I faced a very interesting problem in a C++ code. The code logic was as follows:

#include<stdio.h>

int main()
{

int *p = new int();
int* B[10];

for ( int i =0; i<10; i++)
{
delete p;
//p = NULL;
printf(“Address1 =  %x\n”, p);

int *q = new int();
printf(“Address2 =  %x\n”, q);

B[i] = q;

i++;
}

}

Output:

kanaujia@ubuntu:~/Desktop/ToKeep/cprogs$ ./a.out
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008
Address1 =  96f8008
Address2 =  96f8008

This code looks pretty simple and with no bug, right? But, it has an interesting problem. The first memory allocation of integer will give us an address from the heap (say, it is 0x12345).

Now inside the loop, with first iteration, we free this memory. ‘new’ will mark this address 0x12345 in free-list. Next , we again ask an integer memory allocation. And ‘new’ returned me same address 0x12345 for this allocation. I save this address in array B. Next and henceforth forth iterations will call ‘delete’ on 0x12345, and again ask an allocation. This request again returns 0x12345. So, we end up with single value of 0x12345 for *all* elements of arrayB.

How to fix this:

Always mark the pointer to NULL after calling ‘delete’. Just mark p as NULL here.

9         for ( int i =0; i<10; i++)
10         {
11                 delete p;
12                 p = NULL;
13                 printf(“Address1 =  %x\n”, p);
14
15                 int *q = new int();
16                 printf(“Address2 =  %x\n”, q);
17
18                 B[i] = q;
19
20                 i++;
21         }

Output:

kanaujia@ubuntu:~/Desktop/ToKeep/cprogs$ ./a.out
Address1 =  0
Address2 =  9265008
Address1 =  0
Address2 =  9265018
Address1 =  0
Address2 =  9265028
Address1 =  0
Address2 =  9265038
Address1 =  0
Address2 =  9265048

That’s it folks! Hope you enjoyed it.

Unfolding 2-D array in C

Last weekend my friends and I had a discussion on 2-D array in C. Surprisingly it went long as everyone had some points and knowledge to share 🙂 Finally we could gather some important information and understood this pearl of C better.

I’ll clear this idea with C code snippets.

// Declare an array
int arr[2][3]= {1,2,3,4,5,6};

It’s size is 2*3*sizeof(int) = 24 bytes (Intel x86)

okay, now what will get printed for following statements:
// Say starting address is 1024

o) print &a + 1
o) print a + 1
o) print *a + 1

To answer these questions better, I’ll explain what exactly is a 2-D array. When we declare and define a 2-D array, it’s like a new user defined type to C. It’s a pointer to a memory location that contiguously contains storage of 6 integers. Logically it’s like holding many 1-D array in a followed by one-another.

Ans 1: When you say ‘&a’ , it implies address of user defined type and it’s 1024. Now incrementing it by 1 means moving the pointer by the size of this type which is 24 bytes. Thus it’ll print 1048.

Ans 2: ‘a’ fetch us address of 1-D array or 0th row of our matrix. a+1 would get us address of next row i.e. 1024 + (3*4) = 1036

Ans 3: ‘*a’ would get you the 0th element of 0th row which is 1. So *a + 1 would get us 2.