/*
 * vim:ts=4 sw=4 et: 
 */
#include <poll.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/wait.h>
#include <unistd.h>

const int MAX_PROC = 10000;
const int MAX_READ = 10000;

void read_write(int input, int output)
{
    unsigned char buffer[2];
    int num_read = 0, num_write = 0;
    struct pollfd p[2] = { { .fd = input, .events = POLLIN },
                           { .fd = output, .events = POLLOUT} };
    while (num_read < MAX_READ || num_write < MAX_READ) {
        int rv = poll(p, 2, -1);
        if (p[1].revents & POLLOUT) {
            buffer[0] = num_write % 256;
            buffer[1] = num_write / 256;
            rv = write(output, buffer, 2);
            if (rv == -1) {
                perror("write");
                exit(EXIT_FAILURE);
            }
            num_write += 1;
            if (num_write >= MAX_READ) {
                p[1].fd = -output;
            }
        }
        if (p[0].revents & POLLIN) {
            rv = read(input, buffer, 2);
            if (rv == -1) {
                perror("read");
                exit(EXIT_FAILURE);
            }
            if (buffer[0] != num_read % 256
                || buffer[1] != num_read / 256) {
                fprintf(stderr, "Unexpected read: %d, %d != %d\n", buffer[0], buffer[1], num_read);
            }
            num_read += 1;
            if (num_read >= MAX_READ) {
                p[0].fd = -input;
            }
        }
    }
}

void wait_for(int kids)
{
    while (kids) {
        wait(NULL);
        kids--;
    }
}

int main(void)
{
    int pipes[2];
    int p = MAX_PROC;
    int input, output;
    int rv, pid;
    int kids = 0;

    rv = pipe(pipes);
    if (rv) {
        perror("pipe 1");
        exit(EXIT_FAILURE);
    }
    input = pipes[0];
    output = pipes[1];
    
    while (p > 1) {
        rv = pipe(pipes);
        if (rv) {
            perror("pipe 2");
	    fprintf(stderr, "%d left, exiting\n", p);
            exit(EXIT_FAILURE);
        }
        pid = fork();
        if (pid == -1) {
            perror("fork");
	    fprintf(stderr, "%d left, exiting\n", p);
            exit(EXIT_FAILURE);
        } 
        if (pid) {
            kids++;
            p = (p/2) + (p&1);
            close(pipes[0]);
            output = pipes[1];
        } else {
            kids = 0;
            p = p/2;
            close(pipes[1]);
            input = pipes[0];
        }
    }

    read_write(input, output);
    wait_for(kids);
    return EXIT_SUCCESS;
}