LCOV - code coverage report
Current view: top level - gdk - gdk_cand.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 631 912 69.2 %
Date: 2021-10-13 02:24:04 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        8971 : BATiscand(BAT *b)
      16             : {
      17        8971 :         if (ATOMtype(b->ttype) != TYPE_oid)
      18             :                 return false;
      19        8971 :         if (complex_cand(b))
      20             :                 return true;
      21        6309 :         if (b->ttype == TYPE_void && is_oid_nil(b->tseqbase))
      22             :                 return false;
      23        6309 :         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        1779 : newdensecand(oid first, oid last)
      30             : {
      31        1779 :         if (last <= first)
      32             :                 first = last = 0; /* empty range */
      33        1779 :         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       81519 : BATmergecand(BAT *a, BAT *b)
      43             : {
      44             :         BAT *bn;
      45             :         oid *restrict p, i;
      46             :         struct canditer cia, cib;
      47             : 
      48       81519 :         BATcheck(a, NULL);
      49       81519 :         BATcheck(b, NULL);
      50             : 
      51       81519 :         canditer_init(&cia, NULL, a);
      52       81516 :         canditer_init(&cib, NULL, b);
      53             : 
      54             :         /* we can return a if b is empty (and v.v.) */
      55       81512 :         if (cia.ncand == 0) {
      56       14354 :                 bn = canditer_slice(&cib, 0, cib.ncand);
      57       14354 :                 goto doreturn;
      58             :         }
      59       67158 :         if (cib.ncand == 0) {
      60       11385 :                 bn = canditer_slice(&cia, 0, cia.ncand);
      61       11387 :                 goto doreturn;
      62             :         }
      63             :         /* we can return a if a fully covers b (and v.v) */
      64       55773 :         if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
      65             :                 /* both are dense */
      66       10007 :                 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        1424 :                         bn = newdensecand(cia.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
      70        1424 :                         goto doreturn;
      71             :                 }
      72        8583 :                 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         355 :                         bn = newdensecand(cib.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
      76         355 :                         goto doreturn;
      77             :                 }
      78             :         }
      79       53994 :         if (cia.tpe == cand_dense
      80       11317 :             && cia.seq <= cib.seq
      81        5052 :             && canditer_last(&cia) >= canditer_last(&cib)) {
      82         325 :                 bn = canditer_slice(&cia, 0, cia.ncand);
      83         325 :                 goto doreturn;
      84             :         }
      85       53669 :         if (cib.tpe == cand_dense
      86       37356 :             && cib.seq <= cia.seq
      87        9914 :             && canditer_last(&cib) >= canditer_last(&cia)) {
      88         174 :                 bn = canditer_slice(&cib, 0, cib.ncand);
      89         174 :                 goto doreturn;
      90             :         }
      91             : 
      92       53495 :         bn = COLnew(0, TYPE_oid, cia.ncand + cib.ncand, TRANSIENT);
      93       53494 :         if (bn == NULL)
      94           0 :                 goto doreturn;
      95       53494 :         p = (oid *) Tloc(bn, 0);
      96       53494 :         if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
      97             :                 /* both lists are dense */
      98        8226 :                 if (cia.seq > cib.seq) {
      99             :                         struct canditer ci;
     100        4068 :                         ci = cia;
     101        4068 :                         cia = cib;
     102        4068 :                         cib = ci;
     103             :                 }
     104             :                 /* cia completely before cib */
     105        8226 :                 assert(cia.seq + cia.ncand < cib.seq);
     106       31040 :                 for (i = cia.seq; i < cia.seq + cia.ncand; i++)
     107       22814 :                         *p++ = i;
     108             :                 /* there is a gap */
     109       27491 :                 for (i = cib.seq; i < cib.seq + cib.ncand; i++)
     110       19265 :                         *p++ = i;
     111       45268 :         } else if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
     112       31720 :                 if (cib.tpe == cand_dense) {
     113             :                         struct canditer ci;
     114       28953 :                         ci = cia;
     115       28953 :                         cia = cib;
     116       28953 :                         cib = ci;
     117             :                 }
     118             :                 /* only cia is dense */
     119             : 
     120             :                 /* copy part of cib that's before the start of cia */
     121      125660 :                 while (canditer_peek(&cib) < cia.seq) {
     122       93942 :                         *p++ = canditer_next(&cib);
     123             :                 }
     124             :                 /* copy all of cia */
     125       72550 :                 for (i = cia.seq; i < cia.seq + cia.ncand; i++)
     126       40827 :                         *p++ = i;
     127             :                 /* skip over part of cib that overlaps with cia */
     128       31723 :                 canditer_setidx(&cib, canditer_search(&cib, cia.seq + cia.ncand, true));
     129             :                 /* copy rest of cib */
     130      127396 :                 while (cib.next < cib.ncand) {
     131       95672 :                         *p++ = canditer_next(&cib);
     132             :                 }
     133             :         } else {
     134             :                 /* a and b are both not dense */
     135       13548 :                 oid ao = canditer_next(&cia);
     136       13548 :                 oid bo = canditer_next(&cib);
     137    24492844 :                 while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
     138    24479297 :                         if (ao < bo) {
     139    14763659 :                                 *p++ = ao;
     140    14763659 :                                 ao = canditer_next(&cia);
     141     9715638 :                         } else if (bo < ao) {
     142     9347351 :                                 *p++ = bo;
     143     9347351 :                                 bo = canditer_next(&cib);
     144             :                         } else {
     145      368287 :                                 *p++ = ao;
     146      368287 :                                 ao = canditer_next(&cia);
     147      368279 :                                 bo = canditer_next(&cib);
     148             :                         }
     149             :                 }
     150      428167 :                 while (!is_oid_nil(ao)) {
     151      414620 :                         *p++ = ao;
     152      414620 :                         ao = canditer_next(&cia);
     153             :                 }
     154       31792 :                 while (!is_oid_nil(bo)) {
     155       18245 :                         *p++ = bo;
     156       18245 :                         bo = canditer_next(&cib);
     157             :                 }
     158             :         }
     159             : 
     160             :         /* properties */
     161       53497 :         BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
     162       53501 :         bn->trevsorted = BATcount(bn) <= 1;
     163       53501 :         bn->tsorted = true;
     164       53501 :         bn->tkey = true;
     165       53501 :         bn->tnil = false;
     166       53501 :         bn->tnonil = true;
     167       53501 :         bn = virtualize(bn);
     168       81520 :   doreturn:
     169       81520 :         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     4635288 : binsearchcand(const oid *cand, BUN hi, oid o)
     355             : {
     356             :         BUN lo = 0;
     357             : 
     358     4635288 :         if (o <= cand[lo])
     359             :                 return 0;
     360     4326439 :         if (o > cand[hi])
     361      286507 :                 return hi + 1;
     362             :         /* loop invariant: cand[lo] < o <= cand[hi] */
     363    63057909 :         while (hi > lo + 1) {
     364    60617928 :                 BUN mid = (lo + hi) / 2;
     365    60617928 :                 if (cand[mid] == o)
     366     1599951 :                         return mid;
     367    59017977 :                 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       99397 : count_mask_bits(const struct canditer *ci, BUN lo, BUN hi)
     379             : {
     380             :         BUN n;
     381       99397 :         assert(lo <= hi);
     382       99397 :         assert(ci->tpe == cand_mask);
     383       99397 :         if (lo == hi)
     384             :                 return 0;
     385       99397 :         lo += ci->firstbit;
     386       99397 :         hi += ci->firstbit;
     387       99397 :         BUN loi = lo / 32;
     388       99397 :         BUN hii = hi / 32;
     389       99397 :         lo %= 32;
     390       99397 :         hi %= 32;
     391       99397 :         if (loi == hii)
     392        4236 :                 return (BUN) candmask_pop((ci->mask[loi] & ((1U << hi) - 1)) >> lo);
     393       95161 :         n = (BUN) candmask_pop(ci->mask[loi++] >> lo);
     394     3114372 :         while (loi < hii)
     395     3019211 :                 n += (BUN) candmask_pop(ci->mask[loi++]);
     396       95161 :         if (hi != 0)
     397       27541 :                 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     5156191 : canditer_init(struct canditer *ci, BAT *b, BAT *s)
     404             : {
     405     5156191 :         assert(ci != NULL);
     406             : 
     407     5156191 :         if (s == NULL) {
     408     2778990 :                 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     2778990 :                 *ci = (struct canditer) {
     417             :                         .tpe = cand_dense,
     418     2778990 :                         .seq = b->hseqbase,
     419             :                         .hseq = b->hseqbase,
     420     2778990 :                         .ncand = BATcount(b),
     421             :                 };
     422     2778990 :                 return ci->ncand;
     423             :         }
     424             : 
     425     2377201 :         assert(ATOMtype(s->ttype) == TYPE_oid || s->ttype == TYPE_msk);
     426     2377201 :         assert(s->ttype == TYPE_msk|| s->tsorted);
     427     2377201 :         assert(s->ttype == TYPE_msk|| s->tkey);
     428     2377201 :         assert(s->ttype == TYPE_msk|| s->tnonil);
     429     2377201 :         assert(s->ttype == TYPE_void || s->tvheap == NULL);
     430             : 
     431     2377201 :         BUN cnt = BATcount(s);
     432             : 
     433     2377201 :         if (cnt == 0 || (b != NULL && BATcount(b) == 0)) {
     434             :                 /* candidate list for empty BAT or empty candidate list */
     435      941664 :                 *ci = (struct canditer) {
     436             :                         .tpe = cand_dense,
     437      941664 :                         .hseq = s->hseqbase,
     438             :                         .s = s,
     439             :                 };
     440             :                 return 0;
     441             :         }
     442             : 
     443     1435537 :         *ci = (struct canditer) {
     444     1435537 :                 .seq = s->tseqbase,
     445     1435537 :                 .hseq = s->hseqbase,
     446             :                 .s = s,
     447             :         };
     448             : 
     449     1435537 :         if (mask_cand(s)) {
     450       99399 :                 ci->tpe = cand_mask;
     451       99399 :                 ci->mask = (const uint32_t *) ccand_first(s);
     452       99399 :                 ci->seq = s->tseqbase - (oid) CCAND(s)->firstbit;
     453             :                 ci->hseq = s->hseqbase;
     454       99399 :                 ci->nvals = ccand_free(s) / sizeof(uint32_t);
     455       99399 :                 cnt = ci->nvals * 32;
     456     1336138 :         } 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     1336138 :         } else if (s->ttype == TYPE_void) {
     463      993951 :                 assert(!is_oid_nil(ci->seq));
     464      993951 :                 if (s->tvheap) {
     465       85493 :                         assert(ccand_free(s) % SIZEOF_OID == 0);
     466       85493 :                         ci->nvals = ccand_free(s) / SIZEOF_OID;
     467       85493 :                         if (ci->nvals > 0) {
     468       85493 :                                 ci->tpe = cand_except;
     469       85493 :                                 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      342187 :         } else if (is_oid_nil(ci->seq)) {
     478      306062 :                 ci->tpe = cand_materialized;
     479      306062 :                 ci->oids = (const oid *) Tloc(s, 0);
     480      306062 :                 ci->seq = ci->oids[0];
     481      306062 :                 ci->nvals = cnt;
     482             :         } else {
     483             :                 /* materialized dense: no exceptions */
     484             :                 ci->tpe = cand_dense;
     485             :         }
     486     1435537 :         switch (ci->tpe) {
     487      306051 :         case cand_materialized:
     488      306051 :                 if (b != NULL) {
     489      201169 :                         BUN p = binsearchcand(ci->oids, cnt - 1U, b->hseqbase);
     490             :                         /* p == cnt means candidate list is completely
     491             :                          * before b */
     492      201174 :                         ci->offset = p;
     493      201174 :                         ci->oids += p;
     494      201174 :                         cnt -= p;
     495      201174 :                         if (cnt > 0) {
     496      201168 :                                 cnt = binsearchcand(ci->oids, cnt  - 1U,
     497      201168 :                                                     b->hseqbase + BATcount(b));
     498             :                                 /* cnt == 0 means candidate list is
     499             :                                  * completely after b */
     500             :                         }
     501      201169 :                         if (cnt == 0) {
     502             :                                 /* no overlap */
     503           0 :                                 *ci = (struct canditer) {
     504             :                                         .tpe = cand_dense,
     505             :                                         .s = s,
     506             :                                 };
     507             :                                 return 0;
     508             :                         }
     509      201169 :                         ci->seq = ci->oids[0];
     510      201169 :                         ci->nvals = cnt;
     511      201169 :                         if (ci->oids[cnt - 1U] - ci->seq == cnt - 1U) {
     512             :                                 /* actually dense */
     513           2 :                                 ci->tpe = cand_dense;
     514           2 :                                 ci->oids = NULL;
     515           2 :                                 ci->nvals = 0;
     516             :                         }
     517             :                 }
     518             :                 break;
     519       85493 :         case cand_except:
     520             :                 /* exceptions must all be within range of s */
     521       85493 :                 assert(ci->oids[0] >= ci->seq);
     522       85493 :                 assert(ci->oids[ci->nvals - 1U] < ci->seq + cnt + ci->nvals);
     523             :                 /* prune exceptions at either end of range of s */
     524     3745005 :                 while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
     525     3659512 :                         ci->nvals--;
     526     3659512 :                         ci->oids++;
     527     3659512 :                         ci->seq++;
     528             :                 }
     529       85493 :                 while (ci->nvals > 0 &&
     530       84914 :                        ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
     531           0 :                         ci->nvals--;
     532       85493 :                 if (b != NULL) {
     533       81684 :                         if (ci->seq + cnt + ci->nvals <= b->hseqbase ||
     534       81684 :                             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       85493 :                 if (ci->nvals > 0) {
     544       84914 :                         if (b == NULL)
     545             :                                 break;
     546             :                         BUN p;
     547       81214 :                         p = binsearchcand(ci->oids, ci->nvals - 1U, b->hseqbase);
     548       81214 :                         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       81214 :                         assert(b->hseqbase > ci->seq || p == 0);
     559       81214 :                         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       81214 :                         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       81214 :                         while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
     576           0 :                                 ci->nvals--;
     577           0 :                                 ci->oids++;
     578           0 :                                 ci->seq++;
     579             :                         }
     580       81214 :                         while (ci->nvals > 0 &&
     581       81214 :                                ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
     582           0 :                                 ci->nvals--;
     583       81214 :                         if (ci->nvals > 0)
     584             :                                 break;
     585             :                 }
     586         579 :                 ci->tpe = cand_dense;
     587         579 :                 ci->oids = NULL;
     588             :                 /* fall through */
     589      945182 :         case cand_dense:
     590      945182 :                 if (b != NULL) {
     591      809720 :                         if (ci->seq + cnt <= b->hseqbase ||
     592      809720 :                             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      809720 :                         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      809720 :                         if (ci->seq + cnt > b->hseqbase + BATcount(b))
     606           1 :                                 cnt = b->hseqbase + BATcount(b) - ci->seq;
     607             :                 }
     608             :                 break;
     609       99390 :         case cand_mask:
     610       99390 :                 assert(s->tseqbase != oid_nil);
     611       99390 :                 if (b != NULL) {
     612       41894 :                         if (ci->seq + cnt <= b->hseqbase ||
     613       41894 :                             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       41894 :                         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       41894 :                         if (ci->seq + cnt > b->hseqbase + BATcount(b)) {
     629       41777 :                                 cnt = b->hseqbase + BATcount(b) - ci->seq;
     630             :                         }
     631       41894 :                         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       99390 :                 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       99390 :                 if (ci->firstbit == 0) {
     648      339053 :                         while (cnt >= 32U && ci->mask[0] == 0) {
     649      239659 :                                 cnt -= 32U;
     650      239659 :                                 ci->mask++;
     651      239659 :                                 ci->nvals--;
     652             :                         }
     653             :                 }
     654             :                 /* check whether there are any 1 bits in the last word */
     655       99390 :                 if (cnt == 0 ||
     656       99390 :                     (cnt < 32U - ci->firstbit &&
     657        4236 :                      ((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       99390 :                 int i = candmask_lobit(ci->mask[0] >> ci->firstbit);
     669       99390 :                 assert(i >= 0);      /* there should be a set bit */
     670       99390 :                 ci->firstbit += i;
     671       99390 :                 cnt -= i;
     672       99390 :                 if (mask_cand(s))
     673       99392 :                         ci->mskoff = s->tseqbase - (oid) CCAND(s)->firstbit + (ci->mask - (const uint32_t *) ccand_first(s)) * 32U;
     674             :                 else
     675           0 :                         ci->mskoff = s->tseqbase + (ci->mask - (const uint32_t *) s->theap->base) * 32U;
     676       99390 :                 ci->seq = ci->mskoff + ci->firstbit;
     677       99390 :                 ci->nextbit = ci->firstbit;
     678             :                 /* at this point we know that bit ci->firstbit is set
     679             :                  * in ci->mask[0] */
     680       99390 :                 ci->lastbit = (ci->firstbit + cnt - 1U) % 32U + 1U;
     681       99390 :                 if (ci->lastbit < 32 &&
     682       41778 :                     (ci->mask[ci->nvals - 1] & ((1U << ci->lastbit) - 1)) == 0) {
     683             :                         /* last partial word is all zero */
     684       10001 :                         cnt -= ci->lastbit;
     685       10001 :                         ci->lastbit = 32;
     686       10001 :                         ci->nvals--;
     687             :                 }
     688       99390 :                 if (ci->lastbit == 32) {
     689             :                         /* "remove" zero words at the end */
     690      143306 :                         while (cnt >= 32 && ci->mask[ci->nvals - 1] == 0) {
     691       75694 :                                 ci->nvals--;
     692       75694 :                                 cnt -= 32;
     693             :                         }
     694             :                 }
     695       99390 :                 ci->ncand = count_mask_bits(ci, 0, cnt);
     696       99393 :                 return ci->ncand;
     697             :         }
     698       84914 :         ci->ncand = cnt;
     699     1336147 :         ci->hseq += ci->offset;
     700     1336147 :         return cnt;
     701             : }
     702             : 
     703             : /* return the next candidate without advancing */
     704             : oid
     705     1678306 : canditer_peek(struct canditer *ci)
     706             : {
     707     1678306 :         oid o = oid_nil;
     708     1678306 :         if (ci->next == ci->ncand)
     709             :                 return oid_nil;
     710     1672454 :         switch (ci->tpe) {
     711     1458663 :         case cand_dense:
     712     1458663 :                 o = ci->seq + ci->next;
     713     1458663 :                 break;
     714      202405 :         case cand_materialized:
     715      202405 :                 assert(ci->next < ci->nvals);
     716      202405 :                 o = ci->oids[ci->next];
     717      202405 :                 break;
     718       11386 :         case cand_except:
     719       11386 :                 o = ci->seq + ci->add + ci->next;
     720       12207 :                 while (ci->add < ci->nvals && o == ci->oids[ci->add]) {
     721         821 :                         ci->add++;
     722         821 :                         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         348 : canditer_prev(struct canditer *ci)
     740             : {
     741         348 :         if (ci->next == 0)
     742           0 :                 return oid_nil;
     743         348 :         switch (ci->tpe) {
     744         348 :         case cand_dense:
     745         348 :                 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         593 : canditer_peekprev(struct canditer *ci)
     774             : {
     775         593 :         oid o = oid_nil;
     776             : 
     777         593 :         if (ci->next == 0)
     778             :                 return oid_nil;
     779         593 :         switch (ci->tpe) {
     780         593 :         case cand_dense:
     781         593 :                 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      979159 : canditer_last(const struct canditer *ci)
     851             : {
     852      979159 :         if (ci->ncand == 0)
     853           0 :                 return oid_nil;
     854      979159 :         switch (ci->tpe) {
     855      680312 :         case cand_dense:
     856      680312 :                 return ci->seq + ci->ncand - 1;
     857      179964 :         case cand_materialized:
     858      179964 :                 return ci->oids[ci->ncand - 1];
     859       80320 :         case cand_except:
     860       80320 :                 return ci->seq + ci->ncand + ci->nvals - 1;
     861       38564 :         case cand_mask:
     862      156704 :                 for (uint8_t i = ci->lastbit; i > 0; ) {
     863      156703 :                         if (ci->mask[ci->nvals - 1] & (1U << --i))
     864       38563 :                                 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    68583610 : canditer_idx(const struct canditer *ci, BUN p)
     874             : {
     875    68583610 :         if (p >= ci->ncand)
     876           0 :                 return oid_nil;
     877    68583610 :         switch (ci->tpe) {
     878     4903237 :         case cand_dense:
     879     4903237 :                 return ci->seq + p;
     880    63440565 :         case cand_materialized:
     881    63440565 :                 return ci->oids[p];
     882      239725 :         case cand_except: {
     883      239725 :                 oid o = ci->seq + p;
     884      239725 :                 if (o < ci->oids[0])
     885             :                         return o;
     886      143273 :                 if (o + ci->nvals > ci->oids[ci->nvals - 1])
     887             :                         return o + ci->nvals;
     888       59920 :                 BUN lo = 0, hi = ci->nvals - 1;
     889      398241 :                 while (hi - lo > 1) {
     890      278401 :                         BUN mid = (hi + lo) / 2;
     891      278401 :                         if (ci->oids[mid] - mid > o)
     892             :                                 hi = mid;
     893             :                         else
     894             :                                 lo = mid;
     895             :                 }
     896       59920 :                 return o + hi;
     897             :         }
     898          83 :         case cand_mask: {
     899             :                 BUN x;
     900          83 :                 if ((x = candmask_pop(ci->mask[0] >> ci->firstbit)) > p) {
     901          26 :                         for (uint8_t i = ci->firstbit; ; i++) {
     902         105 :                                 if (ci->mask[0] & (1U << i)) {
     903         105 :                                         if (p == 0)
     904          79 :                                                 return ci->mskoff + i;
     905          26 :                                         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      494252 : canditer_setidx(struct canditer *ci, BUN p)
     932             : {
     933      494252 :         if (p != ci->next) {
     934      463127 :                 if (p >= ci->ncand) {
     935       47435 :                         ci->next = ci->ncand;
     936       47435 :                         switch (ci->tpe) {
     937          11 :                         case cand_except:
     938          11 :                                 ci->add = ci->nvals;
     939          11 :                                 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      415692 :                         ci->next = p;
     953      415692 :                         switch (ci->tpe) {
     954        4216 :                         case cand_except:
     955        4216 :                                 ci->add = canditer_idx(ci, p) - ci->seq - p;
     956        4216 :                                 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       31125 :                 }
     967             :         }
     968      494252 : }
     969             : 
     970             : /* reset */
     971             : void
     972     8599647 : canditer_reset(struct canditer *ci)
     973             : {
     974     8599647 :         if (ci->tpe == cand_mask) {
     975           0 :                 ci->nextbit = ci->firstbit;
     976           0 :                 ci->nextmsk = 0;
     977             :         } else {
     978     8599647 :                 ci->add = 0;
     979             :         }
     980     8599647 :         ci->next = 0;
     981     8599647 : }
     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     4212471 : canditer_search(const struct canditer *ci, oid o, bool next)
     988             : {
     989             :         BUN p;
     990             : 
     991     4212471 :         switch (ci->tpe) {
     992      423690 :         case cand_dense:
     993      423690 :                 if (o < ci->seq)
     994         601 :                         return next ? 0 : BUN_NONE;
     995      423089 :                 if (o >= ci->seq + ci->ncand)
     996      147077 :                         return next ? ci->ncand : BUN_NONE;
     997      276012 :                 return o - ci->seq;
     998     3559787 :         case cand_materialized:
     999     3559787 :                 if (ci->nvals == 0)
    1000             :                         return 0;
    1001     3559741 :                 p = binsearchcand(ci->oids, ci->nvals - 1, o);
    1002     3658110 :                 if (next || (p != ci->nvals && ci->oids[p] == o))
    1003     1597840 :                         return p;
    1004             :                 break;
    1005      228994 :         case cand_except:
    1006      228994 :                 if (o < ci->seq)
    1007           0 :                         return next ? 0 : BUN_NONE;
    1008      228994 :                 if (o >= ci->seq + ci->ncand + ci->nvals)
    1009          13 :                         return next ? ci->ncand : BUN_NONE;
    1010      228981 :                 p = binsearchcand(ci->oids, ci->nvals - 1, o);
    1011      228981 :                 if (next || p == ci->nvals || ci->oids[p] != o)
    1012      188382 :                         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         685 : canditer_sliceval_mask(const struct canditer *ci, oid lo1, oid hi1, BUN cnt1,
    1034             :                        oid lo2, oid hi2, BUN cnt2)
    1035             : {
    1036         685 :         assert(cnt2 == 0 || !is_oid_nil(lo2));
    1037         685 :         assert(cnt2 == 0 || lo2 >= hi1);
    1038         685 :         if (is_oid_nil(lo1) || lo1 < ci->mskoff + ci->firstbit)
    1039         260 :                 lo1 = ci->mskoff + ci->firstbit;
    1040         685 :         if (is_oid_nil(hi1) || hi1 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
    1041         287 :                 hi1 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
    1042             : 
    1043         685 :         BAT *bn = COLnew(0, TYPE_oid, cnt1 + cnt2, TRANSIENT);
    1044         685 :         if (bn == NULL)
    1045             :                 return NULL;
    1046         685 :         bn->tkey = true;
    1047             : 
    1048         685 :         if (hi1 > ci->mskoff) {
    1049         293 :                 if (lo1 < ci->mskoff)
    1050             :                         lo1 = 0;
    1051             :                 else
    1052         293 :                         lo1 -= ci->mskoff;
    1053         293 :                 hi1 -= ci->mskoff;
    1054       68931 :                 for (oid o = lo1; o < hi1 && cnt1 > 0; o++) {
    1055       68638 :                         if (ci->mask[o / 32] & (1U << (o % 32))) {
    1056       39956 :                                 if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
    1057           0 :                                         BBPreclaim(bn);
    1058           0 :                                         return NULL;
    1059             :                                 }
    1060       39956 :                                 cnt1--;
    1061             :                         }
    1062             :                 }
    1063             :         }
    1064         685 :         if (cnt2 > 0) {
    1065           4 :                 if (lo2 < ci->mskoff + ci->firstbit)
    1066             :                         lo2 = ci->mskoff + ci->firstbit;
    1067           4 :                 if (is_oid_nil(hi2) || hi2 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
    1068           4 :                         hi2 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
    1069             : 
    1070           4 :                 lo2 -= ci->mskoff;
    1071           4 :                 hi2 -= ci->mskoff;
    1072           4 :                 for (oid o = lo2; o < hi2 && cnt2 > 0; o++) {
    1073           0 :                         if (ci->mask[o / 32] & (1U << (o % 32))) {
    1074           0 :                                 if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
    1075           0 :                                         BBPreclaim(bn);
    1076           0 :                                         return NULL;
    1077             :                                 }
    1078           0 :                                 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      188805 : canditer_slice(const struct canditer *ci, BUN lo, BUN hi)
    1091             : {
    1092             :         BAT *bn;
    1093             :         oid o;
    1094             :         BUN add;
    1095             : 
    1096      188805 :         assert(ci != NULL);
    1097             : 
    1098      188805 :         if (lo >= ci->ncand || lo >= hi)
    1099       87206 :                 return BATdense(0, 0, 0);
    1100             :         if (hi > ci->ncand)
    1101             :                 hi = ci->ncand;
    1102      101599 :         switch (ci->tpe) {
    1103        6084 :         case cand_materialized:
    1104        6084 :                 if (ci->s) {
    1105        6084 :                         bn = BATslice(ci->s, lo + ci->offset, hi + ci->offset);
    1106        6084 :                         BAThseqbase(bn, 0);
    1107        6084 :                         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       95403 :         default: /* really: case cand_dense: */
    1116       95403 :                 return BATdense(0, ci->seq + lo, hi - lo);
    1117          29 :         case cand_except:
    1118          29 :                 o = canditer_idx(ci, lo);
    1119          29 :                 add = o - ci->seq - lo;
    1120          29 :                 assert(add <= ci->nvals);
    1121          29 :                 if (add == ci->nvals || o + hi - lo < ci->oids[add]) {
    1122             :                         /* after last exception or before next
    1123             :                          * exception: return dense sequence */
    1124          27 :                         return BATdense(0, o, hi - lo);
    1125             :                 }
    1126           2 :                 bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
    1127           2 :                 if (bn == NULL)
    1128             :                         return NULL;
    1129           2 :                 BATsetcount(bn, hi - lo);
    1130           8 :                 for (oid *dst = Tloc(bn, 0); lo < hi; lo++) {
    1131           6 :                         while (add < ci->nvals && o == ci->oids[add]) {
    1132           0 :                                 o++;
    1133           0 :                                 add++;
    1134             :                         }
    1135           6 :                         *dst++ = o++;
    1136             :                 }
    1137             :                 break;
    1138          83 :         case cand_mask:
    1139          83 :                 return canditer_sliceval_mask(ci, canditer_idx(ci, lo),
    1140             :                                               oid_nil, hi - lo,
    1141             :                                               oid_nil, oid_nil, 0);
    1142             :         }
    1143           2 :         bn->tsorted = true;
    1144           2 :         bn->trevsorted = BATcount(bn) <= 1;
    1145           2 :         bn->tkey = true;
    1146           2 :         bn->tseqbase = oid_nil;
    1147           2 :         bn->tnil = false;
    1148           2 :         bn->tnonil = true;
    1149           2 :         bn->tminpos = 0;
    1150           2 :         bn->tmaxpos = BATcount(bn) - 1;
    1151           2 :         return virtualize(bn);
    1152             : }
    1153             : 
    1154             : /* like the above, except the bounds are given by values instead of
    1155             :  * indexes */
    1156             : BAT *
    1157       95483 : canditer_sliceval(const struct canditer *ci, oid lo, oid hi)
    1158             : {
    1159       95483 :         if (ci->tpe != cand_mask) {
    1160      284541 :                 return canditer_slice(
    1161             :                         ci,
    1162       94871 :                         is_oid_nil(lo) ? 0 : canditer_search(ci, lo, true),
    1163       94885 :                         is_oid_nil(hi) ? ci->ncand : canditer_search(ci, hi, true));
    1164             :         }
    1165             : 
    1166         598 :         return canditer_sliceval_mask(ci, lo, hi, ci->ncand,
    1167             :                                       oid_nil, oid_nil, 0);
    1168             : }
    1169             : 
    1170             : /* return the combination of two slices */
    1171             : BAT *
    1172       17193 : canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2)
    1173             : {
    1174             :         BAT *bn;
    1175             :         oid o;
    1176             :         BUN add;
    1177             : 
    1178       17193 :         assert(lo1 <= hi1);
    1179       17193 :         assert(lo2 <= hi2);
    1180       17193 :         assert(hi1 <= lo2 || (lo2 == 0 && hi2 == 0));
    1181             : 
    1182       17193 :         if (hi1 == lo2)         /* consecutive slices: combine into one */
    1183        1308 :                 return canditer_slice(ci, lo1, hi2);
    1184       15885 :         if (lo2 == hi2 || hi1 >= ci->ncand || lo2 >= ci->ncand) {
    1185             :                 /* empty second slice */
    1186        9323 :                 return canditer_slice(ci, lo1, hi1);
    1187             :         }
    1188        6562 :         if (lo1 == hi1)         /* empty first slice */
    1189        4188 :                 return canditer_slice(ci, lo2, hi2);
    1190        2374 :         if (lo1 >= ci->ncand)     /* out of range */
    1191           0 :                 return BATdense(0, 0, 0);
    1192             : 
    1193             :         if (hi2 >= ci->ncand)
    1194             :                 hi2 = ci->ncand;
    1195             : 
    1196        2374 :         bn = COLnew(0, TYPE_oid, hi1 - lo1 + hi2 - lo2, TRANSIENT);
    1197        2374 :         if (bn == NULL)
    1198             :                 return NULL;
    1199        2374 :         BATsetcount(bn, hi1 - lo1 + hi2 - lo2);
    1200        2374 :         bn->tsorted = true;
    1201        2374 :         bn->trevsorted = BATcount(bn) <= 1;
    1202        2374 :         bn->tkey = true;
    1203        2374 :         bn->tseqbase = oid_nil;
    1204        2374 :         bn->tnil = false;
    1205        2374 :         bn->tnonil = true;
    1206             : 
    1207        2374 :         oid *dst = Tloc(bn, 0);
    1208             : 
    1209        2374 :         switch (ci->tpe) {
    1210           1 :         case cand_materialized:
    1211           1 :                 memcpy(dst, ci->oids + lo1, (hi1 - lo1) * sizeof(oid));
    1212           1 :                 memcpy(dst + hi1 - lo1, ci->oids + lo2, (hi2 - lo2) * sizeof(oid));
    1213           1 :                 break;
    1214             :         case cand_dense:
    1215      900578 :                 while (lo1 < hi1)
    1216      898205 :                         *dst++ = ci->seq + lo1++;
    1217      241747 :                 while (lo2 < hi2)
    1218      239374 :                         *dst++ = ci->seq + lo2++;
    1219             :                 break;
    1220           0 :         case cand_except:
    1221           0 :                 o = canditer_idx(ci, lo1);
    1222           0 :                 add = o - ci->seq - lo1;
    1223           0 :                 assert(add <= ci->nvals);
    1224           0 :                 if (add == ci->nvals) {
    1225             :                         /* after last exception: return dense sequence */
    1226           0 :                         while (lo1 < hi1)
    1227           0 :                                 *dst++ = ci->seq + add + lo1++;
    1228             :                 } else {
    1229           0 :                         while (lo1 < hi1) {
    1230           0 :                                 while (add < ci->nvals && o == ci->oids[add]) {
    1231           0 :                                         o++;
    1232           0 :                                         add++;
    1233             :                                 }
    1234           0 :                                 *dst++ = o++;
    1235           0 :                                 lo1++;
    1236             :                         }
    1237             :                 }
    1238           0 :                 o = canditer_idx(ci, lo2);
    1239           0 :                 add = o - ci->seq - lo2;
    1240           0 :                 assert(add <= ci->nvals);
    1241           0 :                 if (add == ci->nvals) {
    1242             :                         /* after last exception: return dense sequence */
    1243           0 :                         while (lo2 < hi2)
    1244           0 :                                 *dst++ = ci->seq + add + lo2++;
    1245             :                 } else {
    1246           0 :                         while (lo2 < hi2) {
    1247           0 :                                 while (add < ci->nvals && o == ci->oids[add]) {
    1248           0 :                                         o++;
    1249           0 :                                         add++;
    1250             :                                 }
    1251           0 :                                 *dst++ = o++;
    1252           0 :                                 lo2++;
    1253             :                         }
    1254             :                 }
    1255             :                 break;
    1256           0 :         case cand_mask:
    1257           0 :                 return canditer_sliceval_mask(ci, canditer_idx(ci, lo1),
    1258             :                                               oid_nil, hi1 - lo1,
    1259             :                                               canditer_idx(ci, lo2),
    1260             :                                               oid_nil, hi2 - lo2);
    1261             :         }
    1262        2374 :         return virtualize(bn);
    1263             : }
    1264             : 
    1265             : BAT *
    1266       17197 : canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2)
    1267             : {
    1268       17197 :         if (ci->tpe != cand_mask) {
    1269       68772 :                 return canditer_slice2(
    1270             :                         ci,
    1271        9749 :                         is_oid_nil(lo1) ? 0 : canditer_search(ci, lo1, true),
    1272       17193 :                         is_oid_nil(hi1) ? ci->ncand : canditer_search(ci, hi1, true),
    1273       17193 :                         is_oid_nil(lo2) ? 0 : canditer_search(ci, lo2, true),
    1274        7444 :                         is_oid_nil(hi2) ? ci->ncand : canditer_search(ci, hi2, true));
    1275             :         }
    1276             : 
    1277           4 :         return canditer_sliceval_mask(ci, lo1, hi1, ci->ncand,
    1278             :                                       lo2, hi2, ci->ncand);
    1279             : }
    1280             : 
    1281             : BAT *
    1282          44 : BATnegcands(BUN nr, BAT *odels)
    1283             : {
    1284             :         const char *nme;
    1285             :         Heap *dels;
    1286             :         BUN lo, hi;
    1287             :         ccand_t *c;
    1288             :         BAT *bn;
    1289             : 
    1290          44 :         bn = BATdense(0, 0, nr);
    1291          44 :         if (bn == NULL)
    1292             :                 return NULL;
    1293          44 :         if (BATcount(odels) == 0)
    1294             :                 return bn;
    1295             : 
    1296          44 :         lo = SORTfndfirst(odels, &bn->tseqbase);
    1297          44 :         hi = SORTfndfirst(odels, &(oid) {bn->tseqbase + BATcount(bn)});
    1298          44 :         if (lo == hi)
    1299             :                 return bn;
    1300             : 
    1301          44 :         nme = BBP_physical(bn->batCacheid);
    1302          44 :         if ((dels = (Heap*)GDKzalloc(sizeof(Heap))) == NULL ||
    1303          44 :             (dels->farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap)) < 0){
    1304           0 :                 GDKfree(dels);
    1305           0 :                 BBPreclaim(bn);
    1306           0 :                 return NULL;
    1307             :         }
    1308          44 :         strconcat_len(dels->filename, sizeof(dels->filename),
    1309             :                       nme, ".theap", NULL);
    1310             : 
    1311          44 :         if (HEAPalloc(dels, hi - lo + (sizeof(ccand_t)/sizeof(oid)), sizeof(oid), 0) != GDK_SUCCEED) {
    1312           0 :                 GDKfree(dels);
    1313           0 :                 BBPreclaim(bn);
    1314           0 :                 return NULL;
    1315             :         }
    1316          44 :         ATOMIC_INIT(&dels->refs, 1);
    1317          44 :         c = (ccand_t *) dels->base;
    1318          44 :         *c = (ccand_t) {
    1319             :                 .type = CAND_NEGOID,
    1320             :         };
    1321          44 :         dels->parentid = bn->batCacheid;
    1322          44 :         dels->free = sizeof(ccand_t) + sizeof(oid) * (hi - lo);
    1323          44 :         dels->dirty = true;
    1324          44 :         BATiter bi = bat_iterator(odels);
    1325          44 :         if (odels->ttype == TYPE_void) {
    1326           0 :                 oid *r = (oid *) (dels->base + sizeof(ccand_t));
    1327           0 :                 for (BUN x = lo; x < hi; x++)
    1328           0 :                         r[x - lo] = x + odels->tseqbase;
    1329             :         } else {
    1330          44 :                 oid *r = (oid *) (dels->base + sizeof(ccand_t));
    1331          44 :                 memcpy(r, (const oid *) bi.base + lo, sizeof(oid) * (hi - lo));
    1332             :         }
    1333          44 :         bat_iterator_end(&bi);
    1334          44 :         bn->batDirtydesc = true;
    1335          44 :         assert(bn->tvheap == NULL);
    1336          44 :         bn->tvheap = dels;
    1337          44 :         BATsetcount(bn, bn->batCount - (hi - lo));
    1338          44 :         TRC_DEBUG(ALGO, "BATnegcands(cands=" ALGOBATFMT ","
    1339             :                   "dels=" ALGOBATFMT ")\n",
    1340             :                   ALGOBATPAR(bn),
    1341             :                   ALGOBATPAR(odels));
    1342          44 :         TRC_DEBUG(ALGO, "nr=" BUNFMT ", odels=" ALGOBATFMT
    1343             :                   " -> " ALGOBATFMT "\n",
    1344             :                   nr, ALGOBATPAR(odels),
    1345             :                   ALGOBATPAR(bn));
    1346             :         return bn;
    1347             : }
    1348             : 
    1349             : BAT *
    1350      155243 : BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected)
    1351             : {
    1352             :         const char *nme;
    1353             :         Heap *msks;
    1354             :         ccand_t *c;
    1355             :         BUN nmask;
    1356             :         BAT *bn;
    1357             : 
    1358      155243 :         assert(masked->ttype == TYPE_msk);
    1359             : 
    1360      155243 :         bn = COLnew(hseq, TYPE_void, 0, TRANSIENT);
    1361      155243 :         if (bn == NULL)
    1362             :                 return NULL;
    1363      155243 :         BATtseqbase(bn, hseq);
    1364             : 
    1365      155243 :         if (BATcount(masked) == 0)
    1366             :                 return bn;
    1367             : 
    1368      155243 :         nme = BBP_physical(bn->batCacheid);
    1369      155243 :         if ((msks = (Heap*)GDKzalloc(sizeof(Heap))) == NULL ||
    1370      155243 :             (msks->farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap)) < 0){
    1371           0 :                 GDKfree(msks);
    1372           0 :                 BBPreclaim(bn);
    1373           0 :                 return NULL;
    1374             :         }
    1375      155243 :         strconcat_len(msks->filename, sizeof(msks->filename),
    1376             :                       nme, ".theap", NULL);
    1377             : 
    1378      155243 :         nmask = (nr + 31) / 32;
    1379      155243 :         if (HEAPalloc(msks, nmask + (sizeof(ccand_t)/sizeof(uint32_t)), sizeof(uint32_t), 0) != GDK_SUCCEED) {
    1380           0 :                 GDKfree(msks);
    1381           0 :                 BBPreclaim(bn);
    1382           0 :                 return NULL;
    1383             :         }
    1384      155243 :         c = (ccand_t *) msks->base;
    1385      155243 :         *c = (ccand_t) {
    1386             :                 .type = CAND_MSK,
    1387             : //              .mask = true,
    1388             :         };
    1389      155243 :         msks->parentid = bn->batCacheid;
    1390      155243 :         msks->free = sizeof(ccand_t) + nmask * sizeof(uint32_t);
    1391      155243 :         msks->dirty = true;
    1392      155243 :         uint32_t *r = (uint32_t*)(msks->base + sizeof(ccand_t));
    1393      155243 :         BATiter bi = bat_iterator(masked);
    1394      155243 :         if (selected) {
    1395      155203 :                 if (nr <= bi.count)
    1396      155203 :                         memcpy(r, bi.base, nmask * sizeof(uint32_t));
    1397             :                 else
    1398           0 :                         memcpy(r, bi.base, (bi.count + 31) / 32 * sizeof(uint32_t));
    1399             :         } else {
    1400          40 :                 const uint32_t *s = (const uint32_t *) bi.base;
    1401          40 :                 BUN nmask_ = (bi.count + 31) / 32;
    1402        3318 :                 for (BUN i = 0; i < nmask_; i++)
    1403        3278 :                         r[i] = ~s[i];
    1404             :         }
    1405      155243 :         if (nr > bi.count) {
    1406           0 :                 BUN rest = bi.count & 31;
    1407           0 :                 BUN nmask_ = (bi.count + 31) / 32;
    1408           0 :                 if (rest > 0)
    1409           0 :                         r[nmask_ -1] |= ((1U << (32 - rest)) - 1) << rest;
    1410           0 :                 for (BUN j = nmask_; j < nmask; j++)
    1411           0 :                         r[j] = ~0;
    1412             :         }
    1413      155243 :         bat_iterator_end(&bi);
    1414             :         /* make sure last word doesn't have any spurious bits set */
    1415      155243 :         BUN cnt = nr % 32;
    1416      155243 :         if (cnt > 0)
    1417      154182 :                 r[nmask - 1] &= (1U << cnt) - 1;
    1418             :         cnt = 0;
    1419    12270134 :         for (BUN i = 0; i < nmask; i++) {
    1420    12114891 :                 if (cnt == 0 && r[i] != 0)
    1421      152786 :                         c->firstbit = candmask_lobit(r[i]) + i * 32;
    1422    12114891 :                 cnt += candmask_pop(r[i]);
    1423             :         }
    1424      155243 :         if (cnt > 0) {
    1425      152786 :                 ATOMIC_INIT(&msks->refs, 1);
    1426      152786 :                 assert(bn->tvheap == NULL);
    1427      152786 :                 bn->tvheap = msks;
    1428      152786 :                 bn->tseqbase += (oid) c->firstbit;
    1429             :         } else {
    1430             :                 /* no point having a mask if it's empty */
    1431        2457 :                 HEAPfree(msks, true);
    1432        2457 :                 GDKfree(msks);
    1433             :         }
    1434      155243 :         bn->batDirtydesc = true;
    1435      155243 :         BATsetcount(bn, cnt);
    1436      155243 :         TRC_DEBUG(ALGO, "hseq=" OIDFMT ", masked=" ALGOBATFMT ", selected=%s"
    1437             :                   " -> " ALGOBATFMT "\n",
    1438             :                   hseq, ALGOBATPAR(masked),
    1439             :                   selected ? "true" : "false",
    1440             :                   ALGOBATPAR(bn));
    1441      155243 :         assert(bn->tseqbase != oid_nil);
    1442             :         return bn;
    1443             : }
    1444             : 
    1445             : /* convert a masked candidate list to a positive or negative candidate list */
    1446             : BAT *
    1447      103719 : BATunmask(BAT *b)
    1448             : {
    1449             : //      assert(!mask_cand(b) || CCAND(b)->mask); /* todo handle negmask case */
    1450             :         BUN cnt;
    1451             :         uint32_t rem;
    1452             :         uint32_t val;
    1453             :         const uint32_t *src;
    1454             :         oid *dst;
    1455             :         BUN n = 0;
    1456      103719 :         oid tseq = b->hseqbase;
    1457             :         bool negcand = false;
    1458             : 
    1459      103719 :         BATiter bi = bat_iterator(b);
    1460      103719 :         if (mask_cand(b)) {
    1461      100544 :                 cnt = ccand_free(b) / sizeof(uint32_t);
    1462             :                 rem = 0;
    1463      100544 :                 src = (const uint32_t *) ccand_first(b);
    1464      100544 :                 tseq = b->tseqbase;
    1465      100544 :                 tseq -= (oid) CCAND(b)->firstbit;
    1466             :                 /* create negative candidate list if more than half the
    1467             :                  * bits are set */
    1468      100544 :                 negcand = BATcount(b) > cnt * 16;
    1469             :         } else {
    1470        3175 :                 cnt = bi.count / 32;
    1471        3175 :                 rem = bi.count % 32;
    1472        3175 :                 src = (const uint32_t *) bi.base;
    1473             :         }
    1474             :         BAT *bn;
    1475             : 
    1476      103719 :         if (negcand) {
    1477       84694 :                 bn = COLnew(b->hseqbase, TYPE_void, 0, TRANSIENT);
    1478       84694 :                 if (bn == NULL) {
    1479           0 :                         bat_iterator_end(&bi);
    1480           0 :                         return NULL;
    1481             :                 }
    1482             :                 Heap *dels;
    1483      169388 :                 if ((dels = GDKzalloc(sizeof(Heap))) == NULL ||
    1484       84693 :                     strconcat_len(dels->filename, sizeof(dels->filename),
    1485       84693 :                                   BBP_physical(bn->batCacheid), ".theap",
    1486       84694 :                                   NULL) >= sizeof(dels->filename) ||
    1487       84694 :                     (dels->farmid = BBPselectfarm(TRANSIENT, TYPE_void,
    1488       84694 :                                                   varheap)) == -1 ||
    1489       84694 :                     HEAPalloc(dels,
    1490       84694 :                               cnt * 32 - bi.count
    1491             :                               + sizeof(ccand_t) / sizeof(oid),
    1492             :                               sizeof(oid), 0) != GDK_SUCCEED) {
    1493           0 :                         GDKfree(dels);
    1494           0 :                         BBPreclaim(bn);
    1495           0 :                         bat_iterator_end(&bi);
    1496           0 :                         return NULL;
    1497             :                 }
    1498       84694 :                 dels->parentid = bn->batCacheid;
    1499       84694 :                 * (ccand_t *) dels->base = (ccand_t) {
    1500             :                         .type = CAND_NEGOID,
    1501             :                 };
    1502             :                 dst = (oid *) (dels->base + sizeof(ccand_t));
    1503     6886269 :                 for (BUN p = 0, v = 0; p < cnt; p++, v += 32) {
    1504     6801575 :                         if ((val = src[p]) == ~UINT32_C(0))
    1505     4999897 :                                 continue;
    1506    57862377 :                         for (uint32_t i = 0; i < 32; i++) {
    1507    56148406 :                                 if ((val & (1U << i)) == 0) {
    1508    47624636 :                                         if (v + i >= b->batCount + n)
    1509             :                                                 break;
    1510    47536929 :                                         dst[n++] = tseq + v + i;
    1511             :                                 }
    1512             :                         }
    1513             :                 }
    1514       84694 :                 if (n == 0) {
    1515             :                         /* didn't need it after all */
    1516           0 :                         HEAPfree(dels, true);
    1517           0 :                         GDKfree(dels);
    1518             :                 } else {
    1519       84694 :                         dels->free = sizeof(ccand_t) + n * sizeof(oid);
    1520       84694 :                         dels->dirty = true;
    1521       84694 :                         ATOMIC_INIT(&dels->refs, 1);
    1522       84694 :                         assert(bn->tvheap == NULL);
    1523       84694 :                         bn->tvheap = dels;
    1524             :                 }
    1525       84694 :                 BATsetcount(bn, n=bi.count);
    1526       84693 :                 bn->tseqbase = tseq;
    1527             :         } else {
    1528       19025 :                 bn = COLnew(b->hseqbase, TYPE_oid, mask_cand(b) ? bi.count : 1024, TRANSIENT);
    1529       19025 :                 if (bn == NULL) {
    1530           0 :                         bat_iterator_end(&bi);
    1531           0 :                         return NULL;
    1532             :                 }
    1533       19025 :                 dst = (oid *) Tloc(bn, 0);
    1534     2657966 :                 for (BUN p = 0; p < cnt; p++) {
    1535     2638941 :                         if ((val = src[p]) == 0)
    1536     1863338 :                                 continue;
    1537    25589775 :                         for (uint32_t i = 0; i < 32; i++) {
    1538    24814172 :                                 if (val & (1U << i)) {
    1539    23029898 :                                         if (n == BATcapacity(bn)) {
    1540          75 :                                                 BATsetcount(bn, n);
    1541          75 :                                                 if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
    1542           0 :                                                         BBPreclaim(bn);
    1543           0 :                                                         bat_iterator_end(&bi);
    1544           0 :                                                         return NULL;
    1545             :                                                 }
    1546          75 :                                                 dst = (oid *) Tloc(bn, 0);
    1547             :                                         }
    1548    23029898 :                                         dst[n++] = tseq + p * 32 + i;
    1549             :                                 }
    1550             :                         }
    1551             :                 }
    1552             :                 /* the last partial mask word */
    1553       19025 :                 if (rem > 0 && (val = src[cnt]) != 0) {
    1554       14063 :                         for (uint32_t i = 0; i < rem; i++) {
    1555       12637 :                                 if (val & (1U << i)) {
    1556         714 :                                         if (n == BATcapacity(bn)) {
    1557           0 :                                                 BATsetcount(bn, n);
    1558           0 :                                                 if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
    1559           0 :                                                         BBPreclaim(bn);
    1560           0 :                                                         bat_iterator_end(&bi);
    1561           0 :                                                         return NULL;
    1562             :                                                 }
    1563           0 :                                                 dst = (oid *) Tloc(bn, 0);
    1564             :                                         }
    1565         714 :                                         dst[n++] = tseq + cnt * 32 + i;
    1566             :                                 }
    1567             :                         }
    1568             :                 }
    1569       19025 :                 BATsetcount(bn, n);
    1570             :         }
    1571      103718 :         bat_iterator_end(&bi);
    1572      103719 :         bn->tkey = true;
    1573      103719 :         bn->tsorted = true;
    1574      103719 :         bn->trevsorted = n <= 1;
    1575      103719 :         bn->tnil = false;
    1576      103719 :         bn->tnonil = true;
    1577      103719 :         bn = virtualize(bn);
    1578      103719 :         TRC_DEBUG(ALGO, ALGOBATFMT " -> " ALGOBATFMT "\n", ALGOBATPAR(b), ALGOBATPAR(bn));
    1579             :         return bn;
    1580             : }

Generated by: LCOV version 1.14