Sorting an array of structs in C

Question

We were given an assignment in class, to sort array of structs. After the assignment was handed in we discussed doing the sorting by using pointers of arrays to sort it as it was more efficient than the way most people had done it.

I decided to try and do it this way as well, however I'm running into some issues that I haven't been able to solve.

http://pastebin.com/Cs3y39yu

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/stat.h>

typedef struct stage2{//standard dec of the struct field
     char need;
         double ring;
         char fight[8];
         int32_t uncle;
         char game;
         double war;
         int8_t train;
         uint32_t beds;
         float crook;
         int32_t feast;
         int32_t rabbits;
         int32_t chin;
         int8_t ground;
         char veil;
         uint32_t flowers;
         int8_t adjustment;
         int16_t pets;
} stage2;

void usage(){//usage method to handle areas
        fprintf(stderr,"File not found\n");//prints to stderr
        exit(1);//exits the program
}

int needS(const void *v1, const void *v2)
{
    const stage2 *p1 = v1;
    const stage2 *p2 = v2;
        printf("%c %c \n",p1->need,p2->need);
    return 0;
}


int main(int argc, char** argv){
        if(argc != 3){//checks for a input files, only 1
          usage();//if not runs usage
  }
  int structSize = 60;//size of structs in bytes, sizeof() doesnt return correct val
  char* fileName = argv[1];  //pull input filename
  FILE *file = fopen(fileName, "r");//opens in read mode
  fseek(file, 0, SEEK_END);  //goes to end of file
  long fileSize = ftell(file);  //saves filesize
  char *vals = malloc(fileSize);  //allocates the correct size for array based on its filesize
  fseek(file, 0, SEEK_SET);  //returns to start of file
  fread(vals, 1, fileSize, file);  //reads the file into char array vals
  fclose(file); //closes file
  int structAmount = fileSize/structSize; //determines amount of structs we need
  stage2 mainArray[structAmount]; //makes array of structs correct size


  int j;//loop variables
  int i;


  printf("need, ring, fight, uncle, game, war, train, beds, crook, feast, rabbits, chin, ground, veil, flowers, adjustment, pets\n");//prints our struct names

  for(i = 0; i < structAmount; i ++){//initialises the array vals
        mainArray[i].need = *(&vals[0+(i*60)]);
        mainArray[i].ring = *((double *)&vals[1+(i*60)]);
        for(j = 0;j<9;j++){
          mainArray[i].fight[j] = *(&vals[j+9+(i*60)]);
        }
        mainArray[i].uncle = *((int32_t *)&vals[17+(i*60)]);
        mainArray[i].game = *(&vals[21+(i*60)]);
        mainArray[i].war = *((double *)&vals[22+(i*60)]);
        mainArray[i].train = *((int8_t *)&vals[30+(i*60)]);
        mainArray[i].beds = *((uint32_t *)&vals[31+(i*60)]);   
        mainArray[i].crook = *((float *)&vals[35+(i*60)]);
        mainArray[i].feast = *((int32_t *)&vals[39+(i*60)]);
        mainArray[i].rabbits = *((int32_t *)&vals[43+(i*60)]);
        mainArray[i].chin = *((int32_t *)&vals[47+(i*60)]);
        mainArray[i].ground = *((int8_t *)&vals[51+(i*60)]);
        mainArray[i].veil = *(&vals[52+(i*60)]);
        mainArray[i].flowers = *((uint32_t *)&vals[53+(i*60)]);
        mainArray[i].adjustment = *((int8_t *)&vals[57+(i*60)]);
        mainArray[i].pets = *((int16_t *)&vals[58+(i*60)]);    
  }

  for(i = 0; i < structAmount; i ++){//prints
        printf("%c, %f, %s, %d, %c, %f, %d, %u, %f, %d, %d, %d, %d, %c, %u, %d, %d \n",
        mainArray[i].need,mainArray[i].ring,mainArray[i].fight,mainArray[i].uncle,mainArray[i].game,mainArray[i].war,mainArray[i].train,
        mainArray[i].beds,mainArray[i].crook,mainArray[i].feast,mainArray[i].rabbits,mainArray[i].chin,mainArray[i].ground,mainArray[i].veil,
        mainArray[i].flowers,mainArray[i].adjustment,mainArray[i].pets);//prints

  }
  free(vals);//frees the memory we allocated to vals

  stage2 *array = malloc(structAmount * structSize);

  for(i = 0; i < structAmount; i ++){
        array[i] = mainArray[i];  
  }
  printf("Before Sort\n\n");  
  for(i = 0; i < structAmount; i ++){
          printf("%c, %f, %s, %d, %c, %f, %d, %u, %f, %d, %d, %d, %d, %c, %u, %d, %d \n",
  array[i].need,array[i].ring,array[i].fight,array[i].uncle,array[i].game,array[i].war,array[i].train,
  array[i].beds,array[i].crook,array[i].feast,array[i].rabbits,array[i].chin,array[i].ground,array[i].veil,
  array[i].flowers,array[i].adjustment,array[i].pets);//prints 
  }
  qsort(array, structAmount,structSize,needS);


  printf("After Sort\n\n");  
  for(i = 0; i < structAmount; i ++){
          printf("%c, %f, %s, %d, %c, %f, %d, %u, %f, %d, %d, %d, %d, %c, %u, %d, %d \n",
  array[i].need,array[i].ring,array[i].fight,array[i].uncle,array[i].game,array[i].war,array[i].train,
  array[i].beds,array[i].crook,array[i].feast,array[i].rabbits,array[i].chin,array[i].ground,array[i].veil,
  array[i].flowers,array[i].adjustment,array[i].pets);//prints 
  }

  FILE *my_file = fopen(argv[2], "wb");
  for(i = 0; i < structAmount; i ++){
          fwrite(&mainArray[i].need, sizeof(char), 1, my_file);
          fwrite(&mainArray[i].ring, sizeof(double), 1, my_file);
          fwrite(&mainArray[i].fight, sizeof(char[8]), 1, my_file);
          fwrite(&mainArray[i].uncle, sizeof(int32_t), 1, my_file);
          fwrite(&mainArray[i].game, sizeof(char), 1, my_file);
          fwrite(&mainArray[i].war, sizeof(double), 1, my_file);
          fwrite(&mainArray[i].train, sizeof(int8_t), 1, my_file);
          fwrite(&mainArray[i].beds, sizeof(uint32_t), 1, my_file);
          fwrite(&mainArray[i].crook, sizeof(float), 1, my_file);
          fwrite(&mainArray[i].feast, sizeof(int32_t), 1, my_file);
          fwrite(&mainArray[i].rabbits, sizeof(int32_t), 1, my_file);
          fwrite(&mainArray[i].chin, sizeof(int32_t), 1, my_file);
          fwrite(&mainArray[i].ground, sizeof(int8_t), 1, my_file);
          fwrite(&mainArray[i].veil, sizeof(char), 1, my_file);
          fwrite(&mainArray[i].flowers, sizeof(uint32_t), 1, my_file);
          fwrite(&mainArray[i].adjustment, sizeof(int8_t), 1, my_file);
          fwrite(&mainArray[i].pets, sizeof(int16_t), 1, my_file);
  }

  fclose(my_file);

  return 0;//return statement
}

