aboutsummaryrefslogtreecommitdiffstats
path: root/test/ccured_olden/newbisort
diff options
context:
space:
mode:
Diffstat (limited to 'test/ccured_olden/newbisort')
-rw-r--r--test/ccured_olden/newbisort/.cvsignore1
-rw-r--r--test/ccured_olden/newbisort/CVS/Entries13
-rw-r--r--test/ccured_olden/newbisort/CVS/Repository1
-rw-r--r--test/ccured_olden/newbisort/CVS/Root1
-rw-r--r--test/ccured_olden/newbisort/HOWTO1
-rw-r--r--test/ccured_olden/newbisort/Makefile49
-rw-r--r--test/ccured_olden/newbisort/Makefile.orig33
-rw-r--r--test/ccured_olden/newbisort/Makefile.plain7
-rw-r--r--test/ccured_olden/newbisort/Makefile.ss7
-rw-r--r--test/ccured_olden/newbisort/args.c32
-rw-r--r--test/ccured_olden/newbisort/bitonic.c267
-rw-r--r--test/ccured_olden/newbisort/node.h18
-rw-r--r--test/ccured_olden/newbisort/proc.h25
-rw-r--r--test/ccured_olden/newbisort/ssplain.c75
-rw-r--r--test/ccured_olden/newbisort/ssplain.h128
-rw-r--r--test/ccured_olden/newbisort/swap.c145
16 files changed, 803 insertions, 0 deletions
diff --git a/test/ccured_olden/newbisort/.cvsignore b/test/ccured_olden/newbisort/.cvsignore
new file mode 100644
index 00000000..5c56af15
--- /dev/null
+++ b/test/ccured_olden/newbisort/.cvsignore
@@ -0,0 +1 @@
+changes
diff --git a/test/ccured_olden/newbisort/CVS/Entries b/test/ccured_olden/newbisort/CVS/Entries
new file mode 100644
index 00000000..cb3bbed9
--- /dev/null
+++ b/test/ccured_olden/newbisort/CVS/Entries
@@ -0,0 +1,13 @@
+/HOWTO/1.1/Fri Jul 6 09:37:30 2001//
+/Makefile/1.2/Sat Jul 21 16:09:41 2001//
+/Makefile.plain/1.1/Fri Jul 6 09:37:30 2001//
+/Makefile.ss/1.1/Fri Jul 6 09:37:30 2001//
+/args.c/1.1/Fri Jul 6 09:37:30 2001//
+/bitonic.c/1.1/Fri Jul 6 09:37:30 2001//
+/node.h/1.1/Fri Jul 6 09:37:30 2001//
+/proc.h/1.1/Fri Jul 6 09:37:30 2001//
+/ssplain.c/1.1/Fri Jul 6 09:37:30 2001//
+/ssplain.h/1.1/Fri Jul 6 09:37:30 2001//
+/swap.c/1.1/Fri Jul 6 09:37:30 2001//
+/.cvsignore/1.1/Thu Nov 8 23:31:03 2001//
+D
diff --git a/test/ccured_olden/newbisort/CVS/Repository b/test/ccured_olden/newbisort/CVS/Repository
new file mode 100644
index 00000000..9cf3bd6a
--- /dev/null
+++ b/test/ccured_olden/newbisort/CVS/Repository
@@ -0,0 +1 @@
+cil/test/olden/newbisort
diff --git a/test/ccured_olden/newbisort/CVS/Root b/test/ccured_olden/newbisort/CVS/Root
new file mode 100644
index 00000000..35f411e9
--- /dev/null
+++ b/test/ccured_olden/newbisort/CVS/Root
@@ -0,0 +1 @@
+/home/cvs-repository
diff --git a/test/ccured_olden/newbisort/HOWTO b/test/ccured_olden/newbisort/HOWTO
new file mode 100644
index 00000000..dd53dde0
--- /dev/null
+++ b/test/ccured_olden/newbisort/HOWTO
@@ -0,0 +1 @@
+250000 0
diff --git a/test/ccured_olden/newbisort/Makefile b/test/ccured_olden/newbisort/Makefile
new file mode 100644
index 00000000..c08a8967
--- /dev/null
+++ b/test/ccured_olden/newbisort/Makefile
@@ -0,0 +1,49 @@
+# /* For copyright information, see olden_v1.0/COPYRIGHT */
+
+BINARY = bisort
+PROGS = bitonic args ssplain
+
+CC = gcc -arch ppc
+CCOMP=../../../../ccomp
+CCOMPFLAGS=-dump-c
+
+SRC = .c
+OBJ = .o
+ASM = .s
+SRCS = $(addsuffix $(SRC),$(PROGS))
+OBJS = $(addsuffix $(OBJ),$(PROGS))
+ASMS = $(addsuffix $(ASM),$(PROGS))
+INCDIRS = /usr/include
+
+EXTRA_CDEFS = -DI_TIME -DI_SYS_TIME -DULTRIX
+CDEFS = -DPLAIN -DSS_PLAIN #-I$(OLDENHOME)/common
+OPTFLAGS = -g -Wall -O3
+
+LIBS = -lc -lgcc -lm
+LIBPATH =
+
+#$(BINARY): $(OBJS)
+# $(CC) $(LDFALGS) $(OPTFLAGS) -o $@ $(OBJS) $(LIBPATH) $(LIBS)
+
+#$(SRC)$(OBJ):
+# $(CC) $(CDEFS) $(EXTRA_CDEFS) $(MY_CDEFS) $(OPTFLAGS) -c $<
+
+
+all_s: $(PROGS:%=%.s)
+
+all: $(PROGS:%=%.compcert)
+
+all_gcc: $(PROGS:%=%.gcc)
+
+%.compcert: %.s
+ $(CC) $(CFLAGS) $(LDFALGS) $(OPTFLAGS) -o $*.compcert $*.s $(LIBS)
+
+%.s: %.c ../../../../ccomp
+ $(CCOMP) $(CCOMPFLAGS) $(CDEFS) $(EXTRA_CDEFS) $*.c
+
+%.gcc: %.c
+ $(CC) $(CFLAGS) $(LDFALGS) $(OPTFLAGS) -o $*.gcc $*.c $(LIBS)
+
+clean:
+ rm -f $(BINARY) $(OBJS) *~ $(ASMS) *.light.c
+
diff --git a/test/ccured_olden/newbisort/Makefile.orig b/test/ccured_olden/newbisort/Makefile.orig
new file mode 100644
index 00000000..81e77568
--- /dev/null
+++ b/test/ccured_olden/newbisort/Makefile.orig
@@ -0,0 +1,33 @@
+# /* For copyright information, see olden_v1.0/COPYRIGHT */
+
+BINARY = bisort
+FILES = bitonic args ssplain
+
+
+
+CC = gcc
+
+SRC = .c
+OBJ = .o
+ASM = .s
+SRCS = $(addsuffix $(SRC),$(FILES))
+OBJS = $(addsuffix $(OBJ),$(FILES))
+ASMS = $(addsuffix $(ASM),$(FILES))
+INCDIRS = /usr/include
+
+EXTRA_CDEFS = -DI_TIME -DI_SYS_TIME -DULTRIX
+CDEFS = -DPLAIN -DSS_PLAIN #-I$(OLDENHOME)/common
+OPTFLAGS = -g -Wall -O3
+
+LIBS = -lc -lgcc -lm
+LIBPATH =
+
+$(BINARY): $(OBJS)
+ $(CC) $(LDFALGS) $(OPTFLAGS) -o $@ $(OBJS) $(LIBPATH) $(LIBS)
+
+$(SRC)$(OBJ):
+ $(CC) $(CDEFS) $(EXTRA_CDEFS) $(MY_CDEFS) $(OPTFLAGS) -c $<
+
+clean:
+ rm -f $(BINARY) $(OBJS) *~
+
diff --git a/test/ccured_olden/newbisort/Makefile.plain b/test/ccured_olden/newbisort/Makefile.plain
new file mode 100644
index 00000000..b1240250
--- /dev/null
+++ b/test/ccured_olden/newbisort/Makefile.plain
@@ -0,0 +1,7 @@
+# /* For copyright information, see olden_v1.0/COPYRIGHT */
+
+BINARY = bisort
+FILES = bitonic args ssplain
+
+include ../Makefile.plain
+
diff --git a/test/ccured_olden/newbisort/Makefile.ss b/test/ccured_olden/newbisort/Makefile.ss
new file mode 100644
index 00000000..00028730
--- /dev/null
+++ b/test/ccured_olden/newbisort/Makefile.ss
@@ -0,0 +1,7 @@
+# /* For copyright information, see olden_v1.0/COPYRIGHT */
+
+BINARY = bisort
+FILES = bitonic args ssplain
+
+include ../Makefile.ss
+
diff --git a/test/ccured_olden/newbisort/args.c b/test/ccured_olden/newbisort/args.c
new file mode 100644
index 00000000..12591026
--- /dev/null
+++ b/test/ccured_olden/newbisort/args.c
@@ -0,0 +1,32 @@
+/* For copyright information, see olden_v1.0/COPYRIGHT */
+
+#ifdef SS_PLAIN
+#include "ssplain.h"
+#endif SS_PLAIN
+
+int mylog(int num)
+{
+ int j=0,k=1;
+
+ while(k<num) { k*=2; j++; }
+ return j;
+}
+
+extern int flag;
+int dealwithargs(int argc, char *argv[])
+{
+ int size;
+
+ if (argc > 2)
+ flag = atoi(argv[2]);
+ else
+ flag = 0;
+
+ if (argc > 1)
+ size = atoi(argv[1]);
+ else
+ size = 16;
+
+ return size;
+}
+
diff --git a/test/ccured_olden/newbisort/bitonic.c b/test/ccured_olden/newbisort/bitonic.c
new file mode 100644
index 00000000..7b08a0a2
--- /dev/null
+++ b/test/ccured_olden/newbisort/bitonic.c
@@ -0,0 +1,267 @@
+/* For copyright information, see olden_v1.0/COPYRIGHT */
+
+/* =================== PROGRAM bitonic===================== */
+/* UP - 0, DOWN - 1 */
+
+#include "node.h" /* Node Definition */
+#include "proc.h" /* Procedure Types/Nums */
+
+#define CONST_m1 10000
+#define CONST_b 31415821
+#define RANGE 100
+
+#ifdef SS_PLAIN
+#include "ssplain.h"
+#endif SS_PLAIN
+
+#define put(a) chatting("%d",a)
+#define puts(a) chatting(a)
+
+
+int flag=0,foo=0;
+
+#define NewNode(h,v) \
+ \
+{ \
+ h = (HANDLE *) malloc(sizeof(struct node)); \
+ h->value = v; \
+ h->left = NIL; \
+ h->right = NIL; \
+ };
+
+
+void InOrder(h)
+ HANDLE *h;
+{
+ HANDLE *l, *r;
+ if ((h != NIL))
+ {
+ l = h->left;
+ r = h->right;
+ InOrder(l);
+ chatting("%d @ 0x%x\n",h->value,h);
+ InOrder(r);
+ }
+}
+
+int mult(int p, int q)
+{
+ int p1, p0, q1, q0;
+
+ p1=p/CONST_m1; p0=p%CONST_m1;
+ q1=q/CONST_m1; q0=q%CONST_m1;
+ return (((p0*q1+p1*q0) % CONST_m1)*CONST_m1+p0*q0);
+}
+
+int skiprand(int seed, int n)
+{
+#ifdef SS_PLAIN
+ for (; n; n--) seed=mult(seed,CONST_b)+1;
+#else SS_PLAIN
+ for (; n; n--) seed=random(seed);
+#endif SS_PLAIN
+ return seed;
+}
+
+#ifndef SS_PLAIN
+int random(int seed)
+{
+ int tmp;
+ tmp = (mult(seed,CONST_b)+1);
+ return tmp;
+}
+#endif SS_PLAIN
+
+HANDLE* RandTree(n,seed,level)
+ int n,seed,level;
+
+{
+ int next_val,my_name;
+ HANDLE *h;
+ my_name=foo++;
+
+ if (n > 1)
+ {
+#ifdef SS_PLAIN
+ seed = mult(seed,CONST_b)+1;
+#else SS_PLAIN
+ seed = random(seed);
+#endif SS_PLAIN
+ next_val=seed % RANGE;
+ NewNode(h,next_val);
+
+ h->left = RandTree((n/2),seed,level+1);
+ h->right = RandTree((n/2),skiprand(seed,(n)+1),level+1);
+ }
+ else
+ h = NIL;
+ return(h);
+}
+
+void SwapVal(l,r)
+ HANDLE *l, *r;
+{
+ int temp;
+
+ temp = l->value; /* MISS PROBLEM */
+ l->value = r->value;
+ r->value = temp;
+}
+
+void SwapLeft(l,r)
+ HANDLE *l, *r;
+{
+ HANDLE *h;
+
+ h = r->left;
+ r->left = l->left;
+ l->left = h;
+}
+
+void SwapRight(l,r)
+ HANDLE *l, *r;
+{
+ HANDLE *h;
+
+ h = r->right;
+ r->right = l->right; /* MISS PROBLEM */
+ l->right = h;
+}
+
+int Bimerge(root,spr_val,dir)
+ HANDLE *root;
+ int spr_val,dir;
+{
+ int rightexchange, elementexchange;
+ HANDLE *pl, *pr;
+
+ /*chatting("enter bimerge %x\n", root);*/
+ rightexchange = ((root->value > spr_val) ^ dir);
+ if (rightexchange)
+ {
+ int temp;
+ temp = root->value;
+ root->value = spr_val;
+ spr_val = temp;
+ }
+
+ pl = root->left;
+ pr = root->right;
+
+ while (pl != NIL)
+ {
+ elementexchange = ((pl->value > /* MISS PROBLEM */pr->value) ^ dir);
+ if (rightexchange)
+ {
+ if (elementexchange)
+ {
+ SwapVal(pl,pr);
+ SwapRight(pl,pr);
+ pl = pl->left;
+ pr = pr->left;
+ }
+ else
+ {
+ pl = pl->right;
+ pr = pr->right;
+ }
+ }
+ else
+ {
+ if (elementexchange)
+ {
+ SwapVal(pl,pr);
+ SwapLeft(pl,pr);
+ pl = pl->right;
+ pr = pr->right;
+ }
+ else
+ {
+ pl = pl->left;
+ pr = pr->left; /* MISS PROBLEM */
+ }
+ }
+ }
+
+ if (root->left != NIL)
+ {
+ root->value=Bimerge(root->left,root->value,dir);
+ spr_val=Bimerge(root->right,spr_val,dir);
+ }
+ /*chatting("exit bimerge %x\n", root);*/
+ return spr_val;
+}
+
+int Bisort(root,spr_val,dir)
+ HANDLE *root;
+ int spr_val,dir;
+{
+ /*chatting("bisort %x\n", root);*/
+ if (root->left == NIL)
+ {
+ if ((root->value > spr_val) ^ dir)
+ {
+ int val;
+ val = spr_val;
+ spr_val = root->value;
+ root->value =val;
+ }
+ }
+ else
+ {
+ /* Bisort both halves of the tree and merge */
+ root->value=Bisort(root->left,root->value,dir);
+ spr_val=Bisort(root->right,spr_val,!dir);
+ spr_val=Bimerge(root,spr_val,dir);
+ }
+ /*chatting("exit bisort %x\n", root);*/
+ return spr_val;
+}
+
+void main(argc,argv)
+ int argc;
+ char *argv[];
+
+
+{
+ HANDLE *h;
+ int sval;
+ int n;
+
+ n = dealwithargs(argc,argv);
+
+ chatting("Bisort with %d size\n", n);
+ h = RandTree(n,12345768,0);
+#ifdef SS_PLAIN
+ sval = (mult(245867,CONST_b)+1) % RANGE;
+#else SS_PLAIN
+ sval = random(245867) % RANGE;
+#endif SS_PLAIN
+ if (flag) {
+ InOrder(h);
+ chatting("%d\n",sval);
+ }
+ chatting("**************************************\n");
+ chatting("BEGINNING BITONIC SORT ALGORITHM HERE\n");
+ chatting("**************************************\n");
+
+ chatting("Sorting forward...");
+ sval=Bisort(h,sval,0);
+ if (flag) {
+ chatting("Sorted Tree:\n");
+ InOrder(h);
+ chatting("%d\n",sval);
+ }
+ chatting("done\n");
+
+ chatting("sorting backward...");
+ sval=Bisort(h,sval,1);
+ if (flag) {
+ chatting("Sorted Tree:\n");
+ InOrder(h);
+ chatting("%d\n",sval);
+ }
+ chatting("done\n");
+ exit(0);
+}
+
diff --git a/test/ccured_olden/newbisort/node.h b/test/ccured_olden/newbisort/node.h
new file mode 100644
index 00000000..c1b81c6d
--- /dev/null
+++ b/test/ccured_olden/newbisort/node.h
@@ -0,0 +1,18 @@
+/* For copyright information, see olden_v1.0/COPYRIGHT */
+
+/* =============== NODE STRUCTURE =================== */
+
+struct node {
+ int value;
+ struct node *left;
+ struct node *right;
+ };
+
+typedef struct node HANDLE;
+
+#define NIL ((HANDLE *) 0)
+#ifdef FUTURES
+#define makenode(procid) ALLOC(procid,sizeof(struct node))
+#else
+#define makenode(procid) mymalloc(sizeof(struct node))
+#endif
diff --git a/test/ccured_olden/newbisort/proc.h b/test/ccured_olden/newbisort/proc.h
new file mode 100644
index 00000000..eadb80aa
--- /dev/null
+++ b/test/ccured_olden/newbisort/proc.h
@@ -0,0 +1,25 @@
+/* For copyright information, see olden_v1.0/COPYRIGHT */
+
+/* ========== PROCEDURE TYPES/NUMS ================== */
+
+
+HANDLE *RandTree();
+
+void SwapValue();
+void SwapValLeft();
+void SwapValRight();
+int Bimerge();
+int Bisort();
+#define DD_EXIT 0
+
+
+/* ================= PROC NAMES ==============*/
+
+#ifdef EXTERN
+ extern char *procnames[];
+#else
+ static char *procnames[] =
+ {
+ "EXIT"
+ };
+#endif
diff --git a/test/ccured_olden/newbisort/ssplain.c b/test/ccured_olden/newbisort/ssplain.c
new file mode 100644
index 00000000..b178e5f5
--- /dev/null
+++ b/test/ccured_olden/newbisort/ssplain.c
@@ -0,0 +1,75 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include <limits.h>
+#include <stddef.h>
+#include "ssplain.h"
+
+void chatting(char *s, ...)
+{
+ va_list ap;
+ va_start(ap,s);
+ vfprintf(stderr, s, ap);
+ va_end(ap);
+}
+
+void __Olden_panic(char *s, ...)
+{
+ va_list ap;
+ va_start(ap,s);
+ vfprintf(stderr, s, ap);
+ va_end(ap);
+ exit(-1);
+}
+
+#ifdef SS_RAND
+double drand48()
+{
+ double d;
+ d = (double) random() / LONG_MAX;
+ return d;
+}
+
+
+long lrand48()
+{
+ long l = random();
+ return l;
+}
+
+void srand48(long seed)
+{
+ srand(seed);
+}
+#endif SS_RAND
+
+
+static unsigned long bytes_allocated = 0;
+static unsigned long allocations = 0;
+
+void*
+ssplain_malloc(int size)
+{
+ allocations++;
+ bytes_allocated+=size;
+ return malloc(size);
+}
+
+void*
+ssplain_calloc(int nelems, int size)
+{
+ void *p;
+ allocations++;
+ bytes_allocated+= nelems * size;
+ p = calloc(nelems, size);
+ assert (p);
+ return p;
+}
+
+void
+ssplain_alloc_stats()
+{
+ chatting("Allocation stats: %d bytes allocated in %d allocations\n",
+ bytes_allocated, allocations);
+}
diff --git a/test/ccured_olden/newbisort/ssplain.h b/test/ccured_olden/newbisort/ssplain.h
new file mode 100644
index 00000000..cb9b3eed
--- /dev/null
+++ b/test/ccured_olden/newbisort/ssplain.h
@@ -0,0 +1,128 @@
+#ifndef SS_PLAIN_H
+#define SS_PLAIN_H
+
+void * ssplain_malloc(int size);
+void * ssplain_calloc(int nelems, int size);
+void ssplain_alloc_stats();
+
+/* Convert MP shutdown to exit */
+#define __ShutDown(ID) { ssplain_alloc_stats(); exit(ID); }
+
+/* All these CM-5 things are nops */
+#define CMMD_node_timer_clear(ID)
+#define CMMD_node_timer_start(ID)
+#define CMMD_node_timer_stop(ID)
+#define CMMD_node_timer_elapsed(ID) ((double)0)
+
+#define CMMD_self_address() 0
+
+#define ClearAllStats()
+
+/* define away the CM-5 allocator */
+#include <stdlib.h>
+
+#ifndef ALLOC
+#define ALLOC(NUM,ESIZE) ssplain_calloc (NUM+1,ESIZE)
+#endif ALLOC
+
+#ifndef mymalloc
+#define mymalloc ssplain_malloc
+#endif mymalloc
+
+/* Get all of these multiprocessing things out of here. */
+/* My id will stay that way */
+#define IDMASK 0xffffffff
+
+/* Nothing is getting tested */
+#ifndef RETEST
+#define RETEST()
+#endif RETEST
+
+#ifndef NOTEST
+#define NOTEST()
+#endif NOTEST
+
+/* Everything is local */
+#ifndef local
+#define local
+#endif local
+
+#ifndef LOCAL
+#define LOCAL(VAL) (VAL)
+#endif LOCAL
+
+#ifndef ISLOCPTR
+#define ISLOCPTR(VAL) (1)
+#endif ISLOCPTR
+
+#ifndef MLOCAL
+#define MLOCAL(VAL)
+#endif MLOCAL
+
+/* An atomic increment is a normal increment */
+#ifndef ATOMICINC
+#define ATOMICINC(PVAL) (*(PVAL) = *(PVAL) + 1)
+#endif ATOMICINC
+
+/* Nothing is migrating anywhere */
+#ifndef MIGRATE
+#define MIGRATE(ID)
+#endif MIGRATE
+
+#ifndef MIGRPH
+#define MIGRPH()
+#endif MIGRPH
+
+#ifndef UNPHASE
+#define UNPHASE()
+#endif UNPHASE
+
+#ifndef PID
+#define PID(VAL) (0)
+#endif PID
+
+/* All these functions */
+void chatting(char *s, ...);
+void __Olden_panic(char *s, ...);
+
+/* just define these guys, they are not going to change */
+#define __NumNodes 1
+#define __MyNodeId 0
+#define __NDim 0
+
+typedef struct ss_future_cell_int {
+ int value;
+} future_cell_int;
+
+/* Where are these things for real? */
+#ifdef SS_RAND
+long lrand48();
+double drand48();
+void srand48(long seed);
+#endif SS_RAND
+
+#define MOD(V,M) ((V) & ((M) - 1))
+#define INC_MOD(V,M) (V) = MOD((V) + 1, (M))
+
+/* Prefetch instructions */
+
+/* Use these for 1 lookahead prefetching */
+
+#ifdef OVERHEAD_ONLY
+#define ASSEMBLE_PREFETCH(ARG)
+#define ASSEMBLE_PREFETCH_HEAD(ARG)
+#else !OVERHEAD_ONLY
+
+#define ASSEMBLE_PREFETCH(ARG) \
+ asm ("lw $0, %0" : /* no outputs */ : "g" (ARG))
+
+/* Use these for infinite lookahead prefetching */
+#define ASSEMBLE_PREFETCH_HEAD(ARG) \
+ asm ("lh $0, %0" : /* no outputs */ : "g" (ARG))
+
+#endif OVERHEAD_ONLY
+
+#endif SS_PLAIN_H
+
+
+
diff --git a/test/ccured_olden/newbisort/swap.c b/test/ccured_olden/newbisort/swap.c
new file mode 100644
index 00000000..e1e98749
--- /dev/null
+++ b/test/ccured_olden/newbisort/swap.c
@@ -0,0 +1,145 @@
+/* For copyright information, see olden_v1.0/COPYRIGHT */
+
+#define COLLECT_SIZE 256
+#define DFS_SIZE 20
+#include "node.h"
+
+#ifdef SS_PLAIN
+#include "ssplain.h"
+#endif SS_PLAIN
+
+
+typedef struct {
+ int top;
+ HANDLE *handles[DFS_SIZE];
+} stack;
+
+#define push(s,v) (s)->handles[++((s)->top)] = v
+#define pop(s) (s)->handles[((s)->top)--]
+#define stackempty(s) ((s)->top < 0)
+void VisitCollect(HANDLE *t, local int *collect)
+{
+ register int val;
+ val = t->value;
+ *collect = val;
+}
+
+void VisitCollectReplace(HANDLE *t, local int *collect)
+{
+ register int temp = *collect;
+ register int val = t->value;
+ *collect = val;
+ t->value = temp;
+}
+
+void VisitReplace(HANDLE *t, local int *collect)
+{
+ register int val = *collect;
+ t->value = val;
+}
+
+void swapDFS(local stack *s, local int collection[], void visit())
+{
+ int num=0;
+
+ while (!stackempty(s) && num < COLLECT_SIZE)
+ {
+ HANDLE *v = pop(s);
+ visit(v,&collection[num]);
+ num++;
+ if (v->left != NULL)
+ {
+ HANDLE *child;
+ child = v->right;
+ push(s,child);
+ child = v->left;
+ push(s,child);
+ }
+ }
+}
+
+void NewSwapSubTree(HANDLE *t1, HANDLE *t2)
+{
+ local stack c1, r1, s2;
+ int collection[COLLECT_SIZE];
+
+ /*chatting("starting swapping\n");*/
+
+ if (t1!=NULL)
+ {
+ c1.top = -1;
+ r1.top = -1;
+ s2.top = -1;
+ push(&c1,t1);
+ push(&r1,t1);
+ push(&s2,t2);
+ while (!stackempty(&c1))
+ {
+ MLOCAL(t1);
+ swapDFS(&c1,collection,VisitCollect);
+ MLOCAL(t2);
+ swapDFS(&s2,collection,VisitCollectReplace);
+ MLOCAL(t1);
+ swapDFS(&r1,collection,VisitReplace);
+ }
+ }
+ /*chatting("ending swapping\n");*/
+
+}
+
+
+int *Collect(HANDLE *t1, local int collection[])
+{
+ register int val;
+ if (t1==NULL) return collection;
+ MLOCAL(t1);
+ val = t1->value;
+ *collection = val;
+ collection += 1;
+ collection = Collect(t1->left,collection);
+ collection = Collect(t1->right,collection);
+ return collection;
+}
+
+int *Collect_Replace(HANDLE *t1, local int collection[])
+{
+ register int temp,val;
+ if (t1==NULL) return collection;
+ MLOCAL(t1);
+ temp = *collection;
+ val = t1->value;
+ *collection = val;
+ t1->value = temp;
+ collection += 1;
+ collection = Collect_Replace(t1->left,collection);
+ collection = Collect_Replace(t1->right,collection);
+ return collection;
+}
+
+int *Replace(HANDLE *t1, local int collection[])
+{
+ register int val;
+ if (t1==NULL) return collection;
+ MLOCAL(t1);
+ val = *collection;
+ t1->value = val;
+ collection +=1;
+ collection = Replace(t1->left,collection);
+ collection = Replace(t1->right,collection);
+ return collection;
+}
+
+
+void SwapSubTree(HANDLE *t1, HANDLE *t2)
+{
+ int collection[COLLECT_SIZE];
+ HANDLE *t1loc, *t2loc;
+
+ MLOCAL(t1);
+ Collect(t1,collection);
+ MLOCAL(t2);
+ Collect_Replace(t2,collection);
+ MLOCAL(t1);
+ Replace(t1,collection);
+}
+
generated by cgit (git 2.34.1) at 2024-07-08 03:06:20 +0000