pqueue.c

一个内存数据库的源代码这是服务器端还有客户端

  }

  return GDK_SUCCEED;
}

/* removes the root element, puts the last element as root and moves it down */
int pqueue_dequeue_fltmax(BAT *h)
{
  BUN hbase;
  int hBUNsize;

  size_t num_elements;

  if (!(num_elements = BATcount(h))) {
	/* printf("pqueue_dequeue: Cannot dequeue from empty queue\n");*/
	return GDK_FAIL;
  }

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  /* copy last element to the first position*/
  memcpy(hbase, hbase+(num_elements-1)*hBUNsize, hBUNsize);

  /*delete last element*/
  BUNdelete(h, hbase+(num_elements-1)*hBUNsize, FALSE);

  pqueue_movedowntop_fltmax(h);
  return GDK_SUCCEED;
}

/* replaces the top element with the input if it is larger (smaller) and
 * updates the heap */
int pqueue_topreplace_fltmax(BAT *h,
		 oid *idx,
		 flt *el)
{
  BUN hbase;

  hbase = BUNfirst(h);

  if (*(flt *)BUNtloc(h,hbase) > *el) {
	memcpy(BUNhloc(h,hbase), idx, sizeof(oid));
	memcpy(BUNtloc(h,hbase), el, sizeof(flt));
	pqueue_movedowntop_fltmax(h);
  }
  
  return GDK_SUCCEED;
}

/* TopN, based on max-pqueue */

int pqueue_topn_voidfltmax(BAT **H, BAT *t, int *N)
{
  flt *v;
  size_t i, n = BATcount(t);
  oid idx = t->hseqbase;

  if ((size_t) *N < n)
	  n = (size_t) *N;
  do_pqueue_init(H,t,n);
  v = (flt*)BUNtail(t,BUNfirst(t));

  for(i=0; i<n; i++, idx++, v++) {
	pqueue_enqueue_fltmax(*H, &idx, v); 
  }
  n = BATcount(t);
  for(; i<n; i++, idx++, v++) {
	pqueue_topreplace_fltmax(*H, &idx, v); 
  }
  return GDK_SUCCEED;
}

