LCOV - code coverage report
Current view: top level - gdk - gdk_cand.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 634 910 69.7 %
Date: 2021-09-14 19:48:19 Functions: 23 25 92.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             : bool
      15       12529 : BATiscand(BAT *b)
      16             : {
      17       12529 :         if (ATOMtype(b->ttype) != TYPE_oid)
      18             :                 return false;
      19       12529 :         if (complex_cand(b))
      20             :                 return true;
      21        9252 :         if (b->ttype == TYPE_void && is_oid_nil(b->tseqbase))
      22             :                 return false;
      23        9252 :         return BATtordered(b) && BATtkey(b);
      24             : }
      25             : 
      26             : /* create a new, dense candidate list with values from `first' up to,
      27             :  * but not including, `last' */
      28             : static inline BAT *
      29        9372 : newdensecand(oid first, oid last)
      30             : {
      31        9372 :         if (last <= first)
      32             :                 first = last = 0; /* empty range */
      33        9372 :         return BATdense(0, first, last - first);
      34             : }
      35             : 
      36             : /* merge two candidate lists and produce a new one
      37             :  *
      38             :  * candidate lists are VOID-headed BATs with an OID tail which is
      39             :  * sorted and unique.
      40             :  */
      41             : BAT *
      42      114786 : BATmergecand(BAT *a, BAT *b)
      43             : {
      44             :         BAT *bn;
      45             :         oid *restrict p, i;
      46             :         struct canditer cia, cib;
      47             : 
      48      114786 :         BATcheck(a, NULL);
      49      114786 :         BATcheck(b, NULL);
      50             : 
      51      114786 :         canditer_init(&cia, NULL, a);
      52      114581 :         canditer_init(&cib, NULL, b);
      53             : 
      54             :         /* we can return a if b is empty (and v.v.) */
      55      114845 :         if (cia.ncand == 0) {
      56       37363 :                 bn = canditer_slice(&cib, 0, cib.ncand);
      57       37390 :                 goto doreturn;
      58             :         }
      59       77482 :         if (cib.ncand == 0) {
      60       19885 :                 bn = canditer_slice(&cia, 0, cia.ncand);
      61       19908 :                 goto doreturn;
      62             :         }
      63             :         /* we can return a if a fully covers b (and v.v) */
      64       57597 :         if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
      65             :                 /* both are dense */
      66       17478 :                 if (cia.seq <= cib.seq && cib.seq <= cia.seq + cia.ncand) {
      67             :                         /* partial overlap starting with a, or b is
      68             :                          * smack bang after a */
      69        6688 :                         bn = newdensecand(cia.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
      70        6695 :                         goto doreturn;
      71             :                 }
      72       10790 :                 if (cib.seq <= cia.seq && cia.seq <= cib.seq + cib.ncand) {
      73             :                         /* partial overlap starting with b, or a is
      74             :                          * smack bang after b */
      75        2682 :                         bn = newdensecand(cib.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
      76        2685 :                         goto doreturn;
      77             :                 }
      78             :         }
      79       48227 :         if (cia.tpe == cand_dense
      80       10367 :             && cia.seq <= cib.seq
      81        4556 :             && canditer_last(&cia) >= canditer_last(&cib)) {
      82         204 :                 bn = canditer_slice(&cia, 0, cia.ncand);
      83         204 :                 goto doreturn;
      84             :         }
      85       48021 :         if (cib.tpe == cand_dense
      86       35481 :             && cib.seq <= cia.seq
      87       10302 :             && canditer_last(&cib) >= canditer_last(&cia)) {
      88         151 :                 bn = canditer_slice(&cib, 0, cib.ncand);
      89         151 :                 goto doreturn;
      90             :         }
      91             : 
      92       47870 :         bn = COLnew(0, TYPE_oid, cia.ncand + cib.ncand, TRANSIENT);
      93       47841 :         if (bn == NULL)
      94           0 :                 goto doreturn;
      95       47841 :         p = (oid *) Tloc(bn, 0);
      96       47841 :         if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
      97             :                 /* both lists are dense */
      98        8107 :                 if (cia.seq > cib.seq) {
      99             :                         struct canditer ci;
     100        4222 :                         ci = cia;
     101        4222 :                         cia = cib;
     102        4222 :                         cib = ci;
     103             :                 }
     104             :                 /* cia completely before cib */
     105        8107 :                 assert(cia.seq + cia.ncand < cib.seq);
     106       30700 :                 for (i = cia.seq; i < cia.seq + cia.ncand; i++)
     107       22593 :                         *p++ = i;
     108             :                 /* there is a gap */
     109       27099 :                 for (i = cib.seq; i < cib.seq + cib.ncand; i++)
     110       18992 :                         *p++ = i;
     111       39734 :         } else if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
     112       29257 :                 if (cib.tpe == cand_dense) {
     113             :                         struct canditer ci;
     114       27256 :                         ci = cia;
     115       27256 :                         cia = cib;
     116       27256 :                         cib = ci;
     117             :                 }
     118             :                 /* only cia is dense */
     119             : 
     120             :                 /* copy part of cib that's before the start of cia */
     121      116893 :                 while (canditer_peek(&cib) < cia.seq) {
     122       87619 :                         *p++ = canditer_next(&cib);
     123             :                 }
     124             :                 /* copy all of cia */
     125       65846 :                 for (i = cia.seq; i < cia.seq + cia.ncand; i++)
     126       36448 :                         *p++ = i;
     127             :                 /* skip over part of cib that overlaps with cia */
     128       29398 :                 canditer_setidx(&cib, canditer_search(&cib, cia.seq + cia.ncand, true));
     129             :                 /* copy rest of cib */
     130      119618 :                 while (cib.next < cib.ncand) {
     131       90248 :                         *p++ = canditer_next(&cib);
     132             :                 }
     133             :         } else {
     134             :                 /* a and b are both not dense */
     135       10477 :                 oid ao = canditer_next(&cia);
     136       10474 :                 oid bo = canditer_next(&cib);
     137    22650335 :                 while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
     138    22639850 :                         if (ao < bo) {
     139    13735936 :                                 *p++ = ao;
     140    13735936 :                                 ao = canditer_next(&cia);
     141     8903914 :                         } else if (bo < ao) {
     142     8542128 :                                 *p++ = bo;
     143     8542128 :                                 bo = canditer_next(&cib);
     144             :                         } else {
     145      361786 :                                 *p++ = ao;
     146      361786 :                                 ao = canditer_next(&cia);
     147      361830 :                                 bo = canditer_next(&cib);
     148             :                         }
     149             :                 }
     150      263292 :                 while (!is_oid_nil(ao)) {
     151      252810 :                         *p++ = ao;
     152      252810 :                         ao = canditer_next(&cia);
     153             :                 }
     154       27341 :                 while (!is_oid_nil(bo)) {
     155       16858 :                         *p++ = bo;
     156       16858 :                         bo = canditer_next(&cib);
     157             :                 }
     158             :         }
     159             : 
     160             :         /* properties */
     161       47960 :         BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
     162       47967 :         bn->trevsorted = BATcount(bn) <= 1;
     163       47967 :         bn->tsorted = true;
     164       47967 :         bn->tkey = true;
     165       47967 :         bn->tnil = false;
     166       47967 :         bn->tnonil = true;
     167       47967 :         bn = virtualize(bn);
     168      114960 :   doreturn:
     169      114960 :         TRC_DEBUG(ALGO, ALGOBATFMT "," ALGOBATFMT " -> " ALGOOPTBATFMT "\n",
     170             :                   ALGOBATPAR(a), ALGOBATPAR(b), ALGOOPTBATPAR(bn));
     171             :         return bn;
     172             : }
     173             : 
     174             : /* intersect two candidate lists and produce a new one
     175             :  *
     176             :  * candidate lists are VOID-headed BATs with an OID tail which is
     177             :  * sorted and unique.
     178             :  */
     179             : BAT *
     180           8 : BATintersectcand(BAT *a, BAT *b)
     181             : {
     182             :         BAT *bn;
     183             :         oid *restrict p;
     184             :         struct canditer cia, cib;
     185             : 
     186           8 :         BATcheck(a, NULL);
     187           8 :         BATcheck(b, NULL);
     188             : 
     189           8 :         canditer_init(&cia, NULL, a);
     190           8 :         canditer_init(&cib, NULL, b);
     191             : 
     192           8 :         if (cia.ncand == 0 || cib.ncand == 0) {
     193           0 :                 bn = BATdense(0, 0, 0);
     194           0 :                 goto doreturn;
     195             :         }
     196             : 
     197           8 :         if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
     198             :                 /* both lists are dense */
     199           0 :                 bn = newdensecand(MAX(cia.seq, cib.seq), MIN(cia.seq + cia.ncand, cib.seq + cib.ncand));
     200           0 :                 goto doreturn;
     201             :         }
     202             : 
     203           8 :         bn = COLnew(0, TYPE_oid, MIN(cia.ncand, cib.ncand), TRANSIENT);
     204           8 :         if (bn == NULL)
     205           0 :                 goto doreturn;
     206           8 :         p = (oid *) Tloc(bn, 0);
     207           8 :         if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
     208           8 :                 if (cib.tpe == cand_dense) {
     209             :                         struct canditer ci;
     210           8 :                         ci = cia;
     211           8 :                         cia = cib;
     212           8 :                         cib = ci;
     213             :                 }
     214             :                 /* only cia is dense */
     215             : 
     216             :                 /* search for first value in cib that is contained in cia */
     217           8 :                 canditer_setidx(&cib, canditer_search(&cib, cia.seq, true));
     218             :                 oid bo;
     219        1029 :                 while (!is_oid_nil(bo = canditer_next(&cib)) && bo < cia.seq + cia.ncand)
     220        1021 :                         *p++ = bo;
     221             :         } else {
     222             :                 /* a and b are both not dense */
     223           0 :                 oid ao = canditer_next(&cia);
     224           0 :                 oid bo = canditer_next(&cib);
     225           0 :                 while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
     226           0 :                         if (ao < bo)
     227           0 :                                 ao = canditer_next(&cia);
     228           0 :                         else if (bo < ao)
     229           0 :                                 bo = canditer_next(&cib);
     230             :                         else {
     231           0 :                                 *p++ = ao;
     232           0 :                                 ao = canditer_next(&cia);
     233           0 :                                 bo = canditer_next(&cib);
     234             :                         }
     235             :                 }
     236             :         }
     237             : 
     238             :         /* properties */
     239           8 :         BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
     240           8 :         bn->trevsorted = BATcount(bn) <= 1;
     241           8 :         bn->tsorted = true;
     242           8 :         bn->tkey = true;
     243           8 :         bn->tnil = false;
     244           8 :         bn->tnonil = true;
     245           8 :         bn = virtualize(bn);
     246           8 :   doreturn:
     247           8 :         TRC_DEBUG(ALGO, ALGOBATFMT "," ALGOBATFMT " -> " ALGOOPTBATFMT "\n",
     248             :                   ALGOBATPAR(a), ALGOBATPAR(b), ALGOOPTBATPAR(bn));
     249             :         return bn;
     250             : }
     251             : 
     252             : /* calculate the difference of two candidate lists and produce a new one
     253             :  */
     254             : BAT *
     255           0 : BATdiffcand(BAT *a, BAT *b)
     256             : {
     257             :         BAT *bn;
     258             :         oid *restrict p;
     259             :         struct canditer cia, cib;
     260             : 
     261           0 :         BATcheck(a, NULL);
     262           0 :         BATcheck(b, NULL);
     263             : 
     264           0 :         canditer_init(&cia, NULL, a);
     265           0 :         canditer_init(&cib, NULL, b);
     266             : 
     267           0 :         if (cia.ncand == 0) {
     268           0 :                 bn = BATdense(0, 0, 0);
     269           0 :                 goto doreturn;
     270             :         }
     271           0 :         if (cib.ncand == 0) {
     272           0 :                 bn = canditer_slice(&cia, 0, cia.ncand);
     273           0 :                 goto doreturn;
     274             :         }
     275             : 
     276           0 :         if (cib.seq > canditer_last(&cia) || canditer_last(&cib) < cia.seq) {
     277             :                 /* no overlap, return a */
     278           0 :                 bn = canditer_slice(&cia, 0, cia.ncand);
     279           0 :                 goto doreturn;
     280             :         }
     281             : 
     282           0 :         if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
     283             :                 /* both a and b are dense */
     284           0 :                 if (cia.seq < cib.seq) {
     285             :                         /* a starts before b */
     286           0 :                         if (cia.seq + cia.ncand <= cib.seq + cib.ncand) {
     287             :                                 /* b overlaps with end of a */
     288           0 :                                 bn = canditer_slice(&cia, 0, cib.seq - cia.seq);
     289           0 :                                 goto doreturn;
     290             :                         }
     291             :                         /* b is subset of a */
     292           0 :                         bn = canditer_slice2(&cia, 0, cib.seq - cia.seq,
     293             :                                              cib.seq + cib.ncand - cia.seq,
     294             :                                              cia.ncand);
     295           0 :                         goto doreturn;
     296             :                 } else {
     297             :                         /* cia.seq >= cib.seq */
     298           0 :                         if (cia.seq + cia.ncand > cib.seq + cib.ncand) {
     299             :                                 /* b overlaps with beginning of a */
     300           0 :                                 bn = canditer_slice(&cia, cib.seq + cib.ncand - cia.seq, cia.ncand);
     301           0 :                                 goto doreturn;
     302             :                         }
     303             :                         /* a is subset f b */
     304           0 :                         bn = BATdense(0, 0, 0);
     305           0 :                         goto doreturn;
     306             :                 }
     307             :         }
     308           0 :         if (cib.tpe == cand_dense) {
     309             :                 /* b is dense and a is not: we can copy the part of a
     310             :                  * that is before the start of b and the part of a
     311             :                  * that is after the end of b */
     312           0 :                 bn = canditer_slice2val(&cia, oid_nil, cib.seq,
     313           0 :                                         cib.seq + cib.ncand, oid_nil);
     314           0 :                 goto doreturn;
     315             :         }
     316             : 
     317             :         /* b is not dense */
     318           0 :         bn = COLnew(0, TYPE_oid, BATcount(a), TRANSIENT);
     319           0 :         if (bn == NULL)
     320           0 :                 goto doreturn;
     321           0 :         p = Tloc(bn, 0);
     322             :         /* find first position in b that is in range of a */
     323           0 :         canditer_setidx(&cib, canditer_search(&cib, cia.seq, true));
     324             :         {
     325             :                 /* because we may jump over this declaration, we put
     326             :                  * it inside a block */
     327           0 :                 oid ob = canditer_next(&cib);
     328           0 :                 for (BUN i = 0; i < cia.ncand; i++) {
     329           0 :                         oid oa = canditer_next(&cia);
     330           0 :                         while (!is_oid_nil(ob) && ob < oa) {
     331           0 :                                 ob = canditer_next(&cib);
     332             :                         }
     333           0 :                         if (!is_oid_nil(ob) && oa < ob)
     334           0 :                                 *p++ = oa;
     335             :                 }
     336             :         }
     337             : 
     338             :         /* properties */
     339           0 :         BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
     340           0 :         bn->trevsorted = BATcount(bn) <= 1;
     341           0 :         bn->tsorted = true;
     342           0 :         bn->tkey = true;
     343           0 :         bn->tnil = false;
     344           0 :         bn->tnonil = true;
     345           0 :         bn = virtualize(bn);
     346           0 :   doreturn:
     347           0 :         TRC_DEBUG(ALGO, ALGOBATFMT "," ALGOBATFMT " -> " ALGOOPTBATFMT "\n",
     348             :                   ALGOBATPAR(a), ALGOBATPAR(b), ALGOOPTBATPAR(bn));
     349             :         return bn;
     350             : }
     351             : 
     352             : /* return offset of first value in cand that is >= o */
     353             : static inline BUN
     354     4053285 : binsearchcand(const oid *cand, BUN hi, oid o)
     355             : {
     356             :         BUN lo = 0;
     357             : 
     358     4053285 :         if (o <= cand[lo])
     359             :                 return 0;
     360     3797272 :         if (o > cand[hi])
     361      243880 :                 return hi + 1;
     362             :         /* loop invariant: cand[lo] < o <= cand[hi] */
     363    58373609 :         while (hi > lo + 1) {
     364    56178636 :                 BUN mid = (lo + hi) / 2;
     365    56178636 :                 if (cand[mid] == o)
     366     1358419 :                         return mid;
     367    54820217 :                 if (cand[mid] < o)
     368             :                         lo = mid;
     369             :                 else
     370             :                         hi = mid;
     371             :         }
     372             :         return hi;
     373             : }
     374             : 
     375             : /* count number of 1 bits in ci->mask between bit positions lo
     376             :  * (inclusive) and hi (not inclusive) */
     377             : static BUN
     378       96459 : count_mask_bits(const struct canditer *ci, BUN lo, BUN hi)
     379             : {
     380             :         BUN n;
     381       96459 :         assert(lo <= hi);
     382       96459 :         assert(ci->tpe == cand_mask);
     383       96459 :         if (lo == hi)
     384             :                 return 0;
     385       96459 :         lo += ci->firstbit;
     386       96459 :         hi += ci->firstbit;
     387       96459 :         BUN loi = lo / 32;
     388       96459 :         BUN hii = hi / 32;
     389       96459 :         lo %= 32;
     390       96459 :         hi %= 32;
     391       96459 :         if (loi == hii)
     392       16393 :                 return (BUN) candmask_pop((ci->mask[loi] & ((1U << hi) - 1)) >> lo);
     393       80066 :         n = (BUN) candmask_pop(ci->mask[loi++] >> lo);
     394     2516289 :         while (loi < hii)
     395     2436223 :                 n += (BUN) candmask_pop(ci->mask[loi++]);
     396       80066 :         if (hi != 0)
     397        9260 :                 n += (BUN) candmask_pop(ci->mask[loi] & ((1U << hi) - 1));
     398             :         return n;
     399             : }
     400             : 
     401             : /* initialize a candidate iterator, return number of iterations */
     402             : BUN
     403     7287802 : canditer_init(struct canditer *ci, BAT *b, BAT *s)
     404             : {
     405     7287802 :         assert(ci != NULL);
     406             : 
     407     7287802 :         if (s == NULL) {
     408     4460838 :                 if (b == NULL) {
     409             :                         /* trivially empty candidate list */
     410           0 :                         *ci = (struct canditer) {
     411             :                                 .tpe = cand_dense,
     412             :                         };
     413             :                         return 0;
     414             :                 }
     415             :                 /* every row is a candidate */
     416     4460838 :                 *ci = (struct canditer) {
     417             :                         .tpe = cand_dense,
     418     4460838 :                         .seq = b->hseqbase,
     419             :                         .hseq = b->hseqbase,
     420     4460838 :                         .ncand = BATcount(b),
     421             :                 };
     422     4460838 :                 return ci->ncand;
     423             :         }
     424             : 
     425     2826964 :         assert(ATOMtype(s->ttype) == TYPE_oid || s->ttype == TYPE_msk);
     426     2826964 :         assert(s->ttype == TYPE_msk|| s->tsorted);
     427     2826964 :         assert(s->ttype == TYPE_msk|| s->tkey);
     428     2826964 :         assert(s->ttype == TYPE_msk|| s->tnonil);
     429     2826964 :         assert(s->ttype == TYPE_void || s->tvheap == NULL);
     430             : 
     431     2826964 :         BUN cnt = BATcount(s);
     432             : 
     433     2826964 :         if (cnt == 0 || (b != NULL && BATcount(b) == 0)) {
     434             :                 /* candidate list for empty BAT or empty candidate list */
     435     1302864 :                 *ci = (struct canditer) {
     436             :                         .tpe = cand_dense,
     437     1302864 :                         .hseq = s->hseqbase,
     438             :                         .s = s,
     439             :                 };
     440             :                 return 0;
     441             :         }
     442             : 
     443     1524100 :         *ci = (struct canditer) {
     444     1524100 :                 .seq = s->tseqbase,
     445     1524100 :                 .hseq = s->hseqbase,
     446             :                 .s = s,
     447             :         };
     448             : 
     449     1524100 :         if (mask_cand(s)) {
     450       96704 :                 ci->tpe = cand_mask;
     451       96704 :                 ci->mask = (const uint32_t *) ccand_first(s);
     452       96704 :                 ci->seq = s->tseqbase - (oid) CCAND(s)->firstbit;
     453             :                 ci->hseq = s->hseqbase;
     454       96704 :                 ci->nvals = ccand_free(s) / sizeof(uint32_t);
     455       96704 :                 cnt = ci->nvals * 32;
     456     1427396 :         } else if (s->ttype == TYPE_msk) {
     457           0 :                 assert(0);
     458             :                 ci->tpe = cand_mask;
     459             :                 ci->mask = (const uint32_t *) s->theap->base;
     460             :                 ci->seq = s->hseqbase;
     461             :                 ci->nvals = (cnt + 31U) / 32U;
     462     1427396 :         } else if (s->ttype == TYPE_void) {
     463     1128909 :                 assert(!is_oid_nil(ci->seq));
     464     1128909 :                 if (s->tvheap) {
     465       66016 :                         assert(ccand_free(s) % SIZEOF_OID == 0);
     466       66016 :                         ci->nvals = ccand_free(s) / SIZEOF_OID;
     467       66016 :                         if (ci->nvals > 0) {
     468       66024 :                                 ci->tpe = cand_except;
     469       66024 :                                 ci->oids = (const oid *) ccand_first(s);
     470             :                         } else {
     471             :                                 /* why the vheap? */
     472             :                                 ci->tpe = cand_dense;
     473             :                         }
     474             :                 } else {
     475             :                         ci->tpe = cand_dense;
     476             :                 }
     477      298487 :         } else if (is_oid_nil(ci->seq)) {
     478      260693 :                 ci->tpe = cand_materialized;
     479      260693 :                 ci->oids = (const oid *) Tloc(s, 0);
     480      260693 :                 ci->seq = ci->oids[0];
     481      260693 :                 ci->nvals = cnt;
     482             :         } else {
     483             :                 /* materialized dense: no exceptions */
     484             :                 ci->tpe = cand_dense;
     485             :         }
     486     1524100 :         switch (ci->tpe) {
     487      260785 :         case cand_materialized:
     488      260785 :                 if (b != NULL) {
     489      172209 :                         BUN p = binsearchcand(ci->oids, cnt - 1U, b->hseqbase);
     490             :                         /* p == cnt means candidate list is completely
     491             :                          * before b */
     492      172294 :                         ci->offset = p;
     493      172294 :                         ci->oids += p;
     494      172294 :                         cnt -= p;
     495      172294 :                         if (cnt > 0) {
     496      172218 :                                 cnt = binsearchcand(ci->oids, cnt  - 1U,
     497      172218 :                                                     b->hseqbase + BATcount(b));
     498             :                                 /* cnt == 0 means candidate list is
     499             :                                  * completely after b */
     500             :                         }
     501      172228 :                         if (cnt == 0) {
     502             :                                 /* no overlap */
     503           0 :                                 *ci = (struct canditer) {
     504             :                                         .tpe = cand_dense,
     505             :                                         .s = s,
     506             :                                 };
     507             :                                 return 0;
     508             :                         }
     509      172228 :                         ci->seq = ci->oids[0];
     510      172228 :                         ci->nvals = cnt;
     511      172228 :                         if (ci->oids[cnt - 1U] - ci->seq == cnt - 1U) {
     512             :                                 /* actually dense */
     513           3 :                                 ci->tpe = cand_dense;
     514           3 :                                 ci->oids = NULL;
     515           3 :                                 ci->nvals = 0;
     516             :                         }
     517             :                 }
     518             :                 break;
     519       66016 :         case cand_except:
     520             :                 /* exceptions must all be within range of s */
     521       66016 :                 assert(ci->oids[0] >= ci->seq);
     522       66016 :                 assert(ci->oids[ci->nvals - 1U] < ci->seq + cnt + ci->nvals);
     523             :                 /* prune exceptions at either end of range of s */
     524     3398622 :                 while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
     525     3332606 :                         ci->nvals--;
     526     3332606 :                         ci->oids++;
     527     3332606 :                         ci->seq++;
     528             :                 }
     529       66016 :                 while (ci->nvals > 0 &&
     530       64368 :                        ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
     531           0 :                         ci->nvals--;
     532       66016 :                 if (b != NULL) {
     533       63307 :                         if (ci->seq + cnt + ci->nvals <= b->hseqbase ||
     534       63307 :                             ci->seq >= b->hseqbase + BATcount(b)) {
     535             :                                 /* candidate list does not overlap with b */
     536           0 :                                 *ci = (struct canditer) {
     537             :                                         .tpe = cand_dense,
     538             :                                         .s = s,
     539             :                                 };
     540             :                                 return 0;
     541             :                         }
     542             :                 }
     543       66016 :                 if (ci->nvals > 0) {
     544       64356 :                         if (b == NULL)
     545             :                                 break;
     546             :                         BUN p;
     547       61824 :                         p = binsearchcand(ci->oids, ci->nvals - 1U, b->hseqbase);
     548       61824 :                         if (p == ci->nvals) {
     549             :                                 /* all exceptions before start of b */
     550           0 :                                 ci->offset = b->hseqbase - ci->seq - ci->nvals;
     551           0 :                                 cnt = ci->seq + cnt + ci->nvals - b->hseqbase;
     552           0 :                                 ci->seq = b->hseqbase;
     553           0 :                                 ci->nvals = 0;
     554           0 :                                 ci->tpe = cand_dense;
     555           0 :                                 ci->oids = NULL;
     556           0 :                                 break;
     557             :                         }
     558       61824 :                         assert(b->hseqbase > ci->seq || p == 0);
     559       61824 :                         if (b->hseqbase > ci->seq) {
     560             :                                 /* skip candidates, possibly including
     561             :                                  * exceptions */
     562           0 :                                 ci->oids += p;
     563           0 :                                 ci->nvals -= p;
     564           0 :                                 p = b->hseqbase - ci->seq - p;
     565           0 :                                 cnt -= p;
     566           0 :                                 ci->offset += p;
     567           0 :                                 ci->seq = b->hseqbase;
     568             :                         }
     569       61824 :                         if (ci->seq + cnt + ci->nvals > b->hseqbase + BATcount(b)) {
     570           0 :                                 p = binsearchcand(ci->oids, ci->nvals - 1U,
     571             :                                                   b->hseqbase + BATcount(b));
     572           0 :                                 ci->nvals = p;
     573           0 :                                 cnt = b->hseqbase + BATcount(b) - ci->seq - ci->nvals;
     574             :                         }
     575       61824 :                         while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
     576           0 :                                 ci->nvals--;
     577           0 :                                 ci->oids++;
     578           0 :                                 ci->seq++;
     579             :                         }
     580       61824 :                         while (ci->nvals > 0 &&
     581       61824 :                                ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
     582           0 :                                 ci->nvals--;
     583       61824 :                         if (ci->nvals > 0)
     584             :                                 break;
     585             :                 }
     586        1660 :                 ci->tpe = cand_dense;
     587        1660 :                 ci->oids = NULL;
     588             :                 /* fall through */
     589     1102440 :         case cand_dense:
     590     1102440 :                 if (b != NULL) {
     591      922183 :                         if (ci->seq + cnt <= b->hseqbase ||
     592      922183 :                             ci->seq >= b->hseqbase + BATcount(b)) {
     593             :                                 /* no overlap */
     594           0 :                                 *ci = (struct canditer) {
     595             :                                         .tpe = cand_dense,
     596             :                                         .s = s,
     597             :                                 };
     598             :                                 return 0;
     599             :                         }
     600      922183 :                         if (b->hseqbase > ci->seq) {
     601           0 :                                 cnt -= b->hseqbase - ci->seq;
     602           0 :                                 ci->offset += b->hseqbase - ci->seq;
     603           0 :                                 ci->seq = b->hseqbase;
     604             :                         }
     605      922183 :                         if (ci->seq + cnt > b->hseqbase + BATcount(b))
     606           1 :                                 cnt = b->hseqbase + BATcount(b) - ci->seq;
     607             :                 }
     608             :                 break;
     609       96519 :         case cand_mask:
     610       96519 :                 assert(s->tseqbase != oid_nil);
     611       96519 :                 if (b != NULL) {
     612       41061 :                         if (ci->seq + cnt <= b->hseqbase ||
     613       41061 :                             ci->seq >= b->hseqbase + BATcount(b)) {
     614             :                                 /* no overlap */
     615           0 :                                 *ci = (struct canditer) {
     616             :                                         .tpe = cand_dense,
     617             :                                         .s = s,
     618             :                                 };
     619             :                                 return 0;
     620             :                         }
     621       41061 :                         if (b->hseqbase > ci->seq) {
     622           0 :                                 cnt = b->hseqbase - ci->seq;
     623           0 :                                 ci->mask += cnt / 32U;
     624           0 :                                 ci->firstbit = (uint8_t) (cnt % 32U);
     625           0 :                                 cnt = BATcount(s) - cnt;
     626           0 :                                 ci->seq = b->hseqbase;
     627             :                         }
     628       41061 :                         if (ci->seq + cnt > b->hseqbase + BATcount(b)) {
     629       41045 :                                 cnt = b->hseqbase + BATcount(b) - ci->seq;
     630             :                         }
     631       41061 :                         ci->nvals = (ci->firstbit + cnt + 31U) / 32U;
     632             :                 }
     633             :                 /* if first value is only partially used, check
     634             :                  * whether there are any 1 bits in the used part */
     635       96519 :                 if (ci->firstbit > 0 && (ci->mask[0] >> ci->firstbit) == 0) {
     636           0 :                         if (cnt <= 32U - ci->firstbit) {
     637             :                                 cnt = 0;
     638             :                                 /* returns below */
     639             :                         } else {
     640           0 :                                 cnt -= 32U - ci->firstbit;
     641           0 :                                 ci->firstbit = 0;
     642           0 :                                 ci->mask++;
     643           0 :                                 ci->nvals--;
     644             :                         }
     645             :                 }
     646             :                 /* skip over any zero mask words that are used completely */
     647       96519 :                 if (ci->firstbit == 0) {
     648      408853 :                         while (cnt >= 32U && ci->mask[0] == 0) {
     649      312247 :                                 cnt -= 32U;
     650      312247 :                                 ci->mask++;
     651      312247 :                                 ci->nvals--;
     652             :                         }
     653             :                 }
     654             :                 /* check whether there are any 1 bits in the last word */
     655       96519 :                 if (cnt == 0 ||
     656       96519 :                     (cnt < 32U - ci->firstbit &&
     657       16397 :                      ((ci->mask[0] >> ci->firstbit) & ((1U << cnt) - 1U)) == 0)) {
     658             :                         /* no one bits in the whole relevant portion
     659             :                          * of the bat */
     660           0 :                         *ci = (struct canditer) {
     661             :                                 .tpe = cand_dense,
     662             :                                 .s = s,
     663             :                         };
     664             :                         return 0;
     665             :                 }
     666             :                 /* here we know there are 1 bits in the first mask
     667             :                  * word */
     668       96519 :                 int i = candmask_lobit(ci->mask[0] >> ci->firstbit);
     669       96519 :                 assert(i >= 0);      /* there should be a set bit */
     670       96519 :                 ci->firstbit += i;
     671       96519 :                 cnt -= i;
     672       96519 :                 if (mask_cand(s))
     673       96510 :                         ci->mskoff = s->tseqbase - (oid) CCAND(s)->firstbit + (ci->mask - (const uint32_t *) ccand_first(s)) * 32U;
     674             :                 else
     675           9 :                         ci->mskoff = s->tseqbase + (ci->mask - (const uint32_t *) s->theap->base) * 32U;
     676       96519 :                 ci->seq = ci->mskoff + ci->firstbit;
     677       96519 :                 ci->nextbit = ci->firstbit;
     678             :                 /* at this point we know that bit ci->firstbit is set
     679             :                  * in ci->mask[0] */
     680       96519 :                 ci->lastbit = (ci->firstbit + cnt - 1U) % 32U + 1U;
     681       96519 :                 if (ci->lastbit < 32 &&
     682       41049 :                     (ci->mask[ci->nvals - 1] & ((1U << ci->lastbit) - 1)) == 0) {
     683             :                         /* last partial word is all zero */
     684       15402 :                         cnt -= ci->lastbit;
     685       15402 :                         ci->lastbit = 32;
     686       15402 :                         ci->nvals--;
     687             :                 }
     688       96519 :                 if (ci->lastbit == 32) {
     689             :                         /* "remove" zero words at the end */
     690      252007 :                         while (cnt >= 32 && ci->mask[ci->nvals - 1] == 0) {
     691      181090 :                                 ci->nvals--;
     692      181090 :                                 cnt -= 32;
     693             :                         }
     694             :                 }
     695       96519 :                 ci->ncand = count_mask_bits(ci, 0, cnt);
     696       96677 :                 return ci->ncand;
     697             :         }
     698       64356 :         ci->ncand = cnt;
     699     1427600 :         ci->hseq += ci->offset;
     700     1427600 :         return cnt;
     701             : }
     702             : 
     703             : /* return the next candidate without advancing */
     704             : oid
     705     2027643 : canditer_peek(struct canditer *ci)
     706             : {
     707     2027643 :         oid o = oid_nil;
     708     2027643 :         if (ci->next == ci->ncand)
     709             :                 return oid_nil;
     710     2022148 :         switch (ci->tpe) {
     711     1828487 :         case cand_dense:
     712     1828487 :                 o = ci->seq + ci->next;
     713     1828487 :                 break;
     714      191628 :         case cand_materialized:
     715      191628 :                 assert(ci->next < ci->nvals);
     716      191628 :                 o = ci->oids[ci->next];
     717      191628 :                 break;
     718        2033 :         case cand_except:
     719        2033 :                 o = ci->seq + ci->add + ci->next;
     720        2038 :                 while (ci->add < ci->nvals && o == ci->oids[ci->add]) {
     721           5 :                         ci->add++;
     722           5 :                         o++;
     723             :                 }
     724             :                 break;
     725             :         case cand_mask:
     726           0 :                 while ((ci->mask[ci->nextmsk] >> ci->nextbit) == 0) {
     727           0 :                         ci->nextmsk++;
     728           0 :                         ci->nextbit = 0;
     729             :                 }
     730           0 :                 ci->nextbit += candmask_lobit(ci->mask[ci->nextmsk] >> ci->nextbit);
     731           0 :                 o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
     732           0 :                 break;
     733             :         }
     734             :         return o;
     735             : }
     736             : 
     737             : /* return the previous candidate */
     738             : oid
     739        1648 : canditer_prev(struct canditer *ci)
     740             : {
     741        1648 :         if (ci->next == 0)
     742           0 :                 return oid_nil;
     743        1648 :         switch (ci->tpe) {
     744        1648 :         case cand_dense:
     745        1648 :                 return ci->seq + --ci->next;
     746           0 :         case cand_materialized:
     747           0 :                 return ci->oids[--ci->next];
     748             :         case cand_except:
     749             :                 break;
     750           0 :         case cand_mask:
     751             :                 for (;;) {
     752           0 :                         if (ci->nextbit == 0) {
     753           0 :                                 ci->nextbit = 32;
     754           0 :                                 while (ci->mask[--ci->nextmsk] == 0)
     755             :                                         ;
     756             :                         }
     757           0 :                         if (ci->mask[ci->nextmsk] & (1U << --ci->nextbit))
     758             :                                 break;
     759             :                 }
     760           0 :                 ci->next--;
     761           0 :                 return ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
     762             :         }
     763           0 :         oid o = ci->seq + ci->add + --ci->next;
     764           0 :         while (ci->add > 0 && o == ci->oids[ci->add - 1]) {
     765           0 :                 ci->add--;
     766           0 :                 o--;
     767             :         }
     768             :         return o;
     769             : }
     770             : 
     771             : /* return the previous candidate without retreating */
     772             : oid
     773        2792 : canditer_peekprev(struct canditer *ci)
     774             : {
     775        2792 :         oid o = oid_nil;
     776             : 
     777        2792 :         if (ci->next == 0)
     778             :                 return oid_nil;
     779        2792 :         switch (ci->tpe) {
     780        2792 :         case cand_dense:
     781        2792 :                 return ci->seq + ci->next - 1;
     782           0 :         case cand_materialized:
     783           0 :                 return ci->oids[ci->next - 1];
     784           0 :         case cand_except:
     785           0 :                 o = ci->seq + ci->add + ci->next - 1;
     786           0 :                 while (ci->add > 0 && o == ci->oids[ci->add - 1]) {
     787           0 :                         ci->add--;
     788           0 :                         o--;
     789             :                 }
     790             :                 break;
     791           0 :         case cand_mask:
     792             :                 do {
     793           0 :                         if (ci->nextbit == 0) {
     794           0 :                                 ci->nextbit = 32;
     795           0 :                                 while (ci->mask[--ci->nextmsk] == 0)
     796             :                                         ;
     797             :                         }
     798           0 :                 } while ((ci->mask[ci->nextmsk] & (1U << --ci->nextbit)) == 0);
     799           0 :                 o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
     800           0 :                 if (++ci->nextbit == 32) {
     801           0 :                         ci->nextbit = 0;
     802           0 :                         ci->nextmsk++;
     803             :                 }
     804             :                 break;
     805             :         }
     806             :         return o;
     807             : }
     808             : 
     809             : /* if o is a candidate, return it, else return the next candidate from
     810             :  * the cand_mask iterator ci after (if next is set) or before (if next
     811             :  * is unset) o; if there are no more candidates, return oid_nil */
     812             : oid
     813           0 : canditer_mask_next(const struct canditer *ci, oid o, bool next)
     814             : {
     815           0 :         if (o < ci->mskoff)
     816           0 :                 return next ? ci->mskoff + ci->firstbit : oid_nil;
     817           0 :         o -= ci->mskoff;
     818           0 :         BUN p = o / 32;
     819           0 :         o %= 32;
     820           0 :         if (p >= ci->nvals || (p == ci->nvals - 1 && o >= ci->lastbit))
     821           0 :                 return next ? oid_nil : canditer_last(ci);
     822           0 :         if (next) {
     823           0 :                 while ((ci->mask[p] & (1U << o)) == 0) {
     824           0 :                         if (++o == 32) {
     825             :                                 o = 0;
     826           0 :                                 if (++p == ci->nvals)
     827           0 :                                         return oid_nil;
     828             :                         }
     829             :                 }
     830           0 :                 if (p == ci->nvals - 1 && o >= ci->lastbit)
     831           0 :                         return oid_nil;
     832             :         } else {
     833           0 :                 while ((ci->mask[p] & (1U << o)) == 0) {
     834           0 :                         if (o == 0) {
     835             :                                 o = 31;
     836           0 :                                 if (p == 0)
     837           0 :                                         return oid_nil;
     838             :                         } else {
     839           0 :                                 o--;
     840             :                         }
     841             :                 }
     842           0 :                 if (p == 0 && o < ci->firstbit)
     843           0 :                         return oid_nil;
     844             :         }
     845           0 :         return ci->mskoff + 32 * p + o;
     846             : }
     847             : 
     848             : /* return the last candidate */
     849             : oid
     850     1110259 : canditer_last(const struct canditer *ci)
     851             : {
     852     1110259 :         if (ci->ncand == 0)
     853           0 :                 return oid_nil;
     854     1110259 :         switch (ci->tpe) {
     855      850178 :         case cand_dense:
     856      850178 :                 return ci->seq + ci->ncand - 1;
     857      164410 :         case cand_materialized:
     858      164410 :                 return ci->oids[ci->ncand - 1];
     859       61656 :         case cand_except:
     860       61656 :                 return ci->seq + ci->ncand + ci->nvals - 1;
     861       33928 :         case cand_mask:
     862      242161 :                 for (uint8_t i = ci->lastbit; i > 0; ) {
     863      242248 :                         if (ci->mask[ci->nvals - 1] & (1U << --i))
     864       34015 :                                 return ci->mskoff + (ci->nvals - 1) * 32 + i;
     865             :                 }
     866             :                 break;          /* cannot happen */
     867             :         }
     868           0 :         return oid_nil;         /* cannot happen */
     869             : }
     870             : 
     871             : /* return the candidate at the given index */
     872             : oid
     873    78804565 : canditer_idx(const struct canditer *ci, BUN p)
     874             : {
     875    78804565 :         if (p >= ci->ncand)
     876           0 :                 return oid_nil;
     877    78804565 :         switch (ci->tpe) {
     878     4985461 :         case cand_dense:
     879     4985461 :                 return ci->seq + p;
     880    73719482 :         case cand_materialized:
     881    73719482 :                 return ci->oids[p];
     882       99542 :         case cand_except: {
     883       99542 :                 oid o = ci->seq + p;
     884       99542 :                 if (o < ci->oids[0])
     885             :                         return o;
     886       72241 :                 if (o + ci->nvals > ci->oids[ci->nvals - 1])
     887             :                         return o + ci->nvals;
     888       24888 :                 BUN lo = 0, hi = ci->nvals - 1;
     889      105795 :                 while (hi - lo > 1) {
     890       56019 :                         BUN mid = (hi + lo) / 2;
     891       56019 :                         if (ci->oids[mid] - mid > o)
     892             :                                 hi = mid;
     893             :                         else
     894             :                                 lo = mid;
     895             :                 }
     896       24888 :                 return o + hi;
     897             :         }
     898          80 :         case cand_mask: {
     899             :                 BUN x;
     900          80 :                 if ((x = candmask_pop(ci->mask[0] >> ci->firstbit)) > p) {
     901          24 :                         for (uint8_t i = ci->firstbit; ; i++) {
     902         100 :                                 if (ci->mask[0] & (1U << i)) {
     903         100 :                                         if (p == 0)
     904          76 :                                                 return ci->mskoff + i;
     905          24 :                                         p--;
     906             :                                 }
     907             :                         }
     908             :                 }
     909        1584 :                 for (BUN n = 1; n < ci->nvals; n++) {
     910        1584 :                         uint32_t mask = ci->mask[n];
     911        1584 :                         p -= x;
     912        1584 :                         x = candmask_pop(mask);
     913        1584 :                         if (x > p) {
     914          63 :                                 for (uint8_t i = 0; ; i++) {
     915          67 :                                         if (mask & (1U << i)) {
     916          56 :                                                 if (p == 0)
     917           4 :                                                         return ci->mskoff + n * 32 + i;
     918          52 :                                                 p--;
     919             :                                         }
     920             :                                 }
     921             :                         }
     922             :                 }
     923             :                 break;          /* cannot happen */
     924             :         }
     925             :         }
     926           0 :         return oid_nil;         /* cannot happen */
     927             : }
     928             : 
     929             : /* set the index for the next candidate to be returned */
     930             : void
     931      599666 : canditer_setidx(struct canditer *ci, BUN p)
     932             : {
     933      599666 :         if (p != ci->next) {
     934      569561 :                 if (p >= ci->ncand) {
     935       56267 :                         ci->next = ci->ncand;
     936       56267 :                         switch (ci->tpe) {
     937           0 :                         case cand_except:
     938           0 :                                 ci->add = ci->nvals;
     939           0 :                                 break;
     940           0 :                         case cand_mask:
     941           0 :                                 ci->nextbit = ci->lastbit;
     942           0 :                                 ci->nextmsk = ci->nvals;
     943           0 :                                 if (ci->nextbit == 32)
     944           0 :                                         ci->nextbit = 0;
     945             :                                 else
     946           0 :                                         ci->nextmsk--;
     947             :                                 break;
     948             :                         default:
     949             :                                 break;
     950             :                         }
     951             :                 } else {
     952      513294 :                         ci->next = p;
     953      513294 :                         switch (ci->tpe) {
     954         727 :                         case cand_except:
     955         727 :                                 ci->add = canditer_idx(ci, p) - ci->seq - p;
     956         727 :                                 break;
     957           0 :                         case cand_mask: {
     958           0 :                                 oid o = canditer_idx(ci, p) - ci->mskoff;
     959           0 :                                 ci->nextmsk = o / 32;
     960           0 :                                 ci->nextbit = (uint8_t) (o % 32);
     961           0 :                                 break;
     962             :                         }
     963             :                         default:
     964             :                                 break;
     965             :                         }
     966       30105 :                 }
     967             :         }
     968      599666 : }
     969             : 
     970             : /* reset */
     971             : void
     972    12511942 : canditer_reset(struct canditer *ci)
     973             : {
     974    12511942 :         if (ci->tpe == cand_mask) {
     975           0 :                 ci->nextbit = ci->firstbit;
     976           0 :                 ci->nextmsk = 0;
     977             :         } else {
     978    12511942 :                 ci->add = 0;
     979             :         }
     980    12511942 :         ci->next = 0;
     981    12511942 : }
     982             : 
     983             : /* return index of given candidate if it occurs; if the candidate does
     984             :  * not occur, if next is set, return index of next larger candidate,
     985             :  * if next is not set, return BUN_NONE */
     986             : BUN
     987     3938384 : canditer_search(const struct canditer *ci, oid o, bool next)
     988             : {
     989             :         BUN p;
     990             : 
     991     3938384 :         switch (ci->tpe) {
     992      611194 :         case cand_dense:
     993      611194 :                 if (o < ci->seq)
     994         817 :                         return next ? 0 : BUN_NONE;
     995      610377 :                 if (o >= ci->seq + ci->ncand)
     996      249645 :                         return next ? ci->ncand : BUN_NONE;
     997      360732 :                 return o - ci->seq;
     998     3201273 :         case cand_materialized:
     999     3201273 :                 if (ci->nvals == 0)
    1000             :                         return 0;
    1001     3204226 :                 p = binsearchcand(ci->oids, ci->nvals - 1, o);
    1002     3237364 :                 if (next || (p != ci->nvals && ci->oids[p] == o))
    1003     1385078 :                         return p;
    1004             :                 break;
    1005      125917 :         case cand_except:
    1006      125917 :                 if (o < ci->seq)
    1007           0 :                         return next ? 0 : BUN_NONE;
    1008      125917 :                 if (o >= ci->seq + ci->ncand + ci->nvals)
    1009          14 :                         return next ? ci->ncand : BUN_NONE;
    1010      125903 :                 p = binsearchcand(ci->oids, ci->nvals - 1, o);
    1011      125903 :                 if (next || p == ci->nvals || ci->oids[p] != o)
    1012      112507 :                         return o - ci->seq - p;
    1013             :                 break;
    1014           0 :         case cand_mask:
    1015           0 :                 if (o < ci->mskoff) {
    1016           0 :                         return next ? 0 : BUN_NONE;
    1017             :                 }
    1018           0 :                 o -= ci->mskoff;
    1019           0 :                 p = o / 32;
    1020           0 :                 if (p >= ci->nvals)
    1021           0 :                         return next ? ci->ncand : BUN_NONE;
    1022           0 :                 o %= 32;
    1023           0 :                 if (p == ci->nvals - 1 && o >= ci->lastbit)
    1024           0 :                         return next ? ci->ncand : BUN_NONE;
    1025           0 :                 if (next || ci->mask[p] & (1U << o))
    1026           0 :                         return count_mask_bits(ci, 0, p * 32 + o) + !(ci->mask[p] & (1U << o));
    1027             :                 break;
    1028             :         }
    1029             :         return BUN_NONE;
    1030             : }
    1031             : 
    1032             : static BAT *
    1033        3836 : canditer_sliceval_mask(const struct canditer *ci, oid lo1, oid hi1, BUN cnt1,
    1034             :                        oid lo2, oid hi2, BUN cnt2)
    1035             : {
    1036        3836 :         assert(cnt2 == 0 || !is_oid_nil(lo2));
    1037        3836 :         assert(cnt2 == 0 || lo2 >= hi1);
    1038        3836 :         if (is_oid_nil(lo1) || lo1 < ci->mskoff + ci->firstbit)
    1039         164 :                 lo1 = ci->mskoff + ci->firstbit;
    1040        3836 :         if (is_oid_nil(hi1) || hi1 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
    1041        2069 :                 hi1 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
    1042             : 
    1043        3836 :         BAT *bn = COLnew(0, TYPE_oid, cnt1 + cnt2, TRANSIENT);
    1044        3837 :         if (bn == NULL)
    1045             :                 return NULL;
    1046        3837 :         bn->tkey = true;
    1047             : 
    1048        3837 :         if (hi1 > ci->mskoff) {
    1049        3677 :                 if (lo1 < ci->mskoff)
    1050             :                         lo1 = 0;
    1051             :                 else
    1052        3677 :                         lo1 -= ci->mskoff;
    1053        3677 :                 hi1 -= ci->mskoff;
    1054       32462 :                 for (oid o = lo1; o < hi1 && cnt1 > 0; o++) {
    1055       28785 :                         if (ci->mask[o / 32] & (1U << (o % 32))) {
    1056       28063 :                                 if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
    1057           0 :                                         BBPreclaim(bn);
    1058           0 :                                         return NULL;
    1059             :                                 }
    1060       28063 :                                 cnt1--;
    1061             :                         }
    1062             :                 }
    1063             :         }
    1064        3837 :         if (cnt2 > 0) {
    1065           6 :                 if (lo2 < ci->mskoff + ci->firstbit)
    1066             :                         lo2 = ci->mskoff + ci->firstbit;
    1067           6 :                 if (is_oid_nil(hi2) || hi2 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
    1068           6 :                         hi2 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
    1069             : 
    1070           6 :                 lo2 -= ci->mskoff;
    1071           6 :                 hi2 -= ci->mskoff;
    1072          16 :                 for (oid o = lo2; o < hi2 && cnt2 > 0; o++) {
    1073          10 :                         if (ci->mask[o / 32] & (1U << (o % 32))) {
    1074           8 :                                 if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
    1075           0 :                                         BBPreclaim(bn);
    1076           0 :                                         return NULL;
    1077             :                                 }
    1078           8 :                                 cnt2--;
    1079             :                         }
    1080             :                 }
    1081             :         }
    1082             :         return bn;
    1083             : }
    1084             : 
    1085             : /* return either an actual BATslice or a new BAT that contains the
    1086             :  * "virtual" slice of the input candidate list BAT; except, unlike
    1087             :  * BATslice, the hseqbase of the returned BAT is 0; note for cand_mask
    1088             :  * candidate iterators, the BUN values refer to number of 1 bits */
    1089             : BAT *
    1090      332391 : canditer_slice(const struct canditer *ci, BUN lo, BUN hi)
    1091             : {
    1092             :         BAT *bn;
    1093             :         oid o;
    1094             :         BUN add;
    1095             : 
    1096      332391 :         assert(ci != NULL);
    1097             : 
    1098      332391 :         if (lo >= ci->ncand || lo >= hi)
    1099      176652 :                 return BATdense(0, 0, 0);
    1100             :         if (hi > ci->ncand)
    1101             :                 hi = ci->ncand;
    1102      155739 :         switch (ci->tpe) {
    1103        5255 :         case cand_materialized:
    1104        5255 :                 if (ci->s) {
    1105        5255 :                         bn = BATslice(ci->s, lo + ci->offset, hi + ci->offset);
    1106        5254 :                         BAThseqbase(bn, 0);
    1107        5253 :                         return bn;
    1108             :                 }
    1109           0 :                 bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
    1110           0 :                 if (bn == NULL)
    1111             :                         return NULL;
    1112           0 :                 BATsetcount(bn, hi - lo);
    1113           0 :                 memcpy(Tloc(bn, 0), ci->oids + lo, (hi - lo) * sizeof(oid));
    1114           0 :                 break;
    1115      150301 :         default: /* really: case cand_dense: */
    1116      150301 :                 return BATdense(0, ci->seq + lo, hi - lo);
    1117         103 :         case cand_except:
    1118         103 :                 o = canditer_idx(ci, lo);
    1119         103 :                 add = o - ci->seq - lo;
    1120         103 :                 assert(add <= ci->nvals);
    1121         103 :                 if (add == ci->nvals || o + hi - lo < ci->oids[add]) {
    1122             :                         /* after last exception or before next
    1123             :                          * exception: return dense sequence */
    1124          28 :                         return BATdense(0, o, hi - lo);
    1125             :                 }
    1126          75 :                 bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
    1127          75 :                 if (bn == NULL)
    1128             :                         return NULL;
    1129          75 :                 BATsetcount(bn, hi - lo);
    1130       22820 :                 for (oid *dst = Tloc(bn, 0); lo < hi; lo++) {
    1131       25278 :                         while (add < ci->nvals && o == ci->oids[add]) {
    1132        2533 :                                 o++;
    1133        2533 :                                 add++;
    1134             :                         }
    1135       22745 :                         *dst++ = o++;
    1136             :                 }
    1137             :                 break;
    1138          80 :         case cand_mask:
    1139          80 :                 return canditer_sliceval_mask(ci, canditer_idx(ci, lo),
    1140             :                                               oid_nil, hi - lo,
    1141             :                                               oid_nil, oid_nil, 0);
    1142             :         }
    1143          75 :         bn->tsorted = true;
    1144          75 :         bn->trevsorted = BATcount(bn) <= 1;
    1145          75 :         bn->tkey = true;
    1146          75 :         bn->tseqbase = oid_nil;
    1147          75 :         bn->tnil = false;
    1148          75 :         bn->tnonil = true;
    1149          75 :         return virtualize(bn);
    1150             : }
    1151             : 
    1152             : /* like the above, except the bounds are given by values instead of
    1153             :  * indexes */
    1154             : BAT *
    1155      177507 : canditer_sliceval(const struct canditer *ci, oid lo, oid hi)
    1156             : {
    1157      177507 :         if (ci->tpe != cand_mask) {
    1158      522291 :                 return canditer_slice(
    1159             :                         ci,
    1160      173988 :                         is_oid_nil(lo) ? 0 : canditer_search(ci, lo, true),
    1161      173757 :                         is_oid_nil(hi) ? ci->ncand : canditer_search(ci, hi, true));
    1162             :         }
    1163             : 
    1164        3750 :         return canditer_sliceval_mask(ci, lo, hi, ci->ncand,
    1165             :                                       oid_nil, oid_nil, 0);
    1166             : }
    1167             : 
    1168             : /* return the combination of two slices */
    1169             : BAT *
    1170       23838 : canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2)
    1171             : {
    1172             :         BAT *bn;
    1173             :         oid o;
    1174             :         BUN add;
    1175             : 
    1176       23838 :         assert(lo1 <= hi1);
    1177       23838 :         assert(lo2 <= hi2);
    1178       23838 :         assert(hi1 <= lo2 || (lo2 == 0 && hi2 == 0));
    1179             : 
    1180       23838 :         if (hi1 == lo2)         /* consecutive slices: combine into one */
    1181        5118 :                 return canditer_slice(ci, lo1, hi2);
    1182       18720 :         if (lo2 == hi2 || hi1 >= ci->ncand || lo2 >= ci->ncand) {
    1183             :                 /* empty second slice */
    1184       12488 :                 return canditer_slice(ci, lo1, hi1);
    1185             :         }
    1186        6232 :         if (lo1 == hi1)         /* empty first slice */
    1187        4218 :                 return canditer_slice(ci, lo2, hi2);
    1188        2014 :         if (lo1 >= ci->ncand)     /* out of range */
    1189           0 :                 return BATdense(0, 0, 0);
    1190             : 
    1191             :         if (hi2 >= ci->ncand)
    1192             :                 hi2 = ci->ncand;
    1193             : 
    1194        2014 :         bn = COLnew(0, TYPE_oid, hi1 - lo1 + hi2 - lo2, TRANSIENT);
    1195        2014 :         if (bn == NULL)
    1196             :                 return NULL;
    1197        2014 :         BATsetcount(bn, hi1 - lo1 + hi2 - lo2);
    1198        2014 :         bn->tsorted = true;
    1199        2014 :         bn->trevsorted = BATcount(bn) <= 1;
    1200        2014 :         bn->tkey = true;
    1201        2014 :         bn->tseqbase = oid_nil;
    1202        2014 :         bn->tnil = false;
    1203        2014 :         bn->tnonil = true;
    1204             : 
    1205        2014 :         oid *dst = Tloc(bn, 0);
    1206             : 
    1207        2014 :         switch (ci->tpe) {
    1208           1 :         case cand_materialized:
    1209           1 :                 memcpy(dst, ci->oids + lo1, (hi1 - lo1) * sizeof(oid));
    1210           1 :                 memcpy(dst + hi1 - lo1, ci->oids + lo2, (hi2 - lo2) * sizeof(oid));
    1211           1 :                 break;
    1212             :         case cand_dense:
    1213      907855 :                 while (lo1 < hi1)
    1214      905842 :                         *dst++ = ci->seq + lo1++;
    1215      257288 :                 while (lo2 < hi2)
    1216      255275 :                         *dst++ = ci->seq + lo2++;
    1217             :                 break;
    1218           0 :         case cand_except:
    1219           0 :                 o = canditer_idx(ci, lo1);
    1220           0 :                 add = o - ci->seq - lo1;
    1221           0 :                 assert(add <= ci->nvals);
    1222           0 :                 if (add == ci->nvals) {
    1223             :                         /* after last exception: return dense sequence */
    1224           0 :                         while (lo1 < hi1)
    1225           0 :                                 *dst++ = ci->seq + add + lo1++;
    1226             :                 } else {
    1227           0 :                         while (lo1 < hi1) {
    1228           0 :                                 while (add < ci->nvals && o == ci->oids[add]) {
    1229           0 :                                         o++;
    1230           0 :                                         add++;
    1231             :                                 }
    1232           0 :                                 *dst++ = o++;
    1233           0 :                                 lo1++;
    1234             :                         }
    1235             :                 }
    1236           0 :                 o = canditer_idx(ci, lo2);
    1237           0 :                 add = o - ci->seq - lo2;
    1238           0 :                 assert(add <= ci->nvals);
    1239           0 :                 if (add == ci->nvals) {
    1240             :                         /* after last exception: return dense sequence */
    1241           0 :                         while (lo2 < hi2)
    1242           0 :                                 *dst++ = ci->seq + add + lo2++;
    1243             :                 } else {
    1244           0 :                         while (lo2 < hi2) {
    1245           0 :                                 while (add < ci->nvals && o == ci->oids[add]) {
    1246           0 :                                         o++;
    1247           0 :                                         add++;
    1248             :                                 }
    1249           0 :                                 *dst++ = o++;
    1250           0 :                                 lo2++;
    1251             :                         }
    1252             :                 }
    1253             :                 break;
    1254           0 :         case cand_mask:
    1255           0 :                 return canditer_sliceval_mask(ci, canditer_idx(ci, lo1),
    1256             :                                               oid_nil, hi1 - lo1,
    1257             :                                               canditer_idx(ci, lo2),
    1258             :                                               oid_nil, hi2 - lo2);
    1259             :         }
    1260        2014 :         return virtualize(bn);
    1261             : }
    1262             : 
    1263             : BAT *
    1264       23833 : canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2)
    1265             : {
    1266       23833 :         if (ci->tpe != cand_mask) {
    1267       95381 :                 return canditer_slice2(
    1268             :                         ci,
    1269       16210 :                         is_oid_nil(lo1) ? 0 : canditer_search(ci, lo1, true),
    1270       23830 :                         is_oid_nil(hi1) ? ci->ncand : canditer_search(ci, hi1, true),
    1271       23827 :                         is_oid_nil(lo2) ? 0 : canditer_search(ci, lo2, true),
    1272        7654 :                         is_oid_nil(hi2) ? ci->ncand : canditer_search(ci, hi2, true));
    1273             :         }
    1274             : 
    1275           6 :         return canditer_sliceval_mask(ci, lo1, hi1, ci->ncand,
    1276             :                                       lo2, hi2, ci->ncand);
    1277             : }
    1278             : 
    1279             : BAT *
    1280          44 : BATnegcands(BUN nr, BAT *odels)
    1281             : {
    1282             :         const char *nme;
    1283             :         Heap *dels;
    1284             :         BUN lo, hi;
    1285             :         ccand_t *c;
    1286             :         BAT *bn;
    1287             : 
    1288          44 :         bn = BATdense(0, 0, nr);
    1289          44 :         if (bn == NULL)
    1290             :                 return NULL;
    1291          44 :         if (BATcount(odels) == 0)
    1292             :                 return bn;
    1293             : 
    1294          44 :         lo = SORTfndfirst(odels, &bn->tseqbase);
    1295          44 :         hi = SORTfndfirst(odels, &(oid) {bn->tseqbase + BATcount(bn)});
    1296          44 :         if (lo == hi)
    1297             :                 return bn;
    1298             : 
    1299          44 :         nme = BBP_physical(bn->batCacheid);
    1300          44 :         if ((dels = (Heap*)GDKzalloc(sizeof(Heap))) == NULL ||
    1301          44 :             (dels->farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap)) < 0){
    1302           0 :                 GDKfree(dels);
    1303           0 :                 BBPreclaim(bn);
    1304           0 :                 return NULL;
    1305             :         }
    1306          44 :         strconcat_len(dels->filename, sizeof(dels->filename),
    1307             :                       nme, ".theap", NULL);
    1308             : 
    1309          44 :         if (HEAPalloc(dels, hi - lo + (sizeof(ccand_t)/sizeof(oid)), sizeof(oid), 0) != GDK_SUCCEED) {
    1310           0 :                 GDKfree(dels);
    1311           0 :                 BBPreclaim(bn);
    1312           0 :                 return NULL;
    1313             :         }
    1314          44 :         ATOMIC_INIT(&dels->refs, 1);
    1315          44 :         c = (ccand_t *) dels->base;
    1316          44 :         *c = (ccand_t) {
    1317             :                 .type = CAND_NEGOID,
    1318             :         };
    1319          44 :         dels->parentid = bn->batCacheid;
    1320          44 :         dels->free = sizeof(ccand_t) + sizeof(oid) * (hi - lo);
    1321          44 :         dels->dirty = true;
    1322          44 :         BATiter bi = bat_iterator(odels);
    1323          44 :         if (odels->ttype == TYPE_void) {
    1324           0 :                 oid *r = (oid *) (dels->base + sizeof(ccand_t));
    1325           0 :                 for (BUN x = lo; x < hi; x++)
    1326           0 :                         r[x - lo] = x + odels->tseqbase;
    1327             :         } else {
    1328          44 :                 oid *r = (oid *) (dels->base + sizeof(ccand_t));
    1329          44 :                 memcpy(r, (const oid *) bi.base + lo, sizeof(oid) * (hi - lo));
    1330             :         }
    1331          44 :         bat_iterator_end(&bi);
    1332          44 :         bn->batDirtydesc = true;
    1333          44 :         assert(bn->tvheap == NULL);
    1334          44 :         bn->tvheap = dels;
    1335          44 :         BATsetcount(bn, bn->batCount - (hi - lo));
    1336          44 :         TRC_DEBUG(ALGO, "BATnegcands(cands=" ALGOBATFMT ","
    1337             :                   "dels=" ALGOBATFMT ")\n",
    1338             :                   ALGOBATPAR(bn),
    1339             :                   ALGOBATPAR(odels));
    1340          44 :         TRC_DEBUG(ALGO, "nr=" BUNFMT ", odels=" ALGOBATFMT
    1341             :                   " -> " ALGOBATFMT "\n",
    1342             :                   nr, ALGOBATPAR(odels),
    1343             :                   ALGOBATPAR(bn));
    1344             :         return bn;
    1345             : }
    1346             : 
    1347             : BAT *
    1348      142308 : BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected)
    1349             : {
    1350             :         const char *nme;
    1351             :         Heap *msks;
    1352             :         ccand_t *c;
    1353             :         BUN nmask;
    1354             :         BAT *bn;
    1355             : 
    1356      142308 :         assert(masked->ttype == TYPE_msk);
    1357             : 
    1358      142308 :         bn = COLnew(hseq, TYPE_void, 0, TRANSIENT);
    1359      142308 :         if (bn == NULL)
    1360             :                 return NULL;
    1361      142308 :         BATtseqbase(bn, hseq);
    1362             : 
    1363      142306 :         if (BATcount(masked) == 0)
    1364             :                 return bn;
    1365             : 
    1366      142308 :         nme = BBP_physical(bn->batCacheid);
    1367      142308 :         if ((msks = (Heap*)GDKzalloc(sizeof(Heap))) == NULL ||
    1368      142306 :             (msks->farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap)) < 0){
    1369           0 :                 GDKfree(msks);
    1370           0 :                 BBPreclaim(bn);
    1371           0 :                 return NULL;
    1372             :         }
    1373      142308 :         strconcat_len(msks->filename, sizeof(msks->filename),
    1374             :                       nme, ".theap", NULL);
    1375             : 
    1376      142305 :         nmask = (nr + 31) / 32;
    1377      142305 :         if (HEAPalloc(msks, nmask + (sizeof(ccand_t)/sizeof(uint32_t)), sizeof(uint32_t), 0) != GDK_SUCCEED) {
    1378           0 :                 GDKfree(msks);
    1379           0 :                 BBPreclaim(bn);
    1380           0 :                 return NULL;
    1381             :         }
    1382      142306 :         c = (ccand_t *) msks->base;
    1383      142306 :         *c = (ccand_t) {
    1384             :                 .type = CAND_MSK,
    1385             : //              .mask = true,
    1386             :         };
    1387      142306 :         msks->parentid = bn->batCacheid;
    1388      142306 :         msks->free = sizeof(ccand_t) + nmask * sizeof(uint32_t);
    1389      142306 :         msks->dirty = true;
    1390      142306 :         uint32_t *r = (uint32_t*)(msks->base + sizeof(ccand_t));
    1391      142306 :         BATiter bi = bat_iterator(masked);
    1392      142301 :         if (selected) {
    1393      142261 :                 if (nr <= bi.count)
    1394      142261 :                         memcpy(r, bi.base, nmask * sizeof(uint32_t));
    1395             :                 else
    1396           0 :                         memcpy(r, bi.base, (bi.count + 31) / 32 * sizeof(uint32_t));
    1397             :         } else {
    1398          40 :                 const uint32_t *s = (const uint32_t *) bi.base;
    1399          40 :                 BUN nmask_ = (bi.count + 31) / 32;
    1400        3318 :                 for (BUN i = 0; i < nmask_; i++)
    1401        3278 :                         r[i] = ~s[i];
    1402             :         }
    1403      142301 :         if (nr > bi.count) {
    1404           0 :                 BUN rest = bi.count & 31;
    1405           0 :                 BUN nmask_ = (bi.count + 31) / 32;
    1406           0 :                 if (rest > 0)
    1407           0 :                         r[nmask_ -1] |= ((1U << (32 - rest)) - 1) << rest;
    1408           0 :                 for (BUN j = nmask_; j < nmask; j++)
    1409           0 :                         r[j] = ~0;
    1410             :         }
    1411      142301 :         bat_iterator_end(&bi);
    1412             :         /* make sure last word doesn't have any spurious bits set */
    1413      142307 :         BUN cnt = nr % 32;
    1414      142307 :         if (cnt > 0)
    1415      141395 :                 r[nmask - 1] &= (1U << cnt) - 1;
    1416             :         cnt = 0;
    1417    11114778 :         for (BUN i = 0; i < nmask; i++) {
    1418    10972471 :                 if (cnt == 0 && r[i] != 0)
    1419      133216 :                         c->firstbit = candmask_lobit(r[i]) + i * 32;
    1420    10972471 :                 cnt += candmask_pop(r[i]);
    1421             :         }
    1422      142307 :         if (cnt > 0) {
    1423      133237 :                 ATOMIC_INIT(&msks->refs, 1);
    1424      133237 :                 assert(bn->tvheap == NULL);
    1425      133237 :                 bn->tvheap = msks;
    1426      133237 :                 bn->tseqbase += (oid) c->firstbit;
    1427             :         } else {
    1428             :                 /* no point having a mask if it's empty */
    1429        9070 :                 HEAPfree(msks, true);
    1430        9070 :                 GDKfree(msks);
    1431             :         }
    1432      142307 :         bn->batDirtydesc = true;
    1433      142307 :         BATsetcount(bn, cnt);
    1434      142309 :         TRC_DEBUG(ALGO, "hseq=" OIDFMT ", masked=" ALGOBATFMT ", selected=%s"
    1435             :                   " -> " ALGOBATFMT "\n",
    1436             :                   hseq, ALGOBATPAR(masked),
    1437             :                   selected ? "true" : "false",
    1438             :                   ALGOBATPAR(bn));
    1439      142309 :         assert(bn->tseqbase != oid_nil);
    1440             :         return bn;
    1441             : }
    1442             : 
    1443             : /* convert a masked candidate list to a positive or negative candidate list */
    1444             : BAT *
    1445       85643 : BATunmask(BAT *b)
    1446             : {
    1447             : //      assert(!mask_cand(b) || CCAND(b)->mask); /* todo handle negmask case */
    1448             :         BUN cnt;
    1449             :         uint32_t rem;
    1450             :         uint32_t val;
    1451             :         const uint32_t *src;
    1452             :         oid *dst;
    1453             :         BUN n = 0;
    1454       85643 :         oid tseq = b->hseqbase;
    1455             :         bool negcand = false;
    1456             : 
    1457       85643 :         BATiter bi = bat_iterator(b);
    1458       85694 :         if (mask_cand(b)) {
    1459       82558 :                 cnt = ccand_free(b) / sizeof(uint32_t);
    1460             :                 rem = 0;
    1461       82558 :                 src = (const uint32_t *) ccand_first(b);
    1462       82558 :                 tseq = b->tseqbase;
    1463       82558 :                 tseq -= (oid) CCAND(b)->firstbit;
    1464             :                 /* create negative candidate list if more than half the
    1465             :                  * bits are set */
    1466       82558 :                 negcand = BATcount(b) > cnt * 16;
    1467             :         } else {
    1468        3136 :                 cnt = bi.count / 32;
    1469        3136 :                 rem = bi.count % 32;
    1470        3136 :                 src = (const uint32_t *) bi.base;
    1471             :         }
    1472             :         BAT *bn;
    1473             : 
    1474       85694 :         if (negcand) {
    1475       65519 :                 bn = COLnew(b->hseqbase, TYPE_void, 0, TRANSIENT);
    1476       65497 :                 if (bn == NULL) {
    1477           0 :                         bat_iterator_end(&bi);
    1478           0 :                         return NULL;
    1479             :                 }
    1480             :                 Heap *dels;
    1481      131000 :                 if ((dels = GDKzalloc(sizeof(Heap))) == NULL ||
    1482       65501 :                     strconcat_len(dels->filename, sizeof(dels->filename),
    1483       65501 :                                   BBP_physical(bn->batCacheid), ".theap",
    1484       65502 :                                   NULL) >= sizeof(dels->filename) ||
    1485       65503 :                     (dels->farmid = BBPselectfarm(TRANSIENT, TYPE_void,
    1486       65511 :                                                   varheap)) == -1 ||
    1487       65502 :                     HEAPalloc(dels,
    1488       65502 :                               cnt * 32 - bi.count
    1489             :                               + sizeof(ccand_t) / sizeof(oid),
    1490             :                               sizeof(oid), 0) != GDK_SUCCEED) {
    1491           0 :                         GDKfree(dels);
    1492           0 :                         BBPreclaim(bn);
    1493           0 :                         bat_iterator_end(&bi);
    1494           0 :                         return NULL;
    1495             :                 }
    1496       65511 :                 dels->parentid = bn->batCacheid;
    1497       65511 :                 * (ccand_t *) dels->base = (ccand_t) {
    1498             :                         .type = CAND_NEGOID,
    1499             :                 };
    1500             :                 dst = (oid *) (dels->base + sizeof(ccand_t));
    1501     5800198 :                 for (BUN p = 0, v = 0; p < cnt; p++, v += 32) {
    1502     5734687 :                         if ((val = src[p]) == ~UINT32_C(0))
    1503     4320788 :                                 continue;
    1504    45557150 :                         for (uint32_t i = 0; i < 32; i++) {
    1505    44210006 :                                 if ((val & (1U << i)) == 0) {
    1506    39795150 :                                         if (v + i >= b->batCount + n)
    1507             :                                                 break;
    1508    39728395 :                                         dst[n++] = tseq + v + i;
    1509             :                                 }
    1510             :                         }
    1511             :                 }
    1512       65511 :                 if (n == 0) {
    1513             :                         /* didn't need it after all */
    1514         301 :                         HEAPfree(dels, true);
    1515         302 :                         GDKfree(dels);
    1516             :                 } else {
    1517       65210 :                         dels->free = sizeof(ccand_t) + n * sizeof(oid);
    1518       65210 :                         dels->dirty = true;
    1519       65210 :                         ATOMIC_INIT(&dels->refs, 1);
    1520       65210 :                         assert(bn->tvheap == NULL);
    1521       65210 :                         bn->tvheap = dels;
    1522             :                 }
    1523       65512 :                 BATsetcount(bn, n=bi.count);
    1524       65513 :                 bn->tseqbase = tseq;
    1525             :         } else {
    1526       20175 :                 bn = COLnew(b->hseqbase, TYPE_oid, mask_cand(b) ? bi.count : 1024, TRANSIENT);
    1527       20152 :                 if (bn == NULL) {
    1528           0 :                         bat_iterator_end(&bi);
    1529           0 :                         return NULL;
    1530             :                 }
    1531       20152 :                 dst = (oid *) Tloc(bn, 0);
    1532     2675385 :                 for (BUN p = 0; p < cnt; p++) {
    1533     2655212 :                         if ((val = src[p]) == 0)
    1534     1855804 :                                 continue;
    1535    26370031 :                         for (uint32_t i = 0; i < 32; i++) {
    1536    25570602 :                                 if (val & (1U << i)) {
    1537    23864150 :                                         if (n == BATcapacity(bn)) {
    1538          54 :                                                 BATsetcount(bn, n);
    1539          75 :                                                 if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
    1540           0 :                                                         BBPreclaim(bn);
    1541           0 :                                                         bat_iterator_end(&bi);
    1542           0 :                                                         return NULL;
    1543             :                                                 }
    1544          75 :                                                 dst = (oid *) Tloc(bn, 0);
    1545             :                                         }
    1546    23864171 :                                         dst[n++] = tseq + p * 32 + i;
    1547             :                                 }
    1548             :                         }
    1549             :                 }
    1550             :                 /* the last partial mask word */
    1551       20173 :                 if (rem > 0 && (val = src[cnt]) != 0) {
    1552       13059 :                         for (uint32_t i = 0; i < rem; i++) {
    1553       11894 :                                 if (val & (1U << i)) {
    1554         679 :                                         if (n == BATcapacity(bn)) {
    1555           0 :                                                 BATsetcount(bn, n);
    1556           0 :                                                 if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
    1557           0 :                                                         BBPreclaim(bn);
    1558           0 :                                                         bat_iterator_end(&bi);
    1559           0 :                                                         return NULL;
    1560             :                                                 }
    1561           0 :                                                 dst = (oid *) Tloc(bn, 0);
    1562             :                                         }
    1563         679 :                                         dst[n++] = tseq + cnt * 32 + i;
    1564             :                                 }
    1565             :                         }
    1566             :                 }
    1567       20173 :                 BATsetcount(bn, n);
    1568             :         }
    1569       85680 :         bat_iterator_end(&bi);
    1570       85695 :         bn->tkey = true;
    1571       85695 :         bn->tsorted = true;
    1572       85695 :         bn->trevsorted = n <= 1;
    1573       85695 :         bn->tnil = false;
    1574       85695 :         bn->tnonil = true;
    1575       85695 :         bn = virtualize(bn);
    1576       85682 :         TRC_DEBUG(ALGO, ALGOBATFMT " -> " ALGOBATFMT "\n", ALGOBATPAR(b), ALGOBATPAR(bn));
    1577             :         return bn;
    1578             : }

Generated by: LCOV version 1.14