#
#include <sys/param.h>
#include <sys/types.h>
#include <unistd.h>
// ------//
// main() implements master process //
// ------//
int
main( int argc, char **argv )
{
extern void do_merger( int, int );
extern void setup_for_read( int * );
extern void setup_for_write( int * );
extern void interleave_streams( int, int, int );
int merger1_pipe_fd[ 2 ];
int merger2_pipe_fd[ 2 ];
pipe( merger1_pipe_fd );
pipe( merger2_pipe_fd );
if( ! fork() )
{
// ------//
// parent master will read from merger1; in //
// child merger1, set up to write to master //
// ------//
do_merger( 1, merger1_pipe_fd[ 1 ] );
// ------//
// avoid falling through to yet another //
// invocation of interleave_streams() //
// ------//
exit( 0 );
}
if( ! fork() )
{
// ------//
// parent master will read from merger2; in //
// child merger2, set up to write to master //
// ------//
do_merger( 2, merger2_pipe_fd[ 1 ] );
// ------//
// avoid falling through to yet another //
// invocation of interleave_streams() //
// ------//
exit( 0 );
}
interleave_streams( merger1_pipe_fd[ 0 ], merger2_pipe_fd[ 0 ], 1 );
}
void
do_merger( int which_pair, int write_to )
{
extern void do_sorter( int, int );
extern void setup_for_read( int * );
extern void setup_for_write( int * );
extern void interleave_streams( int, int, int );
int sorter1_pipe_fd[ 2 ];
int sorter2_pipe_fd[ 2 ];
pipe( sorter1_pipe_fd );
pipe( sorter2_pipe_fd );
if( ! fork() )
{
// ------//
// parent merger, set up to read from sorter 1 //
// ------//
}
else
{
// ------//
// child sorter1, set up to write to merger: //
// merger1 will invoke do_sorter() with arg 1; //
// merger2 will invoke do_sorter() with arg 2 //
// ------//
do_sorter( 2 * which_pair - 1, sorter1_pipe_fd[ 1 ] );
// ------//
// avoid falling through to yet another //
// invocation of interleave_streams() //
// ------//
exit( 0 );
}
if( fork() )
{
// ------//
// parent merger, set up to read from sorter 2 //
// ------//
}
else
{
// ------//
// child sorter2, set up to write to merger: //
// merger1 will invoke do_sorter() with arg 3; //
// merger2 will invoke do_sorter() with arg 4 //
// ------//
do_sorter( 2 * which_pair, sorter2_pipe_fd[ 1 ] );
// ------//
// avoid falling through to yet another //
// invocation of interleave_streams() //
// ------//
exit( 0 );
}
interleave_streams( sorter1_pipe_fd[ 0 ], sorter2_pipe_fd[ 0 ], write_to );
}
void
do_sorter( int which_target_file, int write_to )
{
extern int data_cmp( char **, char ** );
extern void *calloc( size_t, size_t );
// ------//
// to save time, we will assume no more than 100 lines //
// per file, and no more than 80 chars per line; we //
// certainly won't run into trouble alloc()ing ~8kb! //
// ------//
char **pp_data_lines = (char **) calloc( 100, 80 );
int num_data_lines;
// ------//
// effect actual mechanics of sorting a data file, //
// specified by the integer argument (fileN.dat): //
// 4th char of filename is which_target_file + '0' //
// ------//
char data_src[ 80 ];
int src_fd;
sprintf( data_src, "file%d.dat", which_target_file );
// ------//
// we will not bother checking for error returns, as //
// file names are hard-coded and "can't be missing" //
// ------//
src_fd = open( data_src, 0 );
while( get_lin( src_fd, pp_data_lines[ num_data_lines ] ) )
{
num_data_lines++;
}
close( src_fd );
qsort( pp_data_lines, num_data_lines, sizeof (char *), data_cmp );
}
int
data_cmp( char **pp_str1, char **pp_str2 )
{
// ------//
// data lines are sorted based upon second integer field //
// ------//
int second_int_str1;
int second_int_str2;
// ------//
// N.B. %*d format directive, which matches, then //
// suppresses assignment of, an signed integer field //
// ------//
sscanf( *pp_str1, "%*d %d", &second_int_str1 );
sscanf( *pp_str2, "%*d %d", &second_int_str2 );
return second_int_str1 - second_int_str2;
}
void
interleave_streams( int fd1, int fd2, int write_to )
{
extern int get_lin( int, char[] );
char cached1[ 80 ];
char cached2[ 80 ];
int empty1 = 0;
int empty2 = 0;
// ------//
// assume neither stream is initially empty //
// ------//
(void) get_lin( fd1, cached1 );
(void) get_lin( fd2, cached2 );
for( ; ; )
{
if( empty1 & empty2 )
{
break;
}
else
// ------//
// if only one stream is exhausted, print last //
// cached datum and dump rest of other stream //
// ------//
if( empty1 )
{
write( write_to, cached2, strlen( cached2 ) );
write( write_to, "\n", 1 );
while( get_lin( fd2, cached2 ) )
{
write( write_to, cached2, strlen( cached2 ) );
write( write_to, "\n", 1 );
}
}
else
if( empty2 )
{
write( write_to, cached1, strlen( cached1 ) );
write( write_to, "\n", 1 );
while( get_lin( fd1, cached1 ) )
{
write( write_to, cached1, strlen( cached1 ) );
write( write_to, "\n", 1 );
}
}
else
// ------//
// neither stream is exhausted, compare last two //
// cached from each stream; whichever stream it //
// came from, replace w/next datum in that stream //
// ------//
if( strcmp( cached1, cached2 ) <= 0 )
{
write( write_to, cached1, strlen( cached1 ) );
write( write_to, "\n", 1 );
if( get_lin( fd1, cached1 ) == 0 )
{
empty1++;
}
}
else
{
write( write_to, cached2, strlen( cached2 ) );
write( write_to, "\n", 1 );
if( get_lin( fd2, cached2 ) == 0 )
{
empty2++;
}
}
}
}
int
get_lin( int fd, char *p_buf )
{
// ------//
// read() one byte at a time; arguably //
// slow, but screaming performance was //
// not a design criterion of the task, //
// and it's much less fuss than stdio //
// ------//
while( read( fd, p_buf, 1 ) )
{
if( *p_buf == '\n' )
{
*p_buf = '\0';
return 1;
}
else
{
p_buf++;
}
}
return 0;
}
#