chiark - git - mdw - qmail/blob - prioq.c

   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_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 }