pqueue.c

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

#line 125 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB5/src/modules/kernel/pqueue.mx"
#include "mal_config.h"
#include "pqueue.h"
#include "mal_exception.h"
#include "mal_interpreter.h"

/*returns the parent of a pqueue position*/
static INLINE size_t parent(size_t posel)
{
  if (posel%2) /*odd*/
	return posel/2;
  else
	return (posel-1)/2;
}

/*initialize pqueue*/
static void
do_pqueue_init(BAT **h, BAT *b, size_t maxsize)
{
	*h = BATnew(TYPE_oid, b->ttype, maxsize);
        if (*h)
                (*h)->batDirty |= 2;
}

int 
pqueue_init(BAT **h, BAT *b, int *maxsize)
{
	do_pqueue_init(h, b, (size_t) *maxsize);
  	return GDK_SUCCEED;
}



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


#line 334 "/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_chrmin(BAT *h,
		 oid *idx, 
		 chr *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 (*(chr *)BUNtloc(h,ins) < *(chr *)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_chrmin(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 (*(chr *)BUNtloc(h,hbase+(posel*2+1)*hBUNsize) <
	      *(chr *)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 (*(chr *)BUNtloc(h,swp) < *(chr *)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_chrmin(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_chrmin(h);
  return GDK_SUCCEED;
}

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

  hbase = BUNfirst(h);

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

/* TopN, based on min-pqueue */

int pqueue_topn_voidchrmin(BAT **H, BAT *t, int *N)
{
  chr *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 = (chr*)BUNtail(t,BUNfirst(t));

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

int pqueue_topn_chrmin(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_chrmin(*H, (oid*)BUNhloc(t,p), (chr*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_chrmin(*H, (oid*)BUNhloc(t,p), (chr*)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_chrmax(BAT *h,
		 oid *idx, 
		 chr *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 (*(chr *)BUNtloc(h,ins) > *(chr *)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_chrmax(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 (*(chr *)BUNtloc(h,hbase+(posel*2+1)*hBUNsize) >
	      *(chr *)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 (*(chr *)BUNtloc(h,swp) > *(chr *)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_chrmax(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_chrmax(h);
  return GDK_SUCCEED;
}

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

  hbase = BUNfirst(h);

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

/* TopN, based on max-pqueue */

int pqueue_topn_voidchrmax(BAT **H, BAT *t, int *N)
{
  chr *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 = (chr*)BUNtail(t,BUNfirst(t));

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

int pqueue_topn_chrmax(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_chrmax(*H, (oid*)BUNhloc(t,p), (chr*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_chrmax(*H, (oid*)BUNhloc(t,p), (chr*)BUNtloc(t,p)); 
  }
  return GDK_SUCCEED;
}


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



#line 334 "/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_shtmin(BAT *h,
		 oid *idx, 
		 sht *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 (*(sht *)BUNtloc(h,ins) < *(sht *)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_shtmin(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 (*(sht *)BUNtloc(h,hbase+(posel*2+1)*hBUNsize) <
	      *(sht *)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 (*(sht *)BUNtloc(h,swp) < *(sht *)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_shtmin(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_shtmin(h);
  return GDK_SUCCEED;
}

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

  hbase = BUNfirst(h);

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

/* TopN, based on min-pqueue */

int pqueue_topn_voidshtmin(BAT **H, BAT *t, int *N)
{
  sht *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 = (sht*)BUNtail(t,BUNfirst(t));

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

int pqueue_topn_shtmin(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_shtmin(*H, (oid*)BUNhloc(t,p), (sht*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_shtmin(*H, (oid*)BUNhloc(t,p), (sht*)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_shtmax(BAT *h,
		 oid *idx, 
		 sht *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 (*(sht *)BUNtloc(h,ins) > *(sht *)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;