Bell 32V development

Work on file usr/src/libc/gen/qsort.c

Co-Authored-By: John Reiser <jfr@research.uucp>
Synthesized-from: 32v

diff --git a/usr/src/libc/gen/qsort.c b/usr/src/libc/gen/qsort.c
new file mode 100755 (executable)
index 0000000..202c759
--- /dev/null
+++ b/usr/src/libc/gen/qsort.c
@@ -0,0 +1,120 @@
+
+static int     (*qscmp)();
+static int     qses;
+
+qsort(a, n, es, fc)
+char *a;
+unsigned n;
+int es;
+int (*fc)();
+{
+       qscmp = fc;
+       qses = es;
+       qs1(a, a+n*es);
+}
+
+static qs1(a, l)
+char *a, *l;
+{
+       register char *i, *j;
+       register es;
+       char **k;
+       char *lp, *hp;
+       int c;
+       unsigned n;
+
+
+       es = qses;
+
+start:
+       if((n=l-a) <= es)
+               return;
+       n = es * (n / (2*es));
+       hp = lp = a+n;
+       i = a;
+       j = l-es;
+       for(;;) {
+               if(i < lp) {
+                       if((c = (*qscmp)(i, lp)) == 0) {
+                               qsexc(i, lp -= es);
+                               continue;
+                       }
+                       if(c < 0) {
+                               i += es;
+                               continue;
+                       }
+               }
+
+loop:
+               if(j > hp) {
+                       if((c = (*qscmp)(hp, j)) == 0) {
+                               qsexc(hp += es, j);
+                               goto loop;
+                       }
+                       if(c > 0) {
+                               if(i == lp) {
+                                       qstexc(i, hp += es, j);
+                                       i = lp += es;
+                                       goto loop;
+                               }
+                               qsexc(i, j);
+                               j -= es;
+                               i += es;
+                               continue;
+                       }
+                       j -= es;
+                       goto loop;
+               }
+
+
+               if(i == lp) {
+                       if(lp-a >= l-hp) {
+                               qs1(hp+es, l);
+                               l = lp;
+                       } else {
+                               qs1(a, lp);
+                               a = hp+es;
+                       }
+                       goto start;
+               }
+
+
+               qstexc(j, lp -= es, i);
+               j = hp -= es;
+       }
+}
+
+static qsexc(i, j)
+char *i, *j;
+{
+       register char *ri, *rj, c;
+       int n;
+
+       n = qses;
+       ri = i;
+       rj = j;
+       do {
+               c = *ri;
+               *ri++ = *rj;
+               *rj++ = c;
+       } while(--n);
+}
+
+static qstexc(i, j, k)
+char *i, *j, *k;
+{
+       register char *ri, *rj, *rk;
+       int c;
+       int n;
+
+       n = qses;
+       ri = i;
+       rj = j;
+       rk = k;
+       do {
+               c = *ri;
+               *ri++ = *rk;
+               *rk++ = *rj;
+               *rj++ = c;
+       } while(--n);
+}