4.3BSD/usr/contrib/icon/functions/sort.c
#include "../h/rt.h"
/*
* sort(l) - sort list l.
* sort(S) - sort set S.
* sort(t,i) - sort table on reference (i = 1) or value (i = 2) field.
*/
Xsort(nargs, arg2, arg1, arg0)
int nargs;
struct descrip arg2, arg1, arg0;
{
register struct descrip *d1;
register int size, i;
int nelem;
struct b_list *lp, *tp;
union block *bp, *ep;
extern struct b_list *alclist();
extern struct b_lelem *alclstb();
extern anycmp(), trefcmp(), tvalcmp();
DeRef(arg1)
if (arg1.type == D_LIST) {
/*
* Sort the list by copying it into a new list and then using
* qsort to sort the descriptors. (That was easy!)
*/
size = BLKLOC(arg1)->list.cursize;
cplist(&arg1, &arg0, 1, size + 1);
qsort(BLKLOC(BLKLOC(arg0)->list.listhead)->lelem.lslots, size,
sizeof(struct descrip), anycmp);
}
#ifdef SETS
else if (arg1.type == D_SET) {
/*
* Create a list the size of the set (or at least
* LISTBLKSIZE), copy each element into the list, and
* then sort the list using qsort as in list sorting
* and return the sorted list.
*/
nelem = size = BLKLOC(arg1)->set.setsize;
if(nelem < LISTBLKSIZE)
nelem = LISTBLKSIZE;
hneed(sizeof(struct b_list) + sizeof(struct b_lelem) +
nelem * sizeof(struct descrip));
bp = BLKLOC(arg1);
lp = alclist(size);
lp->listhead.type = lp->listtail.type = D_LELEM;
BLKLOC(lp->listtail) = (union block *) alclstb(nelem,0,size);
BLKLOC(lp->listhead) = BLKLOC(lp->listtail);
if (size > 0) { /* only need to sort non-empty sets */
d1 = BLKLOC(lp->listhead)->lelem.lslots;
for(i = 0; i < NBUCKETS; i++) {
ep = BLKLOC(bp->set.sbucks[i]);
while (ep != NULL) {
*d1 = ep->selem.setmem;
d1++;
ep = BLKLOC(ep->selem.sblink);
}
}
qsort(BLKLOC(lp->listhead)->lelem.lslots,size,sizeof(struct descrip),anycmp);
}
arg0.type = D_LIST;
BLKLOC(arg0) = (union block *) lp;
}
#endif SETS
else if (arg1.type == D_TABLE) {
/*
* Default i (the type of sort) to 1, and be sure that it is
* either 1 or 2.
*/
defshort(&arg2, 1);
if (INTVAL(arg2) != 1 && INTVAL(arg2) != 2)
runerr(205, &arg2);
/*
* The list resulting from the sort will have as many elements as
* the table has, so get that value and also make a valid list
* block size out of it.
*/
nelem = size = BLKLOC(arg1)->table.cursize;
if (nelem < LISTBLKSIZE)
nelem = LISTBLKSIZE;
/*
* Ensure space for: the list header block and a list element
* block for the list which is to be returned,
* a list header block and a list element block for each of the two
* element lists the sorted list is to contain. Note that the
* calculation might be better expressed as:
* list_header_size + list_block_size + nelem * descriptor_size +
* nelem * (list_header_size + list_block_size + 2*descriptor_size)
*/
hneed(sizeof(struct b_list) + sizeof(struct b_lelem) +
nelem * (sizeof(struct b_list) + sizeof(struct b_lelem) +
3 * sizeof(struct descrip)));
/*
* Point bp at the table header block of the table to be sorted
* and point lp at a newly allocated list
* that will hold the the result of sorting the table.
*/
bp = BLKLOC(arg1);
lp = alclist(size);
lp->listhead.type = lp->listtail.type = D_LELEM;
BLKLOC(lp->listtail) = (union block *) alclstb(nelem, 0, size);
BLKLOC(lp->listhead) = BLKLOC(lp->listtail);
if (size > 0) { /* No need to sort the elements of an empty table */
/*
* Point d1 at the start of the list elements in the new list
* element block in preparation for use as an index into the list.
*/
d1 = BLKLOC(lp->listhead)->lelem.lslots;
/*
* Traverse the element chain for each table bucket. For each
* element, allocate a two-element list and put the table
* entry value in the first element and the assigned value in
* the second element. The two-element list is assigned to
* the descriptor that d1 points at. When this is done, the
* list of two-element lists is complete, but unsorted.
*/
for (i = 0; i < NBUCKETS; i++) {
ep = BLKLOC(bp->table.buckets[i]);
while (ep != NULL) {
d1->type = D_LIST;
tp = alclist(2);
BLKLOC(*d1) = (union block *) tp;
tp->listhead.type = tp->listtail.type = D_LELEM;
BLKLOC(tp->listtail) = (union block *) alclstb(2, 0, 2);
BLKLOC(tp->listhead) = BLKLOC(tp->listtail);
BLKLOC(tp->listhead)->lelem.lslots[0] = ep->telem.tref;
BLKLOC(tp->listhead)->lelem.lslots[1] = ep->telem.tval;
d1++;
ep = BLKLOC(ep->telem.blink);
}
}
/*
* Sort the resulting two-element list using the sorting function
* determined by i.
*/
if (INTVAL(arg2) == 1)
qsort(BLKLOC(lp->listhead)->lelem.lslots, size,
sizeof(struct descrip), trefcmp);
else
qsort(BLKLOC(lp->listhead)->lelem.lslots, size,
sizeof(struct descrip), tvalcmp);
}
/*
* Make arg0 point at the sorted list.
*/
arg0.type = D_LIST;
BLKLOC(arg0) = (union block *) lp;
}
else /* Tried to sort something that wasn't a list or a table. */
runerr(115, &arg1);
}
Procblock(sort,2)
/*
* trefcmp(d1,d2) - compare two-element lists on first field.
*/
trefcmp(d1,d2)
struct descrip *d1, *d2;
{
extern anycmp();
if (d1->type != D_LIST || d2->type != D_LIST)
syserr("trefcmp: internal consistency check fails.");
return (anycmp(&(BLKLOC(BLKLOC(*d1)->list.listhead)->lelem.lslots[0]),
&(BLKLOC(BLKLOC(*d2)->list.listhead)->lelem.lslots[0])));
}
/*
* tvalcmp(d1,d2) - compare two-element lists on second field.
*/
tvalcmp(d1,d2)
struct descrip *d1, *d2;
{
extern anycmp();
if (d1->type != D_LIST || d2->type != D_LIST)
syserr("tvalcmp: internal consistency check fails.");
return (anycmp(&(BLKLOC(BLKLOC(*d1)->list.listhead)->lelem.lslots[1]),
&(BLKLOC(BLKLOC(*d2)->list.listhead)->lelem.lslots[1])));
}