Monday, May 16, 2011 | By: Kunal Ekawde

vtable usage understanding

Assuming that virtual function concept is clear, I would like to jot down some understanding with respect to use of vtable in virtual function call.

Every class which has a virtual function or is derived from the class which has, has a vtable. Its created by the compiler. For information, you can see the vtable created for the class using the g++ option '-fdump-class-hierarchy'. In the new generated file *.class file, check the Vtable.

For example for following c++ program:
class Base
{
public:
Base(){cout<<"In Base Ctor"<<endl;}
virtual ~Base() {cout<<"In Base Dtor"<<endl;}
virtual void b1() {cout<<"Base b1"<<endl;}
virtual int b2() {cout<<"Base b2"<<endl;}
void b3(int x) {cout<<"Base b2"<<endl;}
};

class Derived
{
public:
Derived() {cout<<"In Drvd Ctor"<<endl;}
~Derived() {cout<<"In Drvd Dtor"<<endl;}
void b1() {cout<<"Drvd b1"<<endl;}
void b1(int x) {cout<<"Drvd b1 x"<<endl;}
//int b1() {} --> Compile Error
virtual void d1() {cout<<"Drvd d1"<<endl;}
};
The vtable for Base and Derived would be:
Vtable for Base
Base::_ZTV4Base: 6u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI4Base)
8 Base::~Base
12 Base::~Base
16 Base::b1
20 Base::b2

Vtable for Derived
Derived::_ZTV7Derived: 7u entries
0 (int (*)(...))0
4 (int (*)(...))(& _ZTI7Derived)
8 Derived::~Derived
12 Derived::~Derived
16 Derived::b1
20 Base::b2
24 Derived::d1

  • The First entry is the offset to top of the actual object being pointed to from the location of vptr of current used (L-Part) object. Its 0 for single inheritance. In multiple level inheritance e.g class Derived:public Base1,public Base2 and Base2* pb2 = new Derived(), when the this pointer is adjusted to Base2 part location in Derived object and during re-adjusting it back, it has to know to which object(size) it was adjusted, which can be known by RTTI information, which in-turn can be located after starting location of that object.
  • The Second entry points to typeinfo object used for RTTI.
  • Third and Fourth entries are for virtual destructor, the first one destructs object w/o calling delete(), while the second calls the delete() after destroying object.
  • Fifth entry is of virtual function b1(), which is override 'd by the Derived class, each vtable has its own separate address.
  • Sixth entry is of b2(), which is not defined in Derived, but inherited and hence both vtables have same address.
  • Seventh entry is present in Derived class as a new virtual function is defined.
Now, suppose we have the following:
I)
Base* bptr = new Derived();
bptr->b1();
To find which instance of b1() has to be called:
1. bptr points to Base part in Derived object.In case of single inheritance, its pointing to Derived.
2. The function b1() is called via bptr(w/o any casting) so vtable has to be consulted.
3. The compiler knows that for b1(), it has to access the fifth location and its vptr is pointing to the actual referenced object i.e Derived.
4. Hence, (16 Derived::b1) is called.

II)
Consider:
bptr->d1();
This would give compile error, as in bptr type(Base), the function d1() is not known. Even though bptr is pointing to Derived object and its vtable has d1(), the compiler restricts it to types in pointer type(Base) as bptr = new Base();bptr->d1() could also be possible then but its an incorrect call.

III)
Line 18 in the program would give compile error as with same function arguments we are trying to override the b1() function with different return type, while Line 17 is fine, as the function signature is different and hence Derived class is not overriding it.

IV)
Virtual destructor works in same fashion as virtual function, once Derived destructor is called, the base is also followed. Logic to call Base could be in destructor of Derived.

V)
Virtual functions should not be called in constructors and destructors. Mainly 2 things:
(a) When the base part of derived object is being created, the derived members are not initialized yet.
(b) When the base part of derived object is being created, the this pointer belongs to the current class i.e base, the virtual functions, RTTI belongs to current class.
During destruction, the derived is first destructed and then Base,(derived part no longer exist) therefore in base destructor, the virtual function points to that of base only.

