Segmentation fault in destructor.

[writetonsharma]

I have written a code to traverse a matrix in circular fashion. The code is working fine and shows the output correctly. It's a template class. For all the data types it works fine but for char it crashes when i try to delete the memory(it shows the output correctly though). i am not able to figure out as everything looks fine. Dont know what i am missing. See the destructor of the class. please have a look..
The code is compiling.

//main.cpp
#include "matrix_cir_trv.h"

using namespace std;


int main(int argc, char *argv[])
{
	//runs fine for int
	cMatrixCirTrv<int>	matrix(3, cMatrixCirTrv<int>::ANTICLOCKWISE);

	//crashes in the destructor for char.
	cMatrixCirTrv<char>	matrix(3, cMatrixCirTrv<int>::ANTICLOCKWISE);

	matrix.MakeMatrix();
	matrix.PrintMatrix();


	return EXIT_SUCCESS;
}

[writetonsharma]

The code looks big, but looking at the whole code is not necessary i think. Constructor and destructor may give you an idea whats wrong.

//matrix_cir_trv.h
#ifndef __MATRIX_CIR_TRV_H__
#define __MATRIX_CIR_TRV_H__

#include <iostream>
#include <vector>
using namespace std;


template<typename _T>
class cMatrixCirTrv
{
private:

	//data
	class node
	{
	private:
		_T 	m_data;		//data
		bool	m_visited;	//is this index visited during traversing

	public:
		node(_T data = _T(0), bool visited = false) :
			m_data(data), m_visited(visited)
		{}

		~node()
		{}

		_T get_data()
		{
			return m_data;
		}
		void set_data(const _T data)
		{
			m_data = data;
		}
		bool get_visited()
		{
			return m_visited;
		}
		void set_visited(const bool visited)
		{
			m_visited = visited;
		}

	};

	node	**m_matrix;		//matrix which will be traversed
	int 	m_size;			//size of the matrix, it will be (size X size)
	int 	m_CurrRow;		//current row
	int 	m_CurrCol;		//current column

	//rotation in which to rotate, either clockwise(turn to righ everytime)
	//or anticlockwise(turn left everytime)
	int m_rotation;

	//which direction we are moving, it can be left, right, up or down
	int m_direction;


	//dont copy or assign
	cMatrixCirTrv(const cMatrixCirTrv&);
	cMatrixCirTrv& operator =(const cMatrixCirTrv&);


	//functions
	bool CanWeGoStraight(const int row, const int column);
	bool CanWeTurnAClockwise(const int row, const int column);
	bool CanWeTurnClockwise(const int row, const int column);

	void MoveStraight(int *row, int *column);
	void TurnAClockwise();
	void TurnClockwise();

	void PrintPosition();


protected:


public:

	cMatrixCirTrv(const int size = MIN_SIZE, const int rotation = DEF_ROTATION);
	~cMatrixCirTrv();


	//which side to rotate
	enum ROTATION
	{
		INVALID = 0,
		CLOCKWISE = 1,
  		ANTICLOCKWISE = 2,
    		DEF_ROTATION = CLOCKWISE,
	};

	//error code of the functions
	enum E_CODES
	{
		_SUCCESS = 0,
  		_ERROR = -1,
	};

	//size of the matrix
	enum SIZE
	{
		MIN_SIZE = 3,
  		MAX_SIZE = 15,
    		DEF_SIZE = 3,
	};

	//which side we are going in the matrix, left, right, up or down
	//left(column decreases), right(column increases), up(row decreases), down(row increases)
	//we can do any one of these, i.e if we are moving left then we are not moving right or up.
	//this is important as we should know which direction we are going in the matrix
	/**
		1	2	3
		4	5	6			up(row--)
		7	8	9	left(column--)	_|_ right(column++)
					 		 |
							down(row++)
	*/
	enum DIRECTION
	{
		LEFT = 1,
  		RIGHT = 2,
    		UP = 3,
      		DOWN = 4,
	};

	int MakeMatrix();
	void PrintMatrix();

};


template<typename _T>
cMatrixCirTrv<_T>::cMatrixCirTrv(const int size, const int rotation) :
		m_size(size),
		m_CurrRow(-1),
		m_CurrCol(-1),
		m_rotation(rotation),
		m_direction(LEFT)
{
	try
	{
		m_matrix = reinterpret_cast<node**>(new node[m_size]);
		for(int i = 0; i < m_size; i++)
		{
			*(m_matrix + i) = new node[m_size];
		}
	}
	catch(std::bad_alloc)
	{
		//oops!! needs to be handled.
		m_matrix = NULL;
	}
}

