Changeset: 89d265d61433 for MonetDB URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=89d265d61433 Modified Files: clients/Tests/exports.stable.out gdk/ChangeLog gdk/gdk.h gdk/gdk_aggr.c gdk/gdk_batop.c gdk/gdk_firstn.c gdk/gdk_imprints.c gdk/gdk_orderidx.c gdk/gdk_qsort.c gdk/gdk_qsort_impl.h gdk/gdk_select.c gdk/gdk_ssort.c gdk/gdk_ssort_impl.h gdk/gdk_tm.c monetdb5/modules/atoms/batxml.c monetdb5/modules/atoms/json.c monetdb5/modules/kernel/algebra.c monetdb5/modules/kernel/bat5.c sql/backends/monet5/sql.c sql/common/sql_list.c sql/server/rel_optimizer.c sql/storage/bat/bat_table.c sql/storage/store.c Branch: default Log Message:
Implemented a nilslast option for BATsort/GDKqsort. When using stable sort (BATsort with stable argument true), the new nilslast parameter must be equal to the reverse parameter. diffs (truncated from 1626 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 @@ -172,7 +172,7 @@ void BATsetcapacity(BAT *b, BUN cnt); void BATsetcount(BAT *b, BUN cnt); void BATsetprop(BAT *b, enum prop_t idx, int type, const void *v); BAT *BATslice(BAT *b, BUN low, BUN high); -gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, BAT *b, BAT *o, BAT *g, bool reverse, bool stable) __attribute__((__warn_unused_result__)); +gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, BAT *b, BAT *o, BAT *g, bool reverse, bool nilslast, bool stable) __attribute__((__warn_unused_result__)); gdk_return BATstr_group_concat(ValPtr res, BAT *b, BAT *s, bool skip_nils, bool abort_on_error, bool nil_if_empty, const char *separator); gdk_return BATsubcross(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr) __attribute__((__warn_unused_result__)); gdk_return BATsum(void *res, int tp, BAT *b, BAT *s, bool skip_nils, bool abort_on_error, bool nil_if_empty); @@ -258,8 +258,7 @@ gdk_return GDKmmapfile(str buffer, size_ int GDKms(void); int GDKnr_threads; void GDKprepareExit(void); -void GDKqsort(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe); -void GDKqsort_rev(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe); +void GDKqsort(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe, bool reverse, bool nilslast); void *GDKrealloc(void *pold, size_t size) __attribute__((__alloc_size__(2))) __attribute__((__warn_unused_result__)); void GDKregister(MT_Id pid); gdk_return GDKreleasemmap(void *ptr, size_t size, size_t id, str *msg); diff --git a/gdk/ChangeLog b/gdk/ChangeLog --- a/gdk/ChangeLog +++ b/gdk/ChangeLog @@ -1,6 +1,14 @@ # ChangeLog file for MonetDB # This file is updated with Maddlog +* 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 + stable sort), but can be different from reverse for non-stable sort. + The functions BATsort and GDKqsort have extra parameters, the function + GDKqsort_rev has been removed (superseded by GDKqsort with the new + `reverse' parameter). + * Tue Oct 30 2018 Sjoerd Mullender <[email protected]> - The BUNtail, BUNtvar, BUNtloc, and BUNtpos macros (and Tloc and Tpos) now return a `void *' instead of a `char *'. diff --git a/gdk/gdk.h b/gdk/gdk.h --- a/gdk/gdk.h +++ b/gdk/gdk.h @@ -1422,12 +1422,11 @@ gdk_export gdk_return BATprint(BAT *b); gdk_export bool BATkeyed(BAT *b); gdk_export bool BATordered(BAT *b); gdk_export bool BATordered_rev(BAT *b); -gdk_export gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, BAT *b, BAT *o, BAT *g, bool reverse, bool stable) +gdk_export gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, BAT *b, BAT *o, BAT *g, bool reverse, bool nilslast, bool stable) __attribute__((__warn_unused_result__)); -gdk_export void GDKqsort(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe); -gdk_export void GDKqsort_rev(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe); +gdk_export void GDKqsort(void *restrict h, void *restrict t, const void *restrict base, size_t n, int hs, int ts, int tpe, bool reverse, bool nilslast); #define BATtordered(b) ((b)->tsorted) #define BATtrevordered(b) ((b)->trevsorted) diff --git a/gdk/gdk_aggr.c b/gdk/gdk_aggr.c --- a/gdk/gdk_aggr.c +++ b/gdk/gdk_aggr.c @@ -2867,14 +2867,14 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, BBPunfix(g->batCacheid); return bn; } - if (BATsort(&t1, &t2, NULL, g, NULL, NULL, false, false) != GDK_SUCCEED) + if (BATsort(&t1, &t2, NULL, g, NULL, NULL, false, false, false) != GDK_SUCCEED) goto bunins_failed; if (freeg) BBPunfix(g->batCacheid); g = t1; freeg = true; - if (BATsort(&t1, NULL, NULL, b, t2, g, false, false) != GDK_SUCCEED) { + if (BATsort(&t1, NULL, NULL, b, t2, g, false, false, false) != GDK_SUCCEED) { BBPunfix(t2->batCacheid); goto bunins_failed; } @@ -2948,7 +2948,7 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, BATcheckorderidx(pb))) { ords = (const oid *) (pb ? pb->torderidx->base : b->torderidx->base) + ORDERIDXOFF; } else { - if (BATsort(NULL, &t1, NULL, b, NULL, g, false, false) != GDK_SUCCEED) + if (BATsort(NULL, &t1, NULL, b, NULL, g, false, false, false) != GDK_SUCCEED) goto bunins_failed; if (BATtdense(t1)) ords = NULL; diff --git a/gdk/gdk_batop.c b/gdk/gdk_batop.c --- a/gdk/gdk_batop.c +++ b/gdk/gdk_batop.c @@ -1326,22 +1326,18 @@ BATordered_rev(BAT *b) * "quick" sort does not produce errors */ static gdk_return do_sort(void *restrict h, void *restrict t, const void *restrict base, - size_t n, int hs, int ts, int tpe, bool reverse, bool stable) + size_t n, int hs, int ts, int tpe, bool reverse, bool nilslast, + bool stable) { if (n <= 1) /* trivially sorted */ return GDK_SUCCEED; - if (reverse) { - if (stable) { + if (stable) { + if (reverse) return GDKssort_rev(h, t, base, n, hs, ts, tpe); - } else { - GDKqsort_rev(h, t, base, n, hs, ts, tpe); - } + else + return GDKssort(h, t, base, n, hs, ts, tpe); } else { - if (stable) { - return GDKssort(h, t, base, n, hs, ts, tpe); - } else { - GDKqsort(h, t, base, n, hs, ts, tpe); - } + GDKqsort(h, t, base, n, hs, ts, tpe, reverse, nilslast); } return GDK_SUCCEED; } @@ -1376,14 +1372,14 @@ do_sort(void *restrict h, void *restrict * Apart from error checking and maintaining reference counts, sorting * three columns (col1, col2, col3) could look like this with the * sorted results in (col1s, col2s, col3s): - * BATsort(&col1s, &ord1, &grp1, col1, NULL, NULL, false, false); - * BATsort(&col2s, &ord2, &grp2, col2, ord1, grp1, false, false); - * BATsort(&col3s, NULL, NULL, col3, ord2, grp2, false, false); + * BATsort(&col1s, &ord1, &grp1, col1, NULL, NULL, false, false, false); + * BATsort(&col2s, &ord2, &grp2, col2, ord1, grp1, false, false, false); + * BATsort(&col3s, NULL, NULL, col3, ord2, grp2, false, false, false); * Note that the "reverse" parameter can be different for each call. */ gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, - BAT *b, BAT *o, BAT *g, bool reverse, bool stable) + BAT *b, BAT *o, BAT *g, bool reverse, bool nilslast, bool stable) { BAT *bn = NULL, *on = NULL, *gn = NULL, *pb = NULL; oid *restrict grps, *restrict ords, prev; @@ -1392,10 +1388,20 @@ BATsort(BAT **sorted, BAT **order, BAT * ALGODEBUG t0 = GDKusec(); + /* we haven't implemented NILs as largest value for stable + * sort, so NILs come first for ascending and last for + * descending */ + assert(!stable || reverse == nilslast); + if (b == NULL) { GDKerror("BATsort: b must exist\n"); return GDK_FAIL; } + if (stable && reverse != nilslast) { + GDKerror("BATsort: stable sort cannot have " + "reverse != nilslast\n"); + return GDK_FAIL; + } if (!ATOMlinear(b->ttype)) { GDKerror("BATsort: type %s cannot be sorted\n", ATOMname(b->ttype)); @@ -1436,7 +1442,8 @@ BATsort(BAT **sorted, BAT **order, BAT * (g->ttype == TYPE_void && /* no nil tail */ BATcount(g) != 0 && is_oid_nil(g->tseqbase)))) { - GDKerror("BATsort: g must have type oid, sorted on the tail, and same size as b\n"); + GDKerror("BATsort: g must have type oid, sorted on the tail, " + "and same size as b\n"); return GDK_FAIL; } if (sorted == NULL && order == NULL) { @@ -1449,8 +1456,15 @@ BATsort(BAT **sorted, BAT **order, BAT * * subsorting and the sort is not stable */ o = NULL; } + if (b->tnonil) { + /* if there are no nils, placement of nils doesn't + * matter, so set nilslast such that ordered bits can + * be used */ + nilslast = reverse; + } if (BATcount(b) <= 1 || - ((reverse ? BATtrevordered(b) : BATtordered(b)) && + (reverse == nilslast && + (reverse ? BATtrevordered(b) : BATtordered(b)) && o == NULL && g == NULL && (groups == NULL || BATtkey(b) || (reverse ? BATtordered(b) : BATtrevordered(b))))) { @@ -1488,11 +1502,12 @@ BATsort(BAT **sorted, BAT **order, BAT * } ALGODEBUG fprintf(stderr, "#BATsort(b=" ALGOBATFMT ",o=" ALGOOPTBATFMT ",g=" ALGOOPTBATFMT - ",reverse=%d,stable=%d) = (" ALGOOPTBATFMT - "," ALGOOPTBATFMT "," ALGOOPTBATFMT - ") -- trivial (" LLFMT " usec)\n", + ",reverse=%d,nilslast=%d,stable=%d) = (" + ALGOOPTBATFMT "," ALGOOPTBATFMT "," + ALGOOPTBATFMT ") -- trivial (" LLFMT + " usec)\n", ALGOBATPAR(b), ALGOOPTBATPAR(o), - ALGOOPTBATPAR(g), reverse, stable, + ALGOOPTBATPAR(g), reverse, nilslast, stable, ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), ALGOOPTBATPAR(on), GDKusec() - t0); return GDK_SUCCEED; @@ -1507,7 +1522,7 @@ BATsort(BAT **sorted, BAT **order, BAT * } else { pb = b; } - if (g == NULL && o == NULL && !reverse && + if (g == NULL && o == NULL && !reverse && !nilslast && pb != NULL && BATcheckorderidx(pb) && /* if we want a stable sort, the order index must be * stable, if we don't want stable, we don't care */ @@ -1556,11 +1571,12 @@ BATsort(BAT **sorted, BAT **order, BAT * } ALGODEBUG fprintf(stderr, "#BATsort(b=" ALGOBATFMT ",o=" ALGOOPTBATFMT ",g=" ALGOOPTBATFMT - ",reverse=%d,stable=%d) = (" ALGOOPTBATFMT - "," ALGOOPTBATFMT "," ALGOOPTBATFMT - ") -- orderidx (" LLFMT " usec)\n", + ",reverse=%d,nilslast=%d,stable=%d) = (" + ALGOOPTBATFMT "," ALGOOPTBATFMT "," + ALGOOPTBATFMT ") -- orderidx (" LLFMT + " usec)\n", ALGOBATPAR(b), ALGOOPTBATPAR(o), - ALGOOPTBATPAR(g), reverse, stable, + ALGOOPTBATPAR(g), reverse, nilslast, stable, ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), ALGOOPTBATPAR(on), GDKusec() - t0); return GDK_SUCCEED; @@ -1657,12 +1673,13 @@ BATsort(BAT **sorted, BAT **order, BAT * } ALGODEBUG fprintf(stderr, "#BATsort(b=" ALGOBATFMT ",o=" ALGOOPTBATFMT ",g=" ALGOBATFMT - ",reverse=%d,stable=%d) = (" - ALGOOPTBATFMT "," ALGOOPTBATFMT "," - ALGOOPTBATFMT ") -- key group (" LLFMT - " usec)\n", ALGOBATPAR(b), - ALGOOPTBATPAR(o), ALGOBATPAR(g), - reverse, stable, ALGOOPTBATPAR(bn), + ",reverse=%d,nilslast=%d,stable=%d" + ") = (" ALGOOPTBATFMT "," + ALGOOPTBATFMT "," ALGOOPTBATFMT + ") -- key group (" LLFMT " usec)\n", + ALGOBATPAR(b), ALGOOPTBATPAR(o), + ALGOBATPAR(g), reverse, nilslast, + stable, ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), ALGOOPTBATPAR(on), GDKusec() - t0); return GDK_SUCCEED; @@ -1679,7 +1696,7 @@ BATsort(BAT **sorted, BAT **order, BAT * ords ? ords + r : NULL, bn->tvheap ? bn->tvheap->base : NULL, p - r, Tsize(bn), ords ? sizeof(oid) : 0, - bn->ttype, reverse, stable) != GDK_SUCCEED) + bn->ttype, reverse, nilslast, stable) != GDK_SUCCEED) goto error; r = p; prev = grps[p]; @@ -1690,17 +1707,18 @@ BATsort(BAT **sorted, BAT **order, BAT * ords ? ords + r : NULL, bn->tvheap ? bn->tvheap->base : NULL, p - r, Tsize(bn), ords ? sizeof(oid) : 0, - bn->ttype, reverse, stable) != GDK_SUCCEED) + bn->ttype, reverse, nilslast, stable) != GDK_SUCCEED) goto error; /* if single group (r==0) the result is (rev)sorted, * otherwise (maybe) not */ - bn->tsorted = r == 0 && !reverse; - bn->trevsorted = r == 0 && reverse; + bn->tsorted = r == 0 && !reverse && !nilslast; + bn->trevsorted = r == 0 && reverse && nilslast; } else { Heap *m = NULL; /* only invest in creating an order index if the BAT * is persistent */ if (!reverse && + !nilslast && pb != NULL && (ords != NULL || pb->batPersistence == PERSISTENT) && (m = createOIDXheap(pb, stable)) != NULL) { @@ -1716,21 +1734,22 @@ BATsort(BAT **sorted, BAT **order, BAT * ords[p] = p + b->hseqbase; } } - if (!(reverse ? bn->trevsorted : bn->tsorted) && + if ((reverse != nilslast || + (reverse ? !bn->trevsorted : !bn->tsorted)) && (BATmaterialize(bn) != GDK_SUCCEED || do_sort(Tloc(bn, 0), ords, bn->tvheap ? bn->tvheap->base : NULL, BATcount(bn), Tsize(bn), ords ? sizeof(oid) : 0, - bn->ttype, reverse, stable) != GDK_SUCCEED)) { + bn->ttype, reverse, nilslast, stable) != GDK_SUCCEED)) { if (m != NULL) { HEAPfree(m, true); GDKfree(m); } goto error; _______________________________________________ checkin-list mailing list [email protected] https://www.monetdb.org/mailman/listinfo/checkin-list
