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 8806 : BATiscand(BAT *b)
20 : {
21 8806 : if (ATOMtype(b->ttype) != TYPE_oid)
22 : return false;
23 8806 : if (complex_cand(b))
24 : return true;
25 8352 : if (b->ttype == TYPE_void && is_oid_nil(b->tseqbase))
26 : return false;
27 16704 : 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 2814 : newdensecand(oid first, oid last)
34 : {
35 2814 : if (last <= first)
36 0 : first = last = 0; /* empty range */
37 2814 : 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 80986 : BATmergecand(BAT *a, BAT *b)
47 : {
48 80986 : BAT *bn;
49 80986 : oid *restrict p, i;
50 80986 : struct canditer cia, cib;
51 :
52 80986 : BATcheck(a, NULL);
53 80986 : BATcheck(b, NULL);
54 :
55 80986 : canditer_init(&cia, NULL, a);
56 80972 : canditer_init(&cib, NULL, b);
57 :
58 : /* we can return a if b is empty (and v.v.) */
59 80978 : if (cia.ncand == 0) {
60 12933 : bn = canditer_slice(&cib, 0, cib.ncand);
61 12933 : goto doreturn;
62 : }
63 68045 : if (cib.ncand == 0) {
64 10915 : bn = canditer_slice(&cia, 0, cia.ncand);
65 10914 : goto doreturn;
66 : }
67 : /* we can return a if a fully covers b (and v.v) */
68 57130 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
69 : /* both are dense */
70 10816 : 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 2373 : bn = newdensecand(cia.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
74 2374 : goto doreturn;
75 : }
76 8443 : 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 431 : bn = newdensecand(cib.seq, cia.seq + cia.ncand < cib.seq + cib.ncand ? cib.seq + cib.ncand : cia.seq + cia.ncand);
80 431 : goto doreturn;
81 : }
82 : }
83 54326 : if (cia.tpe == cand_dense
84 11031 : && cia.seq <= cib.seq
85 4872 : && canditer_last(&cia) >= canditer_last(&cib)) {
86 342 : bn = canditer_slice(&cia, 0, cia.ncand);
87 342 : goto doreturn;
88 : }
89 53984 : if (cib.tpe == cand_dense
90 38014 : && cib.seq <= cia.seq
91 9985 : && canditer_last(&cib) >= canditer_last(&cia)) {
92 186 : bn = canditer_slice(&cib, 0, cib.ncand);
93 186 : goto doreturn;
94 : }
95 :
96 53798 : bn = COLnew(0, TYPE_oid, cia.ncand + cib.ncand, TRANSIENT);
97 53806 : if (bn == NULL)
98 0 : goto doreturn;
99 53806 : p = (oid *) Tloc(bn, 0);
100 53806 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
101 : /* both lists are dense */
102 8012 : if (cia.seq > cib.seq) {
103 4028 : struct canditer ci;
104 4028 : ci = cia;
105 4028 : cia = cib;
106 4028 : cib = ci;
107 : }
108 : /* cia completely before cib */
109 8012 : assert(cia.seq + cia.ncand < cib.seq);
110 30602 : for (i = cia.seq; i < cia.seq + cia.ncand; i++)
111 22590 : *p++ = i;
112 : /* there is a gap */
113 27094 : for (i = cib.seq; i < cib.seq + cib.ncand; i++)
114 19082 : *p++ = i;
115 45794 : } else if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
116 32500 : if (cib.tpe == cand_dense) {
117 29824 : struct canditer ci;
118 29824 : ci = cia;
119 29824 : cia = cib;
120 29824 : cib = ci;
121 : }
122 : /* only cia is dense */
123 :
124 : /* copy part of cib that's before the start of cia */
125 132641 : while (canditer_peek(&cib) < cia.seq) {
126 100142 : *p++ = canditer_next(&cib);
127 : }
128 : /* copy all of cia */
129 75062 : for (i = cia.seq; i < cia.seq + cia.ncand; i++)
130 42563 : *p++ = i;
131 : /* skip over part of cib that overlaps with cia */
132 32499 : canditer_setidx(&cib, canditer_search(&cib, cia.seq + cia.ncand, true));
133 : /* copy rest of cib */
134 122484 : while (cib.next < cib.ncand) {
135 89989 : *p++ = canditer_next(&cib);
136 : }
137 : } else {
138 : /* a and b are both not dense */
139 13294 : oid ao = canditer_next(&cia);
140 13293 : oid bo = canditer_next(&cib);
141 23763520 : while (!is_oid_nil(ao) && !is_oid_nil(bo)) {
142 23750228 : if (ao < bo) {
143 13848522 : *p++ = ao;
144 13848522 : ao = canditer_next(&cia);
145 9901706 : } else if (bo < ao) {
146 8839965 : *p++ = bo;
147 8839965 : bo = canditer_next(&cib);
148 : } else {
149 1061741 : *p++ = ao;
150 1061741 : ao = canditer_next(&cia);
151 1061711 : bo = canditer_next(&cib);
152 : }
153 : }
154 578024 : while (!is_oid_nil(ao)) {
155 564731 : *p++ = ao;
156 564731 : ao = canditer_next(&cia);
157 : }
158 418705 : while (!is_oid_nil(bo)) {
159 405411 : *p++ = bo;
160 405411 : bo = canditer_next(&cib);
161 : }
162 : }
163 :
164 : /* properties */
165 53801 : BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
166 53800 : bn->trevsorted = BATcount(bn) <= 1;
167 53800 : bn->tsorted = true;
168 53800 : bn->tkey = true;
169 53800 : bn->tnil = false;
170 53800 : bn->tnonil = true;
171 53800 : bn = virtualize(bn);
172 80987 : doreturn:
173 80987 : 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 34 : BATintersectcand(BAT *a, BAT *b)
185 : {
186 34 : BAT *bn;
187 34 : oid *restrict p;
188 34 : struct canditer cia, cib;
189 :
190 34 : BATcheck(a, NULL);
191 34 : BATcheck(b, NULL);
192 :
193 34 : canditer_init(&cia, NULL, a);
194 34 : canditer_init(&cib, NULL, b);
195 :
196 34 : if (cia.ncand == 0 || cib.ncand == 0) {
197 7 : bn = BATdense(0, 0, 0);
198 7 : goto doreturn;
199 : }
200 :
201 27 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
202 : /* both lists are dense */
203 9 : bn = newdensecand(MAX(cia.seq, cib.seq), MIN(cia.seq + cia.ncand, cib.seq + cib.ncand));
204 9 : goto doreturn;
205 : }
206 :
207 18 : bn = COLnew(0, TYPE_oid, MIN(cia.ncand, cib.ncand), TRANSIENT);
208 18 : if (bn == NULL)
209 0 : goto doreturn;
210 18 : p = (oid *) Tloc(bn, 0);
211 18 : if (cia.tpe == cand_dense || cib.tpe == cand_dense) {
212 18 : if (cib.tpe == cand_dense) {
213 18 : struct canditer ci;
214 18 : ci = cia;
215 18 : cia = cib;
216 18 : cib = ci;
217 : }
218 : /* only cia is dense */
219 :
220 : /* search for first value in cib that is contained in cia */
221 18 : canditer_setidx(&cib, canditer_search(&cib, cia.seq, true));
222 18 : oid bo;
223 62 : while (!is_oid_nil(bo = canditer_next(&cib)) && bo < cia.seq + cia.ncand)
224 44 : *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 18 : BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
244 18 : bn->trevsorted = BATcount(bn) <= 1;
245 18 : bn->tsorted = true;
246 18 : bn->tkey = true;
247 18 : bn->tnil = false;
248 18 : bn->tnonil = true;
249 18 : bn = virtualize(bn);
250 34 : doreturn:
251 34 : 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 6127 : BATdiffcand(BAT *a, BAT *b)
260 : {
261 6127 : BAT *bn;
262 6127 : oid *restrict p;
263 6127 : struct canditer cia, cib;
264 :
265 6127 : BATcheck(a, NULL);
266 6127 : BATcheck(b, NULL);
267 :
268 6127 : canditer_init(&cia, NULL, a);
269 6127 : canditer_init(&cib, NULL, b);
270 :
271 6127 : if (cia.ncand == 0) {
272 0 : bn = BATdense(0, 0, 0);
273 0 : goto doreturn;
274 : }
275 6127 : if (cib.ncand == 0) {
276 459 : bn = canditer_slice(&cia, 0, cia.ncand);
277 459 : goto doreturn;
278 : }
279 :
280 5668 : 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 5668 : if (cia.tpe == cand_dense && cib.tpe == cand_dense) {
287 : /* both a and b are dense */
288 2129 : if (cia.seq < cib.seq) {
289 : /* a starts before b */
290 673 : if (cia.seq + cia.ncand <= cib.seq + cib.ncand) {
291 : /* b overlaps with end of a */
292 95 : bn = canditer_slice(&cia, 0, cib.seq - cia.seq);
293 95 : goto doreturn;
294 : }
295 : /* b is subset of a */
296 578 : bn = canditer_slice2(&cia, 0, cib.seq - cia.seq,
297 : cib.seq + cib.ncand - cia.seq,
298 : cia.ncand);
299 578 : goto doreturn;
300 : } else {
301 : /* cia.seq >= cib.seq */
302 1456 : if (cia.seq + cia.ncand > cib.seq + cib.ncand) {
303 : /* b overlaps with beginning of a */
304 72 : bn = canditer_slice(&cia, cib.seq + cib.ncand - cia.seq, cia.ncand);
305 72 : goto doreturn;
306 : }
307 : /* a is subset f b */
308 1384 : bn = BATdense(0, 0, 0);
309 1384 : goto doreturn;
310 : }
311 : }
312 3539 : 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 2482 : bn = canditer_slice2val(&cia, oid_nil, cib.seq,
317 : cib.seq + cib.ncand, oid_nil);
318 2482 : goto doreturn;
319 : }
320 :
321 : /* b is not dense */
322 1057 : bn = COLnew(0, TYPE_oid, BATcount(a), TRANSIENT);
323 1057 : if (bn == NULL)
324 0 : goto doreturn;
325 1057 : p = Tloc(bn, 0);
326 : /* find first position in b that is in range of a */
327 1057 : 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 1057 : oid ob = canditer_next(&cib);
332 7412460 : for (BUN i = 0; i < cia.ncand; i++) {
333 7411404 : oid oa = canditer_next(&cia);
334 9965647 : while (!is_oid_nil(ob) && ob < oa) {
335 2553907 : ob = canditer_next(&cib);
336 : }
337 7411403 : if (is_oid_nil(ob) || oa < ob)
338 4861146 : *p++ = oa;
339 : }
340 : }
341 :
342 : /* properties */
343 1056 : BATsetcount(bn, (BUN) (p - (oid *) Tloc(bn, 0)));
344 1056 : bn->trevsorted = BATcount(bn) <= 1;
345 1056 : bn->tsorted = true;
346 1056 : bn->tkey = true;
347 1056 : bn->tnil = false;
348 1056 : bn->tnonil = true;
349 1056 : bn = virtualize(bn);
350 6127 : doreturn:
351 6127 : 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 937214 : binsearchcand(const oid *cand, BUN hi, oid o)
359 : {
360 937214 : BUN lo = 0;
361 :
362 937214 : if (o <= cand[lo])
363 : return 0;
364 463876 : if (o > cand[hi])
365 410798 : return hi + 1;
366 : /* loop invariant: cand[lo] < o <= cand[hi] */
367 291158 : while (hi > lo + 1) {
368 259678 : BUN mid = (lo + hi) / 2;
369 259678 : if (cand[mid] == o)
370 21598 : return mid;
371 238080 : if (cand[mid] < o)
372 : lo = mid;
373 : else
374 167168 : 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 24076 : count_mask_bits(const struct canditer *ci, BUN lo, BUN hi)
383 : {
384 24076 : BUN n;
385 24076 : assert(lo <= hi);
386 24076 : assert(ci->tpe == cand_mask);
387 24076 : if (lo == hi)
388 : return 0;
389 24076 : lo += ci->firstbit;
390 24076 : hi += ci->firstbit;
391 24076 : BUN loi = lo / 32;
392 24076 : BUN hii = hi / 32;
393 24076 : lo %= 32;
394 24076 : hi %= 32;
395 24076 : if (loi == hii)
396 1107 : return (BUN) candmask_pop((ci->mask[loi] & ((1U << hi) - 1)) >> lo);
397 22969 : n = (BUN) candmask_pop(ci->mask[loi++] >> lo);
398 2317548 : while (loi < hii)
399 2294579 : n += (BUN) candmask_pop(ci->mask[loi++]);
400 22969 : if (hi != 0)
401 7218 : n += (BUN) candmask_pop(ci->mask[loi] & ((1U << hi) - 1));
402 : return n;
403 : }
404 :
405 : /* initialize a candidate iterator */
406 : void
407 8158294 : canditer_init(struct canditer *ci, BAT *b, BAT *s)
408 : {
409 8158294 : assert(ci != NULL);
410 8158294 : BUN batcount = 0;
411 8158294 : oid hseq = 0;
412 8158294 : if (b) {
413 7489500 : MT_lock_set(&b->theaplock);
414 7487523 : batcount = BATcount(b);
415 7487523 : hseq = b->hseqbase;
416 7487523 : MT_lock_unset(&b->theaplock);
417 : }
418 :
419 8157550 : if (s == NULL) {
420 3985105 : 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 3985105 : *ci = (struct canditer) {
429 : .tpe = cand_dense,
430 : .seq = hseq,
431 : .hseq = hseq,
432 : .ncand = batcount,
433 : };
434 3985105 : return;
435 : }
436 :
437 4172445 : assert(ATOMtype(s->ttype) == TYPE_oid || s->ttype == TYPE_msk);
438 4172445 : assert(s->ttype == TYPE_msk|| s->tsorted);
439 4172445 : assert(s->ttype == TYPE_msk|| s->tkey);
440 4172445 : assert(s->ttype == TYPE_msk|| s->tnonil);
441 4172445 : assert(s->ttype == TYPE_void || s->tvheap == NULL);
442 :
443 4172445 : BUN cnt = BATcount(s);
444 :
445 4172445 : if (cnt == 0 || (b != NULL && batcount == 0)) {
446 : /* candidate list for empty BAT or empty candidate list */
447 998167 : *ci = (struct canditer) {
448 : .tpe = cand_dense,
449 998167 : .hseq = s->hseqbase,
450 : .s = s,
451 : };
452 998167 : return;
453 : }
454 :
455 3174278 : *ci = (struct canditer) {
456 3174278 : .seq = s->tseqbase,
457 3174278 : .hseq = s->hseqbase,
458 : .s = s,
459 : };
460 :
461 3174278 : if (mask_cand(s)) {
462 24077 : ci->tpe = cand_mask;
463 24077 : ci->mask = (const uint32_t *) ccand_first(s);
464 24077 : ci->seq = s->tseqbase - (oid) CCAND(s)->firstbit;
465 24077 : ci->hseq = s->hseqbase;
466 24077 : ci->nvals = ccand_free(s) / sizeof(uint32_t);
467 24077 : cnt = ci->nvals * 32;
468 3150201 : } 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 3150201 : } else if (s->ttype == TYPE_void) {
475 2604634 : assert(!is_oid_nil(ci->seq));
476 2604634 : if (s->tvheap) {
477 78234 : assert(ccand_free(s) % SIZEOF_OID == 0);
478 78234 : ci->nvals = ccand_free(s) / SIZEOF_OID;
479 78234 : if (ci->nvals > 0) {
480 78234 : ci->tpe = cand_except;
481 78234 : 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 545567 : } else if (is_oid_nil(ci->seq)) {
490 509615 : ci->tpe = cand_materialized;
491 509615 : ci->oids = (const oid *) Tloc(s, 0);
492 509615 : ci->seq = ci->oids[0];
493 509615 : ci->nvals = cnt;
494 : } else {
495 : /* materialized dense: no exceptions */
496 : ci->tpe = cand_dense;
497 : }
498 3174278 : switch (ci->tpe) {
499 509598 : case cand_materialized:
500 509598 : if (b != NULL) {
501 391305 : BUN p = binsearchcand(ci->oids, cnt - 1U, hseq);
502 : /* p == cnt means candidate list is completely
503 : * before b */
504 391306 : ci->offset = p;
505 391306 : ci->oids += p;
506 391306 : cnt -= p;
507 391306 : if (cnt > 0) {
508 391306 : cnt = binsearchcand(ci->oids, cnt - 1U,
509 : hseq + batcount);
510 : /* cnt == 0 means candidate list is
511 : * completely after b */
512 : }
513 391305 : if (cnt == 0) {
514 : /* no overlap */
515 0 : *ci = (struct canditer) {
516 : .tpe = cand_dense,
517 : .s = s,
518 : };
519 0 : return;
520 : }
521 391305 : ci->seq = ci->oids[0];
522 391305 : ci->nvals = cnt;
523 391305 : if (ci->oids[cnt - 1U] - ci->seq == cnt - 1U) {
524 : /* actually dense */
525 57 : ci->tpe = cand_dense;
526 57 : ci->oids = NULL;
527 57 : ci->nvals = 0;
528 : }
529 : }
530 : break;
531 78233 : case cand_except:
532 : /* exceptions must all be within range of s */
533 78233 : assert(ci->oids[0] >= ci->seq);
534 78233 : assert(ci->oids[ci->nvals - 1U] < ci->seq + cnt + ci->nvals);
535 : /* prune exceptions at either end of range of s */
536 3588166 : while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
537 3509933 : ci->nvals--;
538 3509933 : ci->oids++;
539 3509933 : ci->seq++;
540 : }
541 78431 : while (ci->nvals > 0 &&
542 75350 : ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
543 198 : ci->nvals--;
544 78233 : if (b != NULL) {
545 73311 : if (ci->seq + cnt + ci->nvals <= hseq ||
546 73311 : 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 78233 : if (ci->nvals > 0) {
556 75151 : if (b == NULL)
557 : break;
558 70633 : BUN p;
559 70633 : p = binsearchcand(ci->oids, ci->nvals - 1U, hseq);
560 70633 : 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 70633 : assert(hseq > ci->seq || p == 0);
571 70633 : 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 70633 : 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 70633 : while (ci->nvals > 0 && ci->oids[0] == ci->seq) {
588 0 : ci->nvals--;
589 0 : ci->oids++;
590 0 : ci->seq++;
591 : }
592 70633 : while (ci->nvals > 0 &&
593 70633 : ci->oids[ci->nvals - 1U] == ci->seq + cnt + ci->nvals - 1U)
594 0 : ci->nvals--;
595 70633 : if (ci->nvals > 0)
596 : break;
597 : }
598 3082 : ci->tpe = cand_dense;
599 3082 : ci->oids = NULL;
600 : /* fall through */
601 2565454 : case cand_dense:
602 2565454 : if (b != NULL) {
603 2239031 : if (ci->seq + cnt <= hseq ||
604 2239031 : 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 2239031 : if (hseq > ci->seq) {
613 0 : cnt -= hseq - ci->seq;
614 0 : ci->offset += hseq - ci->seq;
615 0 : ci->seq = hseq;
616 : }
617 2239031 : if (ci->seq + cnt > hseq + batcount)
618 0 : cnt = hseq + batcount - ci->seq;
619 : }
620 : break;
621 24075 : case cand_mask:
622 24075 : assert(s->tseqbase != oid_nil);
623 24075 : if (b != NULL) {
624 8787 : if (ci->seq + cnt <= hseq ||
625 8787 : 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 8787 : 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 8787 : if (ci->seq + cnt > hseq + batcount) {
641 8523 : cnt = hseq + batcount - ci->seq;
642 : }
643 8787 : 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 24075 : 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 24075 : if (ci->firstbit == 0) {
660 63663 : while (cnt >= 32U && ci->mask[0] == 0) {
661 39586 : cnt -= 32U;
662 39586 : ci->mask++;
663 39586 : ci->nvals--;
664 : }
665 : }
666 : /* check whether there are any 1 bits in the last word */
667 24075 : if (cnt == 0 ||
668 24075 : (cnt < 32U - ci->firstbit &&
669 1107 : ((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 24075 : int i = candmask_lobit(ci->mask[0] >> ci->firstbit);
681 24075 : assert(i >= 0); /* there should be a set bit */
682 24075 : ci->firstbit += i;
683 24075 : cnt -= i;
684 24075 : if (mask_cand(s))
685 24076 : 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 24075 : ci->seq = ci->mskoff + ci->firstbit;
689 24075 : ci->nextbit = ci->firstbit;
690 : /* at this point we know that bit ci->firstbit is set
691 : * in ci->mask[0] */
692 24075 : ci->lastbit = (ci->firstbit + cnt - 1U) % 32U + 1U;
693 24075 : if (ci->lastbit < 32 &&
694 8522 : (ci->mask[ci->nvals - 1] & ((1U << ci->lastbit) - 1)) == 0) {
695 : /* last partial word is all zero */
696 198 : cnt -= ci->lastbit;
697 198 : ci->lastbit = 32;
698 198 : ci->nvals--;
699 : }
700 24075 : if (ci->lastbit == 32) {
701 : /* "remove" zero words at the end */
702 24004 : while (cnt >= 32 && ci->mask[ci->nvals - 1] == 0) {
703 8253 : ci->nvals--;
704 8253 : cnt -= 32;
705 : }
706 : }
707 24075 : ci->ncand = count_mask_bits(ci, 0, cnt);
708 24076 : return;
709 : default:
710 0 : MT_UNREACHABLE();
711 : }
712 3150203 : ci->ncand = cnt;
713 3150203 : ci->hseq += ci->offset;
714 : }
715 :
716 : /* return the next candidate without advancing */
717 : oid
718 2541226 : canditer_peek(const struct canditer *ci)
719 : {
720 2541226 : oid o = oid_nil;
721 2541226 : if (ci->next == ci->ncand)
722 6410 : return oid_nil;
723 2534816 : switch (ci->tpe) {
724 2269873 : case cand_dense:
725 2269873 : o = ci->seq + ci->next;
726 2269873 : break;
727 254625 : case cand_materialized:
728 254625 : assert(ci->next < ci->nvals);
729 254625 : o = ci->oids[ci->next];
730 254625 : break;
731 10318 : case cand_except:
732 10318 : o = ci->seq + ci->add + ci->next;
733 10504 : for (oid a = ci->add; a < ci->nvals && o == ci->oids[a]; a++)
734 186 : o++;
735 : break;
736 0 : case cand_mask: {
737 0 : BUN m = ci->nextmsk;
738 0 : uint8_t b = ci->nextbit;
739 0 : while ((ci->mask[m] >> b) == 0) {
740 0 : m++;
741 0 : b = 0;
742 : }
743 0 : b += candmask_lobit(ci->mask[m] >> b);
744 0 : o = ci->mskoff + m * 32 + b;
745 0 : break;
746 : }
747 : default:
748 0 : MT_UNREACHABLE();
749 : }
750 : return o;
751 : }
752 :
753 : /* return the previous candidate */
754 : oid
755 893 : canditer_prev(struct canditer *ci)
756 : {
757 893 : if (ci->next == 0)
758 0 : return oid_nil;
759 893 : switch (ci->tpe) {
760 893 : case cand_dense:
761 893 : return ci->seq + --ci->next;
762 0 : case cand_materialized:
763 0 : return ci->oids[--ci->next];
764 : case cand_except:
765 0 : break;
766 0 : case cand_mask:
767 0 : for (;;) {
768 0 : if (ci->nextbit == 0) {
769 0 : ci->nextbit = 32;
770 0 : while (ci->mask[--ci->nextmsk] == 0)
771 : ;
772 : }
773 0 : if (ci->mask[ci->nextmsk] & (1U << --ci->nextbit))
774 : break;
775 : }
776 0 : ci->next--;
777 0 : return ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
778 : default:
779 0 : MT_UNREACHABLE();
780 : }
781 0 : oid o = ci->seq + ci->add + --ci->next;
782 0 : while (ci->add > 0 && o == ci->oids[ci->add - 1]) {
783 0 : ci->add--;
784 0 : o--;
785 : }
786 : return o;
787 : }
788 :
789 : /* return the previous candidate without retreating */
790 : oid
791 3104 : canditer_peekprev(const struct canditer *ci)
792 : {
793 3104 : oid o = oid_nil;
794 :
795 3104 : if (ci->next == 0)
796 0 : return oid_nil;
797 3104 : switch (ci->tpe) {
798 3104 : case cand_dense:
799 3104 : return ci->seq + ci->next - 1;
800 0 : case cand_materialized:
801 0 : return ci->oids[ci->next - 1];
802 0 : case cand_except:
803 0 : o = ci->seq + ci->add + ci->next - 1;
804 0 : for (oid a = ci->add; a > 0 && o == ci->oids[a - 1]; a--)
805 0 : o--;
806 : break;
807 0 : case cand_mask: {
808 0 : BUN m = ci->nextmsk;
809 0 : uint8_t b = ci->nextbit;
810 0 : do {
811 0 : if (b == 0) {
812 0 : b = 32;
813 0 : while (ci->mask[--m] == 0)
814 : ;
815 : }
816 0 : } while ((ci->mask[m] & (1U << --b)) == 0);
817 0 : o = ci->mskoff + m * 32 + b;
818 0 : if (++b == 32) {
819 : b = 0;
820 : m++;
821 : }
822 : break;
823 : }
824 : default:
825 0 : MT_UNREACHABLE();
826 : }
827 : return o;
828 : }
829 :
830 : /* if o is a candidate, return it, else return the next candidate from
831 : * the cand_mask iterator ci after (if next is set) or before (if next
832 : * is unset) o; if there are no more candidates, return oid_nil */
833 : oid
834 0 : canditer_mask_next(const struct canditer *ci, oid o, bool next)
835 : {
836 0 : if (o < ci->mskoff)
837 0 : return next ? ci->mskoff + ci->firstbit : oid_nil;
838 0 : o -= ci->mskoff;
839 0 : BUN p = o / 32;
840 0 : o %= 32;
841 0 : if (p >= ci->nvals || (p == ci->nvals - 1 && o >= ci->lastbit))
842 0 : return next ? oid_nil : canditer_last(ci);
843 0 : if (next) {
844 0 : while ((ci->mask[p] & (1U << o)) == 0) {
845 0 : if (++o == 32) {
846 0 : o = 0;
847 0 : if (++p == ci->nvals)
848 0 : return oid_nil;
849 : }
850 : }
851 0 : if (p == ci->nvals - 1 && o >= ci->lastbit)
852 0 : return oid_nil;
853 : } else {
854 0 : while ((ci->mask[p] & (1U << o)) == 0) {
855 0 : if (o == 0) {
856 0 : o = 31;
857 0 : if (p == 0)
858 0 : return oid_nil;
859 0 : p--;
860 : } else {
861 0 : o--;
862 : }
863 : }
864 0 : if (p == 0 && o < ci->firstbit)
865 0 : return oid_nil;
866 : }
867 0 : return ci->mskoff + 32 * p + o;
868 : }
869 :
870 : /* return the last candidate */
871 : oid
872 247704 : canditer_last(const struct canditer *ci)
873 : {
874 247704 : if (ci->ncand == 0)
875 0 : return oid_nil;
876 247704 : switch (ci->tpe) {
877 220049 : case cand_dense:
878 220049 : return ci->seq + ci->ncand - 1;
879 22255 : case cand_materialized:
880 22255 : return ci->oids[ci->ncand - 1];
881 4723 : case cand_except:
882 4723 : return ci->seq + ci->ncand + ci->nvals - 1;
883 677 : case cand_mask:
884 9911 : for (uint8_t i = ci->lastbit; i > 0; ) {
885 9911 : if (ci->mask[ci->nvals - 1] & (1U << --i))
886 677 : return ci->mskoff + (ci->nvals - 1) * 32 + i;
887 : }
888 0 : break; /* cannot happen */
889 : default:
890 0 : MT_UNREACHABLE();
891 : }
892 0 : return oid_nil; /* cannot happen */
893 : }
894 :
895 : /* return the candidate at the given index */
896 : oid
897 336898252 : canditer_idx(const struct canditer *ci, BUN p)
898 : {
899 336898252 : if (p >= ci->ncand)
900 0 : return oid_nil;
901 336898252 : switch (ci->tpe) {
902 172754769 : case cand_dense:
903 172754769 : return ci->seq + p;
904 163922045 : case cand_materialized:
905 163922045 : return ci->oids[p];
906 221360 : case cand_except: {
907 221360 : oid o = ci->seq + p;
908 221360 : if (o < ci->oids[0])
909 : return o;
910 161810 : if (o + ci->nvals > ci->oids[ci->nvals - 1])
911 : return o + ci->nvals;
912 85691 : BUN lo = 0, hi = ci->nvals - 1;
913 587300 : while (hi - lo > 1) {
914 415918 : BUN mid = (hi + lo) / 2;
915 415918 : if (ci->oids[mid] - mid > o)
916 : hi = mid;
917 : else
918 274802 : lo = mid;
919 : }
920 85691 : return o + hi;
921 : }
922 78 : case cand_mask: {
923 78 : BUN x;
924 78 : if ((x = candmask_pop(ci->mask[0] >> ci->firstbit)) > p) {
925 26 : for (uint8_t i = ci->firstbit; ; i++) {
926 104 : if (ci->mask[0] & (1U << i)) {
927 104 : if (p == 0)
928 78 : return ci->mskoff + i;
929 26 : p--;
930 : }
931 : }
932 : }
933 0 : for (BUN n = 1; n < ci->nvals; n++) {
934 0 : uint32_t mask = ci->mask[n];
935 0 : p -= x;
936 0 : x = candmask_pop(mask);
937 0 : if (x > p) {
938 0 : for (uint8_t i = 0; ; i++) {
939 0 : if (mask & (1U << i)) {
940 0 : if (p == 0)
941 0 : return ci->mskoff + n * 32 + i;
942 0 : p--;
943 : }
944 : }
945 : }
946 : }
947 0 : break; /* cannot happen */
948 : }
949 : default:
950 0 : MT_UNREACHABLE();
951 : }
952 0 : return oid_nil; /* cannot happen */
953 : }
954 :
955 : /* set the index for the next candidate to be returned */
956 : void
957 634940 : canditer_setidx(struct canditer *ci, BUN p)
958 : {
959 634940 : if (p != ci->next) {
960 597943 : if (p >= ci->ncand) {
961 53005 : ci->next = ci->ncand;
962 53005 : switch (ci->tpe) {
963 0 : case cand_except:
964 0 : ci->add = ci->nvals;
965 0 : break;
966 0 : case cand_mask:
967 0 : ci->nextbit = ci->lastbit;
968 0 : ci->nextmsk = ci->nvals;
969 0 : if (ci->nextbit == 32)
970 0 : ci->nextbit = 0;
971 : else
972 0 : ci->nextmsk--;
973 : break;
974 : default:
975 : break;
976 : }
977 : } else {
978 544938 : ci->next = p;
979 544938 : switch (ci->tpe) {
980 7150 : case cand_except:
981 7150 : ci->add = canditer_idx(ci, p) - ci->seq - p;
982 7150 : break;
983 0 : case cand_mask: {
984 0 : oid o = canditer_idx(ci, p) - ci->mskoff;
985 0 : ci->nextmsk = o / 32;
986 0 : ci->nextbit = (uint8_t) (o % 32);
987 0 : break;
988 : }
989 : default:
990 : break;
991 : }
992 : }
993 : }
994 634940 : }
995 :
996 : /* reset */
997 : void
998 684675 : canditer_reset(struct canditer *ci)
999 : {
1000 684675 : if (ci->tpe == cand_mask) {
1001 0 : ci->nextbit = ci->firstbit;
1002 0 : ci->nextmsk = 0;
1003 : } else {
1004 684675 : ci->add = 0;
1005 : }
1006 684675 : ci->next = 0;
1007 684675 : }
1008 :
1009 : /* return index of given candidate if it occurs; if the candidate does
1010 : * not occur, if next is set, return index of next larger candidate,
1011 : * if next is not set, return BUN_NONE */
1012 : BUN
1013 1050657 : canditer_search(const struct canditer *ci, oid o, bool next)
1014 : {
1015 1050657 : BUN p;
1016 :
1017 1050657 : switch (ci->tpe) {
1018 965757 : case cand_dense:
1019 965757 : if (o < ci->seq)
1020 630 : return next ? 0 : BUN_NONE;
1021 965127 : if (o >= ci->seq + ci->ncand)
1022 127348 : return next ? ci->ncand : BUN_NONE;
1023 837779 : return o - ci->seq;
1024 54518 : case cand_materialized:
1025 54518 : if (ci->nvals == 0)
1026 : return 0;
1027 54519 : p = binsearchcand(ci->oids, ci->nvals - 1, o);
1028 54515 : if (next || (p != ci->nvals && ci->oids[p] == o))
1029 54271 : return p;
1030 : break;
1031 30382 : case cand_except:
1032 30382 : if (o < ci->seq)
1033 0 : return next ? 0 : BUN_NONE;
1034 30382 : if (o >= ci->seq + ci->ncand + ci->nvals)
1035 928 : return next ? ci->ncand : BUN_NONE;
1036 29454 : p = binsearchcand(ci->oids, ci->nvals - 1, o);
1037 29454 : if (next || p == ci->nvals || ci->oids[p] != o)
1038 29299 : return o - ci->seq - p;
1039 : break;
1040 0 : case cand_mask:
1041 0 : if (o < ci->mskoff) {
1042 0 : return next ? 0 : BUN_NONE;
1043 : }
1044 0 : o -= ci->mskoff;
1045 0 : p = o / 32;
1046 0 : if (p >= ci->nvals)
1047 0 : return next ? ci->ncand : BUN_NONE;
1048 0 : o %= 32;
1049 0 : if (p == ci->nvals - 1 && o >= ci->lastbit)
1050 0 : return next ? ci->ncand : BUN_NONE;
1051 0 : if (next || ci->mask[p] & (1U << o))
1052 0 : return count_mask_bits(ci, 0, p * 32 + o) + !(ci->mask[p] & (1U << o));
1053 : break;
1054 : default:
1055 0 : MT_UNREACHABLE();
1056 : }
1057 : return BUN_NONE;
1058 : }
1059 :
1060 : static BAT *
1061 844 : canditer_sliceval_mask(const struct canditer *ci, oid lo1, oid hi1, BUN cnt1,
1062 : oid lo2, oid hi2, BUN cnt2)
1063 : {
1064 844 : assert(cnt2 == 0 || !is_oid_nil(lo2));
1065 844 : assert(cnt2 == 0 || lo2 >= hi1);
1066 844 : if (is_oid_nil(lo1) || lo1 < ci->mskoff + ci->firstbit)
1067 182 : lo1 = ci->mskoff + ci->firstbit;
1068 844 : if (is_oid_nil(hi1) || hi1 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
1069 663 : hi1 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
1070 :
1071 844 : BAT *bn = COLnew(0, TYPE_oid, cnt1 + cnt2, TRANSIENT);
1072 844 : if (bn == NULL)
1073 : return NULL;
1074 844 : bn->tkey = true;
1075 :
1076 844 : if (hi1 > ci->mskoff) {
1077 690 : if (lo1 < ci->mskoff)
1078 : lo1 = 0;
1079 : else
1080 690 : lo1 -= ci->mskoff;
1081 690 : hi1 -= ci->mskoff;
1082 169094 : for (oid o = lo1; o < hi1 && cnt1 > 0; o++) {
1083 168404 : if (ci->mask[o / 32] & (1U << (o % 32))) {
1084 136253 : if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
1085 0 : BBPreclaim(bn);
1086 0 : return NULL;
1087 : }
1088 136253 : cnt1--;
1089 : }
1090 : }
1091 : }
1092 844 : if (cnt2 > 0) {
1093 36 : if (lo2 < ci->mskoff + ci->firstbit)
1094 : lo2 = ci->mskoff + ci->firstbit;
1095 36 : if (is_oid_nil(hi2) || hi2 >= ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit)
1096 36 : hi2 = ci->mskoff + (ci->nvals - 1) * 32 + ci->lastbit;
1097 :
1098 36 : lo2 -= ci->mskoff;
1099 36 : hi2 -= ci->mskoff;
1100 210 : for (oid o = lo2; o < hi2 && cnt2 > 0; o++) {
1101 174 : if (ci->mask[o / 32] & (1U << (o % 32))) {
1102 148 : if (BUNappend(bn, &(oid){o + ci->mskoff}, false) != GDK_SUCCEED) {
1103 0 : BBPreclaim(bn);
1104 0 : return NULL;
1105 : }
1106 148 : cnt2--;
1107 : }
1108 : }
1109 : }
1110 : return bn;
1111 : }
1112 :
1113 : /* return either an actual BATslice or a new BAT that contains the
1114 : * "virtual" slice of the input candidate list BAT; except, unlike
1115 : * BATslice, the hseqbase of the returned BAT is 0; note for cand_mask
1116 : * candidate iterators, the BUN values refer to number of 1 bits */
1117 : BAT *
1118 450202 : canditer_slice(const struct canditer *ci, BUN lo, BUN hi)
1119 : {
1120 450202 : BAT *bn;
1121 450202 : oid o;
1122 450202 : BUN add;
1123 :
1124 450202 : assert(ci != NULL);
1125 :
1126 450202 : if (lo >= ci->ncand || lo >= hi)
1127 67235 : return BATdense(0, 0, 0);
1128 382967 : if (hi > ci->ncand)
1129 : hi = ci->ncand;
1130 382967 : if (hi - lo == 1)
1131 326590 : return BATdense(0, canditer_idx(ci, lo), 1);
1132 56377 : switch (ci->tpe) {
1133 5524 : case cand_materialized:
1134 5524 : if (ci->s) {
1135 5524 : bn = BATslice(ci->s, lo + ci->offset, hi + ci->offset);
1136 5524 : BAThseqbase(bn, 0);
1137 5524 : return bn;
1138 : }
1139 0 : bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
1140 0 : if (bn == NULL)
1141 : return NULL;
1142 0 : BATsetcount(bn, hi - lo);
1143 0 : memcpy(Tloc(bn, 0), ci->oids + lo, (hi - lo) * sizeof(oid));
1144 0 : break;
1145 50563 : case cand_dense:
1146 50563 : return BATdense(0, ci->seq + lo, hi - lo);
1147 287 : case cand_except:
1148 287 : o = canditer_idx(ci, lo);
1149 287 : add = o - ci->seq - lo;
1150 287 : assert(add <= ci->nvals);
1151 287 : if (add == ci->nvals || o + hi - lo < ci->oids[add]) {
1152 : /* after last exception or before next
1153 : * exception: return dense sequence */
1154 243 : return BATdense(0, o, hi - lo);
1155 : }
1156 44 : bn = COLnew(0, TYPE_oid, hi - lo, TRANSIENT);
1157 44 : if (bn == NULL)
1158 : return NULL;
1159 44 : BATsetcount(bn, hi - lo);
1160 392 : for (oid *dst = Tloc(bn, 0); lo < hi; lo++) {
1161 501 : while (add < ci->nvals && o == ci->oids[add]) {
1162 153 : o++;
1163 153 : add++;
1164 : }
1165 348 : *dst++ = o++;
1166 : }
1167 : break;
1168 3 : case cand_mask:
1169 3 : return canditer_sliceval_mask(ci, canditer_idx(ci, lo),
1170 : oid_nil, hi - lo,
1171 : oid_nil, oid_nil, 0);
1172 : default:
1173 0 : MT_UNREACHABLE();
1174 : }
1175 44 : bn->tsorted = true;
1176 44 : bn->trevsorted = BATcount(bn) <= 1;
1177 44 : bn->tkey = true;
1178 44 : bn->tseqbase = oid_nil;
1179 44 : bn->tnil = false;
1180 44 : bn->tnonil = true;
1181 44 : bn->tminpos = 0;
1182 44 : bn->tmaxpos = BATcount(bn) - 1;
1183 44 : return virtualize(bn);
1184 : }
1185 :
1186 : /* like the above, except the bounds are given by values instead of
1187 : * indexes */
1188 : BAT *
1189 326903 : canditer_sliceval(const struct canditer *ci, oid lo, oid hi)
1190 : {
1191 326903 : if (ci->tpe != cand_mask) {
1192 978298 : return canditer_slice(
1193 : ci,
1194 326102 : is_oid_nil(lo) ? 0 : canditer_search(ci, lo, true),
1195 326098 : is_oid_nil(hi) ? ci->ncand : canditer_search(ci, hi, true));
1196 : }
1197 :
1198 805 : return canditer_sliceval_mask(ci, lo, hi, ci->ncand,
1199 : oid_nil, oid_nil, 0);
1200 : }
1201 :
1202 : /* return the combination of two slices */
1203 : BAT *
1204 32261 : canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2)
1205 : {
1206 32261 : BAT *bn;
1207 32261 : oid o;
1208 32261 : BUN add;
1209 :
1210 32261 : assert(lo1 <= hi1);
1211 32261 : assert(lo2 <= hi2);
1212 32261 : assert(hi1 <= lo2 || (lo2 == 0 && hi2 == 0));
1213 :
1214 32261 : if (hi1 == lo2) /* consecutive slices: combine into one */
1215 596 : return canditer_slice(ci, lo1, hi2);
1216 31665 : if (lo2 == hi2 || hi1 >= ci->ncand || lo2 >= ci->ncand) {
1217 : /* empty second slice */
1218 24597 : return canditer_slice(ci, lo1, hi1);
1219 : }
1220 7068 : if (lo1 == hi1) /* empty first slice */
1221 1989 : return canditer_slice(ci, lo2, hi2);
1222 5079 : if (lo1 >= ci->ncand) /* out of range */
1223 : return BATdense(0, 0, 0);
1224 :
1225 5079 : if (hi2 >= ci->ncand)
1226 : hi2 = ci->ncand;
1227 :
1228 5079 : bn = COLnew(0, TYPE_oid, hi1 - lo1 + hi2 - lo2, TRANSIENT);
1229 5079 : if (bn == NULL)
1230 : return NULL;
1231 5079 : BATsetcount(bn, hi1 - lo1 + hi2 - lo2);
1232 5079 : bn->tsorted = true;
1233 5079 : bn->trevsorted = BATcount(bn) <= 1;
1234 5079 : bn->tkey = true;
1235 5079 : bn->tseqbase = oid_nil;
1236 5079 : bn->tnil = false;
1237 5079 : bn->tnonil = true;
1238 :
1239 5079 : oid *dst = Tloc(bn, 0);
1240 :
1241 5079 : switch (ci->tpe) {
1242 2426 : case cand_materialized:
1243 2426 : memcpy(dst, ci->oids + lo1, (hi1 - lo1) * sizeof(oid));
1244 2426 : memcpy(dst + hi1 - lo1, ci->oids + lo2, (hi2 - lo2) * sizeof(oid));
1245 2426 : break;
1246 : case cand_dense:
1247 948474 : while (lo1 < hi1)
1248 945822 : *dst++ = ci->seq + lo1++;
1249 289307 : while (lo2 < hi2)
1250 286655 : *dst++ = ci->seq + lo2++;
1251 : break;
1252 1 : case cand_except:
1253 1 : o = canditer_idx(ci, lo1);
1254 1 : add = o - ci->seq - lo1;
1255 1 : assert(add <= ci->nvals);
1256 1 : if (add == ci->nvals) {
1257 : /* after last exception: return dense sequence */
1258 0 : while (lo1 < hi1)
1259 0 : *dst++ = ci->seq + add + lo1++;
1260 : } else {
1261 2 : while (lo1 < hi1) {
1262 1 : while (add < ci->nvals && o == ci->oids[add]) {
1263 0 : o++;
1264 0 : add++;
1265 : }
1266 1 : *dst++ = o++;
1267 1 : lo1++;
1268 : }
1269 : }
1270 1 : o = canditer_idx(ci, lo2);
1271 1 : add = o - ci->seq - lo2;
1272 1 : assert(add <= ci->nvals);
1273 1 : if (add == ci->nvals) {
1274 : /* after last exception: return dense sequence */
1275 0 : while (lo2 < hi2)
1276 0 : *dst++ = ci->seq + add + lo2++;
1277 : } else {
1278 4 : while (lo2 < hi2) {
1279 6 : while (add < ci->nvals && o == ci->oids[add]) {
1280 3 : o++;
1281 3 : add++;
1282 : }
1283 3 : *dst++ = o++;
1284 3 : lo2++;
1285 : }
1286 : }
1287 : break;
1288 0 : case cand_mask:
1289 0 : return canditer_sliceval_mask(ci, canditer_idx(ci, lo1),
1290 : oid_nil, hi1 - lo1,
1291 : canditer_idx(ci, lo2),
1292 : oid_nil, hi2 - lo2);
1293 : default:
1294 0 : MT_UNREACHABLE();
1295 : }
1296 5079 : return virtualize(bn);
1297 : }
1298 :
1299 : BAT *
1300 31719 : canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2)
1301 : {
1302 31719 : if (ci->tpe != cand_mask) {
1303 124252 : return canditer_slice2(
1304 : ci,
1305 28937 : is_oid_nil(lo1) ? 0 : canditer_search(ci, lo1, true),
1306 31683 : is_oid_nil(hi1) ? ci->ncand : canditer_search(ci, hi1, true),
1307 31683 : is_oid_nil(lo2) ? 0 : canditer_search(ci, lo2, true),
1308 266 : is_oid_nil(hi2) ? ci->ncand : canditer_search(ci, hi2, true));
1309 : }
1310 :
1311 36 : return canditer_sliceval_mask(ci, lo1, hi1, ci->ncand,
1312 36 : lo2, hi2, ci->ncand);
1313 : }
1314 :
1315 : BAT *
1316 3160 : BATnegcands(oid tseq, BUN nr, BAT *odels)
1317 : {
1318 3160 : const char *nme;
1319 3160 : Heap *dels;
1320 3160 : BUN lo, hi;
1321 3160 : ccand_t *c;
1322 3160 : BAT *bn;
1323 :
1324 3160 : bn = BATdense(0, tseq, nr);
1325 3160 : if (bn == NULL)
1326 : return NULL;
1327 3160 : if (BATcount(odels) == 0)
1328 2767 : goto doreturn;
1329 :
1330 393 : lo = SORTfndfirst(odels, &bn->tseqbase);
1331 393 : hi = SORTfndfirst(odels, &(oid) {bn->tseqbase + BATcount(bn)});
1332 393 : if (lo == hi)
1333 : return bn;
1334 393 : if (lo + nr == hi) {
1335 134 : BATsetcount(bn, 0);
1336 134 : goto doreturn;
1337 : }
1338 :
1339 259 : nme = BBP_physical(bn->batCacheid);
1340 259 : if ((dels = GDKmalloc(sizeof(Heap))) == NULL){
1341 0 : BBPreclaim(bn);
1342 0 : return NULL;
1343 : }
1344 518 : *dels = (Heap) {
1345 259 : .farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap),
1346 259 : .parentid = bn->batCacheid,
1347 : .dirty = true,
1348 : .refs = ATOMIC_VAR_INIT(1),
1349 : };
1350 259 : strconcat_len(dels->filename, sizeof(dels->filename),
1351 : nme, ".theap", NULL);
1352 :
1353 518 : if (dels->farmid < 0 ||
1354 259 : HEAPalloc(dels, hi - lo + (sizeof(ccand_t)/sizeof(oid)), sizeof(oid)) != GDK_SUCCEED) {
1355 0 : GDKfree(dels);
1356 0 : BBPreclaim(bn);
1357 0 : return NULL;
1358 : }
1359 259 : c = (ccand_t *) dels->base;
1360 259 : *c = (ccand_t) {
1361 : .type = CAND_NEGOID,
1362 : };
1363 259 : dels->free = sizeof(ccand_t) + sizeof(oid) * (hi - lo);
1364 259 : BATiter bi = bat_iterator(odels);
1365 259 : if (bi.type == TYPE_void) {
1366 141 : oid *r = (oid *) (dels->base + sizeof(ccand_t));
1367 93621 : for (BUN x = lo; x < hi; x++)
1368 93480 : r[x - lo] = x + odels->tseqbase;
1369 : } else {
1370 118 : oid *r = (oid *) (dels->base + sizeof(ccand_t));
1371 118 : memcpy(r, (const oid *) bi.base + lo, sizeof(oid) * (hi - lo));
1372 : }
1373 259 : bat_iterator_end(&bi);
1374 259 : assert(bn->tvheap == NULL);
1375 259 : bn->tvheap = dels;
1376 259 : BATsetcount(bn, bn->batCount - (hi - lo));
1377 3160 : doreturn:
1378 3160 : TRC_DEBUG(ALGO, "nr=" BUNFMT ", odels=" ALGOBATFMT
1379 : " -> " ALGOBATFMT "\n",
1380 : nr, ALGOBATPAR(odels),
1381 : ALGOBATPAR(bn));
1382 : return bn;
1383 : }
1384 :
1385 : BAT *
1386 108054 : BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected)
1387 : {
1388 108054 : const char *nme;
1389 108054 : Heap *msks;
1390 108054 : ccand_t *c;
1391 108054 : BUN nmask;
1392 108054 : BAT *bn;
1393 :
1394 108054 : assert(masked->ttype == TYPE_msk);
1395 :
1396 108054 : bn = COLnew(hseq, TYPE_void, 0, TRANSIENT);
1397 108054 : if (bn == NULL)
1398 : return NULL;
1399 108054 : BATtseqbase(bn, hseq);
1400 :
1401 108054 : if (BATcount(masked) == 0)
1402 : return bn;
1403 :
1404 108054 : nme = BBP_physical(bn->batCacheid);
1405 108054 : if ((msks = GDKmalloc(sizeof(Heap))) == NULL){
1406 0 : BBPreclaim(bn);
1407 0 : return NULL;
1408 : }
1409 216108 : *msks = (Heap) {
1410 108054 : .farmid = BBPselectfarm(bn->batRole, bn->ttype, varheap),
1411 108054 : .parentid = bn->batCacheid,
1412 : .dirty = true,
1413 : .refs = ATOMIC_VAR_INIT(1),
1414 : };
1415 108054 : strconcat_len(msks->filename, sizeof(msks->filename),
1416 : nme, ".theap", NULL);
1417 :
1418 108054 : nmask = (nr + 31) / 32;
1419 216107 : if (msks->farmid < 0 ||
1420 108054 : HEAPalloc(msks, nmask + (sizeof(ccand_t)/sizeof(uint32_t)), sizeof(uint32_t)) != GDK_SUCCEED) {
1421 0 : GDKfree(msks);
1422 0 : BBPreclaim(bn);
1423 0 : return NULL;
1424 : }
1425 108053 : c = (ccand_t *) msks->base;
1426 108053 : *c = (ccand_t) {
1427 : .type = CAND_MSK,
1428 : // .mask = true,
1429 : };
1430 108053 : msks->free = sizeof(ccand_t) + nmask * sizeof(uint32_t);
1431 108053 : uint32_t *r = (uint32_t*)(msks->base + sizeof(ccand_t));
1432 108053 : BATiter bi = bat_iterator(masked);
1433 108054 : if (selected) {
1434 108054 : if (nr <= bi.count)
1435 108054 : memcpy(r, bi.base, nmask * sizeof(uint32_t));
1436 : else
1437 0 : memcpy(r, bi.base, (bi.count + 31) / 32 * sizeof(uint32_t));
1438 : } else {
1439 0 : const uint32_t *s = (const uint32_t *) bi.base;
1440 0 : BUN nmask_ = (bi.count + 31) / 32;
1441 0 : for (BUN i = 0; i < nmask_; i++)
1442 0 : r[i] = ~s[i];
1443 : }
1444 108054 : if (nr > bi.count) {
1445 0 : BUN rest = bi.count & 31;
1446 0 : BUN nmask_ = (bi.count + 31) / 32;
1447 0 : if (rest > 0)
1448 0 : r[nmask_ -1] |= ((1U << (32 - rest)) - 1) << rest;
1449 0 : for (BUN j = nmask_; j < nmask; j++)
1450 0 : r[j] = ~0;
1451 : }
1452 108054 : bat_iterator_end(&bi);
1453 : /* make sure last word doesn't have any spurious bits set */
1454 108054 : BUN cnt = nr % 32;
1455 108054 : if (cnt > 0)
1456 106727 : r[nmask - 1] &= (1U << cnt) - 1;
1457 : cnt = 0;
1458 11917039 : for (BUN i = 0; i < nmask; i++) {
1459 11808985 : if (cnt == 0 && r[i] != 0)
1460 107702 : c->firstbit = candmask_lobit(r[i]) + i * 32;
1461 11808985 : cnt += candmask_pop(r[i]);
1462 : }
1463 108054 : if (cnt > 0) {
1464 107710 : assert(bn->tvheap == NULL);
1465 107710 : bn->tvheap = msks;
1466 107710 : bn->tseqbase += (oid) c->firstbit;
1467 : } else {
1468 : /* no point having a mask if it's empty */
1469 344 : HEAPfree(msks, true);
1470 344 : GDKfree(msks);
1471 : }
1472 108054 : BATsetcount(bn, cnt);
1473 108054 : TRC_DEBUG(ALGO, "hseq=" OIDFMT ", masked=" ALGOBATFMT ", selected=%s"
1474 : " -> " ALGOBATFMT "\n",
1475 : hseq, ALGOBATPAR(masked),
1476 : selected ? "true" : "false",
1477 : ALGOBATPAR(bn));
1478 108054 : assert(bn->tseqbase != oid_nil);
1479 : return bn;
1480 : }
1481 :
1482 : /* convert a masked candidate list to a positive or negative candidate list */
1483 : BAT *
1484 104049 : BATunmask(BAT *b)
1485 : {
1486 : // assert(!mask_cand(b) || CCAND(b)->mask); /* todo handle negmask case */
1487 104049 : BUN cnt;
1488 104049 : uint32_t rem;
1489 104049 : uint32_t val;
1490 104049 : const uint32_t *src;
1491 104049 : oid *dst;
1492 104049 : BUN n = 0;
1493 104049 : oid tseq = b->hseqbase;
1494 104049 : bool negcand = false;
1495 :
1496 104049 : BATiter bi = bat_iterator(b);
1497 104047 : if (mask_cand(b)) {
1498 99640 : cnt = ccand_free(b) / sizeof(uint32_t);
1499 99640 : rem = 0;
1500 99640 : src = (const uint32_t *) ccand_first(b);
1501 99640 : tseq = b->tseqbase;
1502 99640 : tseq -= (oid) CCAND(b)->firstbit;
1503 : /* create negative candidate list if more than half the
1504 : * bits are set */
1505 99640 : negcand = BATcount(b) > cnt * 16;
1506 : } else {
1507 4407 : cnt = bi.count / 32;
1508 4407 : rem = bi.count % 32;
1509 4407 : src = (const uint32_t *) bi.base;
1510 : }
1511 104047 : BAT *bn;
1512 :
1513 104047 : if (negcand) {
1514 82634 : bn = COLnew(b->hseqbase, TYPE_void, 0, TRANSIENT);
1515 82635 : if (bn == NULL) {
1516 0 : bat_iterator_end(&bi);
1517 0 : return NULL;
1518 : }
1519 82635 : Heap *dels;
1520 82635 : if ((dels = GDKmalloc(sizeof(Heap))) == NULL) {
1521 0 : BBPreclaim(bn);
1522 0 : bat_iterator_end(&bi);
1523 0 : return NULL;
1524 : }
1525 165270 : *dels = (Heap) {
1526 82635 : .farmid = BBPselectfarm(TRANSIENT, TYPE_void, varheap),
1527 82635 : .parentid = bn->batCacheid,
1528 : .dirty = true,
1529 : .refs = ATOMIC_VAR_INIT(1),
1530 : };
1531 82635 : strconcat_len(dels->filename, sizeof(dels->filename),
1532 82635 : BBP_physical(bn->batCacheid), ".theap", NULL);
1533 :
1534 165270 : if (dels->farmid < 0 ||
1535 82635 : HEAPalloc(dels, cnt * 32 - bi.count
1536 : + sizeof(ccand_t) / sizeof(oid), sizeof(oid)) != GDK_SUCCEED) {
1537 0 : GDKfree(dels);
1538 0 : BBPreclaim(bn);
1539 0 : bat_iterator_end(&bi);
1540 0 : return NULL;
1541 : }
1542 82635 : * (ccand_t *) dels->base = (ccand_t) {
1543 : .type = CAND_NEGOID,
1544 : };
1545 82635 : dst = (oid *) (dels->base + sizeof(ccand_t));
1546 7490477 : for (BUN p = 0, v = 0; p < cnt; p++, v += 32) {
1547 7407842 : if ((val = src[p]) == ~UINT32_C(0))
1548 5699944 : continue;
1549 54958181 : for (uint32_t i = 0; i < 32; i++) {
1550 53333036 : if ((val & (1U << i)) == 0) {
1551 46538112 : if (v + i >= b->batCount + n)
1552 : break;
1553 46455359 : dst[n++] = tseq + v + i;
1554 : }
1555 : }
1556 : }
1557 82635 : if (n == 0) {
1558 : /* didn't need it after all */
1559 10 : HEAPfree(dels, true);
1560 10 : GDKfree(dels);
1561 : } else {
1562 82625 : dels->free = sizeof(ccand_t) + n * sizeof(oid);
1563 82625 : dels->dirty = true;
1564 82625 : assert(bn->tvheap == NULL);
1565 82625 : bn->tvheap = dels;
1566 : }
1567 82635 : BATsetcount(bn, n=bi.count);
1568 82635 : bn->tseqbase = tseq;
1569 : } else {
1570 21413 : bn = COLnew(b->hseqbase, TYPE_oid, mask_cand(b) ? bi.count : 1024, TRANSIENT);
1571 21414 : if (bn == NULL) {
1572 0 : bat_iterator_end(&bi);
1573 0 : return NULL;
1574 : }
1575 21414 : dst = (oid *) Tloc(bn, 0);
1576 2685337 : for (BUN p = 0; p < cnt; p++) {
1577 2663923 : if ((val = src[p]) == 0)
1578 1891714 : continue;
1579 25478731 : for (uint32_t i = 0; i < 32; i++) {
1580 24706522 : if (val & (1U << i)) {
1581 21524169 : if (n == BATcapacity(bn)) {
1582 80 : BATsetcount(bn, n);
1583 80 : if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
1584 0 : BBPreclaim(bn);
1585 0 : bat_iterator_end(&bi);
1586 0 : return NULL;
1587 : }
1588 80 : dst = (oid *) Tloc(bn, 0);
1589 : }
1590 21524169 : dst[n++] = tseq + p * 32 + i;
1591 : }
1592 : }
1593 : }
1594 : /* the last partial mask word */
1595 21414 : if (rem > 0 && (val = src[cnt]) != 0) {
1596 22190 : for (uint32_t i = 0; i < rem; i++) {
1597 19854 : if (val & (1U << i)) {
1598 1172 : if (n == BATcapacity(bn)) {
1599 0 : BATsetcount(bn, n);
1600 0 : if (BATextend(bn, BATgrows(bn)) != GDK_SUCCEED) {
1601 0 : BBPreclaim(bn);
1602 0 : bat_iterator_end(&bi);
1603 0 : return NULL;
1604 : }
1605 0 : dst = (oid *) Tloc(bn, 0);
1606 : }
1607 1172 : dst[n++] = tseq + cnt * 32 + i;
1608 : }
1609 : }
1610 : }
1611 21414 : BATsetcount(bn, n);
1612 : }
1613 104049 : bat_iterator_end(&bi);
1614 104049 : bn->tkey = true;
1615 104049 : bn->tsorted = true;
1616 104049 : bn->trevsorted = n <= 1;
1617 104049 : bn->tnil = false;
1618 104049 : bn->tnonil = true;
1619 104049 : bn = virtualize(bn);
1620 104049 : TRC_DEBUG(ALGO, ALGOBATFMT " -> " ALGOBATFMT "\n", ALGOBATPAR(b), ALGOBATPAR(bn));
1621 : return bn;
1622 : }
|