template<typename _T>
cMatrixCirTrv<_T>::~cMatrixCirTrv()
{

	if(m_matrix != NULL)
	{
		//free the memory
		int i;
		for(i = 0; i < m_size; i++)
		{
			//Crashes here for cMatrixCirTrv<char>
			delete [] *(m_matrix + i);
		}
		delete [] reinterpret_cast<node*>(m_matrix);

		m_size = 0;
		m_rotation = INVALID;
	}

}

template<typename _T>
int cMatrixCirTrv<_T>::MakeMatrix()
{

	cout << "Total elements to enter: " << (m_size * m_size) << endl;
	cout << "Enter row wise" << endl;

	_T temp;

	for(int i = 0; i < m_size; i++)
	{
		for(int j = 0; j < m_size; j++)
		{
			cout << "Enter[" << i << "," << j << "]: ";
			cin >> temp;
			(*(*(m_matrix + i) + j)).set_data(temp);
			(*(*(m_matrix + i) + j)).set_visited(false);
		}
	}

	cout << endl << endl << "You entered: " << endl;

	for(int i = 0; i < m_size; i++)
	{
		for(int j = 0; j < m_size; j++)
		{
			cout << (*(*(m_matrix + i) + j)).get_data() << "\t";
		}

		cout << endl;
	}

	return _SUCCESS;
}

template<typename _T>
void cMatrixCirTrv<_T>::PrintMatrix()
{
	if(m_size == 0)
		return;


	int middle = (m_size / 2);
	m_CurrRow = middle;
  	m_CurrCol = middle;
	m_direction = LEFT;	//in the begining we are moving in left direction
	int iteration = 0;


	cout << endl << endl << "Printing... " << endl;

	//print first element here and move straight
	if(CanWeGoStraight(m_CurrRow, m_CurrCol))
	{
		++iteration;
		PrintPosition();
		MoveStraight(&m_CurrRow, &m_CurrCol);
	}


	while(true)
	{
		if(m_rotation == ANTICLOCKWISE)
		{
			//first we try to move anti-clockwise everytime
			if(CanWeTurnAClockwise(m_CurrRow, m_CurrCol))
			{
				PrintPosition();
				TurnAClockwise();
				MoveStraight(&m_CurrRow, &m_CurrCol);

				if((++iteration % m_size) == 0)
					cout << endl;
				continue;
			}

			//we could not move anti-clockwise, try to move forward
			if(CanWeGoStraight(m_CurrRow, m_CurrCol))
			{
				PrintPosition();
				MoveStraight(&m_CurrRow, &m_CurrCol);

				if((++iteration % m_size) == 0)
					cout << endl;
				continue;
			}

			//we cannot turn as well as move straight, it means we are done
			//print the last one and enjoy the show!!!
			PrintPosition();

			if((++iteration % m_size) == 0)
				cout << endl;

			break;
		}
		else
		{

			//for clockwise move
		}
	}//while(true)

	return;
}


template<typename _T>
bool cMatrixCirTrv<_T>::CanWeGoStraight(const int row, const int column)
{
	bool retval = false;

	switch(m_direction)
	{
		case LEFT:
			if((column - 1) >= 0)
				retval = true;
			break;

		case RIGHT:
			if((column + 1) < m_size)
				retval = true;
			break;

		case UP:
			if((row - 1) >= 0)
				retval = true;
			break;

		case DOWN:
			if((row + 1) < m_size)
				retval = true;
			break;
	}

	return retval;
}


template<typename _T>
bool cMatrixCirTrv<_T>::CanWeTurnAClockwise(const int row, const int column)
{

/**
	1	2	3
	4	5	6			up
	7	8	9	left(column--)	_|_ right(column++)
						 |
					down(row++)

	up - (turning a-clockwise means we need to check (column-1) for validity
	and then we need to see if that is visited or not.
	so lets say we are at 5 and moving up, turning a-clockwise we need to see if we have visited 4 or not.
	again, if se are at 1 and moving up, turning a-clockwise is not possible as (column-1) is less then 0, not valid
	same for all the cases
 */


	//(*(*(m_matrix + row) + column)).get_visited()
	bool retval = false;


	switch(m_direction)
	{
		case LEFT:
			if((row + 1) < m_size)
				retval = !(*(*(m_matrix + row + 1) + column)).get_visited();
			break;

		case RIGHT:
			if((row - 1) >= 0)
				retval = !(*(*(m_matrix + row - 1) + column)).get_visited();
			break;

		case UP:
			if((column - 1) >= 0)
				retval = !(*(*(m_matrix + row) + column - 1)).get_visited();
			break;

		case DOWN:
			if((column + 1) < m_size)
				retval = !(*(*(m_matrix + row) + column + 1)).get_visited();
			break;
	}

	return retval;
}


