Changeset: f795aa2b42f0 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=f795aa2b42f0
Modified Files:
MonetDB5/src/optimizer/opt_prelude.mx
MonetDB5/src/optimizer/opt_support.mx
Branch: default
Log Message:
Merge with Oct2010 branch.
diffs (truncated from 1493 to 300 lines):
diff -r bf48a04f5682 -r f795aa2b42f0 MonetDB5/src/modules/mal/pqueue.mx
--- a/MonetDB5/src/modules/mal/pqueue.mx Mon Sep 06 16:33:46 2010 +0200
+++ b/MonetDB5/src/modules/mal/pqueue.mx Tue Sep 07 10:47:04 2010 +0200
@@ -54,19 +54,19 @@
address pqdeque...@1@2
comment "Removes top element of the @2-pqueue and updates it";
-command to...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:@1]
+command to...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:oid]
address pqto...@1@2
comment "Return the topn elements of the bat t using a @2-pqueue";
-command to...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:@1]
+command to...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:oid]
address pqto...@1@2
comment "Return the topn elements of the bat t using a @2-pqueue";
-command uto...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:@1]
+command uto...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:oid]
address pquto...@1@2
comment "Return the unique topn elements of the bat t using a @2-pqueue";
-command uto...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:@1]
+command uto...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:oid]
address pquto...@1@2
comment "Return the unique topn elements of the bat t using a @2-pqueue";
@@ -83,22 +83,38 @@
address pqdequeue_...@1
comment "Removes top element of the @1-pqueue and updates it";
-command to...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:any_1]
+command to...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
address pqtopn_...@1
comment "Return the topn elements of the bat t using a @1-pqueue";
-command to...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:any_1]
+command to...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
address pqtopn_...@1
comment "Return the topn elements of the bat t using a @1-pqueue";
-command uto...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:any_1]
+command uto...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
address pqutopn_...@1
comment "Return the unique topn elements of the bat t using a @1-pqueue";
-command uto...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:any_1]
+command uto...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
address pqutopn_...@1
comment "Return the unique topn elements of the bat t using a @1-pqueue";
+command to...@1(a:bat[:oid,:oid], t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
+address pqtopn2_...@1
+comment "Return the topn elements of the bat t using a @1-pqueue";
+
+command to...@1(a:bat[:oid,:oid], t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
+address pqtopn2_...@1
+comment "Return the topn elements of the bat t using a @1-pqueue";
+
+command uto...@1(a:bat[:oid,:oid], t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
+address pqutopn2_...@1
+comment "Return the unique topn elements of the bat t using a @1-pqueue";
+
+command uto...@1(a:bat[:oid,:oid], t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
+address pqutopn2_...@1
+comment "Return the unique topn elements of the bat t using a @1-pqueue";
+
@= mel_pqueue_any
@:mel_minmax_any(min)@
@:mel_minmax_any(max)@
@@ -308,8 +324,31 @@
/* TopN, based on @2-pqueue */
+static BAT *
+heap2b...@1@2( BAT *h )
+{
+ BAT *r, *n = BATnew(TYPE_oid, TYPE_oid, BATcount(h));
+ BUN f = BUNfirst(h);
+ oid *o = (oid*)Hloc(h, f), oo = *o;
+ @1 *v = (@1*)Tloc(h, f), ov = *v;
+
+ for(f = BUNfirst(h); f < BUNlast(h); f = BUNfirst(h)) {
+ o = (oid*)Hloc(h, f);
+ v = (@1*)Tloc(h, f);
+ if (ov != *v) {
+ oo = *o;
+ ov = *v;
+ }
+ BUNins(n, o, &oo, FALSE);
+ pqueue_deque...@1@2(h);
+ }
+ r = BATrevert(n);
+ return r;
+}
+
int pqueue_topn_v...@1@2(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
@1 *v;
BUN i, n = BATcount(t);
@@ -317,38 +356,43 @@
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)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
v = (@1*)BUNtail(ti,BUNfirst(t));
for(i=0; i<n; i++, idx++, v++) {
- pqueue_enque...@1@2(*H, &idx, v);
+ pqueue_enque...@1@2(h, &idx, v);
}
n = BATcount(t);
for(; i<n; i++, idx++, v++) {
- pqueue_toprepla...@1@2(*H, &idx, v);
+ pqueue_toprepla...@1@2(h, &idx, v);
}
+ *H = heap2b...@1@2(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
int pqueue_to...@1@2(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)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
for(i=0; i<n; i++, p++) {
- pqueue_enque...@1@2(*H, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
+ pqueue_enque...@1@2(h, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
}
n = BATcount(t);
for(; i<n; i++, p++) {
- pqueue_toprepla...@1@2(*H, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
+ pqueue_toprepla...@1@2(h, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
}
+ *H = heap2b...@1@2(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
@@ -397,10 +441,14 @@
}
}
}
- b = BATjoin(BATmirror(duplicates), *H, BATcount(duplicates));
+ b = heap2b...@1@2(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = VIEWcombine(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = BATleftjoin(*H, duplicates, BATcount(duplicates));
BBPunfix((*H)->batCacheid);
BBPunfix(duplicates->batCacheid);
- *H = b;
+ *H = BATmirror(b);
return GDK_SUCCEED;
}
@@ -448,10 +496,14 @@
}
}
}
- b = BATjoin(BATmirror(duplicates), *H, BATcount(duplicates));
- BBPunfix((*H)->batCacheid);
+ b = heap2b...@1@2(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = VIEWcombine(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = BATleftjoin(*H, duplicates, BATcount(duplicates));
+ BBPunfix((*H)->batCacheid);
BBPunfix(duplicates->batCacheid);
- *H = b;
+ *H = BATmirror(b);
return GDK_SUCCEED;
}
@c
@@ -480,12 +532,13 @@
BUN hbase;
BUN ins,cur;
BUN p, posel;
- unsigned short ts = Tsize(h);
+ unsigned short ts;
hbase = BUNfirst(h);
posel = BATcount(h); /*last position*/
BUNins(h, (ptr)idx, (ptr)el, FALSE);
+ ts = Tsize(h);
ins = hbase+posel;
while(posel >0) {
@@ -592,8 +645,33 @@
return GDK_SUCCEED;
}
+static BAT *
+heap2bat_...@1( BAT *h )
+{
+ BATiter hi = bat_iterator(h);
+ BAT *r, *n = BATnew(TYPE_oid, TYPE_oid, BATcount(h));
+ BUN f = BUNfirst(h);
+ oid *o = (oid*)Hloc(h, f), oo = *o;
+ ptr v = (ptr)BUNtail(hi, f), ov = v;
+ int tpe = h->ttype;
+
+ for(f = BUNfirst(h); f < BUNlast(h); f = BUNfirst(h)) {
+ o = (oid*)Hloc(h, f);
+ v = (ptr)BUNtail(hi, f);
+ if (atom_CMP(ov,v, tpe) != 0) {
+ oo = *o;
+ ov = v;
+ }
+ BUNins(n, o, &oo, FALSE);
+ pqueue_dequeue_...@1(h);
+ }
+ r = BATrevert(n);
+ return r;
+}
+
int pqueue_topn_void...@1(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
BUN i, n = BATcount(t);
oid idx = t->hseqbase;
@@ -602,21 +680,24 @@
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)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
for(i=0; i<n; i++, idx++, p++) {
- pqueue_enqueue_...@1(*H, &idx, BUNtail(ti,p), tpe);
+ pqueue_enqueue_...@1(h, &idx, BUNtail(ti,p), tpe);
}
n = BATcount(t);
for(; i<n; i++, idx++, p++) {
- pqueue_topreplace_...@1(*H, &idx, BUNtail(ti,p), tpe);
+ pqueue_topreplace_...@1(h, &idx, BUNtail(ti,p), tpe);
}
+ *H = heap2bat_...@1(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
int pqueue_topn_...@1(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
BUN i, n = BATcount(t);
BUN p = BUNfirst(t);
@@ -624,16 +705,18 @@
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)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
for(i=0; i<n; i++, p++) {
- pqueue_enqueue_...@1(*H, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
+ pqueue_enqueue_...@1(h, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
}
n = BATcount(t);
for(; i<n; i++, p++) {
- pqueue_topreplace_...@1(*H, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
+ pqueue_topreplace_...@1(h, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
}
+ *H = heap2bat_...@1(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
@@ -684,10 +767,14 @@
}
}
}
- b = BATjoin(BATmirror(duplicates), *H, BATcount(duplicates));
- BBPunfix((*H)->batCacheid);
+ b = heap2bat_...@1(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = VIEWcombine(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = BATleftjoin(*H, duplicates, BATcount(duplicates));
+ BBPunfix((*H)->batCacheid);
BBPunfix(duplicates->batCacheid);
- *H = b;
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
