LCOV - code coverage report
Current view: top level - gdk - gdk_group.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 323 412 78.4 %
Date: 2024-10-07 21:21:43 Functions: 3 3 100.0 %

          Line data    Source code
       1             : /*
       2             :  * SPDX-License-Identifier: MPL-2.0
       3             :  *
       4             :  * This Source Code Form is subject to the terms of the Mozilla Public
       5             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       6             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       7             :  *
       8             :  * Copyright 2024 MonetDB Foundation;
       9             :  * Copyright August 2008 - 2023 MonetDB B.V.;
      10             :  * Copyright 1997 - July 2008 CWI.
      11             :  */
      12             : 
      13             : #include "monetdb_config.h"
      14             : #include "gdk.h"
      15             : #include "gdk_private.h"
      16             : #include "gdk_cand.h"
      17             : 
      18             : /* how much to extend the extent and histo bats when we run out of space */
      19             : #define GROUPBATINCR    8192
      20             : 
      21             : /* BATgroup returns three bats that indicate the grouping of the input
      22             :  * bat.
      23             :  *
      24             :  * Grouping means that all equal values are in the same group, and
      25             :  * differing values are in different groups.  If specified, the input
      26             :  * bat g gives a pre-existing grouping which is then subdivided.  If a
      27             :  * candidate list s is specified, groups (both the pre-existing
      28             :  * grouping in g and the output grouping) are aligned with the
      29             :  * candidate list, else they are aligned with b.
      30             :  *
      31             :  * The outputs are as follows.
      32             :  *
      33             :  * The groups bat is aligned with the candidate list s, or the input
      34             :  * bat b if there is no candidate list, and the tail has group id's
      35             :  * (type oid).
      36             :  *
      37             :  * The extents and histo bats are indexed by group id.  The tail of
      38             :  * extents is the head oid from b of a representative of the group.
      39             :  * The tail of histo is of type lng and contains the number of
      40             :  * elements from b that are member of the group.  The extents BAT can
      41             :  * be used as a candidate list (sorted and unique).
      42             :  *
      43             :  * The extents and histo bats are optionally created.  The groups bat
      44             :  * is always created.  In other words, the groups argument may not be
      45             :  * NULL, but the extents and histo arguments may be NULL.
      46             :  *
      47             :  * There are six different implementations of the grouping code.
      48             :  *
      49             :  * If it can be trivially determined that all groups are singletons,
      50             :  * we can produce the outputs trivially.
      51             :  *
      52             :  * If all values in b are known to be equal (both sorted and reverse
      53             :  * sorted), we produce a single group or copy the input group.
      54             :  *
      55             :  * If the input bats b and g are sorted (either direction) or g is not
      56             :  * specified and b is sorted, or if the subsorted flag is set (only
      57             :  * used by BATsort), we only need to compare consecutive values.
      58             :  *
      59             :  * If the input bat b is sorted, but g is not, we can compare
      60             :  * consecutive values in b and need to scan sections of g for equal
      61             :  * groups.
      62             :  *
      63             :  * If a hash table already exists on b, we can make use of it.
      64             :  *
      65             :  * Otherwise we build a partial hash table on the fly.
      66             :  *
      67             :  * A decision should be made on the order in which grouping occurs.
      68             :  * Let |b| have << different values than |g| then the linked lists
      69             :  * gets extremely long, leading to a n^2 algorithm.
      70             :  * At the MAL level, the multigroup function would perform the dynamic
      71             :  * optimization.
      72             :  */
      73             : 
      74             : #define GRPnotfound()                                                   \
      75             :         do {                                                            \
      76             :                 /* no equal found: start new group */                   \
      77             :                 if (ngrp == maxgrps) {                                  \
      78             :                         /* we need to extend extents and histo bats, */ \
      79             :                         /* do it at most once */                        \
      80             :                         maxgrps = bi.count;                             \
      81             :                         if (extents) {                                  \
      82             :                                 BATsetcount(en, ngrp);                  \
      83             :                                 if (BATextend(en, maxgrps) != GDK_SUCCEED) \
      84             :                                         goto error;                     \
      85             :                                 exts = (oid *) Tloc(en, 0);             \
      86             :                         }                                               \
      87             :                         if (histo) {                                    \
      88             :                                 BATsetcount(hn, ngrp);                  \
      89             :                                 if (BATextend(hn, maxgrps) != GDK_SUCCEED) \
      90             :                                         goto error;                     \
      91             :                                 cnts = (lng *) Tloc(hn, 0);             \
      92             :                         }                                               \
      93             :                 }                                                       \
      94             :                 if (extents)                                            \
      95             :                         exts[ngrp] = hseqb + p - lo;                    \
      96             :                 if (histo)                                              \
      97             :                         cnts[ngrp] = 1;                                 \
      98             :                 ngrps[r] = ngrp++;                                      \
      99             :                 maxgrppos = r;                                          \
     100             :         } while (0)
     101             : 
     102             : 
     103             : #define GRP_compare_consecutive_values(INIT_0,INIT_1,DIFFER,KEEP)       \
     104             :         do {                                                            \
     105             :                 INIT_0;                                                 \
     106             :                 if (ci.tpe == cand_dense) {                             \
     107             :                         if (grps) {                                     \
     108             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, dense, groups"); \
     109             :                                 TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
     110             :                                         p = canditer_next_dense(&ci) - hseqb; \
     111             :                                         INIT_1;                         \
     112             :                                         if (ngrp == 0 || grps[r] != prev || DIFFER) { \
     113             :                                                 GRPnotfound();          \
     114             :                                         } else {                        \
     115             :                                                 ngrps[r] = ngrp - 1;    \
     116             :                                                 if (histo)              \
     117             :                                                         cnts[ngrp - 1]++; \
     118             :                                         }                               \
     119             :                                         KEEP;                           \
     120             :                                         prev = grps[r];                 \
     121             :                                 }                                       \
     122             :                                 TIMEOUT_CHECK(qry_ctx,                  \
     123             :                                               GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     124             :                         } else {                                        \
     125             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, dense, !groups"); \
     126             :                                 TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
     127             :                                         p = canditer_next_dense(&ci) - hseqb; \
     128             :                                         INIT_1;                         \
     129             :                                         if (ngrp == 0 || DIFFER) {      \
     130             :                                                 GRPnotfound();          \
     131             :                                         } else {                        \
     132             :                                                 ngrps[r] = ngrp - 1;    \
     133             :                                                 if (histo)              \
     134             :                                                         cnts[ngrp - 1]++; \
     135             :                                         }                               \
     136             :                                         KEEP;                           \
     137             :                                 }                                       \
     138             :                                 TIMEOUT_CHECK(qry_ctx,                  \
     139             :                                               GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     140             :                         }                                               \
     141             :                 } else {                                                \
     142             :                         if (grps) {                                     \
     143             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, groups"); \
     144             :                                 TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
     145             :                                         p = canditer_next(&ci) - hseqb;     \
     146             :                                         INIT_1;                         \
     147             :                                         if (ngrp == 0 || grps[r] != prev || DIFFER) { \
     148             :                                                 GRPnotfound();          \
     149             :                                         } else {                        \
     150             :                                                 ngrps[r] = ngrp - 1;    \
     151             :                                                 if (histo)              \
     152             :                                                         cnts[ngrp - 1]++; \
     153             :                                         }                               \
     154             :                                         KEEP;                           \
     155             :                                         prev = grps[r];                 \
     156             :                                 }                                       \
     157             :                                 TIMEOUT_CHECK(qry_ctx,                  \
     158             :                                               GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     159             :                         } else {                                        \
     160             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, !groups"); \
     161             :                                 TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
     162             :                                         p = canditer_next(&ci) - hseqb;     \
     163             :                                         INIT_1;                         \
     164             :                                         if (ngrp == 0 || DIFFER) {      \
     165             :                                                 GRPnotfound();          \
     166             :                                         } else {                        \
     167             :                                                 ngrps[r] = ngrp - 1;    \
     168             :                                                 if (histo)              \
     169             :                                                         cnts[ngrp - 1]++; \
     170             :                                         }                               \
     171             :                                         KEEP;                           \
     172             :                                 }                                       \
     173             :                                 TIMEOUT_CHECK(qry_ctx,                  \
     174             :                                               GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     175             :                         }                                               \
     176             :                 }                                                       \
     177             :         } while(0)
     178             : 
     179             : #define flt_neq(a, b)   (is_flt_nil(a) ? !is_flt_nil(b) : is_flt_nil(b) || (a) != (b))
     180             : #define dbl_neq(a, b)   (is_dbl_nil(a) ? !is_dbl_nil(b) : is_dbl_nil(b) || (a) != (b))
     181             : #define bte_neq(a, b)   ((a) != (b))
     182             : #define sht_neq(a, b)   ((a) != (b))
     183             : #define int_neq(a, b)   ((a) != (b))
     184             : #define lng_neq(a, b)   ((a) != (b))
     185             : #define hge_neq(a, b)   ((a) != (b))
     186             : 
     187             : #define GRP_compare_consecutive_values_tpe(TYPE)                \
     188             :         GRP_compare_consecutive_values(                         \
     189             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base;       \
     190             :                         TYPE pw = 0                     ,       \
     191             :         /* INIT_1 */                                    ,       \
     192             :         /* DIFFER */    TYPE##_neq(w[p], pw)            ,       \
     193             :         /* KEEP   */    pw = w[p]                               \
     194             :         )
     195             : 
     196             : #define GRP_compare_consecutive_values_any()                    \
     197             :         GRP_compare_consecutive_values(                         \
     198             :         /* INIT_0 */    pv = NULL                       ,       \
     199             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     200             :         /* DIFFER */    cmp(v, pv) != 0                 ,       \
     201             :         /* KEEP   */    pv = v                                  \
     202             :         )
     203             : 
     204             : 
     205             : #define GRP_subscan_old_groups(INIT_0,INIT_1,EQUAL,KEEP)                \
     206             :         do {                                                            \
     207             :                 INIT_0;                                                 \
     208             :                 pgrp[grps[0]] = 0;                                      \
     209             :                 j = 0;                                                  \
     210             :                 if (ci.tpe == cand_dense) {                             \
     211             :                         MT_thread_setalgorithm("GRP_subscan_old_groups, dense"); \
     212             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     213             :                                 p = canditer_next_dense(&ci) - hseqb;       \
     214             :                                 INIT_1;                                 \
     215             :                                 if (ngrp != 0 && EQUAL) {               \
     216             :                                         /* range [j, r) is all same value */ \
     217             :                                         /* i is position where we saw r's */ \
     218             :                                         /* old group last */            \
     219             :                                         i = pgrp[grps[r]];              \
     220             :                                         /* p is new position where we saw this \
     221             :                                          * group */                     \
     222             :                                         pgrp[grps[r]] = r;              \
     223             :                                         if (j <= i && i < r)      {       \
     224             :                                                 /* i is position of equal */ \
     225             :                                                 /* value in same old group */ \
     226             :                                                 /* as r, so r gets same new */ \
     227             :                                                 /* group as i */        \
     228             :                                                 oid grp = ngrps[i];     \
     229             :                                                 ngrps[r] = grp;         \
     230             :                                                 if (histo)              \
     231             :                                                         cnts[grp]++;    \
     232             :                                                 if (gn->tsorted &&   \
     233             :                                                     grp != ngrp - 1)    \
     234             :                                                         gn->tsorted = false; \
     235             :                                                 /* we found the value/group */ \
     236             :                                                 /* combination, go to next */ \
     237             :                                                 /* value */             \
     238             :                                                 continue;               \
     239             :                                         }                               \
     240             :                                 } else {                                \
     241             :                                         /* value differs from previous value */ \
     242             :                                         /* (or is the first) */         \
     243             :                                         j = r;                          \
     244             :                                         KEEP;                           \
     245             :                                         pgrp[grps[r]] = r;              \
     246             :                                 }                                       \
     247             :                                 /* start a new group */                 \
     248             :                                 GRPnotfound();                          \
     249             :                         }                                               \
     250             :                         TIMEOUT_CHECK(qry_ctx,                          \
     251             :                                       GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     252             :                 } else {                                                \
     253             :                         MT_thread_setalgorithm("GRP_subscan_old_groups, !dense"); \
     254             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     255             :                                 p = canditer_next(&ci) - hseqb;             \
     256             :                                 INIT_1;                                 \
     257             :                                 if (ngrp != 0 && EQUAL) {               \
     258             :                                         /* range [j, r) is all same value */ \
     259             :                                         /* i is position where we saw r's */ \
     260             :                                         /* old group last */            \
     261             :                                         i = pgrp[grps[r]];              \
     262             :                                         /* p is new position where we saw this \
     263             :                                          * group */                     \
     264             :                                         pgrp[grps[r]] = r;              \
     265             :                                         if (j <= i && i < r)      {       \
     266             :                                                 /* i is position of equal */ \
     267             :                                                 /* value in same old group */ \
     268             :                                                 /* as r, so r gets same new */ \
     269             :                                                 /* group as i */        \
     270             :                                                 oid grp = ngrps[i];     \
     271             :                                                 ngrps[r] = grp;         \
     272             :                                                 if (histo)              \
     273             :                                                         cnts[grp]++;    \
     274             :                                                 if (gn->tsorted &&   \
     275             :                                                     grp != ngrp - 1)    \
     276             :                                                         gn->tsorted = false; \
     277             :                                                 /* we found the value/group */ \
     278             :                                                 /* combination, go to next */ \
     279             :                                                 /* value */             \
     280             :                                                 continue;               \
     281             :                                         }                               \
     282             :                                 } else {                                \
     283             :                                         /* value differs from previous value */ \
     284             :                                         /* (or is the first) */         \
     285             :                                         j = r;                          \
     286             :                                         KEEP;                           \
     287             :                                         pgrp[grps[r]] = r;              \
     288             :                                 }                                       \
     289             :                                 /* start a new group */                 \
     290             :                                 GRPnotfound();                          \
     291             :                         }                                               \
     292             :                         TIMEOUT_CHECK(qry_ctx,                          \
     293             :                                       GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     294             :                 }                                                       \
     295             :         } while(0)
     296             : 
     297             : #define flt_equ(a, b)   (is_flt_nil(a) ? is_flt_nil(b) : !is_flt_nil(b) && (a) == (b))
     298             : #define dbl_equ(a, b)   (is_dbl_nil(a) ? is_dbl_nil(b) : !is_dbl_nil(b) && (a) == (b))
     299             : #define bte_equ(a, b)   ((a) == (b))
     300             : #define sht_equ(a, b)   ((a) == (b))
     301             : #define int_equ(a, b)   ((a) == (b))
     302             : #define lng_equ(a, b)   ((a) == (b))
     303             : #define hge_equ(a, b)   ((a) == (b))
     304             : #ifdef HAVE_HGE
     305             : #define uuid_equ(a, b)  ((a).h == (b).h)
     306             : #else
     307             : #define uuid_equ(a, b)  (memcmp((a).u, (b).u, UUID_SIZE) == 0)
     308             : #endif
     309             : 
     310             : #define GRP_subscan_old_groups_tpe(TYPE)                        \
     311             :         GRP_subscan_old_groups(                                 \
     312             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base;       \
     313             :                         TYPE pw = 0                     ,       \
     314             :         /* INIT_1 */                                    ,       \
     315             :         /* EQUAL  */    TYPE##_equ(w[p], pw)            ,       \
     316             :         /* KEEP   */    pw = w[p]                               \
     317             :         )
     318             : 
     319             : #define GRP_subscan_old_groups_any()                            \
     320             :         GRP_subscan_old_groups(                                 \
     321             :         /* INIT_0 */    pv = NULL                       ,       \
     322             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     323             :         /* EQUAL  */    cmp(v, pv) == 0                 ,       \
     324             :         /* KEEP   */    pv = v                                  \
     325             :         )
     326             : 
     327             : /* If a hash table exists on b we use it.
     328             :  *
     329             :  * The algorithm is simple.  We go through b and for each value we
     330             :  * follow the hash chain starting at the next element after that value
     331             :  * to find one that is equal to the value we're currently looking at.
     332             :  * If we found such a value, we add the value to the same group.  If
     333             :  * we reach the end of the chain, we create a new group.
     334             :  *
     335             :  * If b (the original, that is) is a view on another BAT, and this
     336             :  * other BAT has a hash, we use that.  The lo and hi values are the
     337             :  * bounds of the parent BAT that we're considering.
     338             :  *
     339             :  * Note this algorithm depends critically on the fact that our hash
     340             :  * chains go from higher to lower BUNs.
     341             :  */
     342             : #define GRP_use_existing_hash_table(INIT_0,INIT_1,EQUAL)                \
     343             :         do {                                                            \
     344             :                 INIT_0;                                                 \
     345             :                 assert(grps == NULL);                                   \
     346             :                 if (ci.tpe == cand_dense) {                             \
     347             :                         MT_thread_setalgorithm(phash ? "GRP_use_existing_hash_table, dense, parent hash" : "GRP_use_existing_hash_table, dense"); \
     348             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     349             :                                 oid o = canditer_next_dense(&ci);   \
     350             :                                 p = o - hseqb + lo;                     \
     351             :                                 INIT_1;                                 \
     352             :                                 /* this loop is similar, but not */     \
     353             :                                 /* equal, to HASHloop: the difference */ \
     354             :                                 /* is that we only consider BUNs */     \
     355             :                                 /* smaller than the one we're looking */ \
     356             :                                 /* up (p) */                            \
     357             :                                 for (hb = HASHgetlink(hs, p);           \
     358             :                                      hb != BUN_NONE && hb >= lo;     \
     359             :                                      hb = HASHgetlink(hs, hb)) {        \
     360             :                                         oid grp;                        \
     361             :                                         assert(hb < p);                      \
     362             :                                         q = canditer_search_dense(&ci, hb + hseqb - lo, false); \
     363             :                                         if (q == BUN_NONE)              \
     364             :                                                 continue;               \
     365             :                                         if (EQUAL) {                    \
     366             :                                                 grp = ngrps[q];         \
     367             :                                                 ngrps[r] = grp;         \
     368             :                                                 if (histo)              \
     369             :                                                         cnts[grp]++;    \
     370             :                                                 if (gn->tsorted &&   \
     371             :                                                     grp != ngrp - 1)    \
     372             :                                                         gn->tsorted = false; \
     373             :                                                 break;                  \
     374             :                                         }                               \
     375             :                                 }                                       \
     376             :                                 if (hb == BUN_NONE || hb < lo) {     \
     377             :                                         GRPnotfound();                  \
     378             :                                 }                                       \
     379             :                         }                                               \
     380             :                         TIMEOUT_CHECK(qry_ctx,                          \
     381             :                                       GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     382             :                 } else {                                                \
     383             :                         MT_thread_setalgorithm(phash ? "GRP_use_existing_hash_table, !dense, parent hash" : "GRP_use_existing_hash_table, !dense"); \
     384             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     385             :                                 oid o = canditer_next(&ci);         \
     386             :                                 p = o - hseqb + lo;                     \
     387             :                                 INIT_1;                                 \
     388             :                                 /* this loop is similar, but not */     \
     389             :                                 /* equal, to HASHloop: the difference */ \
     390             :                                 /* is that we only consider BUNs */     \
     391             :                                 /* smaller than the one we're looking */ \
     392             :                                 /* up (p) */                            \
     393             :                                 for (hb = HASHgetlink(hs, p);           \
     394             :                                      hb != BUN_NONE && hb >= lo;     \
     395             :                                      hb = HASHgetlink(hs, hb)) {        \
     396             :                                         oid grp;                        \
     397             :                                         assert(hb < p);                      \
     398             :                                         q = canditer_search(&ci, hb + hseqb - lo, false); \
     399             :                                         if (q == BUN_NONE)              \
     400             :                                                 continue;               \
     401             :                                         if (EQUAL) {                    \
     402             :                                                 grp = ngrps[q];         \
     403             :                                                 ngrps[r] = grp;         \
     404             :                                                 if (histo)              \
     405             :                                                         cnts[grp]++;    \
     406             :                                                 if (gn->tsorted &&   \
     407             :                                                     grp != ngrp - 1)    \
     408             :                                                         gn->tsorted = false; \
     409             :                                                 break;                  \
     410             :                                         }                               \
     411             :                                 }                                       \
     412             :                                 if (hb == BUN_NONE || hb < lo) {     \
     413             :                                         GRPnotfound();                  \
     414             :                                 }                                       \
     415             :                         }                                               \
     416             :                         TIMEOUT_CHECK(qry_ctx,                          \
     417             :                                       GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     418             :                 }                                                       \
     419             :         } while(0)
     420             : 
     421             : #define GRP_use_existing_hash_table_tpe(TYPE)                   \
     422             :         GRP_use_existing_hash_table(                            \
     423             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base,       \
     424             :         /* INIT_1 */                                    ,       \
     425             :         /* EQUAL  */    TYPE##_equ(w[p], w[hb])                 \
     426             :         )
     427             : 
     428             : #define GRP_use_existing_hash_table_any()                       \
     429             :         GRP_use_existing_hash_table(                            \
     430             :         /* INIT_0 */                                    ,       \
     431             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     432             :         /* EQUAL  */    cmp(v, BUNtail(bi, hb)) == 0            \
     433             :         )
     434             : 
     435             : /* reverse the bits of an OID value */
     436             : static inline oid
     437    37480711 : rev(oid x)
     438             : {
     439             : #if SIZEOF_OID == 8
     440    37480711 :         x = ((x & 0x5555555555555555) <<  1) | ((x >>  1) & 0x5555555555555555);
     441    37480711 :         x = ((x & 0x3333333333333333) <<  2) | ((x >>  2) & 0x3333333333333333);
     442    37480711 :         x = ((x & 0x0F0F0F0F0F0F0F0F) <<  4) | ((x >>  4) & 0x0F0F0F0F0F0F0F0F);
     443    37480711 :         x = ((x & 0x00FF00FF00FF00FF) <<  8) | ((x >>  8) & 0x00FF00FF00FF00FF);
     444    37480711 :         x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF0000FFFF);
     445    37480711 :         x = ((x & 0x00000000FFFFFFFF) << 32) | ((x >> 32) & 0x00000000FFFFFFFF);
     446             : #else
     447             :         x = ((x & 0x55555555) <<  1) | ((x >>  1) & 0x55555555);
     448             :         x = ((x & 0x33333333) <<  2) | ((x >>  2) & 0x33333333);
     449             :         x = ((x & 0x0F0F0F0F) <<  4) | ((x >>  4) & 0x0F0F0F0F);
     450             :         x = ((x & 0x00FF00FF) <<  8) | ((x >>  8) & 0x00FF00FF);
     451             :         x = ((x & 0x0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF);
     452             : #endif
     453    37480711 :         return x;
     454             : }
     455             : 
     456             : /* count trailing zeros, also see candmask_lobit in gdk_cand.h */
     457             : static inline int __attribute__((__const__))
     458       13614 : ctz(oid x)
     459             : {
     460             : #ifdef __has_builtin
     461             : #if SIZEOF_OID == SIZEOF_INT && __has_builtin(__builtin_ctz)
     462             :         return __builtin_ctz(x);
     463             : #define BUILTIN_USED
     464             : #elif __has_builtin(__builtin_ctzl)
     465       13614 :         return __builtin_ctzl(x);
     466             : #define BUILTIN_USED
     467             : #endif
     468             : #endif
     469             : #ifndef BUILTIN_USED
     470             : #if defined(_MSC_VER)
     471             : #if SIZEOF_OID == SIZEOF_INT
     472             :         unsigned long idx;
     473             :         if (_BitScanForward(&idx, (unsigned long) x))
     474             :                 return (int) idx;
     475             : #else
     476             :         unsigned long idx;
     477             :         if (_BitScanForward64(&idx, (unsigned __int64) x))
     478             :                 return (int) idx;
     479             : #endif
     480             :         return -1;
     481             : #else
     482             :         /* use binary search for the lowest set bit */
     483             :         int n = 1;
     484             : #if SIZEOF_OID == SIZEOF_INT
     485             :         if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
     486             :         if ((x & 0x000000FF) == 0) { n +=  8; x >>=  8; }
     487             :         if ((x & 0x0000000F) == 0) { n +=  4; x >>=  4; }
     488             :         if ((x & 0x00000003) == 0) { n +=  2; x >>=  2; }
     489             : #else
     490             :         if ((x & UINT64_C(0x00000000FFFFFFFF)) == 0) { n += 32; x >>= 32; }
     491             :         if ((x & UINT64_C(0x000000000000FFFF)) == 0) { n += 16; x >>= 16; }
     492             :         if ((x & UINT64_C(0x00000000000000FF)) == 0) { n +=  8; x >>=  8; }
     493             :         if ((x & UINT64_C(0x000000000000000F)) == 0) { n +=  4; x >>=  4; }
     494             :         if ((x & UINT64_C(0x0000000000000003)) == 0) { n +=  2; x >>=  2; }
     495             : #endif
     496             :         return n - (x & 1);
     497             : #endif
     498             : #endif
     499             : #undef BUILTIN_USED
     500             : }
     501             : 
     502             : #define GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,ASSERT,GRPTST) \
     503             :         do {                                                            \
     504             :                 if (ci.tpe == cand_dense) {                             \
     505             :                         MT_thread_setalgorithm("GRP_create_partial_hash_table, dense"); \
     506             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     507             :                                 p = canditer_next_dense(&ci) - hseqb;       \
     508             :                                 INIT_1;                                 \
     509             :                                 prb = HASH;                             \
     510             :                                 for (hb = HASHget(hs, prb);             \
     511             :                                      hb != BUN_NONE;                    \
     512             :                                      hb = HASHgetlink(hs, hb)) {        \
     513             :                                         ASSERT;                         \
     514             :                                         q = canditer_search_dense(&ci, hb + hseqb, false); \
     515             :                                         if (q == BUN_NONE)              \
     516             :                                                 continue;               \
     517             :                                         GRPTST(q, r);                   \
     518             :                                         if (EQUAL) {                    \
     519             :                                                 grp = ngrps[q];         \
     520             :                                                 ngrps[r] = grp;         \
     521             :                                                 if (histo)              \
     522             :                                                         cnts[grp]++;    \
     523             :                                                 if (gn->tsorted &&   \
     524             :                                                     grp != ngrp - 1)    \
     525             :                                                         gn->tsorted = false; \
     526             :                                                 break;                  \
     527             :                                         }                               \
     528             :                                 }                                       \
     529             :                                 if (hb == BUN_NONE) {                   \
     530             :                                         GRPnotfound();                  \
     531             :                                         /* enter new group into hash table */ \
     532             :                                         HASHputlink(hs, p, HASHget(hs, prb)); \
     533             :                                         HASHput(hs, prb, p);            \
     534             :                                 }                                       \
     535             :                         }                                               \
     536             :                         TIMEOUT_CHECK(qry_ctx,                          \
     537             :                                       GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     538             :                 } else {                                                \
     539             :                         MT_thread_setalgorithm("GRP_create_partial_hash_table, !dense"); \
     540             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     541             :                                 p = canditer_next(&ci) - hseqb;             \
     542             :                                 INIT_1;                                 \
     543             :                                 prb = HASH;                             \
     544             :                                 for (hb = HASHget(hs, prb);             \
     545             :                                      hb != BUN_NONE;                    \
     546             :                                      hb = HASHgetlink(hs, hb)) {        \
     547             :                                         ASSERT;                         \
     548             :                                         q = canditer_search(&ci, hb + hseqb, false); \
     549             :                                         if (q == BUN_NONE)              \
     550             :                                                 continue;               \
     551             :                                         GRPTST(q, r);                   \
     552             :                                         if (EQUAL) {                    \
     553             :                                                 grp = ngrps[q];         \
     554             :                                                 ngrps[r] = grp;         \
     555             :                                                 if (histo)              \
     556             :                                                         cnts[grp]++;    \
     557             :                                                 if (gn->tsorted &&   \
     558             :                                                     grp != ngrp - 1)    \
     559             :                                                         gn->tsorted = false; \
     560             :                                                 break;                  \
     561             :                                         }                               \
     562             :                                 }                                       \
     563             :                                 if (hb == BUN_NONE) {                   \
     564             :                                         GRPnotfound();                  \
     565             :                                         /* enter new group into hash table */ \
     566             :                                         HASHputlink(hs, p, HASHget(hs, prb)); \
     567             :                                         HASHput(hs, prb, p);            \
     568             :                                 }                                       \
     569             :                         }                                               \
     570             :                         TIMEOUT_CHECK(qry_ctx,                          \
     571             :                                       GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     572             :                 }                                                       \
     573             :         } while (0)
     574             : #define GCGRPTST(i, j)  if (grps[i] != grps[j]) { hb = BUN_NONE; break; }
     575             : #define GRPTST(i, j)    if (grps[i] != grps[j]) continue
     576             : #define NOGRPTST(i, j)  (void) 0
     577             : #define GRP_create_partial_hash_table(INIT_0,INIT_1,HASH,EQUAL)         \
     578             :         do {                                                            \
     579             :                 INIT_0;                                                 \
     580             :                 if (grps) {                                             \
     581             :                         if (gc) {                                       \
     582             :                                 GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,assert(HASHgetlink(hs, hb) == BUN_NONE || HASHgetlink(hs, hb) < hb),GCGRPTST); \
     583             :                         } else {                                        \
     584             :                                 GRP_create_partial_hash_table_core(INIT_1,HASH ^ (rev(grps[r]) >> bits),EQUAL,(void)0,GRPTST); \
     585             :                         }                                               \
     586             :                 } else {                                                \
     587             :                         GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,(void)0,NOGRPTST); \
     588             :                 }                                                       \
     589             :         } while (0)
     590             : 
     591             : #define GRP_create_partial_hash_table_tpe(TYPE)                 \
     592             :         GRP_create_partial_hash_table(                          \
     593             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base,       \
     594             :         /* INIT_1 */                                    ,       \
     595             :         /* HASH   */    hash_##TYPE(hs, &w[p])              ,       \
     596             :         /* EQUAL  */    TYPE##_equ(w[p], w[hb])                 \
     597             :         )
     598             : 
     599             : #define GRP_create_partial_hash_table_any()                     \
     600             :         GRP_create_partial_hash_table(                          \
     601             :         /* INIT_0 */                                    ,       \
     602             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     603             :         /* HASH   */    hash_any(hs, v)                 ,       \
     604             :         /* EQUAL  */    cmp(v, BUNtail(bi, hb)) == 0            \
     605             :         )
     606             : 
     607             : #define GRP_small_values(BG, BV, GV)                                    \
     608             :         do {                                                            \
     609             :                 uint##BG##_t sgrps[1 << BG];                              \
     610             :                 const uint##BV##_t *restrict w = (const uint##BV##_t *) bi.base; \
     611             :                 uint##BG##_t v;                                         \
     612             :                 memset(sgrps, 0xFF, sizeof(sgrps));                     \
     613             :                 if (histo)                                              \
     614             :                         memset(cnts, 0, maxgrps * sizeof(lng));         \
     615             :                 ngrp = 0;                                               \
     616             :                 gn->tsorted = true;                                  \
     617             :                 if (ci.tpe == cand_dense) {                             \
     618             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     619             :                                 oid o = canditer_next_dense(&ci);   \
     620             :                                 p = o - hseqb;                          \
     621             :                                 uint##BG##_t x = GV;                    \
     622             :                                 if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp < (1 << BG)) { \
     623             :                                         sgrps[x] = v = (uint##BG##_t) ngrp++; \
     624             :                                         maxgrppos = r;                  \
     625             :                                         if (extents)                    \
     626             :                                                 exts[v] = o;            \
     627             :                                 }                                       \
     628             :                                 ngrps[r] = v;                           \
     629             :                                 if (r > 0 && v < ngrps[r - 1])            \
     630             :                                         gn->tsorted = false;         \
     631             :                                 if (histo)                              \
     632             :                                         cnts[v]++;                      \
     633             :                         }                                               \
     634             :                 } else {                                                \
     635             :                         TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) {        \
     636             :                                 oid o = canditer_next(&ci);         \
     637             :                                 p = o - hseqb;                          \
     638             :                                 uint##BG##_t x = GV;                    \
     639             :                                 if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp < (1 << BG)) { \
     640             :                                         sgrps[x] = v = (uint##BG##_t) ngrp++; \
     641             :                                         maxgrppos = r;                  \
     642             :                                         if (extents)                    \
     643             :                                                 exts[v] = o;            \
     644             :                                 }                                       \
     645             :                                 ngrps[r] = v;                           \
     646             :                                 if (r > 0 && v < ngrps[r - 1])            \
     647             :                                         gn->tsorted = false;         \
     648             :                                 if (histo)                              \
     649             :                                         cnts[v]++;                      \
     650             :                         }                                               \
     651             :                 }                                                       \
     652             :                 TIMEOUT_CHECK(qry_ctx,                                  \
     653             :                               GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
     654             :         } while (0)
     655             : 
     656             : gdk_return
     657       93882 : BATgroup_internal(BAT **groups, BAT **extents, BAT **histo,
     658             :                   BAT *b, BAT *s, BAT *g, BAT *e, BAT *h, bool subsorted)
     659             : {
     660       93882 :         BAT *gn = NULL, *en = NULL, *hn = NULL;
     661       93882 :         int t;
     662       93882 :         int (*cmp)(const void *, const void *);
     663       93882 :         const oid *grps = NULL;
     664       93882 :         oid *restrict ngrps, ngrp, prev = 0, hseqb = 0;
     665       93882 :         oid *restrict exts = NULL;
     666       93882 :         lng *restrict cnts = NULL;
     667       93882 :         BUN p, q, r;
     668       93882 :         const void *v, *pv;
     669       93882 :         BATiter bi;
     670       93882 :         Hash *hs = NULL;
     671       93882 :         BUN hb;
     672       93882 :         BUN maxgrps;
     673       93882 :         BUN maxgrppos = BUN_NONE;
     674       93882 :         bat parent;
     675       93882 :         BUN lo = 0;
     676       93882 :         struct canditer ci;
     677       93882 :         oid maxgrp = oid_nil;   /* maximum value of g BAT (if subgrouping) */
     678       93882 :         lng t0 = 0;
     679       93882 :         const char *algomsg = "";
     680       93882 :         bool locked = false;
     681             : 
     682       93882 :         QryCtx *qry_ctx = MT_thread_get_qry_ctx();
     683             : 
     684       93896 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
     685       93896 :         if (b == NULL) {
     686           0 :                 GDKerror("b must exist\n");
     687           0 :                 return GDK_FAIL;
     688             :         }
     689       93896 :         assert(s == NULL || BATttype(s) == TYPE_oid);
     690       93896 :         canditer_init(&ci, b, s);
     691       94180 :         bi = bat_iterator(b);
     692             : 
     693             :         /* g is NULL or [oid(dense),oid] and same size as b or s */
     694       93943 :         assert(g == NULL || BATttype(g) == TYPE_oid || BATcount(g) == 0);
     695       28616 :         assert(g == NULL || BATcount(g) == ci.ncand);
     696       28616 :         assert(g == NULL || BATcount(b) == 0 || (s ? g->hseqbase == s->hseqbase : g->hseqbase == b->hseqbase));
     697             :         /* e is NULL or [oid(dense),oid] */
     698       93943 :         assert(e == NULL || BATttype(e) == TYPE_oid);
     699             :         /* h is NULL or [oid(dense),lng] */
     700       93943 :         assert(h == NULL || h->ttype == TYPE_lng);
     701             :         /* e and h are aligned */
     702       93943 :         assert(e == NULL || h == NULL || BATcount(e) == BATcount(h));
     703       93943 :         assert(e == NULL || h == NULL || e->hseqbase == h->hseqbase);
     704             :         /* we want our output to go somewhere */
     705       93943 :         assert(groups != NULL);
     706             : 
     707       93943 :         if (ci.ncand == 0) {
     708             :                 hseqb = 0;
     709             :         } else {
     710       61480 :                 hseqb = ci.seq;
     711             :         }
     712       93943 :         if (bi.key || ci.ncand <= 1 || (g && (g->tkey || BATtdense(g)))) {
     713             :                 /* grouping is trivial: 1 element per group */
     714       50871 :                 gn = BATdense(hseqb, 0, BATcount(b));
     715       50852 :                 if (gn == NULL)
     716           0 :                         goto error;
     717       50852 :                 *groups = gn;
     718       50852 :                 if (extents) {
     719       50467 :                         en = canditer_slice(&ci, 0, ci.ncand);
     720       50476 :                         if (en == NULL)
     721           0 :                                 goto error;
     722       50476 :                         *extents = en;
     723             :                 }
     724       50861 :                 if (histo) {
     725        1365 :                         hn = BATconstant(0, TYPE_lng, &(lng){1}, ci.ncand, TRANSIENT);
     726        1365 :                         if (hn == NULL)
     727           0 :                                 goto error;
     728        1365 :                         *histo = hn;
     729             :                 }
     730       50861 :                 bat_iterator_end(&bi);
     731       50867 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     732             :                           ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
     733             :                           ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
     734             :                           ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
     735             :                           ",histo=" ALGOOPTBATFMT " (1 element per group -- "
     736             :                           LLFMT " usec)\n",
     737             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOOPTBATPAR(g),
     738             :                           ALGOOPTBATPAR(e), ALGOOPTBATPAR(h),
     739             :                           subsorted ? "true" : "false", ALGOOPTBATPAR(gn),
     740             :                           ALGOOPTBATPAR(en), ALGOOPTBATPAR(hn), GDKusec() - t0);
     741       50867 :                 return GDK_SUCCEED;
     742             :         }
     743       43072 :         assert(!BATtdense(b));
     744       43072 :         if (g) {
     745        8127 :                 assert(!BATtdense(g));
     746        8127 :                 if (g->tsorted)
     747        5525 :                         maxgrp = * (oid *) Tloc(g, BATcount(g) - 1);
     748        2602 :                 else if (g->trevsorted)
     749           0 :                         maxgrp = * (oid *) Tloc(g, 0);
     750             :                 else {
     751             :                         /* group bats are not modified in parallel, so
     752             :                          * no need for locks */
     753        2602 :                         if (g->tmaxpos != BUN_NONE)
     754        2601 :                                 maxgrp = BUNtoid(g, g->tmaxpos);
     755        2608 :                         if (is_oid_nil(maxgrp) /* && BATcount(g) < 10240 */) {
     756           3 :                                 BATmax(g, &maxgrp);
     757             :                         }
     758             :                 }
     759        8133 :                 if (maxgrp == 0)
     760             :                         g = NULL; /* single group */
     761             :                 else
     762        6042 :                         grps = (const oid *) Tloc(g, 0);
     763             :         }
     764       43078 :         (void) BATordered(b);
     765       43397 :         (void) BATordered_rev(b);
     766       43368 :         bat_iterator_end(&bi);
     767       43314 :         bi = bat_iterator(b);
     768       43104 :         if (bi.sorted && bi.revsorted) {
     769             :                 /* all values are equal */
     770        4298 :                 if (g == NULL || (BATordered(g) && BATordered_rev(g))) {
     771             :                         /* there's only a single group: 0 */
     772        3892 :                         gn = BATconstant(hseqb, TYPE_oid, &(oid){0}, ci.ncand, TRANSIENT);
     773        3881 :                         if (gn == NULL)
     774           0 :                                 goto error;
     775        3881 :                         *groups = gn;
     776        3881 :                         if (extents) {
     777        2965 :                                 en = BATdense(0, canditer_next(&ci), 1);
     778        2970 :                                 if (en == NULL)
     779           0 :                                         goto error;
     780        2970 :                                 *extents = en;
     781             :                         }
     782        3886 :                         if (histo) {
     783          48 :                                 hn = BATconstant(0, TYPE_lng, &(lng){(lng)ci.ncand}, 1, TRANSIENT);
     784          48 :                                 if (hn == NULL)
     785           0 :                                         goto error;
     786          48 :                                 *histo = hn;
     787             :                         }
     788        3886 :                         bat_iterator_end(&bi);
     789        3887 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     790             :                                   ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
     791             :                                   ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
     792             :                                   ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
     793             :                                   ",histo=" ALGOOPTBATFMT " (single group -- "
     794             :                                   LLFMT " usec)\n",
     795             :                                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
     796             :                                   ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
     797             :                                   ALGOOPTBATPAR(h),
     798             :                                   subsorted ? "true" : "false",
     799             :                                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
     800             :                                   ALGOOPTBATPAR(hn), GDKusec() - t0);
     801        3887 :                         return GDK_SUCCEED;
     802             :                 }
     803         405 :                 if ((extents == NULL || e != NULL) &&
     804         134 :                     (histo == NULL || h != NULL) &&
     805         134 :                     ci.ncand == BATcount(b)) {
     806             :                         /* inherit given grouping; note that if
     807             :                          * extents/histo is to be returned, we need
     808             :                          * e/h available in order to copy them,
     809             :                          * otherwise we will need to calculate them
     810             :                          * which we will do using the "normal" case */
     811         134 :                         gn = COLcopy(g, g->ttype, false, TRANSIENT);
     812         134 :                         if (gn == NULL)
     813           0 :                                 goto error;
     814             : 
     815         134 :                         *groups = gn;
     816         134 :                         if (extents) {
     817           0 :                                 en = COLcopy(e, e->ttype, false, TRANSIENT);
     818           0 :                                 if (en == NULL)
     819           0 :                                         goto error;
     820           0 :                                 *extents = en;
     821             :                         }
     822         134 :                         if (histo) {
     823           0 :                                 hn = COLcopy(h, h->ttype, false, TRANSIENT);
     824           0 :                                 if (hn == NULL)
     825           0 :                                         goto error;
     826           0 :                                 *histo = hn;
     827             :                         }
     828         134 :                         bat_iterator_end(&bi);
     829         134 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     830             :                                   ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
     831             :                                   ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
     832             :                                   ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
     833             :                                   ",histo=" ALGOOPTBATFMT " (copy groups -- "
     834             :                                   LLFMT " usec)\n",
     835             :                                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
     836             :                                   ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
     837             :                                   ALGOOPTBATPAR(h),
     838             :                                   subsorted ? "true" : "false",
     839             :                                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
     840             :                                   ALGOOPTBATPAR(hn), GDKusec() - t0);
     841         134 :                         return GDK_SUCCEED;
     842             :                 }
     843             :         }
     844       39077 :         assert(g == NULL || !BATtdense(g)); /* i.e. g->ttype == TYPE_oid */
     845       39077 :         cmp = ATOMcompare(bi.type);
     846       39077 :         gn = COLnew(hseqb, TYPE_oid, ci.ncand, TRANSIENT);
     847       39316 :         if (gn == NULL)
     848           0 :                 goto error;
     849       39316 :         ngrps = (oid *) Tloc(gn, 0);
     850       39316 :         maxgrps = BUN_NONE;
     851       39316 :         MT_rwlock_rdlock(&b->thashlock);
     852       39362 :         if (b->thash && b->thash != (Hash *) 1)
     853           1 :                 maxgrps = b->thash->nunique;
     854       39362 :         MT_rwlock_rdunlock(&b->thashlock);
     855       39089 :         if (maxgrps == BUN_NONE) {
     856       39276 :                 if (bi.unique_est != 0) {
     857       32049 :                         maxgrps = (BUN) bi.unique_est;
     858       32049 :                         if (maxgrps > ci.ncand)
     859             :                                 maxgrps = ci.ncand;
     860             :                 } else
     861        7227 :                         maxgrps = ci.ncand / 10;
     862             :         }
     863       39089 :         if (!is_oid_nil(maxgrp) && maxgrps < maxgrp)
     864        1376 :                 maxgrps += maxgrp;
     865       39089 :         if (e && maxgrps < BATcount(e))
     866           1 :                 maxgrps += BATcount(e);
     867       39089 :         if (h && maxgrps < BATcount(h))
     868           0 :                 maxgrps += BATcount(h);
     869       39089 :         if (maxgrps < GROUPBATINCR)
     870             :                 maxgrps = GROUPBATINCR;
     871             : 
     872       39089 :         if (bi.width <= 2) {
     873        8605 :                 maxgrps = (BUN) 1 << (8 * bi.width);
     874        8605 :                 if (bi.width == 1 && maxgrp < 256)
     875         794 :                         maxgrps *= maxgrp;
     876             :         }
     877       39089 :         if (extents) {
     878       32617 :                 en = COLnew(0, TYPE_oid, maxgrps, TRANSIENT);
     879       32866 :                 if (en == NULL)
     880           0 :                         goto error;
     881       32866 :                 exts = (oid *) Tloc(en, 0);
     882             :         }
     883       39338 :         if (histo) {
     884        8356 :                 hn = COLnew(0, TYPE_lng, maxgrps, TRANSIENT);
     885        8357 :                 if (hn == NULL)
     886           0 :                         goto error;
     887        8357 :                 cnts = (lng *) Tloc(hn, 0);
     888             :         }
     889       39339 :         ngrp = 0;
     890       39339 :         BATsetcount(gn, ci.ncand);
     891             : 
     892       38965 :         hseqb = b->hseqbase; /* abbreviation */
     893             : 
     894             :         /* figure out if we can use the storage type also for
     895             :          * comparing values */
     896       38965 :         t = ATOMbasetype(bi.type);
     897             :         /* for strings we can use the offset instead of the actual
     898             :          * string values if we know that the strings in the string
     899             :          * heap are unique */
     900       38965 :         if (t == TYPE_str && GDK_ELIMDOUBLES(bi.vh)) {
     901        6260 :                 switch (bi.width) {
     902             :                 case 1:
     903             :                         t = TYPE_bte;
     904             :                         break;
     905        2892 :                 case 2:
     906        2892 :                         t = TYPE_sht;
     907        2892 :                         break;
     908          54 :                 case 4:
     909          54 :                         t = TYPE_int;
     910          54 :                         break;
     911             : #if SIZEOF_VAR_T == 8
     912           0 :                 case 8:
     913           0 :                         t = TYPE_lng;
     914           0 :                         break;
     915             : #endif
     916             :                 default:
     917           0 :                         MT_UNREACHABLE();
     918             :                 }
     919             :         }
     920             : 
     921       38965 :         if (g == NULL && t == TYPE_bte) {
     922             :                 /* byte-sized values, use 256 entry array to keep
     923             :                  * track of doled out group ids; note that we can't
     924             :                  * possibly have more than 256 groups, so the group id
     925             :                  * fits in a uint8_t */
     926     8543089 :                 GRP_small_values(8, 8, w[p]);
     927       36192 :         } else if (t == TYPE_bte && maxgrp < 256) {
     928             :                 /* subgrouping byte-sized values with a limited number
     929             :                  * of groups, use 65536 entry array to keep track of
     930             :                  * doled out group ids; note that we can't possibly have
     931             :                  * more than 65536 groups, so the group id fits in a
     932             :                  * uint16_t */
     933    18124218 :                 GRP_small_values(16, 8, (uint16_t) (w[p] | (grps[p] << 8)));
     934       35554 :         } else if (g == NULL && t == TYPE_sht) {
     935             :                 /* short-sized values, use 65536 entry array to keep
     936             :                  * track of doled out group ids; note that we can't
     937             :                  * possibly have more than 65536 groups, so the group
     938             :                  * id fits in a uint16_t */
     939     6965790 :                 GRP_small_values(16, 16, w[p]);
     940       31958 :         } else if (subsorted ||
     941       26518 :             ((bi.sorted || bi.revsorted) &&
     942         396 :              (g == NULL || BATordered(g) || BATordered_rev(g)))) {
     943             :                 /* we only need to compare each entry with the previous */
     944       18066 :                 algomsg = "compare consecutive values -- ";
     945       18066 :                 switch (t) {
     946         325 :                 case TYPE_bte:
     947      608760 :                         GRP_compare_consecutive_values_tpe(bte);
     948             :                         break;
     949         458 :                 case TYPE_sht:
     950      443189 :                         GRP_compare_consecutive_values_tpe(sht);
     951             :                         break;
     952       15788 :                 case TYPE_int:
     953    82260124 :                         GRP_compare_consecutive_values_tpe(int);
     954             :                         break;
     955        1333 :                 case TYPE_lng:
     956      784488 :                         GRP_compare_consecutive_values_tpe(lng);
     957             :                         break;
     958             : #ifdef HAVE_HGE
     959          68 :                 case TYPE_hge:
     960        4710 :                         GRP_compare_consecutive_values_tpe(hge);
     961             :                         break;
     962             : #endif
     963           9 :                 case TYPE_flt:
     964         108 :                         GRP_compare_consecutive_values_tpe(flt);
     965             :                         break;
     966          69 :                 case TYPE_dbl:
     967      385094 :                         GRP_compare_consecutive_values_tpe(dbl);
     968             :                         break;
     969          16 :                 default:
     970       34307 :                         GRP_compare_consecutive_values_any();
     971             :                         break;
     972             :                 }
     973             : 
     974       18403 :                 gn->tsorted = true;
     975       18403 :                 *groups = gn;
     976       13893 :         } else if (bi.sorted || bi.revsorted) {
     977         282 :                 BUN i, j;
     978         282 :                 BUN *pgrp;
     979             : 
     980         282 :                 assert(g);      /* if g == NULL or if there is a single */
     981         282 :                 assert(grps);   /* group, we used the code above */
     982             :                 /* for each value, we need to scan all previous equal
     983             :                  * values (a consecutive, possibly empty, range) to
     984             :                  * see if we can find one in the same old group
     985             :                  *
     986             :                  * we do this by maintaining for each old group the
     987             :                  * last time we saw that group, so if the last time we
     988             :                  * saw the old group of the current value is within
     989             :                  * this range, we can reuse the new group */
     990         282 :                 algomsg = "subscan old groups -- ";
     991             :                 /* determine how many old groups there are */
     992         282 :                 if (e) {
     993           0 :                         j = BATcount(e) + (BUN) e->hseqbase;
     994         282 :                 } else if (h) {
     995           0 :                         j = BATcount(h) + (BUN) h->hseqbase;
     996             :                 } else {
     997         282 :                         oid m = 0;
     998    23391784 :                         for (i = 0, j= BATcount(g); i < j; i++)
     999    23391502 :                                 m = MAX(m , grps[i]);
    1000         282 :                         j = (BUN) m + 1;
    1001             :                 }
    1002             :                 /* array to maintain last time we saw each old group */
    1003         282 :                 pgrp = GDKmalloc(sizeof(BUN) * j);
    1004         282 :                 if (pgrp == NULL)
    1005           0 :                         goto error;
    1006             :                 /* initialize to impossible position */
    1007         282 :                 memset(pgrp, ~0, sizeof(BUN) * j);
    1008             : 
    1009         282 :                 gn->tsorted = true; /* be optimistic */
    1010             : 
    1011         282 :                 switch (t) {
    1012           6 :                 case TYPE_bte:
    1013       57924 :                         GRP_subscan_old_groups_tpe(bte);
    1014             :                         break;
    1015           5 :                 case TYPE_sht:
    1016          62 :                         GRP_subscan_old_groups_tpe(sht);
    1017             :                         break;
    1018         259 :                 case TYPE_int:
    1019    23332208 :                         GRP_subscan_old_groups_tpe(int);
    1020             :                         break;
    1021           2 :                 case TYPE_lng:
    1022          98 :                         GRP_subscan_old_groups_tpe(lng);
    1023             :                         break;
    1024             : #ifdef HAVE_HGE
    1025           0 :                 case TYPE_hge:
    1026           0 :                         GRP_subscan_old_groups_tpe(hge);
    1027             :                         break;
    1028             : #endif
    1029           2 :                 case TYPE_flt:
    1030          26 :                         GRP_subscan_old_groups_tpe(flt);
    1031             :                         break;
    1032           8 :                 case TYPE_dbl:
    1033         346 :                         GRP_subscan_old_groups_tpe(dbl);
    1034             :                         break;
    1035           0 :                 default:
    1036           0 :                         GRP_subscan_old_groups_any();
    1037             :                         break;
    1038             :                 }
    1039             : 
    1040         282 :                 GDKfree(pgrp);
    1041       13611 :         } else if (g == NULL &&
    1042       11089 :                    (BATcheckhash(b) ||
    1043       11094 :                     ((!bi.transient ||
    1044       11094 :                       (b->batRole == PERSISTENT && GDKinmemory(0))) &&
    1045           0 :                      BAThash(b) == GDK_SUCCEED) ||
    1046             :                     (/* DISABLES CODE */ (0) &&
    1047             :                      (parent = VIEWtparent(b)) != 0 &&
    1048             : /* if enabled, need to fix/unfix parent bat */
    1049           0 :                      BATcheckhash(BBP_desc(parent))))) {
    1050             :                 /* we already have a hash table on b, or b is
    1051             :                  * persistent and we could create a hash table, or b
    1052             :                  * is a view on a bat that already has a hash table;
    1053             :                  * but don't do this if we're checking for subgroups
    1054             :                  * since we may have to go through long lists of
    1055             :                  * duplicates in the hash table to find an old
    1056             :                  * group */
    1057           0 :                 bool phash = false;
    1058           0 :                 algomsg = "existing hash -- ";
    1059           0 :                 MT_rwlock_rdlock(&b->thashlock);
    1060           0 :                 if (b->thash == NULL &&
    1061             :                     /* DISABLES CODE */ (0) &&
    1062             :                     (parent = VIEWtparent(b)) != 0) {
    1063             :                         /* b is a view on another bat (b2 for now).
    1064             :                          * calculate the bounds [lo, lo+BATcount(b))
    1065             :                          * in the parent that b uses */
    1066             : /* if enabled, need to fix/unfix parent bat */
    1067             :                         BAT *b2 = BBP_desc(parent);
    1068             :                         MT_rwlock_rdunlock(&b->thashlock);
    1069             :                         lo = b->tbaseoff - b2->tbaseoff;
    1070             :                         b = b2;
    1071             :                         bat_iterator_end(&bi);
    1072             :                         bi = bat_iterator(b);
    1073             :                         MT_rwlock_rdlock(&b->thashlock);
    1074             :                         algomsg = "existing parent hash -- ";
    1075             :                         phash = true;
    1076             :                 }
    1077           0 :                 hs = b->thash;
    1078           0 :                 if (hs == NULL) {
    1079           0 :                         MT_rwlock_rdunlock(&b->thashlock);
    1080           0 :                         goto lost_hash;
    1081             :                 }
    1082           0 :                 locked = true;
    1083           0 :                 gn->tsorted = true; /* be optimistic */
    1084             : 
    1085           0 :                 switch (t) {
    1086           0 :                 case TYPE_bte:
    1087           0 :                         GRP_use_existing_hash_table_tpe(bte);
    1088             :                         break;
    1089           0 :                 case TYPE_sht:
    1090           0 :                         GRP_use_existing_hash_table_tpe(sht);
    1091             :                         break;
    1092           0 :                 case TYPE_int:
    1093           0 :                         GRP_use_existing_hash_table_tpe(int);
    1094             :                         break;
    1095           0 :                 case TYPE_lng:
    1096           0 :                         GRP_use_existing_hash_table_tpe(lng);
    1097             :                         break;
    1098             : #ifdef HAVE_HGE
    1099           0 :                 case TYPE_hge:
    1100           0 :                         GRP_use_existing_hash_table_tpe(hge);
    1101             :                         break;
    1102             : #endif
    1103           0 :                 case TYPE_flt:
    1104           0 :                         GRP_use_existing_hash_table_tpe(flt);
    1105             :                         break;
    1106           0 :                 case TYPE_dbl:
    1107           0 :                         GRP_use_existing_hash_table_tpe(dbl);
    1108             :                         break;
    1109           0 :                 case TYPE_uuid:
    1110           0 :                         GRP_use_existing_hash_table_tpe(uuid);
    1111             :                         break;
    1112           0 :                 default:
    1113           0 :                         GRP_use_existing_hash_table_any();
    1114             :                         break;
    1115             :                 }
    1116           0 :                 MT_rwlock_rdunlock(&b->thashlock);
    1117           0 :                 locked = false;
    1118             :         } else {
    1119        2522 :                 bool gc;
    1120        2522 :                 const char *nme;
    1121        2522 :                 BUN prb;
    1122        2522 :                 int bits;
    1123        2522 :                 BUN nbucket;
    1124        2522 :                 oid grp;
    1125             : 
    1126        2522 :           lost_hash:
    1127        2522 :                 gc = g != NULL && (BATordered(g) || BATordered_rev(g));
    1128       13617 :                 bits = 0;
    1129       13617 :                 GDKclrerr();    /* not interested in BAThash errors */
    1130             : 
    1131             :                 /* not sorted, and no pre-existing hash table: we'll
    1132             :                  * build an incomplete hash table on the fly--also see
    1133             :                  * BATassertProps for similar code; we also exploit if
    1134             :                  * g is clustered */
    1135       13611 :                 algomsg = "new partial hash -- ";
    1136       13611 :                 nme = GDKinmemory(bi.h->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
    1137       13614 :                 if (grps && !gc) {
    1138             :                         /* we manipulate the hash value after having
    1139             :                          * calculated it, and when doing that, we
    1140             :                          * assume the mask (i.e. nbucket-1) is a
    1141             :                          * power-of-two minus one, so make sure it
    1142             :                          * is */
    1143        1948 :                         nbucket = ci.ncand | ci.ncand >> 1;
    1144        1948 :                         nbucket |= nbucket >> 2;
    1145        1948 :                         nbucket |= nbucket >> 4;
    1146        1948 :                         nbucket |= nbucket >> 8;
    1147        1948 :                         nbucket |= nbucket >> 16;
    1148             : #if SIZEOF_BUN == 8
    1149        1948 :                         nbucket |= nbucket >> 32;
    1150             : #endif
    1151        1948 :                         nbucket++;
    1152             :                 } else {
    1153       22161 :                         nbucket = MAX(HASHmask(ci.ncand), 1 << 16);
    1154             :                 }
    1155       13614 :                 if (grps == NULL || is_oid_nil(maxgrp)
    1156             : #if SIZEOF_OID == SIZEOF_LNG
    1157        2526 :                     || maxgrp >= ((oid) 1 << (SIZEOF_LNG * 8 - 8))
    1158             : #endif
    1159             :                         ) {
    1160       11088 :                         switch (t) {
    1161             :                         case TYPE_bte:
    1162       13614 :                                 nbucket = 256;
    1163             :                                 break;
    1164           0 :                         case TYPE_sht:
    1165           0 :                                 nbucket = 65536;
    1166           0 :                                 break;
    1167             :                         default:
    1168             :                                 break;
    1169             :                         }
    1170             :                 }
    1171             :                 /* nbucket is a power of two, so ctz(nbucket)
    1172             :                  * tells us which power of two */
    1173       13614 :                 bits = 8 * SIZEOF_OID - ctz(nbucket);
    1174       13614 :                 if ((hs = GDKzalloc(sizeof(Hash))) == NULL ||
    1175       13633 :                     (hs->heaplink.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0 ||
    1176       13628 :                     (hs->heapbckt.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0) {
    1177           0 :                         GDKfree(hs);
    1178           0 :                         hs = NULL;
    1179           0 :                         GDKerror("cannot allocate hash table\n");
    1180           0 :                         goto error;
    1181             :                 }
    1182       13630 :                 hs->heapbckt.parentid = b->batCacheid;
    1183       13630 :                 hs->heaplink.parentid = b->batCacheid;
    1184       13630 :                 if (snprintf(hs->heaplink.filename, sizeof(hs->heaplink.filename), "%s.thshgrpl%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heaplink.filename) ||
    1185       27249 :                     snprintf(hs->heapbckt.filename, sizeof(hs->heapbckt.filename), "%s.thshgrpb%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heapbckt.filename) ||
    1186       13629 :                     HASHnew(hs, bi.type, BATcount(b), nbucket, BUN_NONE, false) != GDK_SUCCEED) {
    1187           9 :                         GDKfree(hs);
    1188           0 :                         hs = NULL;
    1189           0 :                         GDKerror("cannot allocate hash table\n");
    1190           0 :                         goto error;
    1191             :                 }
    1192       13621 :                 gn->tsorted = true; /* be optimistic */
    1193             : 
    1194       13621 :                 switch (t) {
    1195          17 :                 case TYPE_bte:
    1196          17 :                         if (grps && !is_oid_nil(maxgrp)
    1197             : #if SIZEOF_OID == SIZEOF_LNG
    1198          17 :                             && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 8))
    1199             : #endif
    1200             :                                 ) {
    1201          17 :                                 ulng v;
    1202          17 :                                 const bte *w = (bte *) bi.base;
    1203      158078 :                                 GRP_create_partial_hash_table_core(
    1204             :                                         (void) 0,
    1205             :                                         (v = ((ulng)grps[r]<<8)|(uint8_t)w[p], hash_lng(hs, &v)),
    1206             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1207             :                                         (void) 0,
    1208             :                                         NOGRPTST);
    1209             :                         } else
    1210           0 :                                 GRP_create_partial_hash_table_tpe(bte);
    1211             :                         break;
    1212         790 :                 case TYPE_sht:
    1213         790 :                         if (grps && !is_oid_nil(maxgrp)
    1214             : #if SIZEOF_OID == SIZEOF_LNG
    1215         790 :                             && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 16))
    1216             : #endif
    1217             :                                 ) {
    1218         790 :                                 ulng v;
    1219         790 :                                 const sht *w = (sht *) bi.base;
    1220    29003705 :                                 GRP_create_partial_hash_table_core(
    1221             :                                         (void) 0,
    1222             :                                         (v = ((ulng)grps[r]<<16)|(uint16_t)w[p], hash_lng(hs, &v)),
    1223             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1224             :                                         (void) 0,
    1225             :                                         NOGRPTST);
    1226             :                         } else
    1227           0 :                                 GRP_create_partial_hash_table_tpe(sht);
    1228             :                         break;
    1229       12139 :                 case TYPE_int:
    1230       12139 :                         if (grps && !is_oid_nil(maxgrp)
    1231             : #if SIZEOF_OID == SIZEOF_LNG
    1232        1439 :                             && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 32))
    1233             : #endif
    1234             :                                 ) {
    1235        1439 :                                 ulng v;
    1236        1439 :                                 const int *w = (int *) bi.base;
    1237   120417954 :                                 GRP_create_partial_hash_table_core(
    1238             :                                         (void) 0,
    1239             :                                         (v = ((ulng)grps[r]<<32)|(unsigned int)w[p], hash_lng(hs, &v)),
    1240             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1241             :                                         (void) 0,
    1242             :                                         NOGRPTST);
    1243             :                         } else
    1244    78925027 :                                 GRP_create_partial_hash_table_tpe(int);
    1245             :                         break;
    1246         184 :                 case TYPE_lng:
    1247             : #ifdef HAVE_HGE
    1248         184 :                         if (grps) {
    1249          16 :                                 uhge v;
    1250          16 :                                 const lng *w = (lng *) bi.base;
    1251     2068503 :                                 GRP_create_partial_hash_table_core(
    1252             :                                         (void) 0,
    1253             :                                         (v = ((uhge)grps[r]<<64)|(ulng)w[p], hash_hge(hs, &v)),
    1254             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1255             :                                         (void) 0,
    1256             :                                         NOGRPTST);
    1257             :                         } else
    1258             : #endif
    1259       90399 :                                 GRP_create_partial_hash_table_tpe(lng);
    1260             :                         break;
    1261             : #ifdef HAVE_HGE
    1262          21 :                 case TYPE_hge:
    1263    57803697 :                         GRP_create_partial_hash_table_tpe(hge);
    1264             :                         break;
    1265             : #endif
    1266          22 :                 case TYPE_flt:
    1267         724 :                         GRP_create_partial_hash_table_tpe(flt);
    1268             :                         break;
    1269         116 :                 case TYPE_dbl:
    1270        5491 :                         GRP_create_partial_hash_table_tpe(dbl);
    1271             :                         break;
    1272           8 :                 case TYPE_uuid:
    1273          86 :                         GRP_create_partial_hash_table_tpe(uuid);
    1274             :                         break;
    1275         324 :                 default:
    1276    72153666 :                         GRP_create_partial_hash_table_any();
    1277             :                 }
    1278             : 
    1279       13629 :                 HEAPfree(&hs->heapbckt, true);
    1280       13630 :                 HEAPfree(&hs->heaplink, true);
    1281       13631 :                 GDKfree(hs);
    1282             :         }
    1283       39315 :         bat_iterator_end(&bi);
    1284       39123 :         if (extents) {
    1285       32689 :                 BATsetcount(en, (BUN) ngrp);
    1286       32714 :                 en->tkey = true;
    1287       32714 :                 en->tsorted = true;
    1288       32714 :                 en->trevsorted = ngrp == 1;
    1289       32714 :                 en->tnonil = true;
    1290       32714 :                 en->tnil = false;
    1291       32714 :                 en->tunique_est = (double)ngrp;
    1292       32714 :                 *extents = virtualize(en);
    1293             :         }
    1294       39137 :         if (histo) {
    1295        8357 :                 BATsetcount(hn, (BUN) ngrp);
    1296        8357 :                 if (ngrp == ci.ncand || ngrp == 1) {
    1297        5921 :                         hn->tkey = ngrp == 1;
    1298        5921 :                         hn->tsorted = true;
    1299        5921 :                         hn->trevsorted = true;
    1300             :                 } else {
    1301        2436 :                         hn->tkey = false;
    1302        2436 :                         hn->tsorted = false;
    1303        2436 :                         hn->trevsorted = false;
    1304             :                 }
    1305        8357 :                 hn->tnonil = true;
    1306        8357 :                 hn->tnil = false;
    1307        8357 :                 *histo = hn;
    1308             :         }
    1309       39137 :         gn->tkey = ngrp == BATcount(gn);
    1310       39137 :         gn->trevsorted = ngrp == 1 || BATcount(gn) <= 1;
    1311       39137 :         gn->tnonil = true;
    1312       39137 :         gn->tnil = false;
    1313       39137 :         gn->tmaxpos = maxgrppos;
    1314       39137 :         gn->tunique_est = (double)ngrp;
    1315       39137 :         *groups = gn;
    1316       39137 :         if (!g && !e && !s) {
    1317       33303 :                 b->tunique_est = (double)ngrp;
    1318             :         }
    1319       39137 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1320             :                   ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
    1321             :                   ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
    1322             :                   ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
    1323             :                   ",histo=" ALGOOPTBATFMT " (%s" LLFMT " usec)\n",
    1324             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
    1325             :                   ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
    1326             :                   ALGOOPTBATPAR(h),
    1327             :                   subsorted ? "true" : "false",
    1328             :                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
    1329             :                   ALGOOPTBATPAR(hn), algomsg, GDKusec() - t0);
    1330             :         return GDK_SUCCEED;
    1331           0 :   error:
    1332           0 :         bat_iterator_end(&bi);
    1333           0 :         if (hs != NULL && hs != b->thash) {
    1334           0 :                 HEAPfree(&hs->heaplink, true);
    1335           0 :                 HEAPfree(&hs->heapbckt, true);
    1336           0 :                 GDKfree(hs);
    1337             :         }
    1338           0 :         if (locked)
    1339           0 :                 MT_rwlock_rdunlock(&b->thashlock);
    1340           0 :         BBPreclaim(gn);
    1341           0 :         BBPreclaim(en);
    1342           0 :         BBPreclaim(hn);
    1343             :         return GDK_FAIL;
    1344             : }
    1345             : 
    1346             : gdk_return
    1347       85992 : BATgroup(BAT **groups, BAT **extents, BAT **histo,
    1348             :          BAT *b, BAT *s, BAT *g, BAT *e, BAT *h)
    1349             : {
    1350       85992 :         return BATgroup_internal(groups, extents, histo, b, s, g, e, h, false);
    1351             : }

Generated by: LCOV version 1.14