Changeset: 195341e414a8 for MonetDB URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=195341e414a8 Modified Files: clients/Tests/exports.stable.out gdk/ChangeLog gdk/gdk.h gdk/gdk_cand.h gdk/gdk_firstn.c gdk/gdk_private.h gdk/gdk_search.c gdk/gdk_select.c monetdb5/modules/kernel/algebra.c Branch: default Log Message:
Implemented a nilslast option for BATfirstn. diffs (truncated from 1152 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 @@ -116,7 +116,7 @@ BAT *BATdense(oid hseq, oid tseq, BUN cn BAT *BATdiff(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate); gdk_return BATextend(BAT *b, BUN newcap) __attribute__((__warn_unused_result__)); void BATfakeCommit(BAT *b); -gdk_return BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *cands, BAT *grps, BUN n, bool asc, bool distinct) __attribute__((__warn_unused_result__)); +gdk_return BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *cands, BAT *grps, BUN n, bool asc, bool nilslast, bool distinct) __attribute__((__warn_unused_result__)); int BATgetaccess(BAT *b); PROPrec *BATgetprop(BAT *b, enum prop_t idx); gdk_return BATgroup(BAT **groups, BAT **extents, BAT **histo, BAT *b, BAT *s, BAT *g, BAT *e, BAT *h) __attribute__((__warn_unused_result__)); diff --git a/gdk/ChangeLog b/gdk/ChangeLog --- a/gdk/ChangeLog +++ b/gdk/ChangeLog @@ -1,6 +1,12 @@ # ChangeLog file for MonetDB # This file is updated with Maddlog +* Wed Nov 7 2018 Sjoerd Mullender <[email protected]> +- Implemented a nilslast option for BATfirstn. If set, NILs come + last in the ordering that BATfirstn simulates, so non-NIL values are + preferentially returned. The old behavior can be obtained by setting + nilslast to !asc(ending). + * Tue Nov 6 2018 Sjoerd Mullender <[email protected]> - Implemented a nilslast option for BATsort. This option should be equal to the reverse option for stable sort (it is not implemented for diff --git a/gdk/gdk.h b/gdk/gdk.h --- a/gdk/gdk.h +++ b/gdk/gdk.h @@ -2756,7 +2756,7 @@ gdk_export BAT *BATunique(BAT *b, BAT *s gdk_export BAT *BATmergecand(BAT *a, BAT *b); gdk_export BAT *BATintersectcand(BAT *a, BAT *b); -gdk_export gdk_return BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *cands, BAT *grps, BUN n, bool asc, bool distinct) +gdk_export gdk_return BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *cands, BAT *grps, BUN n, bool asc, bool nilslast, bool distinct) __attribute__((__warn_unused_result__)); #include "gdk_calc.h" diff --git a/gdk/gdk_cand.h b/gdk/gdk_cand.h --- a/gdk/gdk_cand.h +++ b/gdk/gdk_cand.h @@ -27,10 +27,8 @@ start = (s)->tseqbase; \ end = start + BATcount(s); \ } else { \ - oid x = (b)->hseqbase; \ - start = SORTfndfirst((s), &x); \ - x += BATcount(b); \ - end = SORTfndfirst((s), &x); \ + start = SORTfndfirst((s), &(b)->hseqbase); \ + end = SORTfndfirst((s), &(oid){(b)->hseqbase+BATcount(b)}); \ cand = (const oid *) Tloc((s), start); \ candend = (const oid *) Tloc((s), end); \ if (cand == candend) { \ diff --git a/gdk/gdk_firstn.c b/gdk/gdk_firstn.c --- a/gdk/gdk_firstn.c +++ b/gdk/gdk_firstn.c @@ -15,14 +15,19 @@ * asc(ending) is set, else the largest n elements). Conceptually, b * is sorted in ascending or descending order (depending on the asc * argument) and then the OIDs of the first n elements are returned. + * If there are NILs in the BAT, their relative ordering is set by + * using the nilslast argument: if set, NILs come last (largest value + * when ascending, smallest value when descending), so if there are + * enough non-NIL values, no NILs will be returned. If unset (false), + * NILs come first and will be returned. * * In addition to the input BAT b, there can be a standard candidate * list s. If s is specified (non-NULL), only elements in b that are * referred to in s are considered. * - * If the third input bat g is non-NULL, then s must also be non-NULL. - * G then specifies groups to which the elements referred to in s - * belong (g must be aligned with s). Conceptually, the group values + * If the third input bat g is non-NULL, then s must also be non-NULL + * and must be aligned with g. G then specifies groups to which the + * elements referred to in s belong. Conceptually, the group values * are sorted in ascending order together with the elements in b that * are referred to in s (in ascending or descending order depending on * asc), and the first n elements are then returned. @@ -39,9 +44,9 @@ * * Note that BATfirstn can be called in cascading fashion to calculate * the first n values of a table of multiple columns: - * BATfirstn(&s1, &g1, b1, NULL, NULL, n, asc, distinct); - * BATfirstn(&s2, &g2, b2, s1, g1, n, asc, distinct); - * BATfirstn(&s3, NULL, b3, s2, g2, n, asc, distinct); + * BATfirstn(&s1, &g1, b1, NULL, NULL, n, asc, nilslast, distinct); + * BATfirstn(&s2, &g2, b2, s1, g1, n, asc, nilslast, distinct); + * BATfirstn(&s3, NULL, b3, s2, g2, n, asc, nilslast, distinct); * If the input BATs b1, b2, b3 are large enough, s3 will contain the * OIDs of the smallest (largest) n elements in the table consisting * of the columns b1, b2, b3 when ordered in ascending order with b1 @@ -50,8 +55,8 @@ /* We use a binary heap for the implementation of the simplest form of * first-N. During processing, the oids list forms a heap with the - * root at position 0 and the children of a node at position n at - * positions 2*n+1 and 2*n+2. The parent node is always + * root at position 0 and the children of a node at position i at + * positions 2*i+1 and 2*i+2. The parent node is always * smaller/larger (depending on the value of asc) than its children * (recursively). The heapify macro creates the heap from the input * in-place. We start off with a heap containing the first N elements @@ -87,14 +92,44 @@ siftdown(OPER, i - 1, SWAP); \ } while (0) +/* we inherit LT and GT from gdk_calc_private.h */ + +#define nLTbte(a, b) (!is_bte_nil(b) && (is_bte_nil(a) || (a) < (b))) +#define nLTsht(a, b) (!is_sht_nil(b) && (is_sht_nil(a) || (a) < (b))) +#define nLTint(a, b) (!is_int_nil(b) && (is_int_nil(a) || (a) < (b))) +#define nLTlng(a, b) (!is_lng_nil(b) && (is_lng_nil(a) || (a) < (b))) +#define nLThge(a, b) (!is_hge_nil(b) && (is_hge_nil(a) || (a) < (b))) + +#define nGTbte(a, b) (!is_bte_nil(b) && (is_bte_nil(a) || (a) > (b))) +#define nGTsht(a, b) (!is_sht_nil(b) && (is_sht_nil(a) || (a) > (b))) +#define nGTint(a, b) (!is_int_nil(b) && (is_int_nil(a) || (a) > (b))) +#define nGTlng(a, b) (!is_lng_nil(b) && (is_lng_nil(a) || (a) > (b))) +#define nGThge(a, b) (!is_hge_nil(b) && (is_hge_nil(a) || (a) > (b))) + #define LTany(p1, p2) (cmp(BUNtail(bi, oids[p1] - b->hseqbase), \ BUNtail(bi, oids[p2] - b->hseqbase)) < 0) #define GTany(p1, p2) (cmp(BUNtail(bi, oids[p1] - b->hseqbase), \ BUNtail(bi, oids[p2] - b->hseqbase)) > 0) -#define LTflt(a, b) ((bit) (!is_flt_nil(b) && (is_flt_nil(a) || (a) < (b)))) -#define LTdbl(a, b) ((bit) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) < (b)))) -#define GTflt(a, b) ((bit) (!is_flt_nil(a) && (is_flt_nil(b) || (a) > (b)))) -#define GTdbl(a, b) ((bit) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) > (b)))) + +#define nLTany(p1, p2) (cmp(BUNtail(bi, oids[p1] - b->hseqbase), nil) != 0 \ + && (cmp(BUNtail(bi, oids[p2] - b->hseqbase), nil) == 0 \ + || cmp(BUNtail(bi, oids[p1] - b->hseqbase), \ + BUNtail(bi, oids[p2] - b->hseqbase)) < 0)) +#define nGTany(p1, p2) (cmp(BUNtail(bi, oids[p2] - b->hseqbase), nil) != 0 \ + && (cmp(BUNtail(bi, oids[p1] - b->hseqbase), nil) == 0 \ + || cmp(BUNtail(bi, oids[p1] - b->hseqbase), \ + BUNtail(bi, oids[p2] - b->hseqbase)) > 0)) + +#define LTflt(a, b) (!is_flt_nil(b) && (is_flt_nil(a) || (a) < (b))) +#define LTdbl(a, b) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) < (b))) +#define GTflt(a, b) (!is_flt_nil(a) && (is_flt_nil(b) || (a) > (b))) +#define GTdbl(a, b) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) > (b))) + +#define nLTflt(a, b) (!is_flt_nil(a) && (is_flt_nil(b) || (a) < (b))) +#define nLTdbl(a, b) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) < (b))) +#define nGTflt(a, b) (!is_flt_nil(b) && (is_flt_nil(a) || (a) > (b))) +#define nGTdbl(a, b) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) > (b))) + #define LTfltfix(p1, p2) LTflt(vals[oids[p1] - b->hseqbase], \ vals[oids[p2] - b->hseqbase]) #define GTfltfix(p1, p2) GTflt(vals[oids[p1] - b->hseqbase], \ @@ -107,6 +142,36 @@ vals[oids[p2] - b->hseqbase]) #define GTfix(p1, p2) GT(vals[oids[p1] - b->hseqbase], \ vals[oids[p2] - b->hseqbase]) + +#define nLTfltfix(p1, p2) nLTflt(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGTfltfix(p1, p2) nGTflt(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nLTdblfix(p1, p2) nLTdbl(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGTdblfix(p1, p2) nGTdbl(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nLTbtefix(p1, p2) nLTbte(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGTbtefix(p1, p2) nGTbte(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nLTshtfix(p1, p2) nLTsht(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGTshtfix(p1, p2) nGTsht(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nLTintfix(p1, p2) nLTint(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGTintfix(p1, p2) nGTint(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nLTlngfix(p1, p2) nLTlng(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGTlngfix(p1, p2) nGTlng(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nLThgefix(p1, p2) nLThge(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) +#define nGThgefix(p1, p2) nGThge(vals[oids[p1] - b->hseqbase], \ + vals[oids[p2] - b->hseqbase]) + #define SWAP1(p1, p2) \ do { \ item = oids[p1]; \ @@ -121,7 +186,7 @@ while (cand ? cand < candend : start < end) { \ i = cand ? *cand++ : start++ + b->hseqbase; \ if (OP(vals[i - b->hseqbase], \ - vals[oids[0] - b->hseqbase])) { \ + vals[oids[0] - b->hseqbase])) { \ oids[0] = i; \ siftdown(OP##fix, 0, SWAP1); \ } \ @@ -139,7 +204,7 @@ * that are not all included in the first N. */ static BAT * -BATfirstn_unique(BAT *b, BAT *s, BUN n, bool asc, oid *lastp) +BATfirstn_unique(BAT *b, BAT *s, BUN n, bool asc, bool nilslast, oid *lastp) { BAT *bn; BATiter bi = bat_iterator(b); @@ -148,6 +213,7 @@ BATfirstn_unique(BAT *b, BAT *s, BUN n, const oid *restrict cand, *candend; int tpe = b->ttype; int (*cmp)(const void *, const void *); + const void *nil; /* variables used in heapify/siftdown macros */ oid item; BUN pos, childpos; @@ -155,67 +221,231 @@ BATfirstn_unique(BAT *b, BAT *s, BUN n, CANDINIT(b, s, start, end, cnt, cand, candend); if (cand) { - if (n >= (BUN) (candend - cand)) { + cnt = (BUN) (candend - cand); + start = (BUN) (cand - (const oid *) Tloc(s, 0)); + end = (BUN) (candend - (const oid *) Tloc(s, 0)); + if (n >= cnt) { /* trivial: return the candidate list (the * part that refers to b, that is) */ if (lastp) *lastp = 0; - return BATslice(s, - (BUN) (cand - (const oid *) Tloc(s, 0)), - (BUN) (candend - (const oid *) Tloc(s, 0))); + return BATslice(s, start, end); + } + } else { + cnt = end - start; + if (n >= cnt) { + /* trivial: return everything */ + bn = BATdense(0, start + b->hseqbase, cnt); + if (bn == NULL) + return NULL; + if (lastp) + *lastp = 0; + return bn; } - } else if (n >= cnt) { - /* trivial: return everything */ - bn = BATdense(0, start + b->hseqbase, cnt); - if (bn == NULL) - return NULL; + } + if (BATtvoid(b)) { + /* nilslast doesn't make a difference: either all are + * nil, or none are */ + if (asc || is_oid_nil(b->tseqbase)) { + /* return the first part of the candidate list + * or of the BAT itself */ + if (cand) { + if (lastp) + *lastp = cand[n - 1]; + return BATslice(s, start, start + n); + } + if (lastp) + *lastp = is_oid_nil(b->tseqbase) + ? oid_nil : b->hseqbase + n - 1; + return BATdense(0, b->hseqbase, n); + } + /* return the last part of the candidate list or of + * the BAT itself */ + if (cand) { + if (lastp) + *lastp = cand[cnt - n]; + return BATslice(s, end - n, end); + } if (lastp) - *lastp = 0; - return bn; + *lastp = b->hseqbase + end - n; + return BATdense(0, b->hseqbase + end - n, n); } /* note, we want to do both calls */ if (BATordered(b) | BATordered_rev(b)) { /* trivial: b is sorted so we just need to return the * initial or final part of it (or of the candidate - * list) */ + * list); however, if nilslast == asc, then the nil + * values (if any) are in the wrong place, so we need + * to do a little more work */ if (cand) { + if (nilslast == asc && !b->tnonil) { + pos = binsearch(cand, b->hseqbase, tpe, + Tloc(b, 0), + b->tvheap?b->tvheap->base:NULL, + b->twidth, 0, + cnt, + ATOMnilptr(tpe), + b->tsorted ? 1 : -1, 1); + /* 0 <= pos <= cnt _______________________________________________ checkin-list mailing list [email protected] https://www.monetdb.org/mailman/listinfo/checkin-list
