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
Similar Threads
