I am writing a program that sorts an array of either floats or doubles -- this is specified at compile time via a command to the compiler. I also must use void pointers. My program compiles, but when I try to run it with floats I get a "segmentation fault" and when i try to run it with doubles I get a "illegal instruction" error message. Any suggestions?? Thanks in advance for your help!!

Here is the main, heapSort file, and header file: (the program also contains files for insert, merge, and bubble which you will see in the main and header but I am only concerned with the heap sort file)

//header file

#ifndef SRT_H
#define SRT_H

#include <string.h>

#define MAX_BUF 256

#define swap(qx,qy,sz)                                              \
do {                                                                \
    char buf[MAX_BUF];                                              \
    char *q1 = qx;                                                  \
    char *q2 = qy;                                                  \
    for (size_t m, ms = sz; ms > 0; ms -= m, q1 += m, q2 += m) {    \
        m = ms < sizeof(buf) ? ms : sizeof(buf);                    \
        memcpy(buf, q1, m);                                         \
        memcpy(q1, q2, m);                                          \
        memcpy(q2, buf, m);                                         \
    }                                                               \
} while (0)

void srtbubb(void *, size_t, size_t, int (*)(const void *, const void *));
void srtheap(void *, size_t, size_t, int (*)(const void *, const void *));
void srtinsr(void *, size_t, size_t, int (*)(const void *, const void *));
void srtmerg(void *, size_t, size_t, int (*)(const void *, const void *));

#endif /* SRT_H */

//main
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include "srt.h"

int compare(const void *, const void *);

int main(int argc, char *argv[]) {

    int size = argc == 2 ? atoi(argv[1]) : SHRT_MAX;

    TYPE *a = calloc(size, sizeof(TYPE));

#ifdef RAND
    for (int i = 0; i < size; ++i) {

        a[i] = (TYPE)rand() / RAND_MAX;
    }
#else
    for (int i = 0; i < size; ++i) {

        a[i] = i;
    }
#endif

#if defined BUBB
    srtbubb(a, size, sizeof(TYPE), compare);
#elif defined HEAP
    srtheap(a, size, sizeof(TYPE), compare);
#elif defined INSR
    srtinsr(a, size, sizeof(TYPE), compare);
#elif defined MERG
    srtmerg(a, size, sizeof(TYPE), compare);
#else
    qsort(a, size, sizeof(TYPE), compare);
#endif

#ifdef PRNT
    for (int i = 0; i < size; ++i) {

        printf("%f\n", a[i]);
    }
#else
    for (int i = 0; i < size - 1; ++i) {

        if (a[i] > a[i + 1]) {

            printf("fail\n");
            goto end;
        }
    }

    printf("pass\n");
#endif

end:

    free(a);

    return 0;
}

int compare(const void *p1, const void *p2) {

    if (*(TYPE *)p1 < *(TYPE *)p2) {

        return -5;
    }
    else if (*(TYPE *)p1 > *(TYPE *)p2) {

        return +5;
    }

    return 0;
}

//heap sort file
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stddef.h>
#include "srt.h"

void heapify (void *, size_t, size_t);
void siftdown(void *, char *, char *, size_t, size_t);
void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *)) {
     
     heapify(base, nelem, size);    
     
     char *pEnd = (char *)base + ((nelem - 1) * size);
     
     while (pEnd > 0){
           swap(pEnd, base, size);
           pEnd -= size;
           siftdown(base, 0, pEnd, size, nelem);
           
     }
}

void heapify(void *pBase, size_t nelem, size_t size){
     
     char *pStart = (char *)pBase + (((nelem-2)/2) * size);     
     char *pEnd = (char *)pBase + ((nelem - 1) * size);
     
     while (pStart >= 0){
           pEnd -= size;
           siftdown(pBase, pStart, pEnd, size, nelem);
           pStart -= size;
     }
     return;
}

void siftdown(void *pBase, char * pStart, char * pEnd, size_t size, size_t nelem){

     char *pRoot;
     pRoot = pStart;
     size_t l = (nelem / 2);
     size_t r = (nelem - 1);
     
     while ((pRoot + (size * l)) <= pEnd){
           char *pChild;
           pChild = (pRoot + (size * l));
           if (((pChild + size) <= pEnd) && (pChild < (pChild + size)))
              pChild += size;
           if (pRoot < pChild){
              swap(pRoot, pChild, size);
              pRoot = pChild;
           }
           else
               return;
     }
     return;
}

Recommended Answers

All 7 Replies

Not surprised by your problem because the code you posted won't compile. You can't run a problem that is just full of crap.

Actually it does compile.

>Actually it does compile.
TYPE is never defined, which causes a relatively large number of errors regardless of which compiler one uses. You also rely on non-portable behavior that breaks two of my compilers (I suppose TYPE is also a compiler extension, since you claim the code compiles on your end), so please specify which compiler you use so that we can tailor our help to your unwarranted assumptions of portability.

I am using the gcc compiler with the following command:

gcc -std=c99 -DRAND -DPRNT -DTYPE=float, double -DHEAP *.c

I apoligize, the command i wrote is wrong this is the correct command I am using:

gcc -std=c99 -DRAND -DPRNT -DTYPE=float -DHEAP *.c

That makes more sense. In the future it would be nice to include those defines in the code, if only to make life easier for the people helping you.

Anyway, your algorithm is somewhat nonsensical. Let's start with these two lines:

while (pEnd > 0){
while (pStart >= 0){

I suspect what you meant was a pointer comparison with pBase and base, respectively. My recommendation is to verify all of your pointer manipulations, and switch over to array notation if you don't feel solid enough using pointers.

Thats my problem -- I dont feel solid with pointers but the assignment must be done using void pointers. I have totally revamped my code as follows:

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include "srt.h"


#define LEFT(x) ((x<<1) + 1)
#define RIGHT(x) ((x<< 1) +2)
#define PARENT(x) ((x-1) >> 1)

void srtheap(void *base, size_t nelem, size_t size, int (*compar)(const void *, const void *))
{
    void *p1;
    void *p2;
    void *last = base + (size*(nelem-1));
    int checkchild;
    int j;
    
    
    size_t index = nelem-1;
    
    for(int i = 0; i< nelem; ++i)
    {
            for(j = 0; j < index-1; i++)
            {
                     if(RIGHT(index) < nelem)
                     {
                        checkchild = 2;
                        p1 = last - size;
                        p2 = last;
                        
                        if(compar(LEFT(index),RIGHT(index) > 0)
                        {
                             p2 = base + ((index-j)*size);
                         
                             if(compar(p1,p2) > 0)
                             {
                                  swap(p1,p2,size);
                                                      
                             }
                        }
                        else if(compar(p1,p2) < 0)
                        {
                              p1 = base+ ((index-j)*size);

                            
                              if(compar(p2,p1) > 0)
                              {
                                  swap(p2, p1,size);
                              }
                        }
                     }
                     else if(LEFT(index) < nelem)
                     {
                          checkchild =1;
                          p1= last;
                          p2 = base+((index-j)*size);
                   
                          if(compar(p1,p2) > 0)
                          {
                               swap(p1,p2,size);
                          }               
                    }
                    switch(checkchild)
                    {
                         case 1:
                               last = base+(size*index);
                               break;
                         case 2:
                               last = base+size*(index-1);
                               break;
                   }
            }
    }
}

however, I am getting syntax errors at lines 33 and 53. AT line 33 there is apparently a syntax error before '{' and at 53 an error before else. There is also an error at line 74 before '}' .. I cant seem to find the issue with these errors, but I think it may have to do with the compar function.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.