summaryrefslogtreecommitdiff
path: root/prioq.c
diff options
context:
space:
mode:
authorJohn Denker <jsd@av8n.com>2012-06-02 01:58:45 (GMT)
committerJohn Denker <jsd@av8n.com>2012-06-02 01:58:45 (GMT)
commitb732a73bc773789894466b0e5320b2f1fe42c7e9 (patch)
tree385358983f064a1f10a5080b33a3ba13010886db /prioq.c
parent634d365a03cb0581a062cd3cf4db9ae69f1cde26 (diff)
original, as downloaded from http://www.qmail.org/netqmail-1.06.tar.gz
Diffstat (limited to 'prioq.c')
-rw-r--r--prioq.c58
1 files changed, 58 insertions, 0 deletions
diff --git a/prioq.c b/prioq.c
new file mode 100644
index 0000000..051aa45
--- /dev/null
+++ b/prioq.c
@@ -0,0 +1,58 @@
+#include "alloc.h"
+#include "gen_allocdefs.h"
+#include "prioq.h"
+
+GEN_ALLOC_readyplus(prioq,struct prioq_elt,p,len,a,i,n,x,100,prioq_readyplus)
+
+int prioq_insert(pq,pe)
+prioq *pq;
+struct prioq_elt *pe;
+{
+ int i;
+ int j;
+ if (!prioq_readyplus(pq,1)) return 0;
+ j = pq->len++;
+ while (j)
+ {
+ i = (j - 1)/2;
+ if (pq->p[i].dt <= pe->dt) break;
+ pq->p[j] = pq->p[i];
+ j = i;
+ }
+ pq->p[j] = *pe;
+ return 1;
+}
+
+int prioq_min(pq,pe)
+prioq *pq;
+struct prioq_elt *pe;
+{
+ if (!pq->p) return 0;
+ if (!pq->len) return 0;
+ *pe = pq->p[0];
+ return 1;
+}
+
+void prioq_delmin(pq)
+prioq *pq;
+{
+ int i;
+ int j;
+ int n;
+ if (!pq->p) return;
+ n = pq->len;
+ if (!n) return;
+ i = 0;
+ --n;
+ for (;;)
+ {
+ j = i + i + 2;
+ if (j > n) break;
+ if (pq->p[j - 1].dt <= pq->p[j].dt) --j;
+ if (pq->p[n].dt <= pq->p[j].dt) break;
+ pq->p[i] = pq->p[j];
+ i = j;
+ }
+ pq->p[i] = pq->p[n];
+ pq->len = n;
+}