Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "gdk.h"
15 : #include "gdk_private.h"
16 : #include "gdk_cand.h"
17 :
18 : bool
19 8284 : BATiscand(BAT *b)
20 : {
21 8284 : if (ATOMtype(b->ttype) != TYPE_oid)
22 : return false;
23 8284 : if (complex_cand(b))
24 : return true;
25 8004 : if (b->ttype == TYPE_void && is_oid_nil(b->tseqbase))
26 : return false;
27 16008 : return b->tsorted && BATtkey(b);
28 : }
29 :
30 : /* create a new, dense candidate list with values from `first' up to,
31 : * but not including, `last' */
32 : static inline BAT *
33 1614 : newdensecand(oid first, oid last)
34 : {
35 1614 : if (last <= first)
36 0 : first = last = 0; /* empty range */
37 1614 : return BATdense(0, first, last - first);
38 : }
39 :
40 : /* merge two candidate lists and produce a new one
41 : *
42 : * candidate lists are VOID-headed BATs with an OID tail which is
43 : * sorted and unique.
44 : */
45 : BAT *
46 78656 : BATmergecand(BAT *a, BAT *b)
47 : {
48 78656 : BAT *bn;
49 78656 : oid *restrict p, i;
50 78656 : struct canditer cia, cib;
51 :
52 78656 : BATcheck(a, NULL);
53 78656 : BATcheck(b, NULL);
54 :
55 78656 : canditer_init(&cia, NULL, a);
56 78639 : canditer_init(&cib, NULL, b);
57 :
58 : /* we can return a if b is empty (and v.v.) */
59 78654 : if (cia.ncand == 0) {
60 13031 : bn = canditer_slice(&cib, 0, cib.ncand);
61 13031 : goto doreturn;
62 : }
63 65623 : if (cib.ncand == 0) {
64 10224 : bn = canditer_slice(&cia, 0, cia.ncand);
65 10224 : goto doreturn;
66 : }
67 : /* we can return a if a fully covers b (and v.v) */
68 55399 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
69 : /* both are dense */
70 9802 : if (cia.seq <= cib.seq && cib.seq <= cia.seq + cia.ncand) {
71 : /* partial overlap starting with a, or b is
72 : * smack bang after a */
73 1249 : bn = newdensecand(cia.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
74 1249 : goto doreturn;
75 : }
76 8553 : if (cib.seq <= cia.seq && cia.seq <= cib.seq + cib.ncand) {
77 : /* partial overlap starting with b, or a is
78 : * smack bang after b */
79 359 : bn = newdensecand(cib.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
80 359 : goto doreturn;
81 : }
82 : }
83 53791 : if (cia.tpe == cand_dense
84 11305 : && cia.seq <= cib.seq
85 5051 : && canditer_last(&cia) >= canditer_last(&cib)) {
86 344 : bn = canditer_slice(&cia, 0, cia.ncand);
87 344 : goto doreturn;
88 : }
89 53447 : if (cib.tpe == cand_dense
90 37312 : && cib.seq <= cia.seq
91 9936 : && canditer_last(&cib) >= canditer_last(&cia)) {
92 197 : bn = canditer_slice(&cib, 0, cib.ncand);
93 197 : goto doreturn;
94 : }
95 :
96 53250 : bn = COLnew(0, TYPE_oid, cia.ncand + cib.ncand, TRANSIENT);
97 53248 : if (bn == NULL)
98 0 : goto doreturn;
99 53248 : p = (oid *) Tloc(bn, 0);
100 53248 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
101 : /* both lists are dense */
102 8194 : if (cia.seq > cib.seq) {
103 4060 : struct canditer ci;
104 4060 : ci = cia;
105 4060 : cia = cib;
106 4060 : cib = ci;
107 : }
108 : /* cia completely before cib */
109 8194 : assert(cia.seq + cia.ncand < cib.seq);
110 30989 : for (i = cia.seq; i < cia.seq + cia.ncand; i++)
111 22795 : *p++ = i;
112 : /* there is a gap */
113 27466 : for (i = cib.seq; i < cib.seq + cib.ncand; i++)
114 19272 : *p++ = i;
115 45054 : } else if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
116 31685 : if (cib.tpe == cand_dense) {
117 28923 : struct canditer ci;
118 28923 : ci = cia;
119 28923 : cia = cib;
120 28923 : cib = ci;
121 : }
122 : /* only cia is dense */
123 :
124 : /* copy part of cib that's before the start of cia */
125 126206 : while (canditer_peek(&cib) < cia.seq) {
126 94523 : *p++ = canditer_next(&cib);
127 : }
128 : /* copy all of cia */
129 73329 : for (i = cia.seq; i < cia.seq + cia.ncand; i++)
130 41646 : *p++ = i;
131 : /* skip over part of cib that overlaps with cia */
132 31683 : canditer_setidx(&cib, canditer_search(&cib, cia.seq + cia.ncand, true));
133 : /* copy rest of cib */
134 126433 : while (cib.next < cib.ncand) {
135 94748 : *p++ = canditer_next(&cib);
136 : }
137 : } else {
138 : /* a and b are both not dense */
139 13369 : oid ao = canditer_next(&cia);
140 13369 : oid bo = canditer_next(&cib);
141 24328555 : while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
142 24315184 : if (ao < bo) {
143 14165700 : *p++ = ao;
144 14165700 : ao = canditer_next(&cia);
145 10149484 : } else if (bo < ao) {
146 9086137 : *p++ = bo;
147 9086137 : bo = canditer_next(&cib);
148 : } else {
149 1063347 : *p++ = ao;
150 1063347 : ao = canditer_next(&cia);
151 1063343 : bo = canditer_next(&cib);
152 : }
153 : }
154 576864 : while (!is_oid_nil(ao)) {
155 563495 : *p++ = ao;
156 563495 : ao = canditer_next(&cia);
157 : }
158 416514 : while (!is_oid_nil(bo)) {
159 403145 : *p++ = bo;
160 403145 : bo = canditer_next(&cib);
161 : }
162 : }
163 :
164 : /* properties */
165 53250 : BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
166 53242 : bn->trevsorted = BATcount(bn) <= 1;
167 53242 : bn->tsorted = true;
168 53242 : bn->tkey = true;
169 53242 : bn->tnil = false;
170 53242 : bn->tnonil = true;
171 53242 : bn = virtualize(bn);
172 78655 : doreturn:
173 78655 : TRC_DEBUG(ALGO, ALGOBATFMT "," ALGOBATFMT " -> " ALGOOPTBATFMT "\n",
174 : ALGOBATPAR(a), ALGOBATPAR(b), ALGOOPTBATPAR(bn));
175 : return bn;
176 : }
177 :
178 : /* intersect two candidate lists and produce a new one
179 : *
180 : * candidate lists are VOID-headed BATs with an OID tail which is
181 : * sorted and unique.
182 : */
183 : BAT *
184 23 : BATintersectcand(BAT *a, BAT *b)
185 : {
186 23 : BAT *bn;
187 23 : oid *restrict p;
188 23 : struct canditer cia, cib;
189 :
190 23 : BATcheck(a, NULL);
191 23 : BATcheck(b, NULL);
192 :
193 23 : canditer_init(&cia, NULL, a);
194 23 : canditer_init(&cib, NULL, b);
195 :
196 23 : if (cia.ncand == 0 || cib.ncand == 0) {
197 5 : bn = BATdense(0, 0, 0);
198 5 : goto doreturn;
199 : }
200 :
201 18 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
202 : /* both lists are dense */
203 6 : bn = newdensecand(MAX(cia.seq, cib.seq), MIN(cia.seq + cia.ncand, cib.seq + cib.ncand));
204 6 : goto doreturn;
205 : }
206 :
207 12 : bn = COLnew(0, TYPE_oid, MIN(cia.ncand, cib.ncand), TRANSIENT);
208 12 : if (bn == NULL)
209 0 : goto doreturn;
210 12 : p = (oid *) Tloc(bn, 0);
211 12 : if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
212 12 : if (cib.tpe == cand_dense) {
213 12 : struct canditer ci;
214 12 : ci = cia;
215 12 : cia = cib;
216 12 : cib = ci;
217 : }
218 : /* only cia is dense */
219 :
220 : /* search for first value in cib that is contained in cia */
221 12 : canditer_setidx(&cib, canditer_search(&cib, cia.seq, true));
222 12 : oid bo;
223 42 : while (!is_oid_nil(bo = canditer_next(&cib)) && bo < cia.seq + cia.ncand)
224 30 : *p++ = bo;
225 : } else {
226 : /* a and b are both not dense */
227 0 : oid ao = canditer_next(&cia);
228 0 : oid bo = canditer_next(&cib);
229 0 : while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
230 0 : if (ao < bo)
231 0 : ao = canditer_next(&cia);
232 0 : else if (bo < ao)
233 0 : bo = canditer_next(&cib);
234 : else {
235 0 : *p++ = ao;
236 0 : ao = canditer_next(&cia);
237 0 : bo = canditer_next(&cib);
238 : }
239 : }
240 : }
241 :
242 : /* properties */
243 12 : BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
244 12 : bn->trevsorted = BATcount(bn) <= 1;
245 12 : bn->tsorted = true;
246 12 : bn->tkey = true;
247 12 : bn->tnil = false;
248 12 : bn->tnonil = true;
249 12 : bn = virtualize(bn);
250 23 : doreturn:
251 23 : TRC_DEBUG(ALGO, ALGOBATFMT "," ALGOBATFMT " -> " ALGOOPTBATFMT "\n",
252 : ALGOBATPAR(a), ALGOBATPAR(b), ALGOOPTBATPAR(bn));
253 : return bn;
254 : }
255 :
256 : /* calculate the difference of two candidate lists and produce a new one
257 : */
258 : BAT *
259 0 : BATdiffcand(BAT *a, BAT *b)
260 : {
261 0 : BAT *bn;
262 0 : oid *restrict p;
263 0 : struct canditer cia, cib;
264 :
265 0 : BATcheck(a, NULL);
266 0 : BATcheck(b, NULL);
267 :
268 0 : canditer_init(&cia, NULL, a);
269 0 : canditer_init(&cib, NULL, b);
270 :
271 0 : if (cia.ncand == 0) {
272 0 : bn = BATdense(0, 0, 0);
273 0 : goto doreturn;
274 : }
275 0 : if (cib.ncand == 0) {
276 0 : bn = canditer_slice(&cia, 0, cia.ncand);
277 0 : goto doreturn;
278 : }
279 :
280 0 : if (cib.seq > canditer_last(&cia) || canditer_last(&cib) < cia.seq) {
281 : /* no overlap, return a */
282 0 : bn = canditer_slice(&cia, 0, cia.ncand);
283 0 : goto doreturn;
284 : }
285 :
286 0 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
287 : /* both a and b are dense */
288 0 : if (cia.seq < cib.seq) {
289 : /* a starts before b */
290 0 : if (cia.seq + cia.ncand <= cib.seq + cib.ncand) {
291 : /* b overlaps with end of a */
292 0 : bn = canditer_slice(&cia, 0, cib.seq - cia.seq);
293 0 : goto doreturn;
294 : }
295 : /* b is subset of a */
296 0 : bn = canditer_slice2(&cia, 0, cib.seq - cia.seq,
297 : cib.seq + cib.ncand - cia.seq,
298 : cia.ncand);
299 0 : goto doreturn;
300 : } else {
301 : /* cia.seq >= cib.seq */
302 0 : if (cia.seq + cia.ncand > cib.seq + cib.ncand) {
303 : /* b overlaps with beginning of a */
304 0 : bn = canditer_slice(&cia, cib.seq + cib.ncand - cia.seq, cia.ncand);
305 0 : goto doreturn;
306 : }
307 : /* a is subset f b */
308 0 : bn = BATdense(0, 0, 0);
309 0 : goto doreturn;
310 : }
311 : }
312 0 : if (cib.tpe == cand_dense) {
313 : /* b is dense and a is not: we can copy the part of a
314 : * that is before the start of b and the part of a
315 : * that is after the end of b */
316 0 : bn = canditer_slice2val(&cia, oid_nil, cib.seq,
317 0 : cib.seq + cib.ncand, oid_nil);
318 0 : goto doreturn;
319 : }
320 :
321 : /* b is not dense */
322 0 : bn = COLnew(0, TYPE_oid, BATcount(a), TRANSIENT);
323 0 : if (bn == NULL)
324 0 : goto doreturn;
325 0 : p = Tloc(bn, 0);
326 : /* find first position in b that is in range of a */
327 0 : canditer_setidx(&cib, canditer_search(&cib, cia.seq, true));
328 : {
329 : /* because we may jump over this declaration, we put
330 : * it inside a block */
331 0 : oid ob = canditer_next(&cib);
332 0 : for (BUN i = 0; i < cia.ncand; i++) {
333 0 : oid oa = canditer_next(&cia);
334 0 : while (!is_oid_nil(ob) && ob < oa) {
335 0 : ob = canditer_next(&cib);
336 : }
337 0 : if (is_oid_nil(ob) || oa < ob)
338 0 : *p++ = oa;
339 : }
340 : }
341 :
342 : /* properties */
343 0 : BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
344 0 : bn->trevsorted = BATcount(bn) <= 1;
345 0 : bn->tsorted = true;
346 0 : bn->tkey = true;
347 0 : bn->tnil = false;
348 0 : bn->tnonil = true;
349 0 : bn = virtualize(bn);
350 0 : doreturn:
351 0 : TRC_DEBUG(ALGO, ALGOBATFMT "," ALGOBATFMT " -> " ALGOOPTBATFMT "\n",
352 : ALGOBATPAR(a), ALGOBATPAR(b), ALGOOPTBATPAR(bn));
353 : return bn;
354 : }
355 :
356 : /* return offset of first value in cand that is >= o */
357 : static inline BUN
358 1339341 : binsearchcand(const oid *cand, BUN hi, oid o)
359 : {
360 1339341 : BUN lo = 0;
361 :
362 1339341 : if (o <= cand[lo])
363 : return 0;
364 664826 : if (o > cand[hi])
365 614751 : return hi + 1;
366 : /* loop invariant: cand[lo] < o <= cand[hi] */
367 310326 : while (hi > lo + 1) {
368 273933 : BUN mid = (lo + hi) / 2;
369 273933 : if (cand[mid] == o)
370 13682 : return mid;
371 260251 : if (cand[mid] < o)
372 : lo = mid;
373 : else
374 190689 : hi = mid;
375 : }
376 : return hi;
377 : }
378 :
379 : /* count number of 1 bits in ci->mask between bit positions lo
380 : * (inclusive) and hi (not inclusive) */
381 : static BUN
382 14362 : count_mask_bits(const struct canditer *ci, BUN lo, BUN hi)
383 : {
384 14362 : BUN n;
385 14362 : assert(lo <= hi);
386 14362 : assert(ci->tpe == cand_mask);
387 14362 : if (lo == hi)
388 : return 0;
389 14362 : lo += ci->firstbit;
390 14362 : hi += ci->firstbit;
391 14362 : BUN loi = lo / 32;
392 14362 : BUN hii = hi / 32;
393 14362 : lo %= 32;
394 14362 : hi %= 32;
395 14362 : if (loi == hii)
396 704 : return (BUN) candmask_pop((ci->mask[loi] & ((1U << hi) - 1)) >> lo);
397 13658 : n = (BUN) candmask_pop(ci->mask[loi++] >> lo);
398 3665007 : while (loi < hii)
399 3651349 : n += (BUN) candmask_pop(ci->mask[loi++]);
400 13658 : if (hi != 0)
401 3782 : n += (BUN) candmask_pop(ci->mask[loi] & ((1U << hi) - 1));
402 : return n;
403 : }
404 :
405 : /* initialize a candidate iterator */
406 : void
407 6834467 : canditer_init(struct canditer *ci, BAT *b, BAT *s)
408 : {
409 6834467 : assert(ci != NULL);
410 6834467 : BUN batcount = 0;
411 6834467 : oid hseq = 0;
412 6834467 : if (b) {
413 6237808 : MT_lock_set(&b->theaplock);
414 6236204 : batcount = BATcount(b);
415 6236204 : hseq = b->hseqbase;
416 6236204 : MT_lock_unset(&b->theaplock);
417 : }
418 :
419 6833720 : if (s == NULL) {
420 2791394 : if (b == NULL) {
421 : /* trivially empty candidate list */
422 0 : *ci = (struct canditer) {
423 : .tpe = cand_dense,
424 : };
425 0 : return;
426 : }
427 : /* every row is a candidate */
428 2791394 : *ci = (struct canditer) {
429 : .tpe = cand_dense,
430 : .seq = hseq,
431 : .hseq = hseq,
432 : .ncand = batcount,
433 : };
434 2791394 : return;
435 : }
436 :
437 4042326 : assert(ATOMtype(s->ttype) == TYPE_oid || s->ttype == TYPE_msk);
438 4042326 : assert(s->ttype == TYPE_msk|| s->tsorted);
439 4042326 : assert(s->ttype == TYPE_msk|| s->tkey);
440 4042326 : assert(s->ttype == TYPE_msk|| s->tnonil);
441 4042326 : assert(s->ttype == TYPE_void || s->tvheap == NULL);
442 :
443 4042326 : BUN cnt = BATcount(s);
444 :
445 4042326 : if (cnt == 0 || (b != NULL && batcount == 0)) {
446 : /* candidate list for empty BAT or empty candidate list */
447 914351 : *ci = (struct canditer) {
448 : .tpe = cand_dense,
449 914351 : .hseq = s->hseqbase,
450 : .s = s,
451 : };
452 914351 : return;
453 : }
454 :
455 3127975 : *ci = (struct canditer) {
456 3127975 : .seq = s->tseqbase,
457 3127975 : .hseq = s->hseqbase,
458 : .s = s,
459 : };
460 :
461 3127975 : if (mask_cand(s)) {
462 14362 : ci->tpe = cand_mask;
463 14362 : ci->mask = (const uint32_t *) ccand_first(s);
464 14362 : ci->seq = s->tseqbase - (oid) CCAND(s)->firstbit;
465 14362 : ci->hseq = s->hseqbase;
466 14362 : ci->nvals = ccand_free(s) / sizeof(uint32_t);
467 14362 : cnt = ci->nvals * 32;
468 3113613 : } else if (s->ttype == TYPE_msk) {
469 0 : assert(0);
470 : ci->tpe = cand_mask;
471 : ci->mask = (const uint32_t *) s->theap->base;
472 : ci->seq = s->hseqbase;
473 : ci->nvals = (cnt + 31U) / 32U;
474 3113613 : } else if (s->ttype == TYPE_void) {
475 2392434 : assert(!is_oid_nil(ci->seq));
476 2392434 : if (s->tvheap) {
477 81586 : assert(ccand_free(s) % SIZEOF_OID == 0);
478 81586 : ci->nvals = ccand_free(s) / SIZEOF_OID;
479 81586 : if (ci->nvals > 0) {
480 81586 : ci->tpe = cand_except;
481 81586 : ci->oids = (const oid *) ccand_first(s);
482 : } else {
483 : /* why the vheap? */
484 : ci->tpe = cand_dense;
485 : }
486 : } else {
487 : ci->tpe = cand_dense;
488 : }
489 721179 : } else if (is_oid_nil(ci->seq)) {
490 689878 : ci->tpe = cand_materialized;
491 689878 : ci->oids = (const oid *) Tloc(s, 0);
492 689878 : ci->seq = ci->oids[0];
493 689878 : ci->nvals = cnt;
494 : } else {
495 : /* materialized dense: no exceptions */
496 : ci->tpe = cand_dense;
497 : }
498 3127975 : switch (ci->tpe) {
499 689881 : case cand_materialized:
500 689881 : if (b != NULL) {
501 599806 : BUN p = binsearchcand(ci->oids, cnt - 1U, hseq);
502 : /* p == cnt means candidate list is completely
503 : * before b */
504 599805 : ci->offset = p;
505 599805 : ci->oids += p;
506 599805 : cnt -= p;
507 599805 : if (cnt > 0) {
508 599795 : cnt = binsearchcand(ci->oids, cnt - 1U,
509 : hseq + batcount);
510 : /* cnt == 0 means candidate list is
511 : * completely after b */
512 : }
513 599795 : if (cnt == 0) {
514 : /* no overlap */
515 10 : *ci = (struct canditer) {
516 : .tpe = cand_dense,
517 : .s = s,
518 : };
519 10 : return;
520 : }
521 599795 : ci->seq = ci->oids[0];
522 599795 : ci->nvals = cnt;
523 599795 : if (ci->oids[cnt - 1U] - ci->seq == cnt - 1U) {
524 : /* actually dense */
525 21 : ci->tpe = cand_dense;
526 21 : ci->oids = NULL;
527 21 : ci->nvals = 0;
528 : }
529 : }
530 : break;
531 81586 : case cand_except:
532 : /* exceptions must all be within range of s */
533 81586 : assert(ci->oids[0] >= ci->seq);
534 81586 : assert(ci->oids[ci->nvals - 1U] < ci->seq + cnt + ci->nvals);
535 : /* prune exceptions at either end of range of s */
536 2754827 : while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
537 2673241 : ci->nvals--;
538 2673241 : ci->oids++;
539 2673241 : ci->seq++;
540 : }
541 81586 : while (ci->nvals > 0 &&
542 80435 : ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
543 0 : ci->nvals--;
544 81586 : if (b != NULL) {
545 64710 : if (ci->seq + cnt + ci->nvals <= hseq ||
546 64710 : ci->seq >= hseq + batcount) {
547 : /* candidate list does not overlap with b */
548 0 : *ci = (struct canditer) {
549 : .tpe = cand_dense,
550 : .s = s,
551 : };
552 0 : return;
553 : }
554 : }
555 81586 : if (ci->nvals > 0) {
556 80435 : if (b == NULL)
557 : break;
558 63648 : BUN p;
559 63648 : p = binsearchcand(ci->oids, ci->nvals - 1U, hseq);
560 63648 : if (p == ci->nvals) {
561 : /* all exceptions before start of b */
562 0 : ci->offset = hseq - ci->seq - ci->nvals;
563 0 : cnt = ci->seq + cnt + ci->nvals - hseq;
564 0 : ci->seq = hseq;
565 0 : ci->nvals = 0;
566 0 : ci->tpe = cand_dense;
567 0 : ci->oids = NULL;
568 0 : break;
569 : }
570 63648 : assert(hseq > ci->seq || p == 0);
571 63648 : if (hseq > ci->seq) {
572 : /* skip candidates, possibly including
573 : * exceptions */
574 0 : ci->oids += p;
575 0 : ci->nvals -= p;
576 0 : p = hseq - ci->seq - p;
577 0 : cnt -= p;
578 0 : ci->offset += p;
579 0 : ci->seq = hseq;
580 : }
581 63648 : if (ci->seq + cnt + ci->nvals > hseq + batcount) {
582 0 : p = binsearchcand(ci->oids, ci->nvals - 1U,
583 : hseq + batcount);
584 0 : ci->nvals = p;
585 0 : cnt = hseq + batcount - ci->seq - ci->nvals;
586 : }
587 63648 : while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
588 0 : ci->nvals--;
589 0 : ci->oids++;
590 0 : ci->seq++;
591 : }
592 63648 : while (ci->nvals > 0 &&
593 63648 : ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
594 0 : ci->nvals--;
595 63648 : if (ci->nvals > 0)
596 : break;
597 : }
598 1151 : ci->tpe = cand_dense;
599 1151 : ci->oids = NULL;
600 : /* fall through */
601 2343297 : case cand_dense:
602 2343297 : if (b != NULL) {
603 2033509 : if (ci->seq + cnt <= hseq ||
604 2033509 : ci->seq >= hseq + batcount) {
605 : /* no overlap */
606 0 : *ci = (struct canditer) {
607 : .tpe = cand_dense,
608 : .s = s,
609 : };
610 0 : return;
611 : }
612 2033509 : if (hseq > ci->seq) {
613 41 : cnt -= hseq - ci->seq;
614 41 : ci->offset += hseq - ci->seq;
615 41 : ci->seq = hseq;
616 : }
617 2033509 : if (ci->seq + cnt > hseq + batcount)
618 40 : cnt = hseq + batcount - ci->seq;
619 : }
620 : break;
621 14363 : case cand_mask:
622 14363 : assert(s->tseqbase != oid_nil);
623 14363 : if (b != NULL) {
624 4635 : if (ci->seq + cnt <= hseq ||
625 4635 : ci->seq >= hseq + batcount) {
626 : /* no overlap */
627 0 : *ci = (struct canditer) {
628 : .tpe = cand_dense,
629 : .s = s,
630 : };
631 0 : return;
632 : }
633 4635 : if (hseq > ci->seq) {
634 0 : cnt = hseq - ci->seq;
635 0 : ci->mask += cnt / 32U;
636 0 : ci->firstbit = (uint8_t) (cnt % 32U);
637 0 : cnt = BATcount(s) - cnt;
638 0 : ci->seq = hseq;
639 : }
640 4635 : if (ci->seq + cnt > hseq + batcount) {
641 4611 : cnt = hseq + batcount - ci->seq;
642 : }
643 4635 : ci->nvals = (ci->firstbit + cnt + 31U) / 32U;
644 : }
645 : /* if first value is only partially used, check
646 : * whether there are any 1 bits in the used part */
647 14363 : if (ci->firstbit > 0 && (ci->mask[0] >> ci->firstbit) == 0) {
648 0 : if (cnt <= 32U - ci->firstbit) {
649 : cnt = 0;
650 : /* returns below */
651 : } else {
652 0 : cnt -= 32U - ci->firstbit;
653 0 : ci->firstbit = 0;
654 0 : ci->mask++;
655 0 : ci->nvals--;
656 : }
657 : }
658 : /* skip over any zero mask words that are used completely */
659 14363 : if (ci->firstbit == 0) {
660 34962 : while (cnt >= 32U && ci->mask[0] == 0) {
661 20601 : cnt -= 32U;
662 20601 : ci->mask++;
663 20601 : ci->nvals--;
664 : }
665 : }
666 : /* check whether there are any 1 bits in the last word */
667 14363 : if (cnt == 0 ||
668 14363 : (cnt < 32U - ci->firstbit &&
669 704 : ((ci->mask[0] >> ci->firstbit) & ((1U << cnt) - 1U)) == 0)) {
670 : /* no one bits in the whole relevant portion
671 : * of the bat */
672 0 : *ci = (struct canditer) {
673 : .tpe = cand_dense,
674 : .s = s,
675 : };
676 0 : return;
677 : }
678 : /* here we know there are 1 bits in the first mask
679 : * word */
680 14363 : int i = candmask_lobit(ci->mask[0] >> ci->firstbit);
681 14363 : assert(i >= 0); /* there should be a set bit */
682 14363 : ci->firstbit += i;
683 14363 : cnt -= i;
684 14363 : if (mask_cand(s))
685 14363 : ci->mskoff = s->tseqbase - (oid) CCAND(s)->firstbit + (ci->mask - (const uint32_t *) ccand_first(s)) * 32U;
686 : else
687 0 : ci->mskoff = s->tseqbase + (ci->mask - (const uint32_t *) s->theap->base) * 32U;
688 14363 : ci->seq = ci->mskoff + ci->firstbit;
689 14363 : ci->nextbit = ci->firstbit;
690 : /* at this point we know that bit ci->firstbit is set
691 : * in ci->mask[0] */
692 14363 : ci->lastbit = (ci->firstbit + cnt - 1U) % 32U + 1U;
693 14363 : if (ci->lastbit < 32 &&
694 4611 : (ci->mask[ci->nvals - 1] & ((1U << ci->lastbit) - 1)) == 0) {
695 : /* last partial word is all zero */
696 125 : cnt -= ci->lastbit;
697 125 : ci->lastbit = 32;
698 125 : ci->nvals--;
699 : }
700 14363 : if (ci->lastbit == 32) {
701 : /* "remove" zero words at the end */
702 12781 : while (cnt >= 32 && ci->mask[ci->nvals - 1] == 0) {
703 2904 : ci->nvals--;
704 2904 : cnt -= 32;
705 : }
706 : }
707 14363 : ci->ncand = count_mask_bits(ci, 0, cnt);
708 14362 : return;
709 : }
710 3113601 : ci->ncand = cnt;
711 3113601 : ci->hseq += ci->offset;
712 : }
713 :
714 : /* return the next candidate without advancing */
715 : oid
716 1582364 : canditer_peek(struct canditer *ci)
717 : {
718 1582364 : oid o = oid_nil;
719 1582364 : if (ci->next == ci->ncand)
720 : return oid_nil;
721 1576515 : switch (ci->tpe) {
722 1304132 : case cand_dense:
723 1304132 : o = ci->seq + ci->next;
724 1304132 : break;
725 262149 : case cand_materialized:
726 262149 : assert(ci->next < ci->nvals);
727 262149 : o = ci->oids[ci->next];
728 262149 : break;
729 10234 : case cand_except:
730 10234 : o = ci->seq + ci->add + ci->next;
731 10348 : while (ci->add < ci->nvals && o == ci->oids[ci->add]) {
732 114 : ci->add++;
733 114 : o++;
734 : }
735 : break;
736 : case cand_mask:
737 0 : while ((ci->mask[ci->nextmsk] >> ci->nextbit) == 0) {
738 0 : ci->nextmsk++;
739 0 : ci->nextbit = 0;
740 : }
741 0 : ci->nextbit += candmask_lobit(ci->mask[ci->nextmsk] >> ci->nextbit);
742 0 : o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
743 0 : break;
744 : }
745 : return o;
746 : }
747 :
748 : /* return the previous candidate */
749 : oid
750 379 : canditer_prev(struct canditer *ci)
751 : {
752 379 : if (ci->next == 0)
753 0 : return oid_nil;
754 379 : switch (ci->tpe) {
755 379 : case cand_dense:
756 379 : return ci->seq + --ci->next;
757 0 : case cand_materialized:
758 0 : return ci->oids[--ci->next];
759 : case cand_except:
760 : break;
761 0 : case cand_mask:
762 0 : for (;;) {
763 0 : if (ci->nextbit == 0) {
764 0 : ci->nextbit = 32;
765 0 : while (ci->mask[--ci->nextmsk] == 0)
766 : ;
767 : }
768 0 : if (ci->mask[ci->nextmsk] & (1U << --ci->nextbit))
769 : break;
770 : }
771 0 : ci->next--;
772 0 : return ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
773 : }
774 0 : oid o = ci->seq + ci->add + --ci->next;
775 0 : while (ci->add > 0 && o == ci->oids[ci->add - 1]) {
776 0 : ci->add--;
777 0 : o--;
778 : }
779 : return o;
780 : }
781 :
782 : /* return the previous candidate without retreating */
783 : oid
784 891 : canditer_peekprev(struct canditer *ci)
785 : {
786 891 : oid o = oid_nil;
787 :
788 891 : if (ci->next == 0)
789 : return oid_nil;
790 891 : switch (ci->tpe) {
791 891 : case cand_dense:
792 891 : return ci->seq + ci->next - 1;
793 0 : case cand_materialized:
794 0 : return ci->oids[ci->next - 1];
795 0 : case cand_except:
796 0 : o = ci->seq + ci->add + ci->next - 1;
797 0 : while (ci->add > 0 && o == ci->oids[ci->add - 1]) {
798 0 : ci->add--;
799 0 : o--;
800 : }
801 : break;
802 0 : case cand_mask:
803 0 : do {
804 0 : if (ci->nextbit == 0) {
805 0 : ci->nextbit = 32;
806 0 : while (ci->mask[--ci->nextmsk] == 0)
807 : ;
808 : }
809 0 : } while ((ci->mask[ci->nextmsk] & (1U << --ci->nextbit)) == 0);
810 0 : o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
811 0 : if (++ci->nextbit == 32) {
812 0 : ci->nextbit = 0;
813 0 : ci->nextmsk++;
814 : }
815 : break;
816 : }
817 : return o;
818 : }
819 :
820 : /* if o is a candidate, return it, else return the next candidate from
821 : * the cand_mask iterator ci after (if next is set) or before (if next
822 : * is unset) o; if there are no more candidates, return oid_nil */
823 : oid
824 0 : canditer_mask_next(const struct canditer *ci, oid o, bool next)
825 : {
826 0 : if (o < ci->mskoff)
827 0 : return next ? ci->mskoff + ci->firstbit : oid_nil;
828 0 : o -= ci->mskoff;
829 0 : BUN p = o / 32;
830 0 : o %= 32;
831 0 : if (p >= ci->nvals || (p == ci->nvals - 1 && o >= ci->lastbit))
832 0 : return next ? oid_nil : canditer_last(ci);
833 0 : if (next) {
834 0 : while ((ci->mask[p] & (1U << o)) == 0) {
835 0 : if (++o == 32) {
836 0 : o = 0;
837 0 : if (++p == ci->nvals)
838 0 : return oid_nil;
839 : }
840 : }
841 0 : if (p == ci->nvals - 1 && o >= ci->lastbit)
842 0 : return oid_nil;
843 : } else {
844 0 : while ((ci->mask[p] & (1U << o)) == 0) {
845 0 : if (o == 0) {
846 0 : o = 31;
847 0 : if (p == 0)
848 0 : return oid_nil;
849 : } else {
850 0 : o--;
851 : }
852 : }
853 0 : if (p == 0 && o < ci->firstbit)
854 0 : return oid_nil;
855 : }
856 0 : return ci->mskoff + 32 * p + o;
857 : }
858 :
859 : /* return the last candidate */
860 : oid
861 1278763 : canditer_last(const struct canditer *ci)
862 : {
863 1278763 : if (ci->ncand == 0)
864 0 : return oid_nil;
865 1278763 : switch (ci->tpe) {
866 968074 : case cand_dense:
867 968074 : return ci->seq + ci->ncand - 1;
868 249770 : case cand_materialized:
869 249770 : return ci->oids[ci->ncand - 1];
870 59760 : case cand_except:
871 59760 : return ci->seq + ci->ncand + ci->nvals - 1;
872 1159 : case cand_mask:
873 2952 : for (uint8_t i = ci->lastbit; i > 0; ) {
874 2952 : if (ci->mask[ci->nvals - 1] & (1U << --i))
875 1159 : return ci->mskoff + (ci->nvals - 1) * 32 + i;
876 : }
877 : break; /* cannot happen */
878 : }
879 0 : return oid_nil; /* cannot happen */
880 : }
881 :
882 : /* return the candidate at the given index */
883 : oid
884 452969834 : canditer_idx(const struct canditer *ci, BUN p)
885 : {
886 452969834 : if (p >= ci->ncand)
887 0 : return oid_nil;
888 452969834 : switch (ci->tpe) {
889 159584454 : case cand_dense:
890 159584454 : return ci->seq + p;
891 293243759 : case cand_materialized:
892 293243759 : return ci->oids[p];
893 141543 : case cand_except: {
894 141543 : oid o = ci->seq + p;
895 141543 : if (o < ci->oids[0])
896 : return o;
897 79386 : if (o + ci->nvals > ci->oids[ci->nvals - 1])
898 : return o + ci->nvals;
899 39354 : BUN lo = 0, hi = ci->nvals - 1;
900 259731 : while (hi - lo > 1) {
901 181023 : BUN mid = (hi + lo) / 2;
902 181023 : if (ci->oids[mid] - mid > o)
903 : hi = mid;
904 : else
905 116368 : lo = mid;
906 : }
907 39354 : return o + hi;
908 : }
909 78 : case cand_mask: {
910 78 : BUN x;
911 78 : if ((x = candmask_pop(ci->mask[0] >> ci->firstbit)) > p) {
912 26 : for (uint8_t i = ci->firstbit; ; i++) {
913 104 : if (ci->mask[0] & (1U << i)) {
914 104 : if (p == 0)
915 78 : return ci->mskoff + i;
916 26 : p--;
917 : }
918 : }
919 : }
920 0 : for (BUN n = 1; n < ci->nvals; n++) {
921 0 : uint32_t mask = ci->mask[n];
922 0 : p -= x;
923 0 : x = candmask_pop(mask);
924 0 : if (x > p) {
925 0 : for (uint8_t i = 0; ; i++) {
926 0 : if (mask & (1U << i)) {
927 0 : if (p == 0)
928 0 : return ci->mskoff + n * 32 + i;
929 0 : p--;
930 : }
931 : }
932 : }
933 : }
934 : break; /* cannot happen */
935 : }
936 : }
937 0 : return oid_nil; /* cannot happen */
938 : }
939 :
940 : /* set the index for the next candidate to be returned */
941 : void
942 274077 : canditer_setidx(struct canditer *ci, BUN p)
943 : {
944 274077 : if (p != ci->next) {
945 242808 : if (p >= ci->ncand) {
946 10293 : ci->next = ci->ncand;
947 10293 : switch (ci->tpe) {
948 0 : case cand_except:
949 0 : ci->add = ci->nvals;
950 0 : break;
951 0 : case cand_mask:
952 0 : ci->nextbit = ci->lastbit;
953 0 : ci->nextmsk = ci->nvals;
954 0 : if (ci->nextbit == 32)
955 0 : ci->nextbit = 0;
956 : else
957 0 : ci->nextmsk--;
958 : break;
959 : default:
960 : break;
961 : }
962 : } else {
963 232515 : ci->next = p;
964 232515 : switch (ci->tpe) {
965 7024 : case cand_except:
966 7024 : ci->add = canditer_idx(ci, p) - ci->seq - p;
967 7024 : break;
968 0 : case cand_mask: {
969 0 : oid o = canditer_idx(ci, p) - ci->mskoff;
970 0 : ci->nextmsk = o / 32;
971 0 : ci->nextbit = (uint8_t) (o % 32);
972 0 : break;
973 : }
974 : default:
975 : break;
976 : }
977 : }
978 : }
979 274077 : }
980 :
981 : /* reset */
982 : void
983 664144 : canditer_reset(struct canditer *ci)
984 : {
985 664144 : if (ci->tpe == cand_mask) {
986 0 : ci->nextbit = ci->firstbit;
987 0 : ci->nextmsk = 0;
988 : } else {
989 664144 : ci->add = 0;
990 : }
991 664144 : ci->next = 0;
992 664144 : }
993 :
994 : /* return index of given candidate if it occurs; if the candidate does
995 : * not occur, if next is set, return index of next larger candidate,
996 : * if next is not set, return BUN_NONE */
997 : BUN
998 1073314 : canditer_search(const struct canditer *ci, oid o, bool next)
999 : {
1000 1073314 : BUN p;
1001 :
1002 1073314 : switch (ci->tpe) {
1003 996286 : case cand_dense:
1004 996286 : if (o < ci->seq)
1005 705 : return next ? 0 : BUN_NONE;
1006 995581 : if (o >= ci->seq + ci->ncand)
1007 209444 : return next ? ci->ncand : BUN_NONE;
1008 786137 : return o - ci->seq;
1009 41903 : case cand_materialized:
1010 41903 : if (ci->nvals == 0)
1011 : return 0;
1012 41903 : p = binsearchcand(ci->oids, ci->nvals - 1, o);
1013 41905 : if (next || (p != ci->nvals && ci->oids[p] == o))
1014 41232 : return p;
1015 : break;
1016 35125 : case cand_except:
1017 35125 : if (o < ci->seq)
1018 0 : return next ? 0 : BUN_NONE;
1019 35125 : if (o >= ci->seq + ci->ncand + ci->nvals)
1020 937 : return next ? ci->ncand : BUN_NONE;
1021 34188 : p = binsearchcand(ci->oids, ci->nvals - 1, o);
1022 34188 : if (next || p == ci->nvals || ci->oids[p] != o)
1023 30721 : return o - ci->seq - p;
1024 : break;
1025 0 : case cand_mask:
1026 0 : if (o < ci->mskoff) {
1027 0 : return next ? 0 : BUN_NONE;
1028 : }
1029 0 : o -= ci->mskoff;
1030 0 : p = o / 32;
1031 0 : if (p >= ci->nvals)
1032 0 : return next ? ci->ncand : BUN_NONE;
1033 0 : o %= 32;
1034 0 : if (p == ci->nvals - 1 && o >= ci->lastbit)
1035 0 : return next ? ci->ncand : BUN_NONE;
1036 0 : if (next || ci->mask[p] & (1U << o))
1037 0 : return count_mask_bits(ci, 0, p * 32 + o) + !(ci->mask[p] & (1U << o));
1038 : break;
1039 : }
1040 : return BUN_NONE;
1041 : }
1042 :
1043 : static BAT *
1044 677 : canditer_sliceval_mask(const struct canditer *ci, oid lo1, oid hi1, BUN cnt1,
1045 : oid lo2, oid hi2, BUN cnt2)
1046 : {
1047 677 : assert(cnt2 == 0 || !is_oid_nil(lo2));
1048 677 : assert(cnt2 == 0 || lo2 >= hi1);
1049 677 : if (is_oid_nil(lo1) || lo1 < ci->mskoff + ci->firstbit)
1050 157 : lo1 = ci->mskoff + ci->firstbit;
1051 677 : if (is_oid_nil(hi1) || hi1 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
1052 375 : hi1 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
1053 :
1054 677 : BAT *bn = COLnew(0, TYPE_oid, cnt1 + cnt2, TRANSIENT);
1055 677 : if (bn == NULL)
1056 : return NULL;
1057 677 : bn->tkey = true;
1058 :
1059 677 : if (hi1 > ci->mskoff) {
1060 398 : if (lo1 < ci->mskoff)
1061 : lo1 = 0;
1062 : else
1063 398 : lo1 -= ci->mskoff;
1064 398 : hi1 -= ci->mskoff;
1065 3548 : for (oid o = lo1; o < hi1 && cnt1 > 0; o++) {
1066 3150 : if (ci->mask[o / 32] & (1U << (o % 32))) {
1067 2694 : if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
1068 0 : BBPreclaim(bn);
1069 0 : return NULL;
1070 : }
1071 2694 : cnt1--;
1072 : }
1073 : }
1074 : }
1075 677 : if (cnt2 > 0) {
1076 26 : if (lo2 < ci->mskoff + ci->firstbit)
1077 : lo2 = ci->mskoff + ci->firstbit;
1078 26 : if (is_oid_nil(hi2) || hi2 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
1079 26 : hi2 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
1080 :
1081 26 : lo2 -= ci->mskoff;
1082 26 : hi2 -= ci->mskoff;
1083 214 : for (oid o = lo2; o < hi2 && cnt2 > 0; o++) {
1084 188 : if (ci->mask[o / 32] & (1U << (o % 32))) {
1085 184 : if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
1086 0 : BBPreclaim(bn);
1087 0 : return NULL;
1088 : }
1089 184 : cnt2--;
1090 : }
1091 : }
1092 : }
1093 : return bn;
1094 : }
1095 :
1096 : /* return either an actual BATslice or a new BAT that contains the
1097 : * "virtual" slice of the input candidate list BAT; except, unlike
1098 : * BATslice, the hseqbase of the returned BAT is 0; note for cand_mask
1099 : * candidate iterators, the BUN values refer to number of 1 bits */
1100 : BAT *
1101 513572 : canditer_slice(const struct canditer *ci, BUN lo, BUN hi)
1102 : {
1103 513572 : BAT *bn;
1104 513572 : oid o;
1105 513572 : BUN add;
1106 :
1107 513572 : assert(ci != NULL);
1108 :
1109 513572 : if (lo >= ci->ncand || lo >= hi)
1110 131488 : return BATdense(0, 0, 0);
1111 382084 : if (hi > ci->ncand)
1112 : hi = ci->ncand;
1113 382084 : if (hi - lo == 1)
1114 329153 : return BATdense(0, canditer_idx(ci, lo), 1);
1115 52931 : switch (ci->tpe) {
1116 4750 : case cand_materialized:
1117 4750 : if (ci->s) {
1118 4750 : bn = BATslice(ci->s, lo + ci->offset, hi + ci->offset);
1119 4750 : BAThseqbase(bn, 0);
1120 4750 : return bn;
1121 : }
1122 0 : bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
1123 0 : if (bn == NULL)
1124 : return NULL;
1125 0 : BATsetcount(bn, hi - lo);
1126 0 : memcpy(Tloc(bn, 0), ci->oids + lo, (hi - lo) * sizeof(oid));
1127 0 : break;
1128 47889 : default: /* really: case cand_dense: */
1129 47889 : return BATdense(0, ci->seq + lo, hi - lo);
1130 289 : case cand_except:
1131 289 : o = canditer_idx(ci, lo);
1132 289 : add = o - ci->seq - lo;
1133 289 : assert(add <= ci->nvals);
1134 289 : if (add == ci->nvals || o + hi - lo < ci->oids[add]) {
1135 : /* after last exception or before next
1136 : * exception: return dense sequence */
1137 256 : return BATdense(0, o, hi - lo);
1138 : }
1139 33 : bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
1140 33 : if (bn == NULL)
1141 : return NULL;
1142 33 : BATsetcount(bn, hi - lo);
1143 254 : for (oid *dst = Tloc(bn, 0); lo < hi; lo++) {
1144 281 : while (add < ci->nvals && o == ci->oids[add]) {
1145 60 : o++;
1146 60 : add++;
1147 : }
1148 221 : *dst++ = o++;
1149 : }
1150 : break;
1151 3 : case cand_mask:
1152 3 : return canditer_sliceval_mask(ci, canditer_idx(ci, lo),
1153 : oid_nil, hi - lo,
1154 : oid_nil, oid_nil, 0);
1155 : }
1156 33 : bn->tsorted = true;
1157 33 : bn->trevsorted = BATcount(bn) <= 1;
1158 33 : bn->tkey = true;
1159 33 : bn->tseqbase = oid_nil;
1160 33 : bn->tnil = false;
1161 33 : bn->tnonil = true;
1162 33 : bn->tminpos = 0;
1163 33 : bn->tmaxpos = BATcount(bn) - 1;
1164 33 : return virtualize(bn);
1165 : }
1166 :
1167 : /* like the above, except the bounds are given by values instead of
1168 : * indexes */
1169 : BAT *
1170 409564 : canditer_sliceval(const struct canditer *ci, oid lo, oid hi)
1171 : {
1172 409564 : if (ci->tpe != cand_mask) {
1173 1226728 : return canditer_slice(
1174 : ci,
1175 408909 : is_oid_nil(lo) ? 0 : canditer_search(ci, lo, true),
1176 408916 : is_oid_nil(hi) ? ci->ncand : canditer_search(ci, hi, true));
1177 : }
1178 :
1179 648 : return canditer_sliceval_mask(ci, lo, hi, ci->ncand,
1180 : oid_nil, oid_nil, 0);
1181 : }
1182 :
1183 : /* return the combination of two slices */
1184 : BAT *
1185 22516 : canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2)
1186 : {
1187 22516 : BAT *bn;
1188 22516 : oid o;
1189 22516 : BUN add;
1190 :
1191 22516 : assert(lo1 <= hi1);
1192 22516 : assert(lo2 <= hi2);
1193 22516 : assert(hi1 <= lo2 || (lo2 == 0 && hi2 == 0));
1194 :
1195 22516 : if (hi1 == lo2) /* consecutive slices: combine into one */
1196 4964 : return canditer_slice(ci, lo1, hi2);
1197 17552 : if (lo2 == hi2 || hi1 >= ci->ncand || lo2 >= ci->ncand) {
1198 : /* empty second slice */
1199 13996 : return canditer_slice(ci, lo1, hi1);
1200 : }
1201 3556 : if (lo1 == hi1) /* empty first slice */
1202 1403 : return canditer_slice(ci, lo2, hi2);
1203 2153 : if (lo1 >= ci->ncand) /* out of range */
1204 : return BATdense(0, 0, 0);
1205 :
1206 2153 : if (hi2 >= ci->ncand)
1207 : hi2 = ci->ncand;
1208 :
1209 2153 : bn = COLnew(0, TYPE_oid, hi1 - lo1 + hi2 - lo2, TRANSIENT);
1210 2152 : if (bn == NULL)
1211 : return NULL;
1212 2152 : BATsetcount(bn, hi1 - lo1 + hi2 - lo2);
1213 2153 : bn->tsorted = true;
1214 2153 : bn->trevsorted = BATcount(bn) <= 1;
1215 2153 : bn->tkey = true;
1216 2153 : bn->tseqbase = oid_nil;
1217 2153 : bn->tnil = false;
1218 2153 : bn->tnonil = true;
1219 :
1220 2153 : oid *dst = Tloc(bn, 0);
1221 :
1222 2153 : switch (ci->tpe) {
1223 1 : case cand_materialized:
1224 1 : memcpy(dst, ci->oids + lo1, (hi1 - lo1) * sizeof(oid));
1225 1 : memcpy(dst + hi1 - lo1, ci->oids + lo2, (hi2 - lo2) * sizeof(oid));
1226 1 : break;
1227 : case cand_dense:
1228 923842 : while (lo1 < hi1)
1229 921690 : *dst++ = ci->seq + lo1++;
1230 262352 : while (lo2 < hi2)
1231 260200 : *dst++ = ci->seq + lo2++;
1232 : break;
1233 0 : case cand_except:
1234 0 : o = canditer_idx(ci, lo1);
1235 0 : add = o - ci->seq - lo1;
1236 0 : assert(add <= ci->nvals);
1237 0 : if (add == ci->nvals) {
1238 : /* after last exception: return dense sequence */
1239 0 : while (lo1 < hi1)
1240 0 : *dst++ = ci->seq + add + lo1++;
1241 : } else {
1242 0 : while (lo1 < hi1) {
1243 0 : while (add < ci->nvals && o == ci->oids[add]) {
1244 0 : o++;
1245 0 : add++;
1246 : }
1247 0 : *dst++ = o++;
1248 0 : lo1++;
1249 : }
1250 : }
1251 0 : o = canditer_idx(ci, lo2);
1252 0 : add = o - ci->seq - lo2;
1253 0 : assert(add <= ci->nvals);
1254 0 : if (add == ci->nvals) {
1255 : /* after last exception: return dense sequence */
1256 0 : while (lo2 < hi2)
1257 0 : *dst++ = ci->seq + add + lo2++;
1258 : } else {
1259 0 : while (lo2 < hi2) {
1260 0 : while (add < ci->nvals && o == ci->oids[add]) {
1261 0 : o++;
1262 0 : add++;
1263 : }
1264 0 : *dst++ = o++;
1265 0 : lo2++;
1266 : }
1267 : }
1268 : break;
1269 0 : case cand_mask:
1270 0 : return canditer_sliceval_mask(ci, canditer_idx(ci, lo1),
1271 : oid_nil, hi1 - lo1,
1272 : canditer_idx(ci, lo2),
1273 : oid_nil, hi2 - lo2);
1274 : }
1275 2153 : return virtualize(bn);
1276 : }
1277 :
1278 : BAT *
1279 22542 : canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2)
1280 : {
1281 22542 : if (ci->tpe != cand_mask) {
1282 90052 : return canditer_slice2(
1283 : ci,
1284 20388 : is_oid_nil(lo1) ? 0 : canditer_search(ci, lo1, true),
1285 22514 : is_oid_nil(hi1) ? ci->ncand : canditer_search(ci, hi1, true),
1286 22516 : is_oid_nil(lo2) ? 0 : canditer_search(ci, lo2, true),
1287 2123 : is_oid_nil(hi2) ? ci->ncand : canditer_search(ci, hi2, true));
1288 : }
1289 :
1290 26 : return canditer_sliceval_mask(ci, lo1, hi1, ci->ncand,
1291 26 : lo2, hi2, ci->ncand);
1292 : }
1293 :
1294 : BAT *
1295 0 : BATnegcands(BUN nr, BAT *odels)
1296 : {
1297 0 : const char *nme;
1298 0 : Heap *dels;
1299 0 : BUN lo, hi;
1300 0 : ccand_t *c;
1301 0 : BAT *bn;
1302 :
1303 0 : bn = BATdense(0, 0, nr);
1304 0 : if (bn == NULL)
1305 : return NULL;
1306 0 : if (BATcount(odels) == 0)
1307 : return bn;
1308 :
1309 0 : lo = SORTfndfirst(odels, &bn->tseqbase);
1310 0 : hi = SORTfndfirst(odels, &(oid) {bn->tseqbase + BATcount(bn)});
1311 0 : if (lo == hi)
1312 : return bn;
1313 :
1314 0 : nme = BBP_physical(bn->batCacheid);
1315 0 : if ((dels = GDKmalloc(sizeof(Heap))) == NULL){
1316 0 : BBPreclaim(bn);
1317 0 : return NULL;
1318 : }
1319 0 : *dels = (Heap) {
1320 0 : .farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap),
1321 0 : .parentid = bn->batCacheid,
1322 : .dirty = true,
1323 : };
1324 0 : strconcat_len(dels->filename, sizeof(dels->filename),
1325 : nme, ".theap", NULL);
1326 :
1327 0 : if (dels->farmid < 0 ||
1328 0 : HEAPalloc(dels, hi - lo + (sizeof(ccand_t)/sizeof(oid)), sizeof(oid)) != GDK_SUCCEED) {
1329 0 : GDKfree(dels);
1330 0 : BBPreclaim(bn);
1331 0 : return NULL;
1332 : }
1333 0 : ATOMIC_INIT(&dels->refs, 1);
1334 0 : c = (ccand_t *) dels->base;
1335 0 : *c = (ccand_t) {
1336 : .type = CAND_NEGOID,
1337 : };
1338 0 : dels->free = sizeof(ccand_t) + sizeof(oid) * (hi - lo);
1339 0 : BATiter bi = bat_iterator(odels);
1340 0 : if (bi.type == TYPE_void) {
1341 0 : oid *r = (oid *) (dels->base + sizeof(ccand_t));
1342 0 : for (BUN x = lo; x < hi; x++)
1343 0 : r[x - lo] = x + odels->tseqbase;
1344 : } else {
1345 0 : oid *r = (oid *) (dels->base + sizeof(ccand_t));
1346 0 : memcpy(r, (const oid *) bi.base + lo, sizeof(oid) * (hi - lo));
1347 : }
1348 0 : bat_iterator_end(&bi);
1349 0 : assert(bn->tvheap == NULL);
1350 0 : bn->tvheap = dels;
1351 0 : BATsetcount(bn, bn->batCount - (hi - lo));
1352 0 : TRC_DEBUG(ALGO, "BATnegcands(cands=" ALGOBATFMT ","
1353 : "dels=" ALGOBATFMT ")\n",
1354 : ALGOBATPAR(bn),
1355 : ALGOBATPAR(odels));
1356 0 : TRC_DEBUG(ALGO, "nr=" BUNFMT ", odels=" ALGOBATFMT
1357 : " -> " ALGOBATFMT "\n",
1358 : nr, ALGOBATPAR(odels),
1359 : ALGOBATPAR(bn));
1360 : return bn;
1361 : }
1362 :
1363 : BAT *
1364 88418 : BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected)
1365 : {
1366 88418 : const char *nme;
1367 88418 : Heap *msks;
1368 88418 : ccand_t *c;
1369 88418 : BUN nmask;
1370 88418 : BAT *bn;
1371 :
1372 88418 : assert(masked->ttype == TYPE_msk);
1373 :
1374 88418 : bn = COLnew(hseq, TYPE_void, 0, TRANSIENT);
1375 88418 : if (bn == NULL)
1376 : return NULL;
1377 88418 : BATtseqbase(bn, hseq);
1378 :
1379 88418 : if (BATcount(masked) == 0)
1380 : return bn;
1381 :
1382 88418 : nme = BBP_physical(bn->batCacheid);
1383 88418 : if ((msks = GDKmalloc(sizeof(Heap))) == NULL){
1384 0 : BBPreclaim(bn);
1385 0 : return NULL;
1386 : }
1387 176835 : *msks = (Heap) {
1388 88418 : .farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap),
1389 88417 : .parentid = bn->batCacheid,
1390 : .dirty = true,
1391 : };
1392 88417 : strconcat_len(msks->filename, sizeof(msks->filename),
1393 : nme, ".theap", NULL);
1394 :
1395 88418 : nmask = (nr + 31) / 32;
1396 176836 : if (msks->farmid < 0 ||
1397 88418 : HEAPalloc(msks, nmask + (sizeof(ccand_t)/sizeof(uint32_t)), sizeof(uint32_t)) != GDK_SUCCEED) {
1398 0 : GDKfree(msks);
1399 0 : BBPreclaim(bn);
1400 0 : return NULL;
1401 : }
1402 88418 : c = (ccand_t *) msks->base;
1403 88418 : *c = (ccand_t) {
1404 : .type = CAND_MSK,
1405 : // .mask = true,
1406 : };
1407 88418 : msks->free = sizeof(ccand_t) + nmask * sizeof(uint32_t);
1408 88418 : uint32_t *r = (uint32_t*)(msks->base + sizeof(ccand_t));
1409 88418 : BATiter bi = bat_iterator(masked);
1410 88418 : if (selected) {
1411 88418 : if (nr <= bi.count)
1412 88418 : memcpy(r, bi.base, nmask * sizeof(uint32_t));
1413 : else
1414 0 : memcpy(r, bi.base, (bi.count + 31) / 32 * sizeof(uint32_t));
1415 : } else {
1416 0 : const uint32_t *s = (const uint32_t *) bi.base;
1417 0 : BUN nmask_ = (bi.count + 31) / 32;
1418 0 : for (BUN i = 0; i < nmask_; i++)
1419 0 : r[i] = ~s[i];
1420 : }
1421 88418 : if (nr > bi.count) {
1422 0 : BUN rest = bi.count & 31;
1423 0 : BUN nmask_ = (bi.count + 31) / 32;
1424 0 : if (rest > 0)
1425 0 : r[nmask_ -1] |= ((1U << (32 - rest)) - 1) << rest;
1426 0 : for (BUN j = nmask_; j < nmask; j++)
1427 0 : r[j] = ~0;
1428 : }
1429 88418 : bat_iterator_end(&bi);
1430 : /* make sure last word doesn't have any spurious bits set */
1431 88418 : BUN cnt = nr % 32;
1432 88418 : if (cnt > 0)
1433 83945 : r[nmask - 1] &= (1U << cnt) - 1;
1434 : cnt = 0;
1435 12152737 : for (BUN i = 0; i < nmask; i++) {
1436 12064319 : if (cnt == 0 && r[i] != 0)
1437 88172 : c->firstbit = candmask_lobit(r[i]) + i * 32;
1438 12064319 : cnt += candmask_pop(r[i]);
1439 : }
1440 88418 : if (cnt > 0) {
1441 88177 : ATOMIC_INIT(&msks->refs, 1);
1442 88177 : assert(bn->tvheap == NULL);
1443 88177 : bn->tvheap = msks;
1444 88177 : bn->tseqbase += (oid) c->firstbit;
1445 : } else {
1446 : /* no point having a mask if it's empty */
1447 241 : HEAPfree(msks, true);
1448 241 : GDKfree(msks);
1449 : }
1450 88418 : BATsetcount(bn, cnt);
1451 88418 : TRC_DEBUG(ALGO, "hseq=" OIDFMT ", masked=" ALGOBATFMT ", selected=%s"
1452 : " -> " ALGOBATFMT "\n",
1453 : hseq, ALGOBATPAR(masked),
1454 : selected ? "true" : "false",
1455 : ALGOBATPAR(bn));
1456 88418 : assert(bn->tseqbase != oid_nil);
1457 : return bn;
1458 : }
1459 :
1460 : /* convert a masked candidate list to a positive or negative candidate list */
1461 : BAT *
1462 99288 : BATunmask(BAT *b)
1463 : {
1464 : // assert(!mask_cand(b) || CCAND(b)->mask); /* todo handle negmask case */
1465 99288 : BUN cnt;
1466 99288 : uint32_t rem;
1467 99288 : uint32_t val;
1468 99288 : const uint32_t *src;
1469 99288 : oid *dst;
1470 99288 : BUN n = 0;
1471 99288 : oid tseq = b->hseqbase;
1472 99288 : bool negcand = false;
1473 :
1474 99288 : BATiter bi = bat_iterator(b);
1475 99287 : if (mask_cand(b)) {
1476 94741 : cnt = ccand_free(b) / sizeof(uint32_t);
1477 94741 : rem = 0;
1478 94741 : src = (const uint32_t *) ccand_first(b);
1479 94741 : tseq = b->tseqbase;
1480 94741 : tseq -= (oid) CCAND(b)->firstbit;
1481 : /* create negative candidate list if more than half the
1482 : * bits are set */
1483 94741 : negcand = BATcount(b) > cnt * 16;
1484 : } else {
1485 4546 : cnt = bi.count / 32;
1486 4546 : rem = bi.count % 32;
1487 4546 : src = (const uint32_t *) bi.base;
1488 : }
1489 99287 : BAT *bn;
1490 :
1491 99287 : if (negcand) {
1492 82214 : bn = COLnew(b->hseqbase, TYPE_void, 0, TRANSIENT);
1493 82215 : if (bn == NULL) {
1494 0 : bat_iterator_end(&bi);
1495 0 : return NULL;
1496 : }
1497 82215 : Heap *dels;
1498 82215 : if ((dels = GDKmalloc(sizeof(Heap))) == NULL) {
1499 0 : BBPreclaim(bn);
1500 0 : bat_iterator_end(&bi);
1501 0 : return NULL;
1502 : }
1503 164424 : *dels = (Heap) {
1504 82213 : .farmid = BBPselectfarm(TRANSIENT, TYPE_void, varheap),
1505 82211 : .parentid = bn->batCacheid,
1506 : .dirty = true,
1507 : };
1508 82211 : strconcat_len(dels->filename, sizeof(dels->filename),
1509 82211 : BBP_physical(bn->batCacheid), ".theap", NULL);
1510 :
1511 164426 : if (dels->farmid < 0 ||
1512 82212 : HEAPalloc(dels, cnt * 32 - bi.count
1513 : + sizeof(ccand_t) / sizeof(oid), sizeof(oid)) != GDK_SUCCEED) {
1514 0 : GDKfree(dels);
1515 0 : BBPreclaim(bn);
1516 0 : bat_iterator_end(&bi);
1517 0 : return NULL;
1518 : }
1519 82214 : * (ccand_t *) dels->base = (ccand_t) {
1520 : .type = CAND_NEGOID,
1521 : };
1522 82214 : dst = (oid *) (dels->base + sizeof(ccand_t));
1523 10811973 : for (BUN p = 0, v = 0; p < cnt; p++, v += 32) {
1524 10729759 : if ((val = src[p]) == ~UINT32_C(0))
1525 9124624 : continue;
1526 51715401 : for (uint32_t i = 0; i < 32; i++) {
1527 50188032 : if ((val & (1U << i)) == 0) {
1528 44920104 : if (v + i >= b->batCount + n)
1529 : break;
1530 44842338 : dst[n++] = tseq + v + i;
1531 : }
1532 : }
1533 : }
1534 82214 : if (n == 0) {
1535 : /* didn't need it after all */
1536 8 : HEAPfree(dels, true);
1537 8 : GDKfree(dels);
1538 : } else {
1539 82206 : dels->free = sizeof(ccand_t) + n * sizeof(oid);
1540 82206 : dels->dirty = true;
1541 82206 : ATOMIC_INIT(&dels->refs, 1);
1542 82206 : assert(bn->tvheap == NULL);
1543 82206 : bn->tvheap = dels;
1544 : }
1545 82214 : BATsetcount(bn, n=bi.count);
1546 82215 : bn->tseqbase = tseq;
1547 : } else {
1548 17073 : bn = COLnew(b->hseqbase, TYPE_oid, mask_cand(b) ? bi.count : 1024, TRANSIENT);
1549 17073 : if (bn == NULL) {
1550 0 : bat_iterator_end(&bi);
1551 0 : return NULL;
1552 : }
1553 17073 : dst = (oid *) Tloc(bn, 0);
1554 2057225 : for (BUN p = 0; p < cnt; p++) {
1555 2040152 : if ((val = src[p]) == 0)
1556 1429337 : continue;
1557 20155881 : for (uint32_t i = 0; i < 32; i++) {
1558 19545066 : if (val & (1U << i)) {
1559 17878322 : if (n == BATcapacity(bn)) {
1560 54 : BATsetcount(bn, n);
1561 54 : if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
1562 0 : BBPreclaim(bn);
1563 0 : bat_iterator_end(&bi);
1564 0 : return NULL;
1565 : }
1566 54 : dst = (oid *) Tloc(bn, 0);
1567 : }
1568 17878322 : dst[n++] = tseq + p * 32 + i;
1569 : }
1570 : }
1571 : }
1572 : /* the last partial mask word */
1573 17073 : if (rem > 0 && (val = src[cnt]) != 0) {
1574 25626 : for (uint32_t i = 0; i < rem; i++) {
1575 23284 : if (val & (1U << i)) {
1576 697 : if (n == BATcapacity(bn)) {
1577 0 : BATsetcount(bn, n);
1578 0 : if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
1579 0 : BBPreclaim(bn);
1580 0 : bat_iterator_end(&bi);
1581 0 : return NULL;
1582 : }
1583 0 : dst = (oid *) Tloc(bn, 0);
1584 : }
1585 697 : dst[n++] = tseq + cnt * 32 + i;
1586 : }
1587 : }
1588 : }
1589 17073 : BATsetcount(bn, n);
1590 : }
1591 99288 : bat_iterator_end(&bi);
1592 99288 : bn->tkey = true;
1593 99288 : bn->tsorted = true;
1594 99288 : bn->trevsorted = n <= 1;
1595 99288 : bn->tnil = false;
1596 99288 : bn->tnonil = true;
1597 99288 : bn = virtualize(bn);
1598 99288 : TRC_DEBUG(ALGO, ALGOBATFMT " -> " ALGOBATFMT "\n", ALGOBATPAR(b), ALGOBATPAR(bn));
1599 : return bn;
1600 : }
|
