1 GCC
2 Back to the Win32 Shootout
3  Back to dada's perl lab
4 
5 [The Original Shootout] � [NEWS] � [FAQ] � [Methodology] � [Platform
6 Details] � [Acknowledgements] � [Scorecard] �
7 
8 
9 All Source For gcc
10 
11 
12 Ackermann's Function
13 
14 
15 
16 
17 /* -*- mode: c -*-
18  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
19  * http://www.bagley.org/~doug/shootout/
20  */
21 
22 #include <stdio.h>
23 #include <stdlib.h>
24 
25 int
26 Ack(int M, int N) {
27     if (M == 0) return( N + 1 );
28     if (N == 0) return( Ack(M - 1, 1) );
29     return( Ack(M - 1, Ack(M, (N - 1))) );
30 }
31 
32 int
main(int argc,char * argv[])33 main(int argc, char *argv[]) {
34     int n = ((argc == 2) ? atoi(argv[1]) : 1);
35 
36     printf("Ack(3,%d): %d\n", n, Ack(3, n));
37     return(0);
38 }
39 
40 
41 
42 
43 
44 Array Access
45 
46 
47 
48 
49 /* -*- mode: c -*-
50  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
51  * http://www.bagley.org/~doug/shootout/
52  *
53  * this program is modified from:
54  *   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
55  * Timing Trials, or, the Trials of Timing: Experiments with Scripting
56  * and User-Interface Languages</a> by Brian W. Kernighan and
57  * Christopher J. Van Wyk.
58  *
59  * I added free() to deallocate memory.
60  */
61 
62 #include <stdio.h>
63 #include <stdlib.h>
64 
65 int
main(int argc,char * argv[])66 main(int argc, char *argv[]) {
67     int n = ((argc == 2) ? atoi(argv[1]) : 1);
68     int i, k, *x, *y;
69 
70     x = (int *) calloc(n, sizeof(int));
71     y = (int *) calloc(n, sizeof(int));
72 
73     for (i = 0; i < n; i++) {
74     x[i] = i + 1;
75     }
76     for (k=0; k<1000; k++) {
77     for (i = n-1; i >= 0; i--) {
78         y[i] += x[i];
79     }
80     }
81 
82     fprintf(stdout, "%d %d\n", y[0], y[n-1]);
83 
84     free(x);
85     free(y);
86 
87     return(0);
88 }
89 
90 
91 
92 Count Lines/Words/Chars
93 
94 
95 
96 
97 /* -*- mode: c -*-
98  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
99  * http://www.bagley.org/~doug/shootout/
100  *
101  * this program is modified from:
102  *   http://cm.bell-labs.com/cm/cs/who/bwk/interps/pap.html
103  * Timing Trials, or, the Trials of Timing: Experiments with Scripting
104  * and User-Interface Languages</a> by Brian W. Kernighan and
105  * Christopher J. Van Wyk.
106  *
107  */
108 
109 #include <stdio.h>
110 #include <stdlib.h>
111 #include <unistd.h>
112 
113 #define    IN    1
114 #define    OUT    0
115 
116 int
117 main() {
118     int i, c, nl, nw, nc, state, nread;
119     char buf[4096];
120 
121     state = OUT;
122     nl = nw = nc = 0;
123     while ((nread = read(0, buf, sizeof(buf))) > 0) {
124     nc += nread;
125     for (i=0; i<nread; i++) {
126         c = buf[i];
127         if (c == '\n')
128         ++nl;
129         if (c == ' ' || c == '\n' || c == '\t')
130         state = OUT;
131         else if (state == OUT) {
132         state = IN;
133         ++nw;
134         }
135     }
136     }
137     printf("%d %d %d\n", nl, nw, nc);
138     return(0);
139 }
140 
141 
142 
143 Echo Client/Server
144 
145 
146 
147 
148 /* -*- mode: c -*-
149  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
150  * http://www.bagley.org/~doug/shootout/
151  */
152 
153 #include <stdio.h>
154 #include <stdlib.h>
155 #include <string.h>
156 #include <unistd.h>
157 #include <signal.h>
158 #include <errno.h>
159 #include <sys/types.h>
160 #include <sys/socket.h>
161 #include <sys/wait.h>
162 #include <netinet/in.h>
163 
164 
165 typedef int (*SOCKACTION_P)(int,struct sockaddr *,socklen_t);
166 #define DATA "Hello there sailor\n"
167 
myabort(char * m)168 void myabort (char *m) { fprintf(stderr, "%s\n", m); exit(1); }
sysabort(char * m)169 void sysabort (char *m) { perror(m); exit(1); }
170 
171 int sigchld = 0;
reaper(int sig)172 void reaper (int sig) { sigchld = 1; }
173 
174 int
genericSock(int port,SOCKACTION_P action,char * actionExceptionText)175 genericSock(int port,SOCKACTION_P action,char *actionExceptionText) {
176     int ss, optval = 1;
177     struct sockaddr_in sin;
178     if ((ss = socket(PF_INET, SOCK_STREAM, 0)) == -1)
179     sysabort("socket");
180     if (setsockopt(ss, SOL_SOCKET, SO_REUSEADDR, &optval, sizeof(optval)) ==
181 -1)
182     sysabort("setsockopt");
183     memset(&sin,0,sizeof(sin));
184     sin.sin_family = AF_INET;
185     sin.sin_addr.s_addr = htonl(INADDR_LOOPBACK);
186     sin.sin_port = port;
187     if (action(ss, (struct sockaddr *)&sin,(socklen_t)sizeof(sin)) == -1)
188     sysabort(actionExceptionText);
189 
190     return(ss);
191 }
192 
193 int
server_sock()194 server_sock () {
195     int ss = genericSock(0,(SOCKACTION_P)bind,"server/bind");
196     return(listen(ss,2),ss);
197 }
198 
199 int
client_sock(int port)200 client_sock (int port) {
201     return(genericSock(port,(SOCKACTION_P)connect,"client/connect"));
202 }
203 
204 int
get_port(int sock)205 get_port (int sock) {
206     struct sockaddr_in sin;
207     socklen_t slen = sizeof(sin);
208     if (getsockname(sock, (struct sockaddr *)&sin, &slen) == -1)
209     sysabort("server/getsockname");
210     return(sin.sin_port);
211 }
212 
213 void
echo_client(int n,int port)214 echo_client (int n, int port) {
215     int i, sock, olen, len, nwritten, nread;
216     char *offset, obuf[64], ibuf[64];
217     char *end = ibuf + sizeof(ibuf);
218 
219     sock = client_sock(port);
220     strcpy(obuf, DATA);
221     olen = strlen(obuf);
222     for (i=0; i<n; i++) {
223     len = olen;
224     offset = obuf;
225     while (len > 0) {
226         if ((nwritten = write(sock, offset, len)) == -1)
227         sysabort("client/write");
228         offset += nwritten;
229         len -= nwritten;
230     }
231     offset = ibuf;
232     while ((nread = read(sock, offset, (end - offset))) > 0) {
233         offset += nread;
234         if (*(offset-1) == '\n') break;
235     }
236     if (nread == -1)
237         sysabort("client/read");
238     *offset = 0;
239     if ((strcmp(obuf, ibuf)) != 0) {
240         char mbuf[128];
241         sprintf(mbuf, "client: \"%s\" ne \"%s\"", obuf, ibuf);
242         myabort(mbuf);
243     }
244     }
245     close(sock);
246 }
247 
248 void
echo_server(int n)249 echo_server (int n) {
250     int ssock, csock, len, nwritten, total_bytes;
251     pid_t pid;
252     char buf[64], *offset;
253     struct sockaddr_in sin;
254     socklen_t slen = sizeof(sin);
255     int status;
256 
257     ssock = server_sock();
258     signal(SIGCHLD, reaper);
259     if ((pid = fork()) == -1)
260     sysabort("server/fork");
261     if (pid) {
262 
263     if ((csock = accept(ssock, (struct sockaddr *)&sin, &slen)) == -1)
264         sysabort("server/accept");
265     total_bytes = 0;
266     while ((len = read(csock, buf, sizeof(buf))) > 0) {
267         if (sigchld) myabort("server/sigchld");
268         offset = buf;
269         total_bytes += len;
270         while (len > 0) {
271         if ((nwritten = write(csock, offset, len)) == -1)
272             sysabort("server/write");
273         offset += nwritten;
274         len -= nwritten;
275         }
276     }
277     if (len == -1)
278         sysabort("server/read");
279     close(csock);
280     fprintf(stdout, "server processed %d bytes\n", total_bytes);
281     } else {
282 
283     echo_client(n, get_port(ssock));
284     }
285     wait(&status);
286 }
287 
288 int
main(int argc,char * argv[])289 main(int argc, char *argv[]) {
290     echo_server((argc == 2) ? atoi(argv[1]) : 1);
291     return(0);
292 }
293 
294 
295 
296 Exception Mechanisms
297 
298 
299 
300 
301 /* -*- mode: c -*-
302  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
303  * http://www.bagley.org/~doug/shootout/
304  */
305 
306 #include <stdio.h>
307 #include <stdlib.h>
308 #include <setjmp.h>
309 
310 int HI = 0, LO = 0;
311 
312 static jmp_buf Hi_exception;
313 static jmp_buf Lo_exception;
314 
blowup(int n)315 void blowup (int n) {
316     if (n & 1) {
317     longjmp(Lo_exception, 1);
318     } else {
319     longjmp(Hi_exception, 1);
320     }
321 }
322 
lo_function(volatile int n)323 void lo_function (volatile int n) {
324     if (setjmp(Lo_exception) != 0) {
325     LO++;
326     } else {
327     blowup(n);
328     }
329 }
330 
hi_function(volatile int n)331 void hi_function (volatile int n) {
332     if (setjmp(Hi_exception) != 0) {
333     HI++;
334     } else {
335     lo_function(n);
336     }
337 }
338 
some_function(int n)339 void some_function (int n) {
340     hi_function(n);
341 }
342 
343 int
main(int argc,char * argv[])344 main(int argc, char *argv[]) {
345     int volatile N = ((argc == 2) ? atoi(argv[1]) : 1);
346 
347     while (N) {
348     some_function(N--);
349     }
350     printf("Exceptions: HI=%d / LO=%d\n", HI, LO);
351     return(0);
352 }
353 
354 
355 
356 Fibonacci Numbers
357 
358 
359 
360 
361 /* -*- mode: c -*-
362  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
363  * http://www.bagley.org/~doug/shootout/
364  */
365 
366 #include <stdio.h>
367 #include <stdlib.h>
368 
369 unsigned long
fib(unsigned long n)370 fib(unsigned long n) {
371     if (n < 2)
372     return(1);
373     else
374     return(fib(n-2) + fib(n-1));
375 }
376 
377 int
main(int argc,char * argv[])378 main(int argc, char *argv[]) {
379     int N = ((argc == 2) ? atoi(argv[1]) : 1);
380     printf("%ld\n", fib(N));
381     return(0);
382 }
383 
384 
385 
Hash(Associative Array)386 Hash (Associative Array) Access
387 
388 
389 
390 
391 /* -*- mode: c -*-
392  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
393  * http://www.bagley.org/~doug/shootout/
394  */
395 
396 #include <stdio.h>
397 #include <stdlib.h>
398 #include <unistd.h>
399 #include "simple_hash.h"
400 
401 int main(int argc, char *argv[]) {
402     int i, c=0, n = ((argc == 2) ? atoi(argv[1]) : 1);
403     char buf[32];
404 
405     struct ht_ht *ht = ht_create(n);
406 
407     for (i=1; i<=n; i++) {
408     sprintf(buf, "%x", i);
409     (ht_find_new(ht, buf))->val = i;
410     }
411 
412     for (i=n; i>0; i--) {
413     sprintf(buf, "%d", i);
414     if (ht_find(ht, buf)) c++;
415     }
416 
417     ht_destroy(ht);
418 
419     printf("%d\n", c);
420     return(0);
421 }
422 
423 
424 
425 Hashes, Part II
426 
427 
428 
429 
430 /* -*- mode: c -*-
431  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
432  * http://www.bagley.org/~doug/shootout/
433  */
434 
435 #include <stdio.h>
436 #include <stdlib.h>
437 #include <unistd.h>
438 #include "simple_hash.h"
439 
440 int main(int argc, char *argv[]) {
441     int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
442     char buf[32];
443     struct ht_ht *ht1 = ht_create(10000);
444     struct ht_ht *ht2 = ht_create(10000);
445     struct ht_node *node;
446 
447     for (i=0; i<=9999; ++i) {
448     sprintf(buf, "foo_%d", i);
449     ht_find_new(ht1, buf)->val = i;
450     }
451 
452     for (i=0; i<n; ++i) {
453     for (node=ht_first(ht1); node; node=ht_next(ht1)) {
454         ht_find_new(ht2, node->key)->val += node->val;
455     }
456     }
457 
458     printf("%d %d %d %d\n",
459        (ht_find(ht1, "foo_1"))->val,
460        (ht_find(ht1, "foo_9999"))->val,
461        (ht_find(ht2, "foo_1"))->val,
462        (ht_find(ht2, "foo_9999"))->val);
463 
464     ht_destroy(ht1);
465     ht_destroy(ht2);
466     return(0);
467 }
468 
469 
470 
471 Heapsort
472 
473 
474 
475 
476 /* -*- mode: c -*-
477  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
478  * http://www.bagley.org/~doug/shootout/
479  */
480 
481 #include <stdlib.h>
482 #include <math.h>
483 #include <stdio.h>
484 
485 #define IM 139968
486 #define IA   3877
487 #define IC  29573
488 
489 double
gen_random(double max)490 gen_random(double max) {
491     static long last = 42;
492     return( max * (last = (last * IA + IC) % IM) / IM );
493 }
494 
495 void
heapsort(int n,double * ra)496 heapsort(int n, double *ra) {
497     int i, j;
498     int ir = n;
499     int l = (n >> 1) + 1;
500     double rra;
501 
502     for (;;) {
503     if (l > 1) {
504         rra = ra[--l];
505     } else {
506         rra = ra[ir];
507         ra[ir] = ra[1];
508         if (--ir == 1) {
509         ra[1] = rra;
510         return;
511         }
512     }
513     i = l;
514     j = l << 1;
515     while (j <= ir) {
516         if (j < ir && ra[j] < ra[j+1]) { ++j; }
517         if (rra < ra[j]) {
518         ra[i] = ra[j];
519         j += (i = j);
520         } else {
521         j = ir + 1;
522         }
523     }
524     ra[i] = rra;
525     }
526 }
527 
528 int
main(int argc,char * argv[])529 main(int argc, char *argv[]) {
530     int N = ((argc == 2) ? atoi(argv[1]) : 1);
531     double *ary;
532     int i;
533 
534 
535     ary = (double *)malloc((N+1) * sizeof(double));
536     for (i=1; i<=N; i++) {
537     ary[i] = gen_random(1);
538     }
539 
540     heapsort(N, ary);
541 
542     printf("%.10g\n", ary[N]);
543 
544     free(ary);
545     return(0);
546 }
547 
548 
549 
550 
551 Hello World
552 
553 
554 
555 
556 /* -*- mode: c -*-
557  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
558  * http://www.bagley.org/~doug/shootout/
559  */
560 
561 #include <stdio.h>
562 
main()563 int main() {
564     fputs("hello world\n", stdout);
565     return(0);
566 }
567 
568 
569 
570 
571 List Operations
572 
573 
574 
575 
576 /* -*- mode: c -*-
577  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
578  * http://www.bagley.org/~doug/shootout/
579  */
580 
581 #include <stdio.h>
582 #include <stdlib.h>
583 #include <string.h>
584 #include <unistd.h>
585 
586 #define SIZE 10000
587 
588 // a simple Double Linked List
589 // the head node is special, it's val is length of list
590 typedef struct DLL {
591     int val;
592     struct DLL *next;
593     struct DLL *prev;
594 } DLL;
595 
list_length(DLL * head)596 inline int list_length(DLL *head) { return(head->val); }
list_empty(DLL * head)597 inline int list_empty(DLL *head) { return(list_length(head) == 0); }
list_first(DLL * head)598 inline DLL *list_first(DLL *head) { return(head->next); }
list_last(DLL * head)599 inline DLL *list_last(DLL *head) { return(head->prev); }
600 
list_push_tail(DLL * head,DLL * item)601 void list_push_tail(DLL *head, DLL *item) {
602     DLL *tail = head->prev;
603     tail->next = item;
604     item->next = head;
605     head->prev = item;
606     item->prev = tail;
607     head->val++;
608 }
609 
list_pop_tail(DLL * head)610 DLL *list_pop_tail(DLL *head) {
611     DLL *prev, *tail;
612     if (list_empty(head)) return(NULL);
613     tail = head->prev;
614     prev = tail->prev;
615     prev->next = head;
616     head->prev = prev;
617     head->val--;
618     return(tail);
619 }
620 
list_push_head(DLL * head,DLL * item)621 void list_push_head(DLL *head, DLL *item) {
622     DLL *next = head->next;
623     head->next = item;
624     next->prev = item;
625     item->next = next;
626     item->prev = head;
627     head->val++;
628 }
629 
list_pop_head(DLL * head)630 DLL *list_pop_head(DLL *head) {
631     DLL *next;
632     if (list_empty(head)) return(NULL);
633     next = head->next;
634     head->next = next->next;
635     next->next->prev = head;
636     head->val--;
637     return(next);
638 }
639 
list_equal(DLL * x,DLL * y)640 int list_equal(DLL *x, DLL *y) {
641     DLL *xp, *yp;
642     // first val's checked will be list lengths
643     for (xp=x, yp=y; xp->next != x; xp=xp->next, yp=yp->next) {
644     if (xp->val != yp->val) return(0);
645     }
646     if (xp->val != yp->val) return(0);
647     return(yp->next == y);
648 }
649 
list_print(char * msg,DLL * x)650 void list_print(char *msg, DLL *x) {
651     DLL *xp, *first = x->next;
652     int i = 0;
653     printf(msg);
654     printf("length: %d\n", list_length(x));
655     for (xp=x->next; xp->next != first; xp=xp->next) {
656     printf("i:%3d  v:%3d  n:%3d  p:%3d\n", ++i,
657            xp->val, xp->next->val, xp->prev->val);
658     }
659     printf("[last entry points to list head]\n");
660     printf("[val of next of tail is:  %d]\n", xp->next->val);
661 }
662 
list_new()663 DLL *list_new() {
664     DLL *l = (DLL *)malloc(sizeof(DLL));
665     l->next = l;
666     l->prev = l;
667     l->val = 0;
668     return(l);
669 }
670 
671 
list_sequence(int from,int to)672 DLL *list_sequence(int from, int to) {
673     int size, tmp, i, j;
674     DLL *l;
675     if (from > to) {
676     tmp = from; from = to; to = tmp;
677     }
678     size = to - from + 1;
679     l = (DLL *)malloc((size+1) * sizeof(DLL));
680     from--;
681     for (i=0, j=1; i<size; ++i, ++j) {
682     l[i].next = &l[i+1];
683     l[j].prev = &l[j-1];
684     l[i].val = from++;
685     }
686     l[0].prev = &l[size];
687     l[size].next = &l[0];
688     l[size].prev = &l[size-1];
689     l[size].val = from;
690     l[0].val = size;
691     return(l);
692 }
693 
list_copy(DLL * x)694 DLL *list_copy(DLL *x) {
695     int i, j, size = list_length(x);
696     DLL *xp, *l = (DLL *)malloc((size+1) * sizeof(DLL));
697     for (i=0, j=1, xp=x; i<size; i++, j++, xp=xp->next) {
698     l[i].next = &l[j];
699     l[j].prev = &l[i];
700     l[i].val = xp->val;
701     }
702     l[0].prev = &l[size];
703     l[size].next = &l[0];
704     l[size].val = list_last(x)->val;
705     return(l);
706 }
707 
list_reverse(DLL * head)708 void list_reverse (DLL *head) {
709     DLL *tmp, *p = head;
710     do {
711     tmp = p->next;
712     p->next = p->prev;
713     p->prev = tmp;
714     p = tmp;
715     } while (p != head);
716 }
717 
test_lists()718 int test_lists() {
719     int len = 0;
720     // create a list of integers (li1) from 1 to SIZE
721     DLL *li1 = list_sequence(1, SIZE);
722     // copy the list to li2
723     DLL *li2 = list_copy(li1);
724     // remove each individual item from left side of li2 and
725     // append to right side of li3 (preserving order)
726     DLL *li3 = list_new();
727     // compare li2 and li1 for equality
728     if (!list_equal(li2, li1)) {
729     fprintf(stderr, "li2 and li1 are not equal\n");
730     exit(1);
731     }
732     while (!list_empty(li2)) {
733     list_push_tail(li3, list_pop_head(li2));
734     }
735     // li2 must now be empty
736     if (!list_empty(li2)) {
737     fprintf(stderr, "li2 should be empty now\n");
738     exit(1);
739     }
740     // remove each individual item from right side of li3 and
741     // append to right side of li2 (reversing list)
742     while (!list_empty(li3)) {
743     list_push_tail(li2, list_pop_tail(li3));
744     }
745     // li3 must now be empty
746     if (!list_empty(li3)) {
747     fprintf(stderr, "li3 should be empty now\n");
748     exit(1);
749     }
750     // reverse li1 in place
751     list_reverse(li1);
752     // check that li1's first item is now SIZE
753     if (list_first(li1)->val != SIZE) {
754     fprintf(stderr, "li1 first value wrong, wanted %d, got %d\n",
755         SIZE, list_first(li1)->val);
756     exit(1);
757     }
758     // check that li1's last item is now 1
759     if (list_last(li1)->val != 1) {
760     fprintf(stderr, "last value wrong, wanted %d, got %d\n",
761         SIZE, list_last(li1)->val);
762     exit(1);
763     }
764     // check that li2's first item is now SIZE
765     if (list_first(li2)->val != SIZE) {
766     fprintf(stderr, "li2 first value wrong, wanted %d, got %d\n",
767         SIZE, list_first(li2)->val);
768     exit(1);
769     }
770     // check that li2's last item is now 1
771     if (list_last(li2)->val != 1) {
772     fprintf(stderr, "last value wrong, wanted %d, got %d\n",
773         SIZE, list_last(li2)->val);
774     exit(1);
775     }
776     // check that li1's length is still SIZE
777     if (list_length(li1) != SIZE) {
778     fprintf(stderr, "li1 size wrong, wanted %d, got %d\n",
779         SIZE, list_length(li1));
780     exit(1);
781     }
782     // compare li1 and li2 for equality
783     if (!list_equal(li1, li2)) {
784     fprintf(stderr, "li1 and li2 are not equal\n");
785     exit(1);
786     }
787     len = list_length(li1);
788     free(li1);
789     free(li2);
790     free(li3);
791     // return the length of the list
792     return(len);
793 }
794 
main(int argc,char * argv[])795 int main(int argc, char *argv[]) {
796     int n = ((argc == 2) ? atoi(argv[1]) : 1);
797     int result = 0;
798     while(n--) result = test_lists();
799     printf("%d\n", result);
800     return 0;
801 }
802 
803 
804 
805 Matrix Multiplication
806 
807 
808 
809 
810 /* -*- mode: c -*-
811  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
812  * http://www.bagley.org/~doug/shootout/
813  */
814 
815 #include <stdio.h>
816 #include <stdlib.h>
817 #include <unistd.h>
818 
819 #define SIZE 30
820 
mkmatrix(int rows,int cols)821 int **mkmatrix(int rows, int cols) {
822     int i, j, count = 1;
823     int **m = (int **) malloc(rows * sizeof(int *));
824     for (i=0; i<rows; i++) {
825     m[i] = (int *) malloc(cols * sizeof(int));
826     for (j=0; j<cols; j++) {
827         m[i][j] = count++;
828     }
829     }
830     return(m);
831 }
832 
zeromatrix(int rows,int cols,int ** m)833 void zeromatrix(int rows, int cols, int **m) {
834     int i, j;
835     for (i=0; i<rows; i++)
836     for (j=0; j<cols; j++)
837         m[i][j] = 0;
838 }
839 
freematrix(int rows,int ** m)840 void freematrix(int rows, int **m) {
841     while (--rows > -1) { free(m[rows]); }
842     free(m);
843 }
844 
mmult(int rows,int cols,int ** m1,int ** m2,int ** m3)845 int **mmult(int rows, int cols, int **m1, int **m2, int **m3) {
846     int i, j, k, val;
847     for (i=0; i<rows; i++) {
848     for (j=0; j<cols; j++) {
849         val = 0;
850         for (k=0; k<cols; k++) {
851         val += m1[i][k] * m2[k][j];
852         }
853         m3[i][j] = val;
854     }
855     }
856     return(m3);
857 }
858 
main(int argc,char * argv[])859 int main(int argc, char *argv[]) {
860     int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
861 
862     int **m1 = mkmatrix(SIZE, SIZE);
863     int **m2 = mkmatrix(SIZE, SIZE);
864     int **mm = mkmatrix(SIZE, SIZE);
865 
866     for (i=0; i<n; i++) {
867     mm = mmult(SIZE, SIZE, m1, m2, mm);
868     }
869     printf("%d %d %d %d\n", mm[0][0], mm[2][3], mm[3][2], mm[4][4]);
870 
871     freematrix(SIZE, m1);
872     freematrix(SIZE, m2);
873     freematrix(SIZE, mm);
874     return(0);
875 }
876 
877 
878 
879 Method Calls
880 
881 
882 
883 
884 /* -*- mode: c -*-
885  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
886  * http://www.bagley.org/~doug/shootout/
887  */
888 
889 #include <stdio.h>
890 #include <stdlib.h>
891 
892 #define true  1
893 #define false 0
894 
895 
896 #define TOGGLE \
897     char state; \
898     char (*value)(struct Toggle *); \
899     struct Toggle *(*activate)(struct Toggle *)
900 
901 #define DESTROY  free
902 
903 typedef struct Toggle {
904     TOGGLE;
905 } Toggle;
906 
toggle_value(Toggle * this)907 char toggle_value(Toggle *this) {
908     return(this->state);
909 }
toggle_activate(Toggle * this)910 Toggle *toggle_activate(Toggle *this) {
911     this->state = !this->state;
912     return(this);
913 }
init_Toggle(Toggle * this,char start_state)914 Toggle *init_Toggle(Toggle *this, char start_state) {
915     this->state = start_state;
916     this->value = toggle_value;
917     this->activate = toggle_activate;
918     return(this);
919 }
new_Toggle(char start_state)920 Toggle *new_Toggle(char start_state) {
921     Toggle *this = (Toggle *)malloc(sizeof(Toggle));
922     return(init_Toggle(this, start_state));
923 }
924 
925 
926 typedef struct NthToggle {
927     TOGGLE;
928     int count_max;
929     int counter;
930 } NthToggle;
931 
nth_toggle_activate(NthToggle * this)932 NthToggle *nth_toggle_activate(NthToggle *this) {
933     if (++this->counter >= this->count_max) {
934     this->state = !this->state;
935     this->counter = 0;
936     }
937     return(this);
938 }
init_NthToggle(NthToggle * this,int max_count)939 NthToggle *init_NthToggle(NthToggle *this, int max_count) {
940     this->count_max = max_count;
941     this->counter = 0;
942     this->activate = (Toggle *(*)(Toggle *))nth_toggle_activate;
943     return(this);
944 }
new_NthToggle(char start_state,int max_count)945 NthToggle *new_NthToggle(char start_state, int max_count) {
946     NthToggle *this = (NthToggle *)malloc(sizeof(NthToggle));
947     this = (NthToggle *)init_Toggle((Toggle *)this, start_state);
948     return(init_NthToggle(this, max_count));
949 }
950 
951 
main(int argc,char * argv[])952 int main(int argc, char *argv[]) {
953     int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
954     Toggle *tog;
955     NthToggle *ntog;
956     char val = true;
957 
958     tog = new_Toggle(true);
959     for (i=0; i<n; i++) {
960     val = tog->activate(tog)->value(tog);
961     }
962     fputs(val ? "true\n" : "false\n", stdout);
963     DESTROY(tog);
964 
965     val = true;
966     ntog = new_NthToggle(val, 3);
967     for (i=0; i<n; i++) {
968     val = ntog->activate(ntog)->value(ntog);
969     }
970     fputs(val ? "true\n" : "false\n", stdout);
971     DESTROY(ntog);
972     return 0;
973 }
974 
975 
976 
977 Nested Loops
978 
979 
980 
981 
982 /* -*- mode: c -*-
983  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
984  * http://www.bagley.org/~doug/shootout/
985  */
986 
987 #include <stdio.h>
988 #include <stdlib.h>
989 #include <unistd.h>
990 
991 int
main(int argc,char * argv[])992 main(int argc, char *argv[]) {
993     int n = ((argc == 2) ? atoi(argv[1]) : 1);
994     int a, b, c, d, e, f, x=0;
995 
996     for (a=0; a<n; a++)
997     for (b=0; b<n; b++)
998         for (c=0; c<n; c++)
999         for (d=0; d<n; d++)
1000             for (e=0; e<n; e++)
1001             for (f=0; f<n; f++)
1002                 x++;
1003 
1004     printf("%d\n", x);
1005     return(0);
1006 }
1007 
1008 
1009 
1010 Object Instantiation
1011 
1012 
1013 
1014 
1015 /* -*- mode: c -*-
1016  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1017  * http://www.bagley.org/~doug/shootout/
1018  */
1019 
1020 #include <stdio.h>
1021 #include <stdlib.h>
1022 
1023 
1024 enum {false, true};
1025 
1026 #define TOGGLE \
1027     char state; \
1028     char (*value)(struct Toggle *); \
1029     struct Toggle *(*activate)(struct Toggle *)
1030 
1031 #define DESTROY  free
1032 
1033 typedef struct Toggle {
1034     TOGGLE;
1035 } Toggle;
1036 
toggle_value(Toggle * this)1037 char toggle_value(Toggle *this) {
1038     return(this->state);
1039 }
toggle_activate(Toggle * this)1040 Toggle *toggle_activate(Toggle *this) {
1041     this->state = !this->state;
1042     return(this);
1043 }
init_Toggle(Toggle * this,char start_state)1044 Toggle *init_Toggle(Toggle *this, char start_state) {
1045     this->state = start_state;
1046     this->value = toggle_value;
1047     this->activate = toggle_activate;
1048     return(this);
1049 }
new_Toggle(char start_state)1050 Toggle *new_Toggle(char start_state) {
1051     Toggle *this = (Toggle *)malloc(sizeof(Toggle));
1052     return(init_Toggle(this, start_state));
1053 }
1054 
1055 
1056 typedef struct NthToggle {
1057     TOGGLE;
1058     int count_max;
1059     int counter;
1060 } NthToggle;
1061 
nth_toggle_activate(NthToggle * this)1062 NthToggle *nth_toggle_activate(NthToggle *this) {
1063     if (++this->counter >= this->count_max) {
1064     this->state = !this->state;
1065     this->counter = 0;
1066     }
1067     return(this);
1068 }
init_NthToggle(NthToggle * this,int max_count)1069 NthToggle *init_NthToggle(NthToggle *this, int max_count) {
1070     this->count_max = max_count;
1071     this->counter = 0;
1072     this->activate = (Toggle *(*)(Toggle *))nth_toggle_activate;
1073     return(this);
1074 }
new_NthToggle(char start_state,int max_count)1075 NthToggle *new_NthToggle(char start_state, int max_count) {
1076     NthToggle *this = (NthToggle *)malloc(sizeof(NthToggle));
1077     this = (NthToggle *)init_Toggle((Toggle *)this, start_state);
1078     return(init_NthToggle(this, max_count));
1079 }
1080 
1081 
main(int argc,char * argv[])1082 int main(int argc, char *argv[]) {
1083     int i, n = ((argc == 2) ? atoi(argv[1]) : 1);
1084     Toggle *tog;
1085     NthToggle *ntog;
1086 
1087     tog = new_Toggle(true);
1088     for (i=0; i<5; i++) {
1089     fputs((tog->activate(tog)->value(tog)) ? "true\n" : "false\n", stdout);
1090     }
1091     DESTROY(tog);
1092     for (i=0; i<n; i++) {
1093     tog = new_Toggle(true);
1094     DESTROY(tog);
1095     }
1096 
1097     fputs("\n", stdout);
1098 
1099     ntog = new_NthToggle(true, 3);
1100     for (i=0; i<8; i++) {
1101     fputs((ntog->activate(ntog)->value(ntog)) ? "true\n" : "false\n",
1102 stdout);
1103     }
1104     DESTROY(ntog);
1105     for (i=0; i<n; i++) {
1106     ntog = new_NthToggle(true, 3);
1107     DESTROY(ntog);
1108     }
1109     return 0;
1110 }
1111 
1112 
1113 
1114 Producer/Consumer Threads
1115 
1116 
1117 
1118 
1119 /* -*- mode: c -*-
1120  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1121  * http://www.bagley.org/~doug/shootout/
1122  */
1123 
1124 #include <stdio.h>
1125 #include <stdlib.h>
1126 #include <string.h>
1127 #include <unistd.h>
1128 #include <signal.h>
1129 #include <errno.h>
1130 #include <sys/types.h>
1131 #include <pthread.h>
1132 
1133 pthread_mutex_t mutex;
1134 pthread_cond_t control;
1135 void producer(unsigned int *arg);
1136 void consumer(unsigned int *arg);
1137 unsigned int count, data, consumed, produced;
1138 
1139 
1140 int
main(int argc,char * argv[])1141 main(int argc, char *argv[]) {
1142     unsigned int n = ((argc == 2) ? atoi(argv[1]) : 1);
1143     pthread_t t1, t2;
1144 
1145     count = data = consumed = produced = 0;
1146 
1147     if (pthread_mutex_init(&mutex, NULL)) {
1148     perror("pthread_mutex_init");
1149     exit(1);
1150     }
1151     if (pthread_cond_init(&control, NULL)) {
1152     perror("pthread_cond_init");
1153     exit(1);
1154     }
1155     if (pthread_create(&t1, (pthread_attr_t *)NULL,
1156                (void * (*)(void *))producer, (void *)&n)) {
1157     perror("pthread_create");
1158     exit(1);
1159     }
1160     if (pthread_create(&t2, (pthread_attr_t *)NULL,
1161                (void * (*)(void *))consumer, (void *)&n)) {
1162     perror("pthread_create");
1163     exit(1);
1164     }
1165 
1166     pthread_join(t1, NULL);
1167     pthread_join(t2, NULL);
1168     fprintf(stdout, "%d %d\n", produced, consumed);
1169     return(0);
1170 }
1171 
1172 
producer(unsigned int * arg)1173 void producer(unsigned int *arg) {
1174     unsigned int i, n = *arg;
1175     for (i=1; i<=n; i++) {
1176     pthread_mutex_lock(&mutex);
1177     while (count == 1) {
1178         pthread_cond_wait(&control, &mutex);
1179     }
1180     data = i;
1181     count = 1;
1182     pthread_cond_signal(&control);
1183     pthread_mutex_unlock(&mutex);
1184     produced++;
1185     }
1186 }
1187 
1188 
consumer(unsigned int * arg)1189 void consumer(unsigned int *arg) {
1190     unsigned int i = 0, n = *arg;
1191     while (1) {
1192     pthread_mutex_lock(&mutex);
1193     while (count == 0) {
1194         pthread_cond_wait(&control, &mutex);
1195     }
1196     i = data;
1197     count = 0;
1198     pthread_cond_signal(&control);
1199     pthread_mutex_unlock(&mutex);
1200     consumed++;
1201     if (i == n) return;
1202     }
1203 }
1204 
1205 
1206 
1207 
1208 Random Number Generator
1209 
1210 
1211 
1212 
1213 /* -*- mode: c -*-
1214  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1215  * http://www.bagley.org/~doug/shootout/
1216  */
1217 
1218 #include <math.h>
1219 #include <stdio.h>
1220 #include <stdlib.h>
1221 
1222 #define IM 139968
1223 #define IA 3877
1224 #define IC 29573
1225 
1226 double
gen_random(double max)1227 gen_random(double max) {
1228     static long last = 42;
1229 
1230     last = (last * IA + IC) % IM;
1231     return( max * last / IM );
1232 }
1233 
1234 int
main(int argc,char * argv[])1235 main(int argc, char *argv[]) {
1236     int N = ((argc == 2) ? atoi(argv[1]) : 1);
1237     double result = 0;
1238 
1239     while (N--) {
1240     result = gen_random(100.0);
1241     }
1242     printf("%.9f\n", result);
1243     return(0);
1244 }
1245 
1246 
1247 
1248 Regular Expression Matching
1249 
1250 
1251 
1252 
1253 /* -*- mode: c -*-
1254  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1255  * http://www.bagley.org/~doug/shootout/
1256  */
1257 
1258 #include <sys/types.h>
1259 #include <sys/stat.h>
1260 #include <fcntl.h>
1261 #include <stdio.h>
1262 #include <pcre.h>
1263 #include <string.h>
1264 
1265 #define MAXLINES   100
1266 #define MAXLINELEN 132
1267 
1268 char *pattern =
1269 "(?:^|[^\\d\\(])"
1270 "(\\()?"
1271 "(\\d\\d\\d)"
1272 "(?(1)\\))"
1273 "[ ]"
1274 "(\\d\\d\\d)"
1275 "[ -]"
1276 "(\\d\\d\\d\\d)"
1277 "\\D"
1278 ;
1279 
1280 
1281 int
main(int argc,char * argv[])1282 main(int argc, char *argv[]) {
1283     int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
1284     int count;
1285     char *cptr = "";
1286     char **phones;
1287     pcre *re;
1288     int erroffset;
1289     const char *errptr;
1290     int n, lines = 0;
1291     char num[256];
1292     int i, j, k, matchlen;
1293     char *matchoffset;
1294     int nmatches;
1295     int *ovec, ovecsize;
1296     pcre_extra *study;
1297 
1298     phones = (char **)malloc(MAXLINES * sizeof(char *));
1299     if (!phones) {
1300     fprintf(stderr, "malloc for phones array failed\n");
1301     exit(1);
1302     }
1303     lines = 0;
1304     while (cptr) {
1305     phones[lines] = (char *)malloc(MAXLINELEN);
1306     if (!phones[lines]) {
1307         fprintf(stderr, "malloc to hold line #%d failed\n", lines);
1308         exit(1);
1309     }
1310     cptr = fgets(phones[lines], MAXLINELEN, stdin);
1311     lines++;
1312     if (lines > MAXLINES) {
1313         fprintf(stderr, "MAXLINES is too small\n");
1314         exit(1);
1315     }
1316     }
1317 
1318     re = pcre_compile(pattern, 0, &errptr, &erroffset, NULL);
1319     if (!re) {
1320     fprintf(stderr, "can't open compile regexp\n");
1321     exit(1);
1322     }
1323 
1324     study = pcre_study(re, 0, &errptr);
1325 
1326     if (pcre_fullinfo(re, NULL, PCRE_INFO_CAPTURECOUNT, &nmatches) != 0) {
1327     fprintf(stderr, "pcre_fullinfo failed\n");
1328     exit(1);
1329     }
1330     nmatches++;
1331 
1332     ovecsize = sizeof(int) * nmatches * 3;
1333     ovec = (int *)malloc(ovecsize);
1334     if (!ovec) {
1335     fprintf(stderr, "malloc for ovec array failed\n");
1336     exit(1);
1337     }
1338 
1339     count = 0;
1340     while (NUM--) {
1341     for (i=0; i<lines; i++) {
1342         n = pcre_exec(re, study,
1343               phones[i], strlen(phones[i]), 0,
1344               0, ovec, ovecsize);
1345         if (n == nmatches) {
1346 
1347         k = 2*2;
1348 
1349         j = 0;
1350         num[j++] = '(';
1351         matchoffset = phones[i] + ovec[k];
1352         matchlen = ovec[k+1] - ovec[k];
1353         strncpy(num+j, matchoffset, matchlen);
1354         j += matchlen; k += 2;
1355         num[j++] = ')';
1356 
1357         num[j++] = ' ';
1358 
1359         matchoffset = phones[i] + ovec[k];
1360         matchlen = ovec[k+1] - ovec[k];
1361         strncpy(num+j, matchoffset, matchlen);
1362         j += matchlen; k += 2;
1363 
1364         num[j++] = '-';
1365 
1366         matchoffset = phones[i] + ovec[k];
1367         matchlen = ovec[k+1] - ovec[k];
1368         strncpy(num+j, matchoffset, matchlen);
1369         j += matchlen; k += 2;
1370 
1371         num[j] = 0;
1372         if (0 == NUM) {
1373             count++;
1374             printf("%d: %s\n", count, num);
1375         }
1376         }
1377     }
1378     }
1379 
1380     for (i=0; i<MAXLINES; i++) {
1381     free(phones[i]);
1382     }
1383     free(phones);
1384     free(ovec);
1385 
1386     return(0);
1387 }
1388 
1389 
1390 
1391 
1392 Reverse a File
1393 
1394 
1395 
1396 
1397 /* -*- mode: c -*-
1398  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1399  * http://www.bagley.org/~doug/shootout/
1400  */
1401 
1402 #include <stdio.h>
1403 #include <stdlib.h>
1404 #include <string.h>
1405 #include <unistd.h>
1406 
1407 #define MAXREAD 4096
1408 
main(int argc,char * argv[])1409 int main(int argc, char *argv[]) {
1410     int nread, len = 0, size = (4 * MAXREAD);
1411     char *cp, *offset, *buf = malloc(size + 1);
1412 
1413     while (1) {
1414     if ((nread = read(0, (buf + len), MAXREAD)) > 0) {
1415         len += nread;
1416         if (MAXREAD > (size - len)) {
1417         size <<= 1;
1418         if (0 == (buf = realloc(buf, size + 1))) {
1419             fprintf(stderr, "realloc failed\n");
1420             exit(1);
1421         }
1422         }
1423     } else {
1424         if ( 0 == nread) break;
1425         if (-1 == nread) {
1426         perror("read");
1427         exit(1);
1428         }
1429     }
1430     }
1431     offset = buf + len;
1432     *offset = 0;
1433     for (cp = offset; cp > buf; --cp) {
1434     if ('\n' == *cp) {
1435         *offset = 0;
1436         if (cp < offset)
1437         fputs(offset = cp+1, stdout);
1438     }
1439     }
1440     if (cp < offset) {
1441     *offset = 0;
1442     fputs(cp, stdout);
1443     }
1444     free(buf);
1445     return(0);
1446 }
1447 
1448 
1449 
1450 Sieve of Erathostenes
1451 
1452 
1453 
1454 
1455 /* -*- mode: c -*-
1456  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1457  * http://www.bagley.org/~doug/shootout/
1458  */
1459 
1460 #include <stdio.h>
1461 #include <stdlib.h>
1462 
1463 int
main(int argc,char * argv[])1464 main(int argc, char *argv[]) {
1465     int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
1466     static char flags[8192 + 1];
1467     long i, k;
1468     int count = 0;
1469 
1470     while (NUM--) {
1471     count = 0;
1472     for (i=2; i <= 8192; i++) {
1473         flags[i] = 1;
1474     }
1475     for (i=2; i <= 8192; i++) {
1476         if (flags[i]) {
1477         // remove all multiples of prime: i
1478         for (k=i+i; k <= 8192; k+=i) {
1479             flags[k] = 0;
1480         }
1481         count++;
1482         }
1483     }
1484     }
1485     printf("Count: %d\n", count);
1486     return(0);
1487 }
1488 
1489 
1490 
1491 
1492 Spell Checker
1493 
1494 
1495 
1496 
1497 /* -*- mode: c -*-
1498  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1499  * http://www.bagley.org/~doug/shootout/
1500  * with help from Brad Knotwell
1501  */
1502 
1503 #include <ctype.h>
1504 #include <stdio.h>
1505 #include <stdlib.h>
1506 #include <unistd.h>
1507 #include "simple_hash.h"
1508 
1509 #define MAXLINELEN 128
1510 
1511 struct ht_ht *dict = NULL;
1512 
handleInput(FILE * input,void (* hashManipFn)(char *))1513 int handleInput(FILE *input,void (*hashManipFn)(char *))
1514 {
1515     int wordbufsize = 80,i = 0;
1516     char *cp, *wordbuf = (char *)malloc(wordbufsize + 1);
1517     char line[MAXLINELEN];
1518 
1519     if((wordbuf = malloc(wordbufsize+1)) == NULL)
1520         return(fprintf(stderr,"malloc\n"),0);
1521 
1522     while (fgets(line, MAXLINELEN, input))
1523     for (cp=line; *cp > 0; cp++) {
1524         if (isspace(*cp)) {
1525         if (i) {
1526             wordbuf[i] = '\0';
1527                     hashManipFn(wordbuf);
1528             i = 0;
1529         }
1530         } else {
1531         wordbuf[i++] = *cp;
1532         if (i == wordbufsize) {
1533             wordbufsize *= 2;
1534             if((wordbuf = realloc(wordbuf, wordbufsize + 1)) == NULL)
1535                         return(fprintf(stderr, "realloc\n"), 0);
1536         }
1537         }
1538         }
1539 
1540     free(wordbuf);
1541     return(1);
1542 }
1543 
spellCheck(char * key)1544 void spellCheck(char *key) {
1545     if (ht_find_new(dict,key)->val != 1) printf("%s\n",key);
1546 }
1547 
hashLoad(char * key)1548 void hashLoad(char *key) { ht_find_new(dict,key)->val = 1; }
1549 
main(int argc,char * argv[])1550 int main(int argc, char *argv[]) {
1551     FILE *fh;
1552     int rc;
1553 
1554     /*
1555         ht_create doesn't handle malloc and calloc failures
1556         so this is superfluous
1557     */
1558     if((dict = ht_create(40000)) == NULL)
1559         return(fprintf(stderr,"hash creation failed\n"),EXIT_FAILURE);
1560 
1561     if ((fh = fopen("Usr.Dict.Words", "r")) == NULL)
1562         return(fprintf(stderr,"couldn't open dictionary\n"),EXIT_FAILURE);
1563 
1564     rc = ((handleInput(fh,hashLoad) && handleInput(stdin,spellCheck)) ?
1565 EXIT_SUCCESS : EXIT_FAILURE);
1566 
1567     ht_destroy(dict);
1568     return(rc);
1569 }
1570 
1571 
1572 
1573 Statistical Moments
1574 
1575 
1576 
1577 
1578 /* -*- mode: c -*-
1579  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1580  * http://www.bagley.org/~doug/shootout/
1581  */
1582 
1583 #include <stdio.h>
1584 #include <stdlib.h>
1585 #include <math.h>
1586 
1587 #define MAXLINELEN 128
1588 
1589 int
compare_doubles(const double * a,const double * b)1590 compare_doubles (const double *a, const double *b) {
1591     return (int) (*a - *b);
1592 }
1593 
1594 
1595 int
main()1596 main() {
1597     char line[MAXLINELEN];
1598     int i, n = 0, mid = 0;
1599     double sum = 0.0;
1600     double mean = 0.0;
1601     double average_deviation = 0.0;
1602     double standard_deviation = 0.0;
1603     double variance = 0.0;
1604     double skew = 0.0;
1605     double kurtosis = 0.0;
1606     double median = 0.0;
1607     double deviation = 0.0;
1608     int array_size = 4096;
1609 
1610     double *nums = (double *)malloc(array_size * sizeof(double));
1611 
1612     while (fgets(line, MAXLINELEN, stdin)) {
1613     sum += (nums[n++] = atof(line));
1614     if (n == array_size) {
1615         array_size *= 2;
1616         nums = (double *)realloc(nums, array_size * sizeof(double));
1617     }
1618     }
1619     mean = sum/n;
1620     for (i=0; i<n; i++) {
1621     deviation = nums[i] - mean;
1622     average_deviation += fabs(deviation);
1623     variance += pow(deviation,2);
1624     skew += pow(deviation,3);
1625     kurtosis += pow(deviation,4);
1626     }
1627     average_deviation /= n;
1628     variance /= (n - 1);
1629     standard_deviation = sqrt(variance);
1630     if (variance) {
1631     skew /= (n * variance * standard_deviation);
1632     kurtosis = (kurtosis/(n * variance * variance)) - 3.0;
1633     }
1634 
1635     qsort(nums, n, sizeof (double),
1636       (int (*)(const void *, const void *))compare_doubles);
1637     mid = (n/2);
1638     median = n % 2 ? nums[mid] : (nums[mid] + nums[mid-1])/2;
1639 
1640     free(nums);
1641 
1642     printf("n:                  %d\n", n);
1643     printf("median:             %f\n", median);
1644     printf("mean:               %f\n", mean);
1645     printf("average_deviation:  %f\n", average_deviation);
1646     printf("standard_deviation: %f\n", standard_deviation);
1647     printf("variance:           %f\n", variance);
1648     printf("skew:               %f\n", skew);
1649     printf("kurtosis:           %f\n", kurtosis);
1650     return(0);
1651 }
1652 
1653 
1654 
1655 String Concatenation
1656 
1657 
1658 
1659 
1660 /* -*- mode: c -*-
1661  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1662  * http://www.bagley.org/~doug/shootout/
1663  */
1664 
1665 #include <stdio.h>
1666 #include <stdlib.h>
1667 #include <string.h>
1668 #include <unistd.h>
1669 
1670 #define STUFF "hello\n"
1671 
1672 int
main(int argc,char * argv[])1673 main(int argc, char *argv[]) {
1674     int n = ((argc == 2) ? atoi(argv[1]) : 1);
1675     int i, buflen = 32;
1676     char *strbuf = calloc(sizeof(char), buflen);
1677     char *strend = strbuf;
1678     int stufflen = strlen(STUFF);
1679 
1680     if (!strbuf) { perror("calloc strbuf"); exit(1); }
1681     for (i=0; i<n; i++) {
1682     if (((strbuf+buflen)-strend) < (stufflen+1)) {
1683         buflen = 2*buflen;
1684         strbuf = realloc(strbuf, buflen);
1685         if (!strbuf) { perror("realloc strbuf"); exit(1); }
1686         strend = strbuf + strlen(strbuf);
1687     }
1688 
1689     strcat(strend, STUFF);
1690     strend += stufflen;
1691     }
1692     fprintf(stdout, "%d\n", strlen(strbuf));
1693     free(strbuf);
1694 
1695     return(0);
1696 }
1697 
1698 
1699 
1700 Sum a Column of Integers
1701 
1702 
1703 
1704 
1705 /* -*- mode: c -*-
1706  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1707  * http://www.bagley.org/~doug/shootout/
1708  */
1709 
1710 #include <stdio.h>
1711 #include <stdlib.h>
1712 
1713 #define MAXLINELEN 128
1714 
1715 int
main()1716 main() {
1717     int sum = 0;
1718     char line[MAXLINELEN];
1719 
1720     while (fgets(line, MAXLINELEN, stdin)) {
1721     sum += atoi(line);
1722     }
1723     printf("%d\n", sum);
1724     return(0);
1725 }
1726 
1727 
1728 
1729 
1730 Word Frequency Count
1731 
1732 
1733 
1734 
1735 /* -*- mode: c -*-
1736  * $Id: bench.c,v 1.1 2002/06/05 20:34:46 michael Exp $
1737  * http://www.bagley.org/~doug/shootout/
1738  */
1739 
1740 #include <stdio.h>
1741 #include <ctype.h>
1742 #include <malloc.h>
1743 #include <stdlib.h>
1744 #include <string.h>
1745 #include "simple_hash.h"
1746 
1747 typedef int (*comparator)(const void *, const void *);
1748 
cmp_hash(struct ht_node ** a,struct ht_node ** b)1749 int cmp_hash(struct ht_node **a, struct ht_node **b) {
1750     int val = (*b)->val - (*a)->val;
1751     return((val == 0) ? strcmp((*b)->key, (*a)->key) : val);
1752 }
1753 
main()1754 int main() {
1755     int bufsize = 80;
1756     char *buf = (char *)malloc(bufsize + 1);
1757     char c;
1758     int i = 0;
1759     struct ht_ht *ht = ht_create(75000);
1760     struct ht_node **sort_array, **sort_tmp, *node;
1761 
1762     while ((c = getchar()) > 0) {
1763         if (isalpha(c)) {
1764             buf[i++] = tolower(c);
1765         if (i == bufsize) {
1766         bufsize *= 2;
1767         buf = realloc(buf, bufsize + 1);
1768         }
1769         } else {
1770         if (i > 0) {
1771         buf[i] = '\0';
1772         ++(ht_find_new(ht, buf)->val);
1773         i = 0;
1774         }
1775         }
1776     }
1777     free(buf);
1778 
1779     sort_array = sort_tmp =
1780     malloc(sizeof(struct ht_node *) * ht_count(ht));
1781 
1782     for (node=ht_first(ht); (*sort_tmp++ = node) != 0; node=ht_next(ht)) ;
1783 
1784     qsort(sort_array, ht_count(ht), sizeof(struct ht_node *),
1785       (comparator)cmp_hash);
1786 
1787     for (i=0; i<ht_count(ht); i++)
1788     printf("%7d\t%s\n", ht_val(sort_array[i]), ht_key(sort_array[i]));
1789 
1790     ht_destroy(ht);
1791     return(0);
1792 }
1793