![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to queue.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / cmd / cifplot|
Return to queue.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / cifplot |
1.1 root 1: /*******************************************************************
2: * *
3: * File: CIFPLOT/queue.c *
4: * Written by Dan Fitzpatrick *
5: * copyright 1980 -- Regents of the University of California *
6: * *
7: ********************************************************************/
8:
9: #include <stdio.h>
10: #include "defs.h"
11: #include "globals.h"
12: #include "structs.h"
13: #include "out_structs.h"
14:
15: IMPORT Element *GetList();
16:
17: InitQueue(q)
18: Queue *q;
19: {
20: q->QStart = NIL;
21: }
22:
23: PutQueue(e,q)
24: Queue *q;
25: Element *e;
26: /* Put element `e' into queue `q' */
27: {
28: e->Link = NIL;
29: if(q->QStart == NIL) {
30: q->QStart = q->QEnd = e;
31: return;
32: }
33: q->QEnd->Link = e;
34: q->QEnd = e;
35: return;
36: }
37:
38: Element *
39: GetQueue(q)
40: Queue *q;
41: /* Return the element at the front of the queue `q'
42: * If the queue is empty return NIL */
43: {
44: register Element *e;
45: e = q->QStart;
46: if(q->QStart != NIL) q->QStart = q->QStart->Link;
47: return(e);
48: }
49:
50: CatQueue(q1,q2)
51: Queue *q1,*q2;
52: /* Tack q2 onto the end of q1 */
53: {
54: if(q1->QStart == NIL)
55: q1->QStart = q2->QStart;
56: else
57: q1->QEnd->Link = q2->QStart;
58: if(q2->QStart != NIL)
59: q1->QEnd = q2->QEnd;
60: }
61:
62: MoveQueue(q1,q2)
63: Queue *q1,*q2;
64: /* Make q1 point to the same queue as q2 */
65: {
66: q1->QStart = q2->QStart;
67: q1->QEnd = q2->QEnd;
68: }
69:
70: InitList(l)
71: List *l;
72: {
73: l->Link = NIL;
74: }
75:
76: PutList(e,l,f)
77: List *l;
78: Element *e;
79: real (*f)();
80: /* Insert element `e' into list `l' maintaining the ascending
81: * order of the list where `f' is a function of two arguments
82: * giving the ordinality of the elements.
83: * So if two elements `i' & `j' are compared then
84: * f(i,j) <= 0 iff i <= j.
85: * If the ordering doesn't matter substitute 0 for f */
86: {
87: Element *p;
88:
89: e->Link = NIL;
90: if(f == 0) {
91: e->Link = l->Link;
92: l->Link = e;
93: return;
94: }
95: if(l->Link == NIL) {
96: l->Link = e;
97: return;
98: }
99:
100: for(p= (Element *) l;p->Link != NIL; p=p->Link)
101: if((*f)(e,p->Link) <= 0.0) {
102: e->Link = p->Link;
103: p->Link = e;
104: return;
105: }
106: p->Link = e;
107: return;
108: }
109:
110: MergeActives(i,list)
111: int i;
112: List *list;
113: {
114: Element *p,*e;
115:
116: if(ActiveEdges[i].Link == NIL) {
117: ActiveEdges[i].Link = list->Link;
118: list->Link = NIL;
119: return;
120: }
121: e = GetList(list);
122: if(e == NIL) return;
123:
124: for(p= (Element *) &(ActiveEdges[i]);p->Link != NIL; p=p->Link)
125: if(((edge *) e)->iy <= ((edge *) p->Link)->iy) {
126: e->Link = p->Link;
127: p->Link = e;
128: e = GetList(list);
129: if(e == NIL) return;
130: }
131: p->Link = e;
132: e->Link = list->Link;
133: list->Link = NIL;
134: return;
135: }
136:
137: Element *
138: GetList(l)
139: List *l;
140: /* Return the element at the front of the list `l' */
141: {
142: register Element *e;
143: e = l->Link;
144: if(e != NIL) l->Link = l->Link->Link;
145: return(e);
146: }
147:
148: Element *
149: PeekList(l)
150: List *l;
151: /* return pointer to first element in list without removing it */
152: {
153: return(l->Link);
154: }
155:
156: SortList(l,f)
157: List *l;
158: real (*f)();
159: /* sort list l with fuction f as in PutList */
160: {
161: register Element *e,*t1,*t2;
162: int sorted;
163:
164: if( (l->Link == NIL) || (l->Link->Link == NIL) ) return;
165: sorted = 0;
166: while(!sorted) {
167: sorted = 1;
168: for(e = (Element *) l; e->Link->Link != NIL; e=e->Link)
169: if((*f)(e->Link,e->Link->Link) > 0.0) {
170: t1 = e->Link;
171: t2 = t1->Link;
172: t1->Link = t2->Link;
173: t2->Link = t1;
174: e->Link = t2;
175: sorted = 0;
176: }
177: }
178: }
179:
180: int sortcnt = 0;
181:
182: SortActives(i)
183: int i;
184: /* Does a bubble sort on ActiveList[i] */
185: {
186: register Element *e,*t1,*t2;
187: Element *last;
188: int sorted;
189:
190: if( (ActiveEdges[i].Link == NIL) || (ActiveEdges[i].Link->Link == NIL) ) return;
191: sorted = 0;
192: last = NIL;
193: while(!sorted) {
194: sorted = 1;
195: sortcnt++;
196: for(e = (Element *) &(ActiveEdges[i]); e->Link->Link != last; e=e->Link) {
197: if(((edge *) e->Link)->iy > ((edge *) e->Link->Link)->iy) {
198: change[i] = 1;
199: t1 = e->Link;
200: t2 = t1->Link;
201: t1->Link = t2->Link;
202: t2->Link = t1;
203: e->Link = t2;
204: sorted = 0;
205: }
206: }
207: last = t1;
208: }
209: }
210:
211: SortSummary()
212: {
213: printf("%d Sort Scans\n",sortcnt);
214: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.