LCOV - code coverage report
Current view: top level - gdk - gdk_firstn.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 283 568 49.8 %
Date: 2021-09-14 19:48:19 Functions: 5 5 100.0 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : #include "monetdb_config.h"
      10             : #include "gdk.h"
      11             : #include "gdk_private.h"
      12             : #include "gdk_calc_private.h"
      13             : 
      14             : /* BATfirstn select the smallest n elements from the input bat b (if
      15             :  * asc(ending) is set, else the largest n elements).  Conceptually, b
      16             :  * is sorted in ascending or descending order (depending on the asc
      17             :  * argument) and then the OIDs of the first n elements are returned.
      18             :  * If there are NILs in the BAT, their relative ordering is set by
      19             :  * using the nilslast argument: if set, NILs come last (largest value
      20             :  * when ascending, smallest value when descending), so if there are
      21             :  * enough non-NIL values, no NILs will be returned.  If unset (false),
      22             :  * NILs come first and will be returned.
      23             :  *
      24             :  * In addition to the input BAT b, there can be a standard candidate
      25             :  * list s.  If s is specified (non-NULL), only elements in b that are
      26             :  * referred to in s are considered.
      27             :  *
      28             :  * If the third input bat g is non-NULL, then s must also be non-NULL
      29             :  * and must be aligned with g.  G then specifies groups to which the
      30             :  * elements referred to in s belong.  Conceptually, the group values
      31             :  * are sorted in ascending order together with the elements in b that
      32             :  * are referred to in s (in ascending or descending order depending on
      33             :  * asc), and the first n elements are then returned.
      34             :  *
      35             :  * If the output argument gids is NULL, only n elements are returned.
      36             :  * If the output argument gids is non-NULL, more than n elements may
      37             :  * be returned.  If there are duplicate values (if g is given, the
      38             :  * group value counts in determining duplication), all duplicates are
      39             :  * returned.
      40             :  *
      41             :  * If distinct is set, the result contains n complete groups of values
      42             :  * instead of just n values (or slightly more than n if gids is set
      43             :  * since then the "last" group is returned completely).
      44             :  *
      45             :  * Note that BATfirstn can be called in cascading fashion to calculate
      46             :  * the first n values of a table of multiple columns:
      47             :  *      BATfirstn(&s1, &g1, b1, NULL, NULL, n, asc, nilslast, distinct);
      48             :  *      BATfirstn(&s2, &g2, b2, s1, g1, n, asc, nilslast, distinct);
      49             :  *      BATfirstn(&s3, NULL, b3, s2, g2, n, asc, nilslast, distinct);
      50             :  * If the input BATs b1, b2, b3 are large enough, s3 will contain the
      51             :  * OIDs of the smallest (largest) n elements in the table consisting
      52             :  * of the columns b1, b2, b3 when ordered in ascending order with b1
      53             :  * the major key.
      54             :  */
      55             : 
      56             : /* We use a binary heap for the implementation of the simplest form of
      57             :  * first-N.  During processing, the oids list forms a heap with the
      58             :  * root at position 0 and the children of a node at position i at
      59             :  * positions 2*i+1 and 2*i+2.  The parent node is always
      60             :  * smaller/larger (depending on the value of asc) than its children
      61             :  * (recursively).  The heapify macro creates the heap from the input
      62             :  * in-place.  We start off with a heap containing the first N elements
      63             :  * of the input, and then go over the rest of the input, replacing the
      64             :  * root of the heap with a new value if appropriate (if the new value
      65             :  * is among the first-N seen so far).  The siftdown macro then
      66             :  * restores the heap property. */
      67             : #define siftdown(OPER, START, SWAP)                                     \
      68             :         do {                                                            \
      69             :                 pos = (START);                                          \
      70             :                 childpos = (pos << 1) + 1;                                \
      71             :                 while (childpos < n) {                                       \
      72             :                         /* find most extreme child */                   \
      73             :                         if (childpos + 1 < n &&                              \
      74             :                             !(OPER(childpos + 1, childpos)))            \
      75             :                                 childpos++;                             \
      76             :                         /* compare parent with most extreme child */    \
      77             :                         if (!OPER(pos, childpos)) {                     \
      78             :                                 /* already correctly ordered */         \
      79             :                                 break;                                  \
      80             :                         }                                               \
      81             :                         /* exchange parent with child and sift child */ \
      82             :                         /* further */                                   \
      83             :                         SWAP(pos, childpos);                            \
      84             :                         pos = childpos;                                 \
      85             :                         childpos = (pos << 1) + 1;                        \
      86             :                 }                                                       \
      87             :         } while (0)
      88             : 
      89             : #define heapify(OPER, SWAP)                             \
      90             :         do {                                            \
      91             :                 for (i = n / 2; i > 0; i--)          \
      92             :                         siftdown(OPER, i - 1, SWAP);    \
      93             :         } while (0)
      94             : 
      95             : /* we inherit LT and GT from gdk_calc_private.h */
      96             : 
      97             : #define nLTbte(a, b)    (!is_bte_nil(b) && (is_bte_nil(a) || (a) < (b)))
      98             : #define nLTsht(a, b)    (!is_sht_nil(b) && (is_sht_nil(a) || (a) < (b)))
      99             : #define nLTint(a, b)    (!is_int_nil(b) && (is_int_nil(a) || (a) < (b)))
     100             : #define nLTlng(a, b)    (!is_lng_nil(b) && (is_lng_nil(a) || (a) < (b)))
     101             : #define nLThge(a, b)    (!is_hge_nil(b) && (is_hge_nil(a) || (a) < (b)))
     102             : 
     103             : #define nGTbte(a, b)    (!is_bte_nil(b) && (is_bte_nil(a) || (a) > (b)))
     104             : #define nGTsht(a, b)    (!is_sht_nil(b) && (is_sht_nil(a) || (a) > (b)))
     105             : #define nGTint(a, b)    (!is_int_nil(b) && (is_int_nil(a) || (a) > (b)))
     106             : #define nGTlng(a, b)    (!is_lng_nil(b) && (is_lng_nil(a) || (a) > (b)))
     107             : #define nGThge(a, b)    (!is_hge_nil(b) && (is_hge_nil(a) || (a) > (b)))
     108             : 
     109             : #define LTany(p1, p2)   (cmp(BUNtail(bi, oids[p1] - b->hseqbase),    \
     110             :                              BUNtail(bi, oids[p2] - b->hseqbase)) < 0)
     111             : #define GTany(p1, p2)   (cmp(BUNtail(bi, oids[p1] - b->hseqbase),    \
     112             :                              BUNtail(bi, oids[p2] - b->hseqbase)) > 0)
     113             : 
     114             : #define nLTany(p1, p2)  (cmp(BUNtail(bi, oids[p1] - b->hseqbase), nil) != 0 \
     115             :                          && (cmp(BUNtail(bi, oids[p2] - b->hseqbase), nil) == 0      \
     116             :                              || cmp(BUNtail(bi, oids[p1] - b->hseqbase), \
     117             :                                     BUNtail(bi, oids[p2] - b->hseqbase)) < 0))
     118             : #define nGTany(p1, p2)  (cmp(BUNtail(bi, oids[p2] - b->hseqbase), nil) != 0 \
     119             :                          && (cmp(BUNtail(bi, oids[p1] - b->hseqbase), nil) == 0      \
     120             :                              || cmp(BUNtail(bi, oids[p1] - b->hseqbase), \
     121             :                                     BUNtail(bi, oids[p2] - b->hseqbase)) > 0))
     122             : 
     123             : #define LTflt(a, b)     (!is_flt_nil(b) && (is_flt_nil(a) || (a) < (b)))
     124             : #define LTdbl(a, b)     (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) < (b)))
     125             : #define GTflt(a, b)     (!is_flt_nil(a) && (is_flt_nil(b) || (a) > (b)))
     126             : #define GTdbl(a, b)     (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) > (b)))
     127             : 
     128             : #define nLTflt(a, b)    (!is_flt_nil(a) && (is_flt_nil(b) || (a) < (b)))
     129             : #define nLTdbl(a, b)    (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) < (b)))
     130             : #define nGTflt(a, b)    (!is_flt_nil(b) && (is_flt_nil(a) || (a) > (b)))
     131             : #define nGTdbl(a, b)    (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) > (b)))
     132             : 
     133             : #define LTfltfix(p1, p2)        LTflt(vals[oids[p1] - b->hseqbase],  \
     134             :                                       vals[oids[p2] - b->hseqbase])
     135             : #define GTfltfix(p1, p2)        GTflt(vals[oids[p1] - b->hseqbase],  \
     136             :                                       vals[oids[p2] - b->hseqbase])
     137             : #define LTdblfix(p1, p2)        LTdbl(vals[oids[p1] - b->hseqbase],  \
     138             :                                       vals[oids[p2] - b->hseqbase])
     139             : #define GTdblfix(p1, p2)        GTdbl(vals[oids[p1] - b->hseqbase],  \
     140             :                                       vals[oids[p2] - b->hseqbase])
     141             : #define LTfix(p1, p2)           LT(vals[oids[p1] - b->hseqbase],     \
     142             :                                    vals[oids[p2] - b->hseqbase])
     143             : #define GTfix(p1, p2)           GT(vals[oids[p1] - b->hseqbase],     \
     144             :                                    vals[oids[p2] - b->hseqbase])
     145             : 
     146             : #define nLTfltfix(p1, p2)       nLTflt(vals[oids[p1] - b->hseqbase], \
     147             :                                        vals[oids[p2] - b->hseqbase])
     148             : #define nGTfltfix(p1, p2)       nGTflt(vals[oids[p1] - b->hseqbase], \
     149             :                                        vals[oids[p2] - b->hseqbase])
     150             : #define nLTdblfix(p1, p2)       nLTdbl(vals[oids[p1] - b->hseqbase], \
     151             :                                        vals[oids[p2] - b->hseqbase])
     152             : #define nGTdblfix(p1, p2)       nGTdbl(vals[oids[p1] - b->hseqbase], \
     153             :                                        vals[oids[p2] - b->hseqbase])
     154             : #define nLTbtefix(p1, p2)       nLTbte(vals[oids[p1] - b->hseqbase], \
     155             :                                        vals[oids[p2] - b->hseqbase])
     156             : #define nGTbtefix(p1, p2)       nGTbte(vals[oids[p1] - b->hseqbase], \
     157             :                                        vals[oids[p2] - b->hseqbase])
     158             : #define nLTshtfix(p1, p2)       nLTsht(vals[oids[p1] - b->hseqbase], \
     159             :                                        vals[oids[p2] - b->hseqbase])
     160             : #define nGTshtfix(p1, p2)       nGTsht(vals[oids[p1] - b->hseqbase], \
     161             :                                        vals[oids[p2] - b->hseqbase])
     162             : #define nLTintfix(p1, p2)       nLTint(vals[oids[p1] - b->hseqbase], \
     163             :                                        vals[oids[p2] - b->hseqbase])
     164             : #define nGTintfix(p1, p2)       nGTint(vals[oids[p1] - b->hseqbase], \
     165             :                                        vals[oids[p2] - b->hseqbase])
     166             : #define nLTlngfix(p1, p2)       nLTlng(vals[oids[p1] - b->hseqbase], \
     167             :                                        vals[oids[p2] - b->hseqbase])
     168             : #define nGTlngfix(p1, p2)       nGTlng(vals[oids[p1] - b->hseqbase], \
     169             :                                        vals[oids[p2] - b->hseqbase])
     170             : #define nLThgefix(p1, p2)       nLThge(vals[oids[p1] - b->hseqbase], \
     171             :                                        vals[oids[p2] - b->hseqbase])
     172             : #define nGThgefix(p1, p2)       nGThge(vals[oids[p1] - b->hseqbase], \
     173             :                                        vals[oids[p2] - b->hseqbase])
     174             : 
     175             : #define SWAP1(p1, p2)                           \
     176             :         do {                                    \
     177             :                 item = oids[p1];                \
     178             :                 oids[p1] = oids[p2];            \
     179             :                 oids[p2] = item;                \
     180             :         } while (0)
     181             : 
     182             : #define shuffle_unique(TYPE, OP)                                        \
     183             :         do {                                                            \
     184             :                 const TYPE *restrict vals = (const TYPE *) bi.base;     \
     185             :                 heapify(OP##fix, SWAP1);                                \
     186             :                 while (cnt > 0) {                                    \
     187             :                         cnt--;                                          \
     188             :                         i = canditer_next(&ci);                             \
     189             :                         if (OP(vals[i - b->hseqbase],                        \
     190             :                                vals[oids[0] - b->hseqbase])) {               \
     191             :                                 oids[0] = i;                            \
     192             :                                 siftdown(OP##fix, 0, SWAP1);            \
     193             :                         }                                               \
     194             :                 }                                                       \
     195             :         } while (0)
     196             : 
     197             : /* This version of BATfirstn returns a list of N oids (where N is the
     198             :  * smallest among BATcount(b), BATcount(s), and n).  The oids returned
     199             :  * refer to the N smallest/largest (depending on asc) tail values of b
     200             :  * (taking the optional candidate list s into account).  If there are
     201             :  * multiple equal values to take us past N, we return a subset of those.
     202             :  *
     203             :  * If lastp is non-NULL, it is filled in with the oid of the "last"
     204             :  * value, i.e. the value of which there may be multiple occurrences
     205             :  * that are not all included in the first N.
     206             :  */
     207             : static BAT *
     208         597 : BATfirstn_unique(BAT *b, BAT *s, BUN n, bool asc, bool nilslast, oid *lastp, lng t0)
     209             : {
     210             :         BAT *bn;
     211             :         oid *restrict oids;
     212             :         BUN i, cnt;
     213             :         struct canditer ci;
     214         597 :         int tpe = b->ttype;
     215             :         int (*cmp)(const void *, const void *);
     216             :         const void *nil;
     217             :         /* variables used in heapify/siftdown macros */
     218             :         oid item;
     219             :         BUN pos, childpos;
     220             : 
     221         597 :         MT_thread_setalgorithm(__func__);
     222         598 :         cnt = canditer_init(&ci, b, s);
     223             : 
     224         597 :         if (n >= cnt) {
     225             :                 /* trivial: return all candidates */
     226         251 :                 if (lastp)
     227          95 :                         *lastp = 0;
     228         251 :                 bn = canditer_slice(&ci, 0, ci.ncand);
     229         252 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     230             :                           ",n=" BUNFMT " -> " ALGOOPTBATFMT
     231             :                           " (trivial -- " LLFMT " usec)\n",
     232             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
     233             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
     234         252 :                 return bn;
     235             :         }
     236             : 
     237         346 :         if (BATtvoid(b)) {
     238             :                 /* nilslast doesn't make a difference: either all are
     239             :                  * nil, or none are */
     240           0 :                 if (asc || is_oid_nil(b->tseqbase)) {
     241             :                         /* return the first part of the candidate list
     242             :                          * or of the BAT itself */
     243           0 :                         bn = canditer_slice(&ci, 0, n);
     244           0 :                         if (bn && lastp)
     245           0 :                                 *lastp = BUNtoid(bn, n - 1);
     246           0 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     247             :                                   ",n=" BUNFMT " -> " ALGOOPTBATFMT
     248             :                                   " (initial slice -- " LLFMT " usec)\n",
     249             :                                   ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
     250             :                                   ALGOOPTBATPAR(bn), GDKusec() - t0);
     251           0 :                         return bn;
     252             :                 }
     253             :                 /* return the last part of the candidate list or of
     254             :                  * the BAT itself */
     255           0 :                 bn = canditer_slice(&ci, cnt - n, cnt);
     256           0 :                 if (bn && lastp)
     257           0 :                         *lastp = BUNtoid(bn, 0);
     258           0 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     259             :                           ",n=" BUNFMT " -> " ALGOOPTBATFMT
     260             :                           " (final slice -- " LLFMT " usec)\n",
     261             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
     262             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
     263           0 :                 return bn;
     264             :         }
     265             :         /* note, we want to do both calls */
     266         346 :         if (BATordered(b) | BATordered_rev(b)) {
     267             :                 /* trivial: b is sorted so we just need to return the
     268             :                  * initial or final part of it (or of the candidate
     269             :                  * list); however, if nilslast == asc, then the nil
     270             :                  * values (if any) are in the wrong place, so we need
     271             :                  * to do a little more work */
     272             : 
     273             :                 /* after we create the to-be-returned BAT, we set pos
     274             :                  * to the BUN in the new BAT whose value we should
     275             :                  * return through *lastp */
     276         178 :                 if (nilslast == asc && !b->tnonil) {
     277           0 :                         pos = SORTfndlast(b, ATOMnilptr(tpe));
     278           0 :                         pos = canditer_search(&ci, b->hseqbase + pos, true);
     279             :                         /* 0 <= pos <= cnt
     280             :                          * 0 < n < cnt
     281             :                          */
     282           0 :                         if (b->tsorted) {
     283             :                                 /* [0..pos) -- nil
     284             :                                  * [pos..cnt) -- non-nil <<<
     285             :                                  */
     286           0 :                                 if (asc) { /* i.e. nilslast */
     287             :                                         /* prefer non-nil and
     288             :                                          * smallest */
     289           0 :                                         if (cnt - pos < n) {
     290           0 :                                                 bn = canditer_slice(&ci, cnt - n, cnt);
     291             :                                                 pos = 0;
     292             :                                         } else {
     293           0 :                                                 bn = canditer_slice(&ci, pos, pos + n);
     294           0 :                                                 pos = n - 1;
     295             :                                         }
     296             :                                 } else { /* i.e. !asc, !nilslast */
     297             :                                         /* prefer nil and largest */
     298           0 :                                         if (pos < n) {
     299           0 :                                                 bn = canditer_slice2(&ci, 0, pos, cnt - (n - pos), cnt);
     300             :                                                 /* pos = pos; */
     301             :                                         } else {
     302           0 :                                                 bn = canditer_slice(&ci, 0, n);
     303             :                                                 pos = 0;
     304             :                                         }
     305             :                                 }
     306             :                         } else { /* i.e. trevsorted */
     307             :                                 /* [0..pos) -- non-nil >>>
     308             :                                  * [pos..cnt) -- nil
     309             :                                  */
     310           0 :                                 if (asc) { /* i.e. nilslast */
     311             :                                         /* prefer non-nil and
     312             :                                          * smallest */
     313           0 :                                         if (pos < n) {
     314           0 :                                                 bn = canditer_slice(&ci, 0, n);
     315             :                                                 /* pos = pos; */
     316             :                                         } else {
     317           0 :                                                 bn = canditer_slice(&ci, pos - n, pos);
     318             :                                                 pos = 0;
     319             :                                         }
     320             :                                 } else { /* i.e. !asc, !nilslast */
     321             :                                         /* prefer nil and largest */
     322           0 :                                         if (cnt - pos < n) {
     323           0 :                                                 bn = canditer_slice2(&ci, 0, n - (cnt - pos), pos, cnt);
     324           0 :                                                 pos = n - (cnt - pos) - 1;
     325             :                                         } else {
     326           0 :                                                 bn = canditer_slice(&ci, pos, pos + n);
     327             :                                                 pos = 0;
     328             :                                         }
     329             :                                 }
     330             :                         }
     331             :                 } else {
     332             :                         /* either there are no nils, or they are in
     333             :                          * the appropriate position already, so we can
     334             :                          * just slice */
     335         178 :                         if (asc ? b->tsorted : b->trevsorted) {
     336             :                                 /* return copy of first part of
     337             :                                  * candidate list */
     338         157 :                                 bn = canditer_slice(&ci, 0, n);
     339         157 :                                 pos = n - 1;
     340             :                         } else {
     341             :                                 /* return copy of last part of
     342             :                                  * candidate list */
     343          21 :                                 bn = canditer_slice(&ci, cnt - n, cnt);
     344             :                                 pos = 0;
     345             :                         }
     346             :                 }
     347         178 :                 if (bn && lastp)
     348          72 :                         *lastp = BUNtoid(bn, pos);
     349         178 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     350             :                           ",n=" BUNFMT " -> " ALGOOPTBATFMT
     351             :                           " (ordered -- " LLFMT " usec)\n",
     352             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
     353             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
     354         178 :                 return bn;
     355             :         }
     356             : 
     357         168 :         bn = COLnew(0, TYPE_oid, n, TRANSIENT);
     358         168 :         if (bn == NULL)
     359             :                 return NULL;
     360         168 :         BATsetcount(bn, n);
     361         168 :         oids = (oid *) Tloc(bn, 0);
     362         168 :         cmp = ATOMcompare(tpe);
     363         168 :         nil = ATOMnilptr(tpe);
     364             :         /* if base type has same comparison function as type itself, we
     365             :          * can use the base type */
     366         168 :         tpe = ATOMbasetype(tpe); /* takes care of oid */
     367             :         /* if the input happens to be almost sorted in ascending order
     368             :          * (likely a common use case), it is more efficient to start
     369             :          * off with the first n elements when doing a firstn-ascending
     370             :          * and to start off with the last n elements when doing a
     371             :          * firstn-descending so that most values that we look at after
     372             :          * this will be skipped.  However, when using a bitmask
     373             :          * candidate list, the manipulation of the canditer structure
     374             :          * doesn't work like this, so we still work from the
     375             :          * beginning. */
     376         168 :         if (asc || ci.tpe == cand_mask) {
     377        8706 :                 for (i = 0; i < n; i++)
     378        8597 :                         oids[i] = canditer_next(&ci);
     379             :         } else {
     380          59 :                 item = canditer_idx(&ci, cnt - n);
     381          59 :                 ci.next = cnt - n;
     382          59 :                 ci.add = item - ci.seq - (cnt - n);
     383         531 :                 for (i = n; i > 0; i--)
     384         472 :                         oids[i - 1] = canditer_next(&ci);
     385          59 :                 canditer_reset(&ci);
     386             :         }
     387         168 :         cnt -= n;
     388             : 
     389         168 :         BATiter bi = bat_iterator(b);
     390             : 
     391         168 :         if (asc) {
     392         109 :                 if (nilslast && !b->tnonil) {
     393           0 :                         switch (tpe) {
     394           0 :                         case TYPE_bte:
     395           0 :                                 shuffle_unique(bte, nLTbte);
     396             :                                 break;
     397           0 :                         case TYPE_sht:
     398           0 :                                 shuffle_unique(sht, nLTsht);
     399             :                                 break;
     400           0 :                         case TYPE_int:
     401           0 :                                 shuffle_unique(int, nLTint);
     402             :                                 break;
     403           0 :                         case TYPE_lng:
     404           0 :                                 shuffle_unique(lng, nLTlng);
     405             :                                 break;
     406             : #ifdef HAVE_HGE
     407           0 :                         case TYPE_hge:
     408           0 :                                 shuffle_unique(hge, nLThge);
     409             :                                 break;
     410             : #endif
     411           0 :                         case TYPE_flt:
     412           0 :                                 shuffle_unique(flt, nLTflt);
     413             :                                 break;
     414           0 :                         case TYPE_dbl:
     415           0 :                                 shuffle_unique(dbl, nLTdbl);
     416             :                                 break;
     417           0 :                         default:
     418           0 :                                 heapify(nLTany, SWAP1);
     419           0 :                                 while (cnt > 0) {
     420           0 :                                         cnt--;
     421           0 :                                         i = canditer_next(&ci);
     422           0 :                                         if (cmp(BUNtail(bi, i - b->hseqbase), nil) != 0
     423           0 :                                             && (cmp(BUNtail(bi, oids[0] - b->hseqbase), nil) == 0
     424           0 :                                                 || cmp(BUNtail(bi, i - b->hseqbase),
     425           0 :                                                        BUNtail(bi, oids[0] - b->hseqbase)) < 0)) {
     426           0 :                                                 oids[0] = i;
     427           0 :                                                 siftdown(nLTany, 0, SWAP1);
     428             :                                         }
     429             :                                 }
     430             :                                 break;
     431             :                         }
     432             :                 } else {
     433         109 :                         switch (tpe) {
     434           0 :                         case TYPE_bte:
     435           0 :                                 shuffle_unique(bte, LT);
     436             :                                 break;
     437           0 :                         case TYPE_sht:
     438           0 :                                 shuffle_unique(sht, LT);
     439             :                                 break;
     440          36 :                         case TYPE_int:
     441        7370 :                                 shuffle_unique(int, LT);
     442             :                                 break;
     443           2 :                         case TYPE_lng:
     444        3571 :                                 shuffle_unique(lng, LT);
     445             :                                 break;
     446             : #ifdef HAVE_HGE
     447           8 :                         case TYPE_hge:
     448      101653 :                                 shuffle_unique(hge, LT);
     449             :                                 break;
     450             : #endif
     451           0 :                         case TYPE_flt:
     452           0 :                                 shuffle_unique(flt, LTflt);
     453             :                                 break;
     454          14 :                         case TYPE_dbl:
     455       94124 :                                 shuffle_unique(dbl, LTdbl);
     456             :                                 break;
     457          49 :                         default:
     458        6034 :                                 heapify(LTany, SWAP1);
     459      137886 :                                 while (cnt > 0) {
     460      137837 :                                         cnt--;
     461      137837 :                                         i = canditer_next(&ci);
     462      138215 :                                         if (cmp(BUNtail(bi, i - b->hseqbase),
     463      138005 :                                                 BUNtail(bi, oids[0] - b->hseqbase)) < 0) {
     464        6528 :                                                 oids[0] = i;
     465       40272 :                                                 siftdown(LTany, 0, SWAP1);
     466             :                                         }
     467             :                                 }
     468             :                                 break;
     469             :                         }
     470             :                 }
     471             :         } else {
     472          59 :                 if (nilslast || b->tnonil) {
     473          59 :                         switch (tpe) {
     474           0 :                         case TYPE_bte:
     475           0 :                                 shuffle_unique(bte, GT);
     476             :                                 break;
     477           0 :                         case TYPE_sht:
     478           0 :                                 shuffle_unique(sht, GT);
     479             :                                 break;
     480          24 :                         case TYPE_int:
     481         192 :                                 shuffle_unique(int, GT);
     482             :                                 break;
     483           1 :                         case TYPE_lng:
     484        2139 :                                 shuffle_unique(lng, GT);
     485             :                                 break;
     486             : #ifdef HAVE_HGE
     487          26 :                         case TYPE_hge:
     488        1493 :                                 shuffle_unique(hge, GT);
     489             :                                 break;
     490             : #endif
     491           0 :                         case TYPE_flt:
     492           0 :                                 shuffle_unique(flt, GTflt);
     493             :                                 break;
     494           0 :                         case TYPE_dbl:
     495           0 :                                 shuffle_unique(dbl, GTdbl);
     496             :                                 break;
     497           8 :                         default:
     498          45 :                                 heapify(GTany, SWAP1);
     499          37 :                                 while (cnt > 0) {
     500          29 :                                         cnt--;
     501          29 :                                         i = canditer_next(&ci);
     502          29 :                                         if (cmp(BUNtail(bi, i - b->hseqbase),
     503          29 :                                                 BUNtail(bi, oids[0] - b->hseqbase)) > 0) {
     504          17 :                                                 oids[0] = i;
     505          42 :                                                 siftdown(GTany, 0, SWAP1);
     506             :                                         }
     507             :                                 }
     508             :                                 break;
     509             :                         }
     510             :                 } else {
     511           0 :                         switch (tpe) {
     512           0 :                         case TYPE_bte:
     513           0 :                                 shuffle_unique(bte, nGTbte);
     514             :                                 break;
     515           0 :                         case TYPE_sht:
     516           0 :                                 shuffle_unique(sht, nGTsht);
     517             :                                 break;
     518           0 :                         case TYPE_int:
     519           0 :                                 shuffle_unique(int, nGTint);
     520             :                                 break;
     521           0 :                         case TYPE_lng:
     522           0 :                                 shuffle_unique(lng, nGTlng);
     523             :                                 break;
     524             : #ifdef HAVE_HGE
     525           0 :                         case TYPE_hge:
     526           0 :                                 shuffle_unique(hge, nGThge);
     527             :                                 break;
     528             : #endif
     529           0 :                         case TYPE_flt:
     530           0 :                                 shuffle_unique(flt, nGTflt);
     531             :                                 break;
     532           0 :                         case TYPE_dbl:
     533           0 :                                 shuffle_unique(dbl, nGTdbl);
     534             :                                 break;
     535           0 :                         default:
     536           0 :                                 heapify(nGTany, SWAP1);
     537           0 :                                 while (cnt > 0) {
     538           0 :                                         cnt--;
     539           0 :                                         i = canditer_next(&ci);
     540           0 :                                         if (cmp(BUNtail(bi, oids[0] - b->hseqbase), nil) != 0
     541           0 :                                             && (cmp(BUNtail(bi, i - b->hseqbase), nil) == 0
     542           0 :                                                 || cmp(BUNtail(bi, i - b->hseqbase),
     543           0 :                                                        BUNtail(bi, oids[0] - b->hseqbase)) > 0)) {
     544           0 :                                                 oids[0] = i;
     545           0 :                                                 siftdown(nGTany, 0, SWAP1);
     546             :                                         }
     547             :                                 }
     548             :                                 break;
     549             :                         }
     550             :                 }
     551             :         }
     552         168 :         bat_iterator_end(&bi);
     553         168 :         if (lastp)
     554          85 :                 *lastp = oids[0]; /* store id of largest value */
     555             :         /* output must be sorted since it's a candidate list */
     556         168 :         GDKqsort(oids, NULL, NULL, (size_t) n, sizeof(oid), 0, TYPE_oid, false, false);
     557         168 :         bn->tsorted = true;
     558         168 :         bn->trevsorted = n <= 1;
     559         168 :         bn->tkey = true;
     560         168 :         bn->tseqbase = n <= 1 ? oids[0] : oid_nil;
     561         168 :         bn->tnil = false;
     562         168 :         bn->tnonil = true;
     563         168 :         bn = virtualize(bn);
     564         167 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     565             :                   ",n=" BUNFMT " -> " ALGOOPTBATFMT
     566             :                   " (" LLFMT " usec)\n",
     567             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
     568             :                   ALGOOPTBATPAR(bn), GDKusec() - t0);
     569             :         return bn;
     570             : }
     571             : 
     572             : #define LTfixgrp(p1, p2)                        \
     573             :         (goids[p1] < goids[p2] ||            \
     574             :          (goids[p1] == goids[p2] &&             \
     575             :           LTfix(p1, p2)))
     576             : #define nLTbtefixgrp(p1, p2)                    \
     577             :         (goids[p1] < goids[p2] ||            \
     578             :          (goids[p1] == goids[p2] &&             \
     579             :           nLTbtefix(p1, p2)))
     580             : #define nLTshtfixgrp(p1, p2)                    \
     581             :         (goids[p1] < goids[p2] ||            \
     582             :          (goids[p1] == goids[p2] &&             \
     583             :           nLTshtfix(p1, p2)))
     584             : #define nLTintfixgrp(p1, p2)                    \
     585             :         (goids[p1] < goids[p2] ||            \
     586             :          (goids[p1] == goids[p2] &&             \
     587             :           nLTintfix(p1, p2)))
     588             : #define nLTlngfixgrp(p1, p2)                    \
     589             :         (goids[p1] < goids[p2] ||            \
     590             :          (goids[p1] == goids[p2] &&             \
     591             :           nLTlngfix(p1, p2)))
     592             : #define nLThgefixgrp(p1, p2)                    \
     593             :         (goids[p1] < goids[p2] ||            \
     594             :          (goids[p1] == goids[p2] &&             \
     595             :           nLThgefix(p1, p2)))
     596             : #define LTfltfixgrp(p1, p2)                     \
     597             :         (goids[p1] < goids[p2] ||            \
     598             :          (goids[p1] == goids[p2] &&             \
     599             :           LTfltfix(p1, p2)))
     600             : #define LTdblfixgrp(p1, p2)                     \
     601             :         (goids[p1] < goids[p2] ||            \
     602             :          (goids[p1] == goids[p2] &&             \
     603             :           LTdblfix(p1, p2)))
     604             : #define nLTfltfixgrp(p1, p2)                    \
     605             :         (goids[p1] < goids[p2] ||            \
     606             :          (goids[p1] == goids[p2] &&             \
     607             :           nLTfltfix(p1, p2)))
     608             : #define nLTdblfixgrp(p1, p2)                    \
     609             :         (goids[p1] < goids[p2] ||            \
     610             :          (goids[p1] == goids[p2] &&             \
     611             :           nLTdblfix(p1, p2)))
     612             : #define GTfixgrp(p1, p2)                        \
     613             :         (goids[p1] < goids[p2] ||            \
     614             :          (goids[p1] == goids[p2] &&             \
     615             :           GTfix(p1, p2)))
     616             : #define nGTbtefixgrp(p1, p2)                    \
     617             :         (goids[p1] < goids[p2] ||            \
     618             :          (goids[p1] == goids[p2] &&             \
     619             :           nGTbtefix(p1, p2)))
     620             : #define nGTshtfixgrp(p1, p2)                    \
     621             :         (goids[p1] < goids[p2] ||            \
     622             :          (goids[p1] == goids[p2] &&             \
     623             :           nGTshtfix(p1, p2)))
     624             : #define nGTintfixgrp(p1, p2)                    \
     625             :         (goids[p1] < goids[p2] ||            \
     626             :          (goids[p1] == goids[p2] &&             \
     627             :           nGTintfix(p1, p2)))
     628             : #define nGTlngfixgrp(p1, p2)                    \
     629             :         (goids[p1] < goids[p2] ||            \
     630             :          (goids[p1] == goids[p2] &&             \
     631             :           nGTlngfix(p1, p2)))
     632             : #define nGThgefixgrp(p1, p2)                    \
     633             :         (goids[p1] < goids[p2] ||            \
     634             :          (goids[p1] == goids[p2] &&             \
     635             :           nGThgefix(p1, p2)))
     636             : #define GTfltfixgrp(p1, p2)                     \
     637             :         (goids[p1] < goids[p2] ||            \
     638             :          (goids[p1] == goids[p2] &&             \
     639             :           GTfltfix(p1, p2)))
     640             : #define GTdblfixgrp(p1, p2)                     \
     641             :         (goids[p1] < goids[p2] ||            \
     642             :          (goids[p1] == goids[p2] &&             \
     643             :           GTdblfix(p1, p2)))
     644             : #define nGTfltfixgrp(p1, p2)                    \
     645             :         (goids[p1] < goids[p2] ||            \
     646             :          (goids[p1] == goids[p2] &&             \
     647             :           nGTfltfix(p1, p2)))
     648             : #define nGTdblfixgrp(p1, p2)                    \
     649             :         (goids[p1] < goids[p2] ||            \
     650             :          (goids[p1] == goids[p2] &&             \
     651             :           nGTdblfix(p1, p2)))
     652             : #define LTvoidgrp(p1, p2)                                       \
     653             :         (goids[p1] < goids[p2] ||                            \
     654             :          (goids[p1] == goids[p2] && oids[p1] < oids[p2]))
     655             : #define GTvoidgrp(p1, p2)                                       \
     656             :         (goids[p1] < goids[p2] ||                            \
     657             :          (goids[p1] == goids[p2] && oids[p1] > oids[p2]))
     658             : #define LTanygrp(p1, p2)                        \
     659             :         (goids[p1] < goids[p2] ||            \
     660             :          (goids[p1] == goids[p2] &&             \
     661             :           LTany(p1, p2)))
     662             : #define GTanygrp(p1, p2)                        \
     663             :         (goids[p1] < goids[p2] ||            \
     664             :          (goids[p1] == goids[p2] &&             \
     665             :           GTany(p1, p2)))
     666             : #define nLTanygrp(p1, p2)                       \
     667             :         (goids[p1] < goids[p2] ||            \
     668             :          (goids[p1] == goids[p2] &&             \
     669             :           nLTany(p1, p2)))
     670             : #define nGTanygrp(p1, p2)                       \
     671             :         (goids[p1] < goids[p2] ||            \
     672             :          (goids[p1] == goids[p2] &&             \
     673             :           nGTany(p1, p2)))
     674             : #define SWAP2(p1, p2)                           \
     675             :         do {                                    \
     676             :                 item = oids[p1];                \
     677             :                 oids[p1] = oids[p2];            \
     678             :                 oids[p2] = item;                \
     679             :                 item = goids[p1];               \
     680             :                 goids[p1] = goids[p2];          \
     681             :                 goids[p2] = item;               \
     682             :         } while (0)
     683             : 
     684             : #define shuffle_unique_with_groups(TYPE, OP)                            \
     685             :         do {                                                            \
     686             :                 const TYPE *restrict vals = (const TYPE *) bi.base;     \
     687             :                 heapify(OP##fixgrp, SWAP2);                             \
     688             :                 while (cnt > 0) {                                    \
     689             :                         cnt--;                                          \
     690             :                         i = canditer_next(&ci);                             \
     691             :                         if (gv[j] < goids[0] ||                              \
     692             :                             (gv[j] == goids[0] &&                       \
     693             :                              OP(vals[i - b->hseqbase],                       \
     694             :                                 vals[oids[0] - b->hseqbase]))) {     \
     695             :                                 oids[0] = i;                            \
     696             :                                 goids[0] = gv[j];                       \
     697             :                                 siftdown(OP##fixgrp, 0, SWAP2);         \
     698             :                         }                                               \
     699             :                         j++;                                            \
     700             :                 }                                                       \
     701             :         } while (0)
     702             : 
     703             : /* This version of BATfirstn is like the one above, except that it
     704             :  * also looks at groups.  The values of the group IDs are important:
     705             :  * we return only the smallest N (i.e., not dependent on asc which
     706             :  * refers only to the values in the BAT b).
     707             :  *
     708             :  * If lastp is non-NULL, it is filled in with the oid of the "last"
     709             :  * value, i.e. the value of which there may be multiple occurrences
     710             :  * that are not all included in the first N.  If lastgp is non-NULL,
     711             :  * it is filled with the group ID (not the oid of the group ID) for
     712             :  * that same value.
     713             :  */
     714             : static BAT *
     715         549 : BATfirstn_unique_with_groups(BAT *b, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, oid *lastp, oid *lastgp, lng t0)
     716             : {
     717             :         BAT *bn;
     718             :         oid *restrict oids, *restrict goids;
     719             :         const oid *restrict gv;
     720             :         BUN i, j, cnt;
     721             :         struct canditer ci;
     722         549 :         int tpe = b->ttype;
     723             :         int (*cmp)(const void *, const void *);
     724             :         const void *nil;
     725             :         /* variables used in heapify/siftdown macros */
     726             :         oid item;
     727             :         BUN pos, childpos;
     728             : 
     729         549 :         MT_thread_setalgorithm(__func__);
     730         549 :         cnt = canditer_init(&ci, b, s);
     731             : 
     732             :         if (n > cnt)
     733             :                 n = cnt;
     734             : 
     735         549 :         if (n == 0) {
     736             :                 /* candidate list might refer only to values outside
     737             :                  * of the bat and hence be effectively empty */
     738           0 :                 if (lastp)
     739           0 :                         *lastp = 0;
     740           0 :                 if (lastgp)
     741           0 :                         *lastgp = 0;
     742           0 :                 bn = BATdense(0, 0, 0);
     743           0 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     744             :                           ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
     745             :                           " (empty -- " LLFMT " usec)\n",
     746             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
     747             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
     748           0 :                 return bn;
     749             :         }
     750             : 
     751         549 :         if (BATtdense(g)) {
     752             :                 /* trivial: g determines ordering, return reference to
     753             :                  * initial part of b (or slice of s) */
     754          82 :                 if (lastgp)
     755          36 :                         *lastgp = g->tseqbase + n - 1;
     756          82 :                 bn = canditer_slice(&ci, 0, n);
     757          81 :                 if (bn && lastp)
     758          36 :                         *lastp = BUNtoid(bn, n - 1);
     759          81 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     760             :                           ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
     761             :                           " (dense group -- " LLFMT " usec)\n",
     762             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
     763             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
     764          81 :                 return bn;
     765             :         }
     766             : 
     767         467 :         bn = COLnew(0, TYPE_oid, n, TRANSIENT);
     768         467 :         if (bn == NULL)
     769             :                 return NULL;
     770         467 :         BATsetcount(bn, n);
     771         467 :         oids = (oid *) Tloc(bn, 0);
     772         467 :         gv = (const oid *) Tloc(g, 0);
     773         467 :         goids = GDKmalloc(n * sizeof(oid));
     774         467 :         if (goids == NULL) {
     775           0 :                 BBPreclaim(bn);
     776           0 :                 return NULL;
     777             :         }
     778             : 
     779         467 :         cmp = ATOMcompare(tpe);
     780         467 :         nil = ATOMnilptr(tpe);
     781             :         /* if base type has same comparison function as type itself, we
     782             :          * can use the base type */
     783         467 :         tpe = ATOMbasetype(tpe); /* takes care of oid */
     784             :         j = 0;
     785       31521 :         for (i = 0; i < n; i++) {
     786       31054 :                 oids[i] = canditer_next(&ci);
     787       31054 :                 goids[i] = gv[j++];
     788             :         }
     789         467 :         cnt -= n;
     790             : 
     791         467 :         BATiter bi = bat_iterator(b);
     792         467 :         if (BATtvoid(b)) {
     793             :                 /* nilslast doesn't make a difference (all nil, or no nil) */
     794           0 :                 if (asc) {
     795           0 :                         heapify(LTvoidgrp, SWAP2);
     796           0 :                         while (cnt > 0) {
     797           0 :                                 cnt--;
     798           0 :                                 i = canditer_next(&ci);
     799           0 :                                 if (gv[j] < goids[0]
     800             :                                     /* || (gv[j] == goids[0]
     801             :                                         && i < oids[0]) -- always false */) {
     802           0 :                                         oids[0] = i;
     803           0 :                                         goids[0] = gv[j];
     804           0 :                                         siftdown(LTvoidgrp, 0, SWAP2);
     805             :                                 }
     806           0 :                                 j++;
     807             :                         }
     808             :                 } else {
     809           0 :                         heapify(GTvoidgrp, SWAP2);
     810           0 :                         while (cnt > 0) {
     811           0 :                                 cnt--;
     812           0 :                                 i = canditer_next(&ci);
     813           0 :                                 if (gv[j] < goids[0]
     814           0 :                                     || (gv[j] == goids[0]
     815             :                                         /* && i > oids[0] -- always true */)) {
     816           0 :                                         oids[0] = i;
     817           0 :                                         goids[0] = gv[j];
     818           0 :                                         siftdown(GTvoidgrp, 0, SWAP2);
     819             :                                 }
     820           0 :                                 j++;
     821             :                         }
     822             :                 }
     823         467 :         } else if (asc) {
     824         442 :                 if (nilslast && !b->tnonil) {
     825           0 :                         switch (tpe) {
     826           0 :                         case TYPE_bte:
     827           0 :                                 shuffle_unique_with_groups(bte, nLTbte);
     828             :                                 break;
     829           0 :                         case TYPE_sht:
     830           0 :                                 shuffle_unique_with_groups(sht, nLTsht);
     831             :                                 break;
     832           0 :                         case TYPE_int:
     833           0 :                                 shuffle_unique_with_groups(int, nLTint);
     834             :                                 break;
     835           0 :                         case TYPE_lng:
     836           0 :                                 shuffle_unique_with_groups(lng, nLTlng);
     837             :                                 break;
     838             : #ifdef HAVE_HGE
     839           0 :                         case TYPE_hge:
     840           0 :                                 shuffle_unique_with_groups(hge, nLThge);
     841             :                                 break;
     842             : #endif
     843           0 :                         case TYPE_flt:
     844           0 :                                 shuffle_unique_with_groups(flt, nLTflt);
     845             :                                 break;
     846           0 :                         case TYPE_dbl:
     847           0 :                                 shuffle_unique_with_groups(dbl, nLTdbl);
     848             :                                 break;
     849           0 :                         default:
     850           0 :                                 heapify(nLTanygrp, SWAP2);
     851           0 :                                 while (cnt > 0) {
     852           0 :                                         cnt--;
     853           0 :                                         i = canditer_next(&ci);
     854           0 :                                         if (gv[j] < goids[0]
     855           0 :                                             || (gv[j] == goids[0]
     856           0 :                                                 && cmp(BUNtail(bi, i - b->hseqbase), nil) != 0
     857           0 :                                                 && (cmp(BUNtail(bi, oids[0] - b->hseqbase), nil) == 0
     858           0 :                                                     || cmp(BUNtail(bi, i - b->hseqbase),
     859           0 :                                                            BUNtail(bi, oids[0] - b->hseqbase)) < 0))) {
     860           0 :                                                 oids[0] = i;
     861           0 :                                                 goids[0] = gv[j];
     862           0 :                                                 siftdown(nLTanygrp, 0, SWAP2);
     863             :                                         }
     864           0 :                                         j++;
     865             :                                 }
     866             :                                 break;
     867             :                         }
     868             :                 } else {
     869         442 :                         switch (tpe) {
     870           2 :                         case TYPE_bte:
     871          15 :                                 shuffle_unique_with_groups(bte, LT);
     872             :                                 break;
     873           2 :                         case TYPE_sht:
     874          28 :                                 shuffle_unique_with_groups(sht, LT);
     875             :                                 break;
     876         159 :                         case TYPE_int:
     877       37321 :                                 shuffle_unique_with_groups(int, LT);
     878             :                                 break;
     879           2 :                         case TYPE_lng:
     880          15 :                                 shuffle_unique_with_groups(lng, LT);
     881             :                                 break;
     882             : #ifdef HAVE_HGE
     883          27 :                         case TYPE_hge:
     884        2495 :                                 shuffle_unique_with_groups(hge, LT);
     885             :                                 break;
     886             : #endif
     887           0 :                         case TYPE_flt:
     888           0 :                                 shuffle_unique_with_groups(flt, LTflt);
     889             :                                 break;
     890           4 :                         case TYPE_dbl:
     891          15 :                                 shuffle_unique_with_groups(dbl, LTdbl);
     892             :                                 break;
     893         246 :                         default:
     894       27842 :                                 heapify(LTanygrp, SWAP2);
     895       27417 :                                 while (cnt > 0) {
     896       27171 :                                         cnt--;
     897       27171 :                                         i = canditer_next(&ci);
     898       27174 :                                         if (gv[j] < goids[0] ||
     899       26815 :                                             (gv[j] == goids[0] &&
     900       26816 :                                              cmp(BUNtail(bi, i - b->hseqbase),
     901       26819 :                                                  BUNtail(bi, oids[0] - b->hseqbase)) < 0)) {
     902        4434 :                                                 oids[0] = i;
     903        4434 :                                                 goids[0] = gv[j];
     904       27571 :                                                 siftdown(LTanygrp, 0, SWAP2);
     905             :                                         }
     906       27171 :                                         j++;
     907             :                                 }
     908             :                                 break;
     909             :                         }
     910             :                 }
     911          25 :         } else if (nilslast || b->tnonil) {
     912          25 :                 switch (tpe) {
     913           0 :                 case TYPE_bte:
     914           0 :                         shuffle_unique_with_groups(bte, GT);
     915             :                         break;
     916           0 :                 case TYPE_sht:
     917           0 :                         shuffle_unique_with_groups(sht, GT);
     918             :                         break;
     919           8 :                 case TYPE_int:
     920          35 :                         shuffle_unique_with_groups(int, GT);
     921             :                         break;
     922           0 :                 case TYPE_lng:
     923           0 :                         shuffle_unique_with_groups(lng, GT);
     924             :                         break;
     925             : #ifdef HAVE_HGE
     926           5 :                 case TYPE_hge:
     927         721 :                         shuffle_unique_with_groups(hge, GT);
     928             :                         break;
     929             : #endif
     930           0 :                 case TYPE_flt:
     931           0 :                         shuffle_unique_with_groups(flt, GTflt);
     932             :                         break;
     933           1 :                 case TYPE_dbl:
     934          12 :                         shuffle_unique_with_groups(dbl, GTdbl);
     935             :                         break;
     936          11 :                 default:
     937          58 :                         heapify(GTanygrp, SWAP2);
     938          14 :                         while (cnt > 0) {
     939           3 :                                 cnt--;
     940           3 :                                 i = canditer_next(&ci);
     941           3 :                                 if (gv[j] < goids[0] ||
     942           2 :                                     (gv[j] == goids[0] &&
     943           2 :                                      cmp(BUNtail(bi, i - b->hseqbase),
     944           2 :                                          BUNtail(bi, oids[0] - b->hseqbase)) > 0)) {
     945           1 :                                         oids[0] = i;
     946           1 :                                         goids[0] = gv[j];
     947           2 :                                         siftdown(GTanygrp, 0, SWAP2);
     948             :                                 }
     949           3 :                                 j++;
     950             :                         }
     951             :                         break;
     952             :                 }
     953             :         } else {
     954           0 :                 switch (tpe) {
     955           0 :                 case TYPE_bte:
     956           0 :                         shuffle_unique_with_groups(bte, nGTbte);
     957             :                         break;
     958           0 :                 case TYPE_sht:
     959           0 :                         shuffle_unique_with_groups(sht, nGTsht);
     960             :                         break;
     961           0 :                 case TYPE_int:
     962           0 :                         shuffle_unique_with_groups(int, nGTint);
     963             :                         break;
     964           0 :                 case TYPE_lng:
     965           0 :                         shuffle_unique_with_groups(lng, nGTlng);
     966             :                         break;
     967             : #ifdef HAVE_HGE
     968           0 :                 case TYPE_hge:
     969           0 :                         shuffle_unique_with_groups(hge, nGThge);
     970             :                         break;
     971             : #endif
     972           0 :                 case TYPE_flt:
     973           0 :                         shuffle_unique_with_groups(flt, nGTflt);
     974             :                         break;
     975           0 :                 case TYPE_dbl:
     976           0 :                         shuffle_unique_with_groups(dbl, nGTdbl);
     977             :                         break;
     978           0 :                 default:
     979           0 :                         heapify(nGTanygrp, SWAP2);
     980           0 :                         while (cnt > 0) {
     981           0 :                                 cnt--;
     982           0 :                                 i = canditer_next(&ci);
     983           0 :                                 if (gv[j] < goids[0]
     984           0 :                                     || (gv[j] == goids[0]
     985           0 :                                         && cmp(BUNtail(bi, oids[0] - b->hseqbase), nil) != 0
     986           0 :                                         && (cmp(BUNtail(bi, i - b->hseqbase), nil) == 0
     987           0 :                                             || cmp(BUNtail(bi, i - b->hseqbase),
     988           0 :                                                    BUNtail(bi, oids[0] - b->hseqbase)) > 0))) {
     989           0 :                                         oids[0] = i;
     990           0 :                                         goids[0] = gv[j];
     991           0 :                                         siftdown(nGTanygrp, 0, SWAP2);
     992             :                                 }
     993           0 :                                 j++;
     994             :                         }
     995             :                         break;
     996             :                 }
     997             :         }
     998         467 :         bat_iterator_end(&bi);
     999         467 :         if (lastp)
    1000         277 :                 *lastp = oids[0];
    1001         467 :         if (lastgp)
    1002         277 :                 *lastgp = goids[0];
    1003         467 :         GDKfree(goids);
    1004             :         /* output must be sorted since it's a candidate list */
    1005         467 :         GDKqsort(oids, NULL, NULL, (size_t) n, sizeof(oid), 0, TYPE_oid, false, false);
    1006         467 :         bn->tsorted = true;
    1007         467 :         bn->trevsorted = n <= 1;
    1008         467 :         bn->tkey = true;
    1009         467 :         bn->tseqbase = n <= 1 ? oids[0] : oid_nil;
    1010         467 :         bn->tnil = false;
    1011         467 :         bn->tnonil = true;
    1012         467 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1013             :                   ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
    1014             :                   " (" LLFMT " usec)\n",
    1015             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
    1016             :                   ALGOOPTBATPAR(bn), GDKusec() - t0);
    1017             :         return bn;
    1018             : }
    1019             : 
    1020             : static gdk_return
    1021         252 : BATfirstn_grouped(BAT **topn, BAT **gids, BAT *b, BAT *s, BUN n, bool asc, bool nilslast, bool distinct, lng t0)
    1022             : {
    1023             :         BAT *bn, *gn = NULL, *su = NULL;
    1024             :         oid last;
    1025             :         gdk_return rc;
    1026             : 
    1027         252 :         MT_thread_setalgorithm(__func__);
    1028         252 :         if (distinct && !b->tkey) {
    1029             :                 su = s;
    1030           0 :                 s = BATunique(b, s);
    1031           0 :                 if (s == NULL)
    1032             :                         return GDK_FAIL;
    1033             :         }
    1034         252 :         bn = BATfirstn_unique(b, s, n, asc, nilslast, &last, t0);
    1035         252 :         if (bn == NULL)
    1036             :                 return GDK_FAIL;
    1037         252 :         if (BATcount(bn) == 0) {
    1038           0 :                 if (gids) {
    1039           0 :                         gn = BATdense(0, 0, 0);
    1040           0 :                         if (gn == NULL) {
    1041           0 :                                 BBPunfix(bn->batCacheid);
    1042           0 :                                 return GDK_FAIL;
    1043             :                         }
    1044           0 :                         *gids = gn;
    1045             :                 }
    1046           0 :                 *topn = bn;
    1047           0 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1048             :                           ",n=" BUNFMT " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
    1049             :                           " (empty -- " LLFMT " usec)\n",
    1050             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
    1051             :                           ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
    1052           0 :                 return GDK_SUCCEED;
    1053             :         }
    1054         252 :         if (!b->tkey) {
    1055         204 :                 if (distinct) {
    1056             :                         BAT *bn1;
    1057             : 
    1058             :                         bn1 = bn;
    1059           0 :                         BBPunfix(s->batCacheid);
    1060           0 :                         bn = BATintersect(b, b, su, bn1, true, false, BUN_NONE);
    1061           0 :                         BBPunfix(bn1->batCacheid);
    1062           0 :                         if (bn == NULL)
    1063             :                                 return GDK_FAIL;
    1064             :                 } else {
    1065         204 :                         BATiter bi = bat_iterator(b);
    1066             :                         BAT *bn1, *bn2;
    1067             : 
    1068             :                         bn1 = bn;
    1069         204 :                         bn2 = BATselect(b, s, BUNtail(bi, last - b->hseqbase), NULL, true, false, false);
    1070         203 :                         bat_iterator_end(&bi);
    1071         203 :                         if (bn2 == NULL) {
    1072           0 :                                 BBPunfix(bn1->batCacheid);
    1073           0 :                                 return GDK_FAIL;
    1074             :                         }
    1075         203 :                         bn = BATmergecand(bn1, bn2);
    1076         203 :                         BBPunfix(bn1->batCacheid);
    1077         204 :                         BBPunfix(bn2->batCacheid);
    1078         204 :                         if (bn == NULL)
    1079             :                                 return GDK_FAIL;
    1080             :                 }
    1081             :         }
    1082         252 :         if (gids) {
    1083             :                 BAT *bn1, *bn2, *bn3, *bn4;
    1084         252 :                 bn1 = BATproject(bn, b);
    1085         252 :                 if (bn1 == NULL) {
    1086           0 :                         BBPunfix(bn->batCacheid);
    1087           0 :                         return GDK_FAIL;
    1088             :                 }
    1089         252 :                 rc = BATsort(NULL, &bn2, &bn3, bn1, NULL, NULL, !asc, !asc, false);
    1090         252 :                 BBPunfix(bn1->batCacheid);
    1091         252 :                 if (rc != GDK_SUCCEED) {
    1092           0 :                         BBPunfix(bn->batCacheid);
    1093           0 :                         return GDK_FAIL;
    1094             :                 }
    1095         252 :                 rc = BATsort(NULL, &bn4, NULL, bn2, NULL, NULL, false, false, false);
    1096         252 :                 BBPunfix(bn2->batCacheid);
    1097         252 :                 if (rc != GDK_SUCCEED) {
    1098           0 :                         BBPunfix(bn->batCacheid);
    1099           0 :                         BBPunfix(bn3->batCacheid);
    1100           0 :                         return GDK_FAIL;
    1101             :                 }
    1102         252 :                 gn = BATproject(bn4, bn3);
    1103         250 :                 BBPunfix(bn3->batCacheid);
    1104         252 :                 BBPunfix(bn4->batCacheid);
    1105         252 :                 if (gn == NULL) {
    1106           0 :                         BBPunfix(bn->batCacheid);
    1107           0 :                         return GDK_FAIL;
    1108             :                 }
    1109         252 :                 *gids = gn;
    1110         252 :                 assert(BATcount(gn) == BATcount(bn));
    1111             :         }
    1112         252 :         *topn = bn;
    1113         252 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1114             :                   ",n=" BUNFMT " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
    1115             :                   " (" LLFMT " usec)\n",
    1116             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s), n,
    1117             :                   ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
    1118             :         return GDK_SUCCEED;
    1119             : }
    1120             : 
    1121             : static gdk_return
    1122         313 : BATfirstn_grouped_with_groups(BAT **topn, BAT **gids, BAT *b, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, bool distinct, lng t0)
    1123             : {
    1124             :         BAT *bn, *gn = NULL;
    1125             :         oid last, lastg;
    1126             :         gdk_return rc;
    1127             : 
    1128         313 :         MT_thread_setalgorithm(__func__);
    1129         313 :         if (distinct) {
    1130             :                 BAT *bn1, *bn2, *bn3, *bn4, *bn5, *bn6, *bn7;
    1131           0 :                 if (BATgroup(&bn1, &bn2, NULL, b, s, g, NULL, NULL) != GDK_SUCCEED)
    1132           0 :                         return GDK_FAIL;
    1133           0 :                 bn3 = BATproject(bn2, b);
    1134           0 :                 if (bn3 == NULL) {
    1135           0 :                         BBPunfix(bn1->batCacheid);
    1136           0 :                         BBPunfix(bn2->batCacheid);
    1137           0 :                         return GDK_FAIL;
    1138             :                 }
    1139           0 :                 bn4 = BATintersect(s, bn2, NULL, NULL, false, false, BUN_NONE);
    1140           0 :                 BBPunfix(bn2->batCacheid);
    1141           0 :                 if (bn4 == NULL) {
    1142           0 :                         BBPunfix(bn1->batCacheid);
    1143           0 :                         return GDK_FAIL;
    1144             :                 }
    1145           0 :                 bn5 = BATproject(bn4, g);
    1146           0 :                 BBPunfix(bn4->batCacheid);
    1147           0 :                 if (bn5 == NULL) {
    1148           0 :                         BBPunfix(bn1->batCacheid);
    1149           0 :                         return GDK_FAIL;
    1150             :                 }
    1151           0 :                 bn6 = BATfirstn_unique_with_groups(bn3, NULL, bn5, n, asc, nilslast, NULL, NULL, t0);
    1152           0 :                 BBPunfix(bn3->batCacheid);
    1153           0 :                 BBPunfix(bn5->batCacheid);
    1154           0 :                 if (bn6 == NULL) {
    1155           0 :                         BBPunfix(bn1->batCacheid);
    1156           0 :                         return GDK_FAIL;
    1157             :                 }
    1158           0 :                 rc = BATleftjoin(&bn7, NULL, bn1, bn6, NULL, NULL, false, BUN_NONE);
    1159           0 :                 BBPunfix(bn6->batCacheid);
    1160           0 :                 if (rc != GDK_SUCCEED)
    1161             :                         return GDK_FAIL;
    1162           0 :                 bn = BATproject(bn7, s);
    1163           0 :                 BBPunfix(bn7->batCacheid);
    1164           0 :                 if (bn == NULL)
    1165             :                         return GDK_FAIL;
    1166             :         } else {
    1167         313 :                 bn = BATfirstn_unique_with_groups(b, s, g, n, asc, nilslast, &last, &lastg, t0);
    1168         313 :                 if (bn == NULL)
    1169             :                         return GDK_FAIL;
    1170             :         }
    1171         313 :         if (BATcount(bn) == 0) {
    1172           0 :                 if (gids) {
    1173           0 :                         gn = BATdense(0, 0, 0);
    1174           0 :                         if (gn == NULL) {
    1175           0 :                                 BBPunfix(bn->batCacheid);
    1176           0 :                                 return GDK_FAIL;
    1177             :                         }
    1178           0 :                         *gids = gn;
    1179             :                 }
    1180           0 :                 *topn = bn;
    1181           0 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1182             :                           ",g=" ALGOBATFMT ",n=" BUNFMT
    1183             :                           " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
    1184             :                           " (empty -- " LLFMT " usec)\n",
    1185             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
    1186             :                           ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
    1187           0 :                 return GDK_SUCCEED;
    1188             :         }
    1189         313 :         if (!distinct && !b->tkey) {
    1190             :                 BAT *bn1, *bn2, *bn3, *bn4;
    1191             : 
    1192             :                 bn1 = bn;
    1193         279 :                 bn2 = BATselect(g, NULL, &lastg, NULL, true, false, false);
    1194         279 :                 if (bn2 == NULL) {
    1195           0 :                         BBPunfix(bn1->batCacheid);
    1196           0 :                         return GDK_FAIL;
    1197             :                 }
    1198         279 :                 bn3 = BATproject(bn2, s);
    1199         279 :                 BBPunfix(bn2->batCacheid);
    1200         279 :                 if (bn3 == NULL) {
    1201           0 :                         BBPunfix(bn1->batCacheid);
    1202           0 :                         return  GDK_FAIL;
    1203             :                 }
    1204         279 :                 BATiter bi = bat_iterator(b);
    1205         279 :                 bn4 = BATselect(b, bn3, BUNtail(bi, last - b->hseqbase), NULL, true, false, false);
    1206         279 :                 bat_iterator_end(&bi);
    1207         279 :                 BBPunfix(bn3->batCacheid);
    1208         279 :                 if (bn4 == NULL) {
    1209           0 :                         BBPunfix(bn1->batCacheid);
    1210           0 :                         return  GDK_FAIL;
    1211             :                 }
    1212         279 :                 bn = BATmergecand(bn1, bn4);
    1213         279 :                 BBPunfix(bn1->batCacheid);
    1214         279 :                 BBPunfix(bn4->batCacheid);
    1215         279 :                 if (bn == NULL)
    1216             :                         return GDK_FAIL;
    1217             :         }
    1218         313 :         if (gids) {
    1219             :                 BAT *bn1, *bn2, *bn3, *bn4, *bn5, *bn6, *bn7, *bn8;
    1220             : 
    1221         313 :                 if ((bn1 = BATintersect(s, bn, NULL, NULL, false, false, BUN_NONE)) == NULL) {
    1222           0 :                         BBPunfix(bn->batCacheid);
    1223           0 :                         return  GDK_FAIL;
    1224             :                 }
    1225         313 :                 bn2 = BATproject(bn1, g);
    1226         313 :                 BBPunfix(bn1->batCacheid);
    1227         313 :                 if (bn2 == NULL) {
    1228           0 :                         BBPunfix(bn->batCacheid);
    1229           0 :                         return GDK_FAIL;
    1230             :                 }
    1231         313 :                 bn3 = BATproject(bn, b);
    1232         313 :                 if (bn3 == NULL) {
    1233           0 :                         BBPunfix(bn2->batCacheid);
    1234           0 :                         return GDK_FAIL;
    1235             :                 }
    1236         313 :                 rc = BATsort(NULL, &bn4, &bn5, bn2, NULL, NULL, false, false, false);
    1237         313 :                 BBPunfix(bn2->batCacheid);
    1238         313 :                 if (rc != GDK_SUCCEED) {
    1239           0 :                         BBPunfix(bn->batCacheid);
    1240           0 :                         BBPunfix(bn3->batCacheid);
    1241           0 :                         return GDK_FAIL;
    1242             :                 }
    1243         313 :                 rc = BATsort(NULL, &bn6, &bn7, bn3, bn4, bn5, !asc, !asc, false);
    1244         313 :                 BBPunfix(bn3->batCacheid);
    1245         313 :                 BBPunfix(bn4->batCacheid);
    1246         313 :                 BBPunfix(bn5->batCacheid);
    1247         313 :                 if (rc != GDK_SUCCEED) {
    1248           0 :                         BBPunfix(bn->batCacheid);
    1249           0 :                         return GDK_FAIL;
    1250             :                 }
    1251         313 :                 rc = BATsort(NULL, &bn8, NULL, bn6, NULL, NULL, false, false, false);
    1252         313 :                 BBPunfix(bn6->batCacheid);
    1253         313 :                 if (rc != GDK_SUCCEED) {
    1254           0 :                         BBPunfix(bn->batCacheid);
    1255           0 :                         BBPunfix(bn7->batCacheid);
    1256           0 :                         return GDK_FAIL;
    1257             :                 }
    1258         313 :                 gn = BATproject(bn8, bn7);
    1259         313 :                 BBPunfix(bn7->batCacheid);
    1260         313 :                 BBPunfix(bn8->batCacheid);
    1261         313 :                 if (gn == NULL) {
    1262           0 :                         BBPunfix(bn->batCacheid);
    1263           0 :                         return GDK_FAIL;
    1264             :                 }
    1265         313 :                 *gids = gn;
    1266         313 :                 assert(BATcount(gn) == BATcount(bn));
    1267             :         }
    1268         313 :         *topn = bn;
    1269         313 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1270             :                   ",g=" ALGOBATFMT ",n=" BUNFMT
    1271             :                   " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
    1272             :                   " (" LLFMT " usec)\n",
    1273             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
    1274             :                   ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
    1275             :         return GDK_SUCCEED;
    1276             : }
    1277             : 
    1278             : gdk_return
    1279        1230 : BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, bool distinct)
    1280             : {
    1281             :         lng t0 = 0;
    1282             : 
    1283        1230 :         assert(topn != NULL);
    1284        1230 :         if (b == NULL) {
    1285           0 :                 *topn = NULL;
    1286           0 :                 return GDK_SUCCEED;
    1287             :         }
    1288             : 
    1289        1230 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    1290             : 
    1291             :         /* if g specified, then so must s */
    1292        1230 :         assert(g == NULL || s != NULL);
    1293             :         /* g and s must be aligned (same size, same hseqbase) */
    1294        1230 :         assert(g == NULL || BATcount(s) == BATcount(g));
    1295        1230 :         assert(g == NULL || BATcount(g) == 0 || s->hseqbase == g->hseqbase);
    1296             : 
    1297        1230 :         if (n == 0 || BATcount(b) == 0 || (s != NULL && BATcount(s) == 0)) {
    1298             :                 /* trivial: empty result */
    1299          84 :                 *topn = BATdense(0, 0, 0);
    1300          85 :                 if (*topn == NULL)
    1301             :                         return GDK_FAIL;
    1302          85 :                 if (gids) {
    1303          47 :                         *gids = BATdense(0, 0, 0);
    1304          47 :                         if (*gids == NULL) {
    1305           0 :                                 BBPreclaim(*topn);
    1306           0 :                                 return GDK_FAIL;
    1307             :                         }
    1308             :                 }
    1309          85 :                 return GDK_SUCCEED;
    1310             :         }
    1311             : 
    1312        1146 :         if (g == NULL) {
    1313         597 :                 if (gids == NULL && !distinct) {
    1314         345 :                         *topn = BATfirstn_unique(b, s, n, asc, nilslast, NULL, t0);
    1315         345 :                         return *topn ? GDK_SUCCEED : GDK_FAIL;
    1316             :                 }
    1317         252 :                 return BATfirstn_grouped(topn, gids, b, s, n, asc, nilslast, distinct, t0);
    1318             :         }
    1319         549 :         if (gids == NULL && !distinct) {
    1320         236 :                 *topn = BATfirstn_unique_with_groups(b, s, g, n, asc, nilslast, NULL, NULL, t0);
    1321         236 :                 return *topn ? GDK_SUCCEED : GDK_FAIL;
    1322             :         }
    1323         313 :         return BATfirstn_grouped_with_groups(topn, gids, b, s, g, n, asc, nilslast, distinct, t0);
    1324             : }

Generated by: LCOV version 1.14