|
12-01-2008, 09:27 AM
| #1 |
| Registered User Join Date: Nov 2008
Posts: 36
|  Unknown Seg Fault and Malloc/Realloc Problems So, if anyone wants to play "find the seg fault in the code stack," be my guest. I will be eternally grateful. And if anyone else would like to point out any errors in my use of malloc/realloc, I would be most obliged. Incidentally, "combination.h" just includes an iterator for moving through combinations of sets of data of a given size called "next_comb". Code: #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#include "combination.h"
float distance(int* x, int* y, int i, int j);
int choose(int x, int y);
int indexCompare(const void*, const void*);
main(){
int number_of_points, number_of_sides;
int i, j, k;
float avg_side_length, variation;
printf("How many points are to be considered?: ");
scanf("%d", &number_of_points);
while (number_of_points < 4){
printf("\nCannot generate polygons with the number of points given.\n\n");
printf("How many points are to be considered?: ");
scanf("%d", &number_of_points);
}
printf("How many sides should each polygon have?: ");
scanf("%d", &number_of_sides);
while ((number_of_sides < 2) || (number_of_sides > number_of_points)){
printf("\nCannot generate polygons with %d sides.\n\n", number_of_sides);
printf("How many sides should each polygon have?: ");
scanf("%d", &number_of_sides);
}
printf("What is the length of an average side?: ");
scanf("%f", &avg_side_length);
printf("How much variation (in terms of percent) are allowed?: ");
scanf("%f", &variation);
float var = (variation/100.0);
int x[number_of_points];
int y[number_of_points];
char vertex[number_of_points];
int edges = 0;
float length;
char edge_string[(number_of_sides*2)+1];
int polygons_found = 0;
int count = 0;
char edge_index_name[(number_of_points)*(number_of_points-1)/2][3];
int *combination = (int *)malloc(number_of_sides * sizeof(int));
int **edge_matrix = (int **)malloc((number_of_points*(number_of_points-1)/2) * sizeof(int *));
/* Label all vertices publicly */
for (i=0; i<number_of_points; i++){
if (i < 26)
vertex[i] = (i + 65);
else if ( (26 <= i) && (i < 52) )
vertex[i] = (i + 71);
else if ( (52 <= i) && (i < 67) )
vertex[i] = (i + 172);
else if ( (67 <= i) && (i < 71) )
vertex[i] = (i - 32);
else if ( (71 <= i) && (i < 81) )
vertex[i] = (i - 23);
else if ( (i == 81) )
vertex[i] = 64;
else
vertex[i] = (i + 46);
}
printf("\n\nFor each point, list the x- and y-coordiates as an ordered pair.\n[Ex., A(x,y): 2,4 ]\n");
for (i=0; i<number_of_points; i++){
printf("%c(x,y): ", vertex[i]);
scanf("%d,%d", &x[i], &y[i]);
}
printf("\n");
/* Count the number of edges for structure matrix */
for (i=0; i<number_of_points; i++){
for (j=i; j<number_of_points; j++){
length = distance(x, y, i, j);
if ( ((1.00 - var)*(avg_side_length) <= length) &&
(length <= (1.00 + var)*(avg_side_length)) ){
edge_index_name[edges][0] = vertex[i];
edge_index_name[edges][1] = vertex[j];
edge_index_name[edges][2] = '\0';
edges++;
}
}
}
if (edges == 0){
printf("No segments found within %f percent.\n", variation);
}
if ((edges < number_of_sides) && (edges != 0)){
printf("Not enough viable segments in graph.\n");
}
if (edges >= number_of_sides){
for (i=0; i<(number_of_points*(number_of_points-1)/2); i++){
edge_matrix[i] = (int *)malloc(number_of_sides * sizeof(int));
}
for (i=0; i<number_of_sides; i++){
combination[i] = i;
edge_matrix[0][i] = i;
}
j = 1;
while (next_comb(combination, number_of_sides, edges)){
for (i=0; i<number_of_sides; i++){
edge_matrix[j][i] = combination[i];
}
j++;
}
}
for (i=0; i<choose(edges, number_of_sides); i++){
for (j=0; j<number_of_sides; j++){
if (j == 0){
strncpy(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
if (j > 0){
strncat(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
}
qsort(edge_string, number_of_sides*2, sizeof(edge_string[0]), indexCompare);
for (k=0; k<(number_of_sides*2); k+=2){
if (edge_string[k] == edge_string[k+1]){
count++;
}
}
if (count == number_of_sides){
for (k=0; k<(number_of_sides*2); k+=2){
printf("%c",edge_string[k]);
polygons_found++;
}
printf("\n");
count = 0;
}
}
printf("\n%d %d-sided polygons found.", polygons_found, number_of_sides);
getch();
/* Endless loop for utilizing the same data set */
while (1){
printf("How many sides should each polygon have?: ");
scanf("%d", &number_of_sides);
while ((number_of_sides < 2) || (number_of_sides > number_of_points)){
printf("\nCannot generate polygons with %d sides.\n\n", number_of_sides);
printf("How many sides should each polygon have?: ");
scanf("%d", &number_of_sides);
}
printf("What is the length of an average side?: ");
scanf("%f", &avg_side_length);
printf("How much variation (in terms of percent) are allowed?: ");
scanf("%f", &variation);
var = (variation/100.0);
polygons_found = 0;
edges = 0;
count = 0;
combination = (int *)realloc((char *)combination, number_of_sides * sizeof(int));
printf("\n");
/* Count the number of edges for structure matrix */
for (i=0; i<number_of_points; i++){
for (j=i; j<number_of_points; j++){
length = distance(x, y, i, j);
if ( ((1.00 - var)*(avg_side_length) <= length) &&
(length <= (1.00 + var)*(avg_side_length)) ){
edge_index_name[edges][0] = vertex[i];
edge_index_name[edges][1] = vertex[j];
edge_index_name[edges][2] = '\0';
edges++;
}
}
}
if (edges == 0){
printf("No segments found within %f percent.\n", variation);
}
if ((edges < number_of_sides) && (edges != 0)){
printf("Not enough viable segments in graph.\n");
}
if (edges >= number_of_sides){
for (i=0; i<(number_of_points*(number_of_points-1)/2); i++){
edge_matrix[i] = (int *)realloc((char *)edge_matrix[i], number_of_sides * sizeof(int));
}
for (i=0; i<number_of_sides; i++){
combination[i] = i;
edge_matrix[0][i] = i;
}
j = 1;
while (next_comb(combination, number_of_sides, edges)){
for (i=0; i<number_of_sides; i++){
edge_matrix[j][i] = combination[i];
}
j++;
}
}
for (i=0; i<choose(edges, number_of_sides); i++){
for (j=0; j<number_of_sides; j++){
if (j == 0){
strncpy(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
if (j > 0){
strncat(edge_string, edge_index_name[edge_matrix[i][j]],2);
}
}
qsort(edge_string, number_of_sides*2, sizeof(edge_string[0]), indexCompare);
for (k=0; k<(number_of_sides*2); k+=2){
if (edge_string[k] == edge_string[k+1]){
count++;
}
}
if (count == number_of_sides){
for (k=0; k<(number_of_sides*2); k+=2){
printf("%c",edge_string[k]);
polygons_found++;
}
printf("\n");
count = 0;
}
}
printf("\n%d %d-sided polygons found.", polygons_found, number_of_sides);
getch();
}
}
float distance(int* x, int* y, int i, int j){
return ( sqrt( pow((y[i] - y[j]),2) + pow((x[i] - x[j]),2) ) );
}
int choose(int x, int y){
if (x < y){
return 0;
}
int i;
int term1 = 1;
int term2 = 1;
int term3 = 1;
for (i=1; i<=x; i++){
term1 *= i;
}
for (i=1; i<=y; i++){
term2 *= i;
}
for (i=1; i<=(x-y); i++){
term3 *= i;
}
return (term1/(term2*term3));
}
int indexCompare(const void* element1, const void* element2){
if (*(const char*)element1 > *(const char*)element2){
return 1;
}
if (*(const char*)element1 == *(const char*)element2){
return 0;
}
if (*(const char*)element1 < *(const char*)element2){
return -1;
}
}
|
| DonFord81 is offline |  |
|
12-01-2008, 09:57 AM
| #2 |
| Registered User  Join Date: Jan 2008 Location: Seattle
Posts: 476
| In a quick test I could not get a seg fault. I had to remove your next_comb function to compile; though, so you may have something in there that is causing your grief. If you supply your combination.h file that may help. I would recommend putting some "break" points in your program to stop at certain key points and check how far along are you getting before the segfault. That would lead you in the right direction a bit. Seeing conio.h you must be trying to compile this on a Window platform? |
| slingerland3g is offline | |
|
12-01-2008, 10:16 AM
| #3 |
| Registered User Join Date: Nov 2008
Posts: 36
| Okay, here's "combination.h". And, yes, this is on a Windows platform, using Bloodshed. Code: /* Prints out a combination like {1, 2} */
void printc(int comb[], int k) {
printf("{");
int i;
for (i = 0; i < k; ++i)
printf("%d, ", comb[i] + 1);
printf("\b\b}\n");
}
/*
next_comb(int comb[], int k, int n)
Generates the next combination of n elements as k after comb
comb => the previous combination ( use (0, 1, 2, ..., k) for first)
k => the size of the subsets to generate
n => the size of the original set
Returns: 1 if a valid combination was found
0, otherwise
*/
int next_comb(int comb[], int k, int n) {
int i = k - 1;
++comb[i];
while ((i >= 0) && (comb[i] >= n - k + 1 + i)) {
--i;
++comb[i];
}
if (comb[0] > n - k) /* Combination (n-k, n-k+1, ..., n) reached */
return 0; /* No more combinations can be generated */
/* comb now looks like (..., x, n, n, n, ..., n).
Turn it into (..., x, x + 1, x + 2, ...) */
for (i = i + 1; i < k; ++i)
comb[i] = comb[i - 1] + 1;
return 1;
}
|
| DonFord81 is offline | |
|
12-01-2008, 10:28 AM
| #4 |
| and the Hat of Ass Join Date: Dec 2007
Posts: 730
| What about some sample data that causes the crash? |
| rags_to_riches is offline | |
|
12-01-2008, 10:38 AM
| #5 |
| Registered User Join Date: Nov 2008
Posts: 36
| Sample data: Number of Points: 14 Number of Sides: 4 Average Side Length: 110.0716361 Variance: 15 A (45, 99) B (132, 85) C (252, 36) D (85, 188) E (173, 157) F (285, 108) G (36, 237) H (165, 229) I (261, 180) J (101, 294) K (173, 301) L (260, 245) M (253, 341) N (116, 429) |
| DonFord81 is offline | |
|
12-01-2008, 10:50 AM
| #6 |
| and the Hat of Ass Join Date: Dec 2007
Posts: 730
| Run on Linux, valgrind shows: Code: ==27887== Invalid read of size 4 ==27887== at 0x8048C5A: main (wha.c:113) ==27887== Address 0x41811d4 is 0 bytes after a block of size 364 alloc'd ==27887== at 0x40218B8: malloc (vg_replace_malloc.c:207) ==27887== by 0x804895B: main (wha.c:55) Code: int **edge_matrix = (int **)malloc((number_of_points*(number_of_points-1)/2) * sizeof(int *)); Code: Program received signal SIGSEGV, Segmentation fault. 0x08048c6f in main () at wha.c:113 113 edge_matrix[j][i] = combination[i]; Code: (gdb) p i $1 = 0 (gdb) p j $2 = 91 (gdb) p edge_matrix $3 = (int **) 0x804b020 (gdb) p combination[i] $4 = 2 (gdb) p number_of_points $7 = 14 (gdb) p (number_of_points*(number_of_points - 1)/2) $8 = 91 |
| rags_to_riches is offline | |
|
12-01-2008, 11:49 PM
| #7 |
| Algorithm Dissector  Join Date: Dec 2005 Location: New Zealand
Posts: 2,476
| DonFord81, make sure you actually investigate how to track down such issues yourself also, and ask furthur questions about how rags_to_riches arrived at the fault etc if necessary. Unless you quit programming and never program again, you're going to need to solve a similiar issue again before too long, and next time it might be even harder because you might not have written the code yourself. Afterall "Give a man a fish and he'll eat for a day, teach a man to fish and he'll have food for life".
__________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger |
| iMalc is offline | |
 |
| Tags |
| array, malloc, realloc, seg fault, segmentation fault |
| Thread Tools | |
| Display Modes | |
|
Linear Mode