There is the link to the code that I have been working on. My main issue is that from what I gather, when using the sorting comparison method needS (line 31) for the first execution of the sort it should return the first field for the first two structs in the array and print them (I am aware that this isn't a valid sorting method but wanted to make sure the variables were what I expected). However that's not what occurs; the p1 variable will print out what I expect however the p2 variable will not. From this point onwards, every use of this will return junk (I think) values.

Is there anything that I'm missing or doing wrong?

Answer 1

Your problem is in this line:

int structSize = 60;  //size of structs in bytes, sizeof() doesn't return correct val

You're wrong; sizeof() does return the correct size. Whatever you're doing is bogus. You need to go back to the basics of serialization. You will need to write the data correctly. You should be able to read all the data into the array in a single read operation. If you really have a 60 bytes per record in the input, you have serious issues.

Note that your structure layout in memory wastes 7 bytes on most systems (3 on some) between the char need; and double ring; elements. There's a similar gap between the char game; and double war;, and another gap (usually 3 bytes) between int8_t train; and uint32_t beds;, and another similar gap between (usually 2 bytes this time) between char veil; and uint32_t flowers; (because char veil; is preceded by int8_t ground;, and a gap of 1 between int8_t adjustment; and int16_t pets; — I won't guarantee that I've spotted all the gaps).

To learn more about structure layouts and padding, see Why isn't sizeof for a struct equal to the sum of sizeof of each member? as suggested by paddy.

To minimize the wasted space, the heuristic is to put the members with bigger base types before those with smaller base types. Thus all the double members should come before any of the char members. If a member is an array type, ignore the array and look at the size of the base type. For example, char fight[8]; is best put with the other char members at the end, though given that it is a multiple of 8 bytes, it could stay where it is — but it is simpler to be consistent. Pointers need to be treated as 8 bytes on 64-bit systems, or as 4 bytes on 32-bit systems. Place pointers between the non-pointer types such as long long or double (usually 8 bytes each) and the smaller non-pointer types such as int or uint32_t. The long type is a nuisance; it can be 4 or 8 bytes, depending (it's 4 bytes on Windows, even Windows 64-bit; it is 8 bytes on 64-bit Unix or 4 bytes on 32-but Unix).

Answer 2

The function needS needs to return a value that is appropriate for sorting the items in the array.

int needS(const void *v1, const void *v2)
{
    const stage2 *p1 = v1;
    const stage2 *p2 = v2;
    printf("%c %c \n",p1->need,p2->need);

    // Something like:
    return (p1->need < p2->need);
}

Answer 3

You have confused the "packed" structure size in your data file with the in-memory structure array that you allocate (by default, struct stage2 will have extra padding to align data types efficiently). This line here is the problem:

stage2 *array = malloc(structAmount * structSize);

It should be:

stage2 *array = malloc(structAmount * sizeof(stage2));

Your call to qsort needs to be updated accordingly too:

qsort(array, structAmount, sizeof(stage2), needS);

Answer 4

In addition to other posters' good answers about comparison functions and structure size, you also don't sort by pointers, which was your initial intention.

In your code, you sort a copy of the whole array of large structs. When sorting by pointer, you create an auxiliary array of pointers to the original array elements and then sort these pointers by way of the data they point to. This will leave the original array intact.

Your comparison function must then treat the void * pointers as pointers to pointers to your struct. Example (with heavily abridged structures) below.

#include <stdio.h>
#include <stdlib.h>

typedef struct stage2 {
    int need;
} stage2;

int needS(const void *v1, const void *v2)
{
    stage2 *const *p1 = v1;
    stage2 *const *p2 = v2;

    return ((*p1)->need - (*p2)->need) - ((*p2)->need - (*p1)->need);
}

int main(int argc, char **argv)
{
    stage2 mainArray[] = {
        {8}, {3}, {5}, {1}, {19}, {-2}, {8}, {0},{0}, {4}, {5}, {1}, {8}
    };
    int structAmount = sizeof(mainArray) / sizeof(*mainArray);

    int i;

    stage2 **array = malloc(structAmount * sizeof(*array));

    // Assign pointers
    for (i = 0; i < structAmount; i++) {
        array[i] = &mainArray[i];
    }

    qsort(array, structAmount, sizeof(*array), needS);

    puts("Original");
    for (i = 0; i < structAmount; i++) {
        printf("%d\n", mainArray[i].need);
    }

    puts("");
    puts("Sorted");
    for (i = 0; i < structAmount; i++) {
        printf("%d\n", array[i]->need);
    }

    free(array);

    return 0;
}