# HG changeset patch
# User kent <kent@cr.ie.u-ryukyu.ac.jp>
# Date 1255489971 -32400
# Node ID 775dfe89866275a860795162195fd89b1440e612
# Parent  0eb6cac880f0ddc0cc2ea27a871b8aa9bcabed19
add quicksort version 2.

diff -r 0eb6cac880f0 -r 775dfe898662 CbC-examples/quicksort/Makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CbC-examples/quicksort/Makefile	Wed Oct 14 12:12:51 2009 +0900
@@ -0,0 +1,30 @@
+CbCC=../../../build_cbc44/INSTALL_DIR/bin/gcc
+CC=gcc
+HEADERMAKER=../../CbC-scripts/make_headers.py
+
+CFLAGS=-g -O2
+
+.SUFFIXES: .cbc .o
+
+all: quicksort_cbc quicksort_c quicksort_cbc2
+
+.cbc.o:
+	$(CbCC) $(CFLAGS) -c -o $@ $<
+.cbc.h:
+	$(HEADERMAKER) $^ > $@
+
+quicksort_cbc.o: quicksort_cbc.h
+quicksort_cbc2.o: quicksort_cbc2.h
+quicksort_test.o: quicksort_test.h
+
+quicksort_cbc: quicksort_cbc.o quicksort_test.o
+	$(CC) -o $@ $^
+quicksort_cbc2: quicksort_cbc2.o quicksort_test.o
+	$(CC) -o $@ $^
+
+quicksort_c: quicksort_c.o
+	$(CC) -o $@ $^
+
+
+clean: 
+	rm -rf *.o quicksort_c quicksort_cbc
diff -r 0eb6cac880f0 -r 775dfe898662 CbC-examples/quicksort/quicksort_c.c
--- a/CbC-examples/quicksort/quicksort_c.c	Tue Oct 13 17:15:58 2009 +0900
+++ b/CbC-examples/quicksort/quicksort_c.c	Wed Oct 14 12:12:51 2009 +0900
@@ -147,15 +147,15 @@
 	int loop=1;
 	int opt, i;
 