template<typename _T>
bool cMatrixCirTrv<_T>::CanWeTurnClockwise(const int row, const int column)
{
	//not implemented for clockwise

}

template<typename _T>
void cMatrixCirTrv<_T>::MoveStraight(int *row, int *column)
{
	//direction will not change in moving straight
	//update the visited value

	switch(m_direction)
	{
		case LEFT:
			(*(*(m_matrix + *row) + *column)).set_visited(true);
			*column -= 1;
			break;

		case RIGHT:
			(*(*(m_matrix + *row) + *column)).set_visited(true);
			*column += 1;
			break;

		case UP:
			(*(*(m_matrix + *row) + *column)).set_visited(true);
			*row -= 1;
			break;

		case DOWN:
			(*(*(m_matrix + *row) + *column)).set_visited(true);
			*row += 1;
			break;
	}

}


template<typename _T>
void cMatrixCirTrv<_T>::TurnAClockwise()
{
	//direction will change and not the index.
	//turning means we will change the face and will not move.
	//move anti-clockwise is a combination of (TurnAClockwise + MoveStraight)


	switch(m_direction)
	{
		case LEFT:
			m_direction = DOWN;
			break;

		case RIGHT:
			m_direction = UP;
			break;

		case UP:
			m_direction = LEFT;
			break;

		case DOWN:
			m_direction = RIGHT;
			break;
	}

}

template<typename _T>
void cMatrixCirTrv<_T>::TurnClockwise()
{


}


template<typename _T>
void cMatrixCirTrv<_T>::PrintPosition()
{
	cout << (*(*(m_matrix + m_CurrRow) + m_CurrCol)).get_data() << "\t";
}


#endif 

[kbw]

The problem is the way matrix is allocated and freed. Keep it simple.

template<typename _T>
cMatrixCirTrv<_T>::cMatrixCirTrv(const int size, const int rotation)
	:	m_size(size),
		m_CurrRow(-1),
		m_CurrCol(-1),
		m_rotation(rotation),
		m_direction(LEFT)
{
	m_matrix = new node*[m_size];
	for(int i = 0; i < m_size; i++)
		m_matrix[i] = new node[m_size];
}

template<typename _T>
cMatrixCirTrv<_T>::~cMatrixCirTrv()
{
	if(m_matrix != NULL)
	{
		for(int i = 0; i < m_size; i++)
		{
			delete [] m_matrix[i];
		}
		delete [] m_matrix;
	}

}

A couple of comments. It would be easier to verify corectness if array indexing was as:

m_matrix[i][j]

You're mixing enums and ints. I think functions that expect an enum should be declared to do so, rather than using in.

[guestgulkan]

I was going to suggest a minor change to the matrx constructor as follows:

cMatrixCirTrv<_T>::cMatrixCirTrv(const int size, const int rotation) :
		m_size(size),
		m_CurrRow(-1),
		m_CurrCol(-1),
		m_rotation(rotation),
		m_direction(LEFT)
{
	try
	{
		m_matrix = reinterpret_cast<node**>(new node*[m_size]); //Notice how this has changed - compare to original
		for(int i = 0; i < m_size; i++)
		{
			*(m_matrix + i) = new node[m_size];
		}
	}
	catch(std::bad_alloc)
	{
		//oops!! needs to be handled.
		m_matrix = NULL;
	}
}

[Disch]

why are you doing reinterpret_cast<node**>?

new node*[foo] already returns node**. No need to cast (let alone reinterpret cast -- blech)

[writetonsharma]

Thanks alot guys.. my mistake.. you all are thinking on the same lines.. dont know why i couldn't..

kbw:

A couple of comments. It would be easier to verify correctness if array indexing was as:
m_matrix[i][j]

i feel more comfortable using pointer notation...thats why..

You're mixing enums and ints. I think functions that expect an enum should be declared to do so, rather than using in.

agreed... :)

guestgulkan:

yes.. and then i dont have to cast it.. :P

Disch:

I myself dont know why...might be most of the times i have used double pointers of primitive data types and had been using malloc..


but i think reinterprest_cast should also work.. its complex i admit.. but shouldnt it work???

