1 #include "alloc.h"
2 #include "gen_allocdefs.h"
3 #include "prioq.h"
4
5 GEN_ALLOC_readyplus(prioq,struct prioq_elt,p,len,a,i,n,x,100,prioq_readyplus)
6
7 int prioq_min(pq,pe)
8 prioq *pq;
9 struct prioq_elt *pe;
10 {
11 struct prioq_elt *x;
12
13 x = pq->p;
14 if (!x) return 0;
15 if (!pq->len) return 0;
16 *pe = x[0];
17 return 1;
18 }
19
prioq_insert(pq,pe)20 int prioq_insert(pq,pe)
21 prioq *pq;
22 struct prioq_elt *pe;
23 {
24 int i;
25 int j;
26 struct prioq_elt *x;
27
28 if (!prioq_readyplus(pq,1)) return 0;
29 x = pq->p;
30
31 i = pq->len++;
32 while (i) {
33 j = (i - 1) >> 1;
34 if (x[j].dt <= pe->dt) break;
35 x[i] = x[j];
36 i = j;
37 }
38 x[i] = *pe;
39
40 return 1;
41 }
42
prioq_delmin(pq)43 void prioq_delmin(pq)
44 prioq *pq;
45 {
46 int i;
47 int j;
48 int n;
49 struct prioq_elt *x;
50
51 x = pq->p;
52 if (!x) return;
53
54 n = pq->len;
55 if (!n) return;
56 --n;
57 pq->len = n;
58
59 i = 1;
60 while ((j = i + i) < n) {
61 if (x[j].dt > x[j - 1].dt) {
62 x[i - 1] = x[j];
63 i = j + 1;
64 }
65 else {
66 x[i - 1] = x[j - 1];
67 i = j;
68 }
69 }
70 if (j == n) {
71 x[i - 1] = x[j - 1];
72 i = j;
73 }
74 while (i > 1) {
75 j = i >> 1;
76 if (x[n].dt <= x[j - 1].dt) break;
77 x[i - 1] = x[j - 1];
78 i = j;
79 }
80 x[i - 1] = x[n];
81 }
82