My Notes - C, C++, Java...

Reverse a stack in place

2012-02-10T00:26:00.007+05:30

Write a C/C++ Program to reverse a stack in place? You can only use the following ADT functions on the stack: 1. empty() 2. push() 3. pop() 4. top() Solution: 1. Whenever in place conversion is required, use recursion which will make use of function stack to store the variables 2. Pop out all the elements from the given stack recursively and store them in a variable. 3. As the stack unwinding

Traversing a Binary Tree

2011-12-06T21:45:00.004+05:30

There are basically two ways of traversing a binary tree 1. Depth First Traversals 2. Breadth First Traversal Depth First Traversal A binary tree can be traversed in three ways using the depth first approach namely 1. Inorder Traversal template <typename T> void BTTraveller<T>::inOrder(BSTNode<T> *node, std::deque<T> &out) { if(node) { inOrder(node->left, out);

A Binary Search Tree Example

2011-12-05T00:19:00.004+05:30

A Binary Tree is a tree where each node may have 0, 1 or 2 children and a Binary Search Tree is a binary tree with a special property that the value of node under discussion is less than all the nodes in its right subtree and greater than all the nodes in its left subtree. The programs below describes the three basic operations in a binary search tree viz. search, insert and remove 1. Searching

Static Library - An Introduction

2011-05-04T08:40:00.011+05:30

Static library is a group of object files bundled together in an archive by the archiver program. The static libraries have a .a extension. Advantages 1. The executable is not dependent on any library as the library code is included in the binary 2. In some cases performance improvementCommand for creating a static library ar rcs -o libmylibrary.a file1.o file2.o file3.o Steps for generating the

Shared Library - An Introduction

2011-05-03T09:33:00.006+05:30

A shared library is a library required by an executable to run properly. Such executables are called incomplete executables as they call routines present in the shared library code. The executables generated from the shared library are smaller in size than the ones generated from a static library When an executable built with shared library is run, the dynamic loader identifies the list of

POSIX Threads - A simple Example

2011-03-20T21:21:00.002+05:30

In our earlier post, we have written multithreaded program using win32 apis. This post deals with writing the multithreaded programs using POSIX thread apis. The important POSIX thread apis are namely pthread_create, pthread_exit and pthread_join Create a threadint pthread_create ( pthread_t *thread, const pthread_attr_t *attr, void *( *start_routine)(void *), void *arg );

Command prompt and setting environment variable properties

2011-03-20T01:13:00.001+05:30

Working on multiple projects which require different compiler versions can be a daunting task especially if you are using windows command prompt cmd.exe to build the projects. You need to export the compiler specific environment variables and set the PATH variable appropriately each time you launch the command window to build each project. Here is a small tip that can help save some time Tip

Customize Cygwin/Linux command prompt

2011-03-15T14:26:00.011+05:30

From the bash manual, the following environment variables control the display of prompt in a Cygwin or Linux terminal namely PS1, PS2, PS3, PS4. Note: For referring the bash manual type info bash Key Points 1. PS1 : The value of this parameter is expanded and used as the primary prompt string. It's default value is '\s-\v\$ ' 2. PS2 : The value of this parameter is expanded as with PS1 and used

Anatomy of a process stack

2011-03-14T21:57:00.007+05:30

A process is a program in execution. A process may have one or more threads executing different sections of the program. Every thread in the process maintains it's own separate stack, registers and program counter. Key Points A stack is a collection of stack frames where each stack frame refers to a function call Stack Frame When a function call is made, a block of memory is set aside which

A simple Makefile example

2011-03-06T15:58:00.003+05:30

Continuing our series on makefile tutorial, below is a simple makefile which compiles the Hello World program Main.cpp into an object file Main.o and generates the binary executable Main.exe #----------------------------------------------------------------------- # A Simple Makefile example #----------------------------------------------------------------------- PROJECT := Main

Makefile tutorial for beginners

2011-03-04T14:51:00.016+05:30

The purpose of the make utility is to determine automatically which pieces of your large program needs to be re-compiled, and issue the commands to recompile them. The make program uses the makefile instructions and the last modified time of the files to decide which of the files needs to be updated. A makefile tells make what to do. The make utility executes commands in the makefile to update

Producer and Consumer Problem revisited with Events

2011-03-02T15:46:00.007+05:30

The producer and consumer problem we visited earlier used CRITICAL_SECTION for synchronization and the threads were spinning and checking over the queue size to add or remove the elements. In this post, we are going to use Windows Event objects for synchronizing the Producer and Consumer threads. Key Points 1. Events are kernel objects which contain an usage count, flag indicating the type of

Sort elements in a Collection using Comparator Interface

2011-02-26T00:02:00.009+05:30

Continuing our series of sorting elements in a Collection, this post makes use of the Comparator interface to sort the objects. Key Idea The sort(List list, Comparator c)method sorts the specified (modifiable) list in the order specified by the comparator The Employee Java Bean below makes use of the EmployeeNameComparator class to sort the Employee elements in the list. Also, note the use of

Sort elements in a collection using Comparable Interface

2011-02-25T21:39:00.011+05:30

The Collections class in java provides the following methods for sorting the specified (modifiable) list. This post deals with the first method from the list. void sort(List list) void sort(List list, Comparator c) Key Points The sort(List list)method sorts the elements in ascending order according to the natural ordering of it's elements. The ordering is defined by implementing Comparable

Orphan Users in SQL Server 2005

2011-02-24T15:41:00.013+05:30

All Sql Server logins are stored in a system base table in master database. Whenever a new user is created, a corresponding entry is added in the system base table. There is a associated login entry for every user in system base table which also stores an associated SID (security identifier). Key Idea 1. An orphan user is one which does not have an associated login entry in the System Base

Mutex vs Semaphores

2011-02-16T22:41:00.004+05:30

Key Points 1. Only the thread which acquires the mutex can release the mutex successfully. 2. A binary semaphore (semaphore with a count of 1) is similar to mutex but allows other threads to release it. A thread which owns a mutex can acquire the same mutex recursively without blocking it's execution. This prevents the thread from deadlocking itself while waiting for the mutex it already owns.

Thread Synchronization using Windows Mutex

2011-02-16T00:35:00.010+05:30

In my earlier post Thread Synchronization in Windows using Critical Section, I have used Windows Critical Section as Locks for synchronizing the threads. This post talks about using Windows Mutex as synchronization objects and demonstrates it's use with a simple example. Windows functions related with Mutexes are CreateMutex, ReleaseMutex and OpenMutex HANDLE CreateMutex( LPSECURITY_ATTRIBUTES

Producer and Consumer Problem using Windows Threads

2011-02-14T01:18:00.006+05:30

Above is class diagram for a simple producer/consumer problem #include <iostream> #include "MQ.h" #include "Thread.h" #include "Runnable.h" #include "ProductionTask.h" #include "ConsumptionTask.h" //File: Main.cpp using namespace examples; int main() { try { MQ q(10); ProductionTask producerTask(q); ConsumptionTask consumerTask(q); Thread t[2] = {

Encapsulating Windows Threads in C++ Objects

2011-02-11T22:02:00.010+05:30

Threads in Windows can be created using the following three routines HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpsa, DWORD cbStack, LPTHREAD_START_ROUTINE lpStartAddr, LPVOID lpvThreadParam, DWORD fdwCreate, LPDWORD lpIDThread );uintptr_t _beginthread( void( *start_address )( void * ), unsigned stack_size, void *arglist );uintptr_t _beginthreadex( void *security, unsigned stack_size, unsigned

Coding simplified with Guard Classes

2011-02-10T01:00:00.008+05:30

With the introduction of exceptions, writing code has become increasingly complex. Any resource acquired has to be released when no longer in use. If not handled properly will lead to handle leaks, memory leaks and in some cases deadlocks which are very difficult to debug. Guard classes takes advantage of the fact that the destructor is always called for an object on the stack regardless of how

Debug the Code : Thread synchronization

2011-02-09T23:11:00.010+05:30

The program is supposed to print multiples of 10 in a new line in increasing order. Although, the program appears to be correct, it is not. It is giving me duplicate values in the output. Locate the problem? #include <windows.h> #include <process.h> #include <iostream> #include <assert.h> #include "Lock.h" using namespace examples; static bool alive = true; static int current = 0; unsigned __

Thread Synchronization in Windows using Critical Section

2011-02-09T00:45:00.008+05:30

In multi threaded environments, where more than one thread operates on the shared data (global variables, collections) the results can be unpredictable due to race conditions. Critical Section is a mechanism that ensures that only one thread executes a particular piece of the code. A thread, once it enters a critical section should not be interrupted. Critical Sections have the advantage of not

Multithreading in Windows - A simple example

2011-02-02T23:50:00.008+05:30

A thread is an independent unit of execution within a process. Threads under windows can be created/terminated using the following Win API functions: 1. CreateThread()/ExitThread() system calls. 2. _beginthread()/_endthread() OR _beginthreadex()/_endthreadex() CRT functions. Key Points 1. Using CreateThread() in a program that uses the CRT functions (for example, links with LIBCMT.LIB) may

Overloading operator()

2011-01-31T02:27:00.014+05:30

Browsing through some of the open source code implementation in C++, came across the function void operator()() Q. Why would one use operator() in the first place? A. Simplicity of usage. Of course, less intuitive if you are seeing it's use for the very first time. The program below implements a matrix and uses operator() as a replacement of subscript operator[] to retrieve and set values at

C Program - struct usage example

2011-01-23T21:52:00.007+05:30

This is a follow up post on my last blog update Pointers in C - an eye opener. The program touches on the following - 1. Using struct as Employee record 2. Using pointer to Employee* as an employee list 3. Using void pointer and casting it to an appropriate type to avoid duplicate code 4. Allocating memory and freeing memory struct Person { char *name; size_t age; }; typedef struct