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_calc_private.h"
17 :
18 : /* BATfirstn select the smallest n elements from the input bat b (if
19 : * asc(ending) is set, else the largest n elements). Conceptually, b
20 : * is sorted in ascending or descending order (depending on the asc
21 : * argument) and then the OIDs of the first n elements are returned.
22 : * If there are NILs in the BAT, their relative ordering is set by
23 : * using the nilslast argument: if set, NILs come last (largest value
24 : * when ascending, smallest value when descending), so if there are
25 : * enough non-NIL values, no NILs will be returned. If unset (false),
26 : * NILs come first and will be returned.
27 : *
28 : * In addition to the input BAT b, there can be a standard candidate
29 : * list s. If s is specified (non-NULL), only elements in b that are
30 : * referred to in s are considered.
31 : *
32 : * If the third input bat g is non-NULL, then s must also be non-NULL
33 : * and must be aligned with g. G then specifies groups to which the
34 : * elements referred to in s belong. Conceptually, the group values
35 : * are sorted in ascending order together with the elements in b that
36 : * are referred to in s (in ascending or descending order depending on
37 : * asc), and the first n elements are then returned.
38 : *
39 : * If the output argument gids is NULL, only n elements are returned.
40 : * If the output argument gids is non-NULL, more than n elements may
41 : * be returned. If there are duplicate values (if g is given, the
42 : * group value counts in determining duplication), all duplicates are
43 : * returned.
44 : *
45 : * If distinct is set, the result contains n complete groups of values
46 : * instead of just n values (or slightly more than n if gids is set
47 : * since then the "last" group is returned completely).
48 : *
49 : * Note that BATfirstn can be called in cascading fashion to calculate
50 : * the first n values of a table of multiple columns:
51 : * BATfirstn(&s1, &g1, b1, NULL, NULL, n, asc, nilslast, distinct);
52 : * BATfirstn(&s2, &g2, b2, s1, g1, n, asc, nilslast, distinct);
53 : * BATfirstn(&s3, NULL, b3, s2, g2, n, asc, nilslast, distinct);
54 : * If the input BATs b1, b2, b3 are large enough, s3 will contain the
55 : * OIDs of the smallest (largest) n elements in the table consisting
56 : * of the columns b1, b2, b3 when ordered in ascending order with b1
57 : * the major key.
58 : */
59 :
60 : /* We use a binary heap for the implementation of the simplest form of
61 : * first-N. During processing, the oids list forms a heap with the
62 : * root at position 0 and the children of a node at position i at
63 : * positions 2*i+1 and 2*i+2. The parent node is always
64 : * smaller/larger (depending on the value of asc) than its children
65 : * (recursively). The heapify macro creates the heap from the input
66 : * in-place. We start off with a heap containing the first N elements
67 : * of the input, and then go over the rest of the input, replacing the
68 : * root of the heap with a new value if appropriate (if the new value
69 : * is among the first-N seen so far). The siftdown macro then
70 : * restores the heap property. */
71 : #define siftdown(OPER, START, SWAP) \
72 : do { \
73 : pos = (START); \
74 : childpos = (pos << 1) + 1; \
75 : while (childpos < n) { \
76 : /* find most extreme child */ \
77 : if (childpos + 1 < n && \
78 : !(OPER(childpos + 1, childpos))) \
79 : childpos++; \
80 : /* compare parent with most extreme child */ \
81 : if (!OPER(pos, childpos)) { \
82 : /* already correctly ordered */ \
83 : break; \
84 : } \
85 : /* exchange parent with child and sift child */ \
86 : /* further */ \
87 : SWAP(pos, childpos); \
88 : pos = childpos; \
89 : childpos = (pos << 1) + 1; \
90 : } \
91 : } while (0)
92 :
93 : #define heapify(OPER, SWAP) \
94 : do { \
95 : for (i = n / 2; i > 0; i--) \
96 : siftdown(OPER, i - 1, SWAP); \
97 : } while (0)
98 :
99 : /* we inherit LT and GT from gdk_calc_private.h */
100 :
101 : #define nLTbte(a, b) (!is_bte_nil(a) && (is_bte_nil(b) || (a) < (b)))
102 : #define nLTsht(a, b) (!is_sht_nil(a) && (is_sht_nil(b) || (a) < (b)))
103 : #define nLTint(a, b) (!is_int_nil(a) && (is_int_nil(b) || (a) < (b)))
104 : #define nLTlng(a, b) (!is_lng_nil(a) && (is_lng_nil(b) || (a) < (b)))
105 : #define nLThge(a, b) (!is_hge_nil(a) && (is_hge_nil(b) || (a) < (b)))
106 :
107 : #define nGTbte(a, b) (!is_bte_nil(b) && (is_bte_nil(a) || (a) > (b)))
108 : #define nGTsht(a, b) (!is_sht_nil(b) && (is_sht_nil(a) || (a) > (b)))
109 : #define nGTint(a, b) (!is_int_nil(b) && (is_int_nil(a) || (a) > (b)))
110 : #define nGTlng(a, b) (!is_lng_nil(b) && (is_lng_nil(a) || (a) > (b)))
111 : #define nGThge(a, b) (!is_hge_nil(b) && (is_hge_nil(a) || (a) > (b)))
112 :
113 : #define LTany(p1, p2) (cmp(BUNtail(*bi, oids[p1] - hseq), \
114 : BUNtail(*bi, oids[p2] - hseq)) < 0)
115 : #define GTany(p1, p2) (cmp(BUNtail(*bi, oids[p1] - hseq), \
116 : BUNtail(*bi, oids[p2] - hseq)) > 0)
117 :
118 : #define nLTany(p1, p2) (cmp(BUNtail(*bi, oids[p1] - hseq), nil) != 0 \
119 : && (cmp(BUNtail(*bi, oids[p2] - hseq), nil) == 0 \
120 : || cmp(BUNtail(*bi, oids[p1] - hseq), \
121 : BUNtail(*bi, oids[p2] - hseq)) < 0))
122 : #define nGTany(p1, p2) (cmp(BUNtail(*bi, oids[p2] - hseq), nil) != 0 \
123 : && (cmp(BUNtail(*bi, oids[p1] - hseq), nil) == 0 \
124 : || cmp(BUNtail(*bi, oids[p1] - hseq), \
125 : BUNtail(*bi, oids[p2] - hseq)) > 0))
126 :
127 : #define LTflt(a, b) (!is_flt_nil(b) && (is_flt_nil(a) || (a) < (b)))
128 : #define LTdbl(a, b) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) < (b)))
129 : #define GTflt(a, b) (!is_flt_nil(a) && (is_flt_nil(b) || (a) > (b)))
130 : #define GTdbl(a, b) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) > (b)))
131 :
132 : #define nLTflt(a, b) (!is_flt_nil(a) && (is_flt_nil(b) || (a) < (b)))
133 : #define nLTdbl(a, b) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) < (b)))
134 : #define nGTflt(a, b) (!is_flt_nil(b) && (is_flt_nil(a) || (a) > (b)))
135 : #define nGTdbl(a, b) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) > (b)))
136 :
137 : #define LTfltfix(p1, p2) LTflt(vals[oids[p1] - hseq], \
138 : vals[oids[p2] - hseq])
139 : #define GTfltfix(p1, p2) GTflt(vals[oids[p1] - hseq], \
140 : vals[oids[p2] - hseq])
141 : #define LTdblfix(p1, p2) LTdbl(vals[oids[p1] - hseq], \
142 : vals[oids[p2] - hseq])
143 : #define GTdblfix(p1, p2) GTdbl(vals[oids[p1] - hseq], \
144 : vals[oids[p2] - hseq])
145 : #define LTfix(p1, p2) LT(vals[oids[p1] - hseq], \
146 : vals[oids[p2] - hseq])
147 : #define GTfix(p1, p2) GT(vals[oids[p1] - hseq], \
148 : vals[oids[p2] - hseq])
149 :
150 : #define nLTfltfix(p1, p2) nLTflt(vals[oids[p1] - hseq], \
151 : vals[oids[p2] - hseq])
152 : #define nGTfltfix(p1, p2) nGTflt(vals[oids[p1] - hseq], \
153 : vals[oids[p2] - hseq])
154 : #define nLTdblfix(p1, p2) nLTdbl(vals[oids[p1] - hseq], \
155 : vals[oids[p2] - hseq])
156 : #define nGTdblfix(p1, p2) nGTdbl(vals[oids[p1] - hseq], \
157 : vals[oids[p2] - hseq])
158 : #define nLTbtefix(p1, p2) nLTbte(vals[oids[p1] - hseq], \
159 : vals[oids[p2] - hseq])
160 : #define nGTbtefix(p1, p2) nGTbte(vals[oids[p1] - hseq], \
161 : vals[oids[p2] - hseq])
162 : #define nLTshtfix(p1, p2) nLTsht(vals[oids[p1] - hseq], \
163 : vals[oids[p2] - hseq])
164 : #define nGTshtfix(p1, p2) nGTsht(vals[oids[p1] - hseq], \
165 : vals[oids[p2] - hseq])
166 : #define nLTintfix(p1, p2) nLTint(vals[oids[p1] - hseq], \
167 : vals[oids[p2] - hseq])
168 : #define nGTintfix(p1, p2) nGTint(vals[oids[p1] - hseq], \
169 : vals[oids[p2] - hseq])
170 : #define nLTlngfix(p1, p2) nLTlng(vals[oids[p1] - hseq], \
171 : vals[oids[p2] - hseq])
172 : #define nGTlngfix(p1, p2) nGTlng(vals[oids[p1] - hseq], \
173 : vals[oids[p2] - hseq])
174 : #define nLThgefix(p1, p2) nLThge(vals[oids[p1] - hseq], \
175 : vals[oids[p2] - hseq])
176 : #define nGThgefix(p1, p2) nGThge(vals[oids[p1] - hseq], \
177 : vals[oids[p2] - hseq])
178 :
179 : #define SWAP1(p1, p2) \
180 : do { \
181 : item = oids[p1]; \
182 : oids[p1] = oids[p2]; \
183 : oids[p2] = item; \
184 : } while (0)
185 :
186 : #define shuffle_unique(TYPE, OP) \
187 : do { \
188 : const TYPE *restrict vals = (const TYPE *) bi->base; \
189 : heapify(OP##fix, SWAP1); \
190 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) { \
191 : i = canditer_next(&ci); \
192 : if (OP(vals[i - hseq], \
193 : vals[oids[0] - hseq])) { \
194 : oids[0] = i; \
195 : siftdown(OP##fix, 0, SWAP1); \
196 : } \
197 : } \
198 : } while (0)
199 :
200 : /* This version of BATfirstn returns a list of N oids (where N is the
201 : * smallest among BATcount(b), BATcount(s), and n). The oids returned
202 : * refer to the N smallest/largest (depending on asc) tail values of b
203 : * (taking the optional candidate list s into account). If there are
204 : * multiple equal values to take us past N, we return a subset of those.
205 : *
206 : * If lastp is non-NULL, it is filled in with the oid of the "last"
207 : * value, i.e. the value of which there may be multiple occurrences
208 : * that are not all included in the first N.
209 : */
210 : static BAT *
211 741 : BATfirstn_unique(BATiter *bi, BAT *s, BUN n, bool asc, bool nilslast, oid *lastp, lng t0)
212 : {
213 741 : BAT *bn;
214 741 : oid *restrict oids;
215 741 : oid hseq = bi->b->hseqbase;
216 741 : BUN i;
217 741 : struct canditer ci;
218 741 : int tpe = bi->type;
219 741 : int (*cmp)(const void *, const void *);
220 741 : const void *nil;
221 : /* variables used in heapify/siftdown macros */
222 741 : oid item;
223 741 : BUN pos, childpos;
224 :
225 741 : MT_thread_setalgorithm(__func__);
226 741 : canditer_init(&ci, bi->b, s);
227 :
228 741 : if (n >= ci.ncand) {
229 : /* trivial: return all candidates */
230 414 : bn = canditer_slice(&ci, 0, ci.ncand);
231 414 : if (bn && lastp)
232 115 : *lastp = oid_nil;
233 414 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
234 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
235 : " (trivial -- " LLFMT " usec)\n",
236 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
237 : ALGOOPTBATPAR(bn), GDKusec() - t0);
238 414 : return bn;
239 : }
240 :
241 327 : if (BATtvoid(bi->b)) {
242 : /* nilslast doesn't make a difference: either all are
243 : * nil, or none are */
244 0 : if (asc || is_oid_nil(bi->tseq)) {
245 : /* return the first part of the candidate list
246 : * or of the BAT itself */
247 0 : bn = canditer_slice(&ci, 0, n);
248 0 : if (bn && lastp)
249 0 : *lastp = BUNtoid(bn, n - 1);
250 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
251 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
252 : " (initial slice -- " LLFMT " usec)\n",
253 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
254 : ALGOOPTBATPAR(bn), GDKusec() - t0);
255 0 : return bn;
256 : }
257 : /* return the last part of the candidate list or of
258 : * the BAT itself */
259 0 : bn = canditer_slice(&ci, ci.ncand - n, ci.ncand);
260 0 : if (bn && lastp)
261 0 : *lastp = BUNtoid(bn, 0);
262 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
263 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
264 : " (final slice -- " LLFMT " usec)\n",
265 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
266 : ALGOOPTBATPAR(bn), GDKusec() - t0);
267 0 : return bn;
268 : }
269 327 : if (bi->sorted || bi->revsorted) {
270 : /* trivial: b is sorted so we just need to return the
271 : * initial or final part of it (or of the candidate
272 : * list); however, if nilslast == asc, then the nil
273 : * values (if any) are in the wrong place, so we need
274 : * to do a little more work */
275 :
276 : /* after we create the to-be-returned BAT, we set pos
277 : * to the BUN in the new BAT whose value we should
278 : * return through *lastp */
279 179 : if (nilslast == asc && !bi->nonil) {
280 0 : pos = SORTfndlast(bi->b, ATOMnilptr(tpe));
281 0 : pos = canditer_search(&ci, hseq + pos, true);
282 : /* 0 <= pos <= ci.ncand
283 : * 0 < n < ci.ncand
284 : */
285 0 : if (bi->sorted) {
286 : /* [0..pos) -- nil
287 : * [pos..ci.ncand) -- non-nil <<<
288 : */
289 0 : if (asc) { /* i.e. nilslast */
290 : /* prefer non-nil and
291 : * smallest */
292 0 : if (ci.ncand - pos < n) {
293 0 : bn = canditer_slice(&ci, ci.ncand - n, ci.ncand);
294 0 : pos = 0;
295 : } else {
296 0 : bn = canditer_slice(&ci, pos, pos + n);
297 0 : pos = n - 1;
298 : }
299 : } else { /* i.e. !asc, !nilslast */
300 : /* prefer nil and largest */
301 0 : if (pos < n) {
302 0 : bn = canditer_slice2(&ci, 0, pos, ci.ncand - (n - pos), ci.ncand);
303 : /* pos = pos; */
304 : } else {
305 0 : bn = canditer_slice(&ci, 0, n);
306 0 : pos = 0;
307 : }
308 : }
309 : } else { /* i.e. trevsorted */
310 : /* [0..pos) -- non-nil >>>
311 : * [pos..ci.ncand) -- nil
312 : */
313 0 : if (asc) { /* i.e. nilslast */
314 : /* prefer non-nil and
315 : * smallest */
316 0 : if (pos < n) {
317 0 : bn = canditer_slice(&ci, 0, n);
318 : /* pos = pos; */
319 : } else {
320 0 : bn = canditer_slice(&ci, pos - n, pos);
321 0 : pos = 0;
322 : }
323 : } else { /* i.e. !asc, !nilslast */
324 : /* prefer nil and largest */
325 0 : if (ci.ncand - pos < n) {
326 0 : bn = canditer_slice2(&ci, 0, n - (ci.ncand - pos), pos, ci.ncand);
327 0 : pos = n - (ci.ncand - pos) - 1;
328 : } else {
329 0 : bn = canditer_slice(&ci, pos, pos + n);
330 0 : pos = 0;
331 : }
332 : }
333 : }
334 : } else {
335 : /* either there are no nils, or they are in
336 : * the appropriate position already, so we can
337 : * just slice */
338 179 : if (asc ? bi->sorted : bi->revsorted) {
339 : /* return copy of first part of
340 : * candidate list */
341 162 : bn = canditer_slice(&ci, 0, n);
342 162 : pos = n - 1;
343 : } else {
344 : /* return copy of last part of
345 : * candidate list */
346 17 : bn = canditer_slice(&ci, ci.ncand - n, ci.ncand);
347 17 : pos = 0;
348 : }
349 : }
350 179 : if (bn && lastp)
351 39 : *lastp = BUNtoid(bn, pos);
352 178 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
353 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
354 : " (ordered -- " LLFMT " usec)\n",
355 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
356 : ALGOOPTBATPAR(bn), GDKusec() - t0);
357 178 : return bn;
358 : }
359 :
360 148 : bn = COLnew(0, TYPE_oid, n, TRANSIENT);
361 148 : if (bn == NULL)
362 : return NULL;
363 148 : BATsetcount(bn, n);
364 148 : oids = (oid *) Tloc(bn, 0);
365 148 : cmp = ATOMcompare(tpe);
366 148 : nil = ATOMnilptr(tpe);
367 : /* if base type has same comparison function as type itself, we
368 : * can use the base type */
369 148 : tpe = ATOMbasetype(tpe); /* takes care of oid */
370 : /* if the input happens to be almost sorted in ascending order
371 : * (likely a common use case), it is more efficient to start
372 : * off with the first n elements when doing a firstn-ascending
373 : * and to start off with the last n elements when doing a
374 : * firstn-descending so that most values that we look at after
375 : * this will be skipped. However, when using a bitmask
376 : * candidate list, the manipulation of the canditer structure
377 : * doesn't work like this, so we still work from the
378 : * beginning. */
379 148 : if (asc || ci.tpe == cand_mask) {
380 305568 : for (i = 0; i < n; i++)
381 305482 : oids[i] = canditer_next(&ci);
382 : } else {
383 62 : item = canditer_idx(&ci, ci.ncand - n);
384 62 : ci.next = ci.ncand - n;
385 62 : ci.add = item - ci.seq - (ci.ncand - n);
386 642 : for (i = n; i > 0; i--)
387 580 : oids[i - 1] = canditer_next(&ci);
388 62 : canditer_reset(&ci);
389 : }
390 :
391 148 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
392 :
393 148 : if (asc) {
394 86 : if (nilslast && !bi->nonil) {
395 14 : switch (tpe) {
396 2 : case TYPE_bte:
397 24 : shuffle_unique(bte, nLTbte);
398 : break;
399 0 : case TYPE_sht:
400 0 : shuffle_unique(sht, nLTsht);
401 : break;
402 2 : case TYPE_int:
403 22 : shuffle_unique(int, nLTint);
404 : break;
405 4 : case TYPE_lng:
406 47 : shuffle_unique(lng, nLTlng);
407 : break;
408 : #ifdef HAVE_HGE
409 0 : case TYPE_hge:
410 0 : shuffle_unique(hge, nLThge);
411 : break;
412 : #endif
413 2 : case TYPE_flt:
414 25 : shuffle_unique(flt, nLTflt);
415 : break;
416 0 : case TYPE_dbl:
417 0 : shuffle_unique(dbl, nLTdbl);
418 : break;
419 4 : default:
420 29 : heapify(nLTany, SWAP1);
421 14 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
422 6 : i = canditer_next(&ci);
423 6 : if (cmp(BUNtail(*bi, i - hseq), nil) != 0
424 5 : && (cmp(BUNtail(*bi, oids[0] - hseq), nil) == 0
425 1 : || cmp(BUNtail(*bi, i - hseq),
426 1 : BUNtail(*bi, oids[0] - hseq)) < 0)) {
427 5 : oids[0] = i;
428 15 : siftdown(nLTany, 0, SWAP1);
429 : }
430 : }
431 : break;
432 : }
433 : } else {
434 72 : switch (tpe) {
435 0 : case TYPE_bte:
436 0 : shuffle_unique(bte, LT);
437 : break;
438 0 : case TYPE_sht:
439 0 : shuffle_unique(sht, LT);
440 : break;
441 25 : case TYPE_int:
442 7025 : shuffle_unique(int, LT);
443 : break;
444 5 : case TYPE_lng:
445 7451861 : shuffle_unique(lng, LT);
446 : break;
447 : #ifdef HAVE_HGE
448 8 : case TYPE_hge:
449 100283 : shuffle_unique(hge, LT);
450 : break;
451 : #endif
452 0 : case TYPE_flt:
453 0 : shuffle_unique(flt, LTflt);
454 : break;
455 3 : case TYPE_dbl:
456 77670 : shuffle_unique(dbl, LTdbl);
457 : break;
458 31 : default:
459 3523 : heapify(LTany, SWAP1);
460 142957 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
461 142893 : i = canditer_next(&ci);
462 142893 : if (cmp(BUNtail(*bi, i - hseq),
463 142893 : BUNtail(*bi, oids[0] - hseq)) < 0) {
464 5724 : oids[0] = i;
465 172792 : siftdown(LTany, 0, SWAP1);
466 : }
467 : }
468 : break;
469 : }
470 : }
471 : } else {
472 62 : if (nilslast || bi->nonil) {
473 41 : switch (tpe) {
474 0 : case TYPE_bte:
475 0 : shuffle_unique(bte, GT);
476 : break;
477 0 : case TYPE_sht:
478 0 : shuffle_unique(sht, GT);
479 : break;
480 24 : case TYPE_int:
481 216 : shuffle_unique(int, GT);
482 : break;
483 1 : case TYPE_lng:
484 2085 : shuffle_unique(lng, GT);
485 : break;
486 : #ifdef HAVE_HGE
487 5 : case TYPE_hge:
488 1446 : shuffle_unique(hge, GT);
489 : break;
490 : #endif
491 0 : case TYPE_flt:
492 0 : shuffle_unique(flt, GTflt);
493 : break;
494 2 : case TYPE_dbl:
495 24 : shuffle_unique(dbl, GTdbl);
496 : break;
497 9 : default:
498 51 : heapify(GTany, SWAP1);
499 49 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
500 31 : i = canditer_next(&ci);
501 31 : if (cmp(BUNtail(*bi, i - hseq),
502 31 : BUNtail(*bi, oids[0] - hseq)) > 0) {
503 19 : oids[0] = i;
504 60 : siftdown(GTany, 0, SWAP1);
505 : }
506 : }
507 : break;
508 : }
509 : } else {
510 21 : switch (tpe) {
511 1 : case TYPE_bte:
512 10 : shuffle_unique(bte, nGTbte);
513 : break;
514 0 : case TYPE_sht:
515 0 : shuffle_unique(sht, nGTsht);
516 : break;
517 2 : case TYPE_int:
518 20 : shuffle_unique(int, nGTint);
519 : break;
520 8 : case TYPE_lng:
521 80 : shuffle_unique(lng, nGTlng);
522 : break;
523 : #ifdef HAVE_HGE
524 0 : case TYPE_hge:
525 0 : shuffle_unique(hge, nGThge);
526 : break;
527 : #endif
528 2 : case TYPE_flt:
529 20 : shuffle_unique(flt, nGTflt);
530 : break;
531 2 : case TYPE_dbl:
532 20 : shuffle_unique(dbl, nGTdbl);
533 : break;
534 6 : default:
535 38 : heapify(nGTany, SWAP1);
536 25 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
537 13 : i = canditer_next(&ci);
538 13 : if (cmp(BUNtail(*bi, oids[0] - hseq), nil) != 0
539 13 : && (cmp(BUNtail(*bi, i - hseq), nil) == 0
540 11 : || cmp(BUNtail(*bi, i - hseq),
541 11 : BUNtail(*bi, oids[0] - hseq)) > 0)) {
542 13 : oids[0] = i;
543 34 : siftdown(nGTany, 0, SWAP1);
544 : }
545 : }
546 : break;
547 : }
548 : }
549 : }
550 148 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
551 148 : if (lastp)
552 56 : *lastp = oids[0]; /* store id of largest value */
553 : /* output must be sorted since it's a candidate list */
554 148 : GDKqsort(oids, NULL, NULL, (size_t) n, sizeof(oid), 0, TYPE_oid, false, false);
555 148 : bn->tsorted = true;
556 148 : bn->trevsorted = n <= 1;
557 148 : bn->tkey = true;
558 148 : bn->tseqbase = n <= 1 ? oids[0] : oid_nil;
559 148 : bn->tnil = false;
560 148 : bn->tnonil = true;
561 148 : bn = virtualize(bn);
562 148 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
563 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
564 : " (" LLFMT " usec)\n",
565 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
566 : ALGOOPTBATPAR(bn), GDKusec() - t0);
567 : return bn;
568 :
569 0 : bailout:
570 0 : BBPreclaim(bn);
571 0 : return NULL;
572 : }
573 :
574 : #define LTfixgrp(p1, p2) \
575 : (goids[p1] < goids[p2] || \
576 : (goids[p1] == goids[p2] && \
577 : LTfix(p1, p2)))
578 : #define nLTbtefixgrp(p1, p2) \
579 : (goids[p1] < goids[p2] || \
580 : (goids[p1] == goids[p2] && \
581 : nLTbtefix(p1, p2)))
582 : #define nLTshtfixgrp(p1, p2) \
583 : (goids[p1] < goids[p2] || \
584 : (goids[p1] == goids[p2] && \
585 : nLTshtfix(p1, p2)))
586 : #define nLTintfixgrp(p1, p2) \
587 : (goids[p1] < goids[p2] || \
588 : (goids[p1] == goids[p2] && \
589 : nLTintfix(p1, p2)))
590 : #define nLTlngfixgrp(p1, p2) \
591 : (goids[p1] < goids[p2] || \
592 : (goids[p1] == goids[p2] && \
593 : nLTlngfix(p1, p2)))
594 : #define nLThgefixgrp(p1, p2) \
595 : (goids[p1] < goids[p2] || \
596 : (goids[p1] == goids[p2] && \
597 : nLThgefix(p1, p2)))
598 : #define LTfltfixgrp(p1, p2) \
599 : (goids[p1] < goids[p2] || \
600 : (goids[p1] == goids[p2] && \
601 : LTfltfix(p1, p2)))
602 : #define LTdblfixgrp(p1, p2) \
603 : (goids[p1] < goids[p2] || \
604 : (goids[p1] == goids[p2] && \
605 : LTdblfix(p1, p2)))
606 : #define nLTfltfixgrp(p1, p2) \
607 : (goids[p1] < goids[p2] || \
608 : (goids[p1] == goids[p2] && \
609 : nLTfltfix(p1, p2)))
610 : #define nLTdblfixgrp(p1, p2) \
611 : (goids[p1] < goids[p2] || \
612 : (goids[p1] == goids[p2] && \
613 : nLTdblfix(p1, p2)))
614 : #define GTfixgrp(p1, p2) \
615 : (goids[p1] < goids[p2] || \
616 : (goids[p1] == goids[p2] && \
617 : GTfix(p1, p2)))
618 : #define nGTbtefixgrp(p1, p2) \
619 : (goids[p1] < goids[p2] || \
620 : (goids[p1] == goids[p2] && \
621 : nGTbtefix(p1, p2)))
622 : #define nGTshtfixgrp(p1, p2) \
623 : (goids[p1] < goids[p2] || \
624 : (goids[p1] == goids[p2] && \
625 : nGTshtfix(p1, p2)))
626 : #define nGTintfixgrp(p1, p2) \
627 : (goids[p1] < goids[p2] || \
628 : (goids[p1] == goids[p2] && \
629 : nGTintfix(p1, p2)))
630 : #define nGTlngfixgrp(p1, p2) \
631 : (goids[p1] < goids[p2] || \
632 : (goids[p1] == goids[p2] && \
633 : nGTlngfix(p1, p2)))
634 : #define nGThgefixgrp(p1, p2) \
635 : (goids[p1] < goids[p2] || \
636 : (goids[p1] == goids[p2] && \
637 : nGThgefix(p1, p2)))
638 : #define GTfltfixgrp(p1, p2) \
639 : (goids[p1] < goids[p2] || \
640 : (goids[p1] == goids[p2] && \
641 : GTfltfix(p1, p2)))
642 : #define GTdblfixgrp(p1, p2) \
643 : (goids[p1] < goids[p2] || \
644 : (goids[p1] == goids[p2] && \
645 : GTdblfix(p1, p2)))
646 : #define nGTfltfixgrp(p1, p2) \
647 : (goids[p1] < goids[p2] || \
648 : (goids[p1] == goids[p2] && \
649 : nGTfltfix(p1, p2)))
650 : #define nGTdblfixgrp(p1, p2) \
651 : (goids[p1] < goids[p2] || \
652 : (goids[p1] == goids[p2] && \
653 : nGTdblfix(p1, p2)))
654 : #define LTvoidgrp(p1, p2) \
655 : (goids[p1] < goids[p2] || \
656 : (goids[p1] == goids[p2] && oids[p1] < oids[p2]))
657 : #define GTvoidgrp(p1, p2) \
658 : (goids[p1] < goids[p2] || \
659 : (goids[p1] == goids[p2] && oids[p1] > oids[p2]))
660 : #define LTanygrp(p1, p2) \
661 : (goids[p1] < goids[p2] || \
662 : (goids[p1] == goids[p2] && \
663 : LTany(p1, p2)))
664 : #define GTanygrp(p1, p2) \
665 : (goids[p1] < goids[p2] || \
666 : (goids[p1] == goids[p2] && \
667 : GTany(p1, p2)))
668 : #define nLTanygrp(p1, p2) \
669 : (goids[p1] < goids[p2] || \
670 : (goids[p1] == goids[p2] && \
671 : nLTany(p1, p2)))
672 : #define nGTanygrp(p1, p2) \
673 : (goids[p1] < goids[p2] || \
674 : (goids[p1] == goids[p2] && \
675 : nGTany(p1, p2)))
676 : #define SWAP2(p1, p2) \
677 : do { \
678 : item = oids[p1]; \
679 : oids[p1] = oids[p2]; \
680 : oids[p2] = item; \
681 : item = goids[p1]; \
682 : goids[p1] = goids[p2]; \
683 : goids[p2] = item; \
684 : } while (0)
685 :
686 : #define shuffle_unique_with_groups(TYPE, OP) \
687 : do { \
688 : const TYPE *restrict vals = (const TYPE *) bi->base; \
689 : heapify(OP##fixgrp, SWAP2); \
690 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) { \
691 : i = canditer_next(&ci); \
692 : if (gv[j] < goids[0] || \
693 : (gv[j] == goids[0] && \
694 : OP(vals[i - hseq], \
695 : vals[oids[0] - hseq]))) { \
696 : oids[0] = i; \
697 : goids[0] = gv[j]; \
698 : siftdown(OP##fixgrp, 0, SWAP2); \
699 : } \
700 : j++; \
701 : } \
702 : } while (0)
703 :
704 : /* This version of BATfirstn is like the one above, except that it
705 : * also looks at groups. The values of the group IDs are important:
706 : * we return only the smallest N (i.e., not dependent on asc which
707 : * refers only to the values in the BAT b).
708 : *
709 : * If lastp is non-NULL, it is filled in with the oid of the "last"
710 : * value, i.e. the value of which there may be multiple occurrences
711 : * that are not all included in the first N. If lastgp is non-NULL,
712 : * it is filled with the group ID (not the oid of the group ID) for
713 : * that same value.
714 : */
715 : static BAT *
716 469 : BATfirstn_unique_with_groups(BATiter *bi, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, oid *lastp, oid *lastgp, lng t0)
717 : {
718 469 : BAT *bn;
719 469 : oid *restrict oids, *restrict goids;
720 469 : oid hseq = bi->b->hseqbase;
721 469 : const oid *restrict gv;
722 469 : BUN i, j;
723 469 : struct canditer ci;
724 469 : int tpe = bi->type;
725 469 : int (*cmp)(const void *, const void *);
726 469 : const void *nil;
727 : /* variables used in heapify/siftdown macros */
728 469 : oid item;
729 469 : BUN pos, childpos;
730 :
731 469 : MT_thread_setalgorithm(__func__);
732 469 : canditer_init(&ci, bi->b, s);
733 :
734 469 : if (n > ci.ncand)
735 : n = ci.ncand;
736 :
737 469 : if (n == 0) {
738 : /* candidate list might refer only to values outside
739 : * of the bat and hence be effectively empty */
740 0 : if (lastp)
741 0 : *lastp = 0;
742 0 : if (lastgp)
743 0 : *lastgp = 0;
744 0 : bn = BATdense(0, 0, 0);
745 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
746 : ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
747 : " (empty -- " LLFMT " usec)\n",
748 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
749 : ALGOOPTBATPAR(bn), GDKusec() - t0);
750 0 : return bn;
751 : }
752 :
753 469 : if (BATtdense(g)) {
754 : /* trivial: g determines ordering, return reference to
755 : * initial part of b (or slice of s) */
756 37 : if (lastgp)
757 16 : *lastgp = g->tseqbase + n - 1;
758 37 : bn = canditer_slice(&ci, 0, n);
759 37 : if (bn && lastp)
760 16 : *lastp = BUNtoid(bn, n - 1);
761 37 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
762 : ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
763 : " (dense group -- " LLFMT " usec)\n",
764 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
765 : ALGOOPTBATPAR(bn), GDKusec() - t0);
766 37 : return bn;
767 : }
768 :
769 432 : bn = COLnew(0, TYPE_oid, n, TRANSIENT);
770 432 : if (bn == NULL)
771 : return NULL;
772 432 : BATsetcount(bn, n);
773 432 : oids = (oid *) Tloc(bn, 0);
774 432 : gv = (const oid *) Tloc(g, 0);
775 432 : goids = GDKmalloc(n * sizeof(oid));
776 432 : if (goids == NULL) {
777 0 : BBPreclaim(bn);
778 0 : return NULL;
779 : }
780 :
781 432 : cmp = ATOMcompare(tpe);
782 432 : nil = ATOMnilptr(tpe);
783 : /* if base type has same comparison function as type itself, we
784 : * can use the base type */
785 432 : tpe = ATOMbasetype(tpe); /* takes care of oid */
786 432 : j = 0;
787 11051060 : for (i = 0; i < n; i++) {
788 11050628 : oids[i] = canditer_next(&ci);
789 11050628 : goids[i] = gv[j++];
790 : }
791 :
792 432 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
793 :
794 432 : if (BATtvoid(bi->b)) {
795 : /* nilslast doesn't make a difference (all nil, or no nil) */
796 0 : if (asc) {
797 0 : heapify(LTvoidgrp, SWAP2);
798 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
799 0 : i = canditer_next(&ci);
800 0 : if (gv[j] < goids[0]
801 : /* || (gv[j] == goids[0]
802 : && i < oids[0]) -- always false */) {
803 0 : oids[0] = i;
804 0 : goids[0] = gv[j];
805 0 : siftdown(LTvoidgrp, 0, SWAP2);
806 : }
807 0 : j++;
808 : }
809 : } else {
810 0 : heapify(GTvoidgrp, SWAP2);
811 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
812 0 : i = canditer_next(&ci);
813 0 : if (gv[j] < goids[0]
814 0 : || (gv[j] == goids[0]
815 : /* && i > oids[0] -- always true */)) {
816 0 : oids[0] = i;
817 0 : goids[0] = gv[j];
818 0 : siftdown(GTvoidgrp, 0, SWAP2);
819 : }
820 0 : j++;
821 : }
822 : }
823 432 : } else if (asc) {
824 373 : if (nilslast && !bi->nonil) {
825 0 : switch (tpe) {
826 0 : case TYPE_bte:
827 0 : shuffle_unique_with_groups(bte, nLTbte);
828 : break;
829 0 : case TYPE_sht:
830 0 : shuffle_unique_with_groups(sht, nLTsht);
831 : break;
832 0 : case TYPE_int:
833 0 : shuffle_unique_with_groups(int, nLTint);
834 : break;
835 0 : case TYPE_lng:
836 0 : shuffle_unique_with_groups(lng, nLTlng);
837 : break;
838 : #ifdef HAVE_HGE
839 0 : case TYPE_hge:
840 0 : shuffle_unique_with_groups(hge, nLThge);
841 : break;
842 : #endif
843 0 : case TYPE_flt:
844 0 : shuffle_unique_with_groups(flt, nLTflt);
845 : break;
846 0 : case TYPE_dbl:
847 0 : shuffle_unique_with_groups(dbl, nLTdbl);
848 : break;
849 0 : default:
850 0 : heapify(nLTanygrp, SWAP2);
851 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
852 0 : i = canditer_next(&ci);
853 0 : if (gv[j] < goids[0]
854 0 : || (gv[j] == goids[0]
855 0 : && cmp(BUNtail(*bi, i - hseq), nil) != 0
856 0 : && (cmp(BUNtail(*bi, oids[0] - hseq), nil) == 0
857 0 : || cmp(BUNtail(*bi, i - hseq),
858 0 : BUNtail(*bi, oids[0] - hseq)) < 0))) {
859 0 : oids[0] = i;
860 0 : goids[0] = gv[j];
861 0 : siftdown(nLTanygrp, 0, SWAP2);
862 : }
863 0 : j++;
864 : }
865 : break;
866 : }
867 : } else {
868 373 : switch (tpe) {
869 21 : case TYPE_bte:
870 1597911 : shuffle_unique_with_groups(bte, LT);
871 : break;
872 14 : case TYPE_sht:
873 1000077 : shuffle_unique_with_groups(sht, LT);
874 : break;
875 126 : case TYPE_int:
876 34480 : shuffle_unique_with_groups(int, LT);
877 : break;
878 10 : case TYPE_lng:
879 597905 : shuffle_unique_with_groups(lng, LT);
880 : break;
881 : #ifdef HAVE_HGE
882 30 : case TYPE_hge:
883 2753 : shuffle_unique_with_groups(hge, LT);
884 : break;
885 : #endif
886 0 : case TYPE_flt:
887 0 : shuffle_unique_with_groups(flt, LTflt);
888 : break;
889 4 : case TYPE_dbl:
890 21 : shuffle_unique_with_groups(dbl, LTdbl);
891 : break;
892 168 : default:
893 260877 : heapify(LTanygrp, SWAP2);
894 16007 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
895 15671 : i = canditer_next(&ci);
896 15671 : if (gv[j] < goids[0] ||
897 15501 : (gv[j] == goids[0] &&
898 15501 : cmp(BUNtail(*bi, i - hseq),
899 15501 : BUNtail(*bi, oids[0] - hseq)) < 0)) {
900 2321 : oids[0] = i;
901 2321 : goids[0] = gv[j];
902 14484 : siftdown(LTanygrp, 0, SWAP2);
903 : }
904 15671 : j++;
905 : }
906 : break;
907 : }
908 : }
909 59 : } else if (nilslast || bi->nonil) {
910 40 : switch (tpe) {
911 5 : case TYPE_bte:
912 227250 : shuffle_unique_with_groups(bte, GT);
913 : break;
914 0 : case TYPE_sht:
915 0 : shuffle_unique_with_groups(sht, GT);
916 : break;
917 15 : case TYPE_int:
918 5301761 : shuffle_unique_with_groups(int, GT);
919 : break;
920 0 : case TYPE_lng:
921 0 : shuffle_unique_with_groups(lng, GT);
922 : break;
923 : #ifdef HAVE_HGE
924 5 : case TYPE_hge:
925 728 : shuffle_unique_with_groups(hge, GT);
926 : break;
927 : #endif
928 0 : case TYPE_flt:
929 0 : shuffle_unique_with_groups(flt, GTflt);
930 : break;
931 6 : case TYPE_dbl:
932 246231 : shuffle_unique_with_groups(dbl, GTdbl);
933 : break;
934 9 : default:
935 54 : heapify(GTanygrp, SWAP2);
936 21 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
937 3 : i = canditer_next(&ci);
938 3 : if (gv[j] < goids[0] ||
939 2 : (gv[j] == goids[0] &&
940 2 : cmp(BUNtail(*bi, i - hseq),
941 2 : BUNtail(*bi, oids[0] - hseq)) > 0)) {
942 2 : oids[0] = i;
943 2 : goids[0] = gv[j];
944 5 : siftdown(GTanygrp, 0, SWAP2);
945 : }
946 3 : j++;
947 : }
948 : break;
949 : }
950 : } else {
951 19 : switch (tpe) {
952 2 : case TYPE_bte:
953 441484 : shuffle_unique_with_groups(bte, nGTbte);
954 : break;
955 0 : case TYPE_sht:
956 0 : shuffle_unique_with_groups(sht, nGTsht);
957 : break;
958 0 : case TYPE_int:
959 0 : shuffle_unique_with_groups(int, nGTint);
960 : break;
961 0 : case TYPE_lng:
962 0 : shuffle_unique_with_groups(lng, nGTlng);
963 : break;
964 : #ifdef HAVE_HGE
965 17 : case TYPE_hge:
966 1619124 : shuffle_unique_with_groups(hge, nGThge);
967 : break;
968 : #endif
969 0 : case TYPE_flt:
970 0 : shuffle_unique_with_groups(flt, nGTflt);
971 : break;
972 0 : case TYPE_dbl:
973 0 : shuffle_unique_with_groups(dbl, nGTdbl);
974 : break;
975 0 : default:
976 0 : heapify(nGTanygrp, SWAP2);
977 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
978 0 : i = canditer_next(&ci);
979 0 : if (gv[j] < goids[0]
980 0 : || (gv[j] == goids[0]
981 0 : && cmp(BUNtail(*bi, oids[0] - hseq), nil) != 0
982 0 : && (cmp(BUNtail(*bi, i - hseq), nil) == 0
983 0 : || cmp(BUNtail(*bi, i - hseq),
984 0 : BUNtail(*bi, oids[0] - hseq)) > 0))) {
985 0 : oids[0] = i;
986 0 : goids[0] = gv[j];
987 0 : siftdown(nGTanygrp, 0, SWAP2);
988 : }
989 0 : j++;
990 : }
991 : break;
992 : }
993 : }
994 432 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
995 432 : if (lastp)
996 259 : *lastp = oids[0];
997 432 : if (lastgp)
998 259 : *lastgp = goids[0];
999 432 : GDKfree(goids);
1000 : /* output must be sorted since it's a candidate list */
1001 432 : GDKqsort(oids, NULL, NULL, (size_t) n, sizeof(oid), 0, TYPE_oid, false, false);
1002 432 : bn->tsorted = true;
1003 432 : bn->trevsorted = n <= 1;
1004 432 : bn->tkey = true;
1005 432 : bn->tseqbase = n <= 1 ? oids[0] : oid_nil;
1006 432 : bn->tnil = false;
1007 432 : bn->tnonil = true;
1008 432 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1009 : ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
1010 : " (" LLFMT " usec)\n",
1011 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
1012 : ALGOOPTBATPAR(bn), GDKusec() - t0);
1013 : return bn;
1014 :
1015 0 : bailout:
1016 0 : GDKfree(goids);
1017 0 : BBPreclaim(bn);
1018 0 : return NULL;
1019 : }
1020 :
1021 : static gdk_return
1022 210 : BATfirstn_grouped(BAT **topn, BAT **gids, BATiter *bi, BAT *s, BUN n, bool asc, bool nilslast, bool distinct, lng t0)
1023 : {
1024 210 : BAT *bn, *gn = NULL, *su = NULL;
1025 210 : oid last;
1026 210 : gdk_return rc;
1027 :
1028 210 : MT_thread_setalgorithm(__func__);
1029 210 : if (distinct && !bi->key) {
1030 0 : su = s;
1031 0 : s = BATunique(bi->b, s);
1032 0 : if (s == NULL)
1033 : return GDK_FAIL;
1034 : }
1035 210 : bn = BATfirstn_unique(bi, s, n, asc, nilslast, &last, t0);
1036 210 : if (bn == NULL)
1037 : return GDK_FAIL;
1038 210 : if (BATcount(bn) == 0) {
1039 0 : if (gids) {
1040 0 : gn = BATdense(0, 0, 0);
1041 0 : if (gn == NULL) {
1042 0 : BBPunfix(bn->batCacheid);
1043 0 : return GDK_FAIL;
1044 : }
1045 0 : *gids = gn;
1046 : }
1047 0 : *topn = bn;
1048 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1049 : ",n=" BUNFMT " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1050 : " (empty -- " LLFMT " usec)\n",
1051 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
1052 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1053 0 : return GDK_SUCCEED;
1054 : }
1055 210 : if (!bi->key) {
1056 184 : if (distinct) {
1057 0 : BAT *bn1;
1058 :
1059 0 : bn1 = bn;
1060 0 : BBPunfix(s->batCacheid);
1061 0 : bn = BATintersect(bi->b, bi->b, su, bn1, true, false, BUN_NONE);
1062 0 : BBPunfix(bn1->batCacheid);
1063 0 : if (bn == NULL)
1064 : return GDK_FAIL;
1065 184 : } else if (last != oid_nil) {
1066 94 : BAT *bn1, *bn2;
1067 :
1068 94 : bn1 = bn;
1069 94 : bn2 = BATselect(bi->b, s, BUNtail(*bi, last - bi->b->hseqbase), NULL, true, false, false);
1070 94 : if (bn2 == NULL) {
1071 0 : BBPunfix(bn1->batCacheid);
1072 0 : return GDK_FAIL;
1073 : }
1074 94 : bn = BATmergecand(bn1, bn2);
1075 94 : BBPunfix(bn1->batCacheid);
1076 94 : BBPunfix(bn2->batCacheid);
1077 94 : if (bn == NULL)
1078 : return GDK_FAIL;
1079 : }
1080 : }
1081 210 : if (gids) {
1082 210 : BAT *bn1, *bn2, *bn3, *bn4;
1083 210 : bn1 = BATproject(bn, bi->b);
1084 210 : if (bn1 == NULL) {
1085 0 : BBPunfix(bn->batCacheid);
1086 0 : return GDK_FAIL;
1087 : }
1088 210 : rc = BATsort(NULL, &bn2, &bn3, bn1, NULL, NULL, !asc, !asc, false);
1089 210 : BBPunfix(bn1->batCacheid);
1090 210 : if (rc != GDK_SUCCEED) {
1091 0 : BBPunfix(bn->batCacheid);
1092 0 : return GDK_FAIL;
1093 : }
1094 210 : rc = BATsort(NULL, &bn4, NULL, bn2, NULL, NULL, false, false, false);
1095 210 : BBPunfix(bn2->batCacheid);
1096 210 : if (rc != GDK_SUCCEED) {
1097 0 : BBPunfix(bn->batCacheid);
1098 0 : BBPunfix(bn3->batCacheid);
1099 0 : return GDK_FAIL;
1100 : }
1101 210 : gn = BATproject(bn4, bn3);
1102 210 : BBPunfix(bn3->batCacheid);
1103 210 : BBPunfix(bn4->batCacheid);
1104 210 : if (gn == NULL) {
1105 0 : BBPunfix(bn->batCacheid);
1106 0 : return GDK_FAIL;
1107 : }
1108 210 : *gids = gn;
1109 210 : assert(BATcount(gn) == BATcount(bn));
1110 : }
1111 210 : *topn = bn;
1112 210 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1113 : ",n=" BUNFMT " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1114 : " (" LLFMT " usec)\n",
1115 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
1116 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1117 : return GDK_SUCCEED;
1118 : }
1119 :
1120 : static gdk_return
1121 275 : BATfirstn_grouped_with_groups(BAT **topn, BAT **gids, BATiter *bi, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, bool distinct, lng t0)
1122 : {
1123 275 : BAT *bn, *gn = NULL;
1124 275 : oid hseq = bi->b->hseqbase;
1125 275 : oid last, lastg;
1126 275 : gdk_return rc;
1127 :
1128 275 : MT_thread_setalgorithm(__func__);
1129 275 : if (distinct) {
1130 0 : BAT *bn1, *bn2, *bn3, *bn4, *bn5, *bn6, *bn7;
1131 0 : if (BATgroup(&bn1, &bn2, NULL, bi->b, s, g, NULL, NULL) != GDK_SUCCEED)
1132 0 : return GDK_FAIL;
1133 0 : bn3 = BATproject(bn2, bi->b);
1134 0 : if (bn3 == NULL) {
1135 0 : BBPunfix(bn1->batCacheid);
1136 0 : BBPunfix(bn2->batCacheid);
1137 0 : return GDK_FAIL;
1138 : }
1139 0 : bn4 = BATintersect(s, bn2, NULL, NULL, false, false, BUN_NONE);
1140 0 : BBPunfix(bn2->batCacheid);
1141 0 : if (bn4 == NULL) {
1142 0 : BBPunfix(bn1->batCacheid);
1143 0 : return GDK_FAIL;
1144 : }
1145 0 : bn5 = BATproject(bn4, g);
1146 0 : BBPunfix(bn4->batCacheid);
1147 0 : if (bn5 == NULL) {
1148 0 : BBPunfix(bn1->batCacheid);
1149 0 : return GDK_FAIL;
1150 : }
1151 0 : BATiter bn3i = bat_iterator(bn3);
1152 0 : bn6 = BATfirstn_unique_with_groups(&bn3i, NULL, bn5, n, asc, nilslast, NULL, NULL, t0);
1153 0 : bat_iterator_end(&bn3i);
1154 0 : BBPunfix(bn3->batCacheid);
1155 0 : BBPunfix(bn5->batCacheid);
1156 0 : if (bn6 == NULL) {
1157 0 : BBPunfix(bn1->batCacheid);
1158 0 : return GDK_FAIL;
1159 : }
1160 0 : rc = BATleftjoin(&bn7, NULL, bn1, bn6, NULL, NULL, false, BUN_NONE);
1161 0 : BBPunfix(bn6->batCacheid);
1162 0 : if (rc != GDK_SUCCEED)
1163 : return GDK_FAIL;
1164 0 : bn = BATproject(bn7, s);
1165 0 : BBPunfix(bn7->batCacheid);
1166 0 : if (bn == NULL)
1167 : return GDK_FAIL;
1168 : } else {
1169 275 : bn = BATfirstn_unique_with_groups(bi, s, g, n, asc, nilslast, &last, &lastg, t0);
1170 275 : if (bn == NULL)
1171 : return GDK_FAIL;
1172 : }
1173 275 : if (BATcount(bn) == 0) {
1174 0 : if (gids) {
1175 0 : gn = BATdense(0, 0, 0);
1176 0 : if (gn == NULL) {
1177 0 : BBPunfix(bn->batCacheid);
1178 0 : return GDK_FAIL;
1179 : }
1180 0 : *gids = gn;
1181 : }
1182 0 : *topn = bn;
1183 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1184 : ",g=" ALGOBATFMT ",n=" BUNFMT
1185 : " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1186 : " (empty -- " LLFMT " usec)\n",
1187 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
1188 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1189 0 : return GDK_SUCCEED;
1190 : }
1191 275 : if (!distinct && !bi->key) {
1192 256 : BAT *bn1, *bn2, *bn3, *bn4;
1193 :
1194 256 : bn1 = bn;
1195 256 : bn2 = BATselect(g, NULL, &lastg, NULL, true, false, false);
1196 256 : if (bn2 == NULL) {
1197 0 : BBPunfix(bn1->batCacheid);
1198 0 : return GDK_FAIL;
1199 : }
1200 256 : bn3 = BATproject(bn2, s);
1201 256 : BBPunfix(bn2->batCacheid);
1202 256 : if (bn3 == NULL) {
1203 0 : BBPunfix(bn1->batCacheid);
1204 0 : return GDK_FAIL;
1205 : }
1206 256 : bn4 = BATselect(bi->b, bn3, BUNtail(*bi, last - hseq), NULL, true, false, false);
1207 256 : BBPunfix(bn3->batCacheid);
1208 256 : if (bn4 == NULL) {
1209 0 : BBPunfix(bn1->batCacheid);
1210 0 : return GDK_FAIL;
1211 : }
1212 256 : bn = BATmergecand(bn1, bn4);
1213 256 : BBPunfix(bn1->batCacheid);
1214 256 : BBPunfix(bn4->batCacheid);
1215 256 : if (bn == NULL)
1216 : return GDK_FAIL;
1217 : }
1218 275 : if (gids) {
1219 275 : BAT *bn1, *bn2, *bn3, *bn4, *bn5, *bn6, *bn7, *bn8;
1220 :
1221 275 : if ((bn1 = BATintersect(s, bn, NULL, NULL, false, false, BUN_NONE)) == NULL) {
1222 0 : BBPunfix(bn->batCacheid);
1223 0 : return GDK_FAIL;
1224 : }
1225 275 : bn2 = BATproject(bn1, g);
1226 275 : BBPunfix(bn1->batCacheid);
1227 275 : if (bn2 == NULL) {
1228 0 : BBPunfix(bn->batCacheid);
1229 0 : return GDK_FAIL;
1230 : }
1231 275 : bn3 = BATproject(bn, bi->b);
1232 275 : if (bn3 == NULL) {
1233 0 : BBPunfix(bn2->batCacheid);
1234 0 : return GDK_FAIL;
1235 : }
1236 275 : rc = BATsort(NULL, &bn4, &bn5, bn2, NULL, NULL, false, false, false);
1237 275 : BBPunfix(bn2->batCacheid);
1238 275 : if (rc != GDK_SUCCEED) {
1239 0 : BBPunfix(bn->batCacheid);
1240 0 : BBPunfix(bn3->batCacheid);
1241 0 : return GDK_FAIL;
1242 : }
1243 275 : rc = BATsort(NULL, &bn6, &bn7, bn3, bn4, bn5, !asc, !asc, false);
1244 275 : BBPunfix(bn3->batCacheid);
1245 275 : BBPunfix(bn4->batCacheid);
1246 275 : BBPunfix(bn5->batCacheid);
1247 275 : if (rc != GDK_SUCCEED) {
1248 0 : BBPunfix(bn->batCacheid);
1249 0 : return GDK_FAIL;
1250 : }
1251 275 : rc = BATsort(NULL, &bn8, NULL, bn6, NULL, NULL, false, false, false);
1252 275 : BBPunfix(bn6->batCacheid);
1253 275 : if (rc != GDK_SUCCEED) {
1254 0 : BBPunfix(bn->batCacheid);
1255 0 : BBPunfix(bn7->batCacheid);
1256 0 : return GDK_FAIL;
1257 : }
1258 275 : gn = BATproject(bn8, bn7);
1259 275 : BBPunfix(bn7->batCacheid);
1260 275 : BBPunfix(bn8->batCacheid);
1261 275 : if (gn == NULL) {
1262 0 : BBPunfix(bn->batCacheid);
1263 0 : return GDK_FAIL;
1264 : }
1265 275 : *gids = gn;
1266 275 : assert(BATcount(gn) == BATcount(bn));
1267 : }
1268 275 : *topn = bn;
1269 275 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1270 : ",g=" ALGOBATFMT ",n=" BUNFMT
1271 : " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1272 : " (" LLFMT " usec)\n",
1273 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
1274 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1275 : return GDK_SUCCEED;
1276 : }
1277 :
1278 : gdk_return
1279 1269 : BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, bool distinct)
1280 : {
1281 1269 : lng t0 = 0;
1282 1269 : gdk_return rc = GDK_SUCCEED;
1283 :
1284 1269 : assert(topn != NULL);
1285 1269 : if (b == NULL) {
1286 0 : *topn = NULL;
1287 0 : return GDK_SUCCEED;
1288 : }
1289 :
1290 1269 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
1291 :
1292 1269 : (void) BATordered(b);
1293 1269 : (void) BATordered_rev(b);
1294 :
1295 1269 : BATiter bi = bat_iterator(b);
1296 :
1297 : /* if g specified, then so must s */
1298 1269 : assert(g == NULL || s != NULL);
1299 : /* g and s must be aligned (same size, same hseqbase) */
1300 1269 : assert(g == NULL || BATcount(s) == BATcount(g));
1301 492 : assert(g == NULL || BATcount(g) == 0 || s->hseqbase == g->hseqbase);
1302 :
1303 1269 : if (n == 0 || BATcount(b) == 0 || (s != NULL && BATcount(s) == 0)) {
1304 : /* trivial: empty result */
1305 59 : *topn = BATdense(0, 0, 0);
1306 59 : if (*topn == NULL) {
1307 : rc = GDK_FAIL;
1308 59 : } else if (gids) {
1309 25 : *gids = BATdense(0, 0, 0);
1310 25 : if (*gids == NULL) {
1311 0 : BBPreclaim(*topn);
1312 : rc = GDK_FAIL;
1313 : }
1314 : }
1315 1210 : } else if (g == NULL) {
1316 741 : if (gids == NULL && !distinct) {
1317 531 : *topn = BATfirstn_unique(&bi, s, n, asc, nilslast, NULL, t0);
1318 531 : rc = *topn ? GDK_SUCCEED : GDK_FAIL;
1319 : } else {
1320 210 : rc = BATfirstn_grouped(topn, gids, &bi, s, n, asc, nilslast, distinct, t0);
1321 : }
1322 469 : } else if (gids == NULL && !distinct) {
1323 194 : *topn = BATfirstn_unique_with_groups(&bi, s, g, n, asc, nilslast, NULL, NULL, t0);
1324 194 : rc = *topn ? GDK_SUCCEED : GDK_FAIL;
1325 : } else {
1326 275 : rc = BATfirstn_grouped_with_groups(topn, gids, &bi, s, g, n, asc, nilslast, distinct, t0);
1327 : }
1328 1269 : bat_iterator_end(&bi);
1329 1269 : return rc;
1330 : }
|
