473,383 Members | 1,877 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,383 software developers and data experts.

Problems with mergesort for files

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 uk******@yahoo.co.uk
Nov 13 '05 #1
1 3359
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
Nov 13 '05 #2

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Andres Rosado-Sepulveda | last post by:
Hello, I'm having trouble compiling PHP 4.3.4 on Solaris 8. This is the error message it is showing: -- start -- Undefined first referenced symbol ...
1
by: Jochus | last post by:
Today, I've programmed Mergesort. And it works very good :-)! But now, the teacher said that you could use Mergesort to count the amount of inversions. This is what I found on the internet: ...
6
by: Jamal | last post by:
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...
1
by: ben81 | last post by:
Hi, the following code is adopted PseudoCode from Introduction to Algorithms (Cormen et al). For some reason it can't get it to work. I always get a index of out bounds exception or some weird...
2
by: rkk | last post by:
Hi, My mergesort program is below. There is a small piece of logical error/bug in this code which I can't figure out, as a result the output array isn't completely sorted. Requesting your help...
51
by: Joerg Schoen | last post by:
Hi folks! Everyone knows how to sort arrays (e. g. quicksort, heapsort etc.) For linked lists, mergesort is the typical choice. While I was looking for a optimized implementation of mergesort...
5
by: Chad | last post by:
I was looking at some old posts in comp.lang.c and found the following ...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
1
by: Sonnysonu | last post by:
This is the data of csv file 1 2 3 1 2 3 1 2 3 1 2 3 2 3 2 3 3 the lengths should be different i have to store the data by column-wise with in the specific length. suppose the i have to...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.