Help, Needed, Having problems with mergesort for files implementation

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

    Applogies if earlier posting caused any confusion
    Jamal, Jul 14, 2003
    #1
    1. Advertising

  2. On 14 Jul 2003 11:38:50 -0700, (Jamal) wrote:

    >I am working on binary files of struct ACTIONS
    >

    snip 300+ lines

    Newsgroups are not chat rooms. You posted the same code two hours
    earlier. Give people a chance to respond. It sometimes takes days to
    get the answer you are looking for.


    <<Remove the del for email>>
    Barry Schwarz, Jul 15, 2003
    #2
    1. Advertising

  3. Jamal

    Jamal Guest

    Ok, once more appologies for the double source posting.

    a cleaned up version with offending comments stripped and suggestions
    applied is at http://www.geocities.com/uk_coder

    Thanks for the suggestion and links

    J
    Jamal, Jul 15, 2003
    #3
  4. (Jamal) wrote in
    news::

    > http://www.geocities.com/uk_coder


    You need to remember that browsers anything enclosed in < and > as tags,
    and silently ignore tags they do not recognize. Did you look at that page
    and notice anything odd?

    Sinan

    --
    A. Sinan Unur

    Remove dashes for address
    Spam bait: mailto:
    A. Sinan Unur, Jul 16, 2003
    #4
  5. On Tue, 15 Jul 2003, A. Sinan Unur wrote:
    >
    > (Jamal) wrote ...
    >
    > > http://www.geocities.com/uk_coder

    >
    > You need to remember that browsers anything enclosed in < and > as tags,
    > and silently ignore tags they do not recognize. Did you look at that page
    > and notice anything odd?


    Yeah ;
    I noticed all the punctuation
    was way out here .
    WTF ?
    I mean really ,
    come on .

    ;)
    To the OP: Look up &lt; and &gt; in your HTML FAQ to fix
    the #include problem.
    -Arthur
    Arthur J. O'Dwyer, Jul 16, 2003
    #5
  6. "Arthur J. O'Dwyer" <> wrote in
    news:p:

    >
    > On Tue, 15 Jul 2003, A. Sinan Unur wrote:
    >>
    >> (Jamal) wrote ...
    >>
    >> > http://www.geocities.com/uk_coder

    >>
    >> You need to remember that browsers anything enclosed in < and > as
    >> tags, and silently ignore tags they do not recognize. Did you look at
    >> that page and notice anything odd?

    >
    > Yeah ;
    > I noticed all the punctuation
    > was way out here .
    > WTF ?
    > I mean really ,
    > come on .
    >
    > ;)


    I agree. I keep thinking there is a missing semi-colon someplace. It is all
    very distracting.

    > To the OP: Look up &lt; and &gt; in your HTML FAQ to fix
    > the #include problem.


    or just copy your source.c to source_c.txt (in case your OS has problems
    with multiple dots in the filename) and post that. That way you do not have
    to deal with any of this stuff. The bare ampersands in the HTML cannot be
    good either even though they seem to display correctly in my browser. But
    the real travesty is:


    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 ;

    What's up with the commas?

    Now, I apologize to the OP for not focusing on his issues, but if you
    create so many obstacles that prevent me from being able to read and
    comprehend your code, I am not going to be able to think about your code.
    it takes less effort on your part to type:

    typedef enum tag_record_type_enum{
    STOCK_ISSUE = 'I',
    CUSTOMER_DELETION = 'D',
    CUSTOMER_CREATION = 'C',
    STOCK_RECEIPT = 'R',
    UNKNOWN = 'U',
    } RECORD_TYPE;

    1. You should not be using names that begin with an underscore (see
    http://www.lysator.liu.se/c/rat/d1.html#4-1-2-1).

    2. Since you ADT's name is RECORD_TYPE, it is unnecessary to append a
    useless RECORD at the end of each value. You can have more descriptive
    names using same or fewer number of characters.

    3. Hence you do not need the useless comments any more. In your scheme, the
    reader of your code has to keep refering back to the comments to remember
    if DELETE_RECORD refers to deletion of a customer or a stock issue.

    4. I have never seen any natural language where it is acceptable to start a
    line with punctuation. Doing this just creates another obstacle to
    comprehension.

    Other issues:

    Why do you define IO_ERROR multiple times in the same source. Since the
    values are the same, it is not a problem at this point, but why create a
    potential headache?

    Don't cast the return value of malloc.

    Have you compiled this code? After getting rid of the HTML, I get this:

    C:\Home\asu1>gcc -Wall -pedantic -c uk_coder.c
    uk_coder.c:63: warning: type defaults to `int' in declaration of
    `SORT_PROC'
    uk_coder.c: In function `merge':
    uk_coder.c:133: warning: missing braces around initializer
    uk_coder.c:133: warning: (near initialization for `a_STR.Create_STR')
    uk_coder.c:134: warning: missing braces around initializer
    uk_coder.c:134: warning: (near initialization for `b_STR.Create_STR')
    uk_coder.c: In function `split':
    uk_coder.c:161: warning: missing braces around initializer
    uk_coder.c:161: warning: (near initialization for `cmp_STR.Create_STR')
    uk_coder.c:162: warning: missing braces around initializer
    uk_coder.c:162: warning: (near initialization for `last_STR.Create_STR')
    uk_coder.c: In function `trivial_error':
    uk_coder.c:263: warning: double format, pointer arg (arg 3)
    uk_coder.c:263: warning: too few arguments for format

    By the way STR and/or is usually used to refer to strings. The suffix is
    very unnecessary and is cluttering the code.

    As for your original question: I am not sure if it works correctly either
    mostly because every time I tried to go through the code, I ended up giving
    up in frustration.

    --
    A. Sinan Unur

    Remove dashes for address
    Spam bait: mailto:
    A. Sinan Unur, Jul 16, 2003
    #6
  7. Jamal

    Dann Corbit Guest

    #include <assert.h>
    #include <ctype.h>
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <process.h>
    #include <stdarg.h>


    /* **************************************************************************
    */
    /* Customer Transactions Structures
    */
    /* **************************************************************************
    */
    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; /****************************/
    #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 */
    /******************************************************************************/
    /* 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; /****************************/

    void fatal_error(const char *s_ptr);
    void trivial_error(const char *s_ptr);
    size_t 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(size_t 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)
    {
    FILE *retval = NULL;
    assert(filename != NULL);
    assert(mode != NULL);
    retval = fopen(filename, mode);
    if (!retval) {
    if (flag == NO_ERR_EXIT) {
    trivial_error(filename);
    } else {
    fatal_error(filename);
    }
    }
    return retval;
    } /* open_file */

    size_t write_action(FILE * fp, const ACTION * rec_ptr, size_t
    count)
    {
    assert(fp != NULL);
    assert(rec_ptr != NULL);
    assert(count >= 1);
    return fwrite(rec_ptr, ACTION_SIZE, count, fp);
    } /* write_action */

    size_t read_action(FILE * fp, ACTION * rec_ptr, size_t count)
    {
    assert(fp != NULL);
    assert(rec_ptr != NULL);
    assert(count >= 1);
    return fread(rec_ptr, ACTION_SIZE, count, fp);
    } /* read_action */



    int cmp(const ACTION * a_ptr, const ACTION * b_ptr)
    {
    /* Ascending CustNum and descending RecType order*/
    int retval;
    assert(a_ptr != NULL);
    assert(b_ptr != NULL);
    retval = strcmp(a_ptr->Delete_STR.CustNo
    ,b_ptr->Delete_STR.CustNo);
    if (!retval) {
    retval = (b_ptr->Delete_STR.RecType
    - a_ptr->Delete_STR.RecType);
    }
    return retval;
    } /* cmp */


    void merge(FILE * fp_one, FILE * fp_two, FILE * fp_out,
    SORT_PROC cmp_proc)
    {
    ACTION a_STR = {'0', "00000", "", "", "", ""};
    ACTION b_STR = {'0', "00000", "", "", "", ""};
    size_t ret1 = 0;
    size_t ret2 = 0;
    if (!fseek(fp_one, 0L, SEEK_SET) && !fseek(fp_two, 0L, SEEK_SET))
    {
    ret1 = read_action(fp_one, &a_STR, 1);
    ret2 = read_action(fp_two, &b_STR, 1);
    while ((ret1 == 1) && (ret2 == 1)) {
    if ((*cmp_proc) (&a_STR, &b_STR) <= 0) {
    write_action(fp_out, &a_STR, 1);
    ret1 = read_action(fp_one, &a_STR, 1);
    } else {
    write_action(fp_out, &b_STR, 1);
    ret2 = read_action(fp_two, &b_STR, 1);
    }
    }
    while (ret1 == 1) {
    write_action(fp_out, &a_STR, 1);
    ret1 = read_action(fp_one, &a_STR, 1);
    }
    while (ret2 == 1) {
    write_action(fp_out, &b_STR, 1);
    ret2 = read_action(fp_two, &b_STR, 1);
    }
    }
    } /* Merge */

    void split(FILE * fp_in, FILE * fp_one, FILE * fp_two,
    SORT_PROC cmp_proc)
    {
    ACTION cmp_STR = {'0', "00000", "", "", "", ""};
    ACTION last_STR = {'0', "00000", "", "", "", ""};
    FILE *fp_split_1 = NULL;
    FILE *fp_split_2 = NULL;
    assert(fp_in != NULL);
    assert(fp_one != NULL);
    assert(fp_two != NULL);
    assert(cmp_proc != NULL);
    fp_split_1 = tmpfile();
    fp_split_2 = tmpfile();
    if ((fp_split_1) && (fp_split_2)) {;
    while (read_action(fp_in, &cmp_STR, 1) == 1) {
    if ((*cmp_proc) (&cmp_STR, &last_STR) >= 0) {
    write_action(fp_split_1, &cmp_STR, 1);
    } else {
    write_action(fp_split_2, &cmp_STR, 1);
    }
    last_STR = cmp_STR;
    }
    rewind(fp_split_1);
    rewind(fp_split_2);
    sort_records(fp_split_1, fp_one, cmp_proc);
    sort_records(fp_split_2, fp_two, cmp_proc);
    fclose(fp_split_1);
    fclose(fp_split_2);
    }
    rewind(fp_one);
    rewind(fp_two);
    } /* split */

    void mergesort(FILE * fp_in, FILE * fp_out, SORT_PROC
    cmp_proc)
    {
    FILE *fp_one = NULL;
    FILE *fp_two = NULL;
    assert(fp_out != NULL);
    assert(fp_in != NULL);
    assert(cmp_proc != NULL);
    fp_one = tmpfile();
    fp_two = tmpfile();
    if ((fp_one != NULL) && (fp_two != NULL)) {
    split(fp_in, fp_one, fp_two, cmp_proc);
    merge(fp_out, fp_one, fp_two, cmp_proc);
    fclose(fp_one);
    fclose(fp_two);
    };
    } /* mergesort */

    ACTION *alloc_action(size_t count)
    {
    assert(count > 0);
    return (ACTION *) malloc(count * ACTION_SIZE);
    } /* alloc_action */

    void sort_records(FILE * fp_in, FILE * fp_out, SORT_PROC
    cmp_proc)
    {
    /* QuickSorts File of records*/
    ACTION *rec_ptr = NULL;
    size_t num = 0;
    assert(fp_in != NULL);
    assert(fp_out != NULL);
    assert(cmp_proc != NULL);
    num = rec_count(fp_in, ACTION_SIZE);
    if (num > 0) {
    rec_ptr = alloc_action(num);
    if (rec_ptr == NULL) {
    mergesort(fp_in, fp_out, cmp_proc);
    } else {
    if (read_action(fp_in, rec_ptr, num) == num) {
    qsort(rec_ptr, num, ACTION_SIZE, cmp_proc);
    write_action(fp_out, rec_ptr, num);
    }
    free(rec_ptr);
    }
    }
    fseek(fp_out, 0L, SEEK_SET);
    } /* Sort Records */



    size_t rec_count(FILE * fp, size_t size)
    {
    size_t count = 0;
    size_t retval = 0;
    if (!fseek(fp, 0L, SEEK_END)) {;
    count = ftell(fp);
    if (!fseek(fp, 0L, SEEK_SET)) {
    retval = (count / size);
    }
    }
    return retval;
    } /* rec_count */


    void fatal_error(const char *s_ptr)
    {
    assert(s_ptr != NULL);
    trivial_error(s_ptr);
    exit(EXIT_FAILURE);
    } /* fatal_error */

    void trivial_error(const char *s_ptr)
    {
    assert(s_ptr != NULL);
    fprintf(stderr, "\n%Error : %s\n", s_ptr);
    } /* trivial_error */

    int main(void)
    {
    #define IN_FILE "a:\\ZENVF.dat" /* DEFINE input file name */
    #define OUT_FILE "a:\\ZENSD.dat" /* Define Output File name */
    FILE *fp_in = NULL;
    FILE *fp_out = NULL;
    fp_in = open_file(IN_FILE, "rb", EXIT_ON_ERR);
    fp_out = open_file(OUT_FILE, "wb+", EXIT_ON_ERR);
    mergesort(fp_in, fp_out, (SORT_PROC) cmp);
    fclose(fp_in);
    fclose(fp_out);
    return (0);
    #undef IN_FILE
    #undef OUT_FILE
    }
    /*

    --- Module: merg.c
    _
    ACTION a_STR = {'0', "00000", "", "", "", ""};
    merg.c(118) : Info 708: union initialization


    From ©ISO/IEC ISO/IEC 9899:1999 (E)
    126 Language §6.7.8
    17 Each brace-enclosed initializer list has an associated current
    object. When no designations are present, subobjects of the current
    object are initialized in order according to the type of the current
    object: array elements in increasing subscript order, structure
    members in declaration order, and the first named member of a
    union.127) In contrast, a designation causes the following initializer
    to begin initialization of the subobject described by the designator.
    Initialization then continues forward in order, beginning with the
    next subobject after that described by the designator.128)
    18 Each designator list begins its description with the current object
    associated with the closest surrounding brace pair. Each item in the
    designator list (in order) specifies a particular member of its
    current object and changes the current object for the next designator
    (if any) to be that member.129) The current object that results at the
    end of the designator list is the subobject to be initialized by the
    following initializer.
    19 The initialization shall occur in initializer list order, each
    initializer provided for a particular subobject overriding any
    previously listed initializer for the same subobject; all subobjects
    that are not initialized explicitly shall be initialized implicitly
    the same as objects that have static storage duration.
    20 If the aggregate or union contains elements or members that are
    aggregates or unions, these rules apply recursively to the
    subaggregates or contained unions. If the initializer of a
    subaggregate or contained union begins with a left brace, the
    initializers enclosed by that brace and its matching right brace
    initialize the elements or members of the subaggregate or the
    contained union. Otherwise, only enough initializers from the list are
    taken to account for the elements or members of the subaggregate or
    the first member of the contained union; any remaining initializers
    are left to initialize the next element or member of the aggregate of
    which the current subaggregate or contained union is a part.

    Footnotes:
    127) If the initializer list for a subaggregate or contained union
    does not begin with a left brace, its subobjects are initialized as
    usual, but the subaggregate or contained union does not become the
    current object: current objects are associated only with
    brace-enclosed initializer lists.
    128) After a union member is initialized, the next object is not the
    next member of the union; instead, it is the next subobject of an
    object containing the union.
    129) Thus, a designator can only specify a strict subobject of the
    aggregate or union that is associated with the surrounding brace pair.
    Note, too, that each separate designator list is independent.
    _
    ACTION b_STR = {'0', "00000", "", "", "", ""};
    merg.c(119) : Info 708: union initialization
    _
    write_action(fp_out, &a_STR, 1);
    merg.c(127) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    write_action(fp_out, &b_STR, 1);
    merg.c(130) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    write_action(fp_out, &a_STR, 1);
    merg.c(135) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    write_action(fp_out, &b_STR, 1);
    merg.c(139) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    ACTION cmp_STR = {'0', "00000", "", "", "", ""};
    merg.c(147) : Info 708: union initialization
    _
    ACTION last_STR = {'0', "00000", "", "", "", ""};
    merg.c(148) : Info 708: union initialization
    _
    write_action(fp_split_1, &cmp_STR, 1);
    merg.c(160) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    write_action(fp_split_2, &cmp_STR, 1);
    merg.c(162) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    write_action(fp_out, rec_ptr, num);
    merg.c(216) : Warning 534: Ignoring return value of
    write_action(struct _iobuf
    *, const union _action_union *, unsigned int) (compare with line
    87)
    _
    count = ftell(fp);
    merg.c(231) : Info 732: Loss of sign (assignment) (long to unsigned
    int)
    _
    fprintf(stderr, "\n%Error : %s\n", s_ptr);
    merg.c(250) : Warning 558: Too few arguments for format (1 missing)
    merg.c(250) : Warning 559: Size of argument no. 3 inconsistent with
    format

    Probably, what was meant here was this:
    fprintf(stderr, "\n%%Error : %s\n", s_ptr);


    --- Wrap-up for Module: merg.c

    Info 750: local macro ISSUE_SIZE (line 40, file merg.c) not referenced
    Info 750: local macro RECEIPT_SIZE (line 41, file merg.c) not
    referenced
    Info 750: local macro DELETE_SIZE (line 42, file merg.c) not
    referenced
    Info 750: local macro CREATE_SIZE (line 43, file merg.c) not
    referenced
    Info 754: local structure member _create_STR::RecType (line 15, file
    merg.c)
    not referenced
    Info 754: local structure member _create_STR::CustNo (line 16, file
    merg.c) not
    referenced
    Info 754: local structure member _create_STR::Name (line 17, file
    merg.c) not
    referenced
    Info 754: local structure member _create_STR::Address (line 18, file
    merg.c)
    not referenced
    Info 754: local structure member _create_STR::Balance (line 19, file
    merg.c)
    not referenced
    Info 754: local structure member _create_STR::Limit (line 20, file
    merg.c) not
    referenced
    Info 754: local structure member _issue_STR::RecType (line 29, file
    merg.c) not
    referenced
    Info 754: local structure member _issue_STR::CustNo (line 30, file
    merg.c) not
    referenced
    Info 754: local structure member _issue_STR::partNo (line 31, file
    merg.c) not
    referenced
    Info 754: local structure member _issue_STR::Qty (line 32, file
    merg.c) not
    referenced
    Info 754: local structure member _action_union::Create_STR (line 36,
    file
    merg.c) not referenced
    Info 754: local structure member _action_union::IssueR_STR (line 38,
    file
    merg.c) not referenced
    Info 766: Header file 'C:\lang\VC98\include\time.h' not used in module
    'merg.c'
    Info 766: Header file 'C:\lang\VC98\include\process.h' not used in
    module
    'merg.c'
    Info 766: Header file 'C:\lang\VC98\include\stdarg.h' not used in
    module
    'merg.c'
    */
    Dann Corbit, Jul 16, 2003
    #7
    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

    Problems with mergesort for files

    Jamal, Jul 14, 2003, in forum: C Programming
    Replies:
    1
    Views:
    452
    Jamal
    Jul 15, 2003
  2. ben81

    MergeSort

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

    mergesort - strange output

    rkk, Sep 30, 2006, in forum: C Programming
    Replies:
    2
    Views:
    359
    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,589
    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:
    631
    Joerg Schoen
    Jan 26, 2007
Loading...

Share This Page