Return to sort.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / icon / functions

Annotation of 43BSD/contrib/icon/functions/sort.c, revision 1.1

1.1     ! root        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:    }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.