Thread: double free or corruption (fasttop)

I've never gotten an error like this before. Could someone tell me what it means?
I think the error is contained in the convertToPostfix function.

Code:

*** glibc detected *** ./a.out: double free or corruption (fasttop): 0x0804a008 ***
======= Backtrace: =========
/lib/tls/i686/cmov/libc.so.6[0xb7ea8a85]
/lib/tls/i686/cmov/libc.so.6(cfree+0x90)[0xb7eac4f0]
./a.out[0x80487a8]
./a.out[0x80486d5]
./a.out[0x804854c]
/lib/tls/i686/cmov/libc.so.6(__libc_start_main+0xe0)[0xb7e53450]
./a.out[0x8048491]
======= Memory map: ========
08048000-08049000 r-xp 00000000 08:11 133301     /home/eugene/cfiles/a.out
08049000-0804a000 rw-p 00000000 08:11 133301     /home/eugene/cfiles/a.out
0804a000-0806b000 rw-p 0804a000 00:00 0          [heap]
b7d00000-b7d21000 rw-p b7d00000 00:00 0 
b7d21000-b7e00000 ---p b7d21000 00:00 0 
b7e31000-b7e3b000 r-xp 00000000 08:11 414672     /lib/libgcc_s.so.1
b7e3b000-b7e3c000 rw-p 0000a000 08:11 414672     /lib/libgcc_s.so.1
b7e3c000-b7e3d000 rw-p b7e3c000 00:00 0 
b7e3d000-b7f86000 r-xp 00000000 08:11 422737     /lib/tls/i686/cmov/libc-2.7.so
b7f86000-b7f87000 r--p 00149000 08:11 422737     /lib/tls/i686/cmov/libc-2.7.so
b7f87000-b7f89000 rw-p 0014a000 08:11 422737     /lib/tls/i686/cmov/libc-2.7.so
b7f89000-b7f8c000 rw-p b7f89000 00:00 0 
b7f99000-b7f9b000 rw-p b7f99000 00:00 0 
b7f9b000-b7f9c000 r-xp b7f9b000 00:00 0          [vdso]
b7f9c000-b7fb6000 r-xp 00000000 08:11 414674     /lib/ld-2.7.so
b7fb6000-b7fb8000 rw-p 00019000 08:11 414674     /lib/ld-2.7.so
bf879000-bf88e000 rw-p bffeb000 00:00 0          [stack]
Aborted

Code:

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

struct stackNode {
	char data;
	struct stackNode *nextPtr;
};

typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;


void convertToPostfix( char infix[], char postfix[] );
//isOperator completed
int isOperator( char c );
//precedence completed
int precedence( char operator1, char operator2 );
//push completed
void push( StackNodePtr *topPtr, char value );
//pop completed
char pop( StackNodePtr *topPtr );
char stackTop( StackNodePtr topPtr );
int isEmpty( StackNodePtr topPtr );
void printStack( StackNodePtr topPtr );



int main()
{
	char iFix[ 10 ] = "(6 + 2)";
	char pFix[ 10 ] = { 0 };

	convertToPostfix( iFix, pFix );
	printf( "%s\n", pFix );


	return 0;
}




void convertToPostfix( char infix[], char postfix[] )
{
	StackNode *stack = NULL;
	char temp[ 2 ] = ")";
	push( &stack, '(' );

/*   APPENDS ")\0" to the end of infix  */
	strcat( infix, temp );


	while( !isEmpty( stack ) ) {


		if ( isdigit( *infix ) ) {
			*postfix = *infix;
			postfix += 2;
		}
		
		if ( *infix == '(' )
			push( &stack, *infix );

		if ( isOperator( *infix ) ) {
			if ( precedence( stackTop( stack ), *infix ) == 0 || precedence( stackTop( stack ), *infix ) == 1 ) {
				*postfix = pop( &stack );
				postfix += 2;
				push( &stack, *infix );
			}
			else
				push( &stack, *infix );
		}

		if ( *infix == ')' ) {
			while ( stackTop( stack ) != '(' ) {
				*postfix = pop( &stack );
				postfix += 2;
			}
			pop( &stack );
		}

		++infix;
	}

}



void printStack( StackNode *topPtr )
{
	while ( topPtr != NULL ) {
		printf( "%c", topPtr->data );
		topPtr = topPtr->nextPtr;
	}

	printf( "\n" );
}



int isEmpty( StackNode *topPtr )
{
	if ( topPtr == NULL )
		return 1;
	else
		return 0;
}



char pop( StackNode **topPtr )
{
	char output;
	StackNode *tempPtr = NULL;

	output = ( *topPtr )->data;
	tempPtr = *topPtr;
	*topPtr = ( *topPtr )->nextPtr;
	free( *topPtr );

	return output;	

}


char stackTop( StackNode *topPtr )
{
	if ( topPtr != NULL )
		return topPtr->data;
	else
		return ' ';

}


void push( StackNode **topPtr, char value )
{
	
	StackNode *newPtr = NULL;
	newPtr = malloc( sizeof( StackNode ) );
	
	if ( newPtr != NULL ) {
		newPtr->nextPtr = *topPtr;
		newPtr->data = value;

		*topPtr = newPtr;
	}
}


int isOperator( char c )
{
	if ( c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%' )
		return 1;

	else
		return 0;


}


//Determine if precedence of operator1 is greater(1), equal(0), or less then(-1) operator2
int precedence( char operator1, char operator2 )
{
	int opValue[ 2 ] = { 0 };
	char operator[ 2 ];
	operator[ 0 ] = operator1;
	operator[ 1 ] = operator2;
	int i = 0;

	for ( i = 0; i < 2; ++i ) {
		switch( operator[ i ] ) {
			case '+': case '-':
				opValue[ i ] = 1;
				break;
			case '*': case '/': case '%':
				opValue[ i ] = 2;
				break;
			case '^':
				opValue[ i ] = 3;
				break;
			case '(': case ')':
				opValue[ i ] = 4;
				break;
		}

	}



	if ( opValue[ 0 ] > opValue[ 1 ] )
		return 1;
	if ( opValue[ 0 ] == opValue[ 1 ] )
		return 0;
	else
		return -1;
}

It seems to me that in pop() you want to free tempPtr, not *topPtr.

The error means that your C library thinks you did a double free (that is, you freed the same thing twice, which is of course a bug) or that you corrupted its data structures, such as by writing beyond the end of a buffer you allocated.

>>cas

Thanks. How did you find the error so fast?

Originally Posted by yougene

>>cas

Thanks. How did you find the error so fast?

Based on glibc's message I figured I'd start by looking at where you call free(). There was only one such place so it was easy to know where to begin. The code you're using to pop follows a nice and standard pattern so I could quickly see where it went wrong.

I guess I have much more to learn

If you are running Linux, just run it through valgrind and it will let you know when it thinks you are doing something funny with memory (it can detect most memory errors, and is usually right).

http://valgrind.org/
http://valgrind.org/docs/manual/mc-m...mc-manual.bugs