Changeset: 90d68726176c for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=90d68726176c
Modified Files:
gdk/gdk_cand.c
Branch: candidate-exceptions
Log Message:
Use candidate iterators for candidate functions.
diffs (truncated from 641 to 300 lines):
diff --git a/gdk/gdk_cand.c b/gdk/gdk_cand.c
--- a/gdk/gdk_cand.c
+++ b/gdk/gdk_cand.c
@@ -13,10 +13,10 @@
/* create a new, dense candidate list with values from `first' up to,
* but not including, `last' */
-static BAT *
+static inline BAT *
newdensecand(oid first, oid last)
{
- if (last < first)
+ if (last <= first)
first = last = 0; /* empty range */
return BATdense(0, first, last - first);
}
@@ -30,113 +30,113 @@ BAT *
BATmergecand(BAT *a, BAT *b)
{
BAT *bn;
- const oid *restrict ap, *restrict bp, *ape, *bpe;
oid *restrict p, i;
- oid af, al, bf, bl;
- bit ad, bd;
+ struct canditer cia, cib;
BATcheck(a, "BATmergecand", NULL);
BATcheck(b, "BATmergecand", NULL);
- assert(ATOMtype(a->ttype) == TYPE_oid);
- assert(ATOMtype(b->ttype) == TYPE_oid);
- assert(BATcount(a) <= 1 || a->tsorted);
- assert(BATcount(b) <= 1 || b->tsorted);
- assert(BATcount(a) <= 1 || a->tkey);
- assert(BATcount(b) <= 1 || b->tkey);
- assert(a->tnonil);
- assert(b->tnonil);
+
+ canditer_init(&cia, NULL, a);
+ canditer_init(&cib, NULL, b);
/* we can return a if b is empty (and v.v.) */
- if (BATcount(a) == 0) {
- return COLcopy(b, b->ttype, false, TRANSIENT);
+ if (cia.ncand == 0) {
+ return canditer_slice(&cib, 0, cib.ncand);
}
- if (BATcount(b) == 0) {
- return COLcopy(a, a->ttype, false, TRANSIENT);
+ if (cib.ncand == 0) {
+ return canditer_slice(&cia, 0, cia.ncand);
}
/* we can return a if a fully covers b (and v.v) */
- af = BUNtoid(a, 0);
- bf = BUNtoid(b, 0);
- al = BUNtoid(a, BUNlast(a) - 1);
- bl = BUNtoid(b, BUNlast(b) - 1);
- ad = (af + BATcount(a) - 1 == al); /* i.e., dense */
- bd = (bf + BATcount(b) - 1 == bl); /* i.e., dense */
- if (ad && bd) {
+ if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
/* both are dense */
- if (af <= bf && bf <= al + 1) {
+ if (cia.seq <= cib.seq && cib.seq <= cia.seq + cia.ncand) {
/* partial overlap starting with a, or b is
* smack bang after a */
- return newdensecand(af, al < bl ? bl + 1 : al + 1);
+ return newdensecand(cia.seq, cia.seq + cia.ncand <
cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
}
- if (bf <= af && af <= bl + 1) {
+ if (cib.seq <= cia.seq && cia.seq <= cib.seq + cib.ncand) {
/* partial overlap starting with b, or a is
* smack bang after b */
- return newdensecand(bf, al < bl ? bl + 1 : al + 1);
+ return newdensecand(cib.seq, cia.seq + cia.ncand <
cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
}
}
- if (ad && af <= bf && al >= bl) {
- return newdensecand(af, al + 1);
+ if (cia.tpe == cand_dense
+ && cia.seq <= cib.seq
+ && canditer_last(&cia) >= canditer_last(&cib)) {
+ return canditer_slice(&cia, 0, cia.ncand);
}
- if (bd && bf <= af && bl >= al) {
- return newdensecand(bf, bl + 1);
+ if (cib.tpe == cand_dense
+ && cib.seq <= cia.seq
+ && canditer_last(&cib) >= canditer_last(&cia)) {
+ return canditer_slice(&cib, 0, cib.ncand);
}
- bn = COLnew(0, TYPE_oid, BATcount(a) + BATcount(b), TRANSIENT);
+ bn = COLnew(0, TYPE_oid, cia.ncand + cib.ncand, TRANSIENT);
if (bn == NULL)
return NULL;
p = (oid *) Tloc(bn, 0);
- if (BATtdense(a) && BATtdense(b)) {
+ if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
/* both lists are dense */
- if (a->tseqbase > b->tseqbase) {
- BAT *t = a;
-
- a = b;
- b = t;
+ if (cia.seq > cib.seq) {
+ struct canditer ci;
+ ci = cia;
+ cia = cib;
+ cib = ci;
}
- /* a->tseqbase <= b->tseqbase */
- for (i = a->tseqbase; i < a->tseqbase + BATcount(a); i++)
+ /* cia completely before cib */
+ assert(cia.seq + cia.ncand < cib.seq);
+ for (i = cia.seq; i < cia.seq + cia.ncand; i++)
*p++ = i;
- for (i = MAX(b->tseqbase, i);
- i < b->tseqbase + BATcount(b);
- i++)
+ /* there is a gap */
+ for (i = cib.seq; i < cib.seq + cib.ncand; i++)
*p++ = i;
- } else if (BATtdense(a) || BATtdense(b)) {
- if (BATtdense(b)) {
- BAT *t = a;
-
- a = b;
- b = t;
+ } else if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
+ if (cib.tpe == cand_dense) {
+ struct canditer ci;
+ ci = cia;
+ cia = cib;
+ cib = ci;
}
- /* only a is dense */
- bp = (const oid *) Tloc(b, 0);
- bpe = bp + BATcount(b);
- while (bp < bpe && *bp < a->tseqbase)
- *p++ = *bp++;
- for (i = a->tseqbase; i < a->tseqbase + BATcount(a); i++)
+ /* only cia is dense */
+
+ /* copy part of cib that's before the start of cia */
+ while (canditer_peek(&cib) < cia.seq) {
+ *p++ = canditer_next(&cib);
+ }
+ /* copy all of cia */
+ for (i = cia.seq; i < cia.seq + cia.ncand; i++)
*p++ = i;
- while (bp < bpe && *bp < i)
- bp++;
- while (bp < bpe)
- *p++ = *bp++;
+ /* skip over part of cib that overlaps with cia */
+ canditer_setidx(&cib, canditer_search(&cib, cia.seq +
cia.ncand, true));
+ /* copy rest of cib */
+ while (cib.next < cib.ncand) {
+ *p++ = canditer_next(&cib);
+ }
} else {
/* a and b are both not dense */
- ap = (const oid *) Tloc(a, 0);
- ape = ap + BATcount(a);
- bp = (const oid *) Tloc(b, 0);
- bpe = bp + BATcount(b);
- while (ap < ape && bp < bpe) {
- if (*ap < *bp)
- *p++ = *ap++;
- else if (*ap > *bp)
- *p++ = *bp++;
- else {
- *p++ = *ap++;
- bp++;
+ oid ao = canditer_next(&cia);
+ oid bo = canditer_next(&cib);
+ while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
+ if (ao < bo) {
+ *p++ = ao;
+ ao = canditer_next(&cia);
+ } else if (bo < ao) {
+ *p++ = bo;
+ bo = canditer_next(&cib);
+ } else {
+ *p++ = ao;
+ ao = canditer_next(&cia);
+ bo = canditer_next(&cib);
}
}
- while (ap < ape)
- *p++ = *ap++;
- while (bp < bpe)
- *p++ = *bp++;
+ while (!is_oid_nil(ao)) {
+ *p++ = ao;
+ ao = canditer_next(&cia);
+ }
+ while (!is_oid_nil(bo)) {
+ *p++ = bo;
+ bo = canditer_next(&cib);
+ }
}
/* properties */
@@ -158,67 +158,55 @@ BAT *
BATintersectcand(BAT *a, BAT *b)
{
BAT *bn;
- const oid *restrict ap, *restrict bp, *ape, *bpe;
oid *restrict p;
- oid af, al, bf, bl;
+ struct canditer cia, cib;
BATcheck(a, "BATintersectcand", NULL);
BATcheck(b, "BATintersectcand", NULL);
- assert(ATOMtype(a->ttype) == TYPE_oid);
- assert(ATOMtype(b->ttype) == TYPE_oid);
- assert(a->tsorted);
- assert(b->tsorted);
- assert(a->tkey);
- assert(b->tkey);
- assert(a->tnonil);
- assert(b->tnonil);
- if (BATcount(a) == 0 || BATcount(b) == 0) {
- return newdensecand(0, 0);
+ canditer_init(&cia, NULL, a);
+ canditer_init(&cib, NULL, b);
+
+ if (cia.ncand == 0 || cib.ncand == 0) {
+ return BATdense(0, 0, 0);
}
- af = BUNtoid(a, 0);
- bf = BUNtoid(b, 0);
- al = BUNtoid(a, BUNlast(a) - 1);
- bl = BUNtoid(b, BUNlast(b) - 1);
-
- if ((af + BATcount(a) - 1 == al) && (bf + BATcount(b) - 1 == bl)) {
+ if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
/* both lists are dense */
- return newdensecand(MAX(af, bf), MIN(al, bl) + 1);
+ return newdensecand(MAX(cia.seq, cib.seq), MIN(cia.seq +
cia.ncand, cib.seq + cib.ncand));
}
- bn = COLnew(0, TYPE_oid, MIN(BATcount(a), BATcount(b)), TRANSIENT);
+ bn = COLnew(0, TYPE_oid, MIN(cia.ncand, cib.ncand), TRANSIENT);
if (bn == NULL)
return NULL;
p = (oid *) Tloc(bn, 0);
- if (BATtdense(a) || BATtdense(b)) {
- if (BATtdense(b)) {
- BAT *t = a;
-
- a = b;
- b = t;
+ if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
+ if (cib.tpe == cand_dense) {
+ struct canditer ci;
+ ci = cia;
+ cia = cib;
+ cib = ci;
}
- /* only a is dense */
- bp = (const oid *) Tloc(b, 0);
- bpe = bp + BATcount(b);
- while (bp < bpe && *bp < a->tseqbase)
- bp++;
- while (bp < bpe && *bp < a->tseqbase + BATcount(a))
- *p++ = *bp++;
+ /* only cia is dense */
+
+ /* search for first value in cib that is contained in cia */
+ canditer_setidx(&cib, canditer_search(&cib, cia.seq, true));
+ oid bo;
+ while (!is_oid_nil(bo = canditer_next(&cib)) && bo < cia.seq +
cia.ncand)
+ *p++ = bo;
} else {
/* a and b are both not dense */
- ap = (const oid *) Tloc(a, 0);
- ape = ap + BATcount(a);
- bp = (const oid *) Tloc(b, 0);
- bpe = bp + BATcount(b);
- while (ap < ape && bp < bpe) {
- if (*ap < *bp)
- ap++;
- else if (*ap > *bp)
- bp++;
+ oid ao = canditer_next(&cia);
+ oid bo = canditer_next(&cib);
+ while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
+ if (ao < bo)
+ ao = canditer_next(&cia);
+ else if (bo < ao)
+ bo = canditer_next(&cib);
else {
- *p++ = *ap++;
- bp++;
+ *p++ = ao;
+ ao = canditer_next(&cia);
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
