Thread: Splitting a list in half with a recursive function, wont work

Hello guys!

I made a thread here a few days ago and got very good feedback. It helped alot but I have stumpled upon a new problem in the same program. This is quite much code (atleast for me, hehe), and I understand if you dont have time to look at it.

Anyway, the problem is that I have a list with a struct in each position. The struct contains four strings; artist, album, type and rating.

I need the user to be able to sort the list depending on one of these columns. For that I will use merge sort. This is the code for the list:

Code:

#ifndef _DLIST_H
#define _DLIST_H


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


#ifndef __DATA
#define __DATA
typedef void *data;
#endif


#ifndef __MEMFREEDATAFUNC
#define __MEMFREEDATAFUNC
typedef void memFreeFunc(data);
#endif


typedef struct link {
    data data;
    struct link *next;
} element;


typedef element * dlist_position;


struct list {
    element *head;
    memFreeFunc *freeFunc;
};
typedef struct list dlist;




dlist *dlist_empty(void);




void dlist_setMemHandler(dlist *l, memFreeFunc *f);


dlist_position dlist_first(dlist *l);


dlist_position dlist_next(dlist *l,dlist_position p);


bool dlist_isEmpty(dlist *l);


dlist_position dlist_insert(dlist *l,dlist_position p,data d);


dlist_position dlist_remove(dlist *l, dlist_position p);


void dlist_free(dlist *l);


data dlist_inspect(dlist *l, dlist_position p);


bool dlist_isEnd(dlist *l, dlist_position p);


#endif

Code:

#include "dlist.h"


dlist *dlist_empty(void) {
    dlist *theList=malloc(sizeof(struct list));
    theList->head=malloc(sizeof(element)); //huvudet för listan
    theList->head->next=NULL;
    theList->freeFunc=NULL;
    return theList;
}


void dlist_setMemHandler(dlist *l, memFreeFunc *f) {
   l->freeFunc=f;
}


dlist_position dlist_first(dlist *l) {
   return l->head;
}


dlist_position dlist_next(dlist *l, dlist_position p) {
   return p->next;
}


bool dlist_isEmpty(dlist *l) {
    return (l->head->next==NULL);
}


dlist_position dlist_insert(dlist *l,dlist_position p,data d) {
   dlist_position newPosition=malloc(sizeof(element));
   newPosition->data=d;
   
   newPosition->next=p->next;
   
   p->next=newPosition;
   return p;
}


data dlist_inspect(dlist *l, dlist_position p) {
    return p->next->data;
}


dlist_position dlist_remove(dlist *l,dlist_position p) {
   dlist_position temp=p->next;
   p->next=p->next->next;
   if(l->freeFunc!=NULL)
      l->freeFunc(temp->data);
   free(temp);
   return p;
}


bool dlist_isEnd(dlist *l,dlist_position p) {
   return (p->next==NULL);
}


void dlist_free(dlist *l) {
   dlist_position p=dlist_first(l);
   while(!dlist_isEmpty(l)) {
       p=dlist_remove(l,p);
   }
   free (l->head);
   free (l);    
}

And here is the code which gives me trouble:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
#include "dlist.h"
#define BUFSIZE 90


typedef struct {
        char artist[41];
        char album[41];
        char type[3];
        char rating[5];
} record;


void printMenu();
void readFile(FILE *infilep, dlist *list);
void printText(dlist *list);
dlist *mergeSort(dlist *list);
/*dlist *merge(dlist *list1, dlist *list2);*/


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


        int n;


        if(argc < 1) {
                fprintf(stderr, "Usage: %s <musik.txt>\n", argv[0]);
                exit(1);
        }


        /* Öppna filen */
        FILE * infilep;
        infilep = fopen(argv[1],"r");


        if (infilep == NULL) {
                fprintf(stderr, "Couldn't open input file.");
                exit(1);
        }


        /* Skapa listor och allokera minne */
        dlist *list=dlist_empty();


        /* Läs filen */
        readFile(infilep, list);


        /* Skriv ut meny */
        printMenu();

        do {


                printf("\n\n Ange ditt val: ");
                scanf("%d",&n);


                switch (n) {
                case -1: printf("Programmet avslutas\n\n"); return 0; break;
                case 0: printMenu(); break;
                case 1: printText(list); break;
                case 2: mergeSort(list); break;
//              case 3: merge(list1, list2); break;
                default: printf("Ogiltigt val\n"); printMenu(); break;
                }


        } while (n != -1);




        return 0;
}


