Generic Delegates: C++ Implementation

Hi Geeks, Hope that you’re fine since the last post and doing well with your bugs and exceptions.
Le’ts get to the topic directly, I was implementing some dirty stuff using C++, and I had to implement a simple event handler, and suddenly some dirty thoughts jumped into my head and asked myself about implementing sort of generic Delegate.

If we were thinking about implementation of Delegate we have to worry about 2 things the first one the return type of the Delegate and the second is argument list, so we can make something like this (Basic Implementation)

#include <iostream>
class Delegate
{
	typedef void(*Callback)(voidp_ptrToObjint parm);
 
public:
	Delegate()
	{}
	Delegate(voidp_objCallback p_func) : m_ptrToObject(p_obj), m_ptrToFunction(p_func)
	{}
	template <class Tvoid (T::*TMethod)(int)>
	//function for making a delegate object
	static Delegate MakeDelegate(T* p_obj)
	{
		Delegate delegate(p_obj, &Call<TTMethod>);
		return delegate;
	}
	void operator()(int p_param)
	{
 
		(*m_ptrToFunction)(m_ptrToObjectp_param);
	}
private:
	Callback   m_ptrToFunction;
	void	   *m_ptrToObject;
 
	template <class Tvoid (T::*TMethod)(int)>
	//Helper function for casting the untyped stored pointer (void*)
	static void Call(void* p_objint param)
	{
		Tptr = static_cast<T*>(p_obj);
		return (ptr->*TMethod)(param);
	}
};
 
//Testing Class
class Test
{
public:
	void Test_foo(int val)
	{
		printf("Test_foo called with value =%d\n"val);
	}
};
 
// Entry point 
void main(void)
{
	Test testObj;
 
	Delegate delegate = Delegate::MakeDelegate < Test, &Test::Test_foo>(&testObj);
	delegate(13);
}

ِAfter checking this implementation, we’ll find that it works with a specific function signature for the delegate function, simply a function that takes a parameter with type (int) and returns (void).

The second implementation is more generic than the previous one, C++ can support us to make a generic return types and argument types , let’s dirty our fingers with some code.

#include <iostream>
template<typename TReturnTypetypename TParam>
class Delegate
{
	typedef TReturnType(*Callback)(voidp_ptrToObjTParam parm);
 
public:
	Delegate()
	{}
	Delegate(voidp_objCallback p_func) : m_ptrToObject(p_obj), m_ptrToFunction(p_func)
	{}
	template <class TTReturnType(T::*TMethod)(TParam)>
	//function for making a delegate object
	static Delegate MakeDelegate(TptrToObj) 
	{
		Delegate delegate(ptrToObj, &Call<TTMethod>);
		return delegate;
	}
	TReturnType operator()(TParam p_param) 
	{
		return (*m_ptrToFunction)(m_ptrToObjectp_param);
	}
private:
	Callback	m_ptrToFunction;
	void	   *m_ptrToObject;
 
	template <class TTReturnType(T::*TMethod)(TParam)>
	//Helper function for casting the untyped stored pointer (void*)
	static TReturnType Call(voidp_objTParam param)
	{
		Tptr = static_cast<T*>(p_obj);
		return (ptr->*TMethod)(param);
	}
};
 
//Testing Class
class Test
{
public:
	int Test_foo(int val)
	{
		int res = val + 10;
		printf("Test_foo returned %d\n"res);
		return res;
	}
};
 
// Entry point 
void main(void)
{
	Test testObj;
	Delegate<intint>  delegate = Delegate<intint> ::MakeDelegate<Test, &Test::Test_foo>(&testObj);
	delegate(20);
}

Hmmm, as you can see, it’s little bit generic, but we still controlled with limited number of arguments, that’s not the target. we need to reach to dynamic return type and dynamic argument list.

Ok, I’ll tell you something about me, some days ago I was reading a book named “Modern C++ design”, seems old but golden one (قطعة من الجنة) and I was reading specifically the part related to Functors’ implementation, and I knew about something in C++ named TypeLists, you can read about it from the book and you can find its implementation here , and after little efforts of online searching I accidentally found something that may be a golden solution for my problem, it’s variadic templates.

variadic templates are templates that accept zero or more template arguments (non-types, types, templates) and supported in C++ since C++11, and it’s considered as a solution for a long standing C++ problem.

template<typename ... TParam>

I think the solution of our problem is clear now, and now it’s the time to dirty our hands with a real generic version of Delegates

