LCOV - code coverage report
Current view: top level - monetdb5/modules/mal - mkey.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 145 281 51.6 %
Date: 2021-01-13 20:07:21 Functions: 5 8 62.5 %

          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             : - * @- The Problem
      11             : - * When creating a join, we want to make a unique key of the attributes on both
      12             : - * sides and then join these keys. Consider the following BATs.
      13             : - *
      14             : - * @verbatim
      15             : - * orders                  customer                link
      16             : - * ====================    =====================   ===========
      17             : - *         zipcode h_nr            zipcode hnr    oid     cid
      18             : - * o1      13      9       c1      11      10      o1      c5
      19             : - * o2      11      10      c2      11      11      o2      c1
      20             : - * o3      11      11      c3      12      2       o3      c2
      21             : - * o4      12      5       c4      12      1       o4      nil
      22             : - * o5      11      10      c5      13      9       o5      c1
      23             : - * o6      12      2       c6      14      7       o6      c3
      24             : - * o7      13      9                               o7      c5
      25             : - * o8      12      1                               o8      c4
      26             : - * o9      13      9                               o9      c5
      27             : - * @end verbatim
      28             : - *
      29             : - * The current approach is designed to take minimal memory, as our previous
      30             : - * solutions to the problem did not scale well. In case of singular keys,
      31             : - * the link is executed by a simple join. Before going into the join, we
      32             : - * make sure the end result size is not too large, which is done by looking
      33             : - * at relation sizes (if the other key is unique) or, if that is not possible,
      34             : - * by computing the exact join size.
      35             : - *
      36             : - * The join algorithm was also improved to do dynamic sampling to determine
      37             : - * with high accuracy the join size, so that we can alloc in one go a memory
      38             : - * region of sufficient size. This also reduces the ds\_link memory requirements.
      39             : - *
      40             : - * For compound keys, those that consist of multiple attributes, we now compute
      41             : - * a derived column that contains an integer hash value derived from all
      42             : - * key columns.
      43             : - * This is done by computing a hash value for each individual key column
      44             : - * and combining those by bitwise XOR and left-rotation. That is, for each
      45             : - * column,we rotate the working hash value by N bits and XOR the hash value
      46             : - * of the column over it. The working hash value is initialized with zero,
      47             : - * and after all columns are processed, this working value is used as output.
      48             : - * Computing the hash value for all columns in the key for one table is done
      49             : - * by the command hash(). Hence, we do hash on both sides, and join
      50             : - * that together with a simple join:
      51             : - *
      52             : - * @code{join(hash(keys), hash(keys.reverse);}
      53             : - *
      54             : - * One complication of this procedure are nil values:
      55             : - * @table
      56             : - * @itemize
      57             : - * @item
      58             : - * it may happen that the final hash-value (an int formed by a
      59             : - * random bit pattern) accidentally has the value of int(nil).
      60             : - * Notice that join never matches nil values.
      61             : - * Hence these accidental nils must be replaced by a begin value (currently: 0).
      62             : - * @item
      63             : - * in case any of the compound key values is nil, our nil semantics
      64             : - * require us that those tuples may never match on a join. Consequently,
      65             : - * during the hash() processing of all compound key columns for computing
      66             : - * the hash value, we also maintain a bit-bat that records which tuples had
      67             : - * a nil value. The bit-bat is initialized to false, and the results of the
      68             : - * nil-check on each column is OR-ed to it.
      69             : - * Afterwards, the hash-value of all tuples that have this nil-bit set to
      70             : - * TRUE are forced to int(nil), which will exclude them from matching.
      71             : - * @end itemize
      72             : - *
      73             : - * Joining on hash values produces a @emph{superset} of the join result:
      74             : - * it may happen that  two different key combinations hash on the same value,
      75             : - * which will make them match on the join (false hits). The final part
      76             : - * of the ds\_link therefore consists of filtering out the false hits.
      77             : - * This is done incrementally by joining back the join result to the original
      78             : - * columns, incrementally one by one for each pair of corresponding
      79             : - * columns. These values are compared with each other and we AND the
      80             : - * result of this comparison together for each pair of columns.
      81             : - * The bat containing these bits is initialized to all TRUE and serves as
      82             : - * final result after all column pairs have been compared.
      83             : - * The initial join result is finally filtered with this bit-bat.
      84             : - *
      85             : - * Joining back from the initial join-result to the original columns on
      86             : - * both sides takes quite a lot of memory. For this reason, the false
      87             : - * hit-filtering is done in slices (not all tuples at one time).
      88             : - * In this way the memory requirements of this phase are kept low.
      89             : - * In fact, the most memory demanding part of the join is the int-join
      90             : - * on hash number, which takes N*24 bytes (where N= |L| = |R|).
      91             : - * In comparison, the previous CTmultigroup/CTmultiderive approach
      92             : - * took N*48 bytes. Additionally, by making it possible to use merge-sort,
      93             : - * it avoids severe performance degradation (memory thrashing) as produced
      94             : - * by the old ds\_link when the inner join relation would be larger than memory.
      95             : - *
      96             : - * If ds\_link performance is still an issue, the sort-merge join used here
      97             : - * could be replaced by partitioned hash-join with radix-cluster/decluster.
      98             : - *
      99             : - * @+ Implementation
     100             : - */
     101             : 
     102             : /*
     103             :  * (c) Peter Boncz, Stefan Manegold, Niels Nes
     104             :  *
     105             :  * new functionality for the low-resource-consumption. It will
     106             :  * first one by one create a hash value out of the multiple attributes.
     107             :  * This hash value is computed by xoring and rotating individual hash
     108             :  * values together. We create a hash and rotate command to do this.
     109             :  */
     110             : 
     111             : #include "monetdb_config.h"
     112             : #include "mal.h"
     113             : #include "mal_interpreter.h"
     114             : #include "mal_exception.h"
     115             : 
     116             : #define MKEYHASH_bte(valp)      ((ulng) (lng) *(const bte*)(valp))
     117             : #define MKEYHASH_sht(valp)      ((ulng) (lng) *(const sht*)(valp))
     118             : #define MKEYHASH_int(valp)      ((ulng) (lng) *(const int*)(valp))
     119             : #define MKEYHASH_lng(valp)      ((ulng) (lng) *(const lng*)(valp))
     120             : #ifdef HAVE_HGE
     121             : #define MKEYHASH_hge(valp)      ((ulng) (*(const uhge *)(valp) >> 64) ^ \
     122             :                                                          (ulng) *(const uhge *)(valp))
     123             : #endif
     124             : 
     125             : static inline ulng
     126             : GDK_ROTATE(ulng x, int y, int z)
     127             : {
     128    63408400 :         return (x << y) | (x >> z);
     129             : }
     130             : 
     131             : /* TODO: nil handling. however; we do not want to lose time in bulk_rotate_xor_hash with that */
     132             : static str
     133           0 : MKEYrotate(lng *res, const lng *val, const int *n)
     134             : {
     135           0 :         *res = (lng) GDK_ROTATE((ulng) *val, *n, (sizeof(lng)*8) - *n);
     136           0 :         return MAL_SUCCEED;
     137             : }
     138             : 
     139             : static str
     140         987 : MKEYhash(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
     141             : {
     142             :         lng *res;
     143             :         ptr val;
     144         987 :         int tpe = getArgType(mb,p,1);
     145             : 
     146             :         (void) cntxt;
     147         987 :         res= getArgReference_lng(stk,p,0);
     148         987 :         val= getArgReference(stk,p,1);
     149         987 :         switch (ATOMstorage(tpe)) {
     150           1 :         case TYPE_void:
     151           1 :                 *res = lng_nil; /* It can be called from SQL */
     152           1 :                 break;
     153           9 :         case TYPE_bat:
     154             :         case TYPE_ptr:
     155             :                 // illegal types, avoid falling into the default case.
     156             :                 assert(0);
     157             :         case TYPE_bte:
     158           9 :                 *res = (lng) MKEYHASH_bte(val);
     159           9 :                 break;
     160           0 :         case TYPE_sht:
     161           0 :                 *res = (lng) MKEYHASH_sht(val);
     162           0 :                 break;
     163         901 :         case TYPE_int:
     164             :         case TYPE_flt:
     165         901 :                 *res = (lng) MKEYHASH_int(val);
     166         901 :                 break;
     167           7 :         case TYPE_lng:
     168             :         case TYPE_dbl:
     169           7 :                 *res = (lng) MKEYHASH_lng(val);
     170           7 :                 break;
     171             : #ifdef HAVE_HGE
     172           0 :         case TYPE_hge:
     173           0 :                 *res = (lng) MKEYHASH_hge(val);
     174           0 :                 break;
     175             : #endif
     176          69 :         default:
     177          69 :                 if (ATOMextern(tpe))
     178          69 :                         *res = (lng) ATOMhash(tpe, *(ptr*)val);
     179             :                 else
     180           0 :                         *res = (lng) ATOMhash(tpe, val);
     181             :                 break;
     182             :         }
     183         987 :         return MAL_SUCCEED;
     184             : }
     185             : 
     186             : static str
     187       10266 : MKEYbathash(bat *res, const bat *bid)
     188             : {
     189             :         BAT *b, *dst;
     190             :         ulng *restrict r;
     191             :         BUN n;
     192             : 
     193       10266 :         if ((b = BATdescriptor(*bid)) == NULL)
     194           0 :                 throw(SQL, "mkey.bathash", SQLSTATE(HY002) RUNTIME_OBJECT_MISSING);
     195             : 
     196       10266 :         n = BATcount(b);
     197       10266 :         dst = COLnew(b->hseqbase, TYPE_lng, n, TRANSIENT);
     198       10266 :         if (dst == NULL) {
     199           0 :                 BBPunfix(b->batCacheid);
     200           0 :                 throw(SQL, "mkey.bathash", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     201             :         }
     202       10266 :         BATsetcount(dst, n);
     203             : 
     204       10266 :         r = (ulng *) Tloc(dst, 0);
     205             : 
     206       10266 :         switch (ATOMstorage(b->ttype)) {
     207           0 :         case TYPE_void: {
     208           0 :                 oid o = b->tseqbase;
     209           0 :                 if (is_oid_nil(o))
     210           0 :                         for (BUN i = 0; i < n; i++)
     211           0 :                                 r[i] = (ulng) lng_nil;
     212             :                 else
     213           0 :                         for (BUN i = 0; i < n; i++)
     214           0 :                                 r[i] = o + i;
     215             :                 break;
     216             :         }
     217          24 :         case TYPE_bte: {
     218          24 :                 const bte *restrict v = (const bte *) Tloc(b, 0);
     219         117 :                 for (BUN i = 0; i < n; i++)
     220          93 :                         r[i] = MKEYHASH_bte(v + i);
     221             :                 break;
     222             :         }
     223           7 :         case TYPE_sht: {
     224           7 :                 const sht *restrict v = (const sht *) Tloc(b, 0);
     225       31494 :                 for (BUN i = 0; i < n; i++)
     226       31487 :                         r[i] = MKEYHASH_sht(v + i);
     227             :                 break;
     228             :         }
     229        9804 :         case TYPE_int:
     230             :         case TYPE_flt: {
     231        9804 :                 const int *restrict v = (const int *) Tloc(b, 0);
     232    39409400 :                 for (BUN i = 0; i < n; i++)
     233    39399600 :                         r[i] = MKEYHASH_int(v + i);
     234             :                 break;
     235             :         }
     236         165 :         case TYPE_lng:
     237             :         case TYPE_dbl: {
     238         165 :                 const lng *restrict v = (const lng *) Tloc(b, 0);
     239       16933 :                 for (BUN i = 0; i < n; i++)
     240       16768 :                         r[i] = MKEYHASH_lng(v + i);
     241             :                 break;
     242             :         }
     243             : #ifdef HAVE_HGE
     244          38 :         case TYPE_hge: {
     245          38 :                 const hge *restrict v = (const hge *) Tloc(b, 0);
     246         221 :                 for (BUN i = 0; i < n; i++)
     247         183 :                         r[i] = MKEYHASH_hge(v + i);
     248             :                 break;
     249             :         }
     250             : #endif
     251         228 :         default: {
     252         228 :                 BATiter bi = bat_iterator(b);
     253         228 :                 BUN (*hash)(const void *) = BATatoms[b->ttype].atomHash;
     254         228 :                 int (*cmp)(const void *, const void *) = ATOMcompare(b->ttype);
     255         228 :                 const void *nil = ATOMnilptr(b->ttype);
     256             : 
     257      462300 :                 for (BUN i = 0; i < n; i++) {
     258      462072 :                         const void *restrict v = BUNtail(bi, i);
     259      462072 :                         if ((*cmp)(v, nil) == 0)
     260        8033 :                                 r[i] = (ulng) lng_nil;
     261             :                         else
     262      454623 :                                 r[i] = (ulng) (*hash)(v);
     263             :                 }
     264             :                 break;
     265             :         }
     266             :         }
     267             : 
     268       10266 :         if (dst->batCount <= 1) {
     269        4134 :                 BATkey(dst, true);
     270        4134 :                 dst->tsorted = dst->trevsorted = true;
     271             :         } else {
     272        6132 :                 BATkey(dst, false);
     273        6132 :                 dst->tsorted = dst->trevsorted = false;
     274             :         }
     275       10266 :         dst->tnonil = false;
     276       10266 :         dst->tnil = false;
     277             : 
     278       10266 :         BBPkeepref(*res = dst->batCacheid);
     279       10266 :         BBPunfix(b->batCacheid);
     280       10266 :         return MAL_SUCCEED;
     281             : }
     282             : 
     283             : static str
     284        1744 : MKEYrotate_xor_hash(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
     285             : {
     286        1744 :         lng *dst = getArgReference_lng(stk, p, 0);
     287        1744 :         ulng h = (ulng) *getArgReference_lng(stk, p, 1);
     288        1744 :         int lbit = *getArgReference_int(stk, p, 2);
     289             :         int rbit = (int) sizeof(lng) * 8 - lbit;
     290        1744 :         int tpe = getArgType(mb, p, 3);
     291        1744 :         ptr *pval = getArgReference(stk, p, 3);
     292             :         ulng val;
     293             : 
     294             :         (void) cntxt;
     295        1744 :         switch (ATOMstorage(tpe)) {
     296           6 :         case TYPE_bte:
     297           6 :                 val = MKEYHASH_bte(pval);
     298           6 :                 break;
     299           1 :         case TYPE_sht:
     300           1 :                 val = MKEYHASH_sht(pval);
     301           1 :                 break;
     302        1483 :         case TYPE_int:
     303             :         case TYPE_flt:
     304        1483 :                 val = MKEYHASH_int(pval);
     305        1483 :                 break;
     306          42 :         case TYPE_lng:
     307             :         case TYPE_dbl:
     308          42 :                 val = MKEYHASH_lng(pval);
     309          42 :                 break;
     310             : #ifdef HAVE_HGE
     311           0 :         case TYPE_hge:
     312           0 :                 val = MKEYHASH_hge(pval);
     313           0 :                 break;
     314             : #endif
     315         212 :         default:
     316         212 :                 if (ATOMextern(tpe))
     317         212 :                         val = ATOMhash(tpe, *(ptr*)pval);
     318             :                 else
     319           0 :                         val = ATOMhash(tpe, pval);
     320             :                 break;
     321             :         }
     322        1744 :         *dst = (lng) (GDK_ROTATE(h, lbit, rbit) ^ val);
     323        1744 :         return MAL_SUCCEED;
     324             : }
     325             : 
     326             : static str
     327       11843 : MKEYbulk_rotate_xor_hash(bat *res, const bat *hid, const int *nbits, const bat *bid)
     328             : {
     329             :         BAT *hb, *b, *bn;
     330       11843 :         int lbit = *nbits;
     331             :         int rbit = (int) sizeof(lng) * 8 - lbit;
     332             :         ulng *restrict r;
     333             :         const ulng *restrict h;
     334             :         BUN n;
     335             : 
     336       11843 :         if ((hb = BATdescriptor(*hid)) == NULL)
     337           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY002) RUNTIME_OBJECT_MISSING);
     338             : 
     339       11843 :         if ((b = BATdescriptor(*bid)) == NULL) {
     340           0 :                 BBPunfix(hb->batCacheid);
     341           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY002) RUNTIME_OBJECT_MISSING);
     342             :         }
     343             : 
     344       11843 :         if (!ALIGNsynced(hb, b) && (BATcount(b) || BATcount(hb))) {
     345           0 :                 BBPunfix(hb->batCacheid);
     346           0 :                 BBPunfix(b->batCacheid);
     347           0 :                 throw(MAL, "mkey.rotate_xor_hash",
     348             :                           OPERATION_FAILED ": input bats are not aligned");
     349             :         }
     350             : 
     351       11843 :         n = BATcount(b);
     352             : 
     353       11843 :         bn = COLnew(b->hseqbase, TYPE_lng, n, TRANSIENT);
     354       11843 :         if (bn == NULL) {
     355           0 :                 BBPunfix(hb->batCacheid);
     356           0 :                 BBPunfix(b->batCacheid);
     357           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     358             :         }
     359       11843 :         BATsetcount(bn, n);
     360             : 
     361       11843 :         r = (ulng *) Tloc(bn, 0);
     362       11843 :         h = (const ulng *) Tloc(hb, 0);
     363             : 
     364       11843 :         switch (ATOMstorage(b->ttype)) {
     365         106 :         case TYPE_bte: {
     366         106 :                 const bte *restrict v = (const bte *) Tloc(b, 0);
     367       23437 :                 for (BUN i = 0; i < n; i++) {
     368       23331 :                         r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ MKEYHASH_bte(v + i);
     369             :                 }
     370             :                 break;
     371             :         }
     372         424 :         case TYPE_sht: {
     373         424 :                 const sht *restrict v = (const sht *) Tloc(b, 0);
     374       57171 :                 for (BUN i = 0; i < n; i++) {
     375       56747 :                         r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ MKEYHASH_sht(v + i);
     376             :                 }
     377             :                 break;
     378             :         }
     379        7480 :         case TYPE_int:
     380             :         case TYPE_flt: {
     381        7480 :                 const int *restrict v = (const int *) Tloc(b, 0);
     382    61780400 :                 for (BUN i = 0; i < n; i++) {
     383    61772900 :                         r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ MKEYHASH_int(v + i);
     384             :                 }
     385             :                 break;
     386             :         }
     387         610 :         case TYPE_lng:
     388             :         case TYPE_dbl: {
     389         610 :                 const lng *restrict v = (const lng *) Tloc(b, 0);
     390      360959 :                 for (BUN i = 0; i < n; i++) {
     391      360349 :                         r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ MKEYHASH_lng(v + i);
     392             :                 }
     393             :                 break;
     394             :         }
     395             : #ifdef HAVE_HGE
     396          28 :         case TYPE_hge: {
     397          28 :                 const hge *restrict v = (const hge *) Tloc(b, 0);
     398         198 :                 for (BUN i = 0; i < n; i++) {
     399         170 :                         r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ MKEYHASH_hge(v + i);
     400             :                 }
     401             :                 break;
     402             :         }
     403             : #endif
     404        3149 :         case TYPE_str:
     405        3149 :                 if (b->tvheap->hashash) {
     406             :                         BATiter bi = bat_iterator(b);
     407           0 :                         for (BUN i = 0; i < n; i++) {
     408           0 :                                 const void *restrict s = BUNtvar(bi, i);
     409           0 :                                 r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ (ulng) ((const BUN *) s)[-1];
     410             :                         }
     411             :                         break;
     412             :                 }
     413             :                 /* fall through */
     414             :         default: {
     415        3195 :                 BATiter bi = bat_iterator(b);
     416        3195 :                 BUN (*hash)(const void *) = BATatoms[b->ttype].atomHash;
     417             : 
     418     1196360 :                 for (BUN i = 0; i < n; i++)
     419     1193250 :                         r[i] = GDK_ROTATE(h[i], lbit, rbit) ^ (ulng) (*hash)(BUNtail(bi, i));
     420             :                 break;
     421             :         }
     422             :         }
     423       11838 :         if (bn->batCount <= 1) {
     424        4513 :                 BATkey(bn, true);
     425        4513 :                 bn->tsorted = bn->trevsorted = true;
     426             :         } else {
     427        7325 :                 BATkey(bn, false);
     428        7326 :                 bn->tsorted = bn->trevsorted = false;
     429             :         }
     430       11839 :         bn->tnonil = false;
     431       11839 :         bn->tnil = false;
     432             : 
     433       11839 :         BBPkeepref(*res = bn->batCacheid);
     434       11843 :         BBPunfix(b->batCacheid);
     435       11840 :         BBPunfix(hb->batCacheid);
     436       11842 :         return MAL_SUCCEED;
     437             : }
     438             : 
     439             : static str
     440           0 : MKEYbulkconst_rotate_xor_hash(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
     441             : {
     442           0 :         bat *res = getArgReference_bat(stk, p, 0);
     443           0 :         bat *hid = getArgReference_bat(stk, p, 1);
     444           0 :         int lbit = *getArgReference_int(stk, p, 2);
     445           0 :         int tpe = getArgType(mb, p, 3);
     446           0 :         ptr *pval = getArgReference(stk, p, 3);
     447             :         BAT *hb, *bn;
     448             :         int rbit = (int) sizeof(lng) * 8 - lbit;
     449             :         ulng *r;
     450             :         const ulng *h;
     451             :         ulng val;
     452             :         BUN n;
     453             : 
     454             :         (void) cntxt;
     455             : 
     456           0 :         if ((hb = BATdescriptor(*hid)) == NULL)
     457           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY002) RUNTIME_OBJECT_MISSING);
     458             : 
     459           0 :         n = BATcount(hb);
     460             : 
     461           0 :         bn = COLnew(hb->hseqbase, TYPE_lng, n, TRANSIENT);
     462           0 :         if (bn == NULL) {
     463           0 :                 BBPunfix(hb->batCacheid);
     464           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     465             :         }
     466           0 :         BATsetcount(bn, n);
     467             : 
     468           0 :         switch (ATOMstorage(tpe)) {
     469           0 :         case TYPE_bte:
     470           0 :                 val = MKEYHASH_bte(pval);
     471           0 :                 break;
     472           0 :         case TYPE_sht:
     473           0 :                 val = MKEYHASH_sht(pval);
     474           0 :                 break;
     475           0 :         case TYPE_int:
     476             :         case TYPE_flt:
     477           0 :                 val = MKEYHASH_int(pval);
     478           0 :                 break;
     479           0 :         case TYPE_lng:
     480             :         case TYPE_dbl:
     481           0 :                 val = MKEYHASH_lng(pval);
     482           0 :                 break;
     483             : #ifdef HAVE_HGE
     484           0 :         case TYPE_hge:
     485           0 :                 val = MKEYHASH_hge(pval);
     486           0 :                 break;
     487             : #endif
     488           0 :         default:
     489           0 :                 if (ATOMextern(tpe))
     490           0 :                         val = (ulng) ATOMhash(tpe, *(ptr*)pval);
     491             :                 else
     492           0 :                         val = (ulng) ATOMhash(tpe, pval);
     493             :                 break;
     494             :         }
     495             : 
     496           0 :         r = (ulng *) Tloc(bn, 0);
     497           0 :         h = (const ulng *) Tloc(hb, 0);
     498             : 
     499           0 :         while (n-- > 0) {
     500           0 :                         *r++ = GDK_ROTATE(*h, lbit, rbit) ^ val;
     501           0 :                         h++;
     502             :         }
     503             : 
     504           0 :         if (bn->batCount <= 1) {
     505           0 :                 BATkey(bn, true);
     506           0 :                 bn->tsorted = bn->trevsorted = true;
     507             :         } else {
     508           0 :                 BATkey(bn, false);
     509           0 :                 bn->tsorted = bn->trevsorted = false;
     510             :         }
     511           0 :         bn->tnonil = false;
     512           0 :         bn->tnil = false;
     513             : 
     514           0 :         BBPkeepref(*res = bn->batCacheid);
     515           0 :         BBPunfix(hb->batCacheid);
     516           0 :         return MAL_SUCCEED;
     517             : }
     518             : 
     519             : static str
     520           0 : MKEYconstbulk_rotate_xor_hash(bat *res, const lng *h, const int *nbits, const bat *bid)
     521             : {
     522             :         BAT *b, *bn;
     523           0 :         int lbit = *nbits;
     524             :         int rbit = (int) sizeof(lng) * 8 - lbit;
     525             :         ulng *restrict r;
     526             :         BUN n;
     527             : 
     528           0 :         if ((b = BATdescriptor(*bid)) == NULL)
     529           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY002) RUNTIME_OBJECT_MISSING);
     530             : 
     531           0 :         n = BATcount(b);
     532             : 
     533           0 :         bn = COLnew(b->hseqbase, TYPE_lng, n, TRANSIENT);
     534           0 :         if (bn == NULL) {
     535           0 :                 BBPunfix(b->batCacheid);
     536           0 :                 throw(MAL, "mkey.rotate_xor_hash", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     537             :         }
     538           0 :         BATsetcount(bn, n);
     539             : 
     540           0 :         r = (ulng *) Tloc(bn, 0);
     541             : 
     542           0 :         switch (ATOMstorage(b->ttype)) {
     543           0 :         case TYPE_bte: {
     544           0 :                 const bte *restrict v = (const bte *) Tloc(b, 0);
     545           0 :                 for (BUN i = 0; i < n; i++)
     546           0 :                         r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ MKEYHASH_bte(v + i);
     547             :                 break;
     548             :         }
     549           0 :         case TYPE_sht: {
     550           0 :                 const sht *restrict v = (const sht *) Tloc(b, 0);
     551           0 :                 for (BUN i = 0; i < n; i++)
     552           0 :                         r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ MKEYHASH_sht(v + i);
     553             :                 break;
     554             :         }
     555           0 :         case TYPE_int:
     556             :         case TYPE_flt: {
     557           0 :                 const int *restrict v = (const int *) Tloc(b, 0);
     558           0 :                 for (BUN i = 0; i < n; i++)
     559           0 :                         r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ MKEYHASH_int(v + i);
     560             :                 break;
     561             :         }
     562           0 :         case TYPE_lng:
     563             :         case TYPE_dbl: {
     564           0 :                 const lng *restrict v = (const lng *) Tloc(b, 0);
     565           0 :                 for (BUN i = 0; i < n; i++)
     566           0 :                         r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ MKEYHASH_lng(v + i);
     567             :                 break;
     568             :         }
     569             : #ifdef HAVE_HGE
     570           0 :         case TYPE_hge: {
     571           0 :                 const hge *restrict v = (const hge *) Tloc(b, 0);
     572           0 :                 for (BUN i = 0; i < n; i++)
     573           0 :                         r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ MKEYHASH_hge(v + i);
     574             :                 break;
     575             :         }
     576             : #endif
     577           0 :         case TYPE_str:
     578           0 :                 if (b->tvheap->hashash) {
     579             :                         BATiter bi = bat_iterator(b);
     580           0 :                         for (BUN i = 0; i < n; i++) {
     581           0 :                                 const char *restrict s = BUNtvar(bi, i);
     582           0 :                                 r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ (ulng) ((const BUN *) s)[-1];
     583             :                         }
     584             :                         break;
     585             :                 }
     586             :                 /* fall through */
     587             :         default: {
     588           0 :                 BATiter bi = bat_iterator(b);
     589           0 :                 BUN (*hash)(const void *) = BATatoms[b->ttype].atomHash;
     590             : 
     591           0 :                 for (BUN i = 0; i < n; i++)
     592           0 :                         r[i] = GDK_ROTATE((ulng) *h, lbit, rbit) ^ (ulng) (*hash)(BUNtail(bi, i));
     593             :                 break;
     594             :         }
     595             :         }
     596           0 :         if (bn->batCount <= 1) {
     597           0 :                 BATkey(bn, true);
     598           0 :                 bn->tsorted = bn->trevsorted = true;
     599             :         } else {
     600           0 :                 BATkey(bn, false);
     601           0 :                 bn->tsorted = bn->trevsorted = false;
     602             :         }
     603           0 :         bn->tnonil = false;
     604           0 :         bn->tnil = false;
     605             : 
     606           0 :         BBPkeepref(*res = bn->batCacheid);
     607           0 :         BBPunfix(b->batCacheid);
     608           0 :         return MAL_SUCCEED;
     609             : }
     610             : 
     611             : #include "mel.h"
     612             : mel_func mkey_init_funcs[] = {
     613             :  command("mkey", "rotate", MKEYrotate, false, "left-rotate an int by nbits", args(1,3, arg("",lng),arg("v",lng),arg("nbits",int))),
     614             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),argany("v",0))),
     615             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",bit))),
     616             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",bte))),
     617             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",sht))),
     618             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",int))),
     619             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",flt))),
     620             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",dbl))),
     621             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",lng))),
     622             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",str))),
     623             :  pattern("mkey", "bulk_rotate_xor_hash", MKEYrotate_xor_hash, false, "post: [:xor=]([:rotate=](h, nbits), [hash](b))", args(1,4, arg("",lng),arg("h",lng),arg("nbits",int),argany("v",0))),
     624             :  command("mkey", "bulk_rotate_xor_hash", MKEYconstbulk_rotate_xor_hash, false, "pre:  h and b should be synced on head\npost: [:xor=]([:rotate=](h, nbits), [hash](b))", args(1,4, batarg("",lng),arg("h",lng),arg("nbits",int),batargany("b",1))),
     625             :  pattern("mkey", "bulk_rotate_xor_hash", MKEYbulkconst_rotate_xor_hash, false, "pre:  h and b should be synced on head\npost: [:xor=]([:rotate=](h, nbits), [hash](b))", args(1,4, batarg("",lng),batarg("h",lng),arg("nbits",int),argany("v",0))),
     626             :  command("mkey", "bulk_rotate_xor_hash", MKEYbulk_rotate_xor_hash, false, "pre:  h and b should be synced on head\npost: [:xor=]([:rotate=](h, nbits), [hash](b))", args(1,4, batarg("",lng),batarg("h",lng),arg("nbits",int),batargany("b",1))),
     627             :  command("batmkey", "hash", MKEYbathash, false, "calculate a hash value", args(1,2, batarg("",lng),batargany("b",1))),
     628             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",bte))),
     629             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",bte))),
     630             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",sht))),
     631             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",sht))),
     632             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",int))),
     633             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",int))),
     634             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",lng))),
     635             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",lng))),
     636             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",oid))),
     637             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",oid))),
     638             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",lng))),
     639             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",lng))),
     640             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",flt))),
     641             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",flt))),
     642             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",dbl))),
     643             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",dbl))),
     644             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),argany("v",0))),
     645             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batargany("b",1))),
     646             :  pattern("calc", "rotate_xor_hash", MKEYrotate_xor_hash, false, "", args(1,4, arg("",lng),arg("h",lng),arg("nbits",int),argany("v",1))),
     647             :  command("batcalc", "rotate_xor_hash", MKEYbulk_rotate_xor_hash, false, "", args(1,4, batarg("",int),batarg("h",lng),arg("nbits",int),batargany("b",1))),
     648             : #ifdef HAVE_HGE
     649             :  pattern("mkey", "hash", MKEYhash, false, "calculate a hash value", args(1,2, arg("",lng),arg("v",hge))),
     650             :  pattern("calc", "hash", MKEYhash, false, "", args(1,2, arg("",lng),arg("v",hge))),
     651             :  command("batcalc", "hash", MKEYbathash, false, "", args(1,2, batarg("",lng),batarg("b",hge))),
     652             : #endif
     653             :  { .imp=NULL }
     654             : };
     655             : #include "mal_import.h"
     656             : #ifdef _MSC_VER
     657             : #undef read
     658             : #pragma section(".CRT$XCU",read)
     659             : #endif
     660         255 : LIB_STARTUP_FUNC(init_mkey_mal)
     661         255 : { mal_module("mkey", NULL, mkey_init_funcs); }

Generated by: LCOV version 1.14