-	while ((opt = getopt(argc, argv, "r:s:n:")) != -1) {
+	while ((opt = getopt(argc, argv, "t:s:n:")) != -1) {
 		switch (opt) {
-			case 's':
+			case 'n':
 				size = atoi(optarg);
 				break;
-			case 'n':
+			case 't':
 				loop = atoi(optarg);
 				break;
-			case 'r':
+			case 's':
 				seed = atoi(optarg);
 				break;
 			default:
diff -r 0eb6cac880f0 -r 775dfe898662 CbC-examples/quicksort/quicksort_cbc.cbc
--- a/CbC-examples/quicksort/quicksort_cbc.cbc	Tue Oct 13 17:15:58 2009 +0900
+++ b/CbC-examples/quicksort/quicksort_cbc.cbc	Wed Oct 14 12:12:51 2009 +0900
@@ -23,7 +23,7 @@
 {
 	framep fp = (framep)sp;
 	sp += fp->size;
-	fp->code(fp->interface, sp);
+	goto fp->code(fp->interface, sp);
 }
 
 __code quicksort_start(void *arg, stack sp)
@@ -118,6 +118,7 @@
 }
 /* recursive call routine end. */
 
+#define STACK_SIZE 10240
 int v[100];
 struct qs_if *outif;
 
@@ -130,14 +131,14 @@
 quicksort(int *v, int s, int e,  RET ret, void *arg )
 {
 	framep fp;
-	stack sp = malloc(10240)+10240;
+	stack sp = malloc(STACK_SIZE)+STACK_SIZE;
 	struct qs *finish_if;
 	
 	/* interface for quicksort_finish.  */
 	finish_if = (sp -= sizeof(*finish_if));
 	finish_if->ret = ret;
 	finish_if->ret_arg = arg;
-	finish_if->sp = sp -10240 + sizeof(*finish_if);
+	finish_if->sp = sp -STACK_SIZE + sizeof(*finish_if);
 
 	/* interface for quicksort_start.  */
 	outif = (sp -= sizeof(*outif));
diff -r 0eb6cac880f0 -r 775dfe898662 CbC-examples/quicksort/quicksort_cbc2.cbc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CbC-examples/quicksort/quicksort_cbc2.cbc	Wed Oct 14 12:12:51 2009 +0900
@@ -0,0 +1,159 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<assert.h>
+
+typedef struct {
+	int *v;
+	int s;
+	int e;
+} QS_IF;
+
+typedef void *stack;
+typedef __code (*RET)(QS_IF, stack);
+typedef struct {
+	int size;
+	QS_IF interface;
+	RET code;
+} frame, *framep;
+
+typedef __code (*RETTYPE)(void*);
+typedef struct {
+	RETTYPE ret;
+	void *ret_arg;
+	stack *sp;
+} QS_FINISH;
+#define STACK_SIZE 10240
+
+#include"quicksort_cbc2.h"
+
+__code returner(stack sp)
+{
+	framep fp = (framep)sp;
+	sp += fp->size;
+	goto fp->code(fp->interface, sp);
+}
+
+__code quicksort_start(QS_IF recvif, stack sp)
+{
+	int a,b,c,p;
+	a = recvif.v[recvif.s];
+	b = recvif.v[recvif.e];
+	c = recvif.v[(recvif.s+recvif.e)/2];
+
+	//printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
+	if (recvif.e <= recvif.s) goto returner(sp);
+
+	if (a < b) {
+		if (b < c)
+			p = b;
+		else if (a < c)
+			p = c;
+		else 
+			p = a;
+	} else {
+		if (a < c)
+			p = a;
+		else if (b < c)
+			p = c;
+		else 
+			p = b;
+	}
+
+	goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp);
+}
+/* main routine end. */
+
+/* divide routine. */
+__code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp)
+{
+	goto quicksort_divider_s(recvif, s, e, p, sp);
+}
+__code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp)
+{
+	if (recvif.v[s]<p) {
+		s++;
+		goto quicksort_divider_s(recvif, s, e, p, sp);
+	} else
+		goto quicksort_divider_e(recvif, s, e, p, sp);
+}
+__code quicksort_divider_e(QS_IF recvif, int s, int e, int p, stack sp)
+{
+	if (p<recvif.v[e]) {
+		e--;
+		goto quicksort_divider_e(recvif, s, e, p, sp);
+	} else
+		goto quicksort_swapper(recvif, s, e, p, sp);
+}
+__code quicksort_swapper(QS_IF recvif, int s, int e, int p, stack sp)
+{
+	if (s<e) {
+		int tmp;
+		tmp = recvif.v[s];
+		recvif.v[s] = recvif.v[e];
+		recvif.v[e] = tmp;
+		s++;
+		e--;
+		goto quicksort_divider(recvif, s, e, p, sp);
+	} else {
+		assert(e+1==s || s==e);
+		goto quicksort_treecall(recvif, s, e, sp);
+	}
+}
+/* divide routin end. */
+
+
+/* recursive call routine. */
+__code quicksort_treecall(QS_IF recvif, int s, int e, stack sp)
+{
+	framep fp;
+
+	/* interface for first quicksort_start this segment directly jump to.  */
+	fp = (sp-=sizeof(frame));
+	fp->code = quicksort_start;
+	fp->size = sizeof(frame);
+	fp->interface.v = recvif.v;
+	fp->interface.s = e+1;
+	fp->interface.e = recvif.e;
+
+	/* recvif is used by second quicksort_start.  */
+	recvif.e = e;
+	goto quicksort_start(recvif, sp);
+}
+/* recursive call routine end. */
+
+__code
+quicksort(int *v, int s, int e,  RETTYPE ret, void *arg )
+{
+	framep fp;
+	stack sp0, sp;
+	sp0 = malloc(STACK_SIZE);
+	printf("allocate a stack %p\n", sp0);
+	sp = sp0 + STACK_SIZE;
+	QS_FINISH *finish_if;
+	
+	/* interface for quicksort_finish.  */
+	finish_if = (sp -= sizeof(*finish_if));
+	finish_if->ret = ret;
+	finish_if->ret_arg = arg;
+	finish_if->sp = sp0;
+
+	/* interface for quicksort_start.  */
+	/* frame for quicksort_finish.  */
+	fp = (sp -= sizeof(frame));
+	fp->code = quicksort_finish;
+	fp->size = sizeof(frame);
+	fp->interface.v = v;
+	fp->interface.s = s;
+	fp->interface.e = e;
+
+	goto quicksort_start(fp->interface, sp);
+}
+__code
+quicksort_finish(QS_IF recvif, stack sp)
+{
+	QS_FINISH *interface = (QS_FINISH*)sp;
+	free(interface->sp);
+	printf("free the stack %p\n", interface->sp);
+	goto interface->ret(interface->ret_arg);
+}
+
diff -r 0eb6cac880f0 -r 775dfe898662 CbC-examples/quicksort/quicksort_test.cbc
--- a/CbC-examples/quicksort/quicksort_test.cbc	Tue Oct 13 17:15:58 2009 +0900
+++ b/CbC-examples/quicksort/quicksort_test.cbc	Wed Oct 14 12:12:51 2009 +0900
@@ -5,6 +5,9 @@
 
 #include"quicksort_test.h"
 
