SIGSEGV error on TSHPATH

[openfoot]

Hello everybody

I've got the problem that I always receive a SIGSEGV error when I submit my C code. On my machine the code is running fine. I tried to find out on ideone.com what could be the problem and I come up that it must be some analyse problem. However, I'm stick with the problem that I don't know where neither why the code fails... the big question is, how to get around it? Are there some tricks?

here the code that fails before compiling

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <string.h>
typedef struct {
	unsigned int cost;
	unsigned int index;
} vertec;
typedef struct {
	char name[11];
	unsigned int countVertec;
	vertec* vertecs;
	unsigned int cost;
} city;
#define swap_integer(a, b) a += b; \
b = a - b; \
a -= b;
/*heap[child].cost += heap[parent].cost;
heap[parent].cost = heap[child].cost - heap[parent].cost;
heap[child].cost -= heap[parent].cost;*/
vertec pop_heap(vertec* heap, unsigned int* length) {
	vertec ret = heap[0];
	(*length)--;
	//heapify the node down
	heap[0]=heap[*length];
	unsigned int parent = 0, child;
	while(parent < *length) {
		child = parent*2+1;
		//is there a left one?
		if(child >= *length)
			break;
		//is there a right one?
		if(child+1<*length) {
			//which is better the right or left one?
			if(heap[child+1].cost <  heap[child].cost)
				child = child+1;
		}
		//is the child smaller?
		if(heap[child].cost >= heap[parent].cost)
			break;
		//swap them
		swap_integer(heap[child].cost, heap[parent].cost)
		swap_integer(heap[child].index, heap[parent].index)
		parent = child;
	}
	return ret;
}
void push_heap(vertec* heap, unsigned int* length, unsigned int index, unsigned int cost) {
	heap[*length].index = index;
	heap[*length].cost = cost;
	unsigned int child = *length, parent;
	(*length)++;
	//heapify up
	while(child>0) {
		parent=floor((child-1)/2);
		//need to swap with parent?
		if(heap[child].cost >= heap[parent].cost)
			break;
		swap_integer(heap[child].cost, heap[parent].cost)
		swap_integer(heap[child].index, heap[parent].index)
		//reloop
		child=parent;
	}
}
int main() {
	unsigned int countTest;
	unsigned int i, a;
	vertec* heap = (vertec*)malloc(sizeof(vertec)*10000*10000);
	unsigned int heap_len;
	scanf("%u", &countTest);
	while(countTest--) {
		unsigned int countCity;
		scanf("%u", &countCity);
		city* cities = (city*)malloc(sizeof(city)*countCity);
		for(i=0;i<countCity;i++) {
			city* c = &(cities[i]);
			scanf("%s", c->name);
			scanf("%u", &(c->countVertec));
			c->vertecs = (vertec*)malloc(sizeof(vertec)*c->countVertec);
			for(a=0;a<c->countVertec;a++) {
				scanf("%u %u", &(c->vertecs[a].index), &(c->vertecs[a].cost));
				c->vertecs[a].index--;
			}
		}
		unsigned int countPath;
		scanf("%u", &countPath);
		while(countPath--) {
			char src[11], dst[11];
			scanf("%s %s", src, dst);
			unsigned int index;
			//reset the stuff
			for(i=0;i<countCity;i++) {
				cities[i].cost=UINT_MAX;
				if(strcmp(cities[i].name, src) == 0) {
					index = i;
				}
			}
			//start algorithm
			heap_len=0;
			push_heap(heap, &heap_len, index, 0);
			while(heap_len) {
				vertec vec = pop_heap(heap, &heap_len);
				city* c = &(cities[vec.index]);
				if(strcmp(c->name, dst)==0) {
					printf("%u\n", vec.cost);
					break;
				}
				for(a=0;a < c->countVertec;a++) {
					vertec v = c->vertecs[a];
					unsigned int newCost = v.cost + vec.cost;
					if(cities[v.index].cost > newCost) {
						cities[v.index].cost = newCost;
						push_heap(heap, &heap_len, v.index, newCost);
					}
				}
			}
			//end algorithm
		}
		//give memory free
		for(i=0;i<countCity;i++)
			free(cities[i].vertecs);
		free(cities);
		scanf("\n");
	}
	free(heap);
	return 0;
}

PS: Does spoj.pl really works with ideone in the background?

[leppyr64]

No SPOJ and ideone are not the same, but they are made by the same people and they run the same compilers. I suspect there is some crossover between the two.

You get SIGSEGV because you use up too much memory. Your vertec* heap is massive.

[openfoot]

Well, the system says that I'm using something around 2.8mb and there are people who use even much more memory than I do...
It seems breaking before. But I will give a try to dynamic allocation.

On ideone I had the impression that the compiler puts into the input stream random data for checking if the code is bulletproof

EDIT: I'm now increasing the heap in 100 steps - still the same problem

[leppyr64]

The surefire way to avoid SIGSEGV is to used fixed memory. As long as you know 100% that the amount of memory that you will use is within the limits, then you will have no issue.

On ideone I had the impression that the compiler puts into the input stream random data for checking if the code is bulletproof

I have no idea where you got this impression.

[openfoot]

The surefire way to avoid SIGSEGV is to used fixed memory. As long as you know 100% that the amount of memory that you will use is within the limits, then you will have no issue.

that's the reason why the heap was that big. And the code breaks already after some 100 milliseconds.

I've now reset the memory to a fixed length and remove the algorithm part -> Wrong Answer.
Looks like that I try to access data outside of the heap...
but this looks impossible to me in push_heap and pop_heap

