Everything about virtual functions

• A class that declares or inherits a virtual function is called a polymorphic class
• A virtual funtion ensures dynamic binding.
• If a function is declared virtual, then if we have a function with the same name and parameters in a derrived class, then that function is automatically virtual, even if we do not declare it as virtual in the derrived class.

   struct A
   {
      virtual void f()
      {
         cout << "A::f()";      
      }    
  }     
  struct B : A    
  {        
      void f( int )      
      {         
         cout << "B::f()";     // Hides A:f()
      }    
  }     
  struct C: B    
  {        
      void f()      
      {          
          cout <<"C::f()";     // This is always virtual
      }    
  }   
  

  In the above example, B::F(int) hides A:f(). A b; b.f is illegal.

  Also, C::F() is implicitly virtual.

• If a funcion has the same name as the base class function and different parameters, then it hides all functions with the same name in the base class. In the Example 1 above, B::f hides A:f
• The return type of a virtual function may be different from the overridden one. This is called covarent virtual function. The return types may differ provided all the following conditions are met:

  1. If A::func returns a pointer or reference of type T, then B:func can return only a direct or un-ambigous derrived class from T

  2. The const or volatile qualifier of type returned by B is at lease as restrictive as A

  3. The return type of B::func must be complete and accessible at the point or it may be a B.

• We can call a base classes virtual function by base::func().
• A virtual function can be == 0, or pure virtual. Instances of abstract classes can not be created and an abstract class can not be used as parameters to templates.
• A derrived class can be abstract, even if it is derrived from a non-abstract class.
• We can pass a pointer or reference to an abstract class as a parameter in a function. In that function, we can even call a pure virtual method. However, we can not have an instance of an abstract class as a parameter.
• We can override a virtual function with an abstract function in a derrived class.

Everything about constructors

1. Everything you wanted to know about constructors
   • Constructors are used to initialize objects.
   • When a class derives from other classes, the constructors are called in the following order.
     • Virtual base classes, left to right in the class decleration
     • base classes, left to right in the class decleration
     • Member classes and references
     • Finally, the body of the constructor is executed.
   • A copy constructor is a constructor which takes a const reference of type self and is used to construct a copy of the instance. A copy constructor is used extensively by STL containers and algorithms.
   • A constructor must not leak memory, even if any of the constructors of base or member classes throws an exception.
   • A default constructor is a constructor which takes no arguments, or a constructor which has default values for all arguments. If we dont define any constructor in our class, then the compiler automatically creates a default constructor for our class
   • If we make the constructor of a class private, then an instance of the class can not be created directly. We often use this to create a singleton pattern.
   • If you have a reference member, then the only way for you to initialize the reference is in the constructor. If your class has pointers, then you should always initialize the pointer to NULL in the constructor.

Virtual Functions in C++

Using Expat to parse XML

Socket programming

Sockets are endpoints in communication. We create a socket on the server application and sit and listen for incomming connections. Clients initiate a connection and send data once the connection is established.

There are two types of sockets; connected and datagram sockets. Connected sockets keep the connection between the client-server. With datagram sockets, there is no gurantee of delivery of packet and we have to use packet counting mechanism if we want to gurantee delivery of data. However, datagram sockets are less resource intensive and can be used with applications like media streaming applications.

Let us look at connection oriented sockets.

For the server side, the basic steps are:

• Create a socket (int aSocket = ::socket(...) )
• Bind the socket to an address and port
• Call accept in a loop to listen to connection requests. This call blocks until there is a connection request. On return, the OS returns a socket which we use to communicate with the client application (see example)

On the client side, we create a socket simply call connect and we are off.

Data structures used:

1. sockaddr and sockaddr_in are used to specify the host and port we want to connect to. Both these structures are of the same size. All networking calls where we need to specify an address take a pointer to a sockaddr structure as a parameter. With TCP/IP sockets, we fill in a sockaddr_in structure and typecast it to a sockaddr structure in calls to networking functions.

