nightmaremail

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs

prioq.c (865B)

      1 #include "prioq.h"
      2 
      3 #include "gen_allocdefs.h"
      4 
      5 GEN_ALLOC_readyplus(prioq,struct prioq_elt,p,len,a,100,prioq_readyplus)
      6 
      7 int prioq_insert(pq,pe)
      8 prioq *pq;
      9 struct prioq_elt *pe;
     10 {
     11  int i;
     12  int j;
     13  if (!prioq_readyplus(pq,1)) return 0;
     14  j = pq->len++;
     15  while (j)
     16   {
     17    i = (j - 1)/2;
     18    if (pq->p[i].dt <= pe->dt) break;
     19    pq->p[j] = pq->p[i];
     20    j = i;
     21   }
     22  pq->p[j] = *pe;
     23  return 1;
     24 }
     25 
     26 int prioq_min(pq,pe)
     27 prioq *pq;
     28 struct prioq_elt *pe;
     29 {
     30  if (!pq->p) return 0;
     31  if (!pq->len) return 0;
     32  *pe = pq->p[0];
     33  return 1;
     34 }
     35 
     36 void prioq_delmin(pq)
     37 prioq *pq;
     38 {
     39  int i;
     40  int j;
     41  int n;
     42  if (!pq->p) return;
     43  n = pq->len;
     44  if (!n) return;
     45  i = 0;
     46  --n;
     47  for (;;)
     48   {
     49    j = i + i + 2;
     50    if (j > n) break;
     51    if (pq->p[j - 1].dt <= pq->p[j].dt) --j;
     52    if (pq->p[n].dt <= pq->p[j].dt) break;
     53    pq->p[i] = pq->p[j];
     54    i = j;
     55   }
     56  pq->p[i] = pq->p[n];
     57  pq->len = n;
     58 }