Changeset: 0478cae3a378 for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=0478cae3a378 Added Files: 3 ArraysTests/Tests/All ArraysTests/Tests/Mtest.py.backup ArraysTests/Tests/approveTests.sh ArraysTests/Tests/create.sql ArraysTests/Tests/drop.sql ArraysTests/Tests/query_2d.sql ArraysTests/Tests/query_2d_no.sql ArraysTests/Tests/query_3d.sql ArraysTests/Tests/query_3d_no.sql ArraysTests/Tests/runTests.sh ArraysTests/Tests/tests.sql ArraysTests/Tests/tests.stable.err ArraysTests/Tests/tests.stable.out monetdb5/modules/kernel/arrays.c monetdb5/modules/kernel/arrays.h monetdb5/modules/kernel/arrays.mal Removed Files: gdk/gdk_arrays.c gdk/gdk_arrays.h gdk/gdk_arrays_aggr.c Modified Files: gdk/Makefile.ag gdk/gdk_aggr.c gdk/gdk_bat.c gdk/gdk_batop.c gdk/gdk_group.c gdk/gdk_join.c gdk/gdk_select.c monetdb5/modules/kernel/Makefile.ag monetdb5/modules/kernel/algebra.h monetdb5/modules/kernel/algebra.mal monetdb5/modules/mal/batcalc.c sql/backends/monet5/rel_bin.c sql/backends/monet5/sql.c sql/backends/monet5/sql.h sql/backends/monet5/sql.mal sql/backends/monet5/sql_gencode.c sql/backends/monet5/sql_statement.c sql/backends/monet5/sql_statement.h sql/server/sql_mvc.h sql/storage/bat/res_table.c Branch: arrays Log Message:
all arrays codes in 3 files arrays.c, arrays.h and arrays.mal found in monetdb5/modules/kernel diffs (truncated from 12568 to 300 lines): diff --git a/3 b/3 new file mode 100644 --- /dev/null +++ b/3 @@ -0,0 +1,3736 @@ +/* + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * Copyright 2008-2015 MonetDB B.V. + */ + +#include "monetdb_config.h" +#include "gdk.h" +#include "gdk_private.h" +#include "gdk_calc_private.h" + +#include <math.h> +/* + * All "sub" join variants produce some sort of join on two input + * BATs, optionally subject to up to two candidate lists. Only values + * in the input BATs that are mentioned in the associated candidate + * list (if provided) are eligible. They all return two output BATs + * in the first two arguments. The join operations differ in the way + * in which tuples from the two inputs are matched. + * + * All inputs BATs must be dense headed, the output BATs will also be + * dense headed. The outputs consist of two aligned BATs (i.e. same + * length and same seqbase in the head column (0@0)) that contain in + * their tails the OIDs of the input BATs that match. The candidate + * lists, if given, contain in their tail the OIDs of the associated + * input BAT which must be considered for matching. The input BATs + * must have the same tail type. + * + * All functions also have a parameter nil_matches which indicates + * whether NIL must be considered an ordinary value that can match, or + * whether NIL must be considered to never match. + * + * The join functions that are provided here are: + * BATsubjoin + * normal equi-join + * BATsubleftjoin + * normal equi-join, but the left output is sorted + * BATsubleftfetchjoin + * normal equi-join, but the left output is sorted, and all + * values in the left input must match at least one value in the + * right input + * BATsubouterjoin + * equi-join, but the left output is sorted, and if there is no + * match for a value in the left input, there is still an output + * with NIL in the right output + * BATsubsemijoin + * equi-join, but the left output is sorted, and if there are + * multiple matches, only one is returned (i.e., the left output + * is also key) + * BATsubthetajoin + * theta-join: an extra operator must be provided encoded as an + * integer (macros JOIN_EQ, JOIN_NE, JOIN_LT, JOIN_LE, JOIN_GT, + * JOIN_GE); value match if the left input has the given + * relationship with the right input; order of the outputs is not + * guaranteed + * BATsubbandjoin + * band-join: two extra input values (c1, c2) must be provided as + * well as Booleans (li, hi) that indicate whether the value + * ranges are inclusive or not; values in the left and right + * inputs match if right - c1 <[=] left <[=] right + c2; if c1 or + * c2 is NIL, there are no matches + * BATsubrangejoin + * range-join: the right input consists of two aligned BATs, + * values match if the left value is between two corresponding + * right values; two extra Boolean parameters, li and hi, + * indicate whether equal values match + */ + +/* Perform a bunch of sanity checks on the inputs to a join. */ +static gdk_return +joinparamcheck(BAT *l, BAT *r1, BAT *r2, BAT *sl, BAT *sr, const char *func) +{ + if (!BAThdense(l) || !BAThdense(r1) || (r2 && !BAThdense(r2))) { + GDKerror("%s: inputs must have dense head.\n", func); + return GDK_FAIL; + } + if (ATOMtype(l->ttype) != ATOMtype(r1->ttype) || + (r2 && ATOMtype(l->ttype) != ATOMtype(r2->ttype))) { + GDKerror("%s: inputs not compatible.\n", func); + return GDK_FAIL; + } + if (r2 && + (BATcount(r1) != BATcount(r2) || r1->hseqbase != r2->hseqbase)) { + GDKerror("%s: right inputs not aligned.\n", func); + return GDK_FAIL; + } + if ((sl && !BAThdense(sl)) || (sr && !BAThdense(sr))) { + GDKerror("%s: candidate lists must have dense head.\n", func); + return GDK_FAIL; + } + if ((sl && ATOMtype(sl->ttype) != TYPE_oid) || + (sr && ATOMtype(sr->ttype) != TYPE_oid)) { + GDKerror("%s: candidate lists must have OID tail.\n", func); + return GDK_FAIL; + } + if ((sl && !BATtordered(sl)) || + (sr && !BATtordered(sr))) { + GDKerror("%s: candidate lists must be sorted.\n", func); + return GDK_FAIL; + } + if ((sl && !BATtkey(sl)) || + (sr && !BATtkey(sr))) { + GDKerror("%s: candidate lists must be unique.\n", func); + return GDK_FAIL; + } + return GDK_SUCCEED; +} + +/* Create the result bats for a join. */ +static gdk_return +joininitresults(BAT **r1p, BAT **r2p, BUN size, const char *func) +{ + BAT *r1, *r2; + + r1 = BATnew(TYPE_void, TYPE_oid, size, TRANSIENT); + r2 = BATnew(TYPE_void, TYPE_oid, size, TRANSIENT); + if (r1 == NULL || r2 == NULL) { + if (r1) + BBPreclaim(r1); + if (r2) + BBPreclaim(r2); + *r1p = *r2p = NULL; + GDKerror("%s: cannot create output BATs.\n", func); + return GDK_FAIL; + } + BATseqbase(r1, 0); + BATseqbase(r2, 0); + r1->T->nil = 0; + r1->T->nonil = 1; + r1->tkey = 1; + r1->tsorted = 1; + r1->trevsorted = 1; + r1->tdense = 1; + r2->T->nil = 0; + r2->T->nonil = 1; + r2->tkey = 1; + r2->tsorted = 1; + r2->trevsorted = 1; + r2->tdense = 1; + *r1p = r1; + *r2p = r2; + return GDK_SUCCEED; +} + +#define VALUE(s, x) (s##vars ? \ + s##vars + VarHeapVal(s##vals, (x), s##width) : \ + s##vals + ((x) * s##width)) +#define FVALUE(s, x) (s##vals + ((x) * s##width)) + +#define BINSEARCHFUNC(TYPE) \ +static inline BUN \ +binsearch_##TYPE(const oid *rcand, oid offset, const TYPE *rvals, \ + BUN lo, BUN hi, const void *vp, int ordering, int last) \ +{ \ + BUN mid; \ + TYPE v, x; \ + \ + assert(ordering == 1 || ordering == -1); \ + assert(lo <= hi); \ + \ + v = *(const TYPE *) vp; /* value we're searching for */ \ + \ + if (ordering > 0) { \ + if (rcand) { \ + if (last) { \ + if ((x = rvals[rcand[lo] - offset]) > v) \ + return lo; \ + if ((x = rvals[rcand[hi] - offset]) < v || \ + x == v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo <= v < value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[rcand[mid] - offset] > v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } else { \ + if ((x = rvals[rcand[lo] - offset]) > v || \ + x == v) \ + return lo; \ + if ((x = rvals[rcand[hi] - offset]) < v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo < v <= value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[rcand[mid] - offset] >= v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } \ + } else { \ + if (last) { \ + if ((x = rvals[lo]) > v) \ + return lo; \ + if ((x = rvals[hi]) < v || x == v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo <= v < value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[mid] > v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } else { \ + if ((x = rvals[lo]) > v || x == v) \ + return lo; \ + if ((x = rvals[hi]) < v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo < v <= value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[mid] >= v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } \ + } \ + } else { \ + if (rcand) { \ + if (last) { \ + if ((x = rvals[rcand[lo] - offset]) < v) \ + return lo; \ + if ((x = rvals[rcand[hi] - offset]) > v || \ + x == v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo >= v > value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[rcand[mid] - offset] < v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } else { \ + if ((x = rvals[rcand[lo] - offset]) < v || \ + x == v) \ + return lo; \ + if ((x = rvals[rcand[hi] - offset]) > v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo > v >= value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[rcand[mid] - offset] <= v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } \ + } else { \ + if (last) { \ + if ((x = rvals[lo]) < v) \ + return lo; \ + if ((x = rvals[hi]) > v || x == v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo >= v > value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[mid] < v) \ + hi = mid; \ + else \ + lo = mid; \ + } \ + } else { \ + if ((x = rvals[lo]) < v || x == v) \ + return lo; \ + if ((x = rvals[hi]) > v) \ + return hi + 1; \ + \ + /* loop invariant: */ \ + /* value@lo > v >= value@hi */ \ + while (hi - lo > 1) { \ + mid = (hi + lo) / 2; \ + if (rvals[mid] <= v) \ + hi = mid; \ _______________________________________________ checkin-list mailing list [email protected] https://www.monetdb.org/mailman/listinfo/checkin-list
