![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to heap.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 41BSD / cmd / cifplot|
Return to heap.c CVS log | Up to [CSRG BSD Unix] / 41BSD / cmd / cifplot |
1.1 root 1: /*******************************************************************
2: * *
3: * File: CIFPLOT/heap.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 "structs.h"
12: #include "out_structs.h"
13:
14: #define INITHSIZE 256
15: #define FATHER(a) ((a)-1)/2
16: #define LEFTSON(a) ((a)+1)*2 - 1
17: #define RIGHTSON(a) ((a)+1)*2
18:
19: #define COMPARE(x,s) h.h[x]->min - h.h[s]->min
20: #define LESSEQUAL(x,s) h.h[x]->min <= h.h[s]->min
21: #define GREATERTHAN(x,s) h.h[x]->min > h.h[s]->min
22: #define SWITCH(x,y) { HTemp = h.h[x]; h.h[x] = h.h[y]; h.h[y] = HTemp; }
23:
24: instance *HTemp;
25:
26: typedef struct temp723 {
27: instance **h;
28: int size,n;
29: } Heap;
30:
31: int UnActMark = -INFINITY;
32:
33: Heap h;
34:
35: InitHeap()
36: /* Allocate space and initalize pointers */
37: {
38: h.h = (instance **) alloc(INITHSIZE*sizeof(instance *));
39: h.n = 0;
40: h.size = INITHSIZE;
41: }
42:
43: PutHeap(v)
44: instance *v;
45: /* Put what v points to into a heap where f is a function
46: that compares values. */
47: {
48: register int a,f;
49:
50: if(h.n == h.size) {
51: h.size *= 2;
52: h.h = (instance **) expand(h.h,h.size*sizeof(instance *));
53: }
54: h.h[h.n] = v;
55: a = h.n++;
56: f = FATHER(a);
57: while(a > 0 && GREATERTHAN(f,a)) {
58: SWITCH(f,a);
59: a = f;
60: f = FATHER(a);
61: }
62: }
63:
64: instance *
65: PeekHeap()
66: {
67: if(h.n == 0) return(NIL);
68: return(h.h[0]);
69: }
70:
71: instance *
72: GetHeap()
73: {
74: register instance *hold;
75:
76: if(h.n != 0) {
77: hold = h.h[0];
78: --h.n;
79: SWITCH(0,h.n);
80: SortHeap(0);
81: return(hold);
82: }
83: else
84: return(NIL);
85: }
86:
87: SortHeap(a)
88: register int a;
89: {
90: register int r,l;
91:
92: while(1) {
93: if((l=LEFTSON(a)) >= h.n) return;
94: if((r=RIGHTSON(a)) >= h.n) {
95: if(GREATERTHAN(a,l))
96: SWITCH(a,l);
97: return;
98: }
99: if(LESSEQUAL(a,r) && LESSEQUAL(a,l)) return;
100: if(LESSEQUAL(l,r)) {
101: SWITCH(a,l);
102: a = l;
103: }
104: else {
105: SWITCH(a,r);
106: a = r;
107: }
108: }
109: }
110:
111: #define UHASH(x) ABS((((int) x) % UTBLSIZE))
112:
113: List UnAct[UTBLSIZE];
114: int UnActCount = 111;
115:
116: InitUnAct()
117: {
118: int i;
119: for(i=0;i<UTBLSIZE;i++)
120: InitList(&(UnAct[i]));
121: UnActCount = 0;
122: }
123:
124: FindNext(n)
125: register int n;
126: {
127: register instance *p;
128: register int i;
129:
130: for(i=0;i<16;i++) {
131: p = (instance *) &(UnAct[UHASH(n+i)]);
132: if(p->Link != NIL && p->Link->min == n+i) {
133: NextUnAct = MIN(n+i,Top);
134: return(NextUnAct);
135: }
136: }
137: NextUnAct = MIN(n+i,Top);
138: return(NextUnAct);
139: }
140:
141: PutUnAct(e)
142: instance *e;
143: {
144: register instance *p;
145: register List *l;
146:
147: if(e->min < UnActMark)
148: /*
149: if(e->min == UnActMark-1)
150: /* Let's ignore floating point round off errors */
151: /*
152: e->min = UnActMark;
153: else
154: */
155: Error("Element submitted past deadline in PutUnAct",INTERNAL);
156: UnActCount++;
157: l = &(UnAct[UHASH(e->min)]);
158: e->Link = NIL;
159: if(l->Link == NIL) {
160: l->Link = (Element *) e;
161: return;
162: }
163: for(p = (instance *) l; p->Link != NIL; p=p->Link)
164: if(e->min <= p->Link->min) {
165: e->Link = p->Link;
166: p->Link = e;
167: return;
168: }
169: p->Link = e;
170: return;
171: }
172:
173: instance *
174: GetUnAct(i)
175: int i;
176: {
177: register instance *e;
178: register List *l;
179:
180: if(i < UnActMark)
181: Error("GetUnAct called in bad order",INTERNAL);
182: UnActMark = i;
183: l = &(UnAct[UHASH(i)]);
184:
185: e = (instance *) l->Link;
186: if(e==NIL) return(NIL);
187: if(e->min == i) {
188: l->Link = (Element *) e->Link;
189: e->Link = NIL;
190: --UnActCount;
191: return(e);
192: }
193: if(e->min > i) {
194: return(NIL);
195: }
196: Error("UnActiveList is out of order",INTERNAL);
197: return(NIL);
198: }
199:
200: CheckUnAct() {
201: int i;
202: for(i=0;i<UTBLSIZE;i++)
203: if(UnAct[i].Link!=NIL) {
204: fprintf(stderr,"UnActiveList is NOT empty\n");
205: return;
206: }
207: fprintf(stderr,"the un active list is empty\n");
208: if(UnActCount != 0) {
209: fprintf(stderr,"the count is %d\n",UnActCount);
210: }
211: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.