Thread: segmentation fault on return

  1. #1
    Registered User
    Join Date
    May 2008
    Posts
    1

    segmentation fault on return

    Attached code produces segmentation fault when returning from the program. The program is a heap sort for quite strange data structure, and the sorting actually works (it crashes at the very end). The troublesome function obviously is swapElement function, as it is the only function which deals with memory. I am struggling with it for three days, so any help would be appreciated very much.

    Code:
    #include <stdlib.h>
    #include <stdio.h>
    #include <unistd.h>
    #include <string.h>
    #include <strings.h>
    
    #define QUEUE_MSGS 10
    #define MSG_LENGTH 160
    #define PRIORITY 8   
    
    typedef struct queue_struct {
        unsigned char message[QUEUE_MSGS][MSG_LENGTH];
    } queue_struct;
    
    void rand_fill(queue_struct* queue){
        int i;
        for (i = 0; i < QUEUE_MSGS; i++) {
            bzero(queue->message[i],MSG_LENGTH);
            queue->message[i][PRIORITY] = rand() % 127;
        }
    }
    
    void print_queue(queue_struct* queue){
        int i;
        for (i = 0; i < QUEUE_MSGS; i++) {
            printf("%i ",queue->message[i][PRIORITY]);
        }
    }
    
    void swapElement(queue_struct* queue,int first, int second){
            unsigned char temp[MSG_LENGTH];
            bzero(temp,MSG_LENGTH);
            printf("-----------------------------------\n");
            printf("---> swapping elements [%d:%d]\n",first, second);
            printf("---> with priorities %d %d\n",queue->message[first][PRIORITY],queue->message[second][PRIORITY]);
            printf("queue before swap: ");
            print_queue(queue);
            printf("\n");
            memcpy(temp,&queue->message[first],MSG_LENGTH);
            memcpy(&queue->message[first],&queue->message[second],MSG_LENGTH);
            memcpy(&queue->message[second],temp,MSG_LENGTH);
            printf("queue after swap: ");
            print_queue(queue);
            printf("\n");
    }
    
    void siftDown(queue_struct* queue, int root, int bottom) {
        int done, maxChild;
        done = 0;
        while ((root*2 <= bottom) && (!done)) {
            if (root*2 == bottom) {
                maxChild = root * 2;
            }
            else if (queue->message[root * 2][PRIORITY] < queue->message[root * 2 + 1][PRIORITY]) {
                maxChild = root * 2;
            }
            else {
                maxChild = root * 2 + 1;
            }
            if (queue->message[root][PRIORITY] > queue->message[maxChild][PRIORITY]) {
                swapElement(queue,root,maxChild);
                root = maxChild;
            }
            else
                done = 1;
        }
    }
    
    void heapSort(queue_struct* queue, int array_size) {
        int i;
        for (i = (array_size / 2)-1; i >= 0; i--){
            siftDown(queue, i, array_size);
        }
        for (i = array_size-1; i >= 1; i--) {
            swapElement(queue,0,i);
            siftDown(queue, 0, i-1);
        }
    }
    
    int main() {
        int bla;
        queue_struct queue;
        srand(getpid());
        
    
        for (bla = 0; bla < 100; bla++){
            rand_fill(&queue);
            heapSort(&queue,QUEUE_MSGS);
            printf("Iteration: %d\n",bla);
        }
        return(EXIT_SUCCESS);
    }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Crashing when you return is usually caused by overrunning some local array and thus overwriting the return address with rubbish.

    I'm not well versed enough in heap-sort to spot any particular problem. I am a bit worried about the code here:
    Code:
            if (root*2 == bottom) {
                maxChild = root * 2;
            }
    ...
            if (queue->message[root][PRIORITY] > queue->message[maxChild][PRIORITY]) {
                swapElement(queue,root,maxChild);
                root = maxChild;
            }
    root * 2 == bottom -> maxChild = bottom. With bottom == QUEUE_MSGS, you would be swapping queue[QUEUE_MSGS] with queue[root], and thus be operating 160 bytes beyond the allowed area.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. can some one please tell me the cause of the error ?
    By broli86 in forum C Programming
    Replies: 8
    Last Post: 06-26-2008, 08:36 PM
  2. 6 measly errors
    By beene in forum Game Programming
    Replies: 11
    Last Post: 11-14-2006, 11:06 AM
  3. DirectInput help
    By Muphin in forum Game Programming
    Replies: 2
    Last Post: 09-10-2005, 11:52 AM
  4. Pong is completed!!!
    By Shamino in forum Game Programming
    Replies: 11
    Last Post: 05-26-2005, 10:50 AM
  5. OpenGL Window
    By Morgul in forum Game Programming
    Replies: 1
    Last Post: 05-15-2005, 12:34 PM