diff options
Diffstat (limited to 'test/ccured_olden/bisort/bitonic.c')
| -rw-r--r-- | test/ccured_olden/bisort/bitonic.c | 267 |
1 files changed, 267 insertions, 0 deletions
diff --git a/test/ccured_olden/bisort/bitonic.c b/test/ccured_olden/bisort/bitonic.c new file mode 100644 index 00000000..72ff8611 --- /dev/null +++ b/test/ccured_olden/bisort/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, (long)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); +} + |