VI)Incase we have a Base w/o any virtual function (with some data members --to make its offset different from Derived) and Derived has and we delete a base pointer pointer to Derived object, the program would dump core. --> This was quite an interesting point for me. I've discussed it here. Basically, free will try to put the entire Derived object in free list, thereby disturbing the admin block of next chunk of data, hence the core dump, instead if Base had virtual destructor, the this pointer is adjusted after destructor of Derived and it cleanly free's the Base and Derived part.
Tuesday, April 12, 2011 | By: Kunal Ekawde

Dynamic Programming Basics

This is very interesting programming / algorithm problem solving technique.
There is a lot of information on this from bing/google about theory and some examples.

What I would like to post is, working example code with some explanation.

Lets consider a simple problem:
Prob) Find the largest strictly increasing continuous sub-sequence from the given sequence.

e.g Seq: 4,5,1,6,3,6,7,9,2,4

Here as we see that increasing sub-sequences are:
1) 4,5
2) 1,6
3) 3,6,7,9
4) 2,4

Hence, the largest turns out to be 3)3,6,7,9
In brute-force / general logic, we would find a max length at each index.
e.g Start at 4, 4>5, max length at 4 is 1, proceed further, compare 4 with 1, 4>1, so the max length remains same(1) else increment it.

Here is C code for same:

int IncSeq::getLargestSeq1(string &seq)
{
cout<< " Seq:"<<seq<<endl;
int maxLen = seq.length();
int i=0,j=0,cnt=0,s=0,max=0,len=0;
for (i=0; i<maxLen; i++)
{
cnt = 0;
s=i;
for (j=i+1; j <maxLen-1; j++)
{
if ( seq[j] > seq[s] )
{
len = ++cnt;
s++;
}
else
break;
}
if (len>max)
max = len;
}
return max;
}
The algorithm takes O(N2).
If we notice, the problem can be divided into sub-problems (on lines of dynamic programming) of find the increasing length from each of the index. At each index we compare the index element with next element and accordingly increment the number.
If we separate the inner loop as follows:

int IncSeq::increasingLenFromIndexM(int i, string &seq, int maxLen)
{
if (maxLen == 0)
return 0;

if ( seq[i+1] > seq[i] )
return 1+increasingLenFromIndexM(i+1, seq, maxLen);
else
return 0;
}

So we see here that if objective of seq[i+1]>seq[i] is satisfied, add to result the next sub-problems result. You can use it as:

int IncSeq::getLargestSeq1(string &seq)
{
cout<< " Seq:"<<seq<<endl;
int maxLen = seq.length();
int i=0,max=0,len=0;

for (i=0; i<maxLen; i++)
{
len = increasingLenFromIndexM(i, seq, maxLen);
if (len>max)
max = len;
}

return max;
}
Another property of dynamic programming is to memoise the answers to sub-problems so that we don't solve them again in recursion. The simplest is to save the answers in an array/table and check it at entry of every sub-problem as follows:

int IncSeq::increasingLenFromIndexM(int i,
string &seq, int maxLen)
{
int res =0;
if (maxLen == 0)
return 0;

if (ans[i]!=0)
return ans[i];

if ( seq[i+1] > seq[i] )
res = 1+increasingLenFromIndexM(i+1, seq, maxLen);
else
res = 0;

ans[i] = res;
return res;
}
Now if you see, it boils down to filling the table with answers of sub-problems.
What if start filling the table backward ? , then we can completely skip memoising the answers.

void IncSeq::dFillAnswers(vector<int>& A, int N)
{
ans[N]=0;

for (int i=N-2; i>=0; i-=1)
{
if ( A[i] < A[i+1] )
ans[i]=1+ans[i+1];
else
ans[i]=0;
}
}
and in function "increasingLenFromIndexM" just return the ans[index].
Thus we have solved the problem using dynamic programming