Thread: Unknown Seg Fault and Malloc/Realloc Problems

In attempting to debug this program, I fear two things. 1) The debugger isn't telling me where my program is seg faulting, and 2) I don't know if I've done my allocations to my arrays correctly.

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;
       }
}

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?

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;
}

What about some sample data that causes the crash?

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)

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)

which corresponds to:

Code:

int **edge_matrix = (int **)malloc((number_of_points*(number_of_points-1)/2) * sizeof(int *));

The crash occurs here:

Code:

Program received signal SIGSEGV, Segmentation fault.
0x08048c6f in main () at wha.c:113
113                 edge_matrix[j][i] = combination[i];

, when j = 91 and i = 0:

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

So you're walking off the end of the first dimension of your edge_matrix array.