Anyway thanks again for seeing the big code.. any suggestions will be helpful.. :)

[Disch]

i feel more comfortable using pointer notation...thats why..

methinks you're a little crazy. But then again aren't all programmers? ;D

but i think reinterprest_cast should also work.. its complex i admit.. but shouldnt it work???

Yes it will work. It's just "bad practice" (tm).

Unnecessary casts (especially C-style casts and reinterpret_cast) are bad because they silence the compiler. If you screw up somewhere and mistype something (say, for example, you accidentally put new node[foo] instead of new node*[foo]), your cast would shut the compiler up, and prevent it from catching this mistake for you. Causing you to waste hours sifting through your code to find out why your program is crashing.

So yeah. This particular cast is fine. There's nothing wrong with it. But you shouldn't get in the habit of explicitly casting everything. C++ is surprisingly smart when it comes to types and type conversions. Let the compiler do the obvious jobs. If you get warnings/errors then there's a high probability that your cast is just bad. Not always though -- sometimes you'll want to do something perfectly legit and the compiler might still bark at you. That is when you explicitly cast.

And even then -- reinterpret_cast should only be used when you need raw reinterpretation (which isn't often!). Stick to static_cast for most things. Much safer.

Anyway yeah. Shake this habit. Will save yourself some headaches in the future.

Plus, you know, extra typing is extra typing. Large, overly wordy, unweildly code is hard to read and maintain. KISS.

[writetonsharma]

Disch:

hahahahaha.... good one... but you havent seen some my craziest programs... :P
i agree on whatever you said..

anyway... i mostly dont use casts.. and reinterpret_cast.. never.. if you need casting, its time to recheck the code..
and if you remember on day i was myself saying that we should not use reinterpret_cast.. hehehehe...

the solution you people gave is the perfect one.. i should be using that only..
but as you said reinterpret_cast will work.. then why it aint working!!!??? i knew from the beginning that the segmentation fault i am getting is due to that casting thing.. but you know even if thats complicated, its correct.. why i am not able to delete the pointer??? and that too only char type template rest everything is working fine...???

lets say node dont have a constructor and i do this:

m_matrix = (node**)malloc(sizeof(node) * m_size);
for(int i = 0; i < m_size; i++)
{
	*(m_matrix + i) = (node*)malloc(sizeof(node) * m_size);
}

//....

for(i = 0; i < m_size; i++)
{
	free(*(m_matrix + i));
}
free(m_matrix);

will this work??? yes it will.. it wont fault when we do free(). so why not the previous one.

[jsmith]

No, it won't, unless sizeof(node) >= sizeof( node* ) because the amount of memory actually allocated will be less than what you needed.

EDIT: which is probably your original problem, since node would contain only a bool and a char, neither of which require special alignment, so sizeof( node ) == 2 in that case.

[writetonsharma]

aaah.. one reply.. i wasnt expecting any so marked the topic as solved... :P

i am not getting what you said smith but one...

why i will allocate node* and not node!! so you will agree that correct use of malloc will work fine for this code.
if you can elaborate on what ur trying to say..

[Disch]

I don't understand the compulsive switch to malloc/free here. You're creating problems for yourself.

malloc/free aren't typesafe and don't call ctors/dtors. In C++, malloc even require an explicit cast -- which will mask any problems caused by a bad/improper allocation (which is apparently your problem? To be honest I haven't really looked at the massive glob of code you posted, I've just been responding to the conversation that's come up afterwards)

Don't use malloc. Use new[] and don't cast it. Let C++ worry about the type conversions -- don't think you have to "outsmart it". If you do something wrong with new[], it will tell you in the form of a compiler error. Compiler errors are much easier to fix than runtime errors.

Your problem is that the compiler was giving you errors because your allocation was bad -- and you told it to "shut up" by reinterpret_cast'ing new. That doesn't solve the problem -- it just makes the problem harder to find.

kbw's first post in this thread hit the nail on the head. Keep it simple.

[jsmith]

This code:

m_matrix = reinterpret_cast<node**>(new node[m_size]);
for(int i = 0; i < m_size; i++)
{
    *(m_matrix + i) = new node[m_size];
}

basically says to allocate m_size node objects and return a pointer to the first one. (line 1)

But then the for loop says, no, the memory we just allocated is not for node objects; it is for pointers to node objects.

So line 1 essentially allocates m_size * sizeof( node ) bytes, but the remaining code requires that m_size * sizeof( node* ) bytes actually have been allocated. If sizeof( node ) < sizeof( node* ), then you have a memory stomp.