On ideone I had the impression that the compiler puts into the input stream random data for checking if the code is bulletproof

I have no idea where you got this impression.

I did not set up any input and I get this error? I set up the error and I get the same error with no change of memory usage

PS: I'm using gcc 4.2.1 from apple

[leppyr64]

Please post your updated code.

[openfoot]

the changes are minimal

I actually only remove the alg part

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <string.h>
typedef struct {
	unsigned int cost;
	unsigned int index;
} vertec;
typedef struct {
	char name[11];
	unsigned int countVertec;
	vertec* vertecs;
	unsigned int cost;
} city;
#define swap_integer(a, b) a += b; \
b = a - b; \
a -= b;
/*heap[child].cost += heap[parent].cost;
heap[parent].cost = heap[child].cost - heap[parent].cost;
heap[child].cost -= heap[parent].cost;*/
vertec pop_heap(vertec* heap, unsigned int* length) {
	vertec ret = heap[0];
	(*length)--;
	//heapify the node down
	heap[0]=heap[*length];
	unsigned int parent = 0, child;
	while(parent < *length) {
		child = parent*2+1;
		//is there a left one?
		if(child >= *length)
			break;
		//is there a right one?
		if(child+1<*length) {
			//which is better the right or left one?
			if(heap[child+1].cost <  heap[child].cost)
				child = child+1;
		}
		//is the child smaller?
		if(heap[child].cost >= heap[parent].cost)
			break;
		//swap them
		swap_integer(heap[child].cost, heap[parent].cost)
		swap_integer(heap[child].index, heap[parent].index)
		parent = child;
	}
	return ret;
}
void push_heap(vertec* heap, unsigned int* length, unsigned int index, unsigned int cost) {
	heap[*length].index = index;
	heap[*length].cost = cost;
	unsigned int child = *length, parent;
	(*length)++;
	//heapify up
	while(child>0) {
		parent=floor((child-1)/2);
		//need to swap with parent?
		if(heap[child].cost >= heap[parent].cost)
			break;
		swap_integer(heap[child].cost, heap[parent].cost)
		swap_integer(heap[child].index, heap[parent].index)
		//reloop
		child=parent;
	}
}
int main() {
	unsigned int countTest;
	unsigned int i, a;
	vertec* heap = (vertec*)malloc(sizeof(vertec)*10000*10000);
	unsigned int heap_len;
	scanf("%u", &countTest);
	while(countTest--) {
		unsigned int countCity;
		scanf("%u", &countCity);
		city* cities = (city*)malloc(sizeof(city)*countCity);
		for(i=0;i<countCity;i++) {
			city* c = &(cities[i]);
			scanf("%s", c->name);
			scanf("%u", &(c->countVertec));
			c->vertecs = (vertec*)malloc(sizeof(vertec)*c->countVertec);
			for(a=0;a<c->countVertec;a++) {
				scanf("%u %u", &(c->vertecs[a].index), &(c->vertecs[a].cost));
				c->vertecs[a].index--;
			}
		}
		unsigned int countPath;
		scanf("%u", &countPath);
		while(countPath--) {
			char src[11], dst[11];
			scanf("%s %s", src, dst);
			unsigned int index;
			//reset the stuff
			for(i=0;i<countCity;i++) {
				cities[i].cost=UINT_MAX;
				if(strcmp(cities[i].name, src) == 0) {
					index = i;
				}
			}
		}
		//give memory free
		for(i=0;i<countCity;i++)
			free(cities[i].vertecs);
		free(cities);
		scanf("\n");
	}
	free(heap);
	return 0;
}

[leppyr64]

I haven't confirmed the reason for your SIGSEGV. I hold firm to the fact that you're pushing the limits with the size of your heap. The main idea behind using a heap is that you only require to push each node into a heap once. This allows you to use O(countCities) memory, as opposed to O(countCities^2).

Also note, if you update the cost of a city, and don't fix your heap, then you invalidate your heap order.

for(a=0;a < c->countVertec;a++) {
   vertec v = c->vertecs[a];
   unsigned int newCost = v.cost + vec.cost;
   if(cities[v.index].cost > newCost) {
	  cities[v.index].cost = newCost; // This breaks your heap.
	  push_heap(heap, &heap_len, v.index, newCost); // You should be updating the heap location of v.index instead.
   }
}

[openfoot]

Thanks a lot for your help.

But I'm kinda unhappy with the answer:

cities[v.index].cost = newCost; // This breaks your heap.

this cannot break the heap... cities is not the heap and index is untouched (only once adjusted to fit with c-arrays) and in is always the boundaries of the array cities

push_heap(heap, &heap_len, v.index, newCost); // You should be updating the heap location of v.index instead.

In this point I agree with you. But I've found a nice way to make it work without loosing perfomance. The problem is that index is not the location in the heap, it's the location in the array cities which is given by the input.

For updating/relaxing the heap I must find in the heap the vertec with the index city.index. This would lead me in the problem of running trough all elements in the heap O(N).

I could also store a second index in city which would hold the index in the heap. But this seems to me even uglier because the heap must swap that too.

I decided to take a simpler approach and just push the better path to heap. The heap will longer hold the bad solution but won't pick it before the shorter path and pop_heap will remove it once. And the heap should be big enough to hold all of them.

I think I've to sleep on it

[leppyr64]

Sorry. I misread your multiple uses of Vertec.

SIGSEGV is comminly caused by trying to read illegal memory or stack memory overflow. Have a good sleep.