Changeset: 285690617d9c for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=285690617d9c
Modified Files:
clients/Tests/exports.stable.out
gdk/gdk.h
gdk/gdk_bat.c
gdk/gdk_cand.c
gdk/gdk_cand.h
gdk/gdk_firstn.c
gdk/gdk_group.c
gdk/gdk_join.c
gdk/gdk_select.c
sql/backends/monet5/generator/generator.c
Branch: msk-type
Log Message:
Implemented BATs of type msk as candidate list.
Totally untested.
diffs (truncated from 1171 to 300 lines):
diff --git a/clients/Tests/exports.stable.out b/clients/Tests/exports.stable.out
--- a/clients/Tests/exports.stable.out
+++ b/clients/Tests/exports.stable.out
@@ -435,6 +435,8 @@ BUN canditer_search(struct canditer *ci,
void canditer_setidx(struct canditer *ci, BUN p);
BAT *canditer_slice(struct canditer *ci, BUN lo, BUN hi);
BAT *canditer_slice2(struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2);
+BAT *canditer_slice2val(struct canditer *ci, oid lo1, oid hi1, oid lo2, oid
hi2);
+BAT *canditer_sliceval(struct canditer *ci, oid lo, oid hi);
int closedir(DIR *dir);
char *ctime_r(const time_t *restrict, char *restrict);
date date_add_day(date dt, int days) __attribute__((__const__));
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -782,14 +782,12 @@ typedef struct BATiter {
static inline void
mskSet(BAT *b, BUN p)
{
- assert(ATOMstorage(b->ttype) == TYPE_msk);
((uint32_t *) b->theap.base)[p / 32] |= 1U << (p % 32);
}
static inline void
mskClr(BAT *b, BUN p)
{
- assert(ATOMstorage(b->ttype) == TYPE_msk);
((uint32_t *) b->theap.base)[p / 32] &= ~(1U << (p % 32));
}
@@ -805,7 +803,6 @@ mskSetVal(BAT *b, BUN p, msk v)
static inline msk
mskGetVal(BAT *b, BUN p)
{
- assert(ATOMstorage(b->ttype) == TYPE_msk);
return ((uint32_t *) b->theap.base)[p / 32] & (1U << (p % 32));
}
@@ -1571,8 +1568,10 @@ static inline gdk_return __attribute__((
tfastins_nocheck(BAT *b, BUN p, const void *v, int s)
{
if (ATOMstorage(b->ttype) == TYPE_msk) {
- if (p % 32 == 0)
+ if (p % 32 == 0) {
+ ((uint32_t *) b->theap.base)[b->theap.free / 4] = 0;
b->theap.free += 4;
+ }
} else
b->theap.free += s;
return Tputvalue(b, p, v, false);
diff --git a/gdk/gdk_bat.c b/gdk/gdk_bat.c
--- a/gdk/gdk_bat.c
+++ b/gdk/gdk_bat.c
@@ -184,9 +184,12 @@ COLnew(oid hseq, int tt, BUN cap, role_t
/* round up to multiple of BATTINY */
if (cap < BUN_MAX - BATTINY)
cap = (cap + BATTINY - 1) & ~(BATTINY - 1);
- if (ATOMstorage(tt) == TYPE_msk && cap < 8*BATTINY)
- cap = 8*BATTINY;
- else if (cap < BATTINY)
+ if (ATOMstorage(tt) == TYPE_msk) {
+ if (cap < 8*BATTINY)
+ cap = 8*BATTINY;
+ else
+ cap = (cap + 31) & ~(BUN)31;
+ } else if (cap < BATTINY)
cap = BATTINY;
/* limit the size */
if (cap > BUN_MAX)
@@ -1179,6 +1182,8 @@ BUNdelete(BAT *b, oid o)
return GDK_FAIL;
if (ATOMstorage(b->ttype) == TYPE_msk) {
mskSetVal(b, p, mskGetVal(b, BUNlast(b) - 1));
+ /* don't leave garbage */
+ mskClr(b, BUNlast(b) - 1);
} else {
memcpy(Tloc(b, p), Tloc(b, BUNlast(b) - 1), Tsize(b));
}
diff --git a/gdk/gdk_cand.c b/gdk/gdk_cand.c
--- a/gdk/gdk_cand.c
+++ b/gdk/gdk_cand.c
@@ -297,10 +297,8 @@ BATdiffcand(BAT *a, BAT *b)
/* b is dense and a is not: we can copy the part of a
* that is before the start of b and the part of a
* that is after the end of b */
- bn = canditer_slice2(&cia, 0,
- canditer_search(&cia, cib.seq, true),
- canditer_search(&cia, cib.seq + cib.ncand,
true),
- cia.ncand);
+ bn = canditer_slice2val(&cia, oid_nil, cib.seq,
+ cib.seq + cib.ncand, oid_nil);
goto doreturn;
}
@@ -362,6 +360,53 @@ binsearchcand(const oid *cand, BUN hi, o
return hi;
}
+/* population count: count number of 1 bits in a value */
+static inline uint32_t __attribute__((__const__))
+pop(uint32_t x)
+{
+#ifdef __GNUC__
+ return (uint32_t) __builtin_popcount(x);
+#else
+#ifdef _MSC_VER
+ return (uint32_t) __popcnt((unsigned int) (x));
+#else
+ /* divide and conquer implementation */
+ x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
+ x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
+ x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
+ x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
+ x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
+ return x;
+#endif
+#endif
+}
+
+/* count number of 1 bits in ci->mask between bit positions lo
+ * (inclusive) and hi (not inclusive) */
+static BUN
+count_mask_bits(struct canditer *ci, BUN lo, BUN hi)
+{
+ BUN n;
+ assert(lo <= hi);
+ assert(ci->tpe == cand_mask);
+ if (lo == hi)
+ return 0;
+ lo += ci->firstbit;
+ hi += ci->firstbit;
+ BUN loi = lo / 32;
+ BUN hii = hi / 32;
+ lo %= 32;
+ hi %= 32;
+ if (loi == hii)
+ return (BUN) pop((ci->mask[loi] & ((1U << hi) - 1)) >> lo);
+ n = (BUN) pop(ci->mask[loi++] >> lo);
+ while (loi < hii)
+ n += (BUN) pop(ci->mask[loi++]);
+ if (hi != 0)
+ n += (BUN) pop(ci->mask[loi] & ((1U << hi) - 1));
+ return n;
+}
+
/* initialize a candidate iterator, return number of iterations */
BUN
canditer_init(struct canditer *ci, BAT *b, BAT *s)
@@ -413,8 +458,8 @@ canditer_init(struct canditer *ci, BAT *
assert(!is_oid_nil(ci->seq));
if (s->tvheap) {
assert(s->tvheap->free % SIZEOF_OID == 0);
- ci->noids = s->tvheap->free / SIZEOF_OID;
- if (ci->noids > 0) {
+ ci->nvals = s->tvheap->free / SIZEOF_OID;
+ if (ci->nvals > 0) {
ci->tpe = cand_except;
ci->oids = (const oid *) s->tvheap->base;
} else {
@@ -424,11 +469,16 @@ canditer_init(struct canditer *ci, BAT *
} else {
ci->tpe = cand_dense;
}
+ } else if (s->ttype == TYPE_msk) {
+ ci->tpe = cand_mask;
+ ci->mask = (const uint32_t *) s->theap.base;
+ ci->seq = s->hseqbase;
+ ci->nvals = (cnt + 31U) / 32U;
} else if (is_oid_nil(ci->seq)) {
ci->tpe = cand_materialized;
ci->oids = (const oid *) s->theap.base;
ci->seq = ci->oids[0];
- ci->noids = cnt;
+ ci->nvals = cnt;
} else {
/* materialized dense: no exceptions */
ci->tpe = cand_dense;
@@ -436,14 +486,14 @@ canditer_init(struct canditer *ci, BAT *
switch (ci->tpe) {
case cand_materialized:
if (b != NULL) {
- BUN p = binsearchcand(ci->oids, cnt - 1, b->hseqbase);
+ BUN p = binsearchcand(ci->oids, cnt - 1U, b->hseqbase);
/* p == cnt means candidate list is completely
* before b */
ci->offset = p;
ci->oids += p;
cnt -= p;
if (cnt > 0) {
- cnt = binsearchcand(ci->oids, cnt - 1,
+ cnt = binsearchcand(ci->oids, cnt - 1U,
b->hseqbase + BATcount(b));
/* cnt == 0 means candidate list is
* completely after b */
@@ -457,49 +507,50 @@ canditer_init(struct canditer *ci, BAT *
return 0;
}
ci->seq = ci->oids[0];
- ci->noids = cnt;
- if (ci->oids[cnt - 1] - ci->seq == cnt - 1) {
+ ci->nvals = cnt;
+ if (ci->oids[cnt - 1U] - ci->seq == cnt - 1U) {
/* actually dense */
ci->tpe = cand_dense;
ci->oids = NULL;
- ci->noids = 0;
+ ci->nvals = 0;
}
}
break;
case cand_except:
/* exceptions must all be within range of s */
assert(ci->oids[0] >= ci->seq);
- assert(ci->oids[ci->noids - 1] < ci->seq + cnt + ci->noids);
+ assert(ci->oids[ci->nvals - 1U] < ci->seq + cnt + ci->nvals);
/* prune exceptions at either end of range of s */
- while (ci->noids > 0 && ci->oids[0] == ci->seq) {
- ci->noids--;
+ while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
+ ci->nvals--;
ci->oids++;
ci->seq++;
}
- while (ci->noids > 0 &&
- ci->oids[ci->noids - 1] == ci->seq + cnt + ci->noids - 1)
- ci->noids--;
+ while (ci->nvals > 0 &&
+ ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals -
1U)
+ ci->nvals--;
if (b != NULL) {
- if (ci->seq + cnt + ci->noids <= b->hseqbase ||
+ if (ci->seq + cnt + ci->nvals <= b->hseqbase ||
ci->seq >= b->hseqbase + BATcount(b)) {
/* candidate list does not overlap with b */
*ci = (struct canditer) {
.tpe = cand_dense,
+ .s = s,
};
return 0;
}
}
- if (ci->noids > 0) {
+ if (ci->nvals > 0) {
if (b == NULL)
break;
BUN p;
- p = binsearchcand(ci->oids, ci->noids - 1, b->hseqbase);
- if (p == ci->noids) {
+ p = binsearchcand(ci->oids, ci->nvals - 1U,
b->hseqbase);
+ if (p == ci->nvals) {
/* all exceptions before start of b */
- ci->offset = b->hseqbase - ci->seq - ci->noids;
- cnt = ci->seq + cnt + ci->noids - b->hseqbase;
+ ci->offset = b->hseqbase - ci->seq - ci->nvals;
+ cnt = ci->seq + cnt + ci->nvals - b->hseqbase;
ci->seq = b->hseqbase;
- ci->noids = 0;
+ ci->nvals = 0;
ci->tpe = cand_dense;
ci->oids = NULL;
break;
@@ -509,27 +560,27 @@ canditer_init(struct canditer *ci, BAT *
/* skip candidates, possibly including
* exceptions */
ci->oids += p;
- ci->noids -= p;
+ ci->nvals -= p;
p = b->hseqbase - ci->seq - p;
cnt -= p;
ci->offset += p;
ci->seq = b->hseqbase;
}
- if (ci->seq + cnt + ci->noids > b->hseqbase +
BATcount(b)) {
- p = binsearchcand(ci->oids, ci->noids - 1,
+ if (ci->seq + cnt + ci->nvals > b->hseqbase +
BATcount(b)) {
+ p = binsearchcand(ci->oids, ci->nvals - 1U,
b->hseqbase + BATcount(b));
- ci->noids = p;
- cnt = b->hseqbase + BATcount(b) - ci->seq -
ci->noids;
+ ci->nvals = p;
+ cnt = b->hseqbase + BATcount(b) - ci->seq -
ci->nvals;
}
- while (ci->noids > 0 && ci->oids[0] == ci->seq) {
- ci->noids--;
+ while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
+ ci->nvals--;
ci->oids++;
ci->seq++;
}
- while (ci->noids > 0 &&
- ci->oids[ci->noids - 1] == ci->seq + cnt +
ci->noids - 1)
- ci->noids--;
- if (ci->noids > 0)
+ while (ci->nvals > 0 &&
+ ci->oids[ci->nvals - 1U] == ci->seq + cnt +
ci->nvals - 1U)
+ ci->nvals--;
+ if (ci->nvals > 0)
break;
}
ci->tpe = cand_dense;
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
