# HG changeset patch
# User kent <kent@cr.ie.u-ryukyu.ac.jp>
# Date 1255421758 -32400
# Node ID 0eb6cac880f0ddc0cc2ea27a871b8aa9bcabed19
# Parent  959d4c8c8abcdb9815d496498dad533c4eaec372
add cbc example of quicksort.

diff -r 959d4c8c8abc -r 0eb6cac880f0 .hgignore
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.hgignore	Tue Oct 13 17:15:58 2009 +0900
@@ -0,0 +1,8 @@
+syntax: glob
+
+.*.swp
+.*.swo
+GTAGS
+GRTAGS
+GSYMS
+GPATH
diff -r 959d4c8c8abc -r 0eb6cac880f0 CbC-examples/conv.c
--- a/CbC-examples/conv.c	Tue Sep 29 20:15:16 2009 +0900
+++ b/CbC-examples/conv.c	Tue Oct 13 17:15:58 2009 +0900
@@ -64,7 +64,7 @@
 
 __code main_return(int i,stack sp) {
     printf("#0061:%d\n",i);
-    goto (( (struct main_continuation *)sp)->main_ret)(0,
+    goto (( (struct main_continuation *)sp)->main_ret)(i,
            ((struct main_continuation *)sp)->env);
 }
 
diff -r 959d4c8c8abc -r 0eb6cac880f0 CbC-examples/quicksort/quicksort_c.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CbC-examples/quicksort/quicksort_c.c	Tue Oct 13 17:15:58 2009 +0900
@@ -0,0 +1,183 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<unistd.h>
+#include<assert.h>
+
+static inline void
+SWAP (int *a, int *b)
+{
+	int tmp;
+	tmp = *a;
+	*a = *b;
+	*b = tmp;
+}
+
+static inline int
+mid_point(int a, int b, int c)
+{
+	if (a < b) {
+		if (b < c)
+			return b;
+		else if (a < c)
+			return c;
+		else 
+			return a;
+	} else {
+		if (a < c)
+			return a;
+		else if (b < c)
+			return c;
+		else 
+			return b;
+	}
+}
+
+void
+selectsort(int *v, int s0, int e0)
+{
+	int i,j;
+	int m;
+	int size = e0-s0+1;
+	v += s0;
+	for (i=0; i<size; i++) {
+		m = i;
+		for (j=i+1; j<size; j++) {
+			if (v[m] > v[j])
+				m = j;
+		}
+		if (m!=i)
+			SWAP(&v[i],&v[m]);
+	}
+	return;
+}
+
+void
+quicksort(int *v, int s0, int e0)
+{
+	int p;
+	int s=s0, e=e0;
+#if 0
+	if (e<=s) return;
+	if (e-s<5) {
+		selectsort(v,s0,e0);
+		return;
+	}
+#else
+	if (e<=s) return;
+#endif
+
+	//p = (v[s]+v[(s+e)/2]+v[e])/3;
+	p = mid_point(v[s],v[e],v[(s+e)/2]);
+
+	while (1) {
+		 while (v[s]<p) s++;
+		 while (p<v[e]) e--;
+
+		 if (!(s<e)) break;
+		 SWAP(&v[s], &v[e]);
+		 s++; e--;
+	}
+	assert(e+1==s || s==e);
+
+	quicksort(v, s0, e);
+	quicksort(v, e+1, e0);
+	return;
+}
+
+static void
+print_array(int *v, int size)
+{
+	int i;
+	printf("[");
+	for (i=0; i<size; i++) {
+		printf("%s%4d", (i%10==0)? "\n  ":" ", v[i]);
+	}
+	printf("]\n");
+}
+
+static int
+check_sort(int *v, int size)
+{
+	int i;
+	for (i=0; i<size-1; i++) {
+		if (v[i] > v[i+1])
+			return 0;
+	}
+	return 1;
+}
+
+void
+random_initialize(int *v, int size, int min, int max)
+{
+	int i;
+	int diff = max-min+1;
+
+	for (i=0; i<size; i++) {
+		v[i] = min+random()%diff;
+	}
+	return;
+}
+
+int
+start_sort(int size)
+{
+	int *target;
+
+	target = (int*)malloc(sizeof(int)*size);
+	if (!target) {
+		perror("malloc");
+		exit(1);
+	}
+
+	random_initialize(target, size, 0, 1);
+
+	//print_array(target, size);
+	quicksort(target, 0, size-1);
+	//selectsort(target, 0, size-1);
+	//print_array(target, size);
+	return check_sort(target, size);
+}
+
+int
+main(int argc, char **argv)
+{
+	//unsigned int seed= -1074072728;
+	unsigned int seed;
+	int size=101;
+	int loop=1;
+	int opt, i;
+
+	while ((opt = getopt(argc, argv, "r:s:n:")) != -1) {
+		switch (opt) {
+			case 's':
+				size = atoi(optarg);
+				break;
+			case 'n':
+				loop = atoi(optarg);
+				break;
+			case 'r':
+				seed = atoi(optarg);
+				break;
+			default:
+				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
+				exit(1);
+		}
+	}
+
+	printf("start seed = %u\n", seed);
+	printf("sort size = %d\n", size);
+	for (i=0; i<loop; i++) {
+		srandom(seed+i);
+		int b = start_sort(size);
+		if (b) {
+			printf("seed = %d+%u, success\n", i, seed);
+		} else {
+			fprintf(stderr, "sorting failure!  seed=%u+%d\n", seed,i);
+			exit(1);
+		}
+	}
+	exit(0);
+}
+
+
+
diff -r 959d4c8c8abc -r 0eb6cac880f0 CbC-examples/quicksort/quicksort_cbc.cbc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CbC-examples/quicksort/quicksort_cbc.cbc	Tue Oct 13 17:15:58 2009 +0900
@@ -0,0 +1,241 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<assert.h>
+
+typedef void *stack;
+typedef struct {
+	int size;
+	void *interface;
+	void (*code)(void*, stack);
+} frame, *framep;
+
+/* quickstart main routine. */
+struct qs_if {
+	int *v;
+	int s;
+	int e;
+};
+typedef __code (*RET)(void*);
+
+#include"quicksort_cbc.h"
+
+__code returner(stack sp)
+{
+	framep fp = (framep)sp;
+	sp += fp->size;
+	fp->code(fp->interface, sp);
+}
+
+__code quicksort_start(void *arg, stack sp)
+{
+	struct qs_if *recvif = arg;
+	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(struct qs_if *recvif, int s, int e, int p, stack sp)
+{
+	goto quicksort_divider_s(recvif, s, e, p, sp);
+}
+__code quicksort_divider_s(struct 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(struct 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(struct 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(struct qs_if *recvif, int s, int e, stack sp)
+{
+	framep fp;
+	struct qs_if *outif;
+
+	/* interface for first quicksort_start this segment directly jump to.  */
+	outif = (sp-=sizeof(struct qs_if));
+	outif->v = recvif->v;
+	outif->s = recvif->s;
+	outif->e = e;
+	fp = (sp-=sizeof(frame));
+	fp->code = quicksort_start;
+	fp->interface = recvif;
+	fp->size = sizeof(frame)+sizeof(struct qs_if);
+
+	/* recvif is used by second quicksort_start.  */
+	recvif->s = e+1;
+	goto quicksort_start(outif, sp);
+}
+/* recursive call routine end. */
+
+int v[100];
+struct qs_if *outif;
+
+struct qs {
+	__code (*ret)(void*);
+	void *ret_arg;
+	stack *sp;
+};
+__code
+quicksort(int *v, int s, int e,  RET ret, void *arg )
+{
+	framep fp;
+	stack sp = malloc(10240)+10240;
+	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);
+
+	/* interface for quicksort_start.  */
+	outif = (sp -= sizeof(*outif));
+	outif->v = v;
+	outif->s = s;
+	outif->e = e;
+	/* frame for quicksort_finish.  */
+	fp = (sp -= sizeof(frame));
+	fp->code = quicksort_finish;
+	fp->interface = finish_if;
+	fp->size = sizeof(frame)+sizeof(outif);
+
+	goto quicksort_start(outif, sp);
+}
+__code
+quicksort_finish(void *arg, stack sp)
+{
+	struct qs interface = *(struct qs*)arg;
+	free(interface.sp);
+	goto interface.ret(interface.ret_arg);
+}
+
+
+
+#if 0
+void
+quicksort_c(int *v, int s0, int e0, stack sp)
+{
+	int p;
+	int s=s0, e=e0;
+	if (e<=s) return;
+
+	//p = (v[s]+v[(s+e)/2]+v[e])/3;
+	p = mid_point(v[s],v[e],v[(s+e)/2]);
+
+	while (1) {
+		 while (v[s]<p) s++;
+		 while (p<v[e]) e--;
+
+		 if (!(s<e)) break;
+		 SWAP(&v[s], &v[e]);
+		 s++; e--;
+	}
+	assert(e+1==s || s==e);
+
+	quicksort(v, s0, e);
+	quicksort(v, e+1, e0);
+	return;
+}
+
+
+
+/*  --------------------
+ *     | args |fp| 
+ *  --------------------
+ *  +            ↑     -
+ *               sp
+ */ 
+/* code segmentへgotoしたときのstack spの状態
+ *
+ * sp が直接さすのは frame 構造体
+ * frame.size:
+ * frame.code: そのcode segmentが終了した時にgotoすべきcode segment.
+ * frame.interface: frame.codeへgotoするときのinterface.
+ *                  このポインタが指すメモリ領域は stack
+ *                  中にあっても良いしなくても良い。
+ *                  ただしframe.codeを登録した側で解放すべき。
+ * sp+sizeof(frame)が指すのは実行中のcode segmentのinterface(引数)
+ * これは実行中のcode segmentがメモリ管理する
+ * 通常はこのcode segmentが終了する際に sp+=frame.size とすればよい
+ */
+__code caller0(void *arg, stack sp)
+{
+	/* interface for caller_finish0.  */
+	double *finish_arg = (sp -= sizeof(double));
+
+	/* arg for quicksort_start.  */
+	outif = (sp -= sizeof(*outif));
+	framep fp = (sp -= sizeof(frame));
+	fp->code = caller_finish;
+	fp->interface = NULL;
+	fp->size = sizeof(*outif)+sizeof(frame);
+
+	goto quicksort_start(outif, sp);
+}
+__code caller_finish0(void *arg, stack sp)
+{
+}
+
+__code __returner0(void *arg , stack sp)
+{
+	framep fp = sp;
+	sp += fp->size;
+	goto fp->code(fp->interface, sp);
+}
+
+#endif
+
+
+
+
diff -r 959d4c8c8abc -r 0eb6cac880f0 CbC-examples/quicksort/quicksort_test.cbc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CbC-examples/quicksort/quicksort_test.cbc	Tue Oct 13 17:15:58 2009 +0900
@@ -0,0 +1,99 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<assert.h>
+#include<unistd.h>
+
+#include"quicksort_test.h"
+
+void
+random_initialize(int *v, int size, int min, int max)
+{
+	int i;
+	int diff = max-min+1;
+
+	for (i=0; i<size; i++) {
+		v[i] = min+random()%diff;
+	}
+	return;
+}
+
+static void
+print_array(int *v, int size)
+{
+	int i;
+	printf("[");
+	for (i=0; i<size; i++) {
+		printf("%s%4d", (i%10==0)? "\n  ":" ", v[i]);
+	}
+	printf(" ]\n");
+}
+
+void
+starter()
+{
+	int *target;
+	int size=100;
+
+	target = (int*)malloc(sizeof(int)*size);
+	if (!target) {
+		perror("malloc");
+		exit(1);
+	}
+
+	random_initialize(target, size, 0, 90);
+
+	print_array(target, size);
+	goto quicksort(target, 0, size-1, exit0, (void*)target);
+
+	printf("bad region\n");
+}
+
+int
+main(int argc, char **argv)
+{
+	unsigned int seed=0;
+	int opt;
+
+	while ((opt = getopt(argc, argv, "s:")) != -1) {
+		switch (opt) {
+			case 's':
+				seed = atoi(optarg);
+				break;
+			default:
+				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
+				exit(1);
+		}
+	}
+
+	srandom(seed);
+	starter();
+	return 0;
+}
+
+static int
+check_sort(int *v, int size)
+{
+	int i;
+	for (i=0; i<size-1; i++) {
+		if (v[i] > v[i+1])
+			return 0;
+	}
+	return 1;
+}
+
+__code
+exit0(void *arg)
+{
+	int *v = arg;
+	int b;
+	print_array(arg, 100);
+	b = check_sort(arg, 100);
+	if (b) {
+		printf("sorting successful!\n");
+		exit(-1);
+	} else {
+		printf("sorting failure! \n");
+		exit(0);
+	}
+}
+
diff -r 959d4c8c8abc -r 0eb6cac880f0 gcc/c-parser.c
--- a/gcc/c-parser.c	Tue Sep 29 20:15:16 2009 +0900
+++ b/gcc/c-parser.c	Tue Oct 13 17:15:58 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;