Changeset: 7bd377d7b351 for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=7bd377d7b351 Added Files: sql/benchmarks/tpch/drop.sql Modified Files: monetdb5/modules/mal/pqueue.c monetdb5/modules/mal/pqueue.mal monetdb5/optimizer/opt_mergetable.c sql/backends/monet5/rel_bin.c sql/backends/monet5/sql_gencode.c sql/backends/monet5/sql_statement.c sql/backends/monet5/sql_statement.h Branch: default Log Message:
use new pqueue interface
diffs (truncated from 2157 to 300 lines):
diff --git a/monetdb5/modules/mal/pqueue.c b/monetdb5/modules/mal/pqueue.c
--- a/monetdb5/modules/mal/pqueue.c
+++ b/monetdb5/modules/mal/pqueue.c
@@ -17,1398 +17,9 @@
* All Rights Reserved.
*/
-/*
- * Nikos Mamoulis, Niels Nes
- * 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).
- *
- */
-
#include "monetdb_config.h"
#include "pqueue.h"
-/* returns the parent of a pqueue position */
-static inline BUN
-parent(BUN posel)
-{
- if (posel % 2) /*odd */
- return posel / 2;
- else
- return (posel - 1) / 2;
-}
-
-/* initialize pqueue */
-static int
-do_pqueue_init(BAT **h, BAT *b, BUN maxsize)
-{
- *h = BATnew(TYPE_oid, b->ttype, maxsize);
- if (*h == NULL)
- return GDK_FAIL;
- (*h)->batDirty |= 2;
- return GDK_SUCCEED;
-}
-
-static int
-pqueue_init(BAT **h, BAT *b, wrd *maxsize)
-{
- return do_pqueue_init(h, b, (BUN) *maxsize);
-}
-
-#define ht_swap(tpe,cur,ins)
\
- do {
\
- oid htmp = *(oid*)BUNhloc(hi,cur);
\
- tpe ttmp = *(tpe*)BUNtloc(hi,cur);
\
- *(oid*)BUNhloc(hi,cur) = *(oid*)BUNhloc(hi,ins); \
- *(tpe*)BUNtloc(hi,cur) = *(tpe*)BUNtloc(hi,ins); \
- *(oid*)BUNhloc(hi,ins) = htmp;
\
- *(tpe*)BUNtloc(hi,ins) = ttmp;
\
- } while (0)
-
-#define any_swap(cur,ins,ts)
\
- do {
\
- unsigned int i;
\
- char ch;
\
- /* only swap the locations (ie var_t's) */
\
- char *c1 = BUNtloc(hi,cur), *c2 = BUNtloc(hi,ins); \
- oid htmp = *(oid*)BUNhloc(hi,cur);
\
- *(oid*)BUNhloc(hi,cur) = *(oid*)BUNhloc(hi,ins); \
- *(oid*)BUNhloc(hi,ins) = htmp;
\
- for(i=0;i<ts;i++) {
\
- ch= c1[i]; c1[i]=c2[i]; c2[i]=ch;
\
- }
\
- } while (0)
-
-#define pqueueimpl_minmax(TYPE,NAME,OPER)
\
- /*enqueue an element*/
\
- static int pqueue_enqueue_##NAME(BAT *h, oid *idx, TYPE *el)
\
- {
\
- BATiter hi = bat_iterator(h);
\
- BUN ins,cur;
\
-
\
- BUN hbase = BUNfirst(h);
\
- BUN p, posel = BATcount(h); /*last position*/
\
-
\
- BUNins(h, (ptr)idx, (ptr)el, FALSE);
\
- ins = hbase+posel;
\
-
\
- while(posel >0) {
\
- p=parent(posel);
\
- cur = hbase+p;
\
- if (*(TYPE *)BUNtloc(hi,ins) OPER *(TYPE
*)BUNtloc(hi,cur)) { \
- /* swap element with its parent */
\
- ht_swap(TYPE,cur,ins);
\
- ins = cur;
\
- posel = parent(posel);
\
- }
\
- else break;
\
- }
\
- h->hsorted = h->tsorted = FALSE;
\
- h->hrevsorted = h->trevsorted = FALSE;
\
-
\
- return GDK_SUCCEED;
\
- }
\
-
\
- /* moves down the root element */
\
- /* used by dequeue (see below) */
\
- static int pqueue_movedowntop_##NAME(BAT *h)
\
- {
\
- BATiter hi = bat_iterator(h);
\
- BUN swp, cur, hbase = BUNfirst(h);
\
- BUN swap, num_elems = BATcount(h);
\
- BUN posel = 0;
\
-
\
- cur = hbase;
\
-
\
- /*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 (*(TYPE *)BUNtloc(hi,hbase+(posel*2+1)) OPER
\
- *(TYPE *)BUNtloc(hi,hbase+(posel*2+2)))
\
- swap = posel*2+1;
\
- else
\
- swap = posel*2+2;
\
- } else
\
- swap = posel*2+1;
\
-
\
- swp = hbase+swap;
\
-
\
- if (*(TYPE *)BUNtloc(hi,swp) OPER *(TYPE
*)BUNtloc(hi,cur)) { \
- /*swap elements*/
\
- ht_swap(TYPE,cur,swp);
\
- cur = swp;
\
- posel = swap;
\
- } else
\
- break;
\
- }
\
-
\
- return GDK_SUCCEED;
\
- }
\
-
\
- /* removes the root element, puts the last element as root and */
\
- /* moves it down */
\
- static int pqueue_dequeue_##NAME(BAT *h)
\
- {
\
- BATiter hi = bat_iterator(h);
\
- BUN hbase;
\
- BUN num_elements;
\
-
\
- if (!(num_elements = BATcount(h))) {
\
- /* pqueue_dequeue: Cannot dequeue from empty queue */
\
- return GDK_FAIL;
\
- }
\
-
\
- hbase = BUNfirst(h);
\
-
\
- /* copy last element to the first position*/
\
- ht_swap(TYPE,hbase, hbase+(num_elements-1));
\
-
\
- /*delete last element*/
\
- BUNdelete(h, hbase+(num_elements-1), FALSE);
\
-
\
- pqueue_movedowntop_##NAME(h);
\
- return GDK_SUCCEED;
\
- }
\
-
\
- /* replaces the top element with the input if it is larger */
\
- /* (smaller) and \ updates the heap */
\
- static int pqueue_topreplace_##NAME(BAT *h, oid *idx, TYPE *el)
\
- {
\
- BATiter hi = bat_iterator(h);
\
- BUN hbase;
\
-
\
- hbase = BUNfirst(h);
\
-
\
- if (*(TYPE *)BUNtloc(hi,hbase) OPER *el) {
\
- *(oid*)BUNhloc(hi,hbase) = *idx;
\
- *(TYPE*)BUNtloc(hi,hbase) = *el;
\
- pqueue_movedowntop_##NAME(h);
\
- }
\
-
\
- return GDK_SUCCEED;
\
- }
\
-
\
- /* TopN, based on ##NAME-pqueue */
\
-
\
- static BAT *
\
- heap2bat_##NAME(BAT *h)
\
- {
\
- BAT *r, *n = BATnew(TYPE_oid, TYPE_oid, BATcount(h));
\
- BUN f = BUNfirst(h);
\
- oid *o = (oid*)Hloc(h, f), oo = *o;
\
- TYPE *v = (TYPE*)Tloc(h, f), ov = *v;
\
-
\
- for(f = BUNfirst(h); f < BUNlast(h); f = BUNfirst(h)) {
\
- o = (oid*)Hloc(h, f);
\
- v = (TYPE*)Tloc(h, f);
\
- if (ov != *v) {
\
- oo = *o;
\
- ov = *v;
\
- }
\
- BUNins(n, o, &oo, FALSE);
\
- pqueue_dequeue_##NAME(h);
\
- }
\
- r = BATrevert(n);
\
- return r;
\
- }
\
-
\
- static int pqueue_topn_void##NAME(BAT **H, BAT *t, wrd *N)
\
- {
\
- BAT *h = NULL;
\
- BATiter ti = bat_iterator(t);
\
- TYPE *v;
\
- BUN i, n = BATcount(t);
\
- oid idx = t->hseqbase;
\
-
\
- if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N
< n) \
- n = (BUN) *N;
\
- if (do_pqueue_init(&h,t,n) == GDK_FAIL)
\
- return GDK_FAIL;
\
- v = (TYPE*)BUNtail(ti,BUNfirst(t));
\
-
\
- for(i=0; i<n; i++, idx++, v++) {
\
- pqueue_enqueue_##NAME(h, &idx, v);
\
- }
\
- n = BATcount(t);
\
- for(; i<n; i++, idx++, v++) {
\
- pqueue_topreplace_##NAME(h, &idx, v);
\
- }
\
- *H = heap2bat_##NAME(h);
\
- BBPunfix(h->batCacheid);
\
- return GDK_SUCCEED;
\
- }
\
-
\
- static int pqueue_topn_##NAME(BAT **H, BAT *t, wrd *N)
\
- {
\
- BAT *h = NULL;
\
- BATiter ti = bat_iterator(t);
\
- BUN i, n = BATcount(t);
\
- BUN p = BUNfirst(t);
\
-
\
- if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N
< n) \
- n = (BUN) *N;
\
- if (do_pqueue_init(&h,t,n) == GDK_FAIL)
\
- return GDK_FAIL;
\
-
\
- for(i=0; i<n; i++, p++) {
\
- pqueue_enqueue_##NAME(h, (oid*)BUNhloc(ti,p),
(TYPE*)BUNtloc(ti,p)); \
- }
\
- n = BATcount(t);
\
- for(; i<n; i++, p++) {
\
- pqueue_topreplace_##NAME(h, (oid*)BUNhloc(ti,p),
(TYPE*)BUNtloc(ti,p)); \
- }
\
- *H = heap2bat_##NAME(h);
\
- BBPunfix(h->batCacheid);
\
- return GDK_SUCCEED;
\
- }
\
-
\
- /* TopN (unique values), based on ##NAME-pqueue */
\
-
\
- static int pqueue_utopn_void##NAME(BAT **H, BAT *t, wrd *N)
\
- {
\
- BAT *duplicates = NULL, *b;
\
- BATiter ti = bat_iterator(t);
\
- TYPE *v;
\
- BUN i, j, n, cnt = BATcount(t), p;
\
- oid idx = t->hseqbase;
\
-
\
- n = cnt;
\
- if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX)
\
- n = (BUN) *N;
\
- if (do_pqueue_init(H,t,n) == GDK_FAIL)
\
- return GDK_FAIL;
\
- duplicates = BATnew(TYPE_oid, TYPE_oid, n);
\
- if (duplicates == NULL) {
\
- BBPunfix((*H)->batCacheid);
\
- return GDK_FAIL;
\
- }
\
- v = (TYPE*)BUNtail(ti,BUNfirst(t));
\
-
\
- for(i=0, j=0; j < cnt && i<n; j++, idx++, v++) {
\
- if ((p = BUNfnd(BATmirror(*H), v)) == BUN_NONE) {
\
- pqueue_enqueue_##NAME(*H, &idx, v);
\
- HASHdestroy(*H);
\
- BUNins(duplicates, &idx, &idx, FALSE);
\
- i++;
\
- } else {
\
- BUNins(duplicates, Hloc(*H, p), &idx, FALSE);
\
- }
\
- }
\
- for(; j<cnt; j++, idx++, v++) {
\
- if (*(TYPE *)Tloc(*H,BUNfirst(*H)) OPER##= *v) {
\
- if ((p = BUNfnd(BATmirror(*H), v)) == BUN_NONE)
{ \
- oid o_idx = *(oid*)Hloc(*H,
BUNfirst(*H)); \
- BUNdelHead(duplicates, &o_idx, TRUE);
\
- pqueue_topreplace_##NAME(*H, &idx, v);
\
- HASHdestroy(*H);
\
- BUNins(duplicates, &idx, &idx, FALSE);
\
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