#include <iostream>
template<typename TReturnTypetypename ... TParams>
class Delegate
{
	typedef TReturnType(*Callback)(voidp_ptrToObjTParams...);
 
public:
	Delegate()
	{}
	Delegate(voidp_objCallback p_func) : m_ptrToObject(p_obj), m_ptrToFunction(p_func)
	{}
	template <class TTReturnType(T::*TMethod)(TParams...)>
	//function for making a delegate object
	static Delegate MakeDelegate(TptrToObj)
	{
		Delegate delegate(ptrToObj, &Call<TTMethod>);
		return delegate;
	}
	TReturnType operator()(TParams...p_paramList)
	{
		return (*m_ptrToFunction)(m_ptrToObjectp_paramList...);
	}
private:
	Callback	m_ptrToFunction;
	void	   *m_ptrToObject;
 
	template <class TTReturnType(T::*TMethod)(TParams...)>
	//Helper function for casting the untyped stored pointer (void*)
	static TReturnType Call(voidp_objTParams...p_paramList)
	{
		Tptr = static_cast<T*>(p_obj);
		return (ptr->*TMethod)(p_paramList...);
	}
};
 
//Testing Class
class Test
{
public:
	int Test_foo(int val)
	{
		int res = val + 10;
		printf("Test_foo returned %d\n"res);
		return res;
	}
	int Test_bar(int xint yint z)
	{
		z = x*y;
		printf("Test_bar returned %d\n"z);
		return z;
	}
};
 
// Entry point 
void main(void)
{
	Test testObj;
	
	auto delegate = Delegate<intint>::MakeDelegate<Test, &Test::Test_foo>(&testObj);
	delegate(20);
	auto delegate1 = Delegate<intint,int,int>::MakeDelegate<Test, &Test::Test_bar>(&testObj);
	delegate1(10, 20, 30);
}

Ohh, finally it’s done, finally we have Delegate implementation for different functions signatures.

A more handsome implementation here on github that supports both Multicast and Unicast delegates.

References:
Advertisements

Calling Conventions (__cdecl, __stdcall, …etc)

Calling convention is considered as a low-level scheme of how subroutines (i.e. functions) receive parameters from their callers and how they return a result, that seems somehow related to the programming language implementation and the compiler design.

  • The calling conventions vary in:
    • Where parameters, return values and return addresses are placed( in registers, call stack, a mix of both, or in other memory structures)  ?
    • The order in which actual arguments for formal parameters are passed.
    • How a return value is delivered from the callee back to the caller (on the sack, in a register, or within the heap) ?
    • How the task of setting up for and cleaning up after a function cal is divided between the caller and the callee.

From this  sense, calling conventions categorized in 3 types (Caller cleanup, Callee cleanup, Either Caller or Call cleanup). Not all conventions are available on all supported platforms, and some conventions use platform-specific implementations, in this article we’ll mention briefly some calling conventions use when programming x86 architecture microprocessor, and supported by visual C/C++ compilers.

Keyword Stack cleanup Parameter passing
__cdecl

Caller

Pushes parameters on the stack, in reverse order (right to left)
__clrcall

n/a

Load parameters onto CLR expression stack in order (left to right).
__stdcall

Callee

Pushes parameters on the stack, in reverse order (right to left)
__fastcall

Callee

Stored in registers, then pushed on stack
__thiscall

Callee

Pushed on stack; this pointer stored in ECX
__vectorcall

Callee

Stored in registers, then pushed on stack in reverse order (right to left)

We’ll pick one of these calling convention to talk about here which is (__cdecl) , and we can revise msdn articles in this topic from here.

__cdecl : stands for (C declaration) Is the default calling convention for C/C++ programs, subroutine’s arguments are passed on the stack. Integer values and memory addresses are returned in the EAX register, (EAX, ECX, EDX) registers are reserved for the caller and the reset reserved for the callee. In context of the C programming language, function arguments are pushed on the stack in reverse order, for example

