LCOV - code coverage report
Current view: top level - gdk - gdk_group.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 311 404 77.0 %
Date: 2021-09-14 19:48:19 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             :                                 for (r = 0; r < cnt; r++) {          \
     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             :                         } else {                                        \
     119             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, dense, !groups"); \
     120             :                                 for (r = 0; r < cnt; r++) {          \
     121             :                                         p = canditer_next_dense(&ci) - hseqb; \
     122             :                                         INIT_1;                         \
     123             :                                         if (ngrp == 0 || DIFFER) {      \
     124             :                                                 GRPnotfound();          \
     125             :                                         } else {                        \
     126             :                                                 ngrps[r] = ngrp - 1;    \
     127             :                                                 if (histo)              \
     128             :                                                         cnts[ngrp - 1]++; \
     129             :                                         }                               \
     130             :                                         KEEP;                           \
     131             :                                 }                                       \
     132             :                         }                                               \
     133             :                 } else {                                                \
     134             :                         if (grps) {                                     \
     135             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, groups"); \
     136             :                                 for (r = 0; r < cnt; r++) {          \
     137             :                                         p = canditer_next(&ci) - hseqb;     \
     138             :                                         INIT_1;                         \
     139             :                                         if (ngrp == 0 || grps[r] != prev || DIFFER) { \
     140             :                                                 GRPnotfound();          \
     141             :                                         } else {                        \
     142             :                                                 ngrps[r] = ngrp - 1;    \
     143             :                                                 if (histo)              \
     144             :                                                         cnts[ngrp - 1]++; \
     145             :                                         }                               \
     146             :                                         KEEP;                           \
     147             :                                         prev = grps[r];                 \
     148             :                                 }                                       \
     149             :                         } else {                                        \
     150             :                                 MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, !groups"); \
     151             :                                 for (r = 0; r < cnt; r++) {          \
     152             :                                         p = canditer_next(&ci) - hseqb;     \
     153             :                                         INIT_1;                         \
     154             :                                         if (ngrp == 0 || DIFFER) {      \
     155             :                                                 GRPnotfound();          \
     156             :                                         } else {                        \
     157             :                                                 ngrps[r] = ngrp - 1;    \
     158             :                                                 if (histo)              \
     159             :                                                         cnts[ngrp - 1]++; \
     160             :                                         }                               \
     161             :                                         KEEP;                           \
     162             :                                 }                                       \
     163             :                         }                                               \
     164             :                 }                                                       \
     165             :         } while(0)
     166             : 
     167             : #define flt_neq(a, b)   (is_flt_nil(a) ? !is_flt_nil(b) : is_flt_nil(b) || (a) != (b))
     168             : #define dbl_neq(a, b)   (is_dbl_nil(a) ? !is_dbl_nil(b) : is_dbl_nil(b) || (a) != (b))
     169             : #define bte_neq(a, b)   ((a) != (b))
     170             : #define sht_neq(a, b)   ((a) != (b))
     171             : #define int_neq(a, b)   ((a) != (b))
     172             : #define lng_neq(a, b)   ((a) != (b))
     173             : #define hge_neq(a, b)   ((a) != (b))
     174             : 
     175             : #define GRP_compare_consecutive_values_tpe(TYPE)                \
     176             :         GRP_compare_consecutive_values(                         \
     177             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base;       \
     178             :                         TYPE pw = 0                     ,       \
     179             :         /* INIT_1 */                                    ,       \
     180             :         /* DIFFER */    TYPE##_neq(w[p], pw)            ,       \
     181             :         /* KEEP   */    pw = w[p]                               \
     182             :         )
     183             : 
     184             : #define GRP_compare_consecutive_values_any()                    \
     185             :         GRP_compare_consecutive_values(                         \
     186             :         /* INIT_0 */    pv = NULL                       ,       \
     187             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     188             :         /* DIFFER */    cmp(v, pv) != 0                 ,       \
     189             :         /* KEEP   */    pv = v                                  \
     190             :         )
     191             : 
     192             : 
     193             : #define GRP_subscan_old_groups(INIT_0,INIT_1,EQUAL,KEEP)                \
     194             :         do {                                                            \
     195             :                 INIT_0;                                                 \
     196             :                 pgrp[grps[0]] = 0;                                      \
     197             :                 j = 0;                                                  \
     198             :                 if (ci.tpe == cand_dense) {                             \
     199             :                         MT_thread_setalgorithm("GRP_subscan_old_groups, dense"); \
     200             :                         for (r = 0; r < cnt; r++) {                  \
     201             :                                 p = canditer_next_dense(&ci) - hseqb;       \
     202             :                                 INIT_1;                                 \
     203             :                                 if (ngrp != 0 && EQUAL) {               \
     204             :                                         /* range [j, r) is all same value */ \
     205             :                                         /* i is position where we saw r's */ \
     206             :                                         /* old group last */            \
     207             :                                         i = pgrp[grps[r]];              \
     208             :                                         /* p is new position where we saw this \
     209             :                                          * group */                     \
     210             :                                         pgrp[grps[r]] = r;              \
     211             :                                         if (j <= i && i < r)      {       \
     212             :                                                 /* i is position of equal */ \
     213             :                                                 /* value in same old group */ \
     214             :                                                 /* as r, so r gets same new */ \
     215             :                                                 /* group as i */        \
     216             :                                                 oid grp = ngrps[i];     \
     217             :                                                 ngrps[r] = grp;         \
     218             :                                                 if (histo)              \
     219             :                                                         cnts[grp]++;    \
     220             :                                                 if (gn->tsorted &&   \
     221             :                                                     grp != ngrp - 1)    \
     222             :                                                         gn->tsorted = false; \
     223             :                                                 /* we found the value/group */ \
     224             :                                                 /* combination, go to next */ \
     225             :                                                 /* value */             \
     226             :                                                 continue;               \
     227             :                                         }                               \
     228             :                                 } else {                                \
     229             :                                         /* value differs from previous value */ \
     230             :                                         /* (or is the first) */         \
     231             :                                         j = r;                          \
     232             :                                         KEEP;                           \
     233             :                                         pgrp[grps[r]] = r;              \
     234             :                                 }                                       \
     235             :                                 /* start a new group */                 \
     236             :                                 GRPnotfound();                          \
     237             :                         }                                               \
     238             :                 } else {                                                \
     239             :                         MT_thread_setalgorithm("GRP_subscan_old_groups, !dense"); \
     240             :                         for (r = 0; r < cnt; r++) {                  \
     241             :                                 p = canditer_next(&ci) - hseqb;             \
     242             :                                 INIT_1;                                 \
     243             :                                 if (ngrp != 0 && EQUAL) {               \
     244             :                                         /* range [j, r) is all same value */ \
     245             :                                         /* i is position where we saw r's */ \
     246             :                                         /* old group last */            \
     247             :                                         i = pgrp[grps[r]];              \
     248             :                                         /* p is new position where we saw this \
     249             :                                          * group */                     \
     250             :                                         pgrp[grps[r]] = r;              \
     251             :                                         if (j <= i && i < r)      {       \
     252             :                                                 /* i is position of equal */ \
     253             :                                                 /* value in same old group */ \
     254             :                                                 /* as r, so r gets same new */ \
     255             :                                                 /* group as i */        \
     256             :                                                 oid grp = ngrps[i];     \
     257             :                                                 ngrps[r] = grp;         \
     258             :                                                 if (histo)              \
     259             :                                                         cnts[grp]++;    \
     260             :                                                 if (gn->tsorted &&   \
     261             :                                                     grp != ngrp - 1)    \
     262             :                                                         gn->tsorted = false; \
     263             :                                                 /* we found the value/group */ \
     264             :                                                 /* combination, go to next */ \
     265             :                                                 /* value */             \
     266             :                                                 continue;               \
     267             :                                         }                               \
     268             :                                 } else {                                \
     269             :                                         /* value differs from previous value */ \
     270             :                                         /* (or is the first) */         \
     271             :                                         j = r;                          \
     272             :                                         KEEP;                           \
     273             :                                         pgrp[grps[r]] = r;              \
     274             :                                 }                                       \
     275             :                                 /* start a new group */                 \
     276             :                                 GRPnotfound();                          \
     277             :                         }                                               \
     278             :                 }                                                       \
     279             :         } while(0)
     280             : 
     281             : #define flt_equ(a, b)   (is_flt_nil(a) ? is_flt_nil(b) : !is_flt_nil(b) && (a) == (b))
     282             : #define dbl_equ(a, b)   (is_dbl_nil(a) ? is_dbl_nil(b) : !is_dbl_nil(b) && (a) == (b))
     283             : #define bte_equ(a, b)   ((a) == (b))
     284             : #define sht_equ(a, b)   ((a) == (b))
     285             : #define int_equ(a, b)   ((a) == (b))
     286             : #define lng_equ(a, b)   ((a) == (b))
     287             : #define hge_equ(a, b)   ((a) == (b))
     288             : #ifdef HAVE_HGE
     289             : #define uuid_equ(a, b)  ((a).h == (b).h)
     290             : #else
     291             : #ifdef HAVE_UUID
     292             : #define uuid_equ(a, b)  (uuid_compare((a).u, (b).u) == 0)
     293             : #else
     294             : #define uuid_equ(a, b)  (memcmp((a).u, (b).u, UUID_SIZE) == 0)
     295             : #endif
     296             : #endif
     297             : 
     298             : #define GRP_subscan_old_groups_tpe(TYPE)                        \
     299             :         GRP_subscan_old_groups(                                 \
     300             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base;       \
     301             :                         TYPE pw = 0                     ,       \
     302             :         /* INIT_1 */                                    ,       \
     303             :         /* EQUAL  */    TYPE##_equ(w[p], pw)            ,       \
     304             :         /* KEEP   */    pw = w[p]                               \
     305             :         )
     306             : 
     307             : #define GRP_subscan_old_groups_any()                            \
     308             :         GRP_subscan_old_groups(                                 \
     309             :         /* INIT_0 */    pv = NULL                       ,       \
     310             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     311             :         /* EQUAL  */    cmp(v, pv) == 0                 ,       \
     312             :         /* KEEP   */    pv = v                                  \
     313             :         )
     314             : 
     315             : /* If a hash table exists on b we use it.
     316             :  *
     317             :  * The algorithm is simple.  We go through b and for each value we
     318             :  * follow the hash chain starting at the next element after that value
     319             :  * to find one that is equal to the value we're currently looking at.
     320             :  * If we found such a value, we add the value to the same group.  If
     321             :  * we reach the end of the chain, we create a new group.
     322             :  *
     323             :  * If b (the original, that is) is a view on another BAT, and this
     324             :  * other BAT has a hash, we use that.  The lo and hi values are the
     325             :  * bounds of the parent BAT that we're considering.
     326             :  *
     327             :  * Note this algorithm depends critically on the fact that our hash
     328             :  * chains go from higher to lower BUNs.
     329             :  */
     330             : #define GRP_use_existing_hash_table(INIT_0,INIT_1,EQUAL)                \
     331             :         do {                                                            \
     332             :                 INIT_0;                                                 \
     333             :                 assert(grps == NULL);                                   \
     334             :                 if (ci.tpe == cand_dense) {                             \
     335             :                         MT_thread_setalgorithm(phash ? "GRP_use_existing_hash_table, dense, parent hash" : "GRP_use_existing_hash_table, dense"); \
     336             :                         for (r = 0; r < cnt; r++) {                  \
     337             :                                 oid o = canditer_next_dense(&ci);   \
     338             :                                 p = o - hseqb + lo;                     \
     339             :                                 INIT_1;                                 \
     340             :                                 /* this loop is similar, but not */     \
     341             :                                 /* equal, to HASHloop: the difference */ \
     342             :                                 /* is that we only consider BUNs */     \
     343             :                                 /* smaller than the one we're looking */ \
     344             :                                 /* up (p) */                            \
     345             :                                 for (hb = HASHgetlink(hs, p);           \
     346             :                                      hb != BUN_NONE && hb >= lo;     \
     347             :                                      hb = HASHgetlink(hs, hb)) {        \
     348             :                                         oid grp;                        \
     349             :                                         assert(hb < p);                      \
     350             :                                         q = canditer_search_dense(&ci, hb + hseqb - lo, false); \
     351             :                                         if (q == BUN_NONE)              \
     352             :                                                 continue;               \
     353             :                                         if (EQUAL) {                    \
     354             :                                                 grp = ngrps[q];         \
     355             :                                                 ngrps[r] = grp;         \
     356             :                                                 if (histo)              \
     357             :                                                         cnts[grp]++;    \
     358             :                                                 if (gn->tsorted &&   \
     359             :                                                     grp != ngrp - 1)    \
     360             :                                                         gn->tsorted = false; \
     361             :                                                 break;                  \
     362             :                                         }                               \
     363             :                                 }                                       \
     364             :                                 if (hb == BUN_NONE || hb < lo) {     \
     365             :                                         GRPnotfound();                  \
     366             :                                 }                                       \
     367             :                         }                                               \
     368             :                 } else {                                                \
     369             :                         MT_thread_setalgorithm(phash ? "GRP_use_existing_hash_table, !dense, parent hash" : "GRP_use_existing_hash_table, !dense"); \
     370             :                         for (r = 0; r < cnt; r++) {                  \
     371             :                                 oid o = canditer_next(&ci);         \
     372             :                                 p = o - hseqb + lo;                     \
     373             :                                 INIT_1;                                 \
     374             :                                 /* this loop is similar, but not */     \
     375             :                                 /* equal, to HASHloop: the difference */ \
     376             :                                 /* is that we only consider BUNs */     \
     377             :                                 /* smaller than the one we're looking */ \
     378             :                                 /* up (p) */                            \
     379             :                                 for (hb = HASHgetlink(hs, p);           \
     380             :                                      hb != BUN_NONE && hb >= lo;     \
     381             :                                      hb = HASHgetlink(hs, hb)) {        \
     382             :                                         oid grp;                        \
     383             :                                         assert(hb < p);                      \
     384             :                                         q = canditer_search(&ci, hb + hseqb - lo, false); \
     385             :                                         if (q == BUN_NONE)              \
     386             :                                                 continue;               \
     387             :                                         if (EQUAL) {                    \
     388             :                                                 grp = ngrps[q];         \
     389             :                                                 ngrps[r] = grp;         \
     390             :                                                 if (histo)              \
     391             :                                                         cnts[grp]++;    \
     392             :                                                 if (gn->tsorted &&   \
     393             :                                                     grp != ngrp - 1)    \
     394             :                                                         gn->tsorted = false; \
     395             :                                                 break;                  \
     396             :                                         }                               \
     397             :                                 }                                       \
     398             :                                 if (hb == BUN_NONE || hb < lo) {     \
     399             :                                         GRPnotfound();                  \
     400             :                                 }                                       \
     401             :                         }                                               \
     402             :                 }                                                       \
     403             :         } while(0)
     404             : 
     405             : #define GRP_use_existing_hash_table_tpe(TYPE)                   \
     406             :         GRP_use_existing_hash_table(                            \
     407             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base,       \
     408             :         /* INIT_1 */                                    ,       \
     409             :         /* EQUAL  */    TYPE##_equ(w[p], w[hb])                 \
     410             :         )
     411             : 
     412             : #define GRP_use_existing_hash_table_any()                       \
     413             :         GRP_use_existing_hash_table(                            \
     414             :         /* INIT_0 */                                    ,       \
     415             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     416             :         /* EQUAL  */    cmp(v, BUNtail(bi, hb)) == 0            \
     417             :         )
     418             : 
     419             : /* reverse the bits of an OID value */
     420             : static inline oid
     421    41741088 : rev(oid x)
     422             : {
     423             : #if SIZEOF_OID == 8
     424    41741088 :         x = ((x & 0x5555555555555555) <<  1) | ((x >>  1) & 0x5555555555555555);
     425    41741088 :         x = ((x & 0x3333333333333333) <<  2) | ((x >>  2) & 0x3333333333333333);
     426    41741088 :         x = ((x & 0x0F0F0F0F0F0F0F0F) <<  4) | ((x >>  4) & 0x0F0F0F0F0F0F0F0F);
     427    41741088 :         x = ((x & 0x00FF00FF00FF00FF) <<  8) | ((x >>  8) & 0x00FF00FF00FF00FF);
     428    41741088 :         x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF0000FFFF);
     429    41741088 :         x = ((x & 0x00000000FFFFFFFF) << 32) | ((x >> 32) & 0x00000000FFFFFFFF);
     430             : #else
     431             :         x = ((x & 0x55555555) <<  1) | ((x >>  1) & 0x55555555);
     432             :         x = ((x & 0x33333333) <<  2) | ((x >>  2) & 0x33333333);
     433             :         x = ((x & 0x0F0F0F0F) <<  4) | ((x >>  4) & 0x0F0F0F0F);
     434             :         x = ((x & 0x00FF00FF) <<  8) | ((x >>  8) & 0x00FF00FF);
     435             :         x = ((x & 0x0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF);
     436             : #endif
     437    41741088 :         return x;
     438             : }
     439             : 
     440             : /* count trailing zeros, also see candmask_lobit in gdk_cand.h */
     441             : static inline int __attribute__((__const__))
     442             : ctz(oid x)
     443             : {
     444             : #if defined(__GNUC__)
     445             : #if SIZEOF_OID == SIZEOF_INT
     446             :         return __builtin_ctz(x);
     447             : #else
     448       16569 :         return __builtin_ctzl(x);
     449             : #endif
     450             : #elif defined(_MSC_VER)
     451             : #if SIZEOF_OID == SIZEOF_INT
     452             :         unsigned long idx;
     453             :         if (_BitScanForward(&idx, (unsigned long) x))
     454             :                 return (int) idx;
     455             : #else
     456             :         unsigned long idx;
     457             :         if (_BitScanForward64(&idx, (unsigned __int64) x))
     458             :                 return (int) idx;
     459             : #endif
     460             :         return -1;
     461             : #else
     462             :         /* use binary search for the lowest set bit */
     463             :         int n = 1;
     464             : #if SIZEOF_OID == SIZEOF_INT
     465             :         if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
     466             :         if ((x & 0x000000FF) == 0) { n +=  8; x >>=  8; }
     467             :         if ((x & 0x0000000F) == 0) { n +=  4; x >>=  4; }
     468             :         if ((x & 0x00000003) == 0) { n +=  2; x >>=  2; }
     469             : #else
     470             :         if ((x & UINT64_C(0x00000000FFFFFFFF)) == 0) { n += 32; x >>= 32; }
     471             :         if ((x & UINT64_C(0x000000000000FFFF)) == 0) { n += 16; x >>= 16; }
     472             :         if ((x & UINT64_C(0x00000000000000FF)) == 0) { n +=  8; x >>=  8; }
     473             :         if ((x & UINT64_C(0x000000000000000F)) == 0) { n +=  4; x >>=  4; }
     474             :         if ((x & UINT64_C(0x0000000000000003)) == 0) { n +=  2; x >>=  2; }
     475             : #endif
     476             :         return n - (x & 1);
     477             : #endif
     478             : }
     479             : 
     480             : #define GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,ASSERT,GRPTST) \
     481             :         do {                                                            \
     482             :                 if (ci.tpe == cand_dense) {                             \
     483             :                         MT_thread_setalgorithm("GRP_create_partial_hash_table, dense"); \
     484             :                         for (r = 0; r < cnt; r++) {                  \
     485             :                                 p = canditer_next_dense(&ci) - hseqb;       \
     486             :                                 INIT_1;                                 \
     487             :                                 prb = HASH;                             \
     488             :                                 for (hb = HASHget(hs, prb);             \
     489             :                                      hb != BUN_NONE;                    \
     490             :                                      hb = HASHgetlink(hs, hb)) {        \
     491             :                                         ASSERT;                         \
     492             :                                         q = canditer_search_dense(&ci, hb + hseqb, false); \
     493             :                                         if (q == BUN_NONE)              \
     494             :                                                 continue;               \
     495             :                                         GRPTST(q, r);                   \
     496             :                                         if (EQUAL) {                    \
     497             :                                                 grp = ngrps[q];         \
     498             :                                                 ngrps[r] = grp;         \
     499             :                                                 if (histo)              \
     500             :                                                         cnts[grp]++;    \
     501             :                                                 if (gn->tsorted &&   \
     502             :                                                     grp != ngrp - 1)    \
     503             :                                                         gn->tsorted = false; \
     504             :                                                 break;                  \
     505             :                                         }                               \
     506             :                                 }                                       \
     507             :                                 if (hb == BUN_NONE) {                   \
     508             :                                         GRPnotfound();                  \
     509             :                                         /* enter new group into hash table */ \
     510             :                                         HASHputlink(hs, p, HASHget(hs, prb)); \
     511             :                                         HASHput(hs, prb, p);            \
     512             :                                 }                                       \
     513             :                         }                                               \
     514             :                 } else {                                                \
     515             :                         MT_thread_setalgorithm("GRP_create_partial_hash_table, !dense"); \
     516             :                         for (r = 0; r < cnt; r++) {                  \
     517             :                                 p = canditer_next(&ci) - hseqb;             \
     518             :                                 INIT_1;                                 \
     519             :                                 prb = HASH;                             \
     520             :                                 for (hb = HASHget(hs, prb);             \
     521             :                                      hb != BUN_NONE;                    \
     522             :                                      hb = HASHgetlink(hs, hb)) {        \
     523             :                                         ASSERT;                         \
     524             :                                         q = canditer_search(&ci, hb + hseqb, false); \
     525             :                                         if (q == BUN_NONE)              \
     526             :                                                 continue;               \
     527             :                                         GRPTST(q, r);                   \
     528             :                                         if (EQUAL) {                    \
     529             :                                                 grp = ngrps[q];         \
     530             :                                                 ngrps[r] = grp;         \
     531             :                                                 if (histo)              \
     532             :                                                         cnts[grp]++;    \
     533             :                                                 if (gn->tsorted &&   \
     534             :                                                     grp != ngrp - 1)    \
     535             :                                                         gn->tsorted = false; \
     536             :                                                 break;                  \
     537             :                                         }                               \
     538             :                                 }                                       \
     539             :                                 if (hb == BUN_NONE) {                   \
     540             :                                         GRPnotfound();                  \
     541             :                                         /* enter new group into hash table */ \
     542             :                                         HASHputlink(hs, p, HASHget(hs, prb)); \
     543             :                                         HASHput(hs, prb, p);            \
     544             :                                 }                                       \
     545             :                         }                                               \
     546             :                 }                                                       \
     547             :         } while (0)
     548             : #define GCGRPTST(i, j)  if (grps[i] != grps[j]) { hb = BUN_NONE; break; }
     549             : #define GRPTST(i, j)    if (grps[i] != grps[j]) continue
     550             : #define NOGRPTST(i, j)  (void) 0
     551             : #define GRP_create_partial_hash_table(INIT_0,INIT_1,HASH,EQUAL)         \
     552             :         do {                                                            \
     553             :                 INIT_0;                                                 \
     554             :                 if (grps) {                                             \
     555             :                         if (gc) {                                       \
     556             :                                 GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,assert(HASHgetlink(hs, hb) == BUN_NONE || HASHgetlink(hs, hb) < hb),GCGRPTST); \
     557             :                         } else {                                        \
     558             :                                 GRP_create_partial_hash_table_core(INIT_1,HASH ^ (rev(grps[r]) >> bits),EQUAL,(void)0,GRPTST); \
     559             :                         }                                               \
     560             :                 } else {                                                \
     561             :                         GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,(void)0,NOGRPTST); \
     562             :                 }                                                       \
     563             :         } while (0)
     564             : 
     565             : #define GRP_create_partial_hash_table_tpe(TYPE)                 \
     566             :         GRP_create_partial_hash_table(                          \
     567             :         /* INIT_0 */    const TYPE *w = (TYPE *) bi.base,       \
     568             :         /* INIT_1 */                                    ,       \
     569             :         /* HASH   */    hash_##TYPE(hs, &w[p])              ,       \
     570             :         /* EQUAL  */    TYPE##_equ(w[p], w[hb])                 \
     571             :         )
     572             : 
     573             : #define GRP_create_partial_hash_table_any()                     \
     574             :         GRP_create_partial_hash_table(                          \
     575             :         /* INIT_0 */                                    ,       \
     576             :         /* INIT_1 */    v = BUNtail(bi, p)              ,       \
     577             :         /* HASH   */    hash_any(hs, v)                 ,       \
     578             :         /* EQUAL  */    cmp(v, BUNtail(bi, hb)) == 0            \
     579             :         )
     580             : 
     581             : 
     582             : gdk_return
     583      101581 : BATgroup_internal(BAT **groups, BAT **extents, BAT **histo,
     584             :                   BAT *b, BAT *s, BAT *g, BAT *e, BAT *h, bool subsorted)
     585             : {
     586             :         BAT *gn = NULL, *en = NULL, *hn = NULL;
     587             :         int t;
     588             :         int (*cmp)(const void *, const void *);
     589             :         const oid *grps = NULL;
     590             :         oid *restrict ngrps, ngrp, prev = 0, hseqb = 0;
     591             :         oid *restrict exts = NULL;
     592             :         lng *restrict cnts = NULL;
     593             :         BUN p, q, r;
     594             :         const void *v, *pv;
     595             :         BATiter bi;
     596             :         Hash *hs = NULL;
     597             :         BUN hb;
     598             :         BUN maxgrps;
     599             :         BUN maxgrppos = BUN_NONE;
     600             :         bat parent;
     601             :         BUN cnt;
     602             :         BUN lo = 0;
     603             :         struct canditer ci;
     604      101581 :         oid maxgrp = oid_nil;   /* maximum value of g BAT (if subgrouping) */
     605             :         const ValRecord *prop;
     606             :         lng t0 = 0;
     607             :         const char *algomsg = "";
     608             :         bool locked = false;
     609             : 
     610      101581 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
     611      101581 :         if (b == NULL) {
     612           0 :                 GDKerror("b must exist\n");
     613           0 :                 return GDK_FAIL;
     614             :         }
     615      101581 :         assert(s == NULL || BATttype(s) == TYPE_oid);
     616      101581 :         cnt = canditer_init(&ci, b, s);
     617             : 
     618             :         /* g is NULL or [oid(dense),oid] and same size as b or s */
     619      101533 :         assert(g == NULL || BATttype(g) == TYPE_oid || BATcount(g) == 0);
     620      101533 :         assert(g == NULL || BATcount(g) == cnt);
     621      101533 :         assert(g == NULL || BATcount(b) == 0 || (s ? g->hseqbase == s->hseqbase : g->hseqbase == b->hseqbase));
     622             :         /* e is NULL or [oid(dense),oid] */
     623      101533 :         assert(e == NULL || BATttype(e) == TYPE_oid);
     624             :         /* h is NULL or [oid(dense),lng] */
     625      101533 :         assert(h == NULL || h->ttype == TYPE_lng);
     626             :         /* e and h are aligned */
     627      101533 :         assert(e == NULL || h == NULL || BATcount(e) == BATcount(h));
     628      101533 :         assert(e == NULL || h == NULL || e->hseqbase == h->hseqbase);
     629             :         /* we want our output to go somewhere */
     630      101533 :         assert(groups != NULL);
     631             : 
     632      101533 :         if (cnt == 0) {
     633             :                 hseqb = 0;
     634             :         } else {
     635       66897 :                 hseqb = ci.seq;
     636             :         }
     637      101533 :         if (b->tkey || cnt <= 1 || (g && (g->tkey || BATtdense(g)))) {
     638             :                 /* grouping is trivial: 1 element per group */
     639       56800 :                 gn = BATdense(hseqb, 0, BATcount(b));
     640       56959 :                 if (gn == NULL)
     641           0 :                         goto error;
     642       56959 :                 *groups = gn;
     643       56959 :                 if (extents) {
     644       56467 :                         en = canditer_slice(&ci, 0, cnt);
     645       56466 :                         if (en == NULL)
     646           0 :                                 goto error;
     647       56466 :                         *extents = en;
     648             :                 }
     649       56958 :                 if (histo) {
     650        2796 :                         hn = BATconstant(0, TYPE_lng, &(lng){1}, cnt, TRANSIENT);
     651        2796 :                         if (hn == NULL)
     652           0 :                                 goto error;
     653        2796 :                         *histo = hn;
     654             :                 }
     655       56958 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     656             :                           ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
     657             :                           ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
     658             :                           ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
     659             :                           ",histo=" ALGOOPTBATFMT " (1 element per group -- "
     660             :                           LLFMT " usec)\n",
     661             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOOPTBATPAR(g),
     662             :                           ALGOOPTBATPAR(e), ALGOOPTBATPAR(h),
     663             :                           subsorted ? "true" : "false", ALGOOPTBATPAR(gn),
     664             :                           ALGOOPTBATPAR(en), ALGOOPTBATPAR(hn), GDKusec() - t0);
     665       56958 :                 return GDK_SUCCEED;
     666             :         }
     667       44733 :         assert(!BATtdense(b));
     668       44733 :         if (g) {
     669       10778 :                 if (BATtdense(g))
     670           0 :                         maxgrp = g->tseqbase + BATcount(g);
     671       10778 :                 else if (BATtordered(g))
     672        5809 :                         maxgrp = * (oid *) Tloc(g, BATcount(g) - 1);
     673        4969 :                 else if (BATtrevordered(g))
     674           0 :                         maxgrp = * (oid *) Tloc(g, 0);
     675             :                 else {
     676        4969 :                         MT_lock_set(&b->theaplock);
     677        4973 :                         prop = BATgetprop_nolock(g, GDK_MAX_VALUE);
     678        4972 :                         if (prop)
     679        4967 :                                 maxgrp = prop->val.oval;
     680        4972 :                         MT_lock_unset(&b->theaplock);
     681        4973 :                         if (is_oid_nil(maxgrp) /* && BATcount(g) < 10240 */) {
     682           5 :                                 BATmax(g, &maxgrp);
     683             :                         }
     684             :                 }
     685       10782 :                 if (maxgrp == 0)
     686             :                         g = NULL; /* single group */
     687             :                 else
     688        9044 :                         grps = (const oid *) Tloc(g, 0);
     689             :         }
     690       44737 :         if (BATordered(b) && BATordered_rev(b)) {
     691             :                 /* all values are equal */
     692        3780 :                 if (g == NULL || (BATordered(g) && BATordered_rev(g))) {
     693             :                         /* there's only a single group: 0 */
     694        2996 :                         gn = BATconstant(hseqb, TYPE_oid, &(oid){0}, cnt, TRANSIENT);
     695        2994 :                         if (gn == NULL)
     696           0 :                                 goto error;
     697        2994 :                         *groups = gn;
     698        2994 :                         if (extents) {
     699        2181 :                                 en = BATdense(0, canditer_next(&ci), 1);
     700        2188 :                                 if (en == NULL)
     701           0 :                                         goto error;
     702        2188 :                                 *extents = en;
     703             :                         }
     704        3001 :                         if (histo) {
     705          35 :                                 hn = BATconstant(0, TYPE_lng, &(lng){(lng)cnt}, 1, TRANSIENT);
     706          35 :                                 if (hn == NULL)
     707           0 :                                         goto error;
     708          35 :                                 *histo = hn;
     709             :                         }
     710        3001 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     711             :                                   ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
     712             :                                   ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
     713             :                                   ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
     714             :                                   ",histo=" ALGOOPTBATFMT " (single group -- "
     715             :                                   LLFMT " usec)\n",
     716             :                                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
     717             :                                   ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
     718             :                                   ALGOOPTBATPAR(h),
     719             :                                   subsorted ? "true" : "false",
     720             :                                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
     721             :                                   ALGOOPTBATPAR(hn), GDKusec() - t0);
     722        3001 :                         return GDK_SUCCEED;
     723             :                 }
     724         784 :                 if ((extents == NULL || e != NULL) &&
     725         188 :                     (histo == NULL || h != NULL) &&
     726         188 :                     cnt == BATcount(b)) {
     727             :                         /* inherit given grouping; note that if
     728             :                          * extents/histo is to be returned, we need
     729             :                          * e/h available in order to copy them,
     730             :                          * otherwise we will need to calculate them
     731             :                          * which we will do using the "normal" case */
     732         188 :                         gn = COLcopy(g, g->ttype, false, TRANSIENT);
     733         188 :                         if (gn == NULL)
     734           0 :                                 goto error;
     735         188 :                         if (!is_oid_nil(maxgrp)) {
     736         188 :                                 prop = BATgetprop(g, GDK_MAX_VALUE);
     737         188 :                                 if (prop)
     738         188 :                                         BATsetprop(gn, GDK_MAX_VALUE, TYPE_oid, &maxgrp);
     739         188 :                                 prop = BATgetprop(g, GDK_MAX_POS);
     740         188 :                                 if (prop)
     741         188 :                                         BATsetprop(gn, GDK_MAX_POS, TYPE_oid, &prop->val.oval);
     742             :                         }
     743             : 
     744         188 :                         *groups = gn;
     745         188 :                         if (extents) {
     746           0 :                                 en = COLcopy(e, e->ttype, false, TRANSIENT);
     747           0 :                                 if (en == NULL)
     748           0 :                                         goto error;
     749           0 :                                 *extents = en;
     750             :                         }
     751         188 :                         if (histo) {
     752           0 :                                 hn = COLcopy(h, h->ttype, false, TRANSIENT);
     753           0 :                                 if (hn == NULL)
     754           0 :                                         goto error;
     755           0 :                                 *histo = hn;
     756             :                         }
     757         188 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     758             :                                   ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
     759             :                                   ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
     760             :                                   ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
     761             :                                   ",histo=" ALGOOPTBATFMT " (copy groups -- "
     762             :                                   LLFMT " usec)\n",
     763             :                                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
     764             :                                   ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
     765             :                                   ALGOOPTBATPAR(h),
     766             :                                   subsorted ? "true" : "false",
     767             :                                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
     768             :                                   ALGOOPTBATPAR(hn), GDKusec() - t0);
     769         188 :                         return GDK_SUCCEED;
     770             :                 }
     771             :         }
     772       41711 :         assert(g == NULL || !BATtdense(g)); /* i.e. g->ttype == TYPE_oid */
     773       41711 :         cmp = ATOMcompare(b->ttype);
     774       41711 :         gn = COLnew(hseqb, TYPE_oid, cnt, TRANSIENT);
     775       41641 :         if (gn == NULL)
     776           0 :                 goto error;
     777       41641 :         ngrps = (oid *) Tloc(gn, 0);
     778             :         maxgrps = BUN_NONE;
     779       41641 :         MT_rwlock_rdlock(&b->thashlock);
     780       41990 :         if (b->thash && b->thash != (Hash *) 1)
     781           0 :                 maxgrps = b->thash->nunique;
     782       41990 :         MT_rwlock_rdunlock(&b->thashlock);
     783       41712 :         if (maxgrps == BUN_NONE) {
     784       41967 :                 MT_lock_set(&b->theaplock);
     785       41792 :                 if ((prop = BATgetprop_nolock(b, GDK_NUNIQUE)) != NULL)
     786           0 :                         maxgrps = prop->val.oval;
     787             :                 else
     788       41458 :                         maxgrps = cnt / 10;
     789       41458 :                 MT_lock_unset(&b->theaplock);
     790             :         }
     791       41728 :         if (!is_oid_nil(maxgrp) && maxgrps < maxgrp)
     792        6554 :                 maxgrps += maxgrp;
     793       41728 :         if (e && maxgrps < BATcount(e))
     794          12 :                 maxgrps += BATcount(e);
     795       41728 :         if (h && maxgrps < BATcount(h))
     796           0 :                 maxgrps += BATcount(h);
     797             :         if (maxgrps < GROUPBATINCR)
     798             :                 maxgrps = GROUPBATINCR;
     799       41728 :         bi = bat_iterator(b);
     800             : 
     801       41888 :         if (bi.width <= 2)
     802        7874 :                 maxgrps = (BUN) 1 << (8 * bi.width);
     803       41888 :         if (extents) {
     804       34582 :                 en = COLnew(0, TYPE_oid, maxgrps, TRANSIENT);
     805       34444 :                 if (en == NULL)
     806           0 :                         goto error1;
     807       34444 :                 exts = (oid *) Tloc(en, 0);
     808             :         }
     809       41750 :         if (histo) {
     810        6181 :                 hn = COLnew(0, TYPE_lng, maxgrps, TRANSIENT);
     811        6183 :                 if (hn == NULL)
     812           0 :                         goto error1;
     813        6183 :                 cnts = (lng *) Tloc(hn, 0);
     814             :         }
     815       41752 :         ngrp = 0;
     816       41752 :         BATsetcount(gn, cnt);
     817             : 
     818       41549 :         hseqb = b->hseqbase; /* abbreviation */
     819             : 
     820             :         /* figure out if we can use the storage type also for
     821             :          * comparing values */
     822       41549 :         t = ATOMbasetype(b->ttype);
     823             :         /* for strings we can use the offset instead of the actual
     824             :          * string values if we know that the strings in the string
     825             :          * heap are unique */
     826       41549 :         if (t == TYPE_str && GDK_ELIMDOUBLES(bi.vh)) {
     827        6875 :                 switch (bi.width) {
     828             :                 case 1:
     829             :                         t = TYPE_bte;
     830             :                         break;
     831        3514 :                 case 2:
     832             :                         t = TYPE_sht;
     833        3514 :                         break;
     834           5 :                 case 4:
     835             :                         t = TYPE_int;
     836           5 :                         break;
     837             : #if SIZEOF_VAR_T == 8
     838           0 :                 case 8:
     839             :                         t = TYPE_lng;
     840           0 :                         break;
     841             : #endif
     842             :                 default:
     843           0 :                         assert(0);
     844             :                 }
     845             :         }
     846             : 
     847       75691 :         if (subsorted ||
     848       68487 :             ((BATordered(b) || BATordered_rev(b)) &&
     849        1112 :              (g == NULL || BATordered(g) || BATordered_rev(g)))) {
     850             :                 /* we only need to compare each entry with the previous */
     851             :                 algomsg = "compare consecutive values -- ";
     852       20483 :                 switch (t) {
     853        1234 :                 case TYPE_bte:
     854     2054280 :                         GRP_compare_consecutive_values_tpe(bte);
     855             :                         break;
     856        1408 :                 case TYPE_sht:
     857      625430 :                         GRP_compare_consecutive_values_tpe(sht);
     858             :                         break;
     859       15253 :                 case TYPE_int:
     860    93928810 :                         GRP_compare_consecutive_values_tpe(int);
     861             :                         break;
     862        1574 :                 case TYPE_lng:
     863     6915960 :                         GRP_compare_consecutive_values_tpe(lng);
     864             :                         break;
     865             : #ifdef HAVE_HGE
     866         640 :                 case TYPE_hge:
     867       16969 :                         GRP_compare_consecutive_values_tpe(hge);
     868             :                         break;
     869             : #endif
     870           9 :                 case TYPE_flt:
     871          90 :                         GRP_compare_consecutive_values_tpe(flt);
     872             :                         break;
     873          99 :                 case TYPE_dbl:
     874        3930 :                         GRP_compare_consecutive_values_tpe(dbl);
     875             :                         break;
     876         266 :                 default:
     877       53061 :                         GRP_compare_consecutive_values_any();
     878             :                         break;
     879             :                 }
     880             : 
     881       20985 :                 gn->tsorted = true;
     882       20985 :                 *groups = gn;
     883       21751 :         } else if (BATordered(b) || BATordered_rev(b)) {
     884             :                 BUN i, j;
     885             :                 BUN *pgrp;
     886             : 
     887         877 :                 assert(g);      /* if g == NULL or if there is a single */
     888         877 :                 assert(grps);   /* group, we used the code above */
     889             :                 /* for each value, we need to scan all previous equal
     890             :                  * values (a consecutive, possibly empty, range) to
     891             :                  * see if we can find one in the same old group
     892             :                  *
     893             :                  * we do this by maintaining for each old group the
     894             :                  * last time we saw that group, so if the last time we
     895             :                  * saw the old group of the current value is within
     896             :                  * this range, we can reuse the new group */
     897             :                 algomsg = "subscan old groups -- ";
     898             :                 /* determine how many old groups there are */
     899         877 :                 if (e) {
     900           0 :                         j = BATcount(e) + (BUN) e->hseqbase;
     901         877 :                 } else if (h) {
     902           0 :                         j = BATcount(h) + (BUN) h->hseqbase;
     903             :                 } else {
     904             :                         oid m = 0;
     905    20779812 :                         for (i = 0, j= BATcount(g); i < j; i++)
     906    20778935 :                                 m = MAX(m , grps[i]);
     907         877 :                         j = (BUN) m + 1;
     908             :                 }
     909             :                 /* array to maintain last time we saw each old group */
     910         877 :                 pgrp = GDKmalloc(sizeof(BUN) * j);
     911         877 :                 if (pgrp == NULL)
     912           0 :                         goto error1;
     913             :                 /* initialize to impossible position */
     914         877 :                 memset(pgrp, ~0, sizeof(BUN) * j);
     915             : 
     916         877 :                 gn->tsorted = true; /* be optimistic */
     917             : 
     918         877 :                 switch (t) {
     919         353 :                 case TYPE_bte:
     920    10002386 :                         GRP_subscan_old_groups_tpe(bte);
     921             :                         break;
     922          15 :                 case TYPE_sht:
     923         134 :                         GRP_subscan_old_groups_tpe(sht);
     924             :                         break;
     925         501 :                 case TYPE_int:
     926    10755585 :                         GRP_subscan_old_groups_tpe(int);
     927             :                         break;
     928           5 :                 case TYPE_lng:
     929         132 :                         GRP_subscan_old_groups_tpe(lng);
     930             :                         break;
     931             : #ifdef HAVE_HGE
     932           0 :                 case TYPE_hge:
     933           0 :                         GRP_subscan_old_groups_tpe(hge);
     934             :                         break;
     935             : #endif
     936           2 :                 case TYPE_flt:
     937          22 :                         GRP_subscan_old_groups_tpe(flt);
     938             :                         break;
     939           1 :                 case TYPE_dbl:
     940           5 :                         GRP_subscan_old_groups_tpe(dbl);
     941             :                         break;
     942           0 :                 default:
     943           0 :                         GRP_subscan_old_groups_any();
     944             :                         break;
     945             :                 }
     946             : 
     947         878 :                 GDKfree(pgrp);
     948       19965 :         } else if (g == NULL && t == TYPE_bte) {
     949             :                 /* byte-sized values, use 256 entry array to keep
     950             :                  * track of doled out group ids; note that we can't
     951             :                  * possibly have more than 256 groups, so the group id
     952             :                  * fits in an unsigned char */
     953        1989 :                 unsigned char *restrict bgrps = GDKmalloc(256);
     954        1989 :                 const unsigned char *restrict w = (const unsigned char *) bi.base;
     955             :                 unsigned char v;
     956             : 
     957             :                 algomsg = "byte-sized groups -- ";
     958        1989 :                 if (bgrps == NULL)
     959           0 :                         goto error1;
     960        1989 :                 memset(bgrps, 0xFF, 256);
     961        1989 :                 if (histo)
     962         983 :                         memset(cnts, 0, maxgrps * sizeof(lng));
     963        1989 :                 ngrp = 0;
     964        1989 :                 gn->tsorted = true;
     965    15421500 :                 for (r = 0; r < cnt; r++) {
     966    15419513 :                         oid o = canditer_next(&ci);
     967    15419511 :                         p = o - b->hseqbase;
     968    15419511 :                         if ((v = bgrps[w[p]]) == 0xFF && ngrp < 256) {
     969       11190 :                                 bgrps[w[p]] = v = (unsigned char) ngrp++;
     970             :                                 maxgrppos = r;
     971       11190 :                                 if (extents)
     972       11192 :                                         exts[v] = o;
     973             :                         }
     974    15419511 :                         ngrps[r] = v;
     975    15419511 :                         if (r > 0 && v < ngrps[r - 1])
     976     2801528 :                                 gn->tsorted = false;
     977    15419511 :                         if (histo)
     978        6913 :                                 cnts[v]++;
     979             :                 }
     980        1987 :                 GDKfree(bgrps);
     981       17976 :         } else if (g == NULL && t == TYPE_sht) {
     982             :                 /* short-sized values, use 65536 entry array to keep
     983             :                  * track of doled out group ids; note that we can't
     984             :                  * possibly have more than 65536 groups, so the group
     985             :                  * id fits in an unsigned short */
     986        1416 :                 unsigned short *restrict sgrps = GDKmalloc(65536 * sizeof(short));
     987        1418 :                 const unsigned short *restrict w = (const unsigned short *) bi.base;
     988             :                 unsigned short v;
     989             : 
     990             :                 algomsg = "short-sized groups -- ";
     991        1418 :                 if (sgrps == NULL)
     992           0 :                         goto error1;
     993        1418 :                 memset(sgrps, 0xFF, 65536 * sizeof(short));
     994        1418 :                 if (histo)
     995         394 :                         memset(cnts, 0, maxgrps * sizeof(lng));
     996        1418 :                 ngrp = 0;
     997        1418 :                 gn->tsorted = true;
     998     6696329 :                 for (r = 0; r < cnt; r++) {
     999     6694909 :                         oid o = canditer_next(&ci);
    1000     6694911 :                         p = o - b->hseqbase;
    1001     6694911 :                         if ((v = sgrps[w[p]]) == 0xFFFF && ngrp < 65536) {
    1002       58424 :                                 sgrps[w[p]] = v = (unsigned short) ngrp++;
    1003             :                                 maxgrppos = r;
    1004       58424 :                                 if (extents)
    1005       58424 :                                         exts[v] = o;
    1006             :                         }
    1007     6694911 :                         ngrps[r] = v;
    1008     6694911 :                         if (r > 0 && v < ngrps[r - 1])
    1009     3156535 :                                 gn->tsorted = false;
    1010     6694911 :                         if (histo)
    1011       14771 :                                 cnts[v]++;
    1012             :                 }
    1013        1420 :                 GDKfree(sgrps);
    1014       16560 :         } else if (g == NULL &&
    1015       11704 :                    (BATcheckhash(b) ||
    1016       11708 :                     (!b->batTransient &&
    1017           0 :                      BAThash(b) == GDK_SUCCEED) ||
    1018             :                     (/* DISABLES CODE */ (0) &&
    1019             :                      (parent = VIEWtparent(b)) != 0 &&
    1020           0 :                      BATcheckhash(BBP_cache(parent))))) {
    1021             :                 /* we already have a hash table on b, or b is
    1022             :                  * persistent and we could create a hash table, or b
    1023             :                  * is a view on a bat that already has a hash table;
    1024             :                  * but don't do this if we're checking for subgroups
    1025             :                  * since we may have to go through long lists of
    1026             :                  * duplicates in the hash table to find an old
    1027             :                  * group */
    1028             :                 bool phash = false;
    1029             :                 algomsg = "existing hash -- ";
    1030           0 :                 MT_rwlock_rdlock(&b->thashlock);
    1031             :                 if (b->thash == NULL &&
    1032             :                     /* DISABLES CODE */ (0) &&
    1033             :                     (parent = VIEWtparent(b)) != 0) {
    1034             :                         /* b is a view on another bat (b2 for now).
    1035             :                          * calculate the bounds [lo, lo+BATcount(b))
    1036             :                          * in the parent that b uses */
    1037             :                         BAT *b2 = BBP_cache(parent);
    1038             :                         MT_rwlock_rdunlock(&b->thashlock);
    1039             :                         lo = b->tbaseoff - b2->tbaseoff;
    1040             :                         b = b2;
    1041             :                         bat_iterator_end(&bi);
    1042             :                         bi = bat_iterator(b);
    1043             :                         MT_rwlock_rdlock(&b->thashlock);
    1044             :                         algomsg = "existing parent hash -- ";
    1045             :                         phash = true;
    1046             :                 }
    1047           0 :                 hs = b->thash;
    1048           0 :                 if (hs == NULL) {
    1049           0 :                         MT_rwlock_rdunlock(&b->thashlock);
    1050           0 :                         goto lost_hash;
    1051             :                 }
    1052             :                 locked = true;
    1053           0 :                 gn->tsorted = true; /* be optimistic */
    1054             : 
    1055           0 :                 switch (t) {
    1056           0 :                 case TYPE_bte:
    1057           0 :                         GRP_use_existing_hash_table_tpe(bte);
    1058             :                         break;
    1059           0 :                 case TYPE_sht:
    1060           0 :                         GRP_use_existing_hash_table_tpe(sht);
    1061             :                         break;
    1062           0 :                 case TYPE_int:
    1063           0 :                         GRP_use_existing_hash_table_tpe(int);
    1064             :                         break;
    1065           0 :                 case TYPE_lng:
    1066           0 :                         GRP_use_existing_hash_table_tpe(lng);
    1067             :                         break;
    1068             : #ifdef HAVE_HGE
    1069           0 :                 case TYPE_hge:
    1070           0 :                         GRP_use_existing_hash_table_tpe(hge);
    1071             :                         break;
    1072             : #endif
    1073           0 :                 case TYPE_flt:
    1074           0 :                         GRP_use_existing_hash_table_tpe(flt);
    1075             :                         break;
    1076           0 :                 case TYPE_dbl:
    1077           0 :                         GRP_use_existing_hash_table_tpe(dbl);
    1078             :                         break;
    1079           0 :                 case TYPE_uuid:
    1080           0 :                         GRP_use_existing_hash_table_tpe(uuid);
    1081             :                         break;
    1082           0 :                 default:
    1083           0 :                         GRP_use_existing_hash_table_any();
    1084             :                         break;
    1085             :                 }
    1086           0 :                 MT_rwlock_rdunlock(&b->thashlock);
    1087             :                 locked = false;
    1088             :         } else {
    1089             :                 bool gc;
    1090             :                 const char *nme;
    1091             :                 BUN prb;
    1092             :                 int bits;
    1093             :                 BUN nbucket;
    1094             :                 oid grp;
    1095             : 
    1096        4856 :           lost_hash:
    1097       16564 :                 gc = g != NULL && (BATordered(g) || BATordered_rev(g));
    1098             :                 bits = 0;
    1099       16573 :                 GDKclrerr();    /* not interested in BAThash errors */
    1100             : 
    1101             :                 /* not sorted, and no pre-existing hash table: we'll
    1102             :                  * build an incomplete hash table on the fly--also see
    1103             :                  * BATassertProps for similar code; we also exploit if
    1104             :                  * g is clustered */
    1105             :                 algomsg = "new partial hash -- ";
    1106       16563 :                 nme = GDKinmemory(bi.h->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
    1107       16569 :                 if (grps && !gc) {
    1108             :                         /* we manipulate the hash value after having
    1109             :                          * calculated it, and when doing that, we
    1110             :                          * assume the mask (i.e. nbucket-1) is a
    1111             :                          * power-of-two minus one, so make sure it
    1112             :                          * is */
    1113        4089 :                         nbucket = cnt | cnt >> 1;
    1114        4089 :                         nbucket |= nbucket >> 2;
    1115        4089 :                         nbucket |= nbucket >> 4;
    1116        4089 :                         nbucket |= nbucket >> 8;
    1117        4089 :                         nbucket |= nbucket >> 16;
    1118             : #if SIZEOF_BUN == 8
    1119        4089 :                         nbucket |= nbucket >> 32;
    1120             : #endif
    1121        4089 :                         nbucket++;
    1122             :                 } else {
    1123       12480 :                         nbucket = MAX(HASHmask(cnt), 1 << 16);
    1124             :                 }
    1125       16569 :                 if (grps == NULL || is_oid_nil(maxgrp)
    1126             : #if SIZEOF_OID == SIZEOF_LNG
    1127        4856 :                     || maxgrp >= ((oid) 1 << (SIZEOF_LNG * 8 - 8))
    1128             : #endif
    1129             :                         ) {
    1130       11712 :                         switch (t) {
    1131           0 :                         case TYPE_bte:
    1132             :                                 nbucket = 256;
    1133           0 :                                 break;
    1134           0 :                         case TYPE_sht:
    1135             :                                 nbucket = 65536;
    1136           0 :                                 break;
    1137             :                         default:
    1138             :                                 break;
    1139             :                         }
    1140        4857 :                 }
    1141             :                 /* nbucket is a power of two, so ctz(nbucket)
    1142             :                  * tells us which power of two */
    1143       16569 :                 bits = 8 * SIZEOF_OID - ctz(nbucket);
    1144       16569 :                 if ((hs = GDKzalloc(sizeof(Hash))) == NULL ||
    1145       16571 :                     (hs->heaplink.farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap)) < 0 ||
    1146       16573 :                     (hs->heapbckt.farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap)) < 0) {
    1147           0 :                         GDKfree(hs);
    1148             :                         hs = NULL;
    1149           0 :                         GDKerror("cannot allocate hash table\n");
    1150           0 :                         goto error1;
    1151             :                 }
    1152       16577 :                 if (snprintf(hs->heaplink.filename, sizeof(hs->heaplink.filename), "%s.thshgrpl%x", nme, (unsigned) THRgettid()) >= (int) sizeof(hs->heaplink.filename) ||
    1153       33172 :                     snprintf(hs->heapbckt.filename, sizeof(hs->heapbckt.filename), "%s.thshgrpb%x", nme, (unsigned) THRgettid()) >= (int) sizeof(hs->heapbckt.filename) ||
    1154       16587 :                     HASHnew(hs, b->ttype, BUNlast(b), nbucket, BUN_NONE, false) != GDK_SUCCEED) {
    1155           0 :                         GDKfree(hs);
    1156             :                         hs = NULL;
    1157           0 :                         GDKerror("cannot allocate hash table\n");
    1158           0 :                         goto error1;
    1159             :                 }
    1160       16578 :                 gn->tsorted = true; /* be optimistic */
    1161             : 
    1162       16578 :                 switch (t) {
    1163         415 :                 case TYPE_bte:
    1164         415 :                         if (grps && !is_oid_nil(maxgrp)
    1165             : #if SIZEOF_OID == SIZEOF_LNG
    1166         416 :                             && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 8))
    1167             : #endif
    1168             :                                 ) {
    1169             :                                 ulng v;
    1170         416 :                                 const bte *w = (bte *) bi.base;
    1171     8365482 :                                 GRP_create_partial_hash_table_core(
    1172             :                                         (void) 0,
    1173             :                                         (v = ((ulng)grps[r]<<8)|(unsigned char)w[p], hash_lng(hs, &v)),
    1174             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1175             :                                         (void) 0,
    1176             :                                         NOGRPTST);
    1177             :                         } else
    1178           0 :                                 GRP_create_partial_hash_table_tpe(bte);
    1179             :                         break;
    1180        1030 :                 case TYPE_sht:
    1181        1030 :                         if (grps && !is_oid_nil(maxgrp)
    1182             : #if SIZEOF_OID == SIZEOF_LNG
    1183        1030 :                             && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 16))
    1184             : #endif
    1185             :                                 ) {
    1186             :                                 ulng v;
    1187        1030 :                                 const sht *w = (sht *) bi.base;
    1188    27775604 :                                 GRP_create_partial_hash_table_core(
    1189             :                                         (void) 0,
    1190             :                                         (v = ((ulng)grps[r]<<16)|(unsigned short)w[p], hash_lng(hs, &v)),
    1191             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1192             :                                         (void) 0,
    1193             :                                         NOGRPTST);
    1194             :                         } else
    1195           0 :                                 GRP_create_partial_hash_table_tpe(sht);
    1196             :                         break;
    1197       14077 :                 case TYPE_int:
    1198       14077 :                         if (grps && !is_oid_nil(maxgrp)
    1199             : #if SIZEOF_OID == SIZEOF_LNG
    1200        2760 :                             && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 32))
    1201             : #endif
    1202             :                                 ) {
    1203             :                                 ulng v;
    1204        2760 :                                 const int *w = (int *) bi.base;
    1205   114852794 :                                 GRP_create_partial_hash_table_core(
    1206             :                                         (void) 0,
    1207             :                                         (v = ((ulng)grps[r]<<32)|(unsigned int)w[p], hash_lng(hs, &v)),
    1208             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1209             :                                         (void) 0,
    1210             :                                         NOGRPTST);
    1211             :                         } else
    1212    59491186 :                                 GRP_create_partial_hash_table_tpe(int);
    1213             :                         break;
    1214         554 :                 case TYPE_lng:
    1215             : #ifdef HAVE_HGE
    1216         554 :                         if (grps) {
    1217             :                                 uhge v;
    1218         379 :                                 const lng *w = (lng *) bi.base;
    1219     1828768 :                                 GRP_create_partial_hash_table_core(
    1220             :                                         (void) 0,
    1221             :                                         (v = ((uhge)grps[r]<<64)|(ulng)w[p], hash_hge(hs, &v)),
    1222             :                                         w[p] == w[hb] && grps[r] == grps[q],
    1223             :                                         (void) 0,
    1224             :                                         NOGRPTST);
    1225             :                         } else
    1226             : #endif
    1227       88463 :                                 GRP_create_partial_hash_table_tpe(lng);
    1228             :                         break;
    1229             : #ifdef HAVE_HGE
    1230          39 :                 case TYPE_hge:
    1231    57800498 :                         GRP_create_partial_hash_table_tpe(hge);
    1232             :                         break;
    1233             : #endif
    1234          23 :                 case TYPE_flt:
    1235         629 :                         GRP_create_partial_hash_table_tpe(flt);
    1236             :                         break;
    1237         112 :                 case TYPE_dbl:
    1238        2949 :                         GRP_create_partial_hash_table_tpe(dbl);
    1239             :                         break;
    1240           6 :                 case TYPE_uuid:
    1241          46 :                         GRP_create_partial_hash_table_tpe(uuid);
    1242             :                         break;
    1243         322 :                 default:
    1244    50424202 :                         GRP_create_partial_hash_table_any();
    1245             :                 }
    1246             : 
    1247           0 :                 HEAPfree(&hs->heapbckt, true);
    1248       16596 :                 HEAPfree(&hs->heaplink, true);
    1249       16598 :                 GDKfree(hs);
    1250             :         }
    1251       41864 :         bat_iterator_end(&bi);
    1252       41644 :         if (extents) {
    1253       34428 :                 BATsetcount(en, (BUN) ngrp);
    1254       34631 :                 en->tkey = true;
    1255       34631 :                 en->tsorted = true;
    1256       34631 :                 en->trevsorted = ngrp == 1;
    1257       34631 :                 en->tnonil = true;
    1258       34631 :                 en->tnil = false;
    1259       34631 :                 *extents = virtualize(en);
    1260             :         }
    1261       41565 :         if (histo) {
    1262        6180 :                 BATsetcount(hn, (BUN) ngrp);
    1263        6183 :                 if (ngrp == cnt || ngrp == 1) {
    1264        3734 :                         hn->tkey = ngrp == 1;
    1265        3734 :                         hn->tsorted = true;
    1266        3734 :                         hn->trevsorted = true;
    1267             :                 } else {
    1268        2449 :                         hn->tkey = false;
    1269        2449 :                         hn->tsorted = false;
    1270        2449 :                         hn->trevsorted = false;
    1271             :                 }
    1272        6183 :                 hn->tnonil = true;
    1273        6183 :                 hn->tnil = false;
    1274        6183 :                 *histo = hn;
    1275             :         }
    1276       41568 :         gn->tkey = ngrp == BATcount(gn);
    1277       41568 :         gn->trevsorted = ngrp == 1 || BATcount(gn) <= 1;
    1278       41568 :         gn->tnonil = true;
    1279       41568 :         gn->tnil = false;
    1280       41568 :         ngrp--;      /* max value is one less than number of values */
    1281       41568 :         BATsetprop(gn, GDK_MAX_VALUE, TYPE_oid, &ngrp);
    1282       41993 :         BATsetprop(gn, GDK_MAX_POS, TYPE_oid, &(oid){maxgrppos});
    1283       41998 :         *groups = gn;
    1284       41998 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    1285             :                   ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
    1286             :                   ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
    1287             :                   ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
    1288             :                   ",histo=" ALGOOPTBATFMT " (%s" LLFMT " usec)\n",
    1289             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
    1290             :                   ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
    1291             :                   ALGOOPTBATPAR(h),
    1292             :                   subsorted ? "true" : "false",
    1293             :                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
    1294             :                   ALGOOPTBATPAR(hn), algomsg, GDKusec() - t0);
    1295             :         return GDK_SUCCEED;
    1296           0 :   error1:
    1297           0 :         bat_iterator_end(&bi);
    1298           0 :   error:
    1299           0 :         if (hs != NULL && hs != b->thash) {
    1300           0 :                 HEAPfree(&hs->heaplink, true);
    1301           0 :                 HEAPfree(&hs->heapbckt, true);
    1302           0 :                 GDKfree(hs);
    1303             :         }
    1304           0 :         if (locked)
    1305           0 :                 MT_rwlock_rdunlock(&b->thashlock);
    1306           0 :         if (gn)
    1307           0 :                 BBPunfix(gn->batCacheid);
    1308           0 :         if (en)
    1309           0 :                 BBPunfix(en->batCacheid);
    1310           0 :         if (hn)
    1311           0 :                 BBPunfix(hn->batCacheid);
    1312             :         return GDK_FAIL;
    1313             : }
    1314             : 
    1315             : gdk_return
    1316       92730 : BATgroup(BAT **groups, BAT **extents, BAT **histo,
    1317             :          BAT *b, BAT *s, BAT *g, BAT *e, BAT *h)
    1318             : {
    1319       92730 :         return BATgroup_internal(groups, extents, histo, b, s, g, e, h, false);
    1320             : }

Generated by: LCOV version 1.14