pqueue.mx

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

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f pqueue
@a Nikos Mamoulis, Niels Nes
@v 2.0
@+ Priority queues

This module includes functions for accessing and updating a pqueue.
A pqueue is an (oid,any) bat. The tail is used as a comparison key.
The first element of the pqueue is the smallest one in a min-pqueue
or the largest one in a max-pqueue. 
Each element is larger than (smaller than) or equal to 
its parent which is defined by (position/2) if position is odd or 
(position-1)/2 if position is even (positions are from 0 to n-1).
The head of the bat is used to keep track of the object-ids which are
organized in the heap with respect to their values (tail column).
@{

@+ Module Definition 
@mal
module pqueue;

command init(a:bat[:void,:any_1],maxsize:int):bat[:oid,:any_1] 
address PQinit
comment "Creates an empty pqueue of bat a's tailtype with maximum size maxsize";

@= mel_minmax
command enqueue_@2(h:bat[:oid,:@1], id:oid, value:@1) 
address PQenqueue_@1@2
comment "Inserts element (oid,@1) in the @2-pqueue";

command topreplace_@2(h:bat[:oid,:@1], id:oid, value:@1) 
address PQtopreplace_@1@2
comment "Replaces top element with input and updates @2-pqueue";

command dequeue_@2(h:bat[:oid,:@1]) 
address PQdequeue_@1@2
comment "Removes top element of the @2-pqueue and updates it";

command topn_@2(t:bat[:oid,:@1], n:int) :bat[:oid,:@1] 
address PQtopn_@1@2
comment "Return the topn elements of the bat t using a @2-pqueue";

command topn_@2(t:bat[:void,:@1],n:int) :bat[:oid,:@1] 
address PQtopn_void@1@2
comment "Return the topn elements of the bat t using a @2-pqueue";

@= mel_minmax_any
pattern topreplace_@1(h:bat[:oid,:any_1], id:oid, value:any_1) 
address PQtopreplace_any@1
comment "Replaces top element with input and updates @1-pqueue";

pattern enqueue_@1(h:bat[:oid,:any_1], id:oid, value:any_1) 
address PQenqueue_any@1
comment "Inserts element (oid,any) in the @1-pqueue";

command dequeue_@1(h:bat[:oid,:any_1]) 
address PQdequeue_any@1
comment "Removes top element of the @1-pqueue and updates it";

command topn_@1(t:bat[:oid,:any_1], n:int) :bat[:oid,:any_1] 
address PQtopn_any@1
comment "Return the topn elements of the bat t using a @1-pqueue";

command topn_@1(t:bat[:void,:any_1], n:int) :bat[:oid,:any_1] 
address PQtopn_voidany@1
comment "Return the topn elements of the bat t using a @1-pqueue";

@= mel_pqueue_any
  @:mel_minmax_any(min)@
  @:mel_minmax_any(max)@
@mal
@:mel_pqueue_any()@

@= mel_pqueue
  @:mel_minmax(@1,min)@
  @:mel_minmax(@1,max)@
@mal
@:mel_pqueue(chr)@

@:mel_pqueue(sht)@
@:mel_pqueue(int)@
@:mel_pqueue(oid)@

@:mel_pqueue(ptr)@
@:mel_pqueue(lng)@
@:mel_pqueue(flt)@
@:mel_pqueue(dbl)@

@+ Implementation
@h
#ifndef _PQUEUE_
#define _PQUEUE_

#include "mal.h"

#ifdef WIN32
#ifndef LIBPQUEUE
#define pqueue_export extern __declspec(dllimport)
#else
#define pqueue_export extern __declspec(dllexport)
#endif
#else
#define pqueue_export extern
#endif

pqueue_export str PQinit(int *ret, int *bid, int *maxsize);

#endif /* _PQUEUE */
@c
#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;
}

@= pqueueimpl_minmax
/*enqueue an element*/
int pqueue_enqueue_@1@2(BAT *h,
		 oid *idx, 
		 @3 *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 (*(@3 *)BUNtloc(h,ins) @4 *(@3 *)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_@1@2(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 (*(@3 *)BUNtloc(h,hbase+(posel*2+1)*hBUNsize) @4
	      *(@3 *)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 (*(@3 *)BUNtloc(h,swp) @4 *(@3 *)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_@1@2(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_@1@2(h);
  return GDK_SUCCEED;
}

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

  hbase = BUNfirst(h);

  if (*(@3 *)BUNtloc(h,hbase) @4 *el) {
	memcpy(BUNhloc(h,hbase), idx, sizeof(oid));
	memcpy(BUNtloc(h,hbase), el, sizeof(@3));
	pqueue_movedowntop_@1@2(h);
  }
  
  return GDK_SUCCEED;
}

/* TopN, based on @2-pqueue */

int pqueue_topn_void@1@2(BAT **H, BAT *t, int *N)
{
  @1 *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 = (@1*)BUNtail(t,BUNfirst(t));

  for(i=0; i<n; i++, idx++, v++) {
	pqueue_enqueue_@1@2(*H, &idx, v); 
  }
  n = BATcount(t);
  for(; i<n; i++, idx++, v++) {
	pqueue_topreplace_@1@2(*H, &idx, v); 
  }
  return GDK_SUCCEED;
}

int pqueue_topn_@1@2(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_@1@2(*H, (oid*)BUNhloc(t,p), (@1*)BUNtloc(t,p)); 
  }
  n = BATcount(t);
  for(; i<n; i++, p+=bs) {
	pqueue_topreplace_@1@2(*H, (oid*)BUNhloc(t,p), (@1*)BUNtloc(t,p)); 
  }
  return GDK_SUCCEED;
}
@c
@= pqueueimpl
  @:pqueueimpl_minmax(@1,min,@1,<)@
  @:pqueueimpl_minmax(@1,max,@1,>)@
@c
@:pqueueimpl(chr)@

@:pqueueimpl(sht)@
@:pqueueimpl(int)@
@:pqueueimpl(oid)@

@:pqueueimpl(ptr)@
@:pqueueimpl(lng)@
@:pqueueimpl(flt)@
@:pqueueimpl(dbl)@

/* The fallback case, non optimized */

@= pqueueimpl_any
/*enqueue an element*/
int pqueue_enqueue_any@1(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) @2 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_any@1(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);