2.9BSD - /usr/src/lib/c/gen/qsort.c

   1: /*	@(#)qsort.c	2.1	SCCS id keyword	*/
   2: 
   3: static int  (*qscmp)();
   4: static int  qses;
   5: 
   6: qsort(a, n, es, fc)
   7: char *a;
   8: unsigned n;
   9: int es;
  10: int (*fc)();
  11: {
  12:     qscmp = fc;
  13:     qses = es;
  14:     qs1(a, a+n*es);
  15: }
  16: 
  17: static qs1(a, l)
  18: char *a, *l;
  19: {
  20:     register char *i, *j;
  21:     register es;
  22:     char **k;
  23:     char *lp, *hp;
  24:     int c;
  25:     unsigned n;
  26: 
  27: 
  28:     es = qses;
  29: 
  30: start:
  31:     if((n=l-a) <= es)
  32:         return;
  33:     n = es * (n / (2*es));
  34:     hp = lp = a+n;
  35:     i = a;
  36:     j = l-es;
  37:     for(;;) {
  38:         if(i < lp) {
  39:             if((c = (*qscmp)(i, lp)) == 0) {
  40:                 qsexc(i, lp -= es);
  41:                 continue;
  42:             }
  43:             if(c < 0) {
  44:                 i += es;
  45:                 continue;
  46:             }
  47:         }
  48: 
  49: loop:
  50:         if(j > hp) {
  51:             if((c = (*qscmp)(hp, j)) == 0) {
  52:                 qsexc(hp += es, j);
  53:                 goto loop;
  54:             }
  55:             if(c > 0) {
  56:                 if(i == lp) {
  57:                     qstexc(i, hp += es, j);
  58:                     i = lp += es;
  59:                     goto loop;
  60:                 }
  61:                 qsexc(i, j);
  62:                 j -= es;
  63:                 i += es;
  64:                 continue;
  65:             }
  66:             j -= es;
  67:             goto loop;
  68:         }
  69: 
  70: 
  71:         if(i == lp) {
  72:             if(lp-a >= l-hp) {
  73:                 qs1(hp+es, l);
  74:                 l = lp;
  75:             } else {
  76:                 qs1(a, lp);
  77:                 a = hp+es;
  78:             }
  79:             goto start;
  80:         }
  81: 
  82: 
  83:         qstexc(j, lp -= es, i);
  84:         j = hp -= es;
  85:     }
  86: }
  87: 
  88: static qsexc(i, j)
  89: char *i, *j;
  90: {
  91:     register char *ri, *rj, c;
  92:     int n;
  93: 
  94:     n = qses;
  95:     ri = i;
  96:     rj = j;
  97:     do {
  98:         c = *ri;
  99:         *ri++ = *rj;
 100:         *rj++ = c;
 101:     } while(--n);
 102: }
 103: 
 104: static qstexc(i, j, k)
 105: char *i, *j, *k;
 106: {
 107:     register char *ri, *rj, *rk;
 108:     int c;
 109:     int n;
 110: 
 111:     n = qses;
 112:     ri = i;
 113:     rj = j;
 114:     rk = k;
 115:     do {
 116:         c = *ri;
 117:         *ri++ = *rk;
 118:         *rk++ = *rj;
 119:         *rj++ = c;
 120:     } while(--n);
 121: }

Defined functions

Defined variables