int callee(intintint);
int caller(void)
{
	int ret;
	ret = callee(1, 2, 3);
	ret += 5;
	return ret;

The produced assembly code on Intel-x68 machines will be as follows:

push	ebp
mov 	ebpesp
push	3
push	2
push	1
call	callee
add 	esp, 12
add 	eax, 5
pop 	ebp
ret

The caller cleans the stack after the function call returns. The __cdecl  as we mentioned is usually the default calling convention for x-86 C/C++ compilers, although many compilers provide options to change the calling convention used, by manually define a function to be _cdecl, as follows

void _cdecl funct();

note: the _cdecl modifier must be included in the function prototype and declaration. Because the stack is cleaned up by the caller in this calling convention, it can be used simply be used to make vararg functions, by writing something like this:

int __cdecl system(const char *);
// Example of the __cdecl keyword on function pointer
typedef BOOL(__cdecl *funcname_ptr)(void * arg1const char * arg2DWORD flags, ...);

I found recently this summarized tutorial on code project, highly recommend and worth reading.

References:

Declare destructors virtual in a polymorphic base classes

let’s start with a simple example from Effective C++ Third Edition.

TimeKeeper Example
  1. class TimeKeeper
  2. {
  3. public:
  4.     TimeKeeper();
  5.     ~TimeKeeper();
  6. };
  7. class AtomicClock: public TimeKeeper{};
  8. class WaterClock : public TimeKeeper{};
  9. class WritstWatch: public TimeKeeper{};

for managing the creation of objects will create a factory function that returns a dynamically allocated object of a class derived from “TimeKeeper”.

  1. TimeKeeper* getTimeKeeper();

The objects returned by this functions are on the heap memory, so to avoid leaking the memory and other resources it’s important to clean up these objects constantly after using them.

  1. TimeKeeper *ptk = getTimeKeeper();
  2. delete ptk;

Suppose that (getTimeKeeper) returns a pointer to a derived class object (ex. AtomicClock), this object is being deleted via a base class pointer and the base class (TimeKeeper) has a non-virtual destructor, this may lead to a disaster as C++ specifies that when a derived class object is deleted through a pointer to a base class with a non-virtual destructor, results are undefined.
What happens in runtime is that the derived part of the object is never destroyed, the data members of the derived class object probably not to be destroyed nor the destructor run, although the base class part will be destroyed and this will lead to a partially destroyed object, and this is a way of leaking resources.
Eliminating this problem is very simple, by giving the base class a virtual destructor  like this.

  1. class TimeKeeper
  2. {
  3. public:
  4.     TimeKeeper();
  5.     virtual ~TimeKeeper();
  6. };
  7. class AtomicClock: public TimeKeeper{};
  8. class WaterClock : public TimeKeeper{};
  9. class WritstWatch: public TimeKeeper{};
  10. TimeKeeper *ptk = getTimeKeeper();
  11. delete ptk;  // now behaves correctly

If a class does not contain virtual functions, that often indicates it won’t be used as a base class. When a class is not intended to be a polymorphic class, making a virtual destructor is usually a bad idea.

Point Class Example
  1. class Point
  2. {
  3. public:
  4.     Point(int xCoord, int yCoord);
  5.     ~Point();
  6. private:
  7.     int x, int y;
  8. };

if an int occupies 32 bits, a Point class object can fit into 64-bit register, the implementation of virtual functions requires the objects carry information that can be used at runtime to determine which virtual functions should be invoked on the object.

This information typically takes the form of a pointer called vptr  (Virtual Table Pointer) , this pointer points to an array of function pointers called vtbl (Virtual Table) each class with virtual functions has an associated vtbl, when a virtual functions is invoked on an object, the actual function called is determined by following the object’s vptr to a vtbl and then looking up the appropriate function pointer in vtbl.

Regarding the class “Point” if the it contains a virtual function, objects of type “Point” will increase in size, on 32-bit architecture, they’ll go from 64 bits (for the two ints x,y) to 96 bits (for the ints + vptr) and from 64 to 128 bits in 64-bit architecture, because pointer on these architectures are 64-bit size, by adding  vptr to “Point” the size will be increased by 50-100% ! No longer can “Point” objects fit in a 64-bit register.

We can summarize this topic in two points

Polymorphic base classes should declare virtual desturcotrs, If a class has any virtual functions, it should have a virtual destructor.

Classes not designed be used polymorphically should not declare virtual destructors.

But take care NOT all base classes are designed to be used polymorphically, for example standard string.

  1. class SpecialString : public std::string{ …. };

This is a bad idea as std::string has non-virtual destructor and not designed to be used polymorphically and if anyone tried to convert pointer to SpeicalString to pointer to std::string and then used delete this will lead to undefined behavior and SpecialString resources will be leaked as the destructor won’t be called, and you’ll find this -lacking of virtual destructor- in all STL types also (e.g vector, list, set, … etc).Unfortunately,  C++ doesn’t offers derivation-prevention mechanism in contrast to Java’s final classes or C#’s sealed classes.

So, DON’T forget Not all base classes are designed to be used polymorphically.

References:
  • Effective C++, Third Edition —Scott Meyers.
  • Professional C++— Nicholas A. Solter Scott J. Kleper. 

Constructors & Destructors in C++

Most of classes we write contain one or more constructors and destructors, which are responsible for controlling the fundamental operations of bringing new object into existence and making sure it’s initialized and getting rid of an object and making sure it’s cleaned up. Making mistakes in these functions will lead to unremarkable serious errors throughout the implemented classes, so in this post we are going to discuss some tips and tricks about how to deal with constructors and destructors that help in writing efficient C++ code.

Silent Calling and Writing of functions

It seems that you may implement an empty class in C++ like this

class EmptyClass{…};

actually this is not an empty  class as the compiler will generate its own version of copy constructor and copy assignment operator, moreover if you didn’t declare constructor the compiler will declare a default constructor and all of these functions will be public and inline ,so the previous line of code and the following code snippet are considered to be the same.

  1. class Empty {
  2. public:
  3.     Empty() { … }    // default constructor
  4.     Empty(const Empty& rhs) { … }// copy constructor
  5.     ~Empty() { … }// destructor
  6.     // for whether it’s virtual
  7.     Empty& operator=(const Empty& rhs) { … } // copy assignment operator
  8. }

The following code will cause these functions to be generated

Empty e1; // default constructor, destructor
Empty e2(e1); // Copy constructor
e2 = e1; // Copy assignment operator

We can ask here, what should these functions do ?!
Regarding default Constructor and Destructor, they give the compiler a place to put behind the scenes code such as invocation of constructor and destructor of base classes and non-static data members, and this generated desturctor is non-virtual unless it’s for a class inheriting from base class that itself  declares virtual destructor.

And regarding copy constructor and the copy assignment operator, the compiler-generated code simply copy each non-static data member of the source object to the target object.We can summarize all of this in one sentence

Compilers may implicitly generate a class’s default constructor, copy constructor, copy assignment operator and destructor.

From this sense we can ask how to disallow the use of compiler-generated functions that we don’t want ?!

The answer is very simple, we’ll declare the corresponding member functions private and won’t give them an implementation.

Class Test Example
  1. class Test
  2. {
  3. public:
  4.   //public members
  5. private:
  6.     Test (const Test&);
  7.     Test& operator= (const Test&);
  8. };

The user won’t be able to copy “Test” object , and if there’s a trial to copy an object the linker will complain and the error will be “can’t find appropiate default constructor”, but it’s possible to move the link-time error up to compile-time where the earlier error detection is always better than later by declaring the constructor and copy assignment operator private not in “Test” class but in a base class designed specifically to prevent copying

Modified Test Example
  1. class UnCopyable
  2. {
  3. protected:
  4.     UnCopyable(){}
  5.     ~UnCopyable(){}
  6. private:
  7.     UnCopyable (const UnCopyable&);
  8.     UnCopyable& operator= (const UnCopyable&);
  9. };
  10. class A : public UnCopyable
  11. {
  12. // no longer defines ctors or copy assignment operator
  13. };

The compiler will try to generate a copy constructor or copy assignment operator if any body tries to copy a “Test” object, the compiler-generated versions of these function will try to call the base class functions, and this will be rejected as the copying operations are private.

To disallow functionality automatically provided by compilers, declare the corresponding member functions private and give no implementations.

That’s enough for today ! To Be Continued …

References
  • Effective C++, Third Edition —Scott Meyers.
  • Professional C++— Nicholas A. Solter Scott J. Kleper. 

Writing Efficient C++

First of all before of writing some tips to write an efficient code using C++, we need to define the term  of efficient code. There are multiple factors to measure the efficiency of any written code like (Speed, Memory Usage, Disk Access, Network use .. etc), so we can say that the efficient program is the program that completes its tasks as quickly as possible within the given circumstances, so the program can be efficient without being fast, if the application domain is mainly prohibitive to quick execution.

Regarding to professional C++ book 2005, there are two approaches to efficiency. The traditional  one is to writing efficient program and  optimizing, or improving the performance and this technique usually relates to Language-Level Efficiency: Some specific, independent code changes such as passing by reference, returning by reference, exception handling .. etc

The second approach is to think about the efficiency from the design point of view, and this named Design-Level efficiency: includes choosing efficient algorithms, avoiding unnecessary steps and  computations, and selecting appropriate design and optimizations. In this post we’ll discuss the first approach which is Language-Level Efficiency.

Language-Level Efficiency

As we previously mentioned, some specific, independent code changes such as passing by reference, returning by reference and so on and we’ll mention some tips and trick related to this.

  • Handling Object Efficiently:
    • Pass-By-Reference
    • Return by Reference
    • Catch Exceptions by reference
    • Avoid creating temporary objects
    • Return Value Optimization
  • Don’t Overuse costly language features
  • Use Inline methods.

Handling Objects Efficiently

  • Pass by reference: 

    Objects should rarely be passed by value to a function or method, as Pass-by-value incurs copying costs that are avoided by pass-by-reference. Assume that you have a class named “ClassA” and you’ll pass an instantiated object to some function to process it, you could write a function that takes a ClassA Object in the following way.

  1. void TestClassA( const ClassA& classAObj)
  2. {/*Test Code*/}

instead of

  1. void TestClassA( ClassA classAObj)
  2. {/*Test Code*/}
  • Return by reference: 

    As you should pass the object by reference to functions, you should also return them by reference from functions in order to avoid unnecessarily copying of the object. And sometimes returning by reference is impossible , such as when you write overloaded operator+ and other similar operators. And take care “You should never return a reference or a pointer to a local object that will be destroyed when the function exits”

  • Catch Exception by reference:

    You should catch exceptions by reference in order to avoid an extra copy. exceptions are heavy in terms of performance.

  1. try{
  2.     …
  3. }
  4. catch(CustomException &e){
  5.     …
  6. }
  • Avoid Creating Temporary Objects: 

    The compiler creates temporary, unnamed objects in several circumstances. for example after writing a global operator+ for a class.

  1. class ClassTest{
  2. private:
  3.     int m_value;
  4. public:
  5.     ClassTest(){}
  6.     ClassTest(double &initialValue):m_value(initialValue){}
  7.     void Set(int value)
  8.     {m_value = value;}
  9. };
  10. const ClassTest operator+(const ClassTest& lhs, const ClassTest& rhs)
  11. {
  12.     ClassTest test;
  13.     test.Set(lhs.m_value+ rhs.m_value);
  14.     return (test);
  15. }

In general, the compiler constructs a temporary object whenever your code converts a variable of one type to another type  This rule applies mostly to function calls. For example, suppose that you write a function like this:

  1. void doSomething(const ClassTest& s);

and you called this function like this: doSomething( 5.5) , The compiler constructs a temporary ClassTest object from 5.5 using the double constructor,which it passes to doSomething(), So generally try to avoid such of these cases in which the compiler is forced to construct temporary objects and you should at least be cognizant of the existence of this “feature” so you aren’t surprised by performance results.

  • Return Value Optimization:

    A function that returns an objects by value can cause the creation of a temporary object.

    1. Person CreatePerson()
    2. {
    3.     Person newP;
    4.     return (newP);
    5. }

Finally, don’t worry about this issue because the compiler will optimize away the temporary variable in most cases. This optimization is called the return value optimization.

Don’t Overuse Costly language features

Several C++ features are costly in term of execution speed: exceptions, virtual methods, and Run-Time Type Information RTTI. If the code efficiency is an important factor for you, then you should consider avoiding these features. Unfortunately, support for exceptions and RTTI incurs performance overhead even if you don’t explicitly use the features in your program should be compiled without support for these features at all.

  1. Class base
  2. {
  3. public:
  4.     base() {}
  5.     virtual ~base() {}
  6. };
  7. class derived : public base {};
  8. int main(int argc, char** argv)
  9. {
  10.     base* b = new derived();
  11.     derived* d = dynamic_cast<derived*>(b); // Use RTTI.
  12.     if (d == NULL) {
  13.         throw exception(); // Use exceptions.
  14.     }
  15.     return (0);
  16. }

and the problem here when dynamic_cast<> fails at run time causing the program to generate segmentation violation exception.

Use Inline Methods

As most of us know that the code for an inline method is inserted directly into the code where it is called, avoiding the overhead of a function call. “However, remember that inlining requests by the programmer are only a recommendation to the compiler. It can refuse to inline the function that you want it to inline.”

On the other hand, some compilers inline appropriate functions and methods during their optimization steps, even if those functions aren’t marked with the inline keyword.

  1. inline void Hello();
References:

Tips To Enhance Technical Skills

I’m writing this post to share some thoughts about improving the technical skills of computer science students, this post will be updated whenever I remember one of my scattering thoughts 😀 Feel free share your thoughts with us in comments, and I’ll feel happy to add them to the post.

  • Practice, Practice, and  Practice to the Infinity –  The direct path to enhance your coding skills. Simply, practice means writing/reading codes. Practice with a defined Goal , practice on things that aren’t easy for you, and always create a schedule or structure to follow.
  • NEVER STOP solving problems on different online judges (TopcoderUVaSPOJCodeforcesUSACO, .. etc)  and participating in online and offline competitions, this will help you to enhance your thinking skills and improve your coding skills by writing bug-free, well-tested, and high-performance code.
  • Learn a different programming language every some period, for example every semester or every year, but be professional in using one of them.
  • NEVER STOP learning new topics and new techniques, and implement them.
  • When you get your summer vacation try to make code re-factoring to the code of your academic projects and document this code, it could be useful for sharing the code online and allowing others to contribute to it. To be honest I never made this, but it’s a very important point.
  • Reading and figuring out the problems of codes that written by different people.
  • Share your code with people to get reviews on your code, you can share it on some of online open source communities like Code project and Sourceforge.
  • Get involved with open source projects, there are multiple open source projects that have many experienced software programmers  working on them.
  • Write a documentation for code written by other people. This helps in understanding the way other people think and program.
  • Try to build a good team with different qualifications, pairing programming with other programmers might increase the quality of code.
  • Seek first to be professional in the basics of computer science ,then to learn the advanced topics.
  • Explain what you know to others, this sometimes helps you to fill the gap in your knowledge, always share your knowledge with others.
  • Don’t hesitate to ask questions on online groups like LinkedIn groups.
  • Attend the online courses on Coursera, Udacity and so on.
  • Broaden your horizons by following some technical magazines, technical blogs,  to be aware of the latest technologies, latest research and projects all over the world.

OOC: Methods and Classes

Hello, advice before start reading!  take a long breath, and check the references of the post while reading. and don’t try this at homes 😉

let’s implement a String Class In C !! What we need to implement a String data type?!
all what we need is a dynamic buffer to hold the text and when the string is deleted we need to free the buffer.

Goal Of The Post

Be able to write these two lines of code

void * a = new(String, "Text");
delete(a);

Flashback !!

Let us remember something from the previous post about new() and delete().

  • new():

    • new was responsible for creating an object, and also know that type of object it’s creating as it has its description in the first parameter.
    • Problem Here !!
      • Assume that we are creating just 100 different data types, then we’ll handle this in new()  by using multiple of if statements which is a great problem, as new()  must contain the code for each data type explicitly.
  • delete():
    • delete was responsible for freeing the memory and checking the available resources.
    • Problem Here !!
      • it acts differently depending on the type of the object for instance String, delete with string type must the buffer.

Let’s think about the solution, as we noticed new() need a description for the object to be able to allocate it,  we can simply think about making new and delete GENERIC for any data type and make a type-specific functions we can name them (Constructor and Destructor) that can be used in initialization and as they do not change we can pass them to new and delete as a part of the type description.

  • IMP note: Note that constructor and destructor are not responsible for acquiring and releasing the memory for an object itself — this is the job of new() and delete().

the constructor is invoked by new() and just initialize the memory area allocated by new() and delete()  calls the destructor that destructs the initialization made by constructor before delete() recycles the memory area allocated by new().

Then, how can delete() locate the destructor function

struct type {
size_t size; /* size of an object */
void (* dtor) (void *); /* destructor */
};
struct String {
const void * destroy;
char * text; /* dynamic string */
};

if we noticed the pointer named (destroy) in the previous code snippet, What Should This pointer point to ?!!

If all we have is the address of an object, this pointer gives us access to type-specific information for the object, such as its destructor function. but what if we have multiple functions (compare, clone, .. etc), so this pointer will point to a table of function pointers.

struct Class {
size_t size; &nbsp;&nbsp;/*length of allocated space*/
void * (* ctor) (void * self, va_list * app); &nbsp;/*to initialize memory*/
void * (* dtor) (void * self); /*to free the memory */
void * (* clone) (const void * self); /*make a copy of the object*/
int (* differ) (const void * self, const void * b); /*comparison*/
};
struct String {
const void * class; /* must be first */
char * text;
};

as we see many object may share the same type descriptor, the same amount of allocated memory and the same methods can be applied to all of them. All objects that have the same type descriptor are named Class.

ohhh, that’s enough for today, to be continued in the next post In Shaa’ ALLAH  with Polymorphism and Dynamic Linkage.

new.h

#ifndef NEW_H_
#define NEW_H_
#include <stddef.h>
void* new(const void *class,...);
void delete(void* item);

void *clone(const void *slef);
int differ(const void *self, const void* b);
size_t sizeOf(const void* self);

#endif /* NEW_H_ */

new.r

this is the representation file, check first reference.

#ifndef CLASS_R
#define CLASS_R

#include <stdarg.h>
#include <stdio.h>

struct Class{

size_t size;
 void *(*ctor)(void *self, va_list *app);
 void *(*dtor)(void *self);
 void *(*clone)(const void *self);

 int(*differ) (const void *self, const void *b);
};
#endif

new.c

#include <assert.h>
#include <stdlib.h>
#include <stdarg.h>

#include "new.h"
#include "new.r"

void* new (const void* _class, ...)
{
 const struct Class* class = _class;
 void *p = calloc(1,class->size);
 assert(p);
 *(const struct Class **)p = class;
 if(class->ctor)
 {
 va_list ap;
 va_start(ap,_class);
 p = class->ctor(p, &ap);
 va_end(ap);
 }
 return p;
}

void delete(void *self)
{
 const struct Class ** cp = self;
 if(self && *cp && (* cp)->dtor)
 self = (* cp)->dtor(self);
 free(self);
}

String.h

#ifndef STRING_H_
#define STRING_H_

extern const void *String;

#endif /* STRING_H_ */

String.c

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>

#include "String.h"
#include "new.h"
#include "new.r"
struct String
{
 const void *class;
 char *text;
};

static void *String_ctor(void *_self, va_list* app)
{
 struct String *self = _self;
 const char* text = va_arg(*app, const char*);

self->text = malloc(strlen(text)+1);
 assert(self->text);
 strcpy(self->text,text);
 return self;
}

static void *String_dtor(void *_self)
{
 struct String *self = _self;
 free(self->text),self->text = 0;
 return self;
}

main.c

#include <stdio.h>
#include <stdlib.h>

#include "String.h"
#include "new.h"

int main(void) {
void * str = new(String, "Text");
delete(str);
return 0;
}

References:

Object Oriented Programming In C

Overview

As most of us know, C language is an imperative (procedural) language and does not support Object Oriented Programming Concepts like information hiding, inheritance,polymorphism .. etc, from this sense, it seems to be hard to make our code reusable and maintainable.
Hence, we can ask what if we want to apply OOP, OOAD concepts in C language?! that’s we are going to talk about in our post.
We are going to write some posts related to this topic lets start with the first one

Abstract Data Types: Information Hiding

Data types are called abstract if we don’t show its representation to the user. Since the representation is not part of the definition, we are free to choose whatever is easiest or most efficient to implement. ADT introduces one of the programming principles which is Information Hiding.Simply, we can say that our target now is to separate the programming tasks of implementation and usage.

Let’s see an example:

  • note: this example is copied from (Object Oriented Programming In C –Axel-Tobias Schreiner )  with some modifications.

Car.h

#ifndef CAR_H_
#define CAR_H_

extern const void* Car;

void* SetModel(void* p_car, char* p_modelName);
void* SetID(void* p_car, int p_modelID);
char* GetName(void* p_car);
int* GetID(void* p_car);

#endif /* CAR_H_ */

Car.c

#include "Car.h"
#include
#include
#include
#include "New.h"
struct Car
{
	char* m_ModelName;
	int   m_ModelID;
};

static const size_t _Car = sizeof(struct Car);

const void * Car = & _Car;

void * new (const void * type, ...)
{	const size_t size = * (const size_t *) type;
	void * p = calloc(1, size);

	assert(p);
	return p;
}

void delete (void * item)
{
	free(item);
}

void* SetModel(void* p_car, char* p_modelName)
{
	struct Car * c= p_car;
	c->m_ModelName = p_modelName;
	return c;
}

void* SetID(void* p_car, int p_modelID)
{
	struct Car * c= p_car;
		c->m_ModelID = p_modelID;
		return c;
}

char* GetName(void* p_car)
{
	struct Car* c = p_car;
	return c->m_ModelName;
}
int* GetID(void* p_car)
{
	struct Car* c = p_car;
	return (int)c->m_ModelID;
}

New.h

#ifndef NEW_H_
#define NEW_H_

void * new (const void * type, ...);
void delete (void * item);

#endif /* NEW_H_ */

Main.c

#include
#include "Car.h"
#include "New.h"
int main ()
{
	void *newCar = new(Car);

	if(SetModel(newCar,"PMW"))puts("YES!!!");
	char* name = GetName(newCar);
	puts(name);
	(GetName(newCar))?puts("YES!!!"):puts("NO!!!");
	delete(newCar);
	(GetName(newCar))?puts("YES!!!"):puts("NO!!!");
		return 0;
}

References

Maze Generation: Recursive Backtracker

This article is inspired by Jamis Buck’s presentation(Algorithm is not a 4-letter word). I’ve talked before about Maze Generation and its importance in acmASCIS blog, it’s great and interesting topic. In this post we’ll talk about a technique of generating a perfect maze, it’s Recursive Backtracking . Recursive backtracking is an algorithm for solving and generating perfect mazes. This algorithm is fast, easy to understand and straightforward to implement, but the maze is still biased(check Jamis Buck’s Presentation about Biased Maze Concept). Recursive backtracker performs a drunkard’s walk from the starting point by randomizing the visited child node at each level, but with some modifications on the drunkard’s walk ,as  it pushes each visited node onto a stack and when it reached a dead-end it pops the nodes off the stack until it finds one that it can continue walking from instead of doing O(n) Search. Algorithm Steps from Jamis Buck’s Blog:

  1. Choose a starting point in the field.
  2. Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
  3. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
  4. The algorithm ends when the process has backed all the way up to the starting point.

    you can check the animation introduced by Jamis Buck (here).

Implementation:

Here’s my Implementation in C#.

  1. publicoverridevoid GenerateMaze()
  2.         {
  3.             while (NumOfVisitedCells < TotalCells)
  4.             {
  5.                 ArrayList adjcentCells = this.GetNeighborsWithWalls(currentCell);
  6.                 if (adjcentCells.Count > 0)
  7.                 {
  8.                     int randomCell = Cell.theRandom.Next(0, adjcentCells.Count);
  9.                     Cell aCell = ((Cell)adjcentCells[randomCell]);
  10.                     currentCell.KnockDownWall(aCell);
  11.                     cellStack.Push(currentCell);
  12.                     currentCell = aCell;
  13.                     numOfVisitesCells++;
  14.                 }
  15.                 else
  16.                 {
  17.                     currentCell = (Cell)cellStack.Pop();
  18.                 }
  19.             }
  20.         }

you can try simple .exe file Maze Generation.exe.

Why Study Compiler Construction?

A compiler is a large, complex program. Compilers often include hundreds of thousands, if not millions of lines of code. Their many parts have complex interaction. Design decisions made for one part of the compiler have important ramifications for other parts. Thus, the design and implementation of a compiler is a substantial exercise in software engineering.
A good compiler contains a microcosm of Computer Science. We can see that in some examples:

  • Greedy Algorithms (Register Allocation)
  • Heuristic Search Techniques (List Scheduling)
  • Graph Algorithms (dead-code elimination)
  • Dynamic Programming (Instruction Selection)
  • Finite Automata and Push-Down Automata (Scanning and Parsing)
  • Fixed-Point Algorithms (Data-Flow Analysis)

It deals with problems such as dynamic allocation, synchronization, naming, locality, memory hierarchy management, and pipeline scheduling.
Compilers play a fundamental role in the central activity of Computer Science: preparing problems for solution by Computer. Most Software is compilers, the correctness of that process and the efficiency of the resulting code have a direct impact on our ability to build  large systems.

Speedy Overview:

The compiler community has been building compilers since 1955, over those years we have learned many lessons about how to structure a compiler, and nowadays we are dealing with a compiler as a black box that translates a source program into a target program.

The Front-End focuses on understanding the source-language program and the Back-End focuses on mapping the programs to the target machine. This separation of concerns has several important implications for the design and implementation of compilers.
This intermediate representation (IR) becomes the compiler’s definitive representation for the code it is translating. At each point in compilation, the compiler will have a definitive representation.

References:

Engineering A compiler – Keith D. Cooper & Linda Torczon.