![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to sort.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSD / contrib / icon / functions|
Return to sort.c CVS log | Up to [CSRG BSD Unix] / 43BSD / contrib / icon / functions |
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.