Fossil

*/
void compute_ancestors(int rid, int N){
  Bag seen;
  PQueue queue;
  Stmt ins;
  Stmt q;
  bag_init(&seen);
  pqueuex_init(&queue);
  bag_insert(&seen, rid);
  pqueuex_insert(&queue, rid, 0.0, 0);
  db_prepare(&ins, "INSERT OR IGNORE INTO ok VALUES(:rid)");
  db_prepare(&q,
    "SELECT a.pid, b.mtime FROM plink a LEFT JOIN plink b ON b.cid=a.pid"
    " WHERE a.cid=:rid"
  );
  while( (N--)>0 && (rid = pqueuex_extract(&queue, 0))!=0 ){
    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);
    db_bind_int(&q, ":rid", rid);
    while( db_step(&q)==SQLITE_ROW ){
      int pid = db_column_int(&q, 0);
      double mtime = db_column_double(&q, 1);
      if( bag_insert(&seen, pid) ){
        pqueuex_insert(&queue, pid, -mtime, 0);
      }
    }
    db_reset(&q);
  }
  bag_clear(&seen);
  pqueuex_clear(&queue);
  db_finalize(&ins);
  db_finalize(&q);
}

/*
** Compute up to N direct ancestors (merge ancestors do not count)
** for the check-in rid and put them in a table named "ancestor".

void compute_descendants(int rid, int N){
  Bag seen;
  PQueue queue;
  Stmt ins;
  Stmt q;

  bag_init(&seen);
  pqueuex_init(&queue);
  bag_insert(&seen, rid);
  pqueuex_insert(&queue, rid, 0.0, 0);
  db_prepare(&ins, "INSERT OR IGNORE INTO ok VALUES(:rid)");
  db_prepare(&q, "SELECT cid, mtime FROM plink WHERE pid=:rid");
  while( (N--)>0 && (rid = pqueuex_extract(&queue, 0))!=0 ){
    db_bind_int(&ins, ":rid", rid);
    db_step(&ins);
    db_reset(&ins);
    db_bind_int(&q, ":rid", rid);
    while( db_step(&q)==SQLITE_ROW ){
      int pid = db_column_int(&q, 0);
      double mtime = db_column_double(&q, 1);
      if( bag_insert(&seen, pid) ){
        pqueuex_insert(&queue, pid, mtime, 0);
      }
    }
    db_reset(&q);
  }
  bag_clear(&seen);
  pqueuex_clear(&queue);
  db_finalize(&ins);
  db_finalize(&q);
}

/*
** COMMAND: descendants*
**

** value.  We can insert integers with each integer tied to its
** value then extract the integer with the smallest value.
**
** The way this queue is used, we never expect it to contain more
** than 2 or 3 elements, so a simple array is sufficient as the
** implementation.  This could give worst case O(N) insert times,
** but because of the nature of the problem we expect O(1) performance.
**
** Compatibility note:  Some versions of OpenSSL export a symbols
** like "pqueue_insert".  This is, technically, a bug in OpenSSL.
** We work around it here by using "pqueuex_" instead of "pqueue_".
*/
#include "config.h"
#include "pqueue.h"
#include <assert.h>


#if INTERFACE

  } *a;
};
#endif

/*
** Initialize a PQueue structure
*/
void pqueuex_init(PQueue *p){
  memset(p, 0, sizeof(*p));
}

/*
** Destroy a PQueue.  Delete all of its content.
*/
void pqueuex_clear(PQueue *p){
  free(p->a);
  pqueuex_init(p);
}

/*
** Change the size of the queue so that it contains N slots
*/
static void pqueuex_resize(PQueue *p, int N){
  p->a = fossil_realloc(p->a, sizeof(p->a[0])*N);
  p->sz = N;
}

/*
** Insert element e into the queue.
*/
void pqueuex_insert(PQueue *p, int e, double v, void *pData){
  int i, j;
  if( p->cnt+1>p->sz ){
    pqueuex_resize(p, p->cnt+5);
  }
  for(i=0; i<p->cnt; i++){
    if( p->a[i].value>v ){
      for(j=p->cnt; j>i; j--){
        p->a[j] = p->a[j-1];
      }
      break;
    }
  }
  p->a[i].id = e;
  p->a[i].p = pData;
  p->a[i].value = v;
  p->cnt++;
}

/*
** Extract the first element from the queue (the element with
** the smallest value) and return its ID.  Return 0 if the queue
** is empty.
*/
int pqueuex_extract(PQueue *p, void **pp){
  int e, i;
  if( p->cnt==0 ){
    if( pp ) *pp = 0;
    return 0;
  }
  e = p->a[0].id;
  if( pp ) *pp = p->a[0].p;
  for(i=0; i<p->cnt-1; i++){
    p->a[i] = p->a[i+1];
  }
  p->cnt--;
  return e;
}

){
  PQueue queue;        /* Queue of check-ins to be tagged */
  Stmt s;              /* Query the children of :pid to which to propagate */
  Stmt ins;            /* INSERT INTO tagxref */
  Stmt eventupdate;    /* UPDATE event */

  assert( tagType==0 || tagType==2 );
  pqueuex_init(&queue);
  pqueuex_insert(&queue, pid, 0.0, 0);

  /* Query for children of :pid to which to propagate the tag.
  ** Three returns:  (1) rid of the child.  (2) timestamp of child.
  ** (3) True to propagate or false to block.
  */
  db_prepare(&s, 
     "SELECT cid, plink.mtime,"

    );
  }
  if( tagid==TAG_BGCOLOR ){
    db_prepare(&eventupdate,
      "UPDATE event SET bgcolor=%Q WHERE objid=:rid", zValue
    );
  }
  while( (pid = pqueuex_extract(&queue, 0))!=0 ){
    db_bind_int(&s, ":pid", pid);
    while( db_step(&s)==SQLITE_ROW ){
      int doit = db_column_int(&s, 2);
      if( doit ){
        int cid = db_column_int(&s, 0);
        double mtime = db_column_double(&s, 1);
        pqueuex_insert(&queue, cid, mtime, 0);
        db_bind_int(&ins, ":rid", cid);
        db_step(&ins);
        db_reset(&ins);
        if( tagid==TAG_BGCOLOR ){
          db_bind_int(&eventupdate, ":rid", cid);
          db_step(&eventupdate);
          db_reset(&eventupdate);
        }
        if( tagid==TAG_BRANCH ){
          leaf_eventually_check(cid);
        }
      }
    }
    db_reset(&s);
  }
  pqueuex_clear(&queue);
  db_finalize(&ins);
  db_finalize(&s);
  if( tagid==TAG_BGCOLOR ){
    db_finalize(&eventupdate);
  }
}