4.3BSD - /usr/src/new/icon/functions/sort.c

   1: #include "../h/rt.h"
   2: 
   3: /*
   4:  * sort(l) - sort list l.
   5:  * sort(S) - sort set S.
   6:  * sort(t,i) - sort table on reference (i = 1) or value (i = 2) field.
   7:  */
   8: 
   9: Xsort(nargs, arg2, arg1, arg0)
  10: int nargs;
  11: struct descrip arg2, arg1, arg0;
  12:    {
  13:    register struct descrip *d1;
  14:    register int size, i;
  15:    int nelem;
  16:    struct b_list *lp, *tp;
  17:    union block *bp, *ep;
  18:    extern struct b_list *alclist();
  19:    extern struct b_lelem *alclstb();
  20:    extern anycmp(), trefcmp(), tvalcmp();
  21: 
  22:    DeRef(arg1)
  23:    if (arg1.type == D_LIST) {
  24:       /*
  25:        * Sort the list by copying it into a new list and then using
  26:        *  qsort to sort the descriptors.  (That was easy!)
  27:        */
  28:       size = BLKLOC(arg1)->list.cursize;
  29:       cplist(&arg1, &arg0, 1, size + 1);
  30:       qsort(BLKLOC(BLKLOC(arg0)->list.listhead)->lelem.lslots, size,
  31:             sizeof(struct descrip), anycmp);
  32:       }
  33: #ifdef SETS
  34:    else if (arg1.type == D_SET) {
  35:       /*
  36:        * Create a list the size of the set (or at least
  37:        *  LISTBLKSIZE), copy each element into the list, and
  38:        *  then sort the list using qsort as in list sorting
  39:        *  and return the sorted list.
  40:        */
  41:    nelem = size = BLKLOC(arg1)->set.setsize;
  42:    if(nelem < LISTBLKSIZE)
  43:       nelem = LISTBLKSIZE;
  44:    hneed(sizeof(struct b_list) + sizeof(struct b_lelem) +
  45:       nelem * sizeof(struct descrip));
  46: 
  47:    bp = BLKLOC(arg1);
  48:    lp = alclist(size);
  49:    lp->listhead.type = lp->listtail.type = D_LELEM;
  50:       BLKLOC(lp->listtail) = (union block *) alclstb(nelem,0,size);
  51:    BLKLOC(lp->listhead) = BLKLOC(lp->listtail);
  52:    if (size > 0) {  /* only need to sort non-empty sets */
  53:       d1 = BLKLOC(lp->listhead)->lelem.lslots;
  54:       for(i = 0; i < NBUCKETS; i++) {
  55:       ep = BLKLOC(bp->set.sbucks[i]);
  56:       while (ep != NULL) {
  57:          *d1 = ep->selem.setmem;
  58:          d1++;
  59:          ep = BLKLOC(ep->selem.sblink);
  60:          }
  61:       }
  62:       qsort(BLKLOC(lp->listhead)->lelem.lslots,size,sizeof(struct descrip),anycmp);
  63:    }
  64:    arg0.type = D_LIST;
  65:    BLKLOC(arg0) = (union block *) lp;
  66:    }
  67: #endif SETS
  68: 
  69:    else if (arg1.type == D_TABLE) {
  70:       /*
  71:        * Default i (the type of sort) to 1, and be sure that it is
  72:        *  either 1 or 2.
  73:        */
  74:       defshort(&arg2, 1);
  75:       if (INTVAL(arg2) != 1 && INTVAL(arg2) != 2)
  76:          runerr(205, &arg2);
  77: 
  78:       /*
  79:        * The list resulting from the sort will have as many elements as
  80:        *  the table has, so get that value and also make a valid list
  81:        *  block size out of it.
  82:        */
  83:       nelem = size = BLKLOC(arg1)->table.cursize;
  84:       if (nelem < LISTBLKSIZE)
  85:          nelem = LISTBLKSIZE;
  86:       /*
  87:        * Ensure space for: the list header block and a list element
  88:        *  block for the list which is to be returned,
  89:        *  a list header block and a list element block for each of the two
  90:        *  element lists the sorted list is to contain.  Note that the
  91:        *  calculation might be better expressed as:
  92:        *    list_header_size + list_block_size + nelem * descriptor_size +
  93:        *     nelem * (list_header_size + list_block_size + 2*descriptor_size)
  94:        */
  95:       hneed(sizeof(struct b_list) + sizeof(struct b_lelem) +
  96:          nelem * (sizeof(struct b_list) + sizeof(struct b_lelem) +
  97:             3 * sizeof(struct descrip)));
  98:       /*
  99:        * Point bp at the table header block of the table to be sorted
 100:        *  and point lp at a newly allocated list
 101:        *  that will hold the the result of sorting the table.
 102:        */
 103:       bp = BLKLOC(arg1);
 104:       lp = alclist(size);
 105:       lp->listhead.type = lp->listtail.type = D_LELEM;
 106:       BLKLOC(lp->listtail) = (union block *) alclstb(nelem, 0, size);
 107:       BLKLOC(lp->listhead) = BLKLOC(lp->listtail);
 108:       if (size > 0) { /* No need to sort the elements of an empty table */
 109:          /*
 110:           * Point d1 at the start of the list elements in the new list
 111:           *  element block in preparation for use as an index into the list.
 112:           */
 113:          d1 = BLKLOC(lp->listhead)->lelem.lslots;
 114:          /*
 115:           * Traverse the element chain for each table bucket.  For each
 116:           *  element, allocate a two-element list and put the table
 117:           *  entry value in the first element and the assigned value in
 118:           *  the second element.  The two-element list is assigned to
 119:           *  the descriptor that d1 points at.  When this is done, the
 120:           *  list of two-element lists is complete, but unsorted.
 121:           */
 122:          for (i = 0; i < NBUCKETS; i++) {
 123:             ep = BLKLOC(bp->table.buckets[i]);
 124:             while (ep != NULL) {
 125:                d1->type = D_LIST;
 126:                tp = alclist(2);
 127:                BLKLOC(*d1) = (union block *) tp;
 128:                tp->listhead.type = tp->listtail.type = D_LELEM;
 129:                BLKLOC(tp->listtail) = (union block *) alclstb(2, 0, 2);
 130:                BLKLOC(tp->listhead) = BLKLOC(tp->listtail);
 131:                BLKLOC(tp->listhead)->lelem.lslots[0] = ep->telem.tref;
 132:                BLKLOC(tp->listhead)->lelem.lslots[1] = ep->telem.tval;
 133:                d1++;
 134:                ep = BLKLOC(ep->telem.blink);
 135:                }
 136:             }
 137:          /*
 138:           * Sort the resulting two-element list using the sorting function
 139:           *  determined by i.
 140:           */
 141:          if (INTVAL(arg2) == 1)
 142:             qsort(BLKLOC(lp->listhead)->lelem.lslots, size,
 143:                   sizeof(struct descrip), trefcmp);
 144:          else
 145:             qsort(BLKLOC(lp->listhead)->lelem.lslots, size,
 146:                   sizeof(struct descrip), tvalcmp);
 147:          }
 148:       /*
 149:        * Make arg0 point at the sorted list.
 150:        */
 151:       arg0.type = D_LIST;
 152:       BLKLOC(arg0) = (union block *) lp;
 153:       }
 154:    else /* Tried to sort something that wasn't a list or a table. */
 155:       runerr(115, &arg1);
 156:    }
 157: 
 158: Procblock(sort,2)
 159: 
 160: /*
 161:  * trefcmp(d1,d2) - compare two-element lists on first field.
 162:  */
 163: 
 164: trefcmp(d1,d2)
 165: struct descrip *d1, *d2;
 166:    {
 167:    extern anycmp();
 168: 
 169:    if (d1->type != D_LIST || d2->type != D_LIST)
 170:       syserr("trefcmp: internal consistency check fails.");
 171:    return (anycmp(&(BLKLOC(BLKLOC(*d1)->list.listhead)->lelem.lslots[0]),
 172:                   &(BLKLOC(BLKLOC(*d2)->list.listhead)->lelem.lslots[0])));
 173:    }
 174: 
 175: /*
 176:  * tvalcmp(d1,d2) - compare two-element lists on second field.
 177:  */
 178: 
 179: tvalcmp(d1,d2)
 180: struct descrip *d1, *d2;
 181:    {
 182:    extern anycmp();
 183: 
 184:    if (d1->type != D_LIST || d2->type != D_LIST)
 185:       syserr("tvalcmp: internal consistency check fails.");
 186:    return (anycmp(&(BLKLOC(BLKLOC(*d1)->list.listhead)->lelem.lslots[1]),
 187:                   &(BLKLOC(BLKLOC(*d2)->list.listhead)->lelem.lslots[1])));
 188:    }

Defined functions