int pqueue_topn_fltmax(BAT **H, BAT *t, int *N)
{
  size_t i, n = BATcount(t);
  int bs = BUNsize(t);
  char *p = BUNfirst(t);

  if ((size_t) *N < n)
	  n = (size_t) *N;
  do_pqueue_init(H,t,n);

  for(i=0; i<n; i++, p+=bs) {
	pqueue_enqueue_fltmax(*H, (oid*)BUNhloc(t,p), (flt*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_fltmax(*H, (oid*)BUNhloc(t,p), (flt*)BUNtloc(t,p)); 
  }
  return GDK_SUCCEED;
}


#line 332 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"



#line 342 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"


#line 331 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"
  
#line 156 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"
/*enqueue an element*/
int pqueue_enqueue_dblmin(BAT *h,
		 oid *idx, 
		 dbl *el)
{
  BUN hbase;
  BUN ins,cur;
  int hBUNsize;

  size_t p, posel;
  char ch;
  int i;

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  posel = BATcount(h); /*last position*/
  BUNins(h, (ptr)idx, (ptr)el, FALSE);
  ins = hbase+posel*hBUNsize;
  
  while(posel >0) {
	p=parent(posel);
	cur = hbase+p*hBUNsize;
	if (*(dbl *)BUNtloc(h,ins) < *(dbl *)BUNtloc(h,cur)) {
	  /* swap element with its parent */
	  for(i=0; i<hBUNsize; i++){
		ch= cur[i]; cur[i]= ins[i]; ins[i]= ch;
	  }
	  ins = cur;
	  posel = parent(posel);
	}
	else break;
  }
  h->hsorted = h->tsorted = FALSE;
  
  return GDK_SUCCEED;
}

/* moves down the root element */
/* used by dequeue (see below) */
int pqueue_movedowntop_dblmin(BAT *h)
{
  BUN hbase;
  BUN swp,cur;
  int hBUNsize;

  size_t swap, num_elems;

  size_t posel;
  char ch;
  int i;

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  cur = hbase;
  num_elems = BATcount(h);
  posel = 0;
  
  /*while posel is not a leaf and pqueue[posel].tail > any of childen*/
  while (posel*2+1 < num_elems) { /*there exists a left son*/
	if (posel*2+2< num_elems) { /*there exists a right son*/
	  if (*(dbl *)BUNtloc(h,hbase+(posel*2+1)*hBUNsize) <
	      *(dbl *)BUNtloc(h,hbase+(posel*2+2)*hBUNsize))
		swap = posel*2+1;
	  else
		swap = posel*2+2;
	} else
		swap = posel*2+1;

	swp = hbase+swap*hBUNsize;

	if (*(dbl *)BUNtloc(h,swp) < *(dbl *)BUNtloc(h,cur)) {
	  /*swap elements*/
	  for(i=0; i<hBUNsize; i++){
		ch= cur[i]; cur[i]= swp[i]; swp[i]= ch;
	  }
	  cur = swp;
	  posel = swap;
	} else 
		break;
  }

  return GDK_SUCCEED;
}

/* removes the root element, puts the last element as root and moves it down */
int pqueue_dequeue_dblmin(BAT *h)
{
  BUN hbase;
  int hBUNsize;

  size_t num_elements;

  if (!(num_elements = BATcount(h))) {
	/* printf("pqueue_dequeue: Cannot dequeue from empty queue\n");*/
	return GDK_FAIL;
  }

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  /* copy last element to the first position*/
  memcpy(hbase, hbase+(num_elements-1)*hBUNsize, hBUNsize);

  /*delete last element*/
  BUNdelete(h, hbase+(num_elements-1)*hBUNsize, FALSE);

  pqueue_movedowntop_dblmin(h);
  return GDK_SUCCEED;
}

/* replaces the top element with the input if it is larger (smaller) and
 * updates the heap */
int pqueue_topreplace_dblmin(BAT *h,
		 oid *idx,
		 dbl *el)
{
  BUN hbase;

  hbase = BUNfirst(h);

  if (*(dbl *)BUNtloc(h,hbase) < *el) {
	memcpy(BUNhloc(h,hbase), idx, sizeof(oid));
	memcpy(BUNtloc(h,hbase), el, sizeof(dbl));
	pqueue_movedowntop_dblmin(h);
  }
  
  return GDK_SUCCEED;
}

/* TopN, based on min-pqueue */

int pqueue_topn_voiddblmin(BAT **H, BAT *t, int *N)
{
  dbl *v;
  size_t i, n = BATcount(t);
  oid idx = t->hseqbase;

  if ((size_t) *N < n)
	  n = (size_t) *N;
  do_pqueue_init(H,t,n);
  v = (dbl*)BUNtail(t,BUNfirst(t));

  for(i=0; i<n; i++, idx++, v++) {
	pqueue_enqueue_dblmin(*H, &idx, v); 
  }
  n = BATcount(t);
  for(; i<n; i++, idx++, v++) {
	pqueue_topreplace_dblmin(*H, &idx, v); 
  }
  return GDK_SUCCEED;
}

int pqueue_topn_dblmin(BAT **H, BAT *t, int *N)
{
  size_t i, n = BATcount(t);
  int bs = BUNsize(t);
  char *p = BUNfirst(t);

  if ((size_t) *N < n)
	  n = (size_t) *N;
  do_pqueue_init(H,t,n);

  for(i=0; i<n; i++, p+=bs) {
	pqueue_enqueue_dblmin(*H, (oid*)BUNhloc(t,p), (dbl*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_dblmin(*H, (oid*)BUNhloc(t,p), (dbl*)BUNtloc(t,p)); 
  }
  return GDK_SUCCEED;
}


#line 331 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"

  
#line 156 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"
/*enqueue an element*/
int pqueue_enqueue_dblmax(BAT *h,
		 oid *idx, 
		 dbl *el)
{
  BUN hbase;
  BUN ins,cur;
  int hBUNsize;

  size_t p, posel;
  char ch;
  int i;

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  posel = BATcount(h); /*last position*/
  BUNins(h, (ptr)idx, (ptr)el, FALSE);
  ins = hbase+posel*hBUNsize;
  
  while(posel >0) {
	p=parent(posel);
	cur = hbase+p*hBUNsize;
	if (*(dbl *)BUNtloc(h,ins) > *(dbl *)BUNtloc(h,cur)) {
	  /* swap element with its parent */
	  for(i=0; i<hBUNsize; i++){
		ch= cur[i]; cur[i]= ins[i]; ins[i]= ch;
	  }
	  ins = cur;
	  posel = parent(posel);
	}
	else break;
  }
  h->hsorted = h->tsorted = FALSE;
  
  return GDK_SUCCEED;
}

/* moves down the root element */
/* used by dequeue (see below) */
int pqueue_movedowntop_dblmax(BAT *h)
{
  BUN hbase;
  BUN swp,cur;
  int hBUNsize;

  size_t swap, num_elems;

  size_t posel;
  char ch;
  int i;

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  cur = hbase;
  num_elems = BATcount(h);
  posel = 0;
  
  /*while posel is not a leaf and pqueue[posel].tail > any of childen*/
  while (posel*2+1 < num_elems) { /*there exists a left son*/
	if (posel*2+2< num_elems) { /*there exists a right son*/
	  if (*(dbl *)BUNtloc(h,hbase+(posel*2+1)*hBUNsize) >
	      *(dbl *)BUNtloc(h,hbase+(posel*2+2)*hBUNsize))
		swap = posel*2+1;
	  else
		swap = posel*2+2;
	} else
		swap = posel*2+1;

	swp = hbase+swap*hBUNsize;

	if (*(dbl *)BUNtloc(h,swp) > *(dbl *)BUNtloc(h,cur)) {
	  /*swap elements*/
	  for(i=0; i<hBUNsize; i++){
		ch= cur[i]; cur[i]= swp[i]; swp[i]= ch;
	  }
	  cur = swp;
	  posel = swap;
	} else 
		break;
  }

  return GDK_SUCCEED;
}

/* removes the root element, puts the last element as root and moves it down */
int pqueue_dequeue_dblmax(BAT *h)
{
  BUN hbase;
  int hBUNsize;

  size_t num_elements;

  if (!(num_elements = BATcount(h))) {
	/* printf("pqueue_dequeue: Cannot dequeue from empty queue\n");*/
	return GDK_FAIL;
  }

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  /* copy last element to the first position*/
  memcpy(hbase, hbase+(num_elements-1)*hBUNsize, hBUNsize);

  /*delete last element*/
  BUNdelete(h, hbase+(num_elements-1)*hBUNsize, FALSE);

  pqueue_movedowntop_dblmax(h);
  return GDK_SUCCEED;
}

/* replaces the top element with the input if it is larger (smaller) and
 * updates the heap */
int pqueue_topreplace_dblmax(BAT *h,
		 oid *idx,
		 dbl *el)
{
  BUN hbase;

  hbase = BUNfirst(h);

  if (*(dbl *)BUNtloc(h,hbase) > *el) {
	memcpy(BUNhloc(h,hbase), idx, sizeof(oid));
	memcpy(BUNtloc(h,hbase), el, sizeof(dbl));
	pqueue_movedowntop_dblmax(h);
  }
  
  return GDK_SUCCEED;
}

/* TopN, based on max-pqueue */

int pqueue_topn_voiddblmax(BAT **H, BAT *t, int *N)
{
  dbl *v;
  size_t i, n = BATcount(t);
  oid idx = t->hseqbase;

  if ((size_t) *N < n)
	  n = (size_t) *N;
  do_pqueue_init(H,t,n);
  v = (dbl*)BUNtail(t,BUNfirst(t));

  for(i=0; i<n; i++, idx++, v++) {
	pqueue_enqueue_dblmax(*H, &idx, v); 
  }
  n = BATcount(t);
  for(; i<n; i++, idx++, v++) {
	pqueue_topreplace_dblmax(*H, &idx, v); 
  }
  return GDK_SUCCEED;
}

int pqueue_topn_dblmax(BAT **H, BAT *t, int *N)
{
  size_t i, n = BATcount(t);
  int bs = BUNsize(t);
  char *p = BUNfirst(t);

  if ((size_t) *N < n)
	  n = (size_t) *N;
  do_pqueue_init(H,t,n);

  for(i=0; i<n; i++, p+=bs) {
	pqueue_enqueue_dblmax(*H, (oid*)BUNhloc(t,p), (dbl*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_dblmax(*H, (oid*)BUNhloc(t,p), (dbl*)BUNtloc(t,p)); 
  }
  return GDK_SUCCEED;
}


#line 332 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"



#line 343 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"


/* The fallback case, non optimized */



#line 524 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"

#line 348 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"
/*enqueue an element*/
int pqueue_enqueue_anymin(BAT *h, oid *idx, ptr el, int tpe)
{
  BUN hbase;
  BUN ins,cur;
  int hBUNsize;

  size_t p, posel;
  char ch;
  int i;

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  posel = BATcount(h); /*last position*/
  BUNins(h, (ptr)idx, (ptr)el, FALSE);
  ins = hbase+posel*hBUNsize;
  
  while(posel >0) {
	p=parent(posel);
	cur = hbase+p*hBUNsize;
	if (atom_CMP(BUNtail(h,ins), BUNtail(h,cur), tpe) < 0 ) {
	  /* swap element with its parent */
	  for(i=0; i<hBUNsize; i++){
		ch= cur[i]; cur[i]=ins[i]; ins[i]=ch;
	  }
	  ins = cur;
	  posel = parent(posel);
	}
	else break;
  }
  h->hsorted = h->tsorted = FALSE;
  
  return GDK_SUCCEED;
}

/* moves down the root element */
/* used by dequeue (see below) */
int pqueue_movedowntop_anymin(BAT *h)
{
  BUN hbase;
  BUN swp,cur;
  int hBUNsize;

  int tpe = BATttype(h);
  size_t swap, num_elems;

  size_t posel;
  char ch;
  int i;

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  cur = hbase;
  num_elems = BATcount(h);
  posel = 0;
  
  /*while posel is not a leaf and pqueue[posel].tail > any of childen*/
  while (posel*2+1 < num_elems) { /*there exists a left son*/
	if (posel*2+2< num_elems) { /*there exists a right son*/
	  if (atom_CMP(
		BUNtail(h,hbase+(posel*2+1)*hBUNsize),
		BUNtail(h,hbase+(posel*2+2)*hBUNsize), tpe) < 0 ) {
		swap = posel*2+1;
	  } else {
		swap = posel*2+2;
	  }
	} else
		swap = posel*2+1;

	swp = hbase+swap*hBUNsize;

	if (atom_CMP( BUNtail(h,swp), BUNtail(h,cur), tpe) < 0 ) {
		/*swap elements*/
		for(i=0;i<hBUNsize; i++){
			ch= cur[i]; cur[i]=swp[i]; swp[i]=ch;
		}
	  cur = swp;
	  posel = swap;
	} else 
		break;
  }
  h->hsorted = h->tsorted = FALSE;

  return GDK_SUCCEED;
}

/* removes the root element, puts the last element as root and moves it down */
int pqueue_dequeue_anymin(BAT *h)
{
  BUN hbase;
  int hBUNsize;

  size_t num_elements;

  if (!(num_elements = BATcount(h))) {
	printf("pqueue_dequeue: Cannot dequeue from empty queue\n");
	return GDK_FAIL;
  }

  hbase = BUNfirst(h);
  hBUNsize = BUNsize(h);

  /* copy last element to the first position*/
  memcpy(hbase, hbase+(num_elements-1)*hBUNsize, hBUNsize);

  /*delete last element*/
  BUNdelete(h, hbase+(num_elements-1)*hBUNsize, FALSE);

  pqueue_movedowntop_anymin(h);
  return GDK_SUCCEED;
}

/* replaces the top element with the input if it is larger (smaller) and
 * updates the heap */
int pqueue_topreplace_anymin(BAT *h, oid *idx, ptr el, int tpe)
{
  BUN hbase;

  hbase = BUNfirst(h);

  if (atom_CMP(BUNtail(h,hbase), el, tpe) < 0) {
	BUNinplace(h, hbase, idx, el, 0);
	*(oid*)hbase = *idx;
	pqueue_movedowntop_anymin(h);
    	h->hsorted = h->tsorted = FALSE;
  }
  
  return GDK_SUCCEED;
}

int pqueue_topn_voidanymin(BAT **H, BAT *t, int *N)
{
  size_t i, n = BATcount(t);
  oid idx = t->hseqbase;
  int bs = BUNsize(t);
  char *p = BUNfirst(t);
  int tpe = BATttype(t);

  if ((size_t) *N < n)
   	n = (size_t) *N;
  do_pqueue_init(H,t,n);

  for(i=0; i<n; i++, idx++, p+=bs) {