LCOV - code coverage report
Current view: top level - gdk - gdk_batop.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 1271 1649 77.1 %
Date: 2021-09-14 19:48:19 Functions: 26 27 96.3 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : /*
      10             :  * (c) M. L. Kersten, P. Boncz, S. Manegold, N. Nes, K.S. Mullender
      11             :  * Common BAT Operations
      12             :  * We factor out all possible overhead by inlining code.  This
      13             :  * includes the macros BUNhead and BUNtail, which do a test to see
      14             :  * whether the atom resides in the buns or in a variable storage
      15             :  * heap.
      16             :  */
      17             : #include "monetdb_config.h"
      18             : #include "gdk.h"
      19             : #include "gdk_private.h"
      20             : 
      21             : gdk_return
      22    49477514 : unshare_varsized_heap(BAT *b)
      23             : {
      24    49477514 :         if (ATOMvarsized(b->ttype) &&
      25    20890026 :             b->tvheap->parentid != b->batCacheid) {
      26         530 :                 Heap *h = GDKmalloc(sizeof(Heap));
      27         531 :                 if (h == NULL)
      28             :                         return GDK_FAIL;
      29         531 :                 MT_thread_setalgorithm("unshare vheap");
      30         530 :                 *h = (Heap) {
      31         530 :                         .parentid = b->batCacheid,
      32         531 :                         .farmid = BBPselectfarm(b->batRole, TYPE_str, varheap),
      33             :                 };
      34         530 :                 strconcat_len(h->filename, sizeof(h->filename),
      35         530 :                               BBP_physical(b->batCacheid), ".theap", NULL);
      36         531 :                 if (HEAPcopy(h, b->tvheap, 0) != GDK_SUCCEED) {
      37           0 :                         HEAPfree(h, true);
      38           0 :                         GDKfree(h);
      39           0 :                         return GDK_FAIL;
      40             :                 }
      41         530 :                 ATOMIC_INIT(&h->refs, 1);
      42         530 :                 MT_lock_set(&b->theaplock);
      43         531 :                 int parent = b->tvheap->parentid;
      44         531 :                 HEAPdecref(b->tvheap, false);
      45         531 :                 b->tvheap = h;
      46         531 :                 MT_lock_unset(&b->theaplock);
      47         531 :                 BBPunshare(parent);
      48         531 :                 BBPunfix(parent);
      49             :         }
      50             :         return GDK_SUCCEED;
      51             : }
      52             : 
      53             : /* We try to be clever when appending one string bat to another.
      54             :  * First of all, we try to actually share the string heap so that we
      55             :  * don't need an extra copy, and if that can't be done, we see whether
      56             :  * it makes sense to just quickly copy the whole string heap instead
      57             :  * of inserting individual strings.  See the comments in the code for
      58             :  * more information. */
      59             : static gdk_return
      60      160283 : insert_string_bat(BAT *b, BAT *n, struct canditer *ci, bool force, bool mayshare)
      61             : {
      62             :         BATiter ni;             /* iterator */
      63             :         size_t toff = ~(size_t) 0;      /* tail offset */
      64             :         BUN p, r;               /* loop variables */
      65             :         const void *tp = NULL;  /* tail value pointer */
      66             :         unsigned char tbv;      /* tail value-as-bte */
      67             :         unsigned short tsv;     /* tail value-as-sht */
      68             : #if SIZEOF_VAR_T == 8
      69             :         unsigned int tiv;       /* tail value-as-int */
      70             : #endif
      71             :         var_t v;                /* value */
      72             :         size_t off;             /* offset within n's string heap */
      73      160283 :         BUN cnt = ci->ncand;
      74      160283 :         BUN oldcnt = BATcount(b);
      75             : 
      76      160283 :         assert(b->ttype == TYPE_str);
      77      160283 :         assert(b->tbaseoff == 0);
      78      160283 :         assert(b->theap->parentid == b->batCacheid);
      79             :         /* only transient bats can use some other bat's string heap */
      80      160283 :         assert(b->batRole == TRANSIENT || b->tvheap->parentid == b->batCacheid);
      81      160283 :         if (cnt == 0)
      82             :                 return GDK_SUCCEED;
      83      160595 :         ni = bat_iterator(n);
      84             : 
      85      161239 :         if (b->tvheap == ni.vh) {
      86             :                 /* vheaps are already shared, continue doing so: we just
      87             :                  * need to append the offsets */
      88             :                 toff = 0;
      89       16958 :                 MT_thread_setalgorithm("shared vheap");
      90      144281 :         } else if (mayshare && b->batRole == TRANSIENT && oldcnt == 0) {
      91             :                 /* we can share the vheaps, so we then only need to
      92             :                  * append the offsets */
      93      129981 :                 MT_lock_set(&b->theaplock);
      94      130653 :                 if (b->tvheap->parentid != b->batCacheid)
      95           0 :                         BBPunshare(b->tvheap->parentid);
      96      130653 :                 HEAPdecref(b->tvheap, b->tvheap->parentid == b->batCacheid);
      97      130671 :                 HEAPincref(ni.vh);
      98      130701 :                 b->tvheap = ni.vh;
      99      130701 :                 BBPshare(ni.vh->parentid);
     100      130548 :                 b->batDirtydesc = true;
     101      130548 :                 MT_lock_unset(&b->theaplock);
     102             :                 toff = 0;
     103      130705 :                 MT_thread_setalgorithm("share vheap");
     104             :         } else {
     105             :                 /* no heap sharing, so also make sure the heap isn't
     106             :                  * shared currently (we're not allowed to write in
     107             :                  * another bat's heap) */
     108       14831 :                 if (b->tvheap->parentid != b->batCacheid &&
     109         531 :                     unshare_varsized_heap(b) != GDK_SUCCEED) {
     110           0 :                         bat_iterator_end(&ni);
     111           0 :                         return GDK_FAIL;
     112             :                 }
     113       14300 :                 if (oldcnt == 0 || (!GDK_ELIMDOUBLES(b->tvheap) &&
     114         103 :                                     !GDK_ELIMDOUBLES(ni.vh) &&
     115          69 :                                     b->tvheap->hashash == ni.vh->hashash)) {
     116             :                         /* we'll consider copying the string heap completely
     117             :                          *
     118             :                          * we first estimate how much space the string heap
     119             :                          * should occupy, given the number of rows we need to
     120             :                          * insert, then, if that is way smaller than the actual
     121             :                          * space occupied, we will skip the copy and just insert
     122             :                          * one by one */
     123             :                         size_t len = 0;
     124     4346739 :                         for (int i = 0; i < 1024; i++) {
     125     4342419 :                                 p = (BUN) (((double) rand() / RAND_MAX) * (cnt - 1));
     126     4341493 :                                 p = canditer_idx(ci, p) - n->hseqbase;
     127     4342472 :                                 len += strlen(BUNtvar(ni, p)) + 1;
     128             :                         }
     129        4320 :                         len = (len + 512) / 1024; /* rounded average length */
     130        4320 :                         r = (GDK_ELIMLIMIT - GDK_STRHASHSIZE) / (len + 12);
     131             :                         /* r is estimate of number of strings in
     132             :                          * double-eliminated area */
     133        4320 :                         if (r < ci->ncand)
     134         764 :                                 len = GDK_ELIMLIMIT + (ci->ncand - r) * len;
     135             :                         else
     136        3556 :                                 len = GDK_STRHASHSIZE + ci->ncand * (len + 12);
     137             :                         /* len is total estimated expected size of vheap */
     138             : 
     139        4320 :                         if (len > ni.vhfree / 2) {
     140             :                                 /* we copy the string heap, perhaps appending */
     141        4283 :                                 if (oldcnt == 0) {
     142             :                                         toff = 0;
     143        4240 :                                         MT_thread_setalgorithm("copy vheap");
     144             :                                 } else {
     145          43 :                                         toff = (b->tvheap->free + GDK_VARALIGN - 1) & ~(GDK_VARALIGN - 1);
     146          43 :                                         MT_thread_setalgorithm("append vheap");
     147             :                                 }
     148             : 
     149        4283 :                                 if (HEAPgrow(&b->theaplock, &b->tvheap, toff + ni.vh->size, force) != GDK_SUCCEED) {
     150           0 :                                         bat_iterator_end(&ni);
     151           0 :                                         return GDK_FAIL;
     152             :                                 }
     153        4281 :                                 memcpy(b->tvheap->base + toff, ni.vh->base, ni.vhfree);
     154        4281 :                                 b->tvheap->free = toff + ni.vhfree;
     155             :                         }
     156             :                 }
     157             :         }
     158             :         /* if toff has the initial value of ~0, we insert strings
     159             :          * individually, otherwise we only copy (insert) offsets */
     160             :         if (toff == ~(size_t) 0)
     161             :                 v = GDK_VAROFFSET;
     162             :         else
     163      151191 :                 v = b->tvheap->free - 1;
     164             : 
     165             :         /* make sure there is (vertical) space in the offset heap, we
     166             :          * may also widen thanks to v, set above */
     167      161261 :         if (GDKupgradevarheap(b, v, oldcnt + cnt < b->batCapacity ? b->batCapacity : oldcnt + cnt, b->batCount) != GDK_SUCCEED) {
     168           0 :                 bat_iterator_end(&ni);
     169           0 :                 return GDK_FAIL;
     170             :         }
     171             : 
     172      161437 :         if (toff == 0 && ni.width == b->twidth && ci->tpe == cand_dense) {
     173             :                 /* we don't need to do any translation of offset
     174             :                  * values, so we can use fast memcpy */
     175      150743 :                 MT_thread_setalgorithm("memcpy offsets");
     176      151156 :                 memcpy(Tloc(b, BUNlast(b)), (const char *) ni.base + ((ci->seq - n->hseqbase) << ni.shift), cnt << ni.shift);
     177       10694 :         } else if (toff != ~(size_t) 0) {
     178             :                 /* we don't need to insert any actual strings since we
     179             :                  * have already made sure that they are all in b's
     180             :                  * string heap at known locations (namely the offset
     181             :                  * in n added to toff), so insert offsets from n after
     182             :                  * adding toff into b */
     183             :                 /* note the use of the "restrict" qualifier here: all
     184             :                  * four pointers below point to the same value, but
     185             :                  * only one of them will actually be used, hence we
     186             :                  * still obey the rule for restrict-qualified
     187             :                  * pointers */
     188         636 :                 const unsigned char *restrict tbp = (const unsigned char *) ni.base;
     189             :                 const unsigned short *restrict tsp = (const unsigned short *) ni.base;
     190             : #if SIZEOF_VAR_T == 8
     191             :                 const unsigned int *restrict tip = (const unsigned int *) ni.base;
     192             : #endif
     193             :                 const var_t *restrict tvp = (const var_t *) ni.base;
     194             : 
     195         636 :                 switch (b->twidth) {
     196             :                 case 1:
     197             :                         tp = &tbv;
     198             :                         break;
     199             :                 case 2:
     200             :                         tp = &tsv;
     201             :                         break;
     202             : #if SIZEOF_VAR_T == 8
     203             :                 case 4:
     204             :                         tp = &tiv;
     205             :                         break;
     206             :                 case 8:
     207             :                         tp = &v;
     208             :                         break;
     209             : #else
     210             :                 case 4:
     211             :                         tp = &v;
     212             :                         break;
     213             : #endif
     214             :                 default:
     215           0 :                         assert(0);
     216             :                 }
     217         636 :                 MT_thread_setalgorithm("copy offset values");
     218         636 :                 r = b->batCount;
     219     3635655 :                 while (cnt > 0) {
     220     3635019 :                         cnt--;
     221     3635019 :                         p = canditer_next(ci) - n->hseqbase;
     222     3635019 :                         switch (ni.width) {
     223         485 :                         case 1:
     224         485 :                                 v = (var_t) tbp[p] + GDK_VAROFFSET;
     225         485 :                                 break;
     226        9145 :                         case 2:
     227        9145 :                                 v = (var_t) tsp[p] + GDK_VAROFFSET;
     228        9145 :                                 break;
     229             : #if SIZEOF_VAR_T == 8
     230     3625488 :                         case 4:
     231     3625488 :                                 v = (var_t) tip[p];
     232     3625488 :                                 break;
     233             : #endif
     234           0 :                         default:
     235           0 :                                 v = tvp[p];
     236           0 :                                 break;
     237             :                         }
     238     3635019 :                         v = (var_t) ((size_t) v + toff);
     239     3635019 :                         assert(v >= GDK_VAROFFSET);
     240     3635019 :                         assert((size_t) v < b->tvheap->free);
     241     3635019 :                         switch (b->twidth) {
     242        9145 :                         case 1:
     243        9145 :                                 assert(v - GDK_VAROFFSET < ((var_t) 1 << 8));
     244        9145 :                                 ((uint8_t *) b->theap->base)[r++] = (uint8_t) (v - GDK_VAROFFSET);
     245        9145 :                                 break;
     246         485 :                         case 2:
     247         485 :                                 assert(v - GDK_VAROFFSET < ((var_t) 1 << 16));
     248         485 :                                 ((uint16_t *) b->theap->base)[r++] = (uint16_t) (v - GDK_VAROFFSET);
     249         485 :                                 break;
     250             : #if SIZEOF_VAR_T == 8
     251     3625389 :                         case 4:
     252     3625389 :                                 assert(v < ((var_t) 1 << 32));
     253     3625389 :                                 ((uint32_t *) b->theap->base)[r++] = (uint32_t) v;
     254     3625389 :                                 break;
     255             : #endif
     256           0 :                         default:
     257           0 :                                 ((var_t *) b->theap->base)[r++] = v;
     258           0 :                                 break;
     259             :                         }
     260             :                 }
     261       10058 :         } else if (b->tvheap->free < ni.vhfree / 2 ||
     262             :                    GDK_ELIMDOUBLES(b->tvheap)) {
     263             :                 /* if b's string heap is much smaller than n's string
     264             :                  * heap, don't bother checking whether n's string
     265             :                  * values occur in b's string heap; also, if b is
     266             :                  * (still) fully double eliminated, we must continue
     267             :                  * to use the double elimination mechanism */
     268        9998 :                 r = b->batCount;
     269        9998 :                 oid hseq = n->hseqbase;
     270        9998 :                 MT_thread_setalgorithm("insert string values");
     271     7206252 :                 while (cnt > 0) {
     272     7196232 :                         cnt--;
     273     7196232 :                         p = canditer_next(ci) - hseq;
     274     7092918 :                         tp = BUNtvar(ni, p);
     275     7092918 :                         if (tfastins_nocheckVAR(b, r, tp) != GDK_SUCCEED) {
     276           0 :                                 bat_iterator_end(&ni);
     277           0 :                                 return GDK_FAIL;
     278             :                         }
     279     7196229 :                         r++;
     280             :                 }
     281             :         } else {
     282             :                 /* Insert values from n individually into b; however,
     283             :                  * we check whether there is a string in b's string
     284             :                  * heap at the same offset as the string is in n's
     285             :                  * string heap (in case b's string heap is a copy of
     286             :                  * n's).  If this is the case, we just copy the
     287             :                  * offset, otherwise we insert normally.  */
     288          60 :                 r = b->batCount;
     289          60 :                 MT_thread_setalgorithm("insert string values with check");
     290       97608 :                 while (cnt > 0) {
     291       97548 :                         cnt--;
     292       97548 :                         p = canditer_next(ci) - n->hseqbase;
     293       97548 :                         off = BUNtvaroff(ni, p); /* the offset */
     294       97548 :                         tp = ni.vh->base + off; /* the string */
     295       97548 :                         if (off < b->tvheap->free &&
     296       97548 :                             strcmp(b->tvheap->base + off, tp) == 0 &&
     297       90726 :                             (!b->tvheap->hashash ||
     298           0 :                              ((BUN *) (b->tvheap->base + off))[-1] == (ni.vh->hashash ? ((BUN *) tp)[-1] : strHash(tp)))) {
     299             :                                 /* we found the string at the same
     300             :                                  * offset in b's string heap as it was
     301             :                                  * in n's string heap, so we don't
     302             :                                  * have to insert a new string into b:
     303             :                                  * we can just copy the offset */
     304             :                                 v = (var_t) off;
     305       90726 :                                 switch (b->twidth) {
     306           0 :                                 case 1:
     307           0 :                                         assert(v - GDK_VAROFFSET < ((var_t) 1 << 8));
     308           0 :                                         ((uint8_t *) b->theap->base)[r] = (unsigned char) (v - GDK_VAROFFSET);
     309           0 :                                         break;
     310           0 :                                 case 2:
     311           0 :                                         assert(v - GDK_VAROFFSET < ((var_t) 1 << 16));
     312           0 :                                         ((uint16_t *) b->theap->base)[r] = (unsigned short) (v - GDK_VAROFFSET);
     313           0 :                                         break;
     314             : #if SIZEOF_VAR_T == 8
     315       90726 :                                 case 4:
     316       90726 :                                         assert(v < ((var_t) 1 << 32));
     317       90726 :                                         ((uint32_t *) b->theap->base)[r] = (unsigned int) v;
     318       90726 :                                         break;
     319             : #endif
     320           0 :                                 default:
     321           0 :                                         ((var_t *) b->theap->base)[r] = v;
     322           0 :                                         break;
     323             :                                 }
     324             :                         } else {
     325        6822 :                                 if (tfastins_nocheckVAR(b, r, tp) != GDK_SUCCEED) {
     326           0 :                                         bat_iterator_end(&ni);
     327           0 :                                         return GDK_FAIL;
     328             :                                 }
     329             :                         }
     330       97548 :                         r++;
     331             :                 }
     332             :         }
     333      161872 :         BATsetcount(b, oldcnt + ci->ncand);
     334      162016 :         bat_iterator_end(&ni);
     335      161823 :         assert(b->batCapacity >= b->batCount);
     336             :         /* maintain hash */
     337      161823 :         MT_rwlock_wrlock(&b->thashlock);
     338      161996 :         for (r = oldcnt, cnt = BATcount(b); b->thash && r < cnt; r++) {
     339         123 :                 HASHappend_locked(b, r, b->tvheap->base + VarHeapVal(Tloc(b, 0), r, b->twidth));
     340             :         }
     341      161873 :         MT_rwlock_wrunlock(&b->thashlock);
     342      161978 :         return GDK_SUCCEED;
     343             : }
     344             : 
     345             : static gdk_return
     346         337 : append_varsized_bat(BAT *b, BAT *n, struct canditer *ci, bool mayshare)
     347             : {
     348             :         BATiter ni;
     349         337 :         BUN cnt = ci->ncand, r;
     350         337 :         oid hseq = n->hseqbase;
     351             : 
     352             :         /* only transient bats can use some other bat's vheap */
     353         337 :         assert(b->batRole == TRANSIENT || b->tvheap->parentid == b->batCacheid);
     354             :         /* make sure the bats use var_t */
     355         337 :         assert(b->twidth == n->twidth);
     356         337 :         assert(b->twidth == SIZEOF_VAR_T);
     357         337 :         if (cnt == 0)
     358             :                 return GDK_SUCCEED;
     359         337 :         if (cnt > BATcapacity(b) - BATcount(b)) {
     360             :                 /* if needed space exceeds a normal growth extend just
     361             :                  * with what's needed */
     362           5 :                 BUN ncap = BATcount(b) + cnt;
     363           5 :                 BUN grows = BATgrows(b);
     364             : 
     365             :                 if (ncap > grows)
     366             :                         grows = ncap;
     367           5 :                 if (BATextend(b, grows) != GDK_SUCCEED)
     368             :                         return GDK_FAIL;
     369             :         }
     370         337 :         ni = bat_iterator(n);
     371         336 :         if (mayshare &&
     372         338 :             BATcount(b) == 0 &&
     373         163 :             b->batRole == TRANSIENT &&
     374          98 :             n->batRestricted == BAT_READ &&
     375          98 :             b->tvheap != ni.vh) {
     376             :                 /* if b is still empty, in the transient farm, and n
     377             :                  * is read-only, we replace b's vheap with a reference
     378             :                  * to n's */
     379             :                 /* make sure locking happens in a predictable order:
     380             :                  * lowest id first */
     381          98 :                 MT_lock_set(&b->theaplock);
     382          99 :                 if (b->tvheap->parentid != b->batCacheid)
     383           0 :                         BBPunshare(b->tvheap->parentid);
     384          99 :                 BBPshare(ni.vh->parentid);
     385          99 :                 HEAPdecref(b->tvheap, true);
     386          99 :                 HEAPincref(ni.vh);
     387          99 :                 b->tvheap = ni.vh;
     388          99 :                 b->batDirtydesc = true;
     389          99 :                 MT_lock_unset(&b->theaplock);
     390             :         }
     391         337 :         if (b->tvheap == ni.vh) {
     392             :                 /* if b and n use the same vheap, we only need to copy
     393             :                  * the offsets from n to b */
     394         229 :                 if (ci->tpe == cand_dense) {
     395             :                         /* fast memcpy since we copy a consecutive
     396             :                          * chunk of memory */
     397         229 :                         memcpy(Tloc(b, BUNlast(b)),
     398         229 :                                (const var_t *) ni.base + (ci->seq - hseq),
     399         229 :                                cnt << b->tshift);
     400             :                 } else {
     401           0 :                         var_t *restrict dst = (var_t *) Tloc(b, BUNlast(b));
     402           0 :                         const var_t *restrict src = (const var_t *) ni.base;
     403           0 :                         while (cnt > 0) {
     404           0 :                                 cnt--;
     405           0 :                                 *dst++ = src[canditer_next(ci) - hseq];
     406             :                         }
     407             :                 }
     408         229 :                 BATsetcount(b, BATcount(b) + ci->ncand);
     409             :                 /* maintain hash table */
     410         230 :                 MT_rwlock_wrlock(&b->thashlock);
     411         228 :                 for (BUN i = BATcount(b) - ci->ncand;
     412         228 :                      b->thash && i < BATcount(b);
     413           0 :                      i++) {
     414           0 :                         HASHappend_locked(b, i, b->tvheap->base + *(var_t *) Tloc(b, i));
     415             :                 }
     416         229 :                 MT_rwlock_wrunlock(&b->thashlock);
     417         229 :                 bat_iterator_end(&ni);
     418         230 :                 return GDK_SUCCEED;
     419             :         }
     420             :         /* b and n do not share their vheap, so we need to copy data */
     421         108 :         if (b->tvheap->parentid != b->batCacheid) {
     422             :                 /* if b shares its vheap with some other bat, unshare it */
     423          10 :                 Heap *h = GDKmalloc(sizeof(Heap));
     424          10 :                 if (h == NULL) {
     425           0 :                         bat_iterator_end(&ni);
     426           0 :                         return GDK_FAIL;
     427             :                 }
     428          10 :                 *h = (Heap) {
     429          10 :                         .parentid = b->batCacheid,
     430          10 :                         .farmid = BBPselectfarm(b->batRole, b->ttype, varheap),
     431             :                 };
     432          10 :                 strconcat_len(h->filename, sizeof(h->filename),
     433          10 :                               BBP_physical(b->batCacheid), ".theap", NULL);
     434          10 :                 if (HEAPcopy(h, b->tvheap, 0) != GDK_SUCCEED) {
     435           0 :                         bat_iterator_end(&ni);
     436           0 :                         HEAPfree(h, true);
     437           0 :                         GDKfree(h);
     438           0 :                         return GDK_FAIL;
     439             :                 }
     440          10 :                 BBPunshare(b->tvheap->parentid);
     441          10 :                 MT_lock_set(&b->theaplock);
     442          10 :                 HEAPdecref(b->tvheap, false);
     443          10 :                 ATOMIC_INIT(&h->refs, 1);
     444          10 :                 b->tvheap = h;
     445          10 :                 MT_lock_unset(&b->theaplock);
     446             :         }
     447             :         /* copy data from n to b */
     448         108 :         r = BUNlast(b);
     449         108 :         MT_rwlock_wrlock(&b->thashlock);
     450     4200536 :         while (cnt > 0) {
     451     4200428 :                 cnt--;
     452     4200428 :                 BUN p = canditer_next(ci) - hseq;
     453     4200428 :                 const void *t = BUNtvar(ni, p);
     454     4200428 :                 if (tfastins_nocheckVAR(b, r, t) != GDK_SUCCEED) {
     455           0 :                         MT_rwlock_wrunlock(&b->thashlock);
     456           0 :                         bat_iterator_end(&ni);
     457           0 :                         return GDK_FAIL;
     458             :                 }
     459     4200428 :                 if (b->thash)
     460           0 :                         HASHappend_locked(b, r, t);
     461     4200428 :                 r++;
     462             :         }
     463         108 :         MT_rwlock_wrunlock(&b->thashlock);
     464         108 :         BATsetcount(b, r);
     465         108 :         bat_iterator_end(&ni);
     466         108 :         return GDK_SUCCEED;
     467             : }
     468             : 
     469             : static gdk_return
     470         103 : append_msk_bat(BAT *b, BAT *n, struct canditer *ci)
     471             : {
     472         103 :         if (ci->ncand == 0)
     473             :                 return GDK_SUCCEED;
     474         103 :         if (BATextend(b, BATcount(b) + ci->ncand) != GDK_SUCCEED)
     475             :                 return GDK_FAIL;
     476             : 
     477         103 :         MT_lock_set(&b->theaplock);
     478             : 
     479         103 :         uint32_t boff = b->batCount % 32;
     480         103 :         uint32_t *bp = (uint32_t *) b->theap->base + b->batCount / 32;
     481         103 :         b->batCount += ci->ncand;
     482         103 :         b->theap->dirty = true;
     483         103 :         b->theap->free = ((b->batCount + 31) / 32) * 4;
     484         103 :         BATiter ni = bat_iterator(n);
     485         103 :         if (ci->tpe == cand_dense) {
     486             :                 const uint32_t *np;
     487             :                 uint32_t noff, mask;
     488             :                 BUN cnt;
     489         103 :                 noff = (ci->seq - n->hseqbase) % 32;
     490         103 :                 cnt = ci->ncand;
     491         103 :                 np = (const uint32_t *) ni.base + (ci->seq - n->hseqbase) / 32;
     492         103 :                 if (boff == noff) {
     493             :                         /* words of b and n are aligned, so we don't
     494             :                          * need to shift bits around */
     495          42 :                         if (boff + cnt <= 32) {
     496             :                                 /* all new bits within one word */
     497          36 :                                 if (cnt == 32) {
     498           0 :                                         *bp = *np;
     499             :                                 } else {
     500          36 :                                         mask = ((1U << cnt) - 1) << boff;
     501          36 :                                         *bp &= ~mask;
     502          36 :                                         *bp |= *np & mask;
     503             :                                 }
     504             :                         } else {
     505             :                                 /* multiple words of b are affected */
     506           6 :                                 if (boff != 0) {
     507             :                                         /* first fill up the rest of the first
     508             :                                          * word */
     509           0 :                                         mask = ~0U << boff;
     510           0 :                                         *bp &= ~mask;
     511           0 :                                         *bp++ |= *np++ & mask;
     512           0 :                                         cnt -= 32 - boff;
     513             :                                 }
     514           6 :                                 if (cnt >= 32) {
     515             :                                         /* copy an integral number of words fast */
     516           6 :                                         BUN nw = cnt / 32;
     517           6 :                                         memcpy(bp, np, nw*sizeof(int));
     518           6 :                                         bp += nw;
     519           6 :                                         np += nw;
     520           6 :                                         cnt %= 32;
     521             :                                 }
     522           6 :                                 if (cnt > 0) {
     523             :                                         /* do the left over bits */
     524           6 :                                         mask = (1U << cnt) - 1;
     525           6 :                                         *bp = *np & mask;
     526             :                                 }
     527             :                         }
     528          61 :                 } else if (boff > noff) {
     529          61 :                         if (boff + cnt <= 32) {
     530             :                                 /* we only need to copy bits from a
     531             :                                  * single word of n to a single word
     532             :                                  * of b */
     533             :                                 /* boff > 0, so cnt < 32, hence the
     534             :                                  * shift is ok */
     535          39 :                                 mask = (1U << cnt) - 1;
     536          39 :                                 *bp &= ~(mask << boff);
     537          39 :                                 *bp |= (*np & (mask << noff)) << (boff - noff);
     538             :                         } else {
     539             :                                 /* first fill the rest of the last partial
     540             :                                  * word of b, so that's 32-boff bits */
     541          22 :                                 mask = (1U << (32 - boff)) - 1;
     542          22 :                                 *bp &= ~(mask << boff);
     543          22 :                                 *bp++ |= (*np & (mask << noff)) << (boff - noff);
     544          22 :                                 cnt -= 32 - boff;
     545             : 
     546             :                                 /* set boff and noff to the amount we need to
     547             :                                  * shift bits in consecutive words of n around
     548             :                                  * to fit into the next word of b; set mask to
     549             :                                  * the mask of the bottom bits of n that fit
     550             :                                  * in a word of b (and the complement are the
     551             :                                  * top bits that go to another word of b) */
     552             :                                 boff -= noff;
     553          22 :                                 noff = 32 - boff;
     554          22 :                                 mask = (1U << noff) - 1;
     555         129 :                                 while (cnt >= 32) {
     556         107 :                                         *bp = (*np++ & ~mask) >> noff;
     557         107 :                                         *bp++ |= (*np & mask) << boff;
     558         107 :                                         cnt -= 32;
     559             :                                 }
     560          22 :                                 if (cnt > boff) {
     561             :                                         /* the last bits come from two words
     562             :                                          * in n */
     563          14 :                                         *bp = (*np++ & ~mask) >> noff;
     564          14 :                                         cnt -= noff;
     565          14 :                                         mask = (1U << cnt) - 1;
     566          14 :                                         *bp++ |= (*np & mask) << boff;
     567           8 :                                 } else if (cnt > 0) {
     568             :                                         /* the last bits come from a single
     569             :                                          * word in n */
     570           8 :                                         mask = ((1U << cnt) - 1) << noff;
     571           8 :                                         *bp = (*np & mask) >> noff;
     572             :                                 }
     573             :                         }
     574             :                 } else {
     575             :                         /* boff < noff */
     576           0 :                         if (noff + cnt <= 32) {
     577             :                                 /* only need part of the first word of n */
     578           0 :                                 mask = (1U << cnt) - 1;
     579           0 :                                 *bp &= ~(mask << boff);
     580           0 :                                 *bp |= (*np & (mask << noff)) >> (noff - boff);
     581           0 :                         } else if (boff + cnt <= 32) {
     582             :                                 /* only need to fill a single word of
     583             :                                  * b, but from two of n */
     584           0 :                                 if (cnt < 32)
     585           0 :                                         *bp &= ~(((1U << cnt) - 1) << boff);
     586             :                                 else
     587           0 :                                         *bp = 0;
     588           0 :                                 mask = ~((1U << noff) - 1);
     589           0 :                                 *bp |= (*np++ & mask) >> (noff - boff);
     590           0 :                                 cnt -= 32 - noff;
     591           0 :                                 mask = (1U << cnt) - 1;
     592           0 :                                 *bp |= (*np & mask) << (32 - noff);
     593             :                         } else {
     594           0 :                                 if (boff > 0) {
     595             :                                         /* fill the rest of the first word of b */
     596           0 :                                         cnt -= 32 - boff;
     597           0 :                                         *bp &= (1U << boff) - 1;
     598           0 :                                         mask = ~((1U << noff) - 1);
     599           0 :                                         noff -= boff;
     600           0 :                                         boff = 32 - noff;
     601           0 :                                         *bp |= (*np++ & mask) >> noff;
     602           0 :                                         *bp |= (*np & ((1U << noff) - 1)) << boff;
     603             :                                 } else {
     604           0 :                                         boff = 32 - noff;
     605             :                                 }
     606           0 :                                 mask = (1U << noff) - 1;
     607           0 :                                 while (cnt >= 32) {
     608           0 :                                         *bp = (*np++ & ~mask) >> noff;
     609           0 :                                         *bp++ |= (*np & mask) << boff;
     610           0 :                                         cnt -= 32;
     611             :                                 }
     612           0 :                                 if (cnt > 0) {
     613           0 :                                         *bp = (*np++ & ~mask) >> noff;
     614           0 :                                         if (cnt > noff)
     615           0 :                                                 *bp++ |= (*np & mask) << boff;
     616             :                                 }
     617             :                         }
     618             :                 }
     619             :         } else {
     620             :                 oid o;
     621           0 :                 uint32_t v = boff > 0 ? *bp & ((1U << boff) - 1) : 0;
     622             :                 do {
     623           0 :                         for (uint32_t i = boff; i < 32; i++) {
     624           0 :                                 o = canditer_next(ci);
     625           0 :                                 if (is_oid_nil(o))
     626             :                                         break;
     627           0 :                                 o -= n->hseqbase;
     628           0 :                                 v |= (uint32_t) Tmskval(&ni, o - n->hseqbase) << i;
     629             :                         }
     630           0 :                         *bp++ = v;
     631             :                         v = 0;
     632             :                         boff = 0;
     633           0 :                 } while (!is_oid_nil(o));
     634             :         }
     635         103 :         bat_iterator_end(&ni);
     636         103 :         MT_lock_unset(&b->theaplock);
     637         103 :         return GDK_SUCCEED;
     638             : }
     639             : 
     640             : /* Append the contents of BAT n (subject to the optional candidate
     641             :  * list s) to BAT b.  If b is empty, b will get the seqbase of s if it
     642             :  * was passed in, and else the seqbase of n. */
     643             : gdk_return
     644     2250245 : BATappend2(BAT *b, BAT *n, BAT *s, bool force, bool mayshare)
     645             : {
     646             :         struct canditer ci;
     647             :         BUN cnt;
     648             :         BUN r;
     649             :         const ValRecord *prop = NULL, *nprop;
     650     2250245 :         oid hseq = n->hseqbase;
     651             :         char buf[64];
     652             :         lng t0 = 0;
     653             : 
     654     2250245 :         if (b == NULL || n == NULL || BATcount(n) == 0) {
     655             :                 return GDK_SUCCEED;
     656             :         }
     657      548909 :         assert(b->theap->parentid == b->batCacheid);
     658             : 
     659      548909 :         TRC_DEBUG_IF(ALGO) {
     660           0 :                 t0 = GDKusec();
     661           0 :                 snprintf(buf, sizeof(buf), ALGOBATFMT, ALGOBATPAR(b));
     662             :         }
     663             : 
     664      548909 :         ALIGNapp(b, force, GDK_FAIL);
     665             : 
     666     1634720 :         if (ATOMstorage(ATOMtype(b->ttype)) != ATOMstorage(ATOMtype(n->ttype))) {
     667           0 :                 GDKerror("Incompatible operands.\n");
     668           0 :                 return GDK_FAIL;
     669             :         }
     670             : 
     671      548909 :         if (BATttype(b) != BATttype(n) &&
     672             :             ATOMtype(b->ttype) != ATOMtype(n->ttype)) {
     673           0 :                 TRC_DEBUG(CHECK_, "Interpreting %s as %s.\n",
     674             :                           ATOMname(BATttype(n)), ATOMname(BATttype(b)));
     675             :         }
     676             : 
     677      548909 :         BATiter ni = bat_iterator(n);
     678             : 
     679      546620 :         cnt = canditer_init(&ci, n, s);
     680      544362 :         if (cnt == 0) {
     681           0 :                 goto doreturn;
     682             :         }
     683             : 
     684      544362 :         if (BUNlast(b) + cnt > BUN_MAX) {
     685           0 :                 bat_iterator_end(&ni);
     686           0 :                 GDKerror("combined BATs too large\n");
     687           0 :                 return GDK_FAIL;
     688             :         }
     689             : 
     690      544362 :         if (b->hseqbase + BATcount(b) + cnt >= GDK_oid_max) {
     691           0 :                 bat_iterator_end(&ni);
     692           0 :                 GDKerror("overflow of head value\n");
     693           0 :                 return GDK_FAIL;
     694             :         }
     695             : 
     696      544362 :         b->batDirtydesc = true;
     697             : 
     698      544362 :         IMPSdestroy(b);         /* imprints do not support updates yet */
     699      544512 :         OIDXdestroy(b);
     700      544125 :         if (BATcount(b) == 0 || (prop = BATgetprop(b, GDK_MAX_VALUE)) != NULL) {
     701      305015 :                 if ((nprop = BATgetprop(n, GDK_MAX_VALUE)) != NULL) {
     702        6629 :                         if (BATcount(b) == 0 || ATOMcmp(b->ttype, VALptr(prop), VALptr(nprop)) < 0) {
     703        6324 :                                 if (s == NULL) {
     704        5954 :                                         BATsetprop(b, GDK_MAX_VALUE, b->ttype, VALptr(nprop));
     705        6030 :                                         if ((nprop = BATgetprop(n, GDK_MAX_POS)) != NULL)
     706        6032 :                                                 BATsetprop(b, GDK_MAX_POS, TYPE_oid, &(oid){nprop->val.oval + BATcount(b)});
     707             :                                         else
     708           0 :                                                 BATrmprop(b, GDK_MAX_POS);
     709             :                                 } else {
     710         370 :                                         BATrmprop(b, GDK_MAX_VALUE);
     711         370 :                                         BATrmprop(b, GDK_MAX_POS);
     712             :                                 }
     713             :                         }
     714             :                 } else {
     715      302480 :                         BATrmprop(b, GDK_MAX_VALUE);
     716      302175 :                         BATrmprop(b, GDK_MAX_POS);
     717             :                 }
     718             :         }
     719      551212 :         if (BATcount(b) == 0 || (prop = BATgetprop(b, GDK_MIN_VALUE)) != NULL) {
     720      310644 :                 if ((nprop = BATgetprop(n, GDK_MIN_VALUE)) != NULL) {
     721        6665 :                         if (BATcount(b) == 0 || ATOMcmp(b->ttype, VALptr(prop), VALptr(nprop)) > 0) {
     722        6222 :                                 if (s == NULL) {
     723        5852 :                                         BATsetprop(b, GDK_MIN_VALUE, b->ttype, VALptr(nprop));
     724        5884 :                                         if ((nprop = BATgetprop(n, GDK_MIN_POS)) != NULL)
     725        5860 :                                                 BATsetprop(b, GDK_MIN_POS, TYPE_oid, &(oid){nprop->val.oval + BATcount(b)});
     726             :                                         else
     727           0 :                                                 BATrmprop(b, GDK_MIN_POS);
     728             :                                 } else {
     729         370 :                                         BATrmprop(b, GDK_MIN_VALUE);
     730         370 :                                         BATrmprop(b, GDK_MIN_POS);
     731             :                                 }
     732             :                         }
     733             :                 } else {
     734      301810 :                         BATrmprop(b, GDK_MIN_VALUE);
     735      302640 :                         BATrmprop(b, GDK_MIN_POS);
     736             :                 }
     737             :         }
     738      551200 :         if (cnt > BATcount(b) / GDK_UNIQUE_ESTIMATE_KEEP_FRACTION)
     739      546629 :                 BATrmprop(b, GDK_UNIQUE_ESTIMATE);
     740             :         /* load hash so that we can maintain it */
     741      555015 :         (void) BATcheckhash(b);
     742             : 
     743      545038 :         if (b->ttype == TYPE_void) {
     744             :                 /* b does not have storage, keep it that way if we can */
     745        2692 :                 HASHdestroy(b); /* we're not maintaining the hash here */
     746        2693 :                 if (BATtdense(n) && ci.tpe == cand_dense &&
     747        2319 :                     (BATcount(b) == 0 ||
     748        1382 :                      (BATtdense(b) &&
     749        1382 :                       b->tseqbase + BATcount(b) == n->tseqbase + ci.seq - hseq))) {
     750             :                         /* n is also dense and consecutive with b */
     751        2264 :                         if (BATcount(b) == 0)
     752         937 :                                 BATtseqbase(b, n->tseqbase + ci.seq - hseq);
     753        2263 :                         BATsetcount(b, BATcount(b) + cnt);
     754        2265 :                         goto doreturn;
     755             :                 }
     756         429 :                 if ((BATcount(b) == 0 || is_oid_nil(b->tseqbase)) &&
     757          55 :                     ni.type == TYPE_void && is_oid_nil(n->tseqbase)) {
     758             :                         /* both b and n are void/nil */
     759          22 :                         BATtseqbase(b, oid_nil);
     760          22 :                         BATsetcount(b, BATcount(b) + cnt);
     761          22 :                         goto doreturn;
     762             :                 }
     763             :                 /* we need to materialize b; allocate enough capacity */
     764         407 :                 b->batCapacity = BATcount(b) + cnt;
     765         407 :                 if (BATmaterialize(b) != GDK_SUCCEED) {
     766           0 :                         bat_iterator_end(&ni);
     767           0 :                         return GDK_FAIL;
     768             :                 }
     769             :         }
     770             : 
     771      542753 :         r = BUNlast(b);
     772             : 
     773             :         /* property setting */
     774      542753 :         if (BATcount(b) == 0) {
     775      303297 :                 b->tsorted = n->tsorted;
     776      303297 :                 b->trevsorted = n->trevsorted;
     777      303297 :                 b->tseqbase = oid_nil;
     778      303297 :                 b->tnonil = n->tnonil;
     779      303297 :                 b->tnil = n->tnil && cnt == BATcount(n);
     780      303297 :                 if (ci.tpe == cand_dense) {
     781      302739 :                         b->tnosorted = ci.seq - hseq <= n->tnosorted && n->tnosorted < ci.seq + cnt - hseq ? n->tnosorted + hseq - ci.seq : 0;
     782      302739 :                         b->tnorevsorted = ci.seq - hseq <= n->tnorevsorted && n->tnorevsorted < ci.seq + cnt - hseq ? n->tnorevsorted + hseq - ci.seq : 0;
     783      302739 :                         if (BATtdense(n)) {
     784        2884 :                                 b->tseqbase = n->tseqbase + ci.seq - hseq;
     785             :                         }
     786             :                 } else {
     787         558 :                         b->tnosorted = 0;
     788         558 :                         b->tnorevsorted = 0;
     789             :                 }
     790      303297 :                 b->tkey = n->tkey;
     791      303297 :                 if (cnt == BATcount(n)) {
     792      298837 :                         b->tnokey[0] = n->tnokey[0];
     793      298837 :                         b->tnokey[1] = n->tnokey[1];
     794             :                 } else {
     795        4460 :                         b->tnokey[0] = b->tnokey[1] = 0;
     796             :                 }
     797             :         } else {
     798      239456 :                 BUN last = r - 1;
     799      239456 :                 BATiter bi = bat_iterator_nolock(b);
     800      238997 :                 int xx = ATOMcmp(b->ttype,
     801             :                                  BUNtail(ni, ci.seq - hseq),
     802             :                                  BUNtail(bi, last));
     803      240083 :                 if (BATtordered(b) && (!BATtordered(n) || xx < 0)) {
     804       24311 :                         b->tsorted = false;
     805       24311 :                         b->tnosorted = 0;
     806       24311 :                         b->tseqbase = oid_nil;
     807             :                 }
     808      240083 :                 if (BATtrevordered(b) &&
     809       40139 :                     (!BATtrevordered(n) || xx > 0)) {
     810       19411 :                         b->trevsorted = false;
     811       19411 :                         b->tnorevsorted = 0;
     812             :                 }
     813      240083 :                 if (b->tkey &&
     814       67977 :                     (!(BATtordered(b) || BATtrevordered(b)) ||
     815       50027 :                      !n->tkey || xx == 0)) {
     816       22854 :                         BATkey(b, false);
     817             :                 }
     818      240069 :                 if (b->ttype != TYPE_void && b->tsorted && BATtdense(b) &&
     819        1377 :                     (!BATtdense(n) ||
     820        2622 :                      ci.tpe != cand_dense ||
     821        1311 :                      1 + *(oid *) BUNtloc(bi, last) != BUNtoid(n, ci.seq - hseq))) {
     822         567 :                         b->tseqbase = oid_nil;
     823             :                 }
     824      240069 :                 b->tnonil &= n->tnonil;
     825      467736 :                 b->tnil |= n->tnil && cnt == ni.count;
     826             :         }
     827      543366 :         if (b->ttype == TYPE_str) {
     828      160422 :                 if (insert_string_bat(b, n, &ci, force, mayshare) != GDK_SUCCEED) {
     829           0 :                         bat_iterator_end(&ni);
     830           0 :                         return GDK_FAIL;
     831             :                 }
     832      382944 :         } else if (ATOMvarsized(b->ttype)) {
     833          64 :                 if (append_varsized_bat(b, n, &ci, mayshare) != GDK_SUCCEED) {
     834           0 :                         bat_iterator_end(&ni);
     835           0 :                         return GDK_FAIL;
     836             :                 }
     837      382880 :         } else if (ATOMstorage(b->ttype) == TYPE_msk) {
     838         103 :                 if (append_msk_bat(b, n, &ci) != GDK_SUCCEED) {
     839           0 :                         bat_iterator_end(&ni);
     840           0 :                         return GDK_FAIL;
     841             :                 }
     842             :         } else {
     843      382777 :                 if (cnt > BATcapacity(b) - BATcount(b)) {
     844             :                         /* if needed space exceeds a normal growth
     845             :                          * extend just with what's needed */
     846       14261 :                         BUN ncap = BATcount(b) + cnt;
     847       14261 :                         BUN grows = BATgrows(b);
     848             : 
     849             :                         if (ncap > grows)
     850             :                                 grows = ncap;
     851       14269 :                         if (BATextend(b, grows) != GDK_SUCCEED) {
     852           0 :                                 bat_iterator_end(&ni);
     853           0 :                                 return GDK_FAIL;
     854             :                         }
     855             :                 }
     856      382922 :                 MT_rwlock_wrlock(&b->thashlock);
     857      385401 :                 if (BATatoms[b->ttype].atomFix == NULL &&
     858      385120 :                     b->ttype != TYPE_void &&
     859      385120 :                     ni.type != TYPE_void &&
     860      380362 :                     ci.tpe == cand_dense) {
     861             :                         /* use fast memcpy if we can */
     862           0 :                         memcpy(Tloc(b, BUNlast(b)),
     863      379184 :                                (const char *) ni.base + ((ci.seq - hseq) << ni.shift),
     864      379184 :                                cnt << ni.shift);
     865      379467 :                         for (BUN i = 0; b->thash && i < cnt; i++) {
     866         444 :                                 HASHappend_locked(b, r, Tloc(b, r));
     867         283 :                                 r++;
     868             :                         }
     869             :                 } else {
     870      631411 :                         while (cnt > 0) {
     871      625196 :                                 cnt--;
     872      625196 :                                 BUN p = canditer_next(&ci) - hseq;
     873      625193 :                                 const void *t = BUNtail(ni, p);
     874      625192 :                                 if (tfastins_nocheck(b, r, t) != GDK_SUCCEED) {
     875           0 :                                         MT_rwlock_wrunlock(&b->thashlock);
     876           0 :                                         bat_iterator_end(&ni);
     877           0 :                                         return GDK_FAIL;
     878             :                                 }
     879      625194 :                                 if (b->thash)
     880           0 :                                         HASHappend_locked(b, r, t);
     881      625194 :                                 r++;
     882             :                         }
     883             :                 }
     884      385238 :                 MT_rwlock_wrunlock(&b->thashlock);
     885      383967 :                 BATsetcount(b, b->batCount + ci.ncand);
     886             :         }
     887             : 
     888      550675 :   doreturn:
     889      550675 :         bat_iterator_end(&ni);
     890      550875 :         TRC_DEBUG(ALGO, "b=%s,n=" ALGOBATFMT ",s=" ALGOOPTBATFMT
     891             :                   " -> " ALGOBATFMT " (" LLFMT " usec)\n",
     892             :                   buf, ALGOBATPAR(n), ALGOOPTBATPAR(s), ALGOBATPAR(b),
     893             :                   GDKusec() - t0);
     894             : 
     895             :         return GDK_SUCCEED;
     896             : }
     897             : 
     898             : gdk_return
     899     2255235 : BATappend(BAT *b, BAT *n, BAT *s, bool force)
     900             : {
     901     2255235 :         return BATappend2(b, n, s, force, true);
     902             : }
     903             : 
     904             : gdk_return
     905           4 : BATdel(BAT *b, BAT *d)
     906             : {
     907           4 :         gdk_return (*unfix) (const void *) = BATatoms[b->ttype].atomUnfix;
     908           4 :         void (*atmdel) (Heap *, var_t *) = BATatoms[b->ttype].atomDel;
     909           4 :         BATiter bi = bat_iterator_nolock(b);
     910             : 
     911           4 :         assert(ATOMtype(d->ttype) == TYPE_oid);
     912           4 :         assert(d->tsorted);
     913           4 :         assert(d->tkey);
     914           4 :         if (BATcount(d) == 0)
     915             :                 return GDK_SUCCEED;
     916           4 :         IMPSdestroy(b);
     917           4 :         OIDXdestroy(b);
     918           4 :         HASHdestroy(b);
     919           4 :         PROPdestroy(b);
     920           6 :         if (BATtdense(d)) {
     921             :                 oid o = d->tseqbase;
     922           2 :                 BUN c = BATcount(d);
     923             : 
     924           2 :                 if (o + c <= b->hseqbase)
     925             :                         return GDK_SUCCEED;
     926           2 :                 if (o < b->hseqbase) {
     927           0 :                         c -= b->hseqbase - o;
     928             :                         o = b->hseqbase;
     929             :                 }
     930           2 :                 if (o - b->hseqbase < b->batInserted) {
     931           0 :                         GDKerror("cannot delete committed values\n");
     932           0 :                         return GDK_FAIL;
     933             :                 }
     934           2 :                 if (o + c > b->hseqbase + BATcount(b))
     935           0 :                         c = b->hseqbase + BATcount(b) - o;
     936           2 :                 if (c == 0)
     937             :                         return GDK_SUCCEED;
     938           2 :                 if (unfix || atmdel) {
     939             :                         BUN p = o - b->hseqbase;
     940           0 :                         BUN q = p + c;
     941           0 :                         while (p < q) {
     942           0 :                                 if (unfix && (*unfix)(BUNtail(bi, p)) != GDK_SUCCEED)
     943             :                                         return GDK_FAIL;
     944           0 :                                 if (atmdel)
     945           0 :                                         (*atmdel)(b->tvheap, (var_t *) BUNtloc(bi, p));
     946           0 :                                 p++;
     947             :                         }
     948             :                 }
     949           2 :                 if (BATtdense(b) && BATmaterialize(b) != GDK_SUCCEED)
     950             :                         return GDK_FAIL;
     951           2 :                 if (o + c < b->hseqbase + BATcount(b)) {
     952           0 :                         o -= b->hseqbase;
     953           0 :                         if (ATOMstorage(b->ttype) == TYPE_msk) {
     954           0 :                                 BUN n = BATcount(b) - (o + c);
     955             :                                 /* not very efficient, but first see
     956             :                                  * how much this is used */
     957           0 :                                 for (BUN i = 0; i < n; i++)
     958           0 :                                         mskSetVal(b, o + i,
     959           0 :                                                   mskGetVal(b, o + c + i));
     960             :                         } else {
     961           0 :                                 memmove(Tloc(b, o),
     962           0 :                                         Tloc(b, o + c),
     963           0 :                                         Tsize(b) * (BATcount(b) - (o + c)));
     964             :                         }
     965           0 :                         b->theap->dirty = true;
     966             :                         // o += b->hseqbase; // if this were to be used again
     967             :                 }
     968           2 :                 MT_lock_set(&b->theaplock);
     969           2 :                 b->batCount -= c;
     970           2 :                 MT_lock_unset(&b->theaplock);
     971             :         } else {
     972           2 :                 BATiter di = bat_iterator(d);
     973           2 :                 const oid *o = (const oid *) di.base;
     974             :                 const oid *s;
     975           2 :                 BUN c = di.count;
     976             :                 BUN nd = 0;
     977             :                 BUN pos;
     978             :                 char *p = NULL;
     979             : 
     980           2 :                 if (o[c - 1] <= b->hseqbase) {
     981           0 :                         bat_iterator_end(&di);
     982           0 :                         return GDK_SUCCEED;
     983             :                 }
     984           2 :                 while (*o < b->hseqbase) {
     985           0 :                         o++;
     986           0 :                         c--;
     987             :                 }
     988           2 :                 if (*o - b->hseqbase < b->batInserted) {
     989           0 :                         bat_iterator_end(&di);
     990           0 :                         GDKerror("cannot delete committed values\n");
     991           0 :                         return GDK_FAIL;
     992             :                 }
     993           2 :                 if (BATtdense(b) && BATmaterialize(b) != GDK_SUCCEED) {
     994           0 :                         bat_iterator_end(&di);
     995           0 :                         return GDK_FAIL;
     996             :                 }
     997             :                 s = o;
     998           2 :                 pos = *o - b->hseqbase;
     999           2 :                 if (ATOMstorage(b->ttype) != TYPE_msk)
    1000           2 :                         p = Tloc(b, pos);
    1001           6 :                 while (c > 0 && *o < b->hseqbase + BATcount(b)) {
    1002             :                         size_t n;
    1003           4 :                         if (unfix)
    1004           0 :                                 (*unfix)(BUNtail(bi, *o - b->hseqbase));
    1005           4 :                         if (atmdel)
    1006           0 :                                 (*atmdel)(b->tvheap, (var_t *) BUNtloc(bi, *o - b->hseqbase));
    1007           4 :                         o++;
    1008           4 :                         c--;
    1009           4 :                         nd++;
    1010           4 :                         if (c == 0 || *o - b->hseqbase >= BATcount(b))
    1011           2 :                                 n = b->hseqbase + BATcount(b) - o[-1] - 1;
    1012           2 :                         else if ((oid) (o - s) < *o - *s)
    1013           2 :                                 n = o[0] - o[-1] - 1;
    1014             :                         else
    1015             :                                 n = 0;
    1016           4 :                         if (n > 0) {
    1017           2 :                                 if (ATOMstorage(b->ttype) == TYPE_msk) {
    1018           0 :                                         BUN opos = o[-1] + 1 - b->hseqbase;
    1019             :                                         /* not very efficient, but
    1020             :                                          * first see how much this is
    1021             :                                          * used */
    1022           0 :                                         for (BUN i = 0; i < n; i++) {
    1023           0 :                                                 mskSetVal(b, pos + i,
    1024           0 :                                                           mskGetVal(b, opos + i));
    1025             :                                         }
    1026           0 :                                         pos += n;
    1027             :                                 } else {
    1028           2 :                                         n *= Tsize(b);
    1029           2 :                                         memmove(p,
    1030           2 :                                                 Tloc(b, o[-1] + 1 - b->hseqbase),
    1031             :                                                 n);
    1032           2 :                                         p += n;
    1033             :                                 }
    1034             :                                 s = o;
    1035             :                         }
    1036             :                 }
    1037           2 :                 bat_iterator_end(&di);
    1038           2 :                 MT_lock_set(&b->theaplock);
    1039           2 :                 b->theap->dirty = true;
    1040           2 :                 b->batCount -= nd;
    1041           2 :                 MT_lock_unset(&b->theaplock);
    1042             :         }
    1043           4 :         if (b->batCount <= 1) {
    1044             :                 /* some trivial properties */
    1045           2 :                 b->tkey = true;
    1046           2 :                 b->tsorted = b->trevsorted = true;
    1047           2 :                 if (b->batCount == 0) {
    1048           2 :                         b->tnil = false;
    1049           2 :                         b->tnonil = true;
    1050             :                 }
    1051             :         }
    1052             :         /* not sure about these anymore */
    1053           4 :         b->tnosorted = b->tnorevsorted = 0;
    1054           4 :         b->tnokey[0] = b->tnokey[1] = 0;
    1055             : 
    1056           4 :         return GDK_SUCCEED;
    1057             : }
    1058             : 
    1059             : /*
    1060             :  * Replace all values in b with values from n whose location is given by
    1061             :  * the oid in either p or positions.
    1062             :  * If positions is used, autoincr specifies whether it is the first of a
    1063             :  * dense range of positions or whether it is a full-blown array of
    1064             :  * position.
    1065             :  * If mayappend is set, the position in p/positions may refer to
    1066             :  * locations beyond the end of b.
    1067             :  */
    1068             : static gdk_return
    1069      118767 : BATappend_or_update(BAT *b, BAT *p, const oid *positions, BAT *n,
    1070             :                     bool mayappend, bool autoincr, bool force)
    1071             : {
    1072      118767 :         lng t0 = GDKusec();
    1073      118778 :         oid pos = oid_nil;
    1074             : 
    1075      118778 :         if (b == NULL || b->ttype == TYPE_void || n == NULL) {
    1076             :                 return GDK_SUCCEED;
    1077             :         }
    1078             :         /* either p or positions */
    1079      118778 :         assert((p == NULL) != (positions == NULL));
    1080      118778 :         if (p != NULL) {
    1081      118589 :                 if (BATcount(p) != BATcount(n)) {
    1082           0 :                         GDKerror("update BATs not the same size\n");
    1083           0 :                         return GDK_FAIL;
    1084             :                 }
    1085      118589 :                 if (ATOMtype(p->ttype) != TYPE_oid) {
    1086           0 :                         GDKerror("positions BAT not type OID\n");
    1087           0 :                         return GDK_FAIL;
    1088             :                 }
    1089      118589 :                 if (BATtdense(p)) {
    1090      111212 :                         pos = p->tseqbase;
    1091             :                         positions = &pos;
    1092             :                         autoincr = true;
    1093      111212 :                         p = NULL;
    1094        7377 :                 } else if (p->ttype != TYPE_void) {
    1095        7376 :                         positions = (const oid *) Tloc(p, 0);
    1096             :                         autoincr = false;
    1097             :                 } else {
    1098             :                         autoincr = false;
    1099             :                 }
    1100         189 :         } else if (autoincr) {
    1101         189 :                 pos = *positions;
    1102             :         }
    1103      118778 :         if (BATcount(n) == 0) {
    1104             :                 return GDK_SUCCEED;
    1105             :         }
    1106       23589 :         if (!force && (b->batRestricted != BAT_WRITE || b->batSharecnt > 0)) {
    1107           0 :                 GDKerror("access denied to %s, aborting.\n", BATgetId(b));
    1108           0 :                 return GDK_FAIL;
    1109             :         }
    1110             : 
    1111       23589 :         BATiter bi = bat_iterator_nolock(b);
    1112       23586 :         BATiter ni = bat_iterator(n);
    1113             : 
    1114       23602 :         OIDXdestroy(b);
    1115       23591 :         IMPSdestroy(b);
    1116       23591 :         if (ni.count > BATcount(b) / GDK_UNIQUE_ESTIMATE_KEEP_FRACTION)
    1117       23476 :                 BATrmprop(b, GDK_UNIQUE_ESTIMATE);
    1118             :         /* load hash so that we can maintain it */
    1119       23611 :         (void) BATcheckhash(b);
    1120             : 
    1121       23587 :         b->tsorted = b->trevsorted = false;
    1122       23587 :         b->tnosorted = b->tnorevsorted = 0;
    1123       23587 :         b->tseqbase = oid_nil;
    1124       23587 :         b->tkey = false;
    1125       23587 :         b->tnokey[0] = b->tnokey[1] = 0;
    1126             : 
    1127       23587 :         const ValRecord *maxprop = BATgetprop(b, GDK_MAX_VALUE);
    1128       23608 :         const ValRecord *minprop = BATgetprop(b, GDK_MIN_VALUE);
    1129       24663 :         int (*atomcmp)(const void *, const void *) = ATOMcompare(b->ttype);
    1130       24663 :         const void *nil = ATOMnilptr(b->ttype);
    1131       24663 :         oid hseqend = b->hseqbase + BATcount(b);
    1132             :         bool anynil = false;
    1133             :         bool locked = false;
    1134             : 
    1135       24663 :         if (b->tvarsized) {
    1136      628214 :                 for (BUN i = 0; i < ni.count; i++) {
    1137             :                         oid updid;
    1138      626411 :                         if (positions) {
    1139      626394 :                                 updid = autoincr ? pos++ : *positions++;
    1140             :                         } else {
    1141          17 :                                 updid = BUNtoid(p, i);
    1142             :                         }
    1143             : 
    1144      626411 :                         if (updid < b->hseqbase ||
    1145      626411 :                             (!mayappend && updid >= hseqend)) {
    1146           0 :                                 GDKerror("id out of range\n");
    1147           0 :                                 goto bailout;
    1148             :                         }
    1149      626411 :                         updid -= b->hseqbase;
    1150      626411 :                         if (!force && updid < b->batInserted) {
    1151           0 :                                 GDKerror("updating committed value\n");
    1152           0 :                                 goto bailout;
    1153             :                         }
    1154             : 
    1155      626411 :                         const void *new = BUNtvar(ni, i);
    1156             : 
    1157      626411 :                         if (updid >= BATcount(b)) {
    1158          30 :                                 assert(mayappend);
    1159          30 :                                 if (locked) {
    1160           5 :                                         MT_rwlock_wrunlock(&b->thashlock);
    1161             :                                         locked = false;
    1162             :                                 }
    1163          30 :                                 if (BATcount(b) < updid &&
    1164           0 :                                     BUNappendmulti(b, NULL, (BUN) (updid - BATcount(b)), force) != GDK_SUCCEED) {
    1165           0 :                                         bat_iterator_end(&ni);
    1166           0 :                                         return GDK_FAIL;
    1167             :                                 }
    1168          30 :                                 if (BUNappend(b, new, force) != GDK_SUCCEED) {
    1169           0 :                                         bat_iterator_end(&ni);
    1170           0 :                                         return GDK_FAIL;
    1171             :                                 }
    1172          30 :                                 bi = bat_iterator_nolock(b);
    1173      182468 :                                 continue;
    1174             :                         }
    1175             : 
    1176      626381 :                         const void *old = BUNtvar(bi, updid);
    1177             : 
    1178      626381 :                         if (atomcmp(old, new) == 0) {
    1179             :                                 /* replacing with the same value:
    1180             :                                  * nothing to do */
    1181      182438 :                                 continue;
    1182             :                         }
    1183             : 
    1184      441429 :                         bool isnil = atomcmp(new, nil) == 0;
    1185      441254 :                         anynil |= isnil;
    1186      441254 :                         if (b->tnil &&
    1187        1015 :                             !anynil &&
    1188        1015 :                             atomcmp(old, nil) == 0) {
    1189             :                                 /* if old value is nil and no new
    1190             :                                  * value is, we're not sure anymore
    1191             :                                  * about the nil property, so we must
    1192             :                                  * clear it */
    1193        1015 :                                 b->tnil = false;
    1194             :                         }
    1195      441254 :                         b->tnonil &= !isnil;
    1196      441254 :                         b->tnil |= isnil;
    1197      441254 :                         if (maxprop) {
    1198         150 :                                 if (!isnil &&
    1199          96 :                                     atomcmp(VALptr(maxprop), new) < 0) {
    1200             :                                         /* new value is larger than
    1201             :                                          * previous largest */
    1202          21 :                                         MT_lock_set(&b->theaplock);
    1203          21 :                                         maxprop = BATsetprop_nolock(b, GDK_MAX_VALUE, b->ttype, new);
    1204          21 :                                         BATsetprop_nolock(b, GDK_MAX_POS, TYPE_oid, &(oid){updid});
    1205          21 :                                         MT_lock_unset(&b->theaplock);
    1206          64 :                                 } else if (atomcmp(VALptr(maxprop), old) == 0 &&
    1207          10 :                                            atomcmp(new, old) != 0) {
    1208             :                                         /* old value is equal to
    1209             :                                          * largest and new value is
    1210             :                                          * smaller, so we don't know
    1211             :                                          * anymore which is the
    1212             :                                          * largest */
    1213          10 :                                         MT_lock_set(&b->theaplock);
    1214          10 :                                         BATrmprop_nolock(b, GDK_MAX_VALUE);
    1215          10 :                                         BATrmprop_nolock(b, GDK_MAX_POS);
    1216          10 :                                         MT_lock_unset(&b->theaplock);
    1217             :                                         maxprop = NULL;
    1218             :                                 }
    1219             :                         }
    1220      441254 :                         if (minprop) {
    1221         237 :                                 if (!isnil &&
    1222          57 :                                     atomcmp(VALptr(minprop), new) > 0) {
    1223             :                                         /* new value is smaller than
    1224             :                                          * previous smallest */
    1225          12 :                                         MT_lock_set(&b->theaplock);
    1226          12 :                                         minprop = BATsetprop_nolock(b, GDK_MIN_VALUE, b->ttype, new);
    1227          12 :                                         BATsetprop_nolock(b, GDK_MIN_POS, TYPE_oid, &(oid){updid});
    1228          12 :                                         MT_lock_unset(&b->theaplock);
    1229         199 :                                 } else if (atomcmp(VALptr(minprop), old) == 0 &&
    1230          19 :                                            atomcmp(new, old) != 0) {
    1231             :                                         /* old value is equal to
    1232             :                                          * smallest and new value is
    1233             :                                          * larger, so we don't know
    1234             :                                          * anymore which is the
    1235             :                                          * smallest */
    1236          19 :                                         MT_lock_set(&b->theaplock);
    1237          19 :                                         BATrmprop_nolock(b, GDK_MIN_VALUE);
    1238          19 :                                         BATrmprop_nolock(b, GDK_MIN_POS);
    1239          19 :                                         MT_lock_unset(&b->theaplock);
    1240             :                                         minprop = NULL;
    1241             :                                 }
    1242             :                         }
    1243      441107 :                         if (!locked) {
    1244        1593 :                                 MT_rwlock_wrlock(&b->thashlock);
    1245             :                                 locked = true;
    1246             :                         }
    1247      441107 :                         HASHdelete_locked(b, updid, old);
    1248             : 
    1249             :                         var_t d;
    1250      440825 :                         switch (b->twidth) {
    1251      423086 :                         default: /* only three or four cases possible */
    1252      423086 :                                 d = (var_t) ((uint8_t *) b->theap->base)[updid] + GDK_VAROFFSET;
    1253      423086 :                                 break;
    1254        9951 :                         case 2:
    1255        9951 :                                 d = (var_t) ((uint16_t *) b->theap->base)[updid] + GDK_VAROFFSET;
    1256        9951 :                                 break;
    1257        7769 :                         case 4:
    1258        7769 :                                 d = (var_t) ((uint32_t *) b->theap->base)[updid];
    1259        7769 :                                 break;
    1260             : #if SIZEOF_VAR_T == 8
    1261          19 :                         case 8:
    1262          19 :                                 d = (var_t) ((uint64_t *) b->theap->base)[updid];
    1263          19 :                                 break;
    1264             : #endif
    1265             :                         }
    1266      440825 :                         if (ATOMreplaceVAR(b, &d, new) != GDK_SUCCEED) {
    1267           0 :                                 goto bailout;
    1268             :                         }
    1269      441648 :                         if (b->twidth < SIZEOF_VAR_T &&
    1270      441629 :                             (b->twidth <= 2 ? d - GDK_VAROFFSET : d) >= ((size_t) 1 << (8 << b->tshift))) {
    1271             :                                 /* doesn't fit in current heap, upgrade it */
    1272          16 :                                 if (GDKupgradevarheap(b, d, 0, MAX(updid, b->batCount)) != GDK_SUCCEED) {
    1273           0 :                                         goto bailout;
    1274             :                                 }
    1275             :                         }
    1276             :                         /* in case ATOMreplaceVAR and/or
    1277             :                          * GDKupgradevarheap replaces a heap, we need to
    1278             :                          * reinitialize the iterator */
    1279      441648 :                         bi = bat_iterator_nolock(b);
    1280      443088 :                         switch (b->twidth) {
    1281      425337 :                         case 1:
    1282      425337 :                                 ((uint8_t *) b->theap->base)[updid] = (uint8_t) (d - GDK_VAROFFSET);
    1283      425337 :                                 break;
    1284        9959 :                         case 2:
    1285        9959 :                                 ((uint16_t *) b->theap->base)[updid] = (uint16_t) (d - GDK_VAROFFSET);
    1286        9959 :                                 break;
    1287        7773 :                         case 4:
    1288        7773 :                                 ((uint32_t *) b->theap->base)[updid] = (uint32_t) d;
    1289        7773 :                                 break;
    1290             : #if SIZEOF_VAR_T == 8
    1291          19 :                         case 8:
    1292          19 :                                 ((uint64_t *) b->theap->base)[updid] = (uint64_t) d;
    1293          19 :                                 break;
    1294             : #endif
    1295             :                         }
    1296      443088 :                         HASHinsert_locked(b, updid, new);
    1297             : 
    1298             :                 }
    1299        1803 :                 if (locked) {
    1300        1590 :                         MT_rwlock_wrunlock(&b->thashlock);
    1301             :                         locked = false;
    1302             :                 }
    1303        1803 :                 MT_lock_set(&b->theaplock);
    1304        1803 :                 b->tvheap->dirty = true;
    1305        1803 :                 MT_lock_unset(&b->theaplock);
    1306       21791 :         } else if (ATOMstorage(b->ttype) == TYPE_msk) {
    1307           0 :                 HASHdestroy(b); /* hash doesn't make sense for msk */
    1308           0 :                 for (BUN i = 0; i < ni.count; i++) {
    1309             :                         oid updid;
    1310           0 :                         if (positions) {
    1311           0 :                                 updid = autoincr ? pos++ : *positions++;
    1312             :                         } else {
    1313           0 :                                 updid = BUNtoid(p, i);
    1314             :                         }
    1315             : 
    1316           0 :                         if (updid < b->hseqbase ||
    1317           0 :                             (!mayappend && updid >= hseqend)) {
    1318           0 :                                 GDKerror("id out of range\n");
    1319           0 :                                 bat_iterator_end(&ni);
    1320           0 :                                 return GDK_FAIL;
    1321             :                         }
    1322           0 :                         updid -= b->hseqbase;
    1323           0 :                         if (!force && updid < b->batInserted) {
    1324           0 :                                 GDKerror("updating committed value\n");
    1325           0 :                                 bat_iterator_end(&ni);
    1326           0 :                                 return GDK_FAIL;
    1327             :                         }
    1328           0 :                         if (updid >= BATcount(b)) {
    1329           0 :                                 assert(mayappend);
    1330           0 :                                 if (BATcount(b) < updid &&
    1331           0 :                                     BUNappendmulti(b, NULL, (BUN) (updid - BATcount(b)), force) != GDK_SUCCEED) {
    1332           0 :                                         bat_iterator_end(&ni);
    1333           0 :                                         return GDK_FAIL;
    1334             :                                 }
    1335           0 :                                 if (BUNappend(b, Tmsk(&ni, i), force) != GDK_SUCCEED) {
    1336           0 :                                         bat_iterator_end(&ni);
    1337           0 :                                         return GDK_FAIL;
    1338             :                                 }
    1339           0 :                                 continue;
    1340             :                         }
    1341           0 :                         mskSetVal(b, updid, Tmskval(&ni, i));
    1342             :                 }
    1343       21791 :         } else if (autoincr) {
    1344       14974 :                 if (pos < b->hseqbase ||
    1345       14807 :                     (!mayappend && pos + ni.count > hseqend)) {
    1346           0 :                         GDKerror("id out of range\n");
    1347           0 :                         bat_iterator_end(&ni);
    1348           0 :                         return GDK_FAIL;
    1349             :                 }
    1350       14974 :                 pos -= b->hseqbase;
    1351       14974 :                 if (!force && pos < b->batInserted) {
    1352           0 :                         GDKerror("updating committed value\n");
    1353           0 :                         bat_iterator_end(&ni);
    1354           0 :                         return GDK_FAIL;
    1355             :                 }
    1356             : 
    1357       14974 :                 if (pos >= BATcount(b)) {
    1358           0 :                         assert(mayappend);
    1359           0 :                         bat_iterator_end(&ni);
    1360           0 :                         if (BATcount(b) < pos &&
    1361           0 :                             BUNappendmulti(b, NULL, (BUN) (pos - BATcount(b)), force) != GDK_SUCCEED) {
    1362             :                                 return GDK_FAIL;
    1363             :                         }
    1364           0 :                         return BATappend(b, n, NULL, force);
    1365             :                 }
    1366       14974 :                 if (pos + ni.count > BATcount(b) &&
    1367           0 :                     BUNappendmulti(b, NULL, (BUN) (pos + ni.count - BATcount(b)), force) != GDK_SUCCEED) {
    1368           0 :                         bat_iterator_end(&ni);
    1369           0 :                         return GDK_FAIL;
    1370             :                 }
    1371             : 
    1372             :                 /* we copy all of n, so if there are nils in n we get
    1373             :                  * nils in b (and else we don't know) */
    1374       14974 :                 b->tnil = n->tnil;
    1375             :                 /* we may not copy over all of b, so we only know that
    1376             :                  * there are no nils in b afterward if there weren't
    1377             :                  * any in either b or n to begin with */
    1378       14974 :                 b->tnonil &= n->tnonil;
    1379             :                 /* if there is no hash, we don't start the loop, if
    1380             :                  * there is only a persisted hash, it will get destroyed
    1381             :                  * in the first iteration, after which there is no hash
    1382             :                  * and the loop ends */
    1383       14974 :                 MT_rwlock_wrlock(&b->thashlock);
    1384             :                 locked = true;
    1385      218191 :                 for (BUN i = pos, j = pos + ni.count; i < j && b->thash; i++)
    1386      203220 :                         HASHdelete_locked(b, i, Tloc(b, i));
    1387       14971 :                 if (n->ttype == TYPE_void) {
    1388          40 :                         assert(b->ttype == TYPE_oid);
    1389          40 :                         oid *o = Tloc(b, pos);
    1390          40 :                         if (is_oid_nil(ni.tseq)) {
    1391             :                                 /* we may or may not overwrite the old
    1392             :                                  * min/max values */
    1393           0 :                                 MT_lock_set(&b->theaplock);
    1394           0 :                                 BATrmprop_nolock(b, GDK_MAX_VALUE);
    1395           0 :                                 BATrmprop_nolock(b, GDK_MIN_VALUE);
    1396           0 :                                 BATrmprop_nolock(b, GDK_MAX_POS);
    1397           0 :                                 BATrmprop_nolock(b, GDK_MIN_POS);
    1398           0 :                                 MT_lock_unset(&b->theaplock);
    1399           0 :                                 for (BUN i = 0, j = ni.count; i < j; i++)
    1400           0 :                                         o[i] = oid_nil;
    1401           0 :                                 b->tnil = true;
    1402             :                         } else {
    1403          40 :                                 oid v = ni.tseq;
    1404             :                                 /* we know min/max of n, so we know
    1405             :                                  * the new min/max of b if those of n
    1406             :                                  * are smaller/larger than the old */
    1407          40 :                                 MT_lock_set(&b->theaplock);
    1408          40 :                                 if (minprop && v <= minprop->val.oval) {
    1409           0 :                                         BATsetprop_nolock(b, GDK_MIN_VALUE, TYPE_oid, &v);
    1410           0 :                                         BATsetprop_nolock(b, GDK_MIN_POS, TYPE_oid, &(oid){pos});
    1411             :                                 } else {
    1412          40 :                                         BATrmprop_nolock(b, GDK_MIN_VALUE);
    1413          40 :                                         BATrmprop_nolock(b, GDK_MIN_POS);
    1414             :                                 }
    1415          40 :                                 MT_lock_unset(&b->theaplock);
    1416        1558 :                                 for (BUN i = 0, j = ni.count; i < j; i++)
    1417        1518 :                                         o[i] = v++;
    1418          40 :                                 MT_lock_set(&b->theaplock);
    1419          40 :                                 if (maxprop && --v >= maxprop->val.oval) {
    1420           0 :                                         BATsetprop_nolock(b, GDK_MAX_VALUE, TYPE_oid, &v);
    1421           0 :                                         BATsetprop_nolock(b, GDK_MAX_POS, TYPE_oid, &(oid){pos + ni.count - 1});
    1422             :                                 } else {
    1423          40 :                                         BATrmprop_nolock(b, GDK_MAX_VALUE);
    1424          40 :                                         BATrmprop_nolock(b, GDK_MAX_POS);
    1425             :                                 }
    1426          40 :                                 MT_lock_unset(&b->theaplock);
    1427             :                         }
    1428             :                 } else {
    1429             :                         /* if the extremes of n are at least as
    1430             :                          * extreme as those of b, we can replace b's
    1431             :                          * min/max, else we don't know what b's new
    1432             :                          * min/max are*/
    1433             :                         const ValRecord *prop;
    1434       16002 :                         if (maxprop != NULL &&
    1435        1128 :                             (prop = BATgetprop(n, GDK_MAX_VALUE)) != NULL &&
    1436          57 :                             atomcmp(VALptr(maxprop), VALptr(prop)) <= 0) {
    1437          30 :                                 BATsetprop(b, GDK_MAX_VALUE, b->ttype, VALptr(prop));
    1438          30 :                                 if ((prop = BATgetprop(n, GDK_MAX_POS)) != NULL)
    1439          30 :                                         BATsetprop(b, GDK_MAX_POS, TYPE_oid, &(oid){prop->val.oval + pos});
    1440             :                                 else
    1441           0 :                                         BATrmprop(b, GDK_MAX_POS);
    1442             :                         } else {
    1443       14901 :                                 BATrmprop(b, GDK_MAX_VALUE);
    1444       14912 :                                 BATrmprop(b, GDK_MAX_POS);
    1445             :                         }
    1446       15975 :                         if (minprop != NULL &&
    1447        1058 :                             (prop = BATgetprop(n, GDK_MIN_VALUE)) != NULL &&
    1448          23 :                             atomcmp(VALptr(minprop), VALptr(prop)) >= 0) {
    1449          10 :                                 BATsetprop(b, GDK_MIN_VALUE, b->ttype, VALptr(prop));
    1450          10 :                                 if ((prop = BATgetprop(n, GDK_MIN_POS)) != NULL)
    1451          10 :                                         BATsetprop(b, GDK_MIN_POS, TYPE_oid, &(oid){prop->val.oval + pos});
    1452             :                                 else
    1453           0 :                                         BATrmprop(b, GDK_MIN_POS);
    1454             :                         } else {
    1455       14930 :                                 MT_lock_set(&b->theaplock);
    1456       14930 :                                 BATrmprop_nolock(b, GDK_MIN_VALUE);
    1457       14935 :                                 BATrmprop_nolock(b, GDK_MIN_POS);
    1458       14938 :                                 MT_lock_unset(&b->theaplock);
    1459             :                         }
    1460       14944 :                         memcpy(Tloc(b, pos), ni.base,
    1461       14944 :                                ni.count << b->tshift);
    1462             :                 }
    1463             :                 /* either we have a hash that was updated above, or we
    1464             :                  * have no hash; we cannot have the case where there is
    1465             :                  * only a persisted (unloaded) hash since it would have
    1466             :                  * been destroyed above */
    1467       14984 :                 if (b->thash != NULL) {
    1468      203642 :                         for (BUN i = pos, j = pos + ni.count; i < j; i++)
    1469      203217 :                                 HASHinsert_locked(b, i, Tloc(b, i));
    1470             :                 }
    1471       14972 :                 MT_rwlock_wrunlock(&b->thashlock);
    1472             :                 locked = false;
    1473       14988 :                 if (ni.count == BATcount(b)) {
    1474             :                         /* if we replaced all values of b by values
    1475             :                          * from n, we can also copy the min/max
    1476             :                          * properties */
    1477        7211 :                         if ((minprop = BATgetprop(n, GDK_MIN_VALUE)) != NULL)
    1478           5 :                                 BATsetprop(b, GDK_MIN_VALUE, b->ttype, VALptr(minprop));
    1479             :                         else
    1480        7197 :                                 BATrmprop(b, GDK_MIN_VALUE);
    1481        7212 :                         if ((minprop = BATgetprop(n, GDK_MIN_POS)) != NULL)
    1482           5 :                                 BATsetprop(b, GDK_MIN_POS, TYPE_oid, &minprop->val.oval);
    1483             :                         else
    1484        7207 :                                 BATrmprop(b, GDK_MIN_POS);
    1485        7212 :                         if ((maxprop = BATgetprop(n, GDK_MAX_VALUE)) != NULL)
    1486           5 :                                 BATsetprop(b, GDK_MAX_VALUE, b->ttype, VALptr(maxprop));
    1487             :                         else
    1488        7208 :                                 BATrmprop(b, GDK_MAX_VALUE);
    1489        7213 :                         if ((maxprop = BATgetprop(n, GDK_MAX_POS)) != NULL)
    1490           5 :                                 BATsetprop(b, GDK_MAX_POS, TYPE_oid, &maxprop->val.oval);
    1491             :                         else
    1492        7204 :                                 BATrmprop(b, GDK_MAX_POS);
    1493        7213 :                         if (BATtdense(n)) {
    1494             :                                 /* replaced all of b with a dense sequence */
    1495          46 :                                 BATtseqbase(b, ni.tseq);
    1496             :                         }
    1497             :                 }
    1498             :         } else {
    1499   122811992 :                 for (BUN i = 0, j = ni.count; i < j; i++) {
    1500             :                         oid updid;
    1501   122805173 :                         if (positions) {
    1502             :                                 /* assert(!autoincr) */
    1503   122805173 :                                 updid = *positions++;
    1504             :                         } else {
    1505           0 :                                 updid = BUNtoid(p, i);
    1506             :                         }
    1507             : 
    1508   122805173 :                         if (updid < b->hseqbase ||
    1509   122805173 :                             (!mayappend && updid >= hseqend)) {
    1510           0 :                                 GDKerror("id out of range\n");
    1511           0 :                                 goto bailout;
    1512             :                         }
    1513   122805173 :                         updid -= b->hseqbase;
    1514   122805173 :                         if (!force && updid < b->batInserted) {
    1515           0 :                                 GDKerror("updating committed value\n");
    1516           0 :                                 goto bailout;
    1517             :                         }
    1518             : 
    1519   122805173 :                         const void *new = BUNtail(ni, i);
    1520             : 
    1521   122802458 :                         if (updid >= BATcount(b)) {
    1522          91 :                                 assert(mayappend);
    1523          91 :                                 if (locked) {
    1524           9 :                                         MT_rwlock_wrunlock(&b->thashlock);
    1525             :                                         locked = false;
    1526             :                                 }
    1527          91 :                                 if (BATcount(b) < updid &&
    1528           0 :                                     BUNappendmulti(b, NULL, (BUN) (updid - BATcount(b)), force) != GDK_SUCCEED) {
    1529           0 :                                         goto bailout;
    1530             :                                 }
    1531          91 :                                 if (BUNappend(b, new, force) != GDK_SUCCEED) {
    1532           0 :                                         bat_iterator_end(&ni);
    1533           0 :                                         return GDK_FAIL;
    1534             :                                 }
    1535          91 :                                 bi = bat_iterator_nolock(b);
    1536          91 :                                 continue;
    1537             :                         }
    1538             : 
    1539   122802367 :                         const void *old = BUNtloc(bi, updid);
    1540   122802367 :                         bool isnil = atomcmp(new, nil) == 0;
    1541   121247787 :                         anynil |= isnil;
    1542   121247787 :                         if (b->tnil &&
    1543        1445 :                             !anynil &&
    1544        1444 :                             atomcmp(old, nil) == 0) {
    1545             :                                 /* if old value is nil and no new
    1546             :                                  * value is, we're not sure anymore
    1547             :                                  * about the nil property, so we must
    1548             :                                  * clear it */
    1549        1445 :                                 b->tnil = false;
    1550             :                         }
    1551   121247788 :                         b->tnonil &= !isnil;
    1552   121247788 :                         b->tnil |= isnil;
    1553   121247788 :                         if (maxprop) {
    1554          34 :                                 if (!isnil &&
    1555          15 :                                     atomcmp(VALptr(maxprop), new) < 0) {
    1556             :                                         /* new value is larger than
    1557             :                                          * previous largest */
    1558           0 :                                         MT_lock_set(&b->theaplock);
    1559           0 :                                         maxprop = BATsetprop_nolock(b, GDK_MAX_VALUE, b->ttype, new);
    1560           0 :                                         BATsetprop_nolock(b, GDK_MAX_POS, TYPE_oid, &(oid){updid});
    1561           0 :                                         MT_lock_unset(&b->theaplock);
    1562          25 :                                 } else if (atomcmp(VALptr(maxprop), old) == 0 &&
    1563           6 :                                            atomcmp(new, old) != 0) {
    1564             :                                         /* old value is equal to
    1565             :                                          * largest and new value is
    1566             :                                          * smaller, so we don't know
    1567             :                                          * anymore which is the
    1568             :                                          * largest */
    1569           6 :                                         MT_lock_set(&b->theaplock);
    1570           6 :                                         BATrmprop_nolock(b, GDK_MAX_VALUE);
    1571           6 :                                         BATrmprop_nolock(b, GDK_MAX_POS);
    1572           6 :                                         MT_lock_unset(&b->theaplock);
    1573             :                                         maxprop = NULL;
    1574             :                                 }
    1575             :                         }
    1576   121247788 :                         if (minprop) {
    1577      432430 :                                 if (!isnil &&
    1578          22 :                                     atomcmp(VALptr(minprop), new) > 0) {
    1579             :                                         /* new value is smaller than
    1580             :                                          * previous smallest */
    1581           5 :                                         MT_lock_set(&b->theaplock);
    1582           5 :                                         minprop = BATsetprop_nolock(b, GDK_MIN_VALUE, b->ttype, new);
    1583           5 :                                         BATsetprop_nolock(b, GDK_MIN_POS, TYPE_oid, &(oid){updid});
    1584           5 :                                         MT_lock_unset(&b->theaplock);
    1585      432414 :                                 } else if (atomcmp(VALptr(minprop), old) == 0 &&
    1586           6 :                                            atomcmp(new, old) != 0) {
    1587             :                                         /* old value is equal to
    1588             :                                          * smallest and new value is
    1589             :                                          * larger, so we don't know
    1590             :                                          * anymore which is the
    1591             :                                          * smallest */
    1592           6 :                                         MT_lock_set(&b->theaplock);
    1593           6 :                                         BATrmprop_nolock(b, GDK_MIN_VALUE);
    1594           6 :                                         BATrmprop_nolock(b, GDK_MIN_POS);
    1595           6 :                                         MT_lock_unset(&b->theaplock);
    1596             :                                         minprop = NULL;
    1597             :                                 }
    1598             :                         }
    1599             : 
    1600   120815396 :                         if (!locked) {
    1601        6812 :                                 MT_rwlock_wrlock(&b->thashlock);
    1602             :                                 locked = true;
    1603             :                         }
    1604   120815403 :                         HASHdelete_locked(b, updid, old);
    1605   120095107 :                         switch (b->twidth) {
    1606     2654019 :                         case 1:
    1607     2654019 :                                 ((bte *) b->theap->base)[updid] = * (bte *) new;
    1608     2654019 :                                 break;
    1609       24531 :                         case 2:
    1610       24531 :                                 ((sht *) b->theap->base)[updid] = * (sht *) new;
    1611       24531 :                                 break;
    1612    19062525 :                         case 4:
    1613    19062525 :                                 ((int *) b->theap->base)[updid] = * (int *) new;
    1614    19062525 :                                 break;
    1615    96679645 :                         case 8:
    1616    96679645 :                                 ((lng *) b->theap->base)[updid] = * (lng *) new;
    1617    96679645 :                                 break;
    1618     1674387 :                         case 16:
    1619             : #ifdef HAVE_HGE
    1620     1674387 :                                 ((hge *) b->theap->base)[updid] = * (hge *) new;
    1621             : #else
    1622             :                                 ((uuid *) b->theap->base)[updid] = * (uuid *) new;
    1623             : #endif
    1624     1674387 :                                 break;
    1625           0 :                         default:
    1626           0 :                                 memcpy(BUNtloc(bi, updid), new, ATOMsize(b->ttype));
    1627           0 :                                 break;
    1628             :                         }
    1629   120095107 :                         HASHinsert_locked(b, updid, new);
    1630             :                 }
    1631        6819 :                 if (locked) {
    1632        6810 :                         MT_rwlock_wrunlock(&b->thashlock);
    1633             :                         locked = false;
    1634             :                 }
    1635             :         }
    1636       23612 :         bat_iterator_end(&ni);
    1637       23606 :         MT_lock_set(&b->theaplock);
    1638       23612 :         b->theap->dirty = true;
    1639       23612 :         MT_lock_unset(&b->theaplock);
    1640             : 
    1641       23610 :         TRC_DEBUG(ALGO,
    1642             :                   "BATreplace(" ALGOBATFMT "," ALGOOPTBATFMT "," ALGOBATFMT ") " LLFMT " usec\n",
    1643             :                   ALGOBATPAR(b), ALGOOPTBATPAR(p), ALGOBATPAR(n),
    1644             :                   GDKusec() - t0);
    1645             :         return GDK_SUCCEED;
    1646             : 
    1647           0 :   bailout:
    1648           0 :         bat_iterator_end(&ni);
    1649           0 :         if (locked) {
    1650           0 :                 Hash *h = b->thash;
    1651           0 :                 b->thash = NULL;
    1652           0 :                 MT_rwlock_wrunlock(&b->thashlock);
    1653           0 :                 doHASHdestroy(b, h);
    1654             :         }
    1655             :         return GDK_FAIL;
    1656             : }
    1657             : 
    1658             : /* replace values from b at locations specified in p with values in n */
    1659             : gdk_return
    1660      118673 : BATreplace(BAT *b, BAT *p, BAT *n, bool force)
    1661             : {
    1662      118673 :         return BATappend_or_update(b, p, NULL, n, false, false, force);
    1663             : }
    1664             : 
    1665             : /* like BATreplace, but p may specify locations beyond the end of b */
    1666             : gdk_return
    1667          14 : BATupdate(BAT *b, BAT *p, BAT *n, bool force)
    1668             : {
    1669          14 :         return BATappend_or_update(b, p, NULL, n, true, false, force);
    1670             : }
    1671             : 
    1672             : /* like BATreplace, but the positions are given by an array of oid values */
    1673             : gdk_return
    1674           0 : BATreplacepos(BAT *b, const oid *positions, BAT *n, bool autoincr, bool force)
    1675             : {
    1676           0 :         return BATappend_or_update(b, NULL, positions, n, false, autoincr, force);
    1677             : }
    1678             : 
    1679             : /* like BATreplace, but the positions are given by an array of oid
    1680             :  * values, and they may specify locations beyond the end of b */
    1681             : gdk_return
    1682         189 : BATupdatepos(BAT *b, const oid *positions, BAT *n, bool autoincr, bool force)
    1683             : {
    1684         189 :         return BATappend_or_update(b, NULL, positions, n, true, autoincr, force);
    1685             : }
    1686             : 
    1687             : /*
    1688             :  *  BAT Selections
    1689             :  * The BAT selectors are among the most heavily used operators.
    1690             :  * Their efficient implementation is therefore mandatory.
    1691             :  *
    1692             :  * BAT slice
    1693             :  * This function returns a horizontal slice from a BAT. It optimizes
    1694             :  * execution by avoiding to copy when the BAT is memory mapped (in
    1695             :  * this case, an independent submap is created) or else when it is
    1696             :  * read-only, then a VIEW bat is created as a result.
    1697             :  *
    1698             :  * If a new copy has to be created, this function takes care to
    1699             :  * preserve void-columns (in this case, the seqbase has to be
    1700             :  * recomputed in the result).
    1701             :  *
    1702             :  * The selected range is excluding the high value.
    1703             :  */
    1704             : BAT *
    1705     5706447 : BATslice(BAT *b, BUN l, BUN h)
    1706             : {
    1707             :         BUN low = l;
    1708             :         BAT *bn = NULL;
    1709             :         BATiter bni;
    1710             :         oid foid;               /* first oid value if oid column */
    1711             : 
    1712     5706447 :         BATcheck(b, NULL);
    1713     5706447 :         if (h > BATcount(b))
    1714             :                 h = BATcount(b);
    1715             :         if (h < l)
    1716             :                 h = l;
    1717             : 
    1718     5706447 :         if (l > BUN_MAX || h > BUN_MAX) {
    1719           0 :                 GDKerror("boundary out of range\n");
    1720           0 :                 goto doreturn;
    1721             :         }
    1722             : 
    1723     5706447 :         if (complex_cand(b)) {
    1724             :                 /* slicing a candidate list with exceptions */
    1725             :                 struct canditer ci;
    1726         161 :                 canditer_init(&ci, NULL, b);
    1727         161 :                 if (b->hseqbase + l >= ci.hseq) {
    1728         161 :                         l = b->hseqbase + l - ci.hseq;
    1729         161 :                         h = b->hseqbase + h - ci.hseq;
    1730             :                 } else {
    1731             :                         l = 0;
    1732           0 :                         if (b->hseqbase + h >= ci.hseq)
    1733           0 :                                 h = b->hseqbase + h - ci.hseq;
    1734             :                         else
    1735             :                                 h = 0;
    1736             :                 }
    1737         161 :                 bn = canditer_slice(&ci, l, h);
    1738         161 :                 goto doreturn;
    1739             :         }
    1740             :         /* If the source BAT is readonly, then we can obtain a VIEW
    1741             :          * that just reuses the memory of the source. */
    1742     5706286 :         if (ATOMstorage(b->ttype) == TYPE_msk) {
    1743             :                 /* forget about slices for bit masks: we can't deal
    1744             :                  * with difference in alignment, so we'll just make a
    1745             :                  * copy */
    1746           0 :                 bn = COLnew((oid) (b->hseqbase + low), b->ttype, h - l, TRANSIENT);
    1747             :                 /* we use BATappend with a candidate list to easily
    1748             :                  * copy the part of b that we need */
    1749           0 :                 BAT *s = BATdense(0, (oid) (b->hseqbase + low), h - l);
    1750           0 :                 if (bn == NULL ||
    1751           0 :                     s == NULL ||
    1752           0 :                     BATappend(bn, b, s, false) != GDK_SUCCEED) {
    1753           0 :                         BBPreclaim(bn);
    1754           0 :                         BBPreclaim(s);
    1755             :                         bn = NULL;
    1756           0 :                         goto doreturn;
    1757             :                 }
    1758           0 :                 BBPunfix(s->batCacheid);
    1759           0 :                 goto doreturn;
    1760     5706286 :         } else if (b->batRestricted == BAT_READ &&
    1761     5605681 :             (!VIEWtparent(b) ||
    1762     1839454 :              BBP_cache(VIEWtparent(b))->batRestricted == BAT_READ)) {
    1763     5607811 :                 bn = VIEWcreate(b->hseqbase + low, b);
    1764     5604672 :                 if (bn == NULL)
    1765           0 :                         goto doreturn;
    1766     5604672 :                 VIEWbounds(b, bn, l, h);
    1767             :         } else {
    1768             :                 /* create a new BAT and put everything into it */
    1769             :                 BUN p = l;
    1770             :                 BUN q = h;
    1771             : 
    1772      161277 :                 bn = COLnew((oid) (b->hseqbase + low), BATtdense(b) ? TYPE_void : b->ttype, h - l, TRANSIENT);
    1773       98618 :                 if (bn == NULL)
    1774           0 :                         goto doreturn;
    1775             : 
    1776       98618 :                 if (bn->ttype == TYPE_void ||
    1777       62833 :                     (!bn->tvarsized &&
    1778       29941 :                      BATatoms[bn->ttype].atomPut == NULL &&
    1779       29967 :                      BATatoms[bn->ttype].atomFix == NULL)) {
    1780       65761 :                         if (bn->ttype) {
    1781       30039 :                                 BATiter bi = bat_iterator(b);
    1782       29945 :                                 memcpy(Tloc(bn, 0), (const char *) bi.base + (p << bi.shift),
    1783       29945 :                                        (q - p) << bn->tshift);
    1784       29945 :                                 bat_iterator_end(&bi);
    1785       30090 :                                 bn->theap->dirty = true;
    1786             :                         }
    1787       65812 :                         BATsetcount(bn, h - l);
    1788             :                 } else {
    1789       32857 :                         BATiter bi = bat_iterator(b);
    1790     2422480 :                         for (; p < q; p++) {
    1791     2389563 :                                 if (bunfastapp(bn, BUNtail(bi, p)) != GDK_SUCCEED) {
    1792           0 :                                         bat_iterator_end(&bi);
    1793           0 :                                         BBPreclaim(bn);
    1794             :                                         bn = NULL;
    1795           0 :                                         goto doreturn;
    1796             :                                 }
    1797             :                         }
    1798       32917 :                         bat_iterator_end(&bi);
    1799             :                 }
    1800       98686 :                 bn->theap->dirty = true;
    1801       98686 :                 bn->tsorted = b->tsorted;
    1802       98686 :                 bn->trevsorted = b->trevsorted;
    1803       98686 :                 bn->tkey = b->tkey;
    1804       98686 :                 bn->tnonil = b->tnonil;
    1805       98686 :                 if (b->tnosorted > l && b->tnosorted < h)
    1806        5095 :                         bn->tnosorted = b->tnosorted - l;
    1807             :                 else
    1808       93591 :                         bn->tnosorted = 0;
    1809       98686 :                 if (b->tnorevsorted > l && b->tnorevsorted < h)
    1810       10400 :                         bn->tnorevsorted = b->tnorevsorted - l;
    1811             :                 else
    1812       88286 :                         bn->tnorevsorted = 0;
    1813       98686 :                 if (b->tnokey[0] >= l && b->tnokey[0] < h &&
    1814       84363 :                     b->tnokey[1] >= l && b->tnokey[1] < h &&
    1815             :                     b->tnokey[0] != b->tnokey[1]) {
    1816         570 :                         bn->tnokey[0] = b->tnokey[0] - l;
    1817         570 :                         bn->tnokey[1] = b->tnokey[1] - l;
    1818             :                 } else {
    1819       98116 :                         bn->tnokey[0] = bn->tnokey[1] = 0;
    1820             :                 }
    1821             :         }
    1822     5706735 :         bn->tnonil = b->tnonil || bn->batCount == 0;
    1823     5706735 :         bn->tnil = false;    /* we just don't know */
    1824     5706735 :         bn->tnosorted = 0;
    1825     5706735 :         bn->tnokey[0] = bn->tnokey[1] = 0;
    1826     5706735 :         bni = bat_iterator_nolock(bn);
    1827     5694185 :         if (BATtdense(b)) {
    1828       40690 :                 BATtseqbase(bn, (oid) (b->tseqbase + low));
    1829     5653495 :         } else if (bn->ttype == TYPE_oid) {
    1830       19010 :                 if (BATcount(bn) == 0) {
    1831           7 :                         BATtseqbase(bn, 0);
    1832       19003 :                 } else if (!is_oid_nil((foid = *(oid *) BUNtloc(bni, 0))) &&
    1833       17220 :                            (BATcount(bn) == 1 ||
    1834       17220 :                             (bn->tkey &&
    1835        7243 :                              bn->tsorted &&
    1836        7243 :                              foid + BATcount(bn) - 1 == *(oid *) BUNtloc(bni, BUNlast(bn) - 1)))) {
    1837        2105 :                         BATtseqbase(bn, foid);
    1838             :                 }
    1839             :         }
    1840     5696997 :         if (bn->batCount <= 1) {
    1841      575083 :                 bn->tsorted = ATOMlinear(b->ttype);
    1842      575083 :                 bn->trevsorted = ATOMlinear(b->ttype);
    1843      575083 :                 BATkey(bn, true);
    1844             :         } else {
    1845     5121914 :                 bn->tsorted = b->tsorted;
    1846     5121914 :                 bn->trevsorted = b->trevsorted;
    1847     9860322 :                 BATkey(bn, BATtkey(b));
    1848             :         }
    1849     5696801 :   doreturn:
    1850     5696801 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",lo=" BUNFMT ",hi=" BUNFMT " -> "
    1851             :                   ALGOOPTBATFMT "\n",
    1852             :                   ALGOBATPAR(b), l, h, ALGOOPTBATPAR(bn));
    1853             :         return bn;
    1854             : }
    1855             : 
    1856             : #define BAT_ORDERED(TPE)                                                \
    1857             :         do {                                                            \
    1858             :                 const TPE *restrict vals = Tloc(b, 0);                  \
    1859             :                 for (BUN q = BUNlast(b), p = 1; p < q; p++) {                \
    1860             :                         if (vals[p - 1] > vals[p]) {                 \
    1861             :                                 b->tnosorted = p;                    \
    1862             :                                 TRC_DEBUG(ALGO, "Fixed nosorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0); \
    1863             :                                 goto doreturn;                          \
    1864             :                         } else if (vals[p - 1] < vals[p]) {          \
    1865             :                                 if (!b->trevsorted && b->tnorevsorted == 0) { \
    1866             :                                         b->tnorevsorted = p;         \
    1867             :                                         TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT "\n", p, ALGOBATPAR(b)); \
    1868             :                                 }                                       \
    1869             :                         } else if (!b->tkey && b->tnokey[1] == 0) {       \
    1870             :                                 b->tnokey[0] = p - 1;                        \
    1871             :                                 b->tnokey[1] = p;                    \
    1872             :                                 TRC_DEBUG(ALGO, "Fixed nokey(" BUNFMT "," BUNFMT") for " ALGOBATFMT "\n", p - 1, p, ALGOBATPAR(b)); \
    1873             :                         }                                               \
    1874             :                 }                                                       \
    1875             :         } while (0)
    1876             : 
    1877             : #define BAT_ORDERED_FP(TPE)                                             \
    1878             :         do {                                                            \
    1879             :                 const TPE *restrict vals = Tloc(b, 0);                  \
    1880             :                 TPE prev = vals[0];                                     \
    1881             :                 bool prevnil = is_##TPE##_nil(prev);                    \
    1882             :                 for (BUN q = BUNlast(b), p = 1; p < q; p++) {                \
    1883             :                         TPE next = vals[p];                             \
    1884             :                         int cmp = prevnil ? -!(prevnil = is_##TPE##_nil(next)) : (prevnil = is_##TPE##_nil(next)) ? 1 : (prev > next) - (prev < next); \
    1885             :                         prev = next;                                    \
    1886             :                         if (cmp > 0) {                                       \
    1887             :                                 b->tnosorted = p;                    \
    1888             :                                 TRC_DEBUG(ALGO, "Fixed nosorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0); \
    1889             :                                 goto doreturn;                          \
    1890             :                         } else if (cmp < 0) {                                \
    1891             :                                 if (!b->trevsorted && b->tnorevsorted == 0) { \
    1892             :                                         b->tnorevsorted = p;         \
    1893             :                                         TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT "\n", p, ALGOBATPAR(b)); \
    1894             :                                 }                                       \
    1895             :                         } else if (!b->tkey && b->tnokey[1] == 0) {       \
    1896             :                                 b->tnokey[0] = p - 1;                        \
    1897             :                                 b->tnokey[1] = p;                    \
    1898             :                                 TRC_DEBUG(ALGO, "Fixed nokey(" BUNFMT "," BUNFMT") for " ALGOBATFMT "\n", p - 1, p, ALGOBATPAR(b)); \
    1899             :                         }                                               \
    1900             :                 }                                                       \
    1901             :         } while (0)
    1902             : 
    1903             : /* Return whether the BAT is ordered or not.  If we don't know, invest
    1904             :  * in a scan and record the results in the bat descriptor.  If during
    1905             :  * the scan we happen to find evidence that the BAT is not reverse
    1906             :  * sorted, we record the location.  */
    1907             : bool
    1908      627358 : BATordered(BAT *b)
    1909             : {
    1910      627358 :         lng t0 = GDKusec();
    1911             : 
    1912      629259 :         if (b->ttype == TYPE_void || b->tsorted || BATcount(b) == 0)
    1913             :                 return true;
    1914      438153 :         if (b->tnosorted > 0 || !ATOMlinear(b->ttype))
    1915             :                 return false;
    1916             : 
    1917             :         /* In order that multiple threads don't scan the same BAT at the
    1918             :          * same time (happens a lot with mitosis/mergetable), we use a
    1919             :          * lock.  We reuse the batIdxLock lock for this, not because this
    1920             :          * scanning interferes with heap reference counting, but because
    1921             :          * it's there, and not so likely to be used at the same time. */
    1922      261756 :         MT_lock_set(&b->batIdxLock);
    1923      262265 :         BATiter bi = bat_iterator_nolock(b);
    1924      260884 :         if (!b->tsorted && b->tnosorted == 0) {
    1925      260710 :                 b->batDirtydesc = true;
    1926      404817 :                 switch (ATOMbasetype(b->ttype)) {
    1927      108199 :                 case TYPE_bte:
    1928    92507723 :                         BAT_ORDERED(bte);
    1929             :                         break;
    1930        7702 :                 case TYPE_sht:
    1931      553127 :                         BAT_ORDERED(sht);
    1932             :                         break;
    1933      103901 :                 case TYPE_int:
    1934    78093229 :                         BAT_ORDERED(int);
    1935             :                         break;
    1936       13778 :                 case TYPE_lng:
    1937    45251982 :                         BAT_ORDERED(lng);
    1938             :                         break;
    1939             : #ifdef HAVE_HGE
    1940         585 :                 case TYPE_hge:
    1941        3518 :                         BAT_ORDERED(hge);
    1942             :                         break;
    1943             : #endif
    1944          78 :                 case TYPE_flt:
    1945         224 :                         BAT_ORDERED_FP(flt);
    1946             :                         break;
    1947         395 :                 case TYPE_dbl:
    1948      396282 :                         BAT_ORDERED_FP(dbl);
    1949             :                         break;
    1950       26031 :                 case TYPE_str:
    1951    13404800 :                         for (BUN q = BUNlast(b), p = 1; p < q; p++) {
    1952             :                                 int c;
    1953    13402415 :                                 const char *p1 = BUNtail(bi, p - 1);
    1954    13410895 :                                 const char *p2 = BUNtail(bi, p);
    1955    13402480 :                                 if (p1 == p2)
    1956             :                                         c = 0;
    1957      115791 :                                 else if (p1[0] == '\200') {
    1958         738 :                                         if (p2[0] == '\200')
    1959             :                                                 c = 0;
    1960             :                                         else
    1961             :                                                 c = -1;
    1962      115053 :                                 } else if (p2[0] == '\200')
    1963             :                                         c = 1;
    1964             :                                 else
    1965      114499 :                                         c = strcmp(p1, p2);
    1966      114499 :                                 if (c > 0) {
    1967       23711 :                                         b->tnosorted = p;
    1968       23711 :                                         TRC_DEBUG(ALGO, "Fixed nosorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0);
    1969       23711 :                                         goto doreturn;
    1970    13378769 :                                 } else if (c < 0) {
    1971       92046 :                                         assert(!b->trevsorted);
    1972       92046 :                                         if (b->tnorevsorted == 0) {
    1973       10948 :                                                 b->tnorevsorted = p;
    1974       10948 :                                                 TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT "\n", p, ALGOBATPAR(b));
    1975             :                                         }
    1976    13286723 :                                 } else if (b->tnokey[1] == 0) {
    1977        9684 :                                         assert(!b->tkey);
    1978        9684 :                                         b->tnokey[0] = p - 1;
    1979        9684 :                                         b->tnokey[1] = p;
    1980        9684 :                                         TRC_DEBUG(ALGO, "Fixed nokey(" BUNFMT "," BUNFMT") for " ALGOBATFMT "\n", p - 1, p, ALGOBATPAR(b));
    1981             :                                 }
    1982             :                         }
    1983             :                         break;
    1984          41 :                 default: {
    1985          41 :                         int (*cmpf)(const void *, const void *) = ATOMcompare(b->ttype);
    1986         136 :                         for (BUN q = BUNlast(b), p = 1; p < q; p++) {
    1987             :                                 int c;
    1988         126 :                                 if ((c = cmpf(BUNtail(bi, p - 1), BUNtail(bi, p))) > 0) {
    1989          31 :                                         b->tnosorted = p;
    1990          31 :                                         TRC_DEBUG(ALGO, "Fixed nosorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0);
    1991          31 :                                         goto doreturn;
    1992          95 :                                 } else if (c < 0) {
    1993          31 :                                         if (!b->trevsorted && b->tnorevsorted == 0) {
    1994          17 :                                                 b->tnorevsorted = p;
    1995          17 :                                                 TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT "\n", p, ALGOBATPAR(b));
    1996             :                                         }
    1997          64 :                                 } else if (!b->tkey && b->tnokey[1] == 0) {
    1998           9 :                                         b->tnokey[0] = p - 1;
    1999           9 :                                         b->tnokey[1] = p;
    2000           9 :                                         TRC_DEBUG(ALGO, "Fixed nokey(" BUNFMT "," BUNFMT") for " ALGOBATFMT "\n", p - 1, p, ALGOBATPAR(b));
    2001             :                                 }
    2002             :                         }
    2003             :                         break;
    2004             :                 }
    2005             :                 }
    2006             :                 /* we only get here if we completed the scan; note that
    2007             :                  * if we didn't record evidence about *reverse*
    2008             :                  * sortedness, we know that the BAT is also reverse
    2009             :                  * sorted; similarly, if we didn't record evidence about
    2010             :                  * keyness, we know the BAT is key */
    2011      116845 :                 b->tsorted = true;
    2012      116845 :                 TRC_DEBUG(ALGO, "Fixed sorted for " ALGOBATFMT " (" LLFMT " usec)\n", ALGOBATPAR(b), GDKusec() - t0);
    2013      116781 :                 if (!b->trevsorted && b->tnorevsorted == 0) {
    2014       64635 :                         b->trevsorted = true;
    2015       64635 :                         TRC_DEBUG(ALGO, "Fixed revsorted for " ALGOBATFMT "\n", ALGOBATPAR(b));
    2016             :                 }
    2017      116781 :                 if (!b->tkey && b->tnokey[1] == 0) {
    2018       27046 :                         b->tkey = true;
    2019       27046 :                         TRC_DEBUG(ALGO, "Fixed key for " ALGOBATFMT "\n", ALGOBATPAR(b));
    2020             :                 }
    2021             :         }
    2022      116955 :   doreturn:
    2023      261491 :         MT_lock_unset(&b->batIdxLock);
    2024      262177 :         return b->tsorted;
    2025             : }
    2026             : 
    2027             : #define BAT_REVORDERED(TPE)                                             \
    2028             :         do {                                                            \
    2029             :                 const TPE *restrict vals = Tloc(b, 0);                  \
    2030             :                 for (BUN q = BUNlast(b), p = 1; p < q; p++) {                \
    2031             :                         if (vals[p - 1] < vals[p]) {                 \
    2032             :                                 b->tnorevsorted = p;                 \
    2033             :                                 TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0); \
    2034             :                                 goto doreturn;                          \
    2035             :                         }                                               \
    2036             :                 }                                                       \
    2037             :         } while (0)
    2038             : 
    2039             : #define BAT_REVORDERED_FP(TPE)                                          \
    2040             :         do {                                                            \
    2041             :                 const TPE *restrict vals = Tloc(b, 0);                  \
    2042             :                 for (BUN q = BUNlast(b), p = 1; p < q; p++) {                \
    2043             :                         TPE prev = vals[p - 1], next = vals[p];         \
    2044             :                         int cmp = is_flt_nil(prev) ? -!is_flt_nil(next) : is_flt_nil(next) ? 1 : (prev > next) - (prev < next);   \
    2045             :                         if (cmp < 0) {                                       \
    2046             :                                 b->tnorevsorted = p;                 \
    2047             :                                 TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0); \
    2048             :                                 goto doreturn;                          \
    2049             :                         }                                               \
    2050             :                 }                                                       \
    2051             :         } while (0)
    2052             : 
    2053             : /* Return whether the BAT is reverse ordered or not.  If we don't
    2054             :  * know, invest in a scan and record the results in the bat
    2055             :  * descriptor.  */
    2056             : bool
    2057      502467 : BATordered_rev(BAT *b)
    2058             : {
    2059      502467 :         lng t0 = GDKusec();
    2060             : 
    2061      503762 :         if (b == NULL || !ATOMlinear(b->ttype))
    2062             :                 return false;
    2063      503762 :         if (BATcount(b) <= 1 || b->trevsorted)
    2064             :                 return true;
    2065      373240 :         if (b->ttype == TYPE_void)
    2066       21488 :                 return is_oid_nil(b->tseqbase);
    2067      351752 :         if (BATtdense(b) || b->tnorevsorted > 0)
    2068             :                 return false;
    2069       76209 :         MT_lock_set(&b->batIdxLock);
    2070       76554 :         BATiter bi = bat_iterator_nolock(b);
    2071       76138 :         if (!b->trevsorted && b->tnorevsorted == 0) {
    2072       76105 :                 b->batDirtydesc = true;
    2073      127584 :                 switch (ATOMbasetype(b->ttype)) {
    2074       22074 :                 case TYPE_bte:
    2075     5653442 :                         BAT_REVORDERED(bte);
    2076             :                         break;
    2077        2719 :                 case TYPE_sht:
    2078      209955 :                         BAT_REVORDERED(sht);
    2079             :                         break;
    2080       32716 :                 case TYPE_int:
    2081      565062 :                         BAT_REVORDERED(int);
    2082             :                         break;
    2083        5213 :                 case TYPE_lng:
    2084      152375 :                         BAT_REVORDERED(lng);
    2085             :                         break;
    2086             : #ifdef HAVE_HGE
    2087         516 :                 case TYPE_hge:
    2088        2354 :                         BAT_REVORDERED(hge);
    2089             :                         break;
    2090             : #endif
    2091          38 :                 case TYPE_flt:
    2092         128 :                         BAT_REVORDERED_FP(flt);
    2093             :                         break;
    2094         200 :                 case TYPE_dbl:
    2095        1053 :                         BAT_REVORDERED_FP(dbl);
    2096             :                         break;
    2097       12629 :                 default: {
    2098       12629 :                         int (*cmpf)(const void *, const void *) = ATOMcompare(b->ttype);
    2099     1166481 :                         for (BUN q = BUNlast(b), p = 1; p < q; p++) {
    2100     1166060 :                                 if (cmpf(BUNtail(bi, p - 1), BUNtail(bi, p)) < 0) {
    2101       12208 :                                         b->tnorevsorted = p;
    2102       12208 :                                         TRC_DEBUG(ALGO, "Fixed norevsorted(" BUNFMT ") for " ALGOBATFMT " (" LLFMT " usec)\n", p, ALGOBATPAR(b), GDKusec() - t0);
    2103       12208 :                                         goto doreturn;
    2104             :                                 }
    2105             :                         }
    2106             :                         break;
    2107             :                 }
    2108             :                 }
    2109       10737 :                 b->trevsorted = true;
    2110       10737 :                 TRC_DEBUG(ALGO, "Fixed revsorted for " ALGOBATFMT " (" LLFMT " usec)\n", ALGOBATPAR(b), GDKusec() - t0);
    2111             :         }
    2112       10770 :   doreturn:
    2113       76138 :         MT_lock_unset(&b->batIdxLock);
    2114       76417 :         return b->trevsorted;
    2115             : }
    2116             : 
    2117             : /* figure out which sort function is to be called
    2118             :  * stable sort can produce an error (not enough memory available),
    2119             :  * "quick" sort does not produce errors */
    2120             : static gdk_return
    2121     3994775 : do_sort(void *restrict h, void *restrict t, const void *restrict base,
    2122             :         size_t n, int hs, int ts, int tpe, bool reverse, bool nilslast,
    2123             :         bool stable)
    2124             : {
    2125     3994775 :         if (n <= 1)          /* trivially sorted */
    2126             :                 return GDK_SUCCEED;
    2127     2742039 :         if (stable) {
    2128         183 :                 if (reverse)
    2129           1 :                         return GDKssort_rev(h, t, base, n, hs, ts, tpe);
    2130             :                 else
    2131         182 :                         return GDKssort(h, t, base, n, hs, ts, tpe);
    2132             :         } else {
    2133     2741856 :                 GDKqsort(h, t, base, n, hs, ts, tpe, reverse, nilslast);
    2134             :         }
    2135     2741858 :         return GDK_SUCCEED;
    2136             : }
    2137             : 
    2138             : /* Sort the bat b according to both o and g.  The stable and reverse
    2139             :  * parameters indicate whether the sort should be stable or descending
    2140             :  * respectively.  The parameter b is required, o and g are optional
    2141             :  * (i.e., they may be NULL).
    2142             :  *
    2143             :  * A sorted copy is returned through the sorted parameter, the new
    2144             :  * ordering is returned through the order parameter, group information
    2145             :  * is returned through the groups parameter.  All three output
    2146             :  * parameters may be NULL.  If they're all NULL, this function does
    2147             :  * nothing.
    2148             :  *
    2149             :  * If o is specified, it is used to first rearrange b according to the
    2150             :  * order specified in o, after which b is sorted taking g into
    2151             :  * account.
    2152             :  *
    2153             :  * If g is specified, it indicates groups which should be individually
    2154             :  * ordered.  Each row of consecutive equal values in g indicates a
    2155             :  * group which is sorted according to stable and reverse.  g is used
    2156             :  * after the order in b was rearranged according to o.
    2157             :  *
    2158             :  * The outputs order and groups can be used in subsequent calls to
    2159             :  * this function.  This can be used if multiple BATs need to be sorted
    2160             :  * together.  The BATs should then be sorted in order of significance,
    2161             :  * and each following call should use the original unordered BAT plus
    2162             :  * the order and groups bat from the previous call.  In this case, the
    2163             :  * sorted BATs are not of much use, so the sorted output parameter
    2164             :  * does not need to be specified.
    2165             :  * Apart from error checking and maintaining reference counts, sorting
    2166             :  * three columns (col1, col2, col3) could look like this with the
    2167             :  * sorted results in (col1s, col2s, col3s):
    2168             :  *      BATsort(&col1s, &ord1, &grp1, col1, NULL, NULL, false, false, false);
    2169             :  *      BATsort(&col2s, &ord2, &grp2, col2, ord1, grp1, false, false, false);
    2170             :  *      BATsort(&col3s,  NULL,  NULL, col3, ord2, grp2, false, false, false);
    2171             :  * Note that the "reverse" parameter can be different for each call.
    2172             :  */
    2173             : gdk_return
    2174       37149 : BATsort(BAT **sorted, BAT **order, BAT **groups,
    2175             :         BAT *b, BAT *o, BAT *g, bool reverse, bool nilslast, bool stable)
    2176             : {
    2177             :         BAT *bn = NULL, *on = NULL, *gn = NULL, *pb = NULL;
    2178             :         oid *restrict grps, *restrict ords, prev;
    2179             :         BUN p, q, r;
    2180       37149 :         lng t0 = GDKusec();
    2181             :         bool mkorderidx, orderidxlock = false;
    2182             :         Heap *oidxh = NULL;
    2183             : 
    2184             :         /* we haven't implemented NILs as largest value for stable
    2185             :          * sort, so NILs come first for ascending and last for
    2186             :          * descending */
    2187       37150 :         assert(!stable || reverse == nilslast);
    2188             : 
    2189       37150 :         if (b == NULL) {
    2190           0 :                 GDKerror("b must exist\n");
    2191           0 :                 return GDK_FAIL;
    2192             :         }
    2193       37150 :         if (stable && reverse != nilslast) {
    2194           0 :                 GDKerror("stable sort cannot have reverse != nilslast\n");
    2195           0 :                 return GDK_FAIL;
    2196             :         }
    2197       37150 :         if (!ATOMlinear(b->ttype)) {
    2198           0 :                 GDKerror("type %s cannot be sorted\n", ATOMname(b->ttype));
    2199           0 :                 return GDK_FAIL;
    2200             :         }
    2201       37150 :         if (b->ttype == TYPE_void) {
    2202         152 :                 if (!b->tsorted) {
    2203           0 :                         b->tsorted = true;
    2204           0 :                         b->batDirtydesc = true;
    2205             :                 }
    2206         189 :                 if (b->trevsorted != (is_oid_nil(b->tseqbase) || b->batCount <= 1)) {
    2207           0 :                         b->trevsorted = !b->trevsorted;
    2208           0 :                         b->batDirtydesc = true;
    2209             :                 }
    2210         152 :                 if (b->tkey != (!is_oid_nil(b->tseqbase) || b->batCount <= 1)) {
    2211           0 :                         b->tkey = !b->tkey;
    2212           0 :                         b->batDirtydesc = true;
    2213             :                 }
    2214       36998 :         } else if (b->batCount <= 1) {
    2215       15616 :                 if (!b->tsorted || !b->trevsorted) {
    2216           0 :                         b->tsorted = b->trevsorted = true;
    2217           0 :                         b->batDirtydesc = true;
    2218             :                 }
    2219             :         }
    2220       37150 :         if (o != NULL &&
    2221       19189 :             (ATOMtype(o->ttype) != TYPE_oid || /* oid tail */
    2222       19189 :              BATcount(o) != BATcount(b) ||     /* same size as b */
    2223        8252 :              (o->ttype == TYPE_void &&              /* no nil tail */
    2224        3659 :               BATcount(o) != 0 &&
    2225        3659 :               is_oid_nil(o->tseqbase)))) {
    2226           2 :                 GDKerror("o must have type oid and same size as b\n");
    2227           0 :                 return GDK_FAIL;
    2228             :         }
    2229       37148 :         if (g != NULL &&
    2230       19187 :             (ATOMtype(g->ttype) != TYPE_oid || /* oid tail */
    2231       19187 :              !g->tsorted ||                 /* sorted */
    2232       19187 :              BATcount(o) != BATcount(b) ||     /* same size as b */
    2233        8219 :              (g->ttype == TYPE_void &&              /* no nil tail */
    2234        8219 :               BATcount(g) != 0 &&
    2235        3925 :               is_oid_nil(g->tseqbase)))) {
    2236           0 :                 GDKerror("g must have type oid, sorted on the tail, "
    2237             :                          "and same size as b\n");
    2238           0 :                 return GDK_FAIL;
    2239             :         }
    2240       37148 :         if (sorted == NULL && order == NULL) {
    2241             :                 /* no place to put result, so we're done quickly */
    2242           0 :                 GDKerror("no place to put the result.\n");
    2243           0 :                 return GDK_FAIL;
    2244             :         }
    2245       37148 :         if (g == NULL && !stable) {
    2246             :                 /* pre-ordering doesn't make sense if we're not
    2247             :                  * subsorting and the sort is not stable */
    2248             :                 o = NULL;
    2249             :         }
    2250       37148 :         if (b->tnonil) {
    2251             :                 /* if there are no nils, placement of nils doesn't
    2252             :                  * matter, so set nilslast such that ordered bits can
    2253             :                  * be used */
    2254             :                 nilslast = reverse;
    2255             :         }
    2256       37921 :         if (BATcount(b) <= 1 ||
    2257       21396 :             (reverse == nilslast &&
    2258             :              (reverse ? BATtrevordered(b) : BATtordered(b)) &&
    2259        3639 :              o == NULL && g == NULL &&
    2260        1974 :              (groups == NULL || BATtkey(b) ||
    2261             :               (reverse ? BATtordered(b) : BATtrevordered(b))))) {
    2262             :                 /* trivially (sub)sorted, and either we don't need to
    2263             :                  * return group information, or we can trivially
    2264             :                  * deduce the groups */
    2265       16990 :                 if (sorted) {
    2266       16159 :                         bn = COLcopy(b, b->ttype, false, TRANSIENT);
    2267       16159 :                         if (bn == NULL)
    2268           0 :                                 goto error;
    2269       16159 :                         *sorted = bn;
    2270             :                 }
    2271       16990 :                 if (order) {
    2272       16886 :                         on = BATdense(b->hseqbase, b->hseqbase, BATcount(b));
    2273       16887 :                         if (on == NULL)
    2274           0 :                                 goto error;
    2275       16887 :                         *order = on;
    2276             :                 }
    2277       16991 :                 if (groups) {
    2278        8152 :                         if (BATtkey(b)) {
    2279             :                                 /* singleton groups */
    2280        7521 :                                 gn = BATdense(0, 0, BATcount(b));
    2281        7521 :                                 if (gn == NULL)
    2282           0 :                                         goto error;
    2283             :                         } else {
    2284             :                                 /* single group */
    2285         631 :                                 const oid *o = 0;
    2286         631 :                                 assert(BATcount(b) == 1 ||
    2287             :                                        (BATtordered(b) && BATtrevordered(b)));
    2288         631 :                                 gn = BATconstant(0, TYPE_oid, &o, BATcount(b), TRANSIENT);
    2289         631 :                                 if (gn == NULL)
    2290           0 :                                         goto error;
    2291             :                         }
    2292        8152 :                         *groups = gn;
    2293             :                 }
    2294       16991 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",o="
    2295             :                           ALGOOPTBATFMT ",g=" ALGOOPTBATFMT
    2296             :                           ",reverse=%d,nilslast=%d,stable=%d) = ("
    2297             :                           ALGOOPTBATFMT "," ALGOOPTBATFMT ","
    2298             :                           ALGOOPTBATFMT " -- trivial (" LLFMT
    2299             :                           " usec)\n",
    2300             :                           ALGOBATPAR(b), ALGOOPTBATPAR(o),
    2301             :                           ALGOOPTBATPAR(g), reverse, nilslast, stable,
    2302             :                           ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn),
    2303             :                           ALGOOPTBATPAR(on), GDKusec() - t0);
    2304       16991 :                 return GDK_SUCCEED;
    2305             :         }
    2306       20158 :         if (VIEWtparent(b)) {
    2307        3439 :                 pb = BBP_cache(VIEWtparent(b));
    2308        3439 :                 if (b->tbaseoff != pb->tbaseoff ||
    2309        2690 :                     BATcount(b) != BATcount(pb) ||
    2310        2482 :                     b->hseqbase != pb->hseqbase ||
    2311        2482 :                     BATatoms[b->ttype].atomCmp != BATatoms[pb->ttype].atomCmp)
    2312             :                         pb = NULL;
    2313             :         } else {
    2314             :                 pb = b;
    2315             :         }
    2316             :         /* when we will create an order index if it doesn't already exist */
    2317       20158 :         mkorderidx = (g == NULL && !reverse && !nilslast && pb != NULL && (order || !pb->batTransient));
    2318       20158 :         if (g == NULL && !reverse && !nilslast && pb != NULL) {
    2319        7132 :                 (void) BATcheckorderidx(pb);
    2320        7132 :                 MT_lock_set(&pb->batIdxLock);
    2321        7131 :                 if (pb->torderidx) {
    2322          39 :                         if (!stable || ((oid *) pb->torderidx->base)[2]) {
    2323             :                                 /* we can use the order index */
    2324             :                                 oidxh = pb->torderidx;
    2325          39 :                                 HEAPincref(oidxh);
    2326             :                         }
    2327             :                         mkorderidx = false;
    2328        7092 :                 } else if (b != pb) {
    2329             :                         /* don't build orderidx on parent bat */
    2330             :                         mkorderidx = false;
    2331        5948 :                 } else if (mkorderidx) {
    2332             :                         /* keep lock when going to create */
    2333             :                         orderidxlock = true;
    2334             :                 }
    2335        7131 :                 if (!orderidxlock)
    2336        1255 :                         MT_lock_unset(&pb->batIdxLock);
    2337             :         }
    2338       20157 :         if (g == NULL && o == NULL && !reverse && !nilslast && oidxh != NULL) {
    2339             :                 /* there is an order index that we can use */
    2340          39 :                 on = COLnew(pb->hseqbase, TYPE_oid, BATcount(pb), TRANSIENT);
    2341          39 :                 if (on == NULL)
    2342           0 :                         goto error;
    2343          39 :                 memcpy(Tloc(on, 0), (oid *) oidxh->base + ORDERIDXOFF, BATcount(pb) * sizeof(oid));
    2344          39 :                 BATsetcount(on, BATcount(b));
    2345          39 :                 HEAPdecref(oidxh, false);
    2346             :                 oidxh = NULL;
    2347          39 :                 on->tkey = true;
    2348          39 :                 on->tnil = false;
    2349          39 :                 on->tnonil = true;
    2350          39 :                 on->tsorted = on->trevsorted = false;
    2351          39 :                 on->tseqbase = oid_nil;
    2352          39 :                 if (sorted || groups) {
    2353          37 :                         bn = BATproject(on, b);
    2354          37 :                         if (bn == NULL)
    2355           0 :                                 goto error;
    2356          37 :                         bn->tsorted = true;
    2357          37 :                         if (groups) {
    2358           0 :                                 if (BATgroup_internal(groups, NULL, NULL, bn, NULL, g, NULL, NULL, true) != GDK_SUCCEED)
    2359           0 :                                         goto error;
    2360           0 :                                 if (sorted &&
    2361           0 :                                     (*groups)->tkey &&
    2362             :                                     g == NULL) {
    2363             :                                         /* if new groups bat is key
    2364             :                                          * and since there is no input
    2365             :                                          * groups bat, we know the
    2366             :                                          * result bat is key */
    2367           0 :                                         bn->tkey = true;
    2368             :                                 }
    2369             :                         }
    2370          37 :                         if (sorted)
    2371          37 :                                 *sorted = bn;
    2372             :                         else {
    2373           0 :                                 BBPunfix(bn->batCacheid);
    2374             :                                 bn = NULL;
    2375             :                         }
    2376             :                 }
    2377          39 :                 if (order)
    2378           7 :                         *order = on;
    2379             :                 else {
    2380          32 :                         BBPunfix(on->batCacheid);
    2381             :                         on = NULL;
    2382             :                 }
    2383          39 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",o="
    2384             :                           ALGOOPTBATFMT ",g=" ALGOOPTBATFMT
    2385             :                           ",reverse=%d,nilslast=%d,stable=%d) = ("
    2386             :                           ALGOOPTBATFMT "," ALGOOPTBATFMT ","
    2387             :                           ALGOOPTBATFMT " -- orderidx (" LLFMT
    2388             :                           " usec)\n",
    2389             :                           ALGOBATPAR(b), ALGOOPTBATPAR(o),
    2390             :                           ALGOOPTBATPAR(g), reverse, nilslast, stable,
    2391             :                           ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn),
    2392             :                           ALGOOPTBATPAR(on), GDKusec() - t0);
    2393          39 :                 return GDK_SUCCEED;
    2394       20118 :         } else if (oidxh) {
    2395           0 :                 HEAPdecref(oidxh, false);
    2396             :                 oidxh = NULL;
    2397             :         }
    2398       20119 :         if (o) {
    2399       12000 :                 bn = BATproject(o, b);
    2400       12000 :                 if (bn == NULL)
    2401           0 :                         goto error;
    2402       12000 :                 if (bn->ttype == TYPE_void || isVIEW(bn)) {
    2403        3980 :                         BAT *b2 = COLcopy(bn, ATOMtype(bn->ttype), true, TRANSIENT);
    2404        1991 :                         BBPunfix(bn->batCacheid);
    2405             :                         bn = b2;
    2406             :                 }
    2407             :                 pb = NULL;
    2408             :         } else {
    2409        8119 :                 bn = COLcopy(b, b->ttype, true, TRANSIENT);
    2410             :         }
    2411       20119 :         if (bn == NULL)
    2412           0 :                 goto error;
    2413       20119 :         if (order) {
    2414             :                 /* prepare order bat */
    2415       19940 :                 if (o) {
    2416             :                         /* make copy of input so that we can refine it;
    2417             :                          * copy can be read-only if we take the shortcut
    2418             :                          * below in the case g is "key" */
    2419       11982 :                         on = COLcopy(o, TYPE_oid,
    2420       11982 :                                      g == NULL ||
    2421       11982 :                                      !(g->tkey || g->ttype == TYPE_void),
    2422             :                                      TRANSIENT);
    2423       11982 :                         if (on == NULL)
    2424           0 :                                 goto error;
    2425       11982 :                         BAThseqbase(on, b->hseqbase);
    2426             :                 } else {
    2427             :                         /* create new order */
    2428        7958 :                         on = COLnew(b->hseqbase, TYPE_oid, BATcount(bn), TRANSIENT);
    2429        7959 :                         if (on == NULL)
    2430           0 :                                 goto error;
    2431        7959 :                         ords = (oid *) Tloc(on, 0);
    2432    23367850 :                         for (p = 0, q = BATcount(bn); p < q; p++)
    2433    23359891 :                                 ords[p] = p + b->hseqbase;
    2434        7959 :                         BATsetcount(on, BATcount(bn));
    2435        7959 :                         on->tkey = true;
    2436        7959 :                         on->tnil = false;
    2437        7959 :                         on->tnonil = true;
    2438             :                 }
    2439             :                 /* COLcopy above can create TYPE_void */
    2440       19939 :                 if (on->ttype != TYPE_void) {
    2441       19186 :                         on->tsorted = on->trevsorted = false; /* it won't be sorted */
    2442       19186 :                         on->tseqbase = oid_nil;      /* and hence not dense */
    2443       19186 :                         on->tnosorted = on->tnorevsorted = 0;
    2444             :                 }
    2445       19939 :                 *order = on;
    2446       19939 :                 ords = (oid *) Tloc(on, 0);
    2447             :         } else {
    2448             :                 ords = NULL;
    2449             :         }
    2450       20118 :         if (g) {
    2451       12001 :                 if (g->tkey || g->ttype == TYPE_void) {
    2452             :                         /* if g is "key", all groups are size 1, so no
    2453             :                          * subsorting needed */
    2454        5812 :                         if (sorted) {
    2455        5307 :                                 *sorted = bn;
    2456             :                         } else {
    2457         505 :                                 BBPunfix(bn->batCacheid);
    2458             :                                 bn = NULL;
    2459             :                         }
    2460        5812 :                         if (order) {
    2461        5811 :                                 *order = on;
    2462        5811 :                                 if (o) {
    2463             :                                         /* we can inherit sortedness
    2464             :                                          * after all */
    2465        5811 :                                         on->tsorted = o->tsorted;
    2466        5811 :                                         on->trevsorted = o->trevsorted;
    2467        5811 :                                         if (o->tnosorted)
    2468         245 :                                                 on->tnosorted = o->tnosorted;
    2469        5811 :                                         if (o->tnorevsorted)
    2470          25 :                                                 on->tnorevsorted = o->tnorevsorted;
    2471             :                                 } else {
    2472             :                                         /* we didn't rearrange, so
    2473             :                                          * still sorted */
    2474           0 :                                         on->tsorted = true;
    2475           0 :                                         on->trevsorted = false;
    2476             :                                 }
    2477        5811 :                                 if (BATcount(on) <= 1) {
    2478           0 :                                         on->tsorted = true;
    2479           0 :                                         on->trevsorted = true;
    2480             :                                 }
    2481             :                         }
    2482        5812 :                         if (groups) {
    2483        2967 :                                 gn = COLcopy(g, g->ttype, false, TRANSIENT);
    2484        2967 :                                 if (gn == NULL)
    2485           0 :                                         goto error;
    2486        2967 :                                 *groups = gn;
    2487             :                         }
    2488        5812 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT
    2489             :                                   ",o=" ALGOOPTBATFMT ",g=" ALGOBATFMT
    2490             :                                   ",reverse=%d,nilslast=%d,stable=%d"
    2491             :                                   ") = (" ALGOOPTBATFMT ","
    2492             :                                   ALGOOPTBATFMT "," ALGOOPTBATFMT
    2493             :                                   " -- key group (" LLFMT " usec)\n",
    2494             :                                   ALGOBATPAR(b), ALGOOPTBATPAR(o),
    2495             :                                   ALGOBATPAR(g), reverse, nilslast,
    2496             :                                   stable, ALGOOPTBATPAR(bn),
    2497             :                                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(on),
    2498             :                                   GDKusec() - t0);
    2499        5812 :                         return GDK_SUCCEED;
    2500             :                 }
    2501        6189 :                 assert(g->ttype == TYPE_oid);
    2502        6189 :                 grps = (oid *) Tloc(g, 0);
    2503        6189 :                 prev = grps[0];
    2504        6189 :                 if (BATmaterialize(bn) != GDK_SUCCEED)
    2505           0 :                         goto error;
    2506    36285655 :                 for (r = 0, p = 1, q = BATcount(g); p < q; p++) {
    2507    36279467 :                         if (grps[p] != prev) {
    2508             :                                 /* sub sort [r,p) */
    2509     7961790 :                                 if (do_sort(Tloc(bn, r),
    2510     3980879 :                                             ords ? ords + r : NULL,
    2511     3980911 :                                             bn->tvheap ? bn->tvheap->base : NULL,
    2512     3980911 :                                             p - r, Tsize(bn), ords ? sizeof(oid) : 0,
    2513     3980911 :                                             bn->ttype, reverse, nilslast, stable) != GDK_SUCCEED)
    2514           0 :                                         goto error;
    2515             :                                 r = p;
    2516     3980910 :                                 prev = grps[p];
    2517             :                         }
    2518             :                 }
    2519             :                 /* sub sort [r,q) */
    2520       12358 :                 if (do_sort(Tloc(bn, r),
    2521        6170 :                             ords ? ords + r : NULL,
    2522        6188 :                             bn->tvheap ? bn->tvheap->base : NULL,
    2523        6188 :                             p - r, Tsize(bn), ords ? sizeof(oid) : 0,
    2524        6188 :                             bn->ttype, reverse, nilslast, stable) != GDK_SUCCEED)
    2525           0 :                         goto error;
    2526             :                 /* if single group (r==0) the result is (rev)sorted,
    2527             :                  * otherwise (maybe) not */
    2528        6188 :                 bn->tsorted = r == 0 && !reverse && !nilslast;
    2529       12366 :                 bn->trevsorted = r == 0 && reverse && nilslast;
    2530             :         } else {
    2531             :                 Heap *m = NULL;
    2532             :                 /* only invest in creating an order index if the BAT
    2533             :                  * is persistent */
    2534        8117 :                 if (mkorderidx) {
    2535        5875 :                         assert(orderidxlock);
    2536        5875 :                         if ((m = createOIDXheap(pb, stable)) != NULL &&
    2537             :                             ords == NULL) {
    2538           6 :                                 ords = (oid *) m->base + ORDERIDXOFF;
    2539           6 :                                 if (o && o->ttype != TYPE_void)
    2540           0 :                                         memcpy(ords, Tloc(o, 0), BATcount(o) * sizeof(oid));
    2541           6 :                                 else if (o)
    2542           0 :                                         for (p = 0, q = BATcount(o); p < q; p++)
    2543           0 :                                                 ords[p] = p + o->tseqbase;
    2544             :                                 else
    2545        1161 :                                         for (p = 0, q = BATcount(b); p < q; p++)
    2546        1155 :                                                 ords[p] = p + b->hseqbase;
    2547             :                         }
    2548             :                 }
    2549        8119 :                 if ((reverse != nilslast ||
    2550       15783 :                      (reverse ? !bn->trevsorted : !bn->tsorted)) &&
    2551       15356 :                     (BATmaterialize(bn) != GDK_SUCCEED ||
    2552        7676 :                      do_sort(Tloc(bn, 0),
    2553             :                              ords,
    2554        7676 :                              bn->tvheap ? bn->tvheap->base : NULL,
    2555        7676 :                              BATcount(bn), Tsize(bn), ords ? sizeof(oid) : 0,
    2556        7676 :                              bn->ttype, reverse, nilslast, stable) != GDK_SUCCEED)) {
    2557           0 :                         if (m != NULL) {
    2558           0 :                                 HEAPfree(m, true);
    2559           0 :                                 GDKfree(m);
    2560             :                         }
    2561           0 :                         goto error;
    2562             :                 }
    2563        8119 :                 bn->tsorted = !reverse && !nilslast;
    2564        8119 :                 bn->trevsorted = reverse && nilslast;
    2565        8119 :                 if (m != NULL) {
    2566        5876 :                         assert(orderidxlock);
    2567        5876 :                         if (pb->torderidx == NULL) {
    2568        5876 :                                 pb->batDirtydesc = true;
    2569        5876 :                                 if (ords != (oid *) m->base + ORDERIDXOFF) {
    2570        5870 :                                         memcpy((oid *) m->base + ORDERIDXOFF,
    2571             :                                                ords,
    2572        5870 :                                                BATcount(pb) * sizeof(oid));
    2573             :                                 }
    2574        5876 :                                 ATOMIC_INIT(&m->refs, 1);
    2575        5876 :                                 pb->torderidx = m;
    2576        5876 :                                 persistOIDX(pb);
    2577             :                         } else {
    2578           0 :                                 HEAPfree(m, true);
    2579           0 :                                 GDKfree(m);
    2580             :                         }
    2581             :                 }
    2582             :         }
    2583       14307 :         if (orderidxlock) {
    2584        5876 :                 MT_lock_unset(&pb->batIdxLock);
    2585             :                 orderidxlock = false;
    2586             :         }
    2587       14307 :         bn->theap->dirty = true;
    2588       14307 :         bn->tnosorted = 0;
    2589       14307 :         bn->tnorevsorted = 0;
    2590       14307 :         bn->tnokey[0] = bn->tnokey[1] = 0;
    2591       14307 :         if (groups) {
    2592        8858 :                 if (BATgroup_internal(groups, NULL, NULL, bn, NULL, g, NULL, NULL, true) != GDK_SUCCEED)
    2593           0 :                         goto error;
    2594        8857 :                 if ((*groups)->tkey &&
    2595        1002 :                     (g == NULL || (g->tsorted && g->trevsorted))) {
    2596             :                         /* if new groups bat is key and the input
    2597             :                          * group bat has a single value (both sorted
    2598             :                          * and revsorted), we know the result bat is
    2599             :                          * key */
    2600        1799 :                         bn->tkey = true;
    2601             :                 }
    2602             :         }
    2603             : 
    2604       14306 :         if (sorted)
    2605       11277 :                 *sorted = bn;
    2606             :         else {
    2607        3029 :                 BBPunfix(bn->batCacheid);
    2608             :                 bn = NULL;
    2609             :         }
    2610             : 
    2611       14309 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",o=" ALGOOPTBATFMT
    2612             :                   ",g=" ALGOOPTBATFMT ",reverse=%d,nilslast=%d,"
    2613             :                   "stable=%d) = (" ALGOOPTBATFMT "," ALGOOPTBATFMT ","
    2614             :                   ALGOOPTBATFMT " -- %ssort (" LLFMT " usec)\n",
    2615             :                   ALGOBATPAR(b), ALGOOPTBATPAR(o), ALGOOPTBATPAR(g),
    2616             :                   reverse, nilslast, stable, ALGOOPTBATPAR(bn),
    2617             :                   ALGOOPTBATPAR(gn), ALGOOPTBATPAR(on),
    2618             :                   g ? "grouped " : "", GDKusec() - t0);
    2619             :         return GDK_SUCCEED;
    2620             : 
    2621           0 :   error:
    2622           0 :         if (orderidxlock)
    2623           0 :                 MT_lock_unset(&pb->batIdxLock);
    2624           0 :         if (oidxh)
    2625           0 :                 HEAPdecref(oidxh, false);
    2626           0 :         if (bn)
    2627           0 :                 BBPunfix(bn->batCacheid);
    2628           0 :         BBPreclaim(on);
    2629           0 :         if (sorted)
    2630           0 :                 *sorted = NULL;
    2631           0 :         if (order)
    2632           0 :                 *order = NULL;
    2633           0 :         if (groups)
    2634           0 :                 *groups = NULL;
    2635             :         return GDK_FAIL;
    2636             : }
    2637             : 
    2638             : /* return a new BAT of length n with seqbase hseq, and the constant v
    2639             :  * in the tail */
    2640             : BAT *
    2641     3039535 : BATconstant(oid hseq, int tailtype, const void *v, BUN n, role_t role)
    2642             : {
    2643             :         BAT *bn;
    2644             :         void *restrict p;
    2645             :         BUN i;
    2646             :         lng t0 = 0;
    2647             : 
    2648     3039535 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    2649     3039535 :         if (v == NULL)
    2650             :                 return NULL;
    2651     3039535 :         bn = COLnew(hseq, tailtype, n, role);
    2652     3037180 :         if (bn != NULL && n > 0) {
    2653       94875 :                 p = Tloc(bn, 0);
    2654       94875 :                 switch (ATOMstorage(tailtype)) {
    2655          56 :                 case TYPE_void:
    2656             :                         v = &oid_nil;
    2657          56 :                         BATtseqbase(bn, oid_nil);
    2658          56 :                         break;
    2659         254 :                 case TYPE_msk:
    2660         254 :                         if (*(msk*)v) {
    2661           0 :                                 memset(p, 0xFF, 4 * ((n + 31) / 32));
    2662           0 :                                 if (n & 31) {
    2663             :                                         uint32_t *m = p;
    2664           0 :                                         m[n / 32] &= (1U << (n % 32)) - 1;
    2665             :                                 }
    2666             :                         } else
    2667         254 :                                 memset(p, 0x00, 4 * ((n + 31) / 32));
    2668             :                         break;
    2669        7440 :                 case TYPE_bte:
    2670        7440 :                         memset(p, *(bte*)v, n);
    2671        7440 :                         break;
    2672             :                 case TYPE_sht:
    2673      295339 :                         for (i = 0; i < n; i++)
    2674      278134 :                                 ((sht *) p)[i] = *(sht *) v;
    2675             :                         break;
    2676             :                 case TYPE_int:
    2677             :                 case TYPE_flt:
    2678             :                         assert(sizeof(int) == sizeof(flt));
    2679   213718542 :                         for (i = 0; i < n; i++)
    2680   213713604 :                                 ((int *) p)[i] = *(int *) v;
    2681             :                         break;
    2682             :                 case TYPE_lng:
    2683             :                 case TYPE_dbl:
    2684             :                         assert(sizeof(lng) == sizeof(dbl));
    2685   191338244 :                         for (i = 0; i < n; i++)
    2686   191288027 :                                 ((lng *) p)[i] = *(lng *) v;
    2687             :                         break;
    2688             : #ifdef HAVE_HGE
    2689             :                 case TYPE_hge:
    2690    22227006 :                         for (i = 0; i < n; i++)
    2691    22225113 :                                 ((hge *) p)[i] = *(hge *) v;
    2692             :                         break;
    2693             : #endif
    2694             :                 case TYPE_uuid:
    2695      200011 :                         for (i = 0; i < n; i++)
    2696      200006 :                                 ((uuid *) p)[i] = *(uuid *) v;
    2697             :                         break;
    2698       12838 :                 case TYPE_str:
    2699             :                         /* insert the first value, then just copy the
    2700             :                          * offset lots of times */
    2701       12838 :                         if (tfastins_nocheck(bn, 0, v) != GDK_SUCCEED) {
    2702           0 :                                 BBPreclaim(bn);
    2703           0 :                                 return NULL;
    2704             :                         }
    2705             :                         char val[sizeof(var_t)];
    2706       12821 :                         memcpy(val, Tloc(bn, 0), bn->twidth);
    2707       12821 :                         if (bn->twidth == 1 && n > 1) {
    2708             :                                 /* single byte value: we have a
    2709             :                                  * function for that */
    2710        6064 :                                 memset(Tloc(bn, 1), val[0], n - 1);
    2711             :                         } else {
    2712        6757 :                                 char *p = Tloc(bn, 0);
    2713        6757 :                                 for (i = 1; i < n; i++) {
    2714           0 :                                         p += bn->twidth;
    2715           0 :                                         memcpy(p, val, bn->twidth);
    2716             :                                 }
    2717             :                         }
    2718             :                         break;
    2719             :                 default:
    2720         176 :                         for (i = 0; i < n; i++)
    2721         147 :                                 if (tfastins_nocheck(bn, i, v) != GDK_SUCCEED) {
    2722           0 :                                         BBPreclaim(bn);
    2723           0 :                                         return NULL;
    2724             :                                 }
    2725             :                         break;
    2726             :                 }
    2727       94858 :                 bn->theap->dirty = true;
    2728       94858 :                 bn->tnil = n >= 1 && ATOMnilptr(tailtype) && (*ATOMcompare(tailtype))(v, ATOMnilptr(tailtype)) == 0;
    2729       94809 :                 BATsetcount(bn, n);
    2730       94999 :                 bn->tsorted = bn->trevsorted = ATOMlinear(tailtype);
    2731       94999 :                 bn->tnonil = !bn->tnil;
    2732       94999 :                 bn->tkey = BATcount(bn) <= 1;
    2733             :         }
    2734     3037304 :         TRC_DEBUG(ALGO, "-> " ALGOOPTBATFMT " " LLFMT "usec\n",
    2735             :                   ALGOOPTBATPAR(bn), GDKusec() - t0);
    2736             :         return bn;
    2737             : }
    2738             : 
    2739             : /*
    2740             :  * BAT Aggregates
    2741             :  *
    2742             :  * We retain the size() and card() aggregate results in the column
    2743             :  * descriptor.  We would like to have such functionality in an
    2744             :  * extensible way for many aggregates, for DD (1) we do not want to
    2745             :  * change the binary BAT format on disk and (2) aggr and size are the
    2746             :  * most relevant aggregates.
    2747             :  *
    2748             :  * It is all hacked into the aggr[3] records; three adjacent integers
    2749             :  * that were left over in the column record. We refer to these as if
    2750             :  * it where an int aggr[3] array.  The below routines set and retrieve
    2751             :  * the aggregate values from the tail of the BAT, as many
    2752             :  * aggregate-manipulating BAT functions work on tail.
    2753             :  *
    2754             :  * The rules are as follows: aggr[0] contains the alignment ID of the
    2755             :  * column (if set i.e. nonzero).  Hence, if this value is nonzero and
    2756             :  * equal to b->talign, the precomputed aggregate values in
    2757             :  * aggr[GDK_AGGR_SIZE] and aggr[GDK_AGGR_CARD] hold. However, only one
    2758             :  * of them may be set at the time. This is encoded by the value
    2759             :  * int_nil, which cannot occur in these two aggregates.
    2760             :  *
    2761             :  * This was now extended to record the property whether we know there
    2762             :  * is a nil value present by mis-using the highest bits of both
    2763             :  * GDK_AGGR_SIZE and GDK_AGGR_CARD.
    2764             :  */
    2765             : 
    2766             : void
    2767    32902719 : PROPdestroy(BAT *b)
    2768             : {
    2769    32902719 :         PROPrec *p = b->tprops;
    2770             :         PROPrec *n;
    2771             : 
    2772    32902719 :         b->tprops = NULL;
    2773    34420338 :         while (p) {
    2774     1522752 :                 n = p->next;
    2775     1522752 :                 VALclear(&p->v);
    2776     1522788 :                 GDKfree(p);
    2777             :                 p = n;
    2778             :         }
    2779    32897586 : }
    2780             : 
    2781             : ValPtr
    2782   164094665 : BATgetprop_nolock(BAT *b, enum prop_t idx)
    2783             : {
    2784             :         PROPrec *p;
    2785             : 
    2786   165380326 :         p = b->tprops;
    2787   355567215 :         while (p && p->id != idx)
    2788   189039470 :                 p = p->next;
    2789   166527745 :         return p ? &p->v : NULL;
    2790             : }
    2791             : 
    2792             : void
    2793    31779323 : BATrmprop_nolock(BAT *b, enum prop_t idx)
    2794             : {
    2795    31779323 :         PROPrec *prop = b->tprops, *prev = NULL;
    2796             : 
    2797    81231446 :         while (prop) {
    2798    49465531 :                 if (prop->id == idx) {
    2799       13408 :                         if (prev)
    2800        6256 :                                 prev->next = prop->next;
    2801             :                         else
    2802        7152 :                                 b->tprops = prop->next;
    2803       13408 :                         VALclear(&prop->v);
    2804       13394 :                         GDKfree(prop);
    2805       13414 :                         return;
    2806             :                 }
    2807             :                 prev = prop;
    2808    49452123 :                 prop = prop->next;
    2809             :         }
    2810             : }
    2811             : 
    2812             : ValPtr
    2813   182408443 : BATsetprop_nolock(BAT *b, enum prop_t idx, int type, const void *v)
    2814             : {
    2815             :         PROPrec *p;
    2816             : 
    2817   182408443 :         p = b->tprops;
    2818   455485291 :         while (p && p->id != idx)
    2819   273076848 :                 p = p->next;
    2820   182408443 :         if (p == NULL) {
    2821     1492653 :                 if ((p = GDKmalloc(sizeof(PROPrec))) == NULL) {
    2822             :                         /* properties are hints, so if we can't create
    2823             :                          * one we ignore the error */
    2824           0 :                         GDKclrerr();
    2825           0 :                         return NULL;
    2826             :                 }
    2827     1526296 :                 p->id = idx;
    2828     1526296 :                 p->next = b->tprops;
    2829     1526296 :                 p->v.vtype = 0;
    2830     1526296 :                 b->tprops = p;
    2831             :         } else {
    2832   180915790 :                 VALclear(&p->v);
    2833             :         }
    2834   182515656 :         if (VALinit(&p->v, type, v) == NULL) {
    2835             :                 /* failed to initialize, so remove property */
    2836           0 :                 BATrmprop_nolock(b, idx);
    2837           0 :                 GDKclrerr();
    2838             :                 p = NULL;
    2839             :         }
    2840           0 :         b->batDirtydesc = true;
    2841   182266683 :         return p ? &p->v : NULL;
    2842             : }
    2843             : 
    2844             : ValPtr
    2845       31926 : BATgetprop_try(BAT *b, enum prop_t idx)
    2846             : {
    2847             :         ValPtr p = NULL;
    2848       31926 :         if (MT_lock_try(&b->theaplock)) {
    2849             :                 p = BATgetprop_nolock(b, idx);
    2850       31925 :                 MT_lock_unset(&b->theaplock);
    2851             :         }
    2852       31926 :         return p;
    2853             : }
    2854             : 
    2855             : ValPtr
    2856     1245286 : BATgetprop(BAT *b, enum prop_t idx)
    2857             : {
    2858             :         ValPtr p;
    2859             : 
    2860     1245286 :         MT_lock_set(&b->theaplock);
    2861             :         p = BATgetprop_nolock(b, idx);
    2862             :         if (p == NULL) {
    2863             :                 /* if looking for the min/max value, we may be able to
    2864             :                  * find it using the position; note we can't do this
    2865             :                  * when reading in the BBP since the BAT type may not be
    2866             :                  * known yet */
    2867     1223405 :                 switch (idx) {
    2868             :                 case GDK_MIN_VALUE:
    2869             :                         if ((p = BATgetprop_nolock(b, GDK_MIN_POS)) != NULL) {
    2870          82 :                                 BATiter bi = bat_iterator_nolock(b);
    2871          82 :                                 p = BATsetprop_nolock(b, GDK_MIN_VALUE, b->ttype, BUNtail(bi, p->val.oval));
    2872             :                         }
    2873             :                         break;
    2874             :                 case GDK_MAX_VALUE:
    2875             :                         if ((p = BATgetprop_nolock(b, GDK_MAX_POS)) != NULL) {
    2876          91 :                                 BATiter bi = bat_iterator_nolock(b);
    2877          91 :                                 p = BATsetprop_nolock(b, GDK_MAX_VALUE, b->ttype, BUNtail(bi, p->val.oval));
    2878             :                         }
    2879             :                         break;
    2880             :                 default:
    2881             :                         break;
    2882             :                 }
    2883       30331 :         }
    2884     1253736 :         MT_lock_unset(&b->theaplock);
    2885     1256925 :         return p;
    2886             : }
    2887             : 
    2888             : ValPtr
    2889      121808 : BATsetprop(BAT *b, enum prop_t idx, int type, const void *v)
    2890             : {
    2891             :         ValPtr p;
    2892      121808 :         MT_lock_set(&b->theaplock);
    2893      122638 :         p = BATsetprop_nolock(b, idx, type, v);
    2894      122095 :         MT_lock_unset(&b->theaplock);
    2895      122702 :         return p;
    2896             : }
    2897             : 
    2898             : void
    2899    15440876 : BATrmprop(BAT *b, enum prop_t idx)
    2900             : {
    2901    15440876 :         MT_lock_set(&b->theaplock);
    2902    15502790 :         BATrmprop_nolock(b, idx);
    2903    15491404 :         MT_lock_unset(&b->theaplock);
    2904    15499752 : }
    2905             : 
    2906             : 
    2907             : /*
    2908             :  * The BATcount_no_nil function counts all BUN in a BAT that have a
    2909             :  * non-nil tail value.
    2910             :  */
    2911             : BUN
    2912         625 : BATcount_no_nil(BAT *b, BAT *s)
    2913             : {
    2914             :         BUN cnt = 0;
    2915             :         BUN i, n;
    2916             :         const void *restrict p, *restrict nil;
    2917             :         const char *restrict base;
    2918             :         int t;
    2919             :         int (*cmp)(const void *, const void *);
    2920             :         struct canditer ci;
    2921             :         oid hseq;
    2922             : 
    2923         625 :         BATcheck(b, 0);
    2924             : 
    2925         625 :         hseq = b->hseqbase;
    2926         625 :         n = canditer_init(&ci, b, s);
    2927         625 :         if (b->tnonil)
    2928             :                 return n;
    2929         209 :         BATiter bi = bat_iterator(b);
    2930         209 :         p = bi.base;
    2931         209 :         t = ATOMbasetype(b->ttype);
    2932         209 :         switch (t) {
    2933           1 :         case TYPE_void:
    2934           1 :                 cnt = n * BATtdense(b);
    2935           1 :                 break;
    2936             :         case TYPE_msk:
    2937             :                 cnt = n;
    2938             :                 break;
    2939             :         case TYPE_bte:
    2940          38 :                 for (i = 0; i < n; i++)
    2941          19 :                         cnt += !is_bte_nil(((const bte *) p)[canditer_next(&ci) - hseq]);
    2942             :                 break;
    2943             :         case TYPE_sht:
    2944           2 :                 for (i = 0; i < n; i++)
    2945           1 :                         cnt += !is_sht_nil(((const sht *) p)[canditer_next(&ci) - hseq]);
    2946             :                 break;
    2947             :         case TYPE_int:
    2948    11702083 :                 for (i = 0; i < n; i++)
    2949    11701943 :                         cnt += !is_int_nil(((const int *) p)[canditer_next(&ci) - hseq]);
    2950             :                 break;
    2951             :         case TYPE_lng:
    2952          48 :                 for (i = 0; i < n; i++)
    2953          27 :                         cnt += !is_lng_nil(((const lng *) p)[canditer_next(&ci) - hseq]);
    2954             :                 break;
    2955             : #ifdef HAVE_HGE
    2956             :         case TYPE_hge:
    2957           0 :                 for (i = 0; i < n; i++)
    2958           0 :                         cnt += !is_hge_nil(((const hge *) p)[canditer_next(&ci) - hseq]);
    2959             :                 break;
    2960             : #endif
    2961             :         case TYPE_flt:
    2962           0 :                 for (i = 0; i < n; i++)
    2963           0 :                         cnt += !is_flt_nil(((const flt *) p)[canditer_next(&ci) - hseq]);
    2964             :                 break;
    2965             :         case TYPE_dbl:
    2966          34 :                 for (i = 0; i < n; i++)
    2967          18 :                         cnt += !is_dbl_nil(((const dbl *) p)[canditer_next(&ci) - hseq]);
    2968             :                 break;
    2969             :         case TYPE_uuid:
    2970           4 :                 for (i = 0; i < n; i++)
    2971           3 :                         cnt += !is_uuid_nil(((const uuid *) p)[canditer_next(&ci) - hseq]);
    2972             :                 break;
    2973           9 :         case TYPE_str:
    2974           9 :                 base = bi.vh->base;
    2975           9 :                 switch (bi.width) {
    2976             :                 case 1:
    2977          46 :                         for (i = 0; i < n; i++)
    2978          37 :                                 cnt += base[(var_t) ((const unsigned char *) p)[canditer_next(&ci) - hseq] + GDK_VAROFFSET] != '\200';
    2979             :                         break;
    2980             :                 case 2:
    2981           0 :                         for (i = 0; i < n; i++)
    2982           0 :                                 cnt += base[(var_t) ((const unsigned short *) p)[canditer_next(&ci) - hseq] + GDK_VAROFFSET] != '\200';
    2983             :                         break;
    2984             : #if SIZEOF_VAR_T != SIZEOF_INT
    2985             :                 case 4:
    2986           0 :                         for (i = 0; i < n; i++)
    2987           0 :                                 cnt += base[(var_t) ((const unsigned int *) p)[canditer_next(&ci) - hseq]] != '\200';
    2988             :                         break;
    2989             : #endif
    2990             :                 default:
    2991           0 :                         for (i = 0; i < n; i++)
    2992           0 :                                 cnt += base[((const var_t *) p)[canditer_next(&ci) - hseq]] != '\200';
    2993             :                         break;
    2994             :                 }
    2995             :                 break;
    2996           0 :         default:
    2997           0 :                 nil = ATOMnilptr(t);
    2998           0 :                 cmp = ATOMcompare(t);
    2999           0 :                 if (nil == NULL) {
    3000             :                         cnt = n;
    3001           0 :                 } else if (b->tvarsized) {
    3002           0 :                         base = b->tvheap->base;
    3003           0 :                         for (i = 0; i < n; i++)
    3004           0 :                                 cnt += (*cmp)(nil, base + ((const var_t *) p)[canditer_next(&ci) - hseq]) != 0;
    3005             :                 } else {
    3006           0 :                         for (i = 0, n += i; i < n; i++)
    3007           0 :                                 cnt += (*cmp)(BUNtloc(bi, canditer_next(&ci) - hseq), nil) != 0;
    3008             :                 }
    3009             :                 break;
    3010             :         }
    3011         208 :         if (cnt == BATcount(b)) {
    3012             :                 /* we learned something */
    3013         133 :                 b->tnonil = true;
    3014         133 :                 assert(!b->tnil);
    3015         133 :                 b->tnil = false;
    3016             :         }
    3017         208 :         bat_iterator_end(&bi);
    3018         209 :         return cnt;
    3019             : }

Generated by: LCOV version 1.14