Problems with mergesort for files

Discussion in 'C Programming' started by Jamal, Jul 14, 2003.

  1. Jamal

    Jamal Guest

    I am working on binary files of struct ACTIONS

    I have a recursive qsort/mergesort hybrid that

    1) i'm not a 100% sure works correctly
    2) would like to convert to iteration

    Any comments or suggestion for improvements
    or conversion to iteration would be much appreciated

    /* MergeTest. c */

    #include <assert.h> /* C runtime assertions */
    #include <ctype.h> /* C classification macros*/
    #include <string.h> /* C-style string functions */
    #include <stdio.h> /* C stream I/O functions */
    #include <stdlib.h> /* C utility functions */
    #include <time.h> /* C time functions & types */
    #include <process.h> /* Process control functions*/
    #include <stdarg.h> /* variable arguments header*/
    /* ************************************************************************** */
    /* Customer Transactions Structures */
    /* ************************************************************************** */
    /* CUSTOMER CREATIONS */
    typedef struct _create_STR{ /****************************/
    char RecType ; /* Secondary key */
    char CustNo[6] ; /* Primary key */
    char Name[21] ; /* Customer name */
    char Address[61] ; /* Customer address */
    char Balance[10] ; /* Account balance */
    char Limit[8] ; /* Acc credit limit */
    }CREATE ; /****************************/
    /* CUSTOMER DELETIONS */
    typedef struct _delete_STR{ /****************************/
    char RecType ; /* Secondary key */
    char CustNo[6] ; /* Primary key */
    }DELETE ; /****************************/
    /* STOCK ISSUES\RECEIPTS */
    typedef struct _issue_STR{ /****************************/
    char RecType ; /* Secondary key */
    char CustNo[6] ; /* Primary key */
    char PartNo[7] ; /* Item part code */
    char Qty[5] ; /* Order quantity */
    }ISSUE ; /****************************/
    /* ACTIONS UNION */
    typedef union _action_union{ /****************************/
    CREATE Create_STR ; /* Creation data */
    DELETE Delete_STR ; /* Deletion data */
    ISSUE IssueR_STR ; /* Transaction data */
    }ACTION ; /****************************/
    /* RECORD TYPE CODES */
    typedef enum _record_type_enum{ /****************************/
    ISSUE_RECORD = 'I' /* Stock Issues */
    ,DELETE_RECORD = 'D' /* Customer Deletions */
    ,CREATE_RECORD = 'C' /* Customer Creations */
    ,RECEIPT_RECORD = 'R' /* Stock Receipts */
    ,UNKNOWN_RECORD = 'U' /* Unclassified Record */
    }REC_TYPE ; /****************************/
    #define ISSUE_SIZE sizeof( ISSUE ) /* Size of customer issue */
    #define RECEIPT_SIZE ISSUE_SIZE /* Size of customer receipt */
    #define DELETE_SIZE sizeof( DELETE ) /* Size of customer deletion*/
    #define CREATE_SIZE sizeof( CREATE ) /* Size of customer creation*/
    #define ACTION_SIZE sizeof( ACTION ) /* Size of Action union */
    #define IO_ERROR (size_t)0 /* Binary I/O error return */
    /******************************************************************************/
    /* OPTIONS FOR open_file() */
    typedef enum _open_option_enum{ /****************************/
    EXIT_ON_ERR = 0 /* Post (EXIT_FAILURE) to OS*/
    ,NO_ERR_EXIT /* Return NULL to caller */
    }OPEN_OPTION ; /****************************/
    #define IO_ERROR (size_t)0 /* Error Return for ZenApi binary I/O functions */

    void fatal_error( const char *s_ptr ) ;
    void trivial_error( const char *s_ptr ) ;
    long rec_count(FILE *fp, size_t size) ;
    typedef (*SORT_PROC)( const void* ,const void *); /* Function pointer type */
    int cmp( const ACTION *a_ptr, const ACTION *b_ptr ) ;
    void merge( FILE *fp_one, FILE *fp_two, FILE *fp_out, SORT_PROC cmp_proc ) ;
    void split( FILE *fp_in,FILE *fp_one,FILE *fp_two,SORT_PROC cmp_proc) ;
    void mergesort( FILE *fp_in, FILE *fp_out, SORT_PROC cmp_proc ) ;
    ACTION* alloc_action( long count ) ;
    void sort_records(FILE *fp_in, FILE *fp_out,SORT_PROC cmp_proc) ;
    size_t read_action(FILE *fp, ACTION *rec_ptr, size_t count) ;
    size_t write_action(FILE *fp, const ACTION *rec_ptr, size_t count) ;
    FILE* open_file(const char *filename, const char *mode, OPEN_OPTION flag ) ;

    FILE* open_file(const char *filename, const char *mode, OPEN_OPTION flag ){
    /* provides error checked call of fopen ****************************/
    FILE *retval = NULL ; /* Proc return value */
    assert( filename != NULL ) ; /* Should never be NULL */
    assert( mode != NULL ) ; /* Should never be NULL */
    retval = fopen( filename , mode ) ; /* Try to open file */
    if(!retval){ /* Fopen call sucessful ? */
    if( flag == NO_ERR_EXIT ){ /* No, is trivial error ? */
    trivial_error( filename ) ; /* Yes, return NULL */
    } /****************************/
    else{ /* No, treat as fatal error */
    fatal_error( filename ) ; /* Quit application */
    } /****************************/
    } /* All done time to return */
    return retval ; /* Return result of proc */
    }/* open_file */ /****************************/

    size_t write_action(FILE *fp, const ACTION *rec_ptr, size_t count){
    /* provides error checked binary output for ACTIONS****************************/
    #define REC_SIZE ACTION_SIZE /* Size of an ACTION union */
    size_t retval = 0 ; /* Hold Proc Return value */
    assert( fp != NULL ) ; /* Should never be NULL */
    assert( rec_ptr != NULL ) ; /* Should never be NULL */
    assert( count >= 1 ) ; /* Should be >= 1 */
    retval = fwrite( rec_ptr,REC_SIZE,count,fp ); /* Call proc via pointer */
    if( ( ferror(fp) ) || ( retval != count ) ){ /* Was Call Successfull ? */
    retval = IO_ERROR ; /* No, return Error value */
    } /****************************/
    return retval ; /* Return Result of Proc */
    }/* write_action */ /****************************/

    size_t read_action(FILE *fp, ACTION *rec_ptr, size_t count){
    /* provides error checked input via io_call ****************************/
    size_t retval = 0 ; /* Hold Proc Return value */
    assert( fp != NULL ) ; /* Should never be NULL */
    assert( rec_ptr != NULL ) ; /* Should never be NULL */
    assert( count >= 1 ) ; /* Should be >= 1 */
    retval = fread(rec_ptr,ACTION_SIZE,count,fp); /* Call proc via pointer */
    if( ( ferror(fp) ) || ( retval != count ) ){ /* Was Call Successfull ? */
    retval = IO_ERROR ; /* No, return Error value */
    } /****************************/
    return retval ; /* Return Result of Proc */
    }/* read_action */ /****************************/



    int cmp(const ACTION *a_ptr, const ACTION *b_ptr ){
    /* Ascending CustNum and descending RecType order ****************************/
    int retval ; /* Hold result of comparison*/
    assert( a_ptr != NULL ) ; /* Rec A Must Never be NULL */
    assert( b_ptr != NULL ) ; /* Rec B Must Never be NULL */
    retval = strcmp( a_ptr->Delete_STR.CustNo /* Compare Record A's CustNo*/
    ,b_ptr->Delete_STR.CustNo ) ; /* ... To Record B's CustNo */
    if( !retval ){ /* Do they share a CustNo ? */
    retval = ( b_ptr->Delete_STR.RecType /* Yes, Compare B's RecType */
    - a_ptr->Delete_STR.RecType ) ; /* ... To Rec A's RecType */
    } /****************************/
    return retval ; /* Return comparison result */
    }/*cmp*/ /****************************/


    void merge( FILE *fp_one, FILE *fp_two, FILE *fp_out, SORT_PROC cmp_proc ){
    /* Merges two sorted binary files using comp_proc ****************************/
    ACTION a_STR = { '0',"00000","","","",""}; /* Rec read from subfile_one*/
    ACTION b_STR = { '0',"00000","","","",""}; /* Rec read from subfile_two*/
    int difference = 0 ; /* Result of rec comparison */
    read_action( fp_one, &a_STR, 1) ; /* Read record from fp_one */
    read_action( fp_two, &b_STR, 1) ; /* Read record from fp_two */
    while( (!feof(fp_one)) && (!feof(fp_two)) ){ /* Any Records to process ? */
    difference = (*cmp_proc)(&a_STR,&b_STR); /* Compare with comp_proc */
    if( difference > 0 ){ /* Is a_STR > b_STR ? */
    write_action( fp_out, &a_STR, 1 ) ; /* Yes, Write a_STR to file */
    read_action( fp_one, &a_STR, 1 ) ; /* Read next rec from fp_one*/
    } /****************************/
    else{ /* No, a_STR is <= b_STR */
    write_action( fp_out,&b_STR, 1 ) ; /* Write b_STR to file */
    read_action( fp_two,&b_STR, 1 ) ; /* Read next rec from fp_two*/
    } /****************************/
    } /* Process remaining records*/
    while( !feof( fp_one ) ){ /* Any Records to process ? */
    write_action( fp_out,&a_STR, 1 ) ; /* Yes, Write a_STR to file */
    read_action( fp_one,&a_STR, 1 ) ; /* Read next rec from fp_one*/
    } /****************************/
    while( !feof( fp_two ) ){ /* Any Records to process ? */
    write_action( fp_out,&b_STR, 1 ) ; /* Yes, Write a_STR to file */
    read_action( fp_two,&b_STR, 1 ) ; /* Read next rec from fp_two*/
    } /****************************/
    rewind( fp_out ) ; /* Prepare OutFile for read */
    }/*Merge*/ /****************************/

    void split( FILE *fp_in,FILE *fp_one,FILE *fp_two,SORT_PROC cmp_proc){
    ACTION cmp_STR = { '0',"00000","","","",""}; /* Holds Rec from input file*/
    ACTION last_STR = { '0',"00000","","","",""}; /* Hold last record read */
    FILE* fp_split_1 = NULL ; /* Hold ordered top split */
    FILE* fp_split_2 = NULL ; /* Hold ordered bottom split*/
    assert( fp_in != NULL ) ; /* Must never be NULL */
    assert( fp_one != NULL ) ; /* Must never be NULL */
    assert( fp_two != NULL ) ; /* Must never be NULL */
    assert( cmp_proc != NULL ) ; /* Must never be NULL */
    read_action( fp_in, &cmp_STR,1 ) ; /* Read rec from Input file */
    fp_split_1 = tmpfile() ; /* Open file_1 for spliting */
    fp_split_2 = tmpfile() ; /* Open file_2 for spliting */
    if( (fp_split_1) && (fp_split_2) ){ /* Temp files opened ok ? */
    while( !feof( fp_in ) ){ /* Any Records to process ? */
    if((*cmp_proc)(&cmp_STR,&last_STR)>=0 ){/* Yes, is rec > last ? */
    write_action(fp_split_1,&cmp_STR,1);/* Yes, write to split_one */
    } /****************************/
    else{ /* No, cmp_STR <= last_STR */
    write_action(fp_split_2,&cmp_STR,1);/* Write to split_two */
    } /****************************/
    last_STR = cmp_STR ; /* Save value of last read */
    read_action( fp_in, &cmp_STR, 1 ) ; /* Read rec from Input file */
    } /****************************/
    rewind( fp_split_1 ) ; /* No, Seek to top of fp_one*/
    rewind( fp_split_2 ) ; /* Seek to top of fp_two */
    sort_records( fp_split_1,fp_one,cmp_proc); /* Sort split recursively */
    sort_records( fp_split_2,fp_two,cmp_proc); /* Sort split recursively */
    fclose( fp_split_1 ) ; /* Close temp split file */
    fclose( fp_split_2 ) ; /* Close temp split file */
    } /****************************/
    rewind( fp_one ) ; /* Rewind sorted split file */
    rewind( fp_two ) ; /* Rewind sorted split file */
    }/*split*/ /****************************/

    void mergesort( FILE *fp_in, FILE *fp_out, SORT_PROC cmp_proc ){
    /* recursive variant of mergesort algorithm ****************************/
    FILE *fp_one = NULL ; /* Top half of current split*/
    FILE *fp_two = NULL ; /* Bottom half of split */
    assert( fp_out != NULL ) ; /* Must never be NULL */
    assert( fp_in != NULL ) ; /* Must never be NULL */
    assert( cmp_proc != NULL ) ; /* Must never be NULL */
    fp_one = tmpfile() ; /* Open first subfile */
    fp_two = tmpfile() ; /* Open second subfile */
    if( ( fp_one != NULL ) && ( fp_two != NULL)){ /* Both files opened ok ? */
    split( fp_in, fp_one, fp_two, cmp_proc ); /* Yes, split input file */
    merge( fp_out, fp_one, fp_two, cmp_proc); /* Merge subfiles */
    fclose( fp_one ) ; /* Close bottom split file */
    fclose( fp_two ) ; /* Close top half split file*/
    } /****************************/
    rewind( fp_out ) ; /* Rewind output file */
    }/*mergesort*/ /****************************/

    ACTION* alloc_action( long count ){
    /* Allocate a list of count actions via malloc ****************************/
    assert( count > 0 ) ; /* Ensure malloc arg is ok */
    return (ACTION*) malloc(count * ACTION_SIZE); /* Delegate to malloc */
    }/*alloc_action*/ /****************************/

    void sort_records(FILE *fp_in, FILE *fp_out,SORT_PROC cmp_proc){
    /* QuickSorts File of records ****************************/
    ACTION *rec_ptr = NULL ; /* Hold start of list in mem*/
    long num = 0 ; /* Holds # of recs to sort */
    size_t ret = 0 ; /* Hold result of I/O calls */
    assert( fp_in != NULL ) ; /* Must never be null */
    assert( fp_out != NULL ) ; /* Must never be null */
    assert( cmp_proc != NULL ) ; /* Must never be null */
    num = rec_count( fp_in, ACTION_SIZE ) ; /* Count records in the file*/
    if( num > 0 ){ /* Was the file empty ? */
    rec_ptr = alloc_action( num ) ; /* No, Request list memory */
    if( rec_ptr == NULL ){ /* Was Request sucessful ? */
    mergesort( fp_in, fp_out, cmp_proc ); /* No, mergesort the file */
    } /****************************/
    else{ /* Yes, Request succeeded */
    ret = read_action(fp_in,rec_ptr,num); /* Read entire file into mem*/
    if( ret != IO_ERROR ){ /* Was Read Successful ? */
    qsort( rec_ptr /* Yes, qsort record array */
    ,num /* ... with "num" entries */
    ,ACTION_SIZE /* ... of size ACTION_SIZE */
    ,cmp_proc /* ... compare with cmp_proc*/
    ) ; /****************************/
    write_action(fp_out,rec_ptr,num); /* write array to file */
    } /****************************/
    free( rec_ptr ) ; /* release allocated storage*/
    } /****************************/
    fseek( fp_out, 0L, SEEK_SET ) ; /* rewind output file to top*/
    } /****************************/
    rewind( fp_in ) ; /* rewind input file to top */
    }/*Sort Records*/ /****************************/



    long rec_count(FILE *fp, size_t size){
    /* Returns number of blocks of size "size" in fp ****************************/
    long count = 0L ; /* Holds byte ofset from top*/
    fseek( fp, 0L, SEEK_END ) ; /* Seek to end of file */
    count = ftell( fp ) ; /* Save the number of bytes */
    rewind( fp ) ; /* Return to top of file */
    return ( count / size ) ; /* return number of blocks */
    }/*rec_count*/ /****************************/


    void fatal_error(const char *s_ptr){
    /* prints s_ptr then exits ****************************/
    assert( s_ptr != NULL ) ; /* Should never be NULL */
    trivial_error( s_ptr ) ; /* Delegate to trivial_error*/
    exit( EXIT_FAILURE ) ; /* Post failure message */
    }/*fatal_error*/ /****************************/

    void trivial_error( const char *s_ptr ){
    /* prints s_ptr then return ****************************/
    assert( s_ptr != NULL ) ; /* Should never be NULL */
    fprintf(stderr,"\n%Error : %s\n" ,s_ptr ) ; /* Print Error message */
    }/*trivial_error*/ /****************************/

    int main( void ){
    /* Application Entry point for MergeTest.c ****************************/
    #define IN_FILE "ZenVF.dat" /* DEFINE input file name */
    #define OUT_FILE "ZenSD.dat" /* Define Output File name*/
    FILE *fp_in = NULL ; /* Binary Input stream */
    FILE *fp_out = NULL ; /* Binary Output stream */
    fp_in = open_file(IN_FILE ,"rb",EXIT_ON_ERR); /* Open Input stream */
    fp_out = open_file(OUT_FILE,"wb",EXIT_ON_ERR); /* Open Output stream */
    mergesort( fp_in, fp_out, (SORT_PROC)cmp ) ; /* Sort Output file */
    fclose( fp_in ) ; /* Close opened stream */
    fclose( fp_out) ; /* Close opened stream */
    return( 0 ) ; /* Return value to OS */
    #undef IN_FILE /* This is no longer needed */
    #undef OUT_FILE /* This is no longer needed */
    }/*main*/ /****************************/

    Jamal Natour
     
    Jamal, Jul 14, 2003
    #1
    1. Advertising

  2. Jamal

    Jamal Guest

    Thanks for your suggestion, I have implemented the change after
    reading the FAQ answers,

    I have also placed a copy on http://www.geocities.com/uk_coder, this
    has
    comments stripped and should be more readable.

    Thanks again

    J
     
    Jamal, Jul 15, 2003
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jamal
    Replies:
    6
    Views:
    648
    Dann Corbit
    Jul 16, 2003
  2. ben81

    MergeSort

    ben81, Aug 9, 2006, in forum: Python
    Replies:
    1
    Views:
    503
    Steven D'Aprano
    Aug 10, 2006
  3. rkk

    mergesort - strange output

    rkk, Sep 30, 2006, in forum: C Programming
    Replies:
    2
    Views:
    376
    CBFalconer
    Oct 1, 2006
  4. Joerg Schoen

    Mergesort algorithm for linked lists

    Joerg Schoen, Jan 22, 2007, in forum: C Programming
    Replies:
    51
    Views:
    1,624
    Richard Harter
    Jan 30, 2007
  5. Joerg Schoen

    Mergesort algorithm for linked lists

    Joerg Schoen, Jan 26, 2007, in forum: C Programming
    Replies:
    0
    Views:
    642
    Joerg Schoen
    Jan 26, 2007
Loading...

Share This Page