+extern __code quicksort(int *,int,int, __code(*)(void*), void*);
+
+
 void
 random_initialize(int *v, int size, int min, int max)
 {
@@ -29,10 +32,9 @@
 }
 
 void
-starter()
+starter(int size)
 {
 	int *target;
-	int size=100;
 
 	target = (int*)malloc(sizeof(int)*size);
 	if (!target) {
@@ -42,7 +44,7 @@
 
 	random_initialize(target, size, 0, 90);
 
-	print_array(target, size);
+	//print_array(target, size);
 	goto quicksort(target, 0, size-1, exit0, (void*)target);
 
 	printf("bad region\n");
@@ -52,13 +54,17 @@
 main(int argc, char **argv)
 {
 	unsigned int seed=0;
+	int size=100;
 	int opt;
 
-	while ((opt = getopt(argc, argv, "s:")) != -1) {
+	while ((opt = getopt(argc, argv, "s:n:")) != -1) {
 		switch (opt) {
 			case 's':
 				seed = atoi(optarg);
 				break;
+			case 'n':
+				size = atoi(optarg);
+				break;
 			default:
 				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
 				exit(1);
@@ -66,7 +72,7 @@
 	}
 
 	srandom(seed);
-	starter();
+	starter(size);
 	return 0;
 }
 
@@ -86,8 +92,8 @@
 {
 	int *v = arg;
 	int b;
-	print_array(arg, 100);
-	b = check_sort(arg, 100);
+	//print_array(arg, 100);
+	//b = check_sort(arg, 100);
 	if (b) {
 		printf("sorting successful!\n");
 		exit(-1);
diff -r 0eb6cac880f0 -r 775dfe898662 gcc/c-parser.c
--- a/gcc/c-parser.c	Tue Oct 13 17:15:58 2009 +0900
+++ b/gcc/c-parser.c	Wed Oct 14 12:12:51 2009 +0900
@@ -1547,9 +1547,9 @@
 	  t.spec = c_parser_peek_token (parser)->value;
 	  declspecs_add_type (specs, t);
 
-	  //attrs = get_identifier("fastcall");
-	  //attrs = build_tree_list(attrs, NULL_TREE);
-	  //declspecs_add_attrs(specs, attrs);
+	  attrs = get_identifier("fastcall");
+	  attrs = build_tree_list(attrs, NULL_TREE);
+	  declspecs_add_attrs(specs, attrs);
 
 	  c_parser_consume_token (parser);
 	  break;