typedef uint32_t in_addr_t;

struct in_addr
{
  in_addr_t s_addr;
};

struct sockaddr_in
{
  sa_family_t sin_family;
  in_port_t sin_port;
  struct in_addr sin_addr;

  unsigned char __pad[16 - sizeof(short int)
   - sizeof(unsigned short int) - sizeof(struct in_addr)];
};

The following functions can be used to convert dotted (127.0.0.1) to binary and vice-versa:

    #include 
    in_addr_t inet_addr(const char *cp);
    char *inet_ntoa(struct in_addr in);

--more stuff to follow ---

Using the select command

Typically, on the server side, we would have several sockets which we would read and write data to. We use the select function to determine which sockets we can read and/or write to without the call blocking.

The select call takes the following parameters:

   int select(int maxFD, fd_set *read, 
              fd_set *write, 
              fd_set *exceptions, 
              struct timeval *tv);

where:

• The first parameter, i.e. maxFD in the above call is the highest number +1 of descriptor in read, write and except set we are interested in. For example, if we currently have sockets 4,7 and 9 open and we wish to read from any one of these, we would pass 10 as the first argument to select call.
• read, write and ex in the call above are pointers to three fd_set structures which specify the sockets we are interested in. This structure is described below. Any or all of these parameters can be null. For example, if we are only interested in determining which sockets have data to read, we would pass NULL for the write and exceptions sets. We use the FD_SET, FD_CLR calls to set, clear individual sockets and FD_ZERO to zero out the entire set. FD_ISSET is used to determine which sockets are ready (see example below).
• The timeval struct gives the number of seconds to wait before returning. This argument can be used to specify an indefinite wait, or a definite wait time, as described below.
• The return value is the total number of descriptors that are ready, with -1 representing an error condition, 0 means that the call timed out before any of the descriptors became ready, etc.

The fd_set structure is simply a bit map with each bit representing an integer value. For example, if we use the FD_SET macro like FD_SET( 4,&readFD), bit 4 in the readFD will be set.

The struct timeval is as follows:

    struct timeval
    {
        long tv_sec;
        long tv_usec;
     };

where tv_sec and tv_usec specify the seconds and microseconds to wait.

• If the tv parameter is null, then the kernal will wait forever until a socket does become ready.
• If both tv_sec and tv_usec are zero, then the call will return immediately.
• If either of these parameters is non-zero, then the call will wait for the specified interval. We can then use the return value from this call to check if any of the sockets are ready. The POSIX specs allow the call to modify this struct, so remember to reset the values before each call.

If a bit is set on the exception set, that indicates the arrival of out-of-band data.

Note that setting a socket in the non-blocking mode will not affect the way select works. So, even if all the sockets in the read set are non-blocking, the select call will wait as specified by the tv parameter.

Producer-Consumer using Windows threading

Here is a simple solution to the producer-consumer problem using Windows threading. Basic classes are

• Producer This is the thread that produces jobs at random intervals
• Consumer This is the thread that pulls jobs off the messageQueue and processes the job. There are multiple consumers.
• MessageQueue Fixed size queue to hold the jobs
• Job Abstract job class that the Consumer consumes
• Thread Utility class to manage trreads

Barber Problem Solution in C++

The barber shop simulation is a good problem to practice multi-threading concepts. Here is the problem, which we need to simulate. Barber shop consists of a waiting room with 'n' chairs, and a barber room with one barber chair

1. If there are no customers to be served the barber goes to sleep.
2. If a customer enters the barber shop and all the chairs are occupied then customer leaves shop.
3. If barber is busy but chairs are available then customer sits in one of the free chairs.
4. If barber is asleep the customer wakes up barber.

Here is one solution to the barber problem using Windows threading primitives. Essential classes that we need:

