Unknown Seg Fault and Malloc/Realloc Problems

This is a discussion on Unknown Seg Fault and Malloc/Realloc Problems within the C Programming forums, part of the General Programming Boards category; In attempting to debug this program, I fear two things. 1) The debugger isn't telling me where my program is ...

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    38

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

  2. #2
    Registered User slingerland3g's Avatar
    Join Date
    Jan 2008
    Location
    Seattle
    Posts
    602
    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?

  3. #3
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    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;
    }

  4. #4
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,648
    What about some sample data that causes the crash?

  5. #5
    Registered User
    Join Date
    Nov 2008
    Posts
    38
    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)

  6. #6
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,648
    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.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    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

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21