LCOV - code coverage report
Current view: top level - gdk - gdk_group.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 303 394 76.9 %
Date: 2021-10-13 02:24:04 Functions: 3 3 100.0 %

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

Generated by: LCOV version 1.14