/*
Funktion: printMenu
Beskrivning: Skriver ut menyn för programmet.
Input: -
Output: -
*/
void printMenu(void) {


        printf("\nMENY:\n");
        printf("0. Visa menyn\n");
        printf("1. Visa lista\n");
        printf("2. Sortera lista på artister\n");
        printf("3. Sortera lista på album\n");
        printf("4. Sortera lista på typ\n");
        printf("5. Sortera lista på betyg\n");
        printf("-1. Avsluta\n");


}


/*
Funktion: readFile
Beskrivning: Läser in data från filen.
Input: Datastukturen record och filpekaren infilep.
Output: -a
*/
void readFile(FILE *infilep, dlist *list) {


        char line[BUFSIZE];
        dlist_position pos;
        pos=dlist_first(list);


        /*Läs in information från musik.txt och spara
          structs i listan */
        while (fgets(line, BUFSIZE, infilep) != NULL) {
                record *info = malloc(sizeof(record));
                sscanf(line, "%[^;];%[^;];%[^;];%s",
                info->artist, info->album,
                info->type, info->rating);
                pos = dlist_insert(list,pos,info);
                pos = dlist_next(list,pos);
        }


}


/*
Funktion: printText
Beskrivning: Skriver ut artist, album, typ och betyg
i kolumner på skärmen. Man kan välja att visa mer text.
Input: Riktad lista
Output: Utskriven text
*/


void printText(dlist *list) {


        int n;
        dlist_position pos;
        pos = dlist_first(list);


        printf("\nAnge hur många rader du vill visa:");
        scanf("%d",&n);


        printf("\nARTIST                                  ALBUM                                   TYP


        /* Skriver ut det antal rader användaren bestämt */
        for(int i = 0; i < n; i++) {


                record *rcrd = (record*) dlist_inspect(list, pos);
                printf("%-40s%-40s%-2s %-4s\n", rcrd->artist, rcrd->album, rcrd->type, rcrd->rating);
                pos=dlist_next(list, pos);
                        if(dlist_isEnd(list, pos) == 1) {
                                printf("\n Listans slut.");
                                return;
                        }
        }


}


/*
Funktion: mergeSort
Beskrivning: Delar upp den ursprungliga listan i två delar, där vartannat värde hamnar
i lista1, och vartannat i lista 2. Funktionen anropar sig själv så att två till listor skapas,
och slutar först när listorna bara har en position. Då skickas listorna vidare till
funktionen merge.
Input: Riktad lista
Output: Halverade listor
*/
dlist *mergeSort(dlist *list) {


        dlist_position pos, pos1, pos2;


        /* Skapa två nya listor */
        dlist *list1 = dlist_empty();
        dlist *list2 = dlist_empty();


        /* Tag fram den första posititonen */
        pos = dlist_first(list);
        pos1 = dlist_first(list1);
        pos2 = dlist_first(list2);


        /* Allokera minne */
        record *rec = malloc(sizeof(record));


                /* Dela upp ursprungslistan i två nya listor */
                if(!dlist_isEnd(list, pos)) {


                        while(!dlist_isEmpty(list)) {


                                rec = (record*) dlist_inspect(list, pos);
                                dlist_remove(list, pos);
                                dlist_next(list, pos);


                                dlist_insert(list1, pos1, rec);
                                dlist_next(list1, pos1);


                                        if(!dlist_isEmpty(list)) {


                                                rec = (record*) dlist_inspect(list, pos);
                                                dlist_remove(list, pos);
                                                dlist_next(list, pos);


                                                dlist_insert(list2, pos2, rec);
                                                dlist_next(list2, pos2);


                                        }


                        }
                }
        /* Anropa mergeSort med de nya listorna */
        list1 = mergeSort(list1);
        list2 = mergeSort(list2);


        /* Anropa merge med listorna */
        merge(list1, list2);


        /* Returnera den sorterade listan */
        return(list);
}

The commenting is in swedish I'm afraid, but I hope you can get something out of it without the comments...

When I try to run the program it runs through the while-loop in mergeSort a few times but then I get a segmentation fault. I think it has to do with dlist_inspect trying to extract a struct when there is nothing to extract. But at the same time I thought I fixed that with the "!dlist_isEmpty(list)"...

Would love some help, if its possible.

Thanks