• Barber This class runs in a different thread. It calls BarberShop.GetNextCustomer to get an available customer.
• Customer
• BarberShop This is where all the business logic resides. The two main routines are GetNextCustomer, which picks up the next available customer from the queue or blocks on m_BarberSleepEvt if no customers. The NeedsHaircut routine adds a customer to the end of the queue of waiting customers if the queue has empty spaces. If not, it simply ignores the request. If the queue was empty before adding, then it means that the barber thread was waiting on the event and it releases the event after adding the customer.
• Thread This is a utility class that can be used to start/stop threads. Simply derive your class from this class after overriding the virtual run method and then call the Start routine.

The entire solution is in 2 files. I compiled the code using Borland's command line C++ compiler (free).

---

File: BarberShopSimulation.h

#ifndef _BARBER_SHOP_SIMULATION_H
#define _BARBER_SHOP_SIMULATION_H


#define NUM_WAITING_CHAIRS  5


class Barber;
class Customer;
class BarberShop;

class Thread
{
    HANDLE m_ThreadHandle;
    bool m_Terminate;
    DWORD m_ThreadID;

    static DWORD _ThreadProc(void *);
public:
    Thread();
    virtual ~Thread();
    void Start();
    void Stop() {m_Terminate = true;}
    bool KeepRunning() {return !m_Terminate;}
    DWORD GetThreadID() const {return m_ThreadID;}
    virtual DWORD run() = 0;
};


class Barber : public Thread
{
    BarberShop & m_Shop;

public:
    Barber( BarberShop & inShop);
    ~Barber();
    DWORD run();
};


// Dummy class
class Customer
{
    int m_ID;
public:
    Customer(int inID) : m_ID(inID)
    {
    }
    int GetID() const  {return m_ID;}

    Customer(const Customer & inCust): m_ID( inCust.m_ID )
    {
    }
};


std::ostream & operator << (std::ostream & os, const Customer & inCust)
{
    os << inCust.GetID() ;
    return os;
}


class BarberShop
{

    std::auto_ptr m_Barber;
    HANDLE m_BarberSleepEvt;
    HANDLE m_Mutex;
    int m_Head, m_Tail;
    std::auto_ptr  m_WaitingCustomers[ NUM_WAITING_CHAIRS];

    inline incr(int& inValue)
    {
        ++inValue;
        if(inValue >= NUM_WAITING_CHAIRS )
            inValue = 0;
    }
public:
    BarberShop();
    ~BarberShop() {}

    void GetNextCusomer( std::auto_ptr & outCust);
    void NeedsHaircut( std::auto_ptr& inCust);
};



#endif // _BARBER_SHOP_SIMULATION_H

---

BarberShopSimulation.cpp

#include <iostream>
#include <windows.h>
#include "BarberShopSimulation.h"

// For random sleep
#include <stdio.h>javascript:void(0)
#include <stdlib.h>
#include <time.h>

// =================================================
//      Thread
// =================================================
Thread::Thread()
: m_ThreadHandle(NULL), m_Terminate(false)
{
}

Thread::~Thread()
{
    if( m_ThreadHandle != NULL )
    {
        ::TerminateThread( m_ThreadHandle, 0 );
        m_ThreadHandle = NULL;
    }
}

DWORD Thread::_ThreadProc(void *ap)
{
    Thread *r = (Thread *)ap;
    return r->run();
}

void Thread::Start()
{
    m_ThreadHandle = ::CreateThread(
                     NULL,       // default security attributes
                     0,          // default stack size
                     (LPTHREAD_START_ROUTINE) _ThreadProc,
                     this,       // no thread function arguments
                     0,          // default creation flags
                     &m_ThreadID); // receive thread identifier
    if( m_ThreadHandle == NULL )
        std::cout << "Could not create a thread!\n";
}

// =================================================
//      Barber
// =================================================
Barber:: Barber( BarberShop & inShop)
: m_Shop(inShop)
{
}
Barber::~Barber()
{
}

DWORD Barber::run()
{
    std::cout << "Barber::run...";
    while(1)
    {

        std::auto_ptr aCust;
        m_Shop.GetNextCusomer( aCust );
        if( !aCust.get() )
        {
            std::cout << "Barber Error: Customer is null ?? terminating...";
            return 1;
        }
        std::cout << "Barber is now cutting hair for customer " << *aCust << "...\n";
        ::Sleep( 600 );
        std::cout << " finished\n";
    }
}


// =================================================
//      BarberShop
// =================================================

BarberShop::BarberShop()
:m_BarberSleepEvt(NULL),
    m_Mutex(NULL),
    m_Head(0),
    m_Tail(0)
{
    m_BarberSleepEvt = ::CreateEvent( NULL, FALSE, FALSE, NULL);
    m_Mutex = ::CreateMutex( NULL, FALSE, NULL );
    std::auto_ptr aBarb( new Barber(*this) );
    m_Barber = aBarb;
    m_Barber->Start();
}


void BarberShop::GetNextCusomer( std::auto_ptr & outCust)
{
    DWORD aResult;

    do
    {
        aResult = ::WaitForSingleObject( m_Mutex, INFINITE );
        if( aResult != WAIT_OBJECT_0 )
        {
            std::cout << "BarberShop::GetNextCusomer. Error while waiting for mutex!\n";
            return;
        }
        // If the queue is empty, go to sleep. When a customer arrives, we will be woken up
        if( m_Head == m_Tail)
        {
            ::ReleaseMutex( m_Mutex );
            aResult = ::WaitForSingleObject( m_BarberSleepEvt, INFINITE );
            if( aResult != WAIT_OBJECT_0 )
            {
                std::cout << "BarberShop::GetNextCusomer. Error while waiting for event!\n";
                return;
            }
        }
        else
        {
            // There are some waiting customers. Get the one from the head
            outCust = m_WaitingCustomers[m_Head];
            incr( m_Head );
            ::ReleaseMutex( m_Mutex );
            return;
        }
    }
    while(1);
}


void BarberShop::NeedsHaircut( std::auto_ptr & inCust)
{
    DWORD aResult;
    int aNextPos;
    bool aQueueWasEmpty;

    // Get the mutex...
    aResult = ::WaitForSingleObject( m_Mutex, INFINITE );
    if( aResult != WAIT_OBJECT_0 )
    {
        std::cout << "BarberShop::GetNextCusomer. Error while waiting for mutex!\n";
        return;
    }

    // Check if the queue was empty. If the queue was empty, then we need to signal the
    // sleeping barber that there is a waiting customer
    aQueueWasEmpty = m_Tail == m_Head;
    aNextPos = m_Tail;
    incr(aNextPos );
    if( aNextPos == m_Head )
    {
        std::cout << "BarberShop::NeedsHaircut. Cant accept customer " << *inCust << " as Queue is full..\n";
        ::ReleaseMutex( m_Mutex );
        return;
    }
    // queue is not full. Add the customer to the tail
    m_WaitingCustomers[ m_Tail ] = inCust;
    m_Tail = aNextPos;
    ::ReleaseMutex( m_Mutex );
    if( aQueueWasEmpty )
    {
        ::SetEvent(m_BarberSleepEvt);
    }
    return;
}



// ====================================================
//    Application
// ====================================================
int main(int, char **)
{
    std::cout << "Hello, everyone. I am now running barber shop simulation\n";

    BarberShop aShop;
    for(int i=0; i < 1000; i++)
    {
        std::auto_ptr aCust( new Customer(i));
        std::cout << "adding customer # " << i << " to shop\n";
        aShop.NeedsHaircut( aCust );
        ::srand(time(NULL));
        int aCount = ::rand()%100 + 10;
        ::Sleep( 700 ); //aCount );
    }
    ::Sleep(10000);
}