Changeset: f51ee5727b6f for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=f51ee5727b6f
Modified Files:
gdk/gdk_batop.c
Branch: Oct2014
Log Message:
Try harder to return a void-void bat for candidate lists.
diffs (165 lines):
diff --git a/gdk/gdk_batop.c b/gdk/gdk_batop.c
--- a/gdk/gdk_batop.c
+++ b/gdk/gdk_batop.c
@@ -1884,6 +1884,21 @@ BATcount_no_nil(BAT *b)
return cnt;
}
+static BAT *
+newdensecand(oid first, oid last)
+{
+ BAT *bn;
+
+ if ((bn = BATnew(TYPE_void, TYPE_void, 0, TRANSIENT)) == NULL)
+ return NULL;
+ if (last < first)
+ first = last = 0; /* empty range */
+ BATsetcount(bn, last - first + 1);
+ BATseqbase(bn, 0);
+ BATseqbase(BATmirror(bn), first);
+ return bn;
+}
+
/* merge two candidate lists and produce a new one
*
* candidate lists are VOID-headed BATs with an OID tail which is
@@ -1913,10 +1928,10 @@ BATmergecand(BAT *a, BAT *b)
assert(b->T->nonil);
/* we can return a if b is empty (and v.v.) */
- if ( BATcount(a) == 0){
+ if (BATcount(a) == 0) {
return BATcopy(b, b->htype, b->ttype, 0, TRANSIENT);
}
- if ( BATcount(b) == 0){
+ if (BATcount(b) == 0) {
return BATcopy(a, a->htype, a->ttype, 0, TRANSIENT);
}
/* we can return a if a fully covers b (and v.v) */
@@ -1928,11 +1943,24 @@ BATmergecand(BAT *a, BAT *b)
bl = *(oid*) BUNtail(bi, BUNlast(b) - 1);
ad = (af + BATcount(a) - 1 == al); /* i.e., dense */
bd = (bf + BATcount(b) - 1 == bl); /* i.e., dense */
+ if (ad && bd) {
+ /* both are dense */
+ if (af <= bf && bf <= al + 1) {
+ /* partial overlap starting with a, or b is
+ * smack bang after a */
+ return newdensecand(af, al < bl ? bl : al);
+ }
+ if (bf <= af && af <= bl + 1) {
+ /* partial overlap starting with b, or a is
+ * smack bang after b */
+ return newdensecand(bf, al < bl ? bl : al);
+ }
+ }
if (ad && af <= bf && al >= bl) {
- return BATcopy(a, a->htype, a->ttype, 0, TRANSIENT);
+ return newdensecand(af, al);
}
if (bd && bf <= af && bl >= al) {
- return BATcopy(b, b->htype, b->ttype, 0, TRANSIENT);
+ return newdensecand(bf, bl);
}
bn = BATnew(TYPE_void, TYPE_oid, BATcount(a) + BATcount(b), TRANSIENT);
@@ -1997,11 +2025,22 @@ BATmergecand(BAT *a, BAT *b)
/* properties */
BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, BUNfirst(bn))));
BATseqbase(bn, 0);
- bn->trevsorted = 0;
+ bn->trevsorted = BATcount(bn) <= 1;
bn->tsorted = 1;
bn->tkey = 1;
bn->T->nil = 0;
bn->T->nonil = 1;
+ af = * (const oid *) Tloc(bn, BUNfirst(bn));
+ if (af + BATcount(bn) - 1 == *(const oid *) Tloc(bn, BUNlast(bn) - 1)) {
+ /* new bat is in fact dense, replace by void column */
+ bn->tseqbase = af;
+ bn->tdense = 1;
+ HEAPfree(&bn->T->heap);
+ bn->ttype = TYPE_void;
+ bn->tvarsized = 1;
+ bn->T->width = 0;
+ bn->T->shift = 0;
+ }
return bn;
}
@@ -2015,7 +2054,9 @@ BATintersectcand(BAT *a, BAT *b)
{
BAT *bn;
const oid *ap, *bp, *ape, *bpe;
- oid *p, i;
+ oid *p;
+ oid af, al, bf, bl;
+ BATiter ai, bi;
BATcheck(a, "BATintersectcand");
BATcheck(b, "BATintersectcand");
@@ -2031,30 +2072,19 @@ BATintersectcand(BAT *a, BAT *b)
assert(b->T->nonil);
if (BATcount(a) == 0 || BATcount(b) == 0) {
- bn = BATnew(TYPE_void, TYPE_void, 0, TRANSIENT);
- if (bn) {
- BATseqbase(bn, 0);
- BATseqbase(BATmirror(bn), 0);
- }
- return bn;
+ return newdensecand(0, 0);
}
- if (a->ttype == TYPE_void && b->ttype == TYPE_void) {
+ ai = bat_iterator(a);
+ bi = bat_iterator(b);
+ af = *(oid*) BUNtail(ai, BUNfirst(a));
+ bf = *(oid*) BUNtail(bi, BUNfirst(b));
+ al = *(oid*) BUNtail(ai, BUNlast(a) - 1);
+ bl = *(oid*) BUNtail(bi, BUNlast(b) - 1);
+
+ if ((af + BATcount(a) - 1 == al) && (bf + BATcount(b) - 1 == bl)) {
/* both lists are VOID */
- bn = BATnew(TYPE_void, TYPE_void, 0, TRANSIENT);
- if (bn == NULL)
- return NULL;
- i = MAX(a->tseqbase, b->tseqbase);
- if (a->tseqbase + BATcount(a) <= b->tseqbase ||
- b->tseqbase + BATcount(b) <= a->tseqbase) {
- /* no overlap */
- BATsetcount(bn, 0);
- } else {
- BATsetcount(bn, MIN(a->tseqbase + BATcount(a) - i,
- b->tseqbase + BATcount(b) - i));
- }
- BATseqbase(BATmirror(bn), i);
- return bn;
+ return newdensecand(MAX(af, bf), MIN(al, bl));
}
bn = BATnew(TYPE_void, TYPE_oid, MIN(BATcount(a), BATcount(b)),
TRANSIENT);
@@ -2096,10 +2126,22 @@ BATintersectcand(BAT *a, BAT *b)
/* properties */
BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, BUNfirst(bn))));
BATseqbase(bn, 0);
- bn->trevsorted = 0;
+ bn->trevsorted = BATcount(bn) <= 1;
bn->tsorted = 1;
bn->tkey = 1;
bn->T->nil = 0;
bn->T->nonil = 1;
+ if (BATcount(bn) == 0 ||
+ (af = * (const oid *) Tloc(bn, BUNfirst(bn))) + BATcount(bn) - 1 ==
+ * (const oid *) Tloc(bn, BUNlast(bn) - 1)) {
+ /* new bat is in fact dense, replace by void column */
+ bn->tseqbase = BATcount(bn) == 0 ? 0 : af;
+ bn->tdense = 1;
+ HEAPfree(&bn->T->heap);
+ bn->ttype = TYPE_void;
+ bn->tvarsized = 1;
+ bn->T->width = 0;
+ bn->T->shift = 0;
+ }
return bn;
}
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
