/* -*- mode: c -*-
 * $Id: ackermann.gcc,v 1.5 2001/05/04 01:21:38 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>

int 
Ack(int M, int N) {
    if (M == 0) return( N + 1 );
    if (N == 0) return( Ack(M - 1, 1) );
    return( Ack(M - 1, Ack(M, (N - 1))) );
}

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);

    printf("Ack(3,%d): %d\n", n, Ack(3, n));
    return(0);
}

/* -*- mode: c -*-
 * $Id: ary3.gcc,v 1.1 2001/05/31 02:27:48 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 *
 * this program is modified from:
 *   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
 * Timing Trials, or, the Trials of Timing: Experiments with Scripting
 * and User-Interface Languages</a> by Brian W. Kernighan and
 * Christopher J. Van Wyk.
 *
 * I added free() to deallocate memory.
 */

#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    int i, k, *x, *y;
    
    x = (int *) calloc(n, sizeof(int));
    y = (int *) calloc(n, sizeof(int));

    for (i = 0; i < n; i++) {
    x[i] = i + 1;
    }
    for (k=0; k<1000; k++) {
    for (i = n-1; i >= 0; i--) {
        y[i] += x[i];
    }
    }

    fprintf(stdout, "%d %d\n", y[0], y[n-1]);

    free(x);
    free(y);

    return(0);
}

