diff options
author | John Denker <jsd@av8n.com> | 2012-06-01 18:58:45 -0700 |
---|---|---|
committer | John Denker <jsd@av8n.com> | 2012-06-01 18:58:45 -0700 |
commit | b732a73bc773789894466b0e5320b2f1fe42c7e9 (patch) | |
tree | 385358983f064a1f10a5080b33a3ba13010886db /prioq.c | |
parent | 634d365a03cb0581a062cd3cf4db9ae69f1cde26 (diff) |
original, as downloaded from http://www.qmail.org/netqmail-1.06.tar.gz
Diffstat (limited to 'prioq.c')
-rw-r--r-- | prioq.c | 58 |
1 files changed, 58 insertions, 0 deletions
@@ -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; +} |