I will get more and more pleasure if you ask me more and more Intelligent quetion
Saturday, July 19, 2008
FAQ for Academic students: Any Computer Science subjects
Thursday, July 3, 2008
Wednesday, July 2, 2008
Restriction on creation of object into heap, stack, static memory
This is just for a kind of information.
Here I am going to explain how to make a class so that user can create object of it on free List( heap memory) or Stack.
{
HeapOnly
HeapOnly * ptr = new HeapOnly; // Object created on heap
ptr->DestroyMe() // Object deallocated
}
Example 2: Object should be created Only On stack memory or static memory. Idea is that just overload the new and delete operator and make it private member and dummy implemetation.
Here I am going to explain how to make a class so that user can create object of it on free List( heap memory) or Stack.
Example 1: Object should be created Only On Heap memory.Idea is that make constructor as private so that no one create on stack. But one drawback is that constructor can be overloaded so better make destructor as private member of class because Destructor can'nt be overloaded. It's very safeto make destructor as private member of class for this purpose.
Code: cpp
class HeapOnly
{
public:
void DestroyMe() //This function will call destructor
{
delete this; // Current object will be deleted means destructor
}
private:
~HeapOnly(); // destructor only can be call by member function
};
Now you can test above class.class HeapOnly
{
public:
void DestroyMe() //This function will call destructor
{
delete this; // Current object will be deleted means destructor
}
private:
~HeapOnly(); // destructor only can be call by member function
};
Client Code:
int main(){
HeapOnly
HeapOnly * ptr = new HeapOnly; // Object created on heap
ptr->DestroyMe() // Object deallocated
}
Code: Cpp
class autoOnly
{
public:
autoOnly()
{
;
}
~autoOnly()
{
;
}
private:
void* operator new(size_t)
{
// Dummy Implementation
}
void* operator new[](size_t)
{
// Dummy Implementation
}
void operator delete(void*)
{
// Dummy Implementation
}
void operator delete[](void*)
{
//Dummy Implementation
}
};
Now you can test it .
class autoOnly
{
public:
autoOnly()
{
;
}
~autoOnly()
{
;
}
private:
void* operator new(size_t)
{
// Dummy Implementation
}
void* operator new[](size_t)
{
// Dummy Implementation
}
void operator delete(void*)
{
// Dummy Implementation
}
void operator delete[](void*)
{
//Dummy Implementation
}
};
Now you can test it .
Client Code:
int main()
{
autoOnly *ptr= new autoOnly; // Error " cannt Access private member
autoOnly obj; // Created on stack
static autoOnly obj1; //Created on static memory
return 0;
}
int main()
{
autoOnly *ptr= new autoOnly; // Error " cannt Access private member
autoOnly obj; // Created on stack
static autoOnly obj1; //Created on static memory
return 0;
}
One Tips :: For Coding Guidelines
One problem is solved by two methods. Can you tell me which is better and why?
Method 1:
void client1()
{
fun();
}
void clenit2()
{
fun();
}
...............
...............
...............
...............
void clientN()
{
fun();
}
void fun()
{
if(con1)
return;
if(con2)
return;
if(con3)
return;
//Rest Code is functionalitywise of fun as
....
....
}
Method 2:
void client1()
{
if(!con1 || !con2 || !con3)
fun();
}
void clenit2()
{
if(!con1 || !con2 || !con3)
fun();
}
...............
...............
...............
...............
void clientN()
{
if(!con1 || !con2 || !con3)
fun();
}
void fun()
{
//functionality of fun as
}
My Point Of View:
Case1: No question if either con1or con2 or con3 will be false , Offcourse Method 1 will be the best. Atleast No duplicasy of code.No Overhead..Fine
Case2: In case Of Either con1 or con2 or con3 =true then
In case of method1 , Every clients will make a stack frame while calling fun() ...Costly ...overhead!!! But No duplicasy of code..Seing code nicely
In case of method2, Every clients will not call fun()....Not Costly..No Overhead!!! But duplicasy of code...Bad looking code
Results:
Now both has advantages and disadvantages, then what you will do? Now we have to check our fun()'s Objective. suppose clients calls fun() 20% of his some life. Then i will suggest to use Method1. Else totally depends on objective of fun().
Give your views. I am waiting for your comments.
Tuesday, July 1, 2008
Memory Leak detection Program
I worked for a long time for this article. This program is tested on Sun-Solaris system using gcc compiler.
In market, there are a lot of tools for detecting the memory leaks. Here I made a program which has to include in your source file and it will tell the desired informations to find where memory leaks happen.
There are two files one is findLeak.c and other is findLeak.h . Source file is test.c , this is your program which you want to check memory leaks.
Concept is that when user call library function "malloc or calloc " for allocating dynamic memory, then we have to call our malloc or calloc (In case of my source code 'MyCalloc' function in place of 'calloc' and MyMalloc function in place of 'malloc'). So we have to define malloc to your malloc and in .c file you have to undef malloc and calloc By this way we can call our MyMalloc or MyCalloc function and in this function we will call another function which keeps all info about how much memory allocated. We will do the same for Library function "free" to deallocating memory( In my source file "MyFree" is used in plae of free function).
Now for keeping information, i made a simple singly linked list. which will add info about memory when user call "malloc" or "calloc" function and will also keep information when user call "free" function.
By program you can easily understand.
Heder File : findLeak.h
Code: c
#define uint unsigned int
#define cchar const char
#define OutFile "/home/asadulla/test/MemLeakInfo.txt" // Just Suppose
#define MAX_FILENAME_LENGTH 256
#define calloc(objs, nSize) MyCalloc (objs, nSize, __FILE__, __LINE__)
#define malloc(nSize) MyMalloc (nSize, __FILE__, __LINE__)
#define free(rMem) MyFree(rMem)
// This structure is keeping info about memory leak
struct InfoMem
{
//starting address of memory where pointer points
void *addr;
//Total size of memory in bytes which By malloc
//allocates memory dynamically */
uint nSize;
//Source File Name which you want
//to find memory leak information
char fileName[MAX_FILENAME_LENGTH];
//Line number of source File due to
// which User forget to deallocate memory
uint lineNumber;
};
typedef struct InfoMem infoMem;
//This is link list of InfoMem which keeps a List of memory Leak in a source file
struct LeakMem
{
infoMem memData;
struct LeakMem *nxt; // Next Memory leak Block
};
typedef struct LeakMem leakMem;
// This function is used for writing into file to see the memory leaks summary
void WriteMemLeak(void);
// These two function add information of memory leak information when user
// calls malloc or calloc
void SubAddMemInfo(void *rMem, uint nSize, cchar *file, uint lno);
void SubAdd(infoMem alloc_info);
// These two function remove and deallocated memory and remove the leak
// information when user calls free function
void ResetInfo(uint pos); //erase
void DeleteAll(void); //clear(void);
// This is hidden to user , This function will call when user call malloc function
void *MyMalloc(uint size, cchar *file, uint line);
// This is hidden to user , This function will call when user call calloc function
void *MyCalloc(uint elements, uint size, cchar * file, uint lno);
// This is hidden to user , This function will call when user call free function
void MyFree(void * mem_ref);
Source File: findLeak.c
Code: c
#include
#include
#include
#include "findLeak.h"
#undef malloc
#undef calloc
#undef free
static leakMem * ptr_start = NULL;
static leakMem * ptr_next = NULL;
// -----------------------------------------------------------
// Name: MyMalloc
// Desc: This is hidden to user. when user call malloc function then
// this function will be called.
void *MyMalloc (uint nSize, cchar* file, uint lineNumber)
{
void * ptr = malloc (nSize);
if (ptr != NULL)
{
SubAddMemInfo(ptr, nSize, file, lineNumber);
}
return ptr;
}
// -----------------------------------------------------------
// Name: MyCalloc
// Desc: This is hidden to user. when user call calloc function then
// this function will be called.
void * MyCalloc (uint elements, uint nSize, const char * file, uint lineNumber)
{
uint tSize;
void * ptr = calloc(elements , nSize);
if(ptr != NULL)
{
tSize = elements * nSize;
SubAddMemInfo (ptr, tSize, file, lineNumber);
}
return ptr;
}
// -----------------------------------------------------------
// Name: SubAdd
// Desc: It's actually Adding the Info.
void SubAdd(infoMem alloc_info)
{
leakMem * mem_leak_info = NULL;
mem_leak_info = (leakMem *) malloc (sizeof(leakMem));
mem_leak_info->memData.addr = alloc_info.addr;
mem_leak_info->memData.nSize = alloc_info.nSize;
strcpy(mem_leak_info->memData.fileName, alloc_info.fileName);
mem_leak_info->memData.lineNumber = alloc_info.lineNumber;
mem_leak_info->nxt = NULL;
if (ptr_start == NULL)
{
ptr_start = mem_leak_info;
ptr_next = ptr_start;
}
else {
ptr_next->nxt = mem_leak_info;
ptr_next = ptr_next->nxt;
}
}
// -----------------------------------------------------------
// Name: ResetInfo
// Desc: It erasing the memory using by List on the basis of info( pos)
void ResetInfo(uint pos)
{
uint index = 0;
leakMem * alloc_info, * temp;
if(pos == 0)
{
leakMem * temp = ptr_start;
ptr_start = ptr_start->nxt;
free(temp);
}
else
{
for(index = 0, alloc_info = ptr_start; index < pos;
alloc_info = alloc_info->nxt, ++index)
{
if(pos == index + 1)
{
temp = alloc_info->nxt;
alloc_info->nxt = temp->nxt;
free(temp);
break;
}
}
}
}
// -----------------------------------------------------------
// Name: DeleteAll
// Desc: It deletes the all elements which resides on List
void DeleteAll()
{
leakMem * temp = ptr_start;
leakMem * alloc_info = ptr_start;
while(alloc_info != NULL)
{
alloc_info = alloc_info->nxt;
free(temp);
temp = alloc_info;
}
}
// -----------------------------------------------------------
// Name: MyFree
// Desc:
void MyFree(void * mem_ref)
{
uint loop;
// if the allocated memory info is part of the list, removes it
leakMem *leak_info = ptr_start;
/* check if allocate memory is in our list */
for(loop = 0; leak_info != NULL; ++loop, leak_info = leak_info->nxt)
{
if ( leak_info->memData.addr == mem_ref )
{
ResetInfo(loop);
break;
}
}
free(mem_ref);
}
// -----------------------------------------------------------
// Name: SubAddMemInfo
// Desc: it also fill the the Info
void SubAddMemInfo (void * mem_ref, uint nSize, cchar * file, uint lineNumber)
{
infoMem AllocInfo;
/* fill up the structure with all info */
memset( &AllocInfo, 0, sizeof ( AllocInfo ) );
AllocInfo.addr = mem_ref;
AllocInfo.nSize = nSize;
strncpy(AllocInfo.fileName, file, MAX_FILENAME_LENGTH);
AllocInfo.lineNumber = lineNumber;
/* SubAdd the above info to a list */
SubAdd(AllocInfo);
}
// -----------------------------------------------------------
// Name: WriteMemLeak
// Desc: It writes information about Memory leaks in a file
// Example: File is as : "/home/asadulla/test/MemLeakInfo.txt"
void WriteMemLeak(void)
{
uint index;
leakMem *leak_info;
FILE * fp_write = fopen(OutFile, "wt");
char info[1024];
if(fp_write != NULL)
{
sprintf(info, "%s\n", "SUMMARY ABOUT MEMORY LEAKS OF YOUR SOURCE FILE ");
fwrite(info, (strlen(info) + 1) , 1, fp_write);
sprintf(info, "%s\n", "-----------------------------------");
fwrite(info, (strlen(info) + 1) , 1, fp_write);
for(leak_info = ptr_start; leak_info != NULL; leak_info = leak_info->nxt)
{
sprintf(info, "Name of your Source File : %s\n", leak_info->memData.fileName);
fwrite(info, (strlen(info) + 1) , 1, fp_write);
sprintf(info, "Starting Address : %d\n", leak_info->memData.addr);
fwrite(info, (strlen(info) + 1) , 1, fp_write);
sprintf(info, " Total size Of memory Leak : %d bytes\n", leak_info->memData.nSize);
fwrite(info, (strlen(info) + 1) , 1, fp_write);
sprintf(info, "Line Number for which no DeAllocation : %d\n", leak_info->memData.lineNumber);
fwrite(info, (strlen(info) + 1) , 1, fp_write);
sprintf(info, "%s\n", "-----------------------------------");
fwrite(info, (strlen(info) + 1) , 1, fp_write);
fwrite(info, (strlen(info) + 1) , 1, fp_write);
}
}
DeleteAll();
}
Source File for detecting memory leak is as Here you can gice your own source file and in this source file you have write onle line to include file #include"findLeak.h"
Source File : test.c
Code: c
#include
#include"findLeak.h"
int main()
{
int *p1 = (int *)malloc(10);
int *p2 = (int *)calloc(10, sizeof(int));
char *p3 = (char *) calloc(15, sizeof(float));
float *p4 = (float*) malloc(16);
free(p2);
WriteMemLeak();
return 0;
}
Now user can compile these programmes in a console as :
> g++ test.c findLeak.c
and give a command for run
> ./a.out
then go to you your directory where you have defined a macro "OutFile" and open this defined file and you can see the results.
Output of above source file is as:
Code: output
SUMMARY ABOUT MEMORY LEAKS OF YOUR SOURCE FILE
-----------------------------------
Name of your Source File : test.c
Starting Address : 184960
Total size Of memory Leak : 10 bytes
Line Number for which no DeAllocation : 7
-----------------------------------
-----------------------------------
Name of your Source File : test.c
Starting Address : 187104
Total size Of memory Leak : 60 bytes
Line Number for which no DeAllocation : 9
-----------------------------------
-----------------------------------
Name of your Source File : test.c
Starting Address : 184984
Total size Of memory Leak : 16 bytes
Line Number for which no DeAllocation : 10
-----------------------------------
-----------------------------------
Detail About Recursion and its Type
Introduction
Here I am going to give a detail about Recursion in C++. Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.
Many complex problem can be solved by recursion in a simple code. But it's too much costly than iterative. because in every recursion call one stack frame will formed.You all already know that about it's cost. but if problem is very complex than no way to solve except recursion.
Background
First recursion came into mathematics and then came into Computer science. Idea of it's use that first broke your problem into subproblems and solve it by using recursion.
The code
In C++, Recursion can be divided into two types:
(a)Run- Time Recursion: Normal as in C
(b)Compile- Time Recursion: By using Template
Each of these can be also divided into following types:
1. Linear Recursion
2. Binary Recursion
3. Tail Recursion
4. Mutual Recursion
5. Nested Recursion
1. Linear Recursion: This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called 'Winding' and when it returns to caller that is called 'Un-Winding'. Termination condition also known as Base condition.
Example: Factorial calculation by linear recursion
Run-Time Version
Code:
int Fact(long n)
{
if(0>n)
return -1;
if(0 == n)
return 1;
else
{
return ( n* Fact(n-1));
}
}
Winding Process:
Function called Function return
Fact(6) 6*Fact(5)
Fact(5) 5*Fact(4)
Fact(4) 4*Fact(3)
Fact(3) 3* Fact(2)
Fact(2) 2* Fact(1)
Fact(1) 1* Fact(0)
Terminating Point
Fact(0) 1
Unwinding Process
Fact(1) 1*1
Fact(2) 2*1
Fact(3) 3*2*1
Fact(4) 4*3*2*1
Fact(5) 5*4*3*2*1
Fact(6) 6*5*4*3*2*1
Compile-Time Version
Code:
// template for Base Condition
template <>
struct Fact<0>
{
enum
{
factVal = 1
};
};
template
struct Fact
{
// Recursion call by linear method
enum
{
value = n * Fact::factVal
};
};
To test it how it's working at compile time, just call
cout <<>::factVal ;
And compile it then compiler error will come, because no template for -1.
2. Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it's using in data structure like operations for tree as traversal, finding height, merging, etc.
Example: Fibonacci number
Run Time Version Code
Code:
int FibNum(int n)
{
// Base conditions
if (n < 1)
return -1;
if (1 == n || 2 == n)
return 1; // Recursive call by Binary Method
return FibNum(n - 1) + FibNum(n - 2);
// At a time two recursive function called so Binary
}
// binary }
Compile Time Version Code
Code:
// Base Conditions
template<>
struct FibNum<2>
{
enum { val = 1 };
};
template <>
struct FibNum<1>
{
enum { val = 1 };
};
// Recursive call by Binary Method
template
struct FibNum
{
enum { val= FibNum::val + FibNum ::val };
};
3. Tail Recursion: In this method, recursive function is called at the last. So it's more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.
Example: Fibonacci number
Run Time Version Code
Code:
int FibNum(int n, int x, int y)
{
if (1 == n) // Base Condition
{
return y;
}
else // Recursive call by Tail method
{
return FibNum(n-1, y, x+y);
}
}
Compile Time Version Code
Code:
template
struct FibNum
{
// Recursive call By tail method
enum
{
val = FibNum::val
};
};
// Base Condition or Termination
template
struct FibNum<1,>
{
enum
{
val = y
};
};
4. Mutual Recursion: Functions calling each other. Let's say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it's doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.
Example: To find Even Or Odd number
Run Time Version Code
Code:
bool IsOddNumber(int n)
{
// Base or Termination Condition
if (0 == n)
return 0;
else
// Recursive call by Mutual Method
return IsEvenNumber(n - 1);
}
bool IsEvenNumber(int n)
{
// Base or Termination Condition
if (0 == n)
return 1;
else
// Recursive call by Mutual Method
return IsOddNumber(n - 1);
}
Compile Time Version Code
Code:
// Base Or Termination Conditions
template <>
struct IsOddNumber<0>
{
enum
{
val = 0
};
};
template <>
struct IsEvenNumber<0>
{
enum
{
val = 1
};
};
// Recursive calls by Mutual Method
template
struct IsOddNumber
{
enum
{
val = n == 0 ? 0 : IsEvenNumber::val
};
};
template
struct IsEvenNumber
{
enum
{
val = n == 0 ? 1 : IsOddNumber::val
};
};
5.Nested Recursion: It's very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.
Example: Ackermann function
Run Time Version Code
Code:
int Ackermann(int x, int y)
{
// Base or Termination Condition
if (0 == x)
{
return y + 1;
}
// Error Handling condition
if (x <> 0 && 0 == y)
{
return Ackermann(x-1, 1);
}
// Recursive call by Nested method
else
{
return Ackermann(x-1, Ackermann(x, y-1));
}
}
Compile Time Version Code
Code:
// Base Or Termination condition
template
struct Ackermann<0,>
{
enum { val = y + 1 };
};
// Recursive Call by Linear Method
template
struct Ackermann
{
enum
{
val = Ackermann::val
};
};
// Recursive Call by Nested Method
template
struct Ackermann
{
Enum
{
val = Ackermann::val>::val
};
};
References
"Teaching recursion using recursively generated geometric design"
by Aaron Gordon
Subscribe to:
Posts (Atom)