/* -*- mode: c -*-
 * $Id: wc.gcc,v 1.4 2001/05/24 20:55:35 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 *
 * this program is modified from:
 *   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
 * Timing Trials, or, the Trials of Timing: Experiments with Scripting
 * and User-Interface Languages</a> by Brian W. Kernighan and
 * Christopher J. Van Wyk.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define    IN    1    
#define    OUT    0    

int
main() {
    int i, c, nl, nw, nc, state, nread;
    char buf[4096];

    state = OUT;
    nl = nw = nc = 0;
    while ((nread = read(0, buf, sizeof(buf))) > 0) {
    nc += nread;
    for (i=0; i<nread; i++) {
        c = buf[i];
        if (c == '\n')
        ++nl;
        if (c == ' ' || c == '\n' || c == '\t')
        state = OUT;
        else if (state == OUT) {
        state = IN;
        ++nw;
        }
    }
    }
    printf("%d %d %d\n", nl, nw, nc);
    return(0);
}

/* -*- mode: c -*-
 * $Id: echo.gcc,v 1.9 2001/06/28 03:04:47 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <sys/wait.h>
#include <netinet/in.h>


typedef int (*SOCKACTION_P)(int,struct sockaddr *,socklen_t);
#define DATA "Hello there sailor\n"

void myabort (char *m) { fprintf(stderr, "%s\n", m); exit(1); }
void sysabort (char *m) { perror(m); exit(1); }

int sigchld = 0;
void reaper (int sig) { sigchld = 1; }

int 
genericSock(int port,SOCKACTION_P action,char *actionExceptionText) {
    int ss, optval = 1;
    struct sockaddr_in sin;
    if ((ss = socket(PF_INET, SOCK_STREAM, 0)) == -1)
    sysabort("socket");
    if (setsockopt(ss, SOL_SOCKET, SO_REUSEADDR, &optval, sizeof(optval)) == -1)
    sysabort("setsockopt");
    memset(&sin,0,sizeof(sin));
    sin.sin_family = AF_INET;
    sin.sin_addr.s_addr = htonl(INADDR_LOOPBACK);
    sin.sin_port = port; 
    if (action(ss, (struct sockaddr *)&sin,(socklen_t)sizeof(sin)) == -1)
    sysabort(actionExceptionText);

    return(ss);
}

int
server_sock () {
    int ss = genericSock(0,(SOCKACTION_P)bind,"server/bind");
    return(listen(ss,2),ss);
}

int
client_sock (int port) {
    return(genericSock(port,(SOCKACTION_P)connect,"client/connect"));
}

int
get_port (int sock) {
    struct sockaddr_in sin;
    socklen_t slen = sizeof(sin);
    if (getsockname(sock, (struct sockaddr *)&sin, &slen) == -1)
    sysabort("server/getsockname");
    return(sin.sin_port);
}    

void
echo_client (int n, int port) {
    int i, sock, olen, len, nwritten, nread;
    char *offset, obuf[64], ibuf[64];
    char *end = ibuf + sizeof(ibuf);

    sock = client_sock(port);
    strcpy(obuf, DATA);
    olen = strlen(obuf);
    for (i=0; i<n; i++) {
    len = olen;
    offset = obuf;
    while (len > 0) {
        if ((nwritten = write(sock, offset, len)) == -1)
        sysabort("client/write");
        offset += nwritten;
        len -= nwritten;
    }
    offset = ibuf;
    while ((nread = read(sock, offset, (end - offset))) > 0) {
        offset += nread;
        if (*(offset-1) == '\n') break;
    }
    if (nread == -1)
        sysabort("client/read");
    *offset = 0;
    if ((strcmp(obuf, ibuf)) != 0) {
        char mbuf[128];
        sprintf(mbuf, "client: \"%s\" ne \"%s\"", obuf, ibuf);
        myabort(mbuf);
    }
    }
    close(sock);
}

void
echo_server (int n) {
    int ssock, csock, len, nwritten, total_bytes;
    pid_t pid;
    char buf[64], *offset;
    struct sockaddr_in sin;
    socklen_t slen = sizeof(sin);
    int status;

    ssock = server_sock();
    signal(SIGCHLD, reaper);
    if ((pid = fork()) == -1)
    sysabort("server/fork");
    if (pid) {
    
    if ((csock = accept(ssock, (struct sockaddr *)&sin, &slen)) == -1)
        sysabort("server/accept");
    total_bytes = 0;
    while ((len = read(csock, buf, sizeof(buf))) > 0) {
        if (sigchld) myabort("server/sigchld");
        offset = buf;
        total_bytes += len;
        while (len > 0) {
        if ((nwritten = write(csock, offset, len)) == -1)
            sysabort("server/write");
        offset += nwritten;
        len -= nwritten;
        }
    }
    if (len == -1)
        sysabort("server/read");
    close(csock);
    fprintf(stdout, "server processed %d bytes\n", total_bytes);
    } else {
    
    echo_client(n, get_port(ssock));
    }
    wait(&status);
}

int
main(int argc, char *argv[]) {
    echo_server((argc == 2) ? atoi(argv[1]) : 1);
    return(0);
}

/* -*- mode: c -*-
 * $Id: except.gcc,v 1.1 2001/01/07 04:31:15 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>

int HI = 0, LO = 0;

static jmp_buf Hi_exception;
static jmp_buf Lo_exception;

void blowup (int n) {
    if (n & 1) {
    longjmp(Lo_exception, 1);
    } else {
    longjmp(Hi_exception, 1);
    }
}

void lo_function (volatile int n) {
    if (setjmp(Lo_exception) != 0) {
    LO++;
    } else {
    blowup(n);
    }
}

void hi_function (volatile int n) {
    if (setjmp(Hi_exception) != 0) {
    HI++;
    } else {
    lo_function(n);
    }
}

void some_function (int n) {
    hi_function(n);
}

int
main(int argc, char *argv[]) {
    int volatile N = ((argc == 2) ? atoi(argv[1]) : 1);

    while (N) {
    some_function(N--);
    }
    printf("Exceptions: HI=%d / LO=%d\n", HI, LO);
    return(0);
}

/* -*- mode: c -*-
 * $Id: fibo.gcc,v 1.2 2000/12/24 19:10:50 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>

unsigned long
fib(unsigned long n) {
    if (n < 2)
    return(1);
    else
    return(fib(n-2) + fib(n-1));
}

int
main(int argc, char *argv[]) {
    int N = ((argc == 2) ? atoi(argv[1]) : 1);
    printf("%ld\n", fib(N));
    return(0);
}

/* -*- mode: c -*-
 * $Id: hash.gcc,v 1.2 2001/01/07 08:33:09 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "simple_hash.h"

int main(int argc, char *argv[]) {
    int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];

    struct ht_ht *ht = ht_create(n);

    for (i=1; i<=n; i++) {
    sprintf(buf, "%x", i);
    (ht_find_new(ht, buf))->val = i;
    }

    for (i=n; i>0; i--) {
    sprintf(buf, "%d", i);
    if (ht_find(ht, buf)) c++;
    }

    ht_destroy(ht);

    printf("%d\n", c);
    return(0);
}

/* -*- mode: c -*-
 * $Id: hash2.gcc,v 1.3 2001/01/07 16:23:00 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "simple_hash.h"

int main(int argc, char *argv[]) {
    int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
    char buf[32];
    struct ht_ht *ht1 = ht_create(10000);
    struct ht_ht *ht2 = ht_create(10000);
    struct ht_node *node;

    for (i=0; i<=9999; ++i) {
    sprintf(buf, "foo_%d", i);
    ht_find_new(ht1, buf)->val = i;
    }

    for (i=0; i<n; ++i) {
    for (node=ht_first(ht1); node; node=ht_next(ht1)) {
        ht_find_new(ht2, node->key)->val += node->val;
    }
    }

    printf("%d %d %d %d\n",
       (ht_find(ht1, "foo_1"))->val,
       (ht_find(ht1, "foo_9999"))->val,
       (ht_find(ht2, "foo_1"))->val,
       (ht_find(ht2, "foo_9999"))->val);

    ht_destroy(ht1);
    ht_destroy(ht2);
    return(0);
}

/* -*- mode: c -*-
 * $Id: heapsort.gcc,v 1.10 2001/05/08 02:46:59 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdlib.h>
#include <math.h>
#include <stdio.h>

#define IM 139968
#define IA   3877
#define IC  29573

double
gen_random(double max) {
    static long last = 42;
    return( max * (last = (last * IA + IC) % IM) / IM );
}

void
heapsort(int n, double *ra) {
    int i, j;
    int ir = n;
    int l = (n >> 1) + 1;
    double rra;

    for (;;) {
    if (l > 1) {
        rra = ra[--l];
    } else {
        rra = ra[ir];
        ra[ir] = ra[1];
        if (--ir == 1) {
        ra[1] = rra;
        return;
        }
    }
    i = l;
    j = l << 1;
    while (j <= ir) {
        if (j < ir && ra[j] < ra[j+1]) { ++j; }
        if (rra < ra[j]) {
        ra[i] = ra[j];
        j += (i = j);
        } else {
        j = ir + 1;
        }
    }
    ra[i] = rra;
    }
}

int
main(int argc, char *argv[]) {
    int N = ((argc == 2) ? atoi(argv[1]) : 1);
    double *ary;
    int i;
    
    
    ary = (double *)malloc((N+1) * sizeof(double));
    for (i=1; i<=N; i++) {
    ary[i] = gen_random(1);
    }

    heapsort(N, ary);

    printf("%.10g\n", ary[N]);

    free(ary);
    return(0);
}

/* -*- mode: c -*-
 * $Id: hello.gcc,v 1.2 2001/06/18 01:13:58 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>

int main() {
    fputs("hello world\n", stdout);
    return(0);
}

/* -*- mode: c -*-
 * $Id: lists.gcc,v 1.3 2001/04/29 04:39:50 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define SIZE 10000

// a simple Double Linked List
// the head node is special, it's val is length of list
typedef struct DLL {
    int val;
    struct DLL *next;    
    struct DLL *prev;    
} DLL;

inline int list_length(DLL *head) { return(head->val); }
inline int list_empty(DLL *head) { return(list_length(head) == 0); }
inline DLL *list_first(DLL *head) { return(head->next); }
inline DLL *list_last(DLL *head) { return(head->prev); }

void list_push_tail(DLL *head, DLL *item) {
    DLL *tail = head->prev;
    tail->next = item;
    item->next = head;
    head->prev = item;
    item->prev = tail;
    head->val++;
}

DLL *list_pop_tail(DLL *head) {
    DLL *prev, *tail;
    if (list_empty(head)) return(NULL);
    tail = head->prev;
    prev = tail->prev;
    prev->next = head;
    head->prev = prev;
    head->val--;
    return(tail);
}

void list_push_head(DLL *head, DLL *item) {
    DLL *next = head->next;
    head->next = item;
    next->prev = item;
    item->next = next;
    item->prev = head;
    head->val++;
}

DLL *list_pop_head(DLL *head) {
    DLL *next;
    if (list_empty(head)) return(NULL);
    next = head->next;
    head->next = next->next;
    next->next->prev = head;
    head->val--;
    return(next);
}

int list_equal(DLL *x, DLL *y) {
    DLL *xp, *yp;
    // first val's checked will be list lengths
    for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
    if (xp->val != yp->val) return(0);
    }
    if (xp->val != yp->val) return(0);
    return(yp->next == y);
}

void list_print(char *msg, DLL *x) {
    DLL *xp, *first = x->next;
    int i = 0;
    printf(msg);
    printf("length: %d\n", list_length(x));
    for (xp=x->next; xp->next != first; xp=xp->next) {
    printf("i:%3d  v:%3d  n:%3d  p:%3d\n", ++i,
           xp->val, xp->next->val, xp->prev->val);
    }
    printf("[last entry points to list head]\n");
    printf("[val of next of tail is:  %d]\n", xp->next->val);
}

DLL *list_new() {
    DLL *l = (DLL *)malloc(sizeof(DLL));
    l->next = l;
    l->prev = l;
    l->val = 0;
    return(l);
}


DLL *list_sequence(int from, int to) {
    int size, tmp, i, j;
    DLL *l;
    if (from > to) {
    tmp = from; from = to; to = tmp;
    }
    size = to - from + 1;
    l = (DLL *)malloc((size+1) * sizeof(DLL));
    from--;
    for (i=0, j=1; i<size; ++i, ++j) {
    l[i].next = &l[i+1];
    l[j].prev = &l[j-1];
    l[i].val = from++;
    }
    l[0].prev = &l[size];
    l[size].next = &l[0];
    l[size].prev = &l[size-1];
    l[size].val = from;
    l[0].val = size;
    return(l);
}

DLL *list_copy(DLL *x) {
    int i, j, size = list_length(x);
    DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
    for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
    l[i].next = &l[j];
    l[j].prev = &l[i];
    l[i].val = xp->val;
    }
    l[0].prev = &l[size];
    l[size].next = &l[0];
    l[size].val = list_last(x)->val;
    return(l);
}

void list_reverse (DLL *head) {
    DLL *tmp, *p = head;
    do {
    tmp = p->next;
    p->next = p->prev;
    p->prev = tmp;
    p = tmp;
    } while (p != head);
}

int test_lists() {
    int len = 0;
    // create a list of integers (li1) from 1 to SIZE
    DLL *li1 = list_sequence(1, SIZE);
    // copy the list to li2
    DLL *li2 = list_copy(li1);
    // remove each individual item from left side of li2 and
    // append to right side of li3 (preserving order)
    DLL *li3 = list_new();
    // compare li2 and li1 for equality
    if (!list_equal(li2, li1)) {
    fprintf(stderr, "li2 and li1 are not equal\n");
    exit(1);
    }
    while (!list_empty(li2)) {
    list_push_tail(li3, list_pop_head(li2));
    }
    // li2 must now be empty
    if (!list_empty(li2)) {
    fprintf(stderr, "li2 should be empty now\n");
    exit(1);
    }
    // remove each individual item from right side of li3 and
    // append to right side of li2 (reversing list)
    while (!list_empty(li3)) {
    list_push_tail(li2, list_pop_tail(li3));
    }
    // li3 must now be empty
    if (!list_empty(li3)) {
    fprintf(stderr, "li3 should be empty now\n");
    exit(1);
    }
    // reverse li1 in place
    list_reverse(li1);
    // check that li1's first item is now SIZE
    if (list_first(li1)->val != SIZE) {
    fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
        SIZE, list_first(li1)->val);
    exit(1);
    }
    // check that li1's last item is now 1
    if (list_last(li1)->val != 1) {
    fprintf(stderr, "last value wrong, wanted %d, got %d\n",
        SIZE, list_last(li1)->val);
    exit(1);
    }
    // check that li2's first item is now SIZE
    if (list_first(li2)->val != SIZE) {
    fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
        SIZE, list_first(li2)->val);
    exit(1);
    }
    // check that li2's last item is now 1
    if (list_last(li2)->val != 1) {
    fprintf(stderr, "last value wrong, wanted %d, got %d\n",
        SIZE, list_last(li2)->val);
    exit(1);
    }
    // check that li1's length is still SIZE
    if (list_length(li1) != SIZE) {
    fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
        SIZE, list_length(li1));
    exit(1);
    }
    // compare li1 and li2 for equality
    if (!list_equal(li1, li2)) {
    fprintf(stderr, "li1 and li2 are not equal\n");
    exit(1);
    }
    len = list_length(li1);
    free(li1);
    free(li2);
    free(li3);
    // return the length of the list
    return(len);
}

int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    int result = 0;
    while(n--) result = test_lists();
    printf("%d\n", result);
    return 0;
}

/* -*- mode: c -*-
 * $Id: matrix.gcc,v 1.6 2001/03/31 15:52:48 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define SIZE 30

int **mkmatrix(int rows, int cols) {
    int i, j, count = 1;
    int **m = (int **) malloc(rows * sizeof(int *));
    for (i=0; i<rows; i++) {
    m[i] = (int *) malloc(cols * sizeof(int));
    for (j=0; j<cols; j++) {
        m[i][j] = count++;
    }
    }
    return(m);
}

void zeromatrix(int rows, int cols, int **m) {
    int i, j;
    for (i=0; i<rows; i++)
    for (j=0; j<cols; j++)
        m[i][j] = 0;
}

void freematrix(int rows, int **m) {
    while (--rows > -1) { free(m[rows]); }
    free(m);
}

int **mmult(int rows, int cols, int **m1, int **m2, int **m3) {
    int i, j, k, val;
    for (i=0; i<rows; i++) {
    for (j=0; j<cols; j++) {
        val = 0;
        for (k=0; k<cols; k++) {
        val += m1[i][k] * m2[k][j];
        }
        m3[i][j] = val;
    }
    }
    return(m3);
}

int main(int argc, char *argv[]) {
    int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
    
    int **m1 = mkmatrix(SIZE, SIZE);
    int **m2 = mkmatrix(SIZE, SIZE);
    int **mm = mkmatrix(SIZE, SIZE);

    for (i=0; i<n; i++) {
    mm = mmult(SIZE, SIZE, m1, m2, mm);
    }
    printf("%d %d %d %d\n", mm[0][0], mm[2][3], mm[3][2], mm[4][4]);

    freematrix(SIZE, m1);
    freematrix(SIZE, m2);
    freematrix(SIZE, mm);
    return(0);
}

/* -*- mode: c -*-
 * $Id: methcall.gcc,v 1.3 2001/06/14 12:58:39 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>

#define true  1
#define false 0


#define TOGGLE \
    char state; \
    char (*value)(struct Toggle *); \
    struct Toggle *(*activate)(struct Toggle *)

#define DESTROY  free

typedef struct Toggle {
    TOGGLE;
} Toggle;

char toggle_value(Toggle *this) {
    return(this->state);
}
Toggle *toggle_activate(Toggle *this) {
    this->state = !this->state;
    return(this);
}
Toggle *init_Toggle(Toggle *this, char start_state) {
    this->state = start_state;
    this->value = toggle_value;
    this->activate = toggle_activate;
    return(this);
}
Toggle *new_Toggle(char start_state) {
    Toggle *this = (Toggle *)malloc(sizeof(Toggle));
    return(init_Toggle(this, start_state));
}


typedef struct NthToggle {
    TOGGLE;
    int count_max;
    int counter;
} NthToggle;

NthToggle *nth_toggle_activate(NthToggle *this) {
    if (++this->counter >= this->count_max) {
    this->state = !this->state;
    this->counter = 0;
    }
    return(this);
}
NthToggle *init_NthToggle(NthToggle *this, int max_count) {
    this->count_max = max_count;
    this->counter = 0;
    this->activate = (Toggle *(*)(Toggle *))nth_toggle_activate;
    return(this);
}
NthToggle *new_NthToggle(char start_state, int max_count) {
    NthToggle *this = (NthToggle *)malloc(sizeof(NthToggle));
    this = (NthToggle *)init_Toggle((Toggle *)this, start_state);
    return(init_NthToggle(this, max_count));
}


int main(int argc, char *argv[]) {
    int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
    Toggle *tog;
    NthToggle *ntog;
    char val = true;

    tog = new_Toggle(true);
    for (i=0; i<n; i++) {
    val = tog->activate(tog)->value(tog);
    }
    fputs(val ? "true\n" : "false\n", stdout);
    DESTROY(tog);
    
    val = true;
    ntog = new_NthToggle(val, 3);
    for (i=0; i<n; i++) {
    val = ntog->activate(ntog)->value(ntog);
    }
    fputs(val ? "true\n" : "false\n", stdout);
    DESTROY(ntog);
    return 0;
}

/* -*- mode: c -*-
 * $Id: nestedloop.gcc,v 1.1 2000/12/30 21:42:57 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    int a, b, c, d, e, f, x=0;
    
    for (a=0; a<n; a++)
    for (b=0; b<n; b++)
        for (c=0; c<n; c++)
        for (d=0; d<n; d++)
            for (e=0; e<n; e++)
            for (f=0; f<n; f++)
                x++;

    printf("%d\n", x);
    return(0);
}

/* -*- mode: c -*-
 * $Id: objinst.gcc,v 1.3 2001/07/04 03:36:08 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>


enum {false, true};

#define TOGGLE \
    char state; \
    char (*value)(struct Toggle *); \
    struct Toggle *(*activate)(struct Toggle *)

#define DESTROY  free

typedef struct Toggle {
    TOGGLE;
} Toggle;

char toggle_value(Toggle *this) {
    return(this->state);
}
Toggle *toggle_activate(Toggle *this) {
    this->state = !this->state;
    return(this);
}
Toggle *init_Toggle(Toggle *this, char start_state) {
    this->state = start_state;
    this->value = toggle_value;
    this->activate = toggle_activate;
    return(this);
}
Toggle *new_Toggle(char start_state) {
    Toggle *this = (Toggle *)malloc(sizeof(Toggle));
    return(init_Toggle(this, start_state));
}


typedef struct NthToggle {
    TOGGLE;
    int count_max;
    int counter;
} NthToggle;

NthToggle *nth_toggle_activate(NthToggle *this) {
    if (++this->counter >= this->count_max) {
    this->state = !this->state;
    this->counter = 0;
    }
    return(this);
}
NthToggle *init_NthToggle(NthToggle *this, int max_count) {
    this->count_max = max_count;
    this->counter = 0;
    this->activate = (Toggle *(*)(Toggle *))nth_toggle_activate;
    return(this);
}
NthToggle *new_NthToggle(char start_state, int max_count) {
    NthToggle *this = (NthToggle *)malloc(sizeof(NthToggle));
    this = (NthToggle *)init_Toggle((Toggle *)this, start_state);
    return(init_NthToggle(this, max_count));
}


int main(int argc, char *argv[]) {
    int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
    Toggle *tog;
    NthToggle *ntog;

    tog = new_Toggle(true);
    for (i=0; i<5; i++) {
    fputs((tog->activate(tog)->value(tog)) ? "true\n" : "false\n", stdout);
    }
    DESTROY(tog);
    for (i=0; i<n; i++) {
    tog = new_Toggle(true);
    DESTROY(tog);
    }
    
    fputs("\n", stdout);

    ntog = new_NthToggle(true, 3);
    for (i=0; i<8; i++) {
    fputs((ntog->activate(ntog)->value(ntog)) ? "true\n" : "false\n", stdout);
    }
    DESTROY(ntog);
    for (i=0; i<n; i++) {
    ntog = new_NthToggle(true, 3);
    DESTROY(ntog);
    }
    return 0;
}

/* -*- mode: c -*-
 * $Id: prodcons.gcc,v 1.3 2001/05/27 18:25:11 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>
#include <sys/types.h>
#include <pthread.h>

pthread_mutex_t mutex;
pthread_cond_t control;
void producer(unsigned int *arg);
void consumer(unsigned int *arg);
unsigned int count, data, consumed, produced;


int
main(int argc, char *argv[]) {
    unsigned int n = ((argc == 2) ? atoi(argv[1]) : 1);
    pthread_t t1, t2;
    
    count = data = consumed = produced = 0;

    if (pthread_mutex_init(&mutex, NULL)) {
    perror("pthread_mutex_init");
    exit(1);
    }
    if (pthread_cond_init(&control, NULL)) {
    perror("pthread_cond_init");
    exit(1);
    }
    if (pthread_create(&t1, (pthread_attr_t *)NULL,
               (void * (*)(void *))producer, (void *)&n)) {
    perror("pthread_create");
    exit(1);
    }
    if (pthread_create(&t2, (pthread_attr_t *)NULL,
               (void * (*)(void *))consumer, (void *)&n)) {
    perror("pthread_create");
    exit(1);
    }
  
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    fprintf(stdout, "%d %d\n", produced, consumed);
    return(0);
}


void producer(unsigned int *arg) {
    unsigned int i, n = *arg;
    for (i=1; i<=n; i++) {
    pthread_mutex_lock(&mutex);
    while (count == 1) {
        pthread_cond_wait(&control, &mutex);
    }
    data = i;
    count = 1;
    pthread_cond_signal(&control);
    pthread_mutex_unlock(&mutex);
    produced++;
    }
}
 

void consumer(unsigned int *arg) {
    unsigned int i = 0, n = *arg;
    while (1) {
    pthread_mutex_lock(&mutex);
    while (count == 0) {
        pthread_cond_wait(&control, &mutex);
    }
    i = data;
    count = 0;
    pthread_cond_signal(&control);
    pthread_mutex_unlock(&mutex);
    consumed++;
    if (i == n) return;
    }
}

/* -*- mode: c -*-
 * $Id: random.gcc,v 1.14 2001/05/08 01:36:50 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define IM 139968
#define IA 3877
#define IC 29573

double
gen_random(double max) {
    static long last = 42;
    
    last = (last * IA + IC) % IM;
    return( max * last / IM );
}

int
main(int argc, char *argv[]) {
    int N = ((argc == 2) ? atoi(argv[1]) : 1);
    double result = 0;
    
    while (N--) {
    result = gen_random(100.0);
    }
    printf("%.9f\n", result);
    return(0);
}

/* -*- mode: c -*-
 * $Id: regexmatch.gcc,v 1.4 2000/12/24 05:43:53 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <pcre.h>
#include <string.h>

#define MAXLINES   100
#define MAXLINELEN 132

char *pattern = 
"(?:^|[^\\d\\(])"        
"(\\()?"            
"(\\d\\d\\d)"            
"(?(1)\\))"            
"[ ]"                
"(\\d\\d\\d)"            
"[ -]"                
"(\\d\\d\\d\\d)"        
"\\D"                
;


int
main(int argc, char *argv[]) {
    int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
    int count;
    char *cptr = "";
    char **phones;
    pcre *re;
    int erroffset;
    const char *errptr;
    int n, lines = 0;
    char num[256];
    int i, j, k, matchlen;
    char *matchoffset;
    int nmatches;
    int *ovec, ovecsize;
    pcre_extra *study;

    phones = (char **)malloc(MAXLINES * sizeof(char *));
    if (!phones) {
    fprintf(stderr, "malloc for phones array failed\n");
    exit(1);
    }
    lines = 0;
    while (cptr) {
    phones[lines] = (char *)malloc(MAXLINELEN);
    if (!phones[lines]) {
        fprintf(stderr, "malloc to hold line #%d failed\n", lines);
        exit(1);
    }
    cptr = fgets(phones[lines], MAXLINELEN, stdin);
    lines++;
    if (lines > MAXLINES) {
        fprintf(stderr, "MAXLINES is too small\n");
        exit(1);
    }
    }

    re = pcre_compile(pattern, 0, &errptr, &erroffset, NULL);
    if (!re) {
    fprintf(stderr, "can't open compile regexp\n");
    exit(1);
    }

    study = pcre_study(re, 0, &errptr);

    if (pcre_fullinfo(re, NULL, PCRE_INFO_CAPTURECOUNT, &nmatches) != 0) {
    fprintf(stderr, "pcre_fullinfo failed\n");
    exit(1);
    }
    nmatches++;            

    ovecsize = sizeof(int) * nmatches * 3;
    ovec = (int *)malloc(ovecsize);
    if (!ovec) {
    fprintf(stderr, "malloc for ovec array failed\n");
    exit(1);
    }

    count = 0;
    while (NUM--) {
    for (i=0; i<lines; i++) {
        n = pcre_exec(re, study,
              phones[i], strlen(phones[i]), 0,
              0, ovec, ovecsize);
        if (n == nmatches) {
        
        k = 2*2;    
        
        j = 0;
        num[j++] = '(';
        matchoffset = phones[i] + ovec[k];
        matchlen = ovec[k+1] - ovec[k];
        strncpy(num+j, matchoffset, matchlen);
        j += matchlen; k += 2;
        num[j++] = ')';
        
        num[j++] = ' ';
        
        matchoffset = phones[i] + ovec[k];
        matchlen = ovec[k+1] - ovec[k];
        strncpy(num+j, matchoffset, matchlen);
        j += matchlen; k += 2;
        
        num[j++] = '-';
        
        matchoffset = phones[i] + ovec[k];
        matchlen = ovec[k+1] - ovec[k];
        strncpy(num+j, matchoffset, matchlen);
        j += matchlen; k += 2;
        
        num[j] = 0;
        if (0 == NUM) {
            count++;
            printf("%d: %s\n", count, num);
        }
        }
    }
    }

    for (i=0; i<MAXLINES; i++) {
    free(phones[i]);
    }
    free(phones);
    free(ovec);

    return(0);
}

/* -*- mode: c -*-
 * $Id: reversefile.gcc,v 1.9 2001/06/25 01:45:44 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MAXREAD 4096

int main(int argc, char *argv[]) {
    int nread, len = 0, size = (4 * MAXREAD);
    char *cp, *offset, *buf = malloc(size + 1);

    while (1) {
    if ((nread = read(0, (buf + len), MAXREAD)) > 0) {
        len += nread;
        if (MAXREAD > (size - len)) {
        size <<= 1;
        if (0 == (buf = realloc(buf, size + 1))) {
            fprintf(stderr, "realloc failed\n");
            exit(1);
        }
        }
    } else {
        if ( 0 == nread) break;
        if (-1 == nread) {
        perror("read");
        exit(1);
        }
    }    
    }
    offset = buf + len;
    *offset = 0;
    for (cp = offset; cp > buf; --cp) {
    if ('\n' == *cp) {
        *offset = 0;
        if (cp < offset)
        fputs(offset = cp+1, stdout);
    }
    }
    if (cp < offset) {
    *offset = 0;
    fputs(cp, stdout);
    }
    free(buf);
    return(0);
}

/* -*- mode: c -*-
 * $Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>

int
main(int argc, char *argv[]) {
    int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
    static char flags[8192 + 1];
    long i, k;
    int count = 0;

    while (NUM--) {
    count = 0; 
    for (i=2; i <= 8192; i++) {
        flags[i] = 1;
    }
    for (i=2; i <= 8192; i++) {
        if (flags[i]) {
        // remove all multiples of prime: i
        for (k=i+i; k <= 8192; k+=i) {
            flags[k] = 0;
        }
        count++;
        }
    }
    }
    printf("Count: %d\n", count);
    return(0);
}

/* -*- mode: c -*-
 * $Id: spellcheck.gcc,v 1.7 2001/07/26 14:52:16 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 * with help from Brad Knotwell
 */

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "simple_hash.h"

#define MAXLINELEN 128

struct ht_ht *dict = NULL;

int handleInput(FILE *input,void (*hashManipFn)(char *))
{
    int wordbufsize = 80,i = 0;
    char *cp, *wordbuf = (char *)malloc(wordbufsize + 1);
    char line[MAXLINELEN];
    
    if((wordbuf = malloc(wordbufsize+1)) == NULL) 
        return(fprintf(stderr,"malloc\n"),0);

    while (fgets(line, MAXLINELEN, input))
    for (cp=line; *cp > 0; cp++) {
        if (isspace(*cp)) {
        if (i) {
            wordbuf[i] = '\0';
                    hashManipFn(wordbuf);
            i = 0;
        }
        } else {
        wordbuf[i++] = *cp;
        if (i == wordbufsize) {
            wordbufsize *= 2;
            if((wordbuf = realloc(wordbuf, wordbufsize + 1)) == NULL)
                        return(fprintf(stderr, "realloc\n"), 0);
        }
        }
        }

    free(wordbuf);
    return(1);
}

void spellCheck(char *key) { 
    if (ht_find_new(dict,key)->val != 1) printf("%s\n",key);
}

void hashLoad(char *key) { ht_find_new(dict,key)->val = 1; }
 
int main(int argc, char *argv[]) {
    FILE *fh;
    int rc;

    /*  
        ht_create doesn't handle malloc and calloc failures 
        so this is superfluous 
    */
    if((dict = ht_create(40000)) == NULL)
        return(fprintf(stderr,"hash creation failed\n"),EXIT_FAILURE);
    
    if ((fh = fopen("Usr.Dict.Words", "r")) == NULL) 
        return(fprintf(stderr,"couldn't open dictionary\n"),EXIT_FAILURE);

    rc = ((handleInput(fh,hashLoad) && handleInput(stdin,spellCheck)) ? EXIT_SUCCESS : EXIT_FAILURE);

    ht_destroy(dict);
    return(rc);
}

/* -*- mode: c -*-
 * $Id: moments.gcc,v 1.7 2001/01/05 02:07:51 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXLINELEN 128

int
compare_doubles (const double *a, const double *b) {
    return (int) (*a - *b);
}


int
main() {
    char line[MAXLINELEN];
    int i, n = 0, mid = 0;
    double sum = 0.0;
    double mean = 0.0;
    double average_deviation = 0.0;
    double standard_deviation = 0.0;
    double variance = 0.0;
    double skew = 0.0;
    double kurtosis = 0.0;
    double median = 0.0;
    double deviation = 0.0;
    int array_size = 4096;

    double *nums = (double *)malloc(array_size * sizeof(double));

    while (fgets(line, MAXLINELEN, stdin)) {
    sum += (nums[n++] = atof(line));
    if (n == array_size) {
        array_size *= 2;
        nums = (double *)realloc(nums, array_size * sizeof(double));
    }
    }
    mean = sum/n;
    for (i=0; i<n; i++) {
    deviation = nums[i] - mean;
    average_deviation += fabs(deviation);
    variance += pow(deviation,2);
    skew += pow(deviation,3);
    kurtosis += pow(deviation,4);
    }
    average_deviation /= n;
    variance /= (n - 1);
    standard_deviation = sqrt(variance);
    if (variance) {
    skew /= (n * variance * standard_deviation);
    kurtosis = (kurtosis/(n * variance * variance)) - 3.0;
    }

    qsort(nums, n, sizeof (double),
      (int (*)(const void *, const void *))compare_doubles);
    mid = (n/2);
    median = n % 2 ? nums[mid] : (nums[mid] + nums[mid-1])/2;

    free(nums);

    printf("n:                  %d\n", n);
    printf("median:             %f\n", median);
    printf("mean:               %f\n", mean);
    printf("average_deviation:  %f\n", average_deviation);
    printf("standard_deviation: %f\n", standard_deviation);
    printf("variance:           %f\n", variance);
    printf("skew:               %f\n", skew);
    printf("kurtosis:           %f\n", kurtosis);
    return(0);
}

/* -*- mode: c -*-
 * $Id: strcat.gcc,v 1.7 2001/05/02 05:55:44 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define STUFF "hello\n"

int
main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    int i, buflen = 32;
    char *strbuf = calloc(sizeof(char), buflen);
    char *strend = strbuf;
    int stufflen = strlen(STUFF);

    if (!strbuf) { perror("calloc strbuf"); exit(1); }
    for (i=0; i<n; i++) {
    if (((strbuf+buflen)-strend) < (stufflen+1)) {
        buflen = 2*buflen;
        strbuf = realloc(strbuf, buflen);
        if (!strbuf) { perror("realloc strbuf"); exit(1); }
        strend = strbuf + strlen(strbuf);
    }
    
    strcat(strend, STUFF);
    strend += stufflen;
    }
    fprintf(stdout, "%d\n", strlen(strbuf));
    free(strbuf);

    return(0);
}

/* -*- mode: c -*-
 * $Id: sumcol.gcc,v 1.3 2000/12/24 05:43:53 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <stdlib.h>

#define MAXLINELEN 128

int
main() {
    int sum = 0;
    char line[MAXLINELEN];

    while (fgets(line, MAXLINELEN, stdin)) {
    sum += atoi(line);
    }
    printf("%d\n", sum);
    return(0);
}

/* -*- mode: c -*-
 * $Id: wordfreq.gcc,v 1.4 2001/01/07 19:24:51 doug Exp $
 * http://www.bagley.org/~doug/shootout/
 */

#include <stdio.h>
#include <ctype.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include "simple_hash.h"

typedef int (*comparator)(const void *, const void *);

int cmp_hash(struct ht_node **a, struct ht_node **b) {
    int val = (*b)->val - (*a)->val;
    return((val == 0) ? strcmp((*b)->key, (*a)->key) : val);
}

int main() {
    int bufsize = 80;
    char *buf = (char *)malloc(bufsize + 1);
    char c;
    int i = 0;
    struct ht_ht *ht = ht_create(75000);
    struct ht_node **sort_array, **sort_tmp, *node;

    while ((c = getchar()) > 0) {
        if (isalpha(c)) {
            buf[i++] = tolower(c);
        if (i == bufsize) {
        bufsize *= 2;
        buf = realloc(buf, bufsize + 1);
        } 
        } else {
        if (i > 0) {
        buf[i] = '\0';
        ++(ht_find_new(ht, buf)->val);
        i = 0;
        }
        }
    }
    free(buf);

    sort_array = sort_tmp =
    malloc(sizeof(struct ht_node *) * ht_count(ht));

    for (node=ht_first(ht); (*sort_tmp++ = node) != 0; node=ht_next(ht)) ;

    qsort(sort_array, ht_count(ht), sizeof(struct ht_node *),
      (comparator)cmp_hash);

    for (i=0; i<ht_count(ht); i++)
    printf("%7d\t%s\n", ht_val(sort_array[i]), ht_key(sort_array[i])); 

    ht_destroy(ht);
    return(0);
}