LCOV - code coverage report
Current view: top level - gdk - gdk_hash.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 532 693 76.8 %
Date: 2021-10-13 02:24:04 Functions: 21 26 80.8 %

          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             :  * - Hash Table Creation
      11             :  * The hash indexing scheme for BATs reserves a block of memory to
      12             :  * maintain the hash table and a collision list. A one-to-one mapping
      13             :  * exists between the BAT and the collision list using the BUN
      14             :  * index. NOTE: we alloc the link list as a parallel array to the BUN
      15             :  * array; hence the hash link array has the same size as
      16             :  * BATcapacity(b) (not BATcount(b)). This allows us in the BUN insert
      17             :  * and delete to assume that there is hash space if there is BUN
      18             :  * space.
      19             :  *
      20             :  * The hash mask size is a power of two, so we can do bitwise AND on
      21             :  * the hash (integer) number to quickly find the head of the bucket
      22             :  * chain.  Clearly, the hash mask size is a crucial parameter. If we
      23             :  * know that the column is unique (tkey), we use direct hashing (mask
      24             :  * size ~= BATcount). Otherwise we dynamically determine the mask size
      25             :  * by starting out with mask size = BATcount/64 (just 1.5% of memory
      26             :  * storage overhead). Then we start building the hash table on the
      27             :  * first 25% of the BAT. As we aim for max-collisions list length of
      28             :  * 4, the list on 25% should not exceed length 1. So, if a small
      29             :  * number of collisssions occurs (mask/2) then we abandon the attempt
      30             :  * and restart with a mask that is 4 times larger. This converges
      31             :  * after three cycles to direct hashing.
      32             :  */
      33             : 
      34             : #include "monetdb_config.h"
      35             : #include "gdk.h"
      36             : #include "gdk_private.h"
      37             : 
      38             : static inline uint8_t __attribute__((__const__))
      39             : HASHwidth(BUN hashsize)
      40             : {
      41             :         (void) hashsize;
      42             : #ifdef BUN2
      43      245189 :         if (hashsize <= (BUN) BUN2_NONE)
      44             :                 return BUN2;
      45             : #endif
      46             : #ifdef BUN8
      47        1474 :         if (hashsize > (BUN) BUN4_NONE)
      48           0 :                 return BUN8;
      49             : #endif
      50             :         return BUN4;
      51             : }
      52             : 
      53             : static inline BUN __attribute__((__const__))
      54      105240 : hashmask(BUN m)
      55             : {
      56      105240 :         m |= m >> 1;
      57      105240 :         m |= m >> 2;
      58      105240 :         m |= m >> 4;
      59      105240 :         m |= m >> 8;
      60      105240 :         m |= m >> 16;
      61             : #if SIZEOF_BUN == 8
      62      105240 :         m |= m >> 32;
      63             : #endif
      64      105240 :         return m;
      65             : }
      66             : 
      67             : BUN
      68      240959 : HASHmask(BUN cnt)
      69             : {
      70             :         BUN m = cnt;
      71             : 
      72             : #if 0
      73             :         /* find largest power of 2 smaller than or equal to cnt */
      74             :         m = hashmask(m);
      75             :         m -= m >> 1;
      76             : 
      77             :         /* if cnt is more than 1/3 into the gap between m and 2*m,
      78             :            double m */
      79             :         if (m + m - cnt < 2 * (cnt - m))
      80             :                 m += m;
      81             : #else
      82      345082 :         m = m * 8 / 7;
      83             : #endif
      84      251643 :         if (m < BATTINY)
      85             :                 m = BATTINY;
      86      240959 :         return m;
      87             : }
      88             : 
      89             : static inline void
      90      361053 : HASHclear(Hash *h)
      91             : {
      92             :         /* since BUN2_NONE, BUN4_NONE, BUN8_NONE
      93             :          * are all equal to ~0, i.e., have all bits set,
      94             :          * we can use a simple memset() to clear the Hash,
      95             :          * rather than iteratively assigning individual
      96             :          * BUNi_NONE values in a for-loop
      97             :          */
      98      361053 :         memset(h->Bckt, 0xFF, h->nbucket * h->width);
      99      361053 : }
     100             : 
     101             : #define HASH_VERSION            4
     102             : /* this is only for the change of hash function of the UUID type; if
     103             :  * HASH_VERSION is increased again from 4, the code associated with
     104             :  * HASH_VERSION_NOUUID must be deleted */
     105             : #define HASH_VERSION_NOUUID     3
     106             : #define HASH_HEADER_SIZE        7       /* nr of size_t fields in header */
     107             : 
     108             : void
     109       99703 : doHASHdestroy(BAT *b, Hash *hs)
     110             : {
     111       99703 :         if (hs == (Hash *) 1) {
     112         134 :                 GDKunlink(BBPselectfarm(b->batRole, b->ttype, hashheap),
     113             :                           BATDIR,
     114         134 :                           BBP_physical(b->batCacheid),
     115             :                           "thashl");
     116         134 :                 GDKunlink(BBPselectfarm(b->batRole, b->ttype, hashheap),
     117             :                           BATDIR,
     118         134 :                           BBP_physical(b->batCacheid),
     119             :                           "thashb");
     120       99569 :         } else if (hs) {
     121       99569 :                 bat p = VIEWtparent(b);
     122             :                 BAT *hp = NULL;
     123             : 
     124       87485 :                 if (p)
     125       87485 :                         hp = BBP_cache(p);
     126             : 
     127       99569 :                 if (!hp || hs != hp->thash) {
     128       99569 :                         TRC_DEBUG(ACCELERATOR, ALGOBATFMT ": removing%s hash\n", ALGOBATPAR(b), *(size_t *) hs->heapbckt.base & (1 << 24) ? " persisted" : "");
     129       99569 :                         HEAPfree(&hs->heapbckt, true);
     130       99569 :                         HEAPfree(&hs->heaplink, true);
     131       99569 :                         GDKfree(hs);
     132             :                 }
     133             :         }
     134       99703 : }
     135             : 
     136             : gdk_return
     137      361051 : HASHnew(Hash *h, int tpe, BUN size, BUN mask, BUN count, bool bcktonly)
     138             : {
     139      361051 :         if (h->width == 0)
     140      245189 :                 h->width = HASHwidth(size);
     141             : 
     142      361051 :         if (!bcktonly) {
     143      245191 :                 if (HEAPalloc(&h->heaplink, size, h->width, 0) != GDK_SUCCEED)
     144             :                         return GDK_FAIL;
     145      245202 :                 h->heaplink.free = size * h->width;
     146      245202 :                 h->Link = h->heaplink.base;
     147             :         }
     148      361062 :         if (HEAPalloc(&h->heapbckt, mask + HASH_HEADER_SIZE * SIZEOF_SIZE_T / h->width, h->width, 0) != GDK_SUCCEED)
     149             :                 return GDK_FAIL;
     150      361055 :         h->heapbckt.free = mask * h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
     151      361055 :         h->nbucket = mask;
     152      361055 :         if (mask & (mask - 1)) {
     153      104842 :                 h->mask2 = hashmask(mask);
     154      104842 :                 h->mask1 = h->mask2 >> 1;
     155             :         } else {
     156             :                 /* mask is a power of two */
     157      256213 :                 h->mask1 = mask - 1;
     158      256213 :                 h->mask2 = h->mask1 << 1 | 1;
     159             :         }
     160      361055 :         h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
     161      361055 :         h->type = tpe;
     162      361055 :         HASHclear(h);           /* zero the mask */
     163      361034 :         ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
     164      361034 :         ((size_t *) h->heapbckt.base)[1] = (size_t) size;
     165      361034 :         ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
     166      361034 :         ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
     167      361034 :         ((size_t *) h->heapbckt.base)[4] = (size_t) count;
     168      361034 :         ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
     169      361034 :         ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
     170      361034 :         TRC_DEBUG(ACCELERATOR,
     171             :                   "create hash(size " BUNFMT ", mask " BUNFMT ", width %d, total " BUNFMT " bytes);\n", size, mask, h->width, (size + mask) * h->width);
     172             :         return GDK_SUCCEED;
     173             : }
     174             : 
     175             : /* collect HASH statistics for analysis */
     176             : static void
     177           0 : HASHcollisions(BAT *b, Hash *h, const char *func)
     178             : {
     179             :         lng cnt, entries = 0, max = 0;
     180             :         double total = 0;
     181             :         BUN p, i, j;
     182             : 
     183           0 :         if (b == 0 || h == 0)
     184             :                 return;
     185           0 :         for (i = 0, j = h->nbucket; i < j; i++)
     186           0 :                 if ((p = HASHget(h, i)) != BUN_NONE) {
     187           0 :                         entries++;
     188             :                         cnt = 0;
     189           0 :                         for (; p != BUN_NONE; p = HASHgetlink(h, p))
     190           0 :                                 cnt++;
     191             :                         if (cnt > max)
     192             :                                 max = cnt;
     193           0 :                         total += cnt;
     194             :                 }
     195           0 :         TRC_DEBUG_ENDIF(ACCELERATOR,
     196             :                         "%s(" ALGOBATFMT "): statistics " BUNFMT ", "
     197             :                         "entries " LLFMT ", nunique " BUNFMT ", "
     198             :                         "nbucket " BUNFMT ", max " LLFMT ", avg %2.6f;\n",
     199             :                         func, ALGOBATPAR(b), BATcount(b), entries,
     200             :                         h->nunique, h->nbucket, max,
     201             :                         entries == 0 ? 0 : total / entries);
     202             : }
     203             : 
     204             : static gdk_return
     205           0 : HASHupgradehashheap(BAT *b)
     206             : {
     207             : #if defined(BUN2) || defined(BUN8)
     208           0 :         Hash *h = b->thash;
     209           0 :         int nwidth = h->width << 1;
     210             :         BUN i;
     211             : 
     212           0 :         assert(nwidth <= SIZEOF_BUN);
     213           0 :         assert((nwidth & (nwidth - 1)) == 0);
     214             : 
     215           0 :         if (HEAPextend(&h->heaplink, h->heaplink.size * nwidth / h->width, true) != GDK_SUCCEED ||
     216           0 :             HEAPextend(&h->heapbckt, (h->heapbckt.size - HASH_HEADER_SIZE * SIZEOF_SIZE_T) * nwidth / h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T, true) != GDK_SUCCEED) {
     217           0 :                 b->thash = NULL;
     218           0 :                 doHASHdestroy(b, h);
     219           0 :                 return GDK_FAIL;
     220             :         }
     221           0 :         h->Link = h->heaplink.base;
     222           0 :         h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
     223           0 :         switch (nwidth) {
     224           0 :         case BUN4:
     225             : #ifdef BUN2
     226           0 :                 switch (h->width) {
     227           0 :                 case BUN2:
     228           0 :                         i = h->heaplink.free / h->width;
     229           0 :                         h->heaplink.free = i * nwidth;
     230           0 :                         while (i > 0) {
     231           0 :                                 i--;
     232           0 :                                 BUN2type v = ((BUN2type *) h->Link)[i];
     233           0 :                                 ((BUN4type *) h->Link)[i] = v == BUN2_NONE ? BUN4_NONE : v;
     234             :                         }
     235           0 :                         i = (h->heapbckt.free - HASH_HEADER_SIZE * SIZEOF_SIZE_T) / h->width;
     236           0 :                         h->heapbckt.free = HASH_HEADER_SIZE * SIZEOF_SIZE_T + i * nwidth;
     237           0 :                         while (i > 0) {
     238           0 :                                 i--;
     239           0 :                                 BUN2type v = ((BUN2type *) h->Bckt)[i];
     240           0 :                                 ((BUN4type *) h->Bckt)[i] = v == BUN2_NONE ? BUN4_NONE : v;
     241             :                         }
     242             :                         break;
     243             :                 }
     244             : #endif
     245             :                 break;
     246             : #ifdef BUN8
     247           0 :         case BUN8:
     248           0 :                 switch (h->width) {
     249             : #ifdef BUN2
     250           0 :                 case BUN2:
     251           0 :                         i = h->heaplink.free / h->width;
     252           0 :                         h->heaplink.free = i * nwidth;
     253           0 :                         while (i > 0) {
     254           0 :                                 i--;
     255           0 :                                 BUN2type v = ((BUN2type *) h->Link)[i];
     256           0 :                                 ((BUN8type *) h->Link)[i] = v == BUN2_NONE ? BUN8_NONE : v;
     257             :                         }
     258           0 :                         i = (h->heapbckt.free - HASH_HEADER_SIZE * SIZEOF_SIZE_T) / h->width;
     259           0 :                         h->heapbckt.free = HASH_HEADER_SIZE * SIZEOF_SIZE_T + i * nwidth;
     260           0 :                         while (i > 0) {
     261           0 :                                 i--;
     262           0 :                                 BUN2type v = ((BUN2type *) h->Bckt)[i];
     263           0 :                                 ((BUN8type *) h->Bckt)[i] = v == BUN2_NONE ? BUN8_NONE : v;
     264             :                         }
     265             :                         break;
     266             : #endif
     267           0 :                 case BUN4:
     268           0 :                         i = h->heaplink.free / h->width;
     269           0 :                         h->heaplink.free = i * nwidth;
     270           0 :                         while (i > 0) {
     271           0 :                                 i--;
     272           0 :                                 BUN4type v = ((BUN4type *) h->Link)[i];
     273           0 :                                 ((BUN8type *) h->Link)[i] = v == BUN4_NONE ? BUN8_NONE : v;
     274             :                         }
     275           0 :                         i = (h->heapbckt.free - HASH_HEADER_SIZE * SIZEOF_SIZE_T) / h->width;
     276           0 :                         h->heapbckt.free = HASH_HEADER_SIZE * SIZEOF_SIZE_T + i * nwidth;
     277           0 :                         while (i > 0) {
     278           0 :                                 i--;
     279           0 :                                 BUN4type v = ((BUN4type *) h->Bckt)[i];
     280           0 :                                 ((BUN8type *) h->Bckt)[i] = v == BUN4_NONE ? BUN8_NONE : v;
     281             :                         }
     282             :                         break;
     283             :                 }
     284             :                 break;
     285             : #endif
     286             :         }
     287           0 :         h->width = nwidth;
     288             : #else
     289             :         (void) b;
     290             : #endif
     291           0 :         return GDK_SUCCEED;
     292             : }
     293             : 
     294             : /* write/remove the bit into/from the hash file that indicates the hash
     295             :  * is good to go; the bit is the last part to be written and the first
     296             :  * to be removed */
     297             : static inline gdk_return
     298     1712626 : HASHfix(Hash *h, bool save, bool dosync)
     299             : {
     300     1712626 :         if (!h->heapbckt.dirty && !h->heaplink.dirty) {
     301             :                 const size_t mask = (size_t) 1 << 24;
     302       57188 :                 if (((size_t *) h->heapbckt.base)[0] & mask) {
     303       23109 :                         if (save)
     304             :                                 return GDK_SUCCEED;
     305       23109 :                         ((size_t *) h->heapbckt.base)[0] &= ~mask;
     306             :                 } else {
     307       34079 :                         if (!save)
     308             :                                 return GDK_SUCCEED;
     309       34078 :                         ((size_t *) h->heapbckt.base)[0] |= mask;
     310             :                 }
     311       57187 :                 if (h->heapbckt.storage == STORE_MEM) {
     312             :                         gdk_return rc = GDK_FAIL;
     313       57059 :                         int fd = GDKfdlocate(h->heapbckt.farmid, h->heapbckt.filename, "rb+", NULL);
     314       57059 :                         if (fd >= 0) {
     315       57059 :                                 if (write(fd, h->heapbckt.base, SIZEOF_SIZE_T) == SIZEOF_SIZE_T) {
     316       57059 :                                         if (dosync &&
     317       57059 :                                             !(GDKdebug & NOSYNCMASK)) {
     318             : #if defined(NATIVE_WIN32)
     319             :                                                 _commit(fd);
     320             : #elif defined(HAVE_FDATASYNC)
     321          92 :                                                 fdatasync(fd);
     322             : #elif defined(HAVE_FSYNC)
     323             :                                                 fsync(fd);
     324             : #endif
     325             :                                         }
     326             :                                         rc = GDK_SUCCEED;
     327             :                                 }
     328       57059 :                                 close(fd);
     329             :                         }
     330       57059 :                         if (rc != GDK_SUCCEED)
     331           0 :                                 ((size_t *) h->heapbckt.base)[0] &= ~mask;
     332       57059 :                         return rc;
     333             :                 } else {
     334         128 :                         if (dosync &&
     335         247 :                             !(GDKdebug & NOSYNCMASK) &&
     336         119 :                             MT_msync(h->heapbckt.base, SIZEOF_SIZE_T) < 0) {
     337           0 :                                 ((size_t *) h->heapbckt.base)[0] &= ~mask;
     338           0 :                                 return GDK_FAIL;
     339             :                         }
     340             :                 }
     341             :         }
     342             :         return GDK_SUCCEED;
     343             : }
     344             : 
     345             : static gdk_return
     346      861401 : HASHgrowbucket(BAT *b)
     347             : {
     348      861401 :         Hash *h = b->thash;
     349             :         BUN nbucket;
     350      861401 :         BUN onbucket = h->nbucket;
     351             :         lng t0 = 0;
     352             : 
     353      861401 :         TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
     354             : 
     355             :         /* only needed to fix hash tables built before this fix was
     356             :          * introduced */
     357      861401 :         if (h->width < SIZEOF_BUN &&
     358      861401 :             ((BUN) 1 << (h->width * 8)) - 1 <= h->mask2 &&
     359           0 :             HASHupgradehashheap(b) != GDK_SUCCEED)
     360             :                 return GDK_FAIL;
     361             : 
     362      861401 :         h->heapbckt.dirty = true;
     363      861401 :         h->heaplink.dirty = true;
     364     1117623 :         while (h->nunique >= (nbucket = h->nbucket) * 7 / 8) {
     365             :                 BUN new = h->nbucket;
     366      256222 :                 BUN old = new & h->mask1;
     367      256222 :                 BUN mask = h->mask1 + 1; /* == h->mask2 - h->mask1 */
     368             : 
     369      256222 :                 assert(h->heapbckt.free == nbucket * h->width + HASH_HEADER_SIZE * SIZEOF_SIZE_T);
     370      256222 :                 if (h->heapbckt.free + h->width > h->heapbckt.size) {
     371        2970 :                         if (HEAPextend(&h->heapbckt,
     372             :                                        h->heapbckt.size + GDK_mmap_pagesize,
     373             :                                        true) != GDK_SUCCEED) {
     374           0 :                                 return GDK_FAIL;
     375             :                         }
     376        2970 :                         h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
     377             :                 }
     378      256222 :                 assert(h->heapbckt.free + h->width <= h->heapbckt.size);
     379      256222 :                 if (h->nbucket == h->mask2) {
     380         273 :                         h->mask1 = h->mask2;
     381         273 :                         h->mask2 |= h->mask2 << 1;
     382         273 :                         if (h->width < SIZEOF_BUN &&
     383         273 :                             h->mask2 == ((BUN) 1 << (h->width * 8)) - 1) {
     384             :                                 /* time to widen the hash table */
     385           0 :                                 if (HASHupgradehashheap(b) != GDK_SUCCEED)
     386             :                                         return GDK_FAIL;
     387             :                         }
     388             :                 }
     389      256222 :                 h->nbucket++;
     390      256222 :                 h->heapbckt.free += h->width;
     391             :                 BUN lold, lnew, hb;
     392             :                 lold = lnew = BUN_NONE;
     393      256222 :                 BATiter bi = bat_iterator(b);
     394      256222 :                 if ((hb = HASHget(h, old)) != BUN_NONE) {
     395      214407 :                         h->nheads--;
     396             :                         do {
     397      446344 :                                 const void *v = BUNtail(bi, hb);
     398      446344 :                                 BUN hsh = ATOMhash(h->type, v);
     399      446344 :                                 assert((hsh & (mask - 1)) == old);
     400      446344 :                                 if (hsh & mask) {
     401             :                                         /* move to new list */
     402      157163 :                                         if (lnew == BUN_NONE) {
     403      115688 :                                                 HASHput(h, new, hb);
     404      115688 :                                                 h->nheads++;
     405             :                                         } else
     406       41475 :                                                 HASHputlink(h, lnew, hb);
     407             :                                         lnew = hb;
     408             :                                 } else {
     409             :                                         /* move to old list */
     410      289181 :                                         if (lold == BUN_NONE) {
     411      152136 :                                                 h->nheads++;
     412      152136 :                                                 HASHput(h, old, hb);
     413             :                                         } else
     414      137045 :                                                 HASHputlink(h, lold, hb);
     415             :                                         lold = hb;
     416             :                                 }
     417      446344 :                                 hb = HASHgetlink(h, hb);
     418      446344 :                         } while (hb != BUN_NONE);
     419             :                 }
     420      256222 :                 bat_iterator_end(&bi);
     421      256222 :                 if (lnew == BUN_NONE)
     422      140534 :                         HASHput(h, new, BUN_NONE);
     423             :                 else
     424      115688 :                         HASHputlink(h, lnew, BUN_NONE);
     425      256222 :                 if (lold == BUN_NONE)
     426      104086 :                         HASHput(h, old, BUN_NONE);
     427             :                 else
     428      152136 :                         HASHputlink(h, lold, BUN_NONE);
     429             :         }
     430      861401 :         TRC_DEBUG_IF(ACCELERATOR) if (h->nbucket > onbucket) {
     431           0 :                 TRC_DEBUG_ENDIF(ACCELERATOR, ALGOBATFMT " " BUNFMT
     432             :                         " -> " BUNFMT " buckets (" LLFMT " usec)\n",
     433             :                         ALGOBATPAR(b),
     434             :                         onbucket, h->nbucket, GDKusec() - t0);
     435           0 :                 HASHcollisions(b, h, __func__);
     436             :         }
     437             :         return GDK_SUCCEED;
     438             : }
     439             : 
     440             : /* Return TRUE if we have a hash on the tail, even if we need to read
     441             :  * one from disk.
     442             :  *
     443             :  * Note that the b->thash pointer can be NULL, meaning there is no
     444             :  * hash; (Hash *) 1, meaning there is no hash loaded, but it may exist
     445             :  * on disk; or a valid pointer to a loaded hash.  These values are
     446             :  * maintained here, in the HASHdestroy and HASHfree functions, and in
     447             :  * BBPdiskscan during initialization. */
     448             : bool
     449     4169683 : BATcheckhash(BAT *b)
     450             : {
     451             :         bool ret;
     452             :         lng t = 0;
     453             : 
     454             :         /* we don't need the lock just to read the value b->thash */
     455     4169683 :         if (b->thash == (Hash *) 1) {
     456             :                 /* but when we want to change it, we need the lock */
     457        1146 :                 TRC_DEBUG_IF(ACCELERATOR) t = GDKusec();
     458        1146 :                 MT_rwlock_wrlock(&b->thashlock);
     459        1146 :                 TRC_DEBUG_IF(ACCELERATOR) t = GDKusec() - t;
     460             :                 /* if still 1 now that we have the lock, we can update */
     461        1146 :                 if (b->thash == (Hash *) 1) {
     462             :                         Hash *h;
     463             :                         int fd;
     464             : 
     465        1145 :                         assert(!GDKinmemory(b->theap->farmid));
     466        1145 :                         b->thash = NULL;
     467        1145 :                         if ((h = GDKzalloc(sizeof(*h))) != NULL &&
     468        1145 :                             (h->heaplink.farmid = BBPselectfarm(b->batRole, b->ttype, hashheap)) >= 0 &&
     469        1145 :                             (h->heapbckt.farmid = BBPselectfarm(b->batRole, b->ttype, hashheap)) >= 0) {
     470        1145 :                                 const char *nme = BBP_physical(b->batCacheid);
     471        1145 :                                 strconcat_len(h->heaplink.filename,
     472             :                                               sizeof(h->heaplink.filename),
     473             :                                               nme, ".thashl", NULL);
     474        1145 :                                 strconcat_len(h->heapbckt.filename,
     475             :                                               sizeof(h->heapbckt.filename),
     476             :                                               nme, ".thashb", NULL);
     477        1145 :                                 h->heaplink.storage = STORE_INVALID;
     478        1145 :                                 h->heaplink.newstorage = STORE_INVALID;
     479        1145 :                                 h->heapbckt.storage = STORE_INVALID;
     480        1145 :                                 h->heapbckt.newstorage = STORE_INVALID;
     481             : 
     482             :                                 /* check whether a persisted hash can be found */
     483        1145 :                                 if ((fd = GDKfdlocate(h->heapbckt.farmid, nme, "rb+", "thashb")) >= 0) {
     484             :                                         size_t hdata[HASH_HEADER_SIZE];
     485             :                                         struct stat st;
     486             : 
     487        1145 :                                         if (read(fd, hdata, sizeof(hdata)) == sizeof(hdata) &&
     488        1145 :                                             (hdata[0] == (
     489             : #ifdef PERSISTENTHASH
     490             :                                                     ((size_t) 1 << 24) |
     491             : #endif
     492             :                                                     HASH_VERSION)
     493             : #ifdef HASH_VERSION_NOUUID
     494             :                                              /* if not uuid, also allow previous version */
     495           3 :                                              || (hdata[0] == (
     496             : #ifdef PERSISTENTHASH
     497             :                                                          ((size_t) 1 << 24) |
     498             : #endif
     499           0 :                                                          HASH_VERSION_NOUUID) &&
     500           0 :                                                  strcmp(ATOMname(b->ttype), "uuid") != 0)
     501             : #endif
     502        1142 :                                                     ) &&
     503        1142 :                                             hdata[1] > 0 &&
     504             :                                             (
     505             : #ifdef BUN2
     506        1142 :                                                     hdata[3] == BUN2 ||
     507             : #endif
     508             :                                                     hdata[3] == BUN4
     509             : #ifdef BUN8
     510           0 :                                                     || hdata[3] == BUN8
     511             : #endif
     512        1142 :                                                     ) &&
     513        2284 :                                             hdata[4] == (size_t) BATcount(b) &&
     514        1142 :                                             fstat(fd, &st) == 0 &&
     515        2284 :                                             st.st_size >= (off_t) (h->heapbckt.size = h->heapbckt.free = (h->nbucket = (BUN) hdata[2]) * (BUN) (h->width = (uint8_t) hdata[3]) + HASH_HEADER_SIZE * SIZEOF_SIZE_T) &&
     516        2284 :                                             close(fd) == 0 &&
     517        2284 :                                             (fd = GDKfdlocate(h->heaplink.farmid, nme, "rb+", "thashl")) >= 0 &&
     518        1142 :                                             fstat(fd, &st) == 0 &&
     519        1142 :                                             st.st_size > 0 &&
     520        2284 :                                             st.st_size >= (off_t) (h->heaplink.size = h->heaplink.free = hdata[1] * h->width) &&
     521        1142 :                                             HEAPload(&h->heaplink, nme, "thashl", false) == GDK_SUCCEED) {
     522        1142 :                                                 if (HEAPload(&h->heapbckt, nme, "thashb", false) == GDK_SUCCEED) {
     523        1142 :                                                         if (h->nbucket & (h->nbucket - 1)) {
     524         398 :                                                                 h->mask2 = hashmask(h->nbucket);
     525         398 :                                                                 h->mask1 = h->mask2 >> 1;
     526             :                                                         } else {
     527         744 :                                                                 h->mask1 = h->nbucket - 1;
     528         744 :                                                                 h->mask2 = h->mask1 << 1 | 1;
     529             :                                                         }
     530        1142 :                                                         h->nunique = hdata[5];
     531        1142 :                                                         h->nheads = hdata[6];
     532        1142 :                                                         h->type = ATOMtype(b->ttype);
     533        1142 :                                                         if (h->width < SIZEOF_BUN &&
     534        1142 :                                                             ((BUN) 1 << (8 * h->width)) - 1 > h->nbucket) {
     535        1135 :                                                                 close(fd);
     536        1135 :                                                                 h->Link = h->heaplink.base;
     537        1135 :                                                                 h->Bckt = h->heapbckt.base + HASH_HEADER_SIZE * SIZEOF_SIZE_T;
     538        1135 :                                                                 h->heaplink.parentid = b->batCacheid;
     539        1135 :                                                                 h->heapbckt.parentid = b->batCacheid;
     540        1135 :                                                                 h->heaplink.dirty = false;
     541        1135 :                                                                 h->heapbckt.dirty = false;
     542        1135 :                                                                 b->thash = h;
     543        1135 :                                                                 TRC_DEBUG(ACCELERATOR,
     544             :                                                                           ALGOBATFMT ": reusing persisted hash\n", ALGOBATPAR(b));
     545        1135 :                                                                 MT_rwlock_wrunlock(&b->thashlock);
     546        1135 :                                                                 return true;
     547             :                                                         }
     548             :                                                         /* if h->nbucket
     549             :                                                          * equals the
     550             :                                                          * BUN_NONE
     551             :                                                          * representation
     552             :                                                          * for the
     553             :                                                          * current hash
     554             :                                                          * width (was
     555             :                                                          * possible in
     556             :                                                          * previous
     557             :                                                          * iterations of
     558             :                                                          * the code),
     559             :                                                          * then we can't
     560             :                                                          * use the hash
     561             :                                                          * since we
     562             :                                                          * can't
     563             :                                                          * distinguish
     564             :                                                          * between
     565             :                                                          * end-of-list
     566             :                                                          * and a valid
     567             :                                                          * link */
     568           7 :                                                         HEAPfree(&h->heapbckt, false);
     569             :                                                 }
     570           7 :                                                 HEAPfree(&h->heaplink, false);
     571             :                                         }
     572          10 :                                         close(fd);
     573             :                                         /* unlink unusable file */
     574          10 :                                         GDKunlink(h->heaplink.farmid, BATDIR, nme, "thashl");
     575          10 :                                         GDKunlink(h->heapbckt.farmid, BATDIR, nme, "thashb");
     576             :                                 }
     577             :                         }
     578          10 :                         GDKfree(h);
     579          10 :                         GDKclrerr();    /* we're not currently interested in errors */
     580             :                 }
     581          11 :                 MT_rwlock_wrunlock(&b->thashlock);
     582             :         }
     583     4168548 :         ret = b->thash != NULL;
     584     4168548 :         if (ret) {
     585     2599087 :                 TRC_DEBUG(ACCELERATOR, ALGOBATFMT ": already has hash, waited " LLFMT " usec\n", ALGOBATPAR(b), t);
     586             :         }
     587             :         return ret;
     588             : }
     589             : 
     590             : static void
     591       74879 : BAThashsave_intern(BAT *b, bool dosync)
     592             : {
     593             :         Hash *h;
     594             :         lng t0 = 0;
     595             : 
     596       74879 :         TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
     597             : 
     598       74879 :         if ((h = b->thash) != NULL) {
     599       74879 :                 Heap *hp = &h->heapbckt;
     600             : 
     601             : #ifndef PERSISTENTHASH
     602             :                 /* no need to sync if not persistent */
     603             :                 dosync = false;
     604             : #endif
     605             : 
     606             :                 /* only persist if parent BAT hasn't changed in the
     607             :                  * mean time */
     608       74879 :                 if (!b->theap->dirty &&
     609       68156 :                     ((size_t *) h->heapbckt.base)[4] == BATcount(b) &&
     610       68156 :                     HEAPsave(&h->heaplink, h->heaplink.filename, NULL, dosync, h->heaplink.free) == GDK_SUCCEED &&
     611       34078 :                     HEAPsave(hp, hp->filename, NULL, dosync, hp->free) == GDK_SUCCEED) {
     612       34078 :                         h->heaplink.dirty = false;
     613       34078 :                         hp->dirty = false;
     614       34078 :                         gdk_return rc = HASHfix(h, true, dosync);
     615       34078 :                         TRC_DEBUG(ACCELERATOR,
     616             :                                   ALGOBATFMT ": persisting hash %s%s (" LLFMT " usec)%s\n", ALGOBATPAR(b), hp->filename, dosync ? "" : " no sync", GDKusec() - t0, rc == GDK_SUCCEED ? "" : " failed");
     617             :                 }
     618       74879 :                 GDKclrerr();
     619             :         }
     620       74880 : }
     621             : 
     622             : void
     623       65853 : BAThashsave(BAT *b, bool dosync)
     624             : {
     625       65853 :         Hash *h = b->thash;
     626       65853 :         if (h == NULL)
     627             :                 return;
     628       65853 :         ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
     629       65853 :         ((size_t *) h->heapbckt.base)[1] = (size_t) (h->heaplink.free / h->width);
     630       65853 :         ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
     631       65853 :         ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
     632       65853 :         ((size_t *) h->heapbckt.base)[4] = (size_t) BATcount(b);
     633       65853 :         ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
     634       65853 :         ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
     635       65853 :         BAThashsave_intern(b, dosync);
     636             : }
     637             : 
     638             : #ifdef PERSISTENTHASH
     639             : static void
     640        9027 : BAThashsync(void *arg)
     641             : {
     642             :         BAT *b = arg;
     643             : 
     644             :         /* we could check whether b->thash == NULL before getting the
     645             :          * lock, and only lock if it isn't; however, it's very
     646             :          * unlikely that that is the case, so we don't */
     647        9027 :         MT_rwlock_rdlock(&b->thashlock);
     648        9027 :         BAThashsave_intern(b, true);
     649        9027 :         MT_rwlock_rdunlock(&b->thashlock);
     650        9027 :         BBPunfix(b->batCacheid);
     651        9027 : }
     652             : #endif
     653             : 
     654             : #define EQbte(a, b)     ((a) == (b))
     655             : #define EQsht(a, b)     ((a) == (b))
     656             : #define EQint(a, b)     ((a) == (b))
     657             : #define EQlng(a, b)     ((a) == (b))
     658             : #ifdef HAVE_HGE
     659             : #define EQhge(a, b)     ((a) == (b))
     660             : #endif
     661             : #define EQflt(a, b)     (is_flt_nil(a) ? is_flt_nil(b) : (a) == (b))
     662             : #define EQdbl(a, b)     (is_dbl_nil(a) ? is_dbl_nil(b) : (a) == (b))
     663             : #ifdef HAVE_HGE
     664             : #define EQuuid(a, b)    ((a).h == (b).h)
     665             : #else
     666             : #ifdef HAVE_UUID
     667             : #define EQuuid(a, b)    (uuid_compare((a).u, (b).u) == 0)
     668             : #else
     669             : #define EQuuid(a, b)    (memcmp((a).u, (b).u, UUID_SIZE) == 0)
     670             : #endif
     671             : #endif
     672             : 
     673             : #define starthash(TYPE)                                                 \
     674             :         do {                                                            \
     675             :                 const TYPE *restrict v = (const TYPE *) BUNtloc(bi, 0); \
     676             :                 TIMEOUT_LOOP(p, timeoffset) {                           \
     677             :                         hget = HASHget(h, c);                           \
     678             :                         if (hget == BUN_NONE) {                         \
     679             :                                 if (h->nheads == maxslots)           \
     680             :                                         TIMEOUT_LOOP_BREAK; /* mask too full */ \
     681             :                                 h->nheads++;                         \
     682             :                                 h->nunique++;                                \
     683             :                         } else {                                        \
     684             :                                 for (hb = hget;                         \
     685             :                                      hb != BUN_NONE;                    \
     686             :                                      hb = HASHgetlink(h, hb)) {         \
     687             :                                         if (EQ##TYPE(v[o - b->hseqbase], v[hb])) \
     688             :                                                 break;                  \
     689             :                                 }                                       \
     690             :                                 h->nunique += hb == BUN_NONE;                \
     691             :                         }                                               \
     692             :                         HASHputlink(h, p, hget);                        \
     693             :                         HASHput(h, c, p);                               \
     694             :                         o = canditer_next(ci);                          \
     695             :                 }                                                       \
     696             :                 TIMEOUT_CHECK(timeoffset,                               \
     697             :                               GOTO_LABEL_TIMEOUT_HANDLER(bailout));     \
     698             :         } while (0)
     699             : #define finishhash(TYPE)                                                \
     700             :         do {                                                            \
     701             :                 const TYPE *restrict v = (const TYPE *) BUNtloc(bi, 0); \
     702             :                 TIMEOUT_LOOP(ci->ncand - p, timeoffset) {            \
     703             :                         c = hash_##TYPE(h, v + o - b->hseqbase);     \
     704             :                         hget = HASHget(h, c);                           \
     705             :                         h->nheads += hget == BUN_NONE;                       \
     706             :                         if (!hascand) {                                 \
     707             :                                 for (hb = hget;                         \
     708             :                                      hb != BUN_NONE;                    \
     709             :                                      hb = HASHgetlink(h, hb)) {         \
     710             :                                         if (EQ##TYPE(v[o - b->hseqbase], v[hb])) \
     711             :                                                 break;                  \
     712             :                                 }                                       \
     713             :                                 h->nunique += hb == BUN_NONE;                \
     714             :                                 o = canditer_next_dense(ci);            \
     715             :                         } else {                                        \
     716             :                                 o = canditer_next(ci);                  \
     717             :                         }                                               \
     718             :                         HASHputlink(h, p, hget);                        \
     719             :                         HASHput(h, c, p);                               \
     720             :                         p++;                                            \
     721             :                 }                                                       \
     722             :                 TIMEOUT_CHECK(timeoffset,                               \
     723             :                               GOTO_LABEL_TIMEOUT_HANDLER(bailout));     \
     724             :         } while (0)
     725             : 
     726             : /* Internal function to create a hash table for the given BAT b.
     727             :  * If a candidate list s is also given, the hash table is specific for
     728             :  * the combination of the two: only values from b that are referred to
     729             :  * by s are included in the hash table, so if a result is found when
     730             :  * searching the hash table, the result is a candidate. */
     731             : Hash *
     732      105177 : BAThash_impl(BAT *restrict b, struct canditer *restrict ci, const char *restrict ext)
     733             : {
     734             :         lng t0 = 0;
     735      105177 :         unsigned int tpe = ATOMbasetype(b->ttype);
     736             :         BUN cnt1;
     737             :         BUN mask, maxmask = 0;
     738             :         BUN p, c;
     739             :         oid o;
     740             :         BUN hget, hb;
     741             :         Hash *h = NULL;
     742      105177 :         const char *nme = GDKinmemory(b->theap->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
     743      105177 :         BATiter bi = bat_iterator(b);
     744      105177 :         bool hascand = ci->tpe != cand_dense || ci->ncand != bi.count;
     745             : 
     746             :         lng timeoffset = 0;
     747      105177 :         QryCtx *qry_ctx = MT_thread_get_qry_ctx();
     748      105176 :         if (qry_ctx != NULL) {
     749       93920 :                 timeoffset = (qry_ctx->starttime && qry_ctx->querytimeout) ? (qry_ctx->starttime + qry_ctx->querytimeout) : 0;
     750             :         }
     751             : 
     752      105176 :         assert(strcmp(ext, "thash") != 0 || !hascand);
     753             : 
     754      210291 :         MT_thread_setalgorithm(hascand ? "create hash with candidates" : "create hash");
     755      105175 :         TRC_DEBUG_IF(ACCELERATOR) t0 = GDKusec();
     756      105175 :         TRC_DEBUG(ACCELERATOR,
     757             :                   ALGOBATFMT ": create hash;\n", ALGOBATPAR(b));
     758      105175 :         if (b->ttype == TYPE_void) {
     759           0 :                 if (is_oid_nil(b->tseqbase)) {
     760           0 :                         TRC_DEBUG(ACCELERATOR,
     761             :                                   "cannot create hash-table on void-NIL column.\n");
     762           0 :                         GDKerror("no hash on void/nil column\n");
     763           0 :                         bat_iterator_end(&bi);
     764           0 :                         return NULL;
     765             :                 }
     766           0 :                 TRC_DEBUG(ACCELERATOR,
     767             :                           "creating hash-table on void column..\n");
     768           0 :                 assert(0);
     769             :                 tpe = TYPE_void;
     770             :         }
     771             : 
     772      105175 :         if ((h = GDKzalloc(sizeof(*h))) == NULL ||
     773      105176 :             (h->heaplink.farmid = BBPselectfarm(hascand ? TRANSIENT : b->batRole, b->ttype, hashheap)) < 0 ||
     774      105176 :             (h->heapbckt.farmid = BBPselectfarm(hascand ? TRANSIENT : b->batRole, b->ttype, hashheap)) < 0) {
     775           0 :                 GDKfree(h);
     776           0 :                 bat_iterator_end(&bi);
     777           0 :                 return NULL;
     778             :         }
     779      105176 :         h->width = HASHwidth(BATcapacity(b));
     780      105176 :         h->heaplink.dirty = true;
     781      105176 :         h->heapbckt.dirty = true;
     782      105176 :         strconcat_len(h->heaplink.filename, sizeof(h->heaplink.filename),
     783             :                       nme, ".", ext, "l", NULL);
     784      105176 :         strconcat_len(h->heapbckt.filename, sizeof(h->heapbckt.filename),
     785             :                       nme, ".", ext, "b", NULL);
     786      105177 :         if (HEAPalloc(&h->heaplink, hascand ? ci->ncand : BATcapacity(b),
     787      105177 :                       h->width, 0) != GDK_SUCCEED) {
     788           0 :                 GDKfree(h);
     789           0 :                 bat_iterator_end(&bi);
     790           0 :                 return NULL;
     791             :         }
     792      105176 :         h->heaplink.free = ci->ncand * h->width;
     793      105176 :         h->Link = h->heaplink.base;
     794             : #ifndef NDEBUG
     795             :         /* clear unused part of Link array */
     796      105176 :         if (h->heaplink.size > h->heaplink.free)
     797       18066 :                 memset(h->heaplink.base + h->heaplink.free, 0,
     798             :                        h->heaplink.size - h->heaplink.free);
     799             : #endif
     800             : 
     801             :         /* determine hash mask size */
     802             :         cnt1 = 0;
     803      105176 :         if (ATOMsize(tpe) == 1) {
     804             :                 /* perfect hash for one-byte sized atoms */
     805             :                 mask = (1 << 8);
     806      104836 :         } else if (ATOMsize(tpe) == 2) {
     807             :                 /* perfect hash for two-byte sized atoms */
     808             :                 mask = (1 << 16);
     809      104407 :         } else if (b->tkey || ci->ncand <= 4096) {
     810             :                 /* if key, or if small, don't bother dynamically
     811             :                  * adjusting the hash mask */
     812       93439 :                 mask = HASHmask(ci->ncand);
     813       10968 :         } else if (!hascand && bi.unique_est != 0) {
     814         284 :                 mask = (BUN) (bi.unique_est * 1.15); /* about 8/7 */
     815             :         } else {
     816             :                 /* dynamic hash: we start with HASHmask(ci->ncand)/64, or,
     817             :                  * if ci->ncand large enough, HASHmask(ci->ncand)/256; if there
     818             :                  * are too many collisions we try HASHmask(ci->ncand)/64,
     819             :                  * HASHmask(ci->ncand)/16, HASHmask(ci->ncand)/4, and finally
     820             :                  * HASHmask(ci->ncand), but we might skip some of these if
     821             :                  * there are many distinct values.  */
     822             :                 maxmask = HASHmask(ci->ncand);
     823       10684 :                 mask = maxmask >> 6;
     824       10771 :                 while (mask > 4096)
     825          87 :                         mask >>= 2;
     826             :                 /* try out on first 25% of b */
     827       10684 :                 cnt1 = ci->ncand >> 2;
     828             :         }
     829             : 
     830      105176 :         o = canditer_next(ci);  /* always one ahead */
     831       10684 :         for (;;) {
     832             :                 lng t1 = 0;
     833      115855 :                 TRC_DEBUG_IF(ACCELERATOR) t1 = GDKusec();
     834      115855 :                 BUN maxslots = (mask >> 3) - 1;   /* 1/8 full is too full */
     835             : 
     836      115855 :                 h->nheads = 0;
     837      115855 :                 h->nunique = 0;
     838             :                 p = 0;
     839      115855 :                 HEAPfree(&h->heapbckt, true);
     840             :                 /* create the hash structures */
     841      231722 :                 if (HASHnew(h, ATOMtype(b->ttype), BATcapacity(b),
     842             :                             mask, ci->ncand, true) != GDK_SUCCEED) {
     843           0 :                         HEAPfree(&h->heaplink, true);
     844           0 :                         GDKfree(h);
     845           0 :                         bat_iterator_end(&bi);
     846           0 :                         return NULL;
     847             :                 }
     848             : 
     849      115861 :                 switch (tpe) {
     850         340 :                 case TYPE_bte:
     851         340 :                         starthash(bte);
     852             :                         break;
     853         429 :                 case TYPE_sht:
     854         429 :                         starthash(sht);
     855             :                         break;
     856          12 :                 case TYPE_flt:
     857          12 :                         starthash(flt);
     858             :                         break;
     859      111568 :                 case TYPE_int:
     860      111568 :                         starthash(int);
     861             :                         break;
     862          27 :                 case TYPE_dbl:
     863          27 :                         starthash(dbl);
     864             :                         break;
     865        1259 :                 case TYPE_lng:
     866        1259 :                         starthash(lng);
     867             :                         break;
     868             : #ifdef HAVE_HGE
     869          16 :                 case TYPE_hge:
     870          16 :                         starthash(hge);
     871             :                         break;
     872             : #endif
     873           0 :                 case TYPE_uuid:
     874           0 :                         starthash(uuid);
     875             :                         break;
     876             :                 default:
     877             :                         TIMEOUT_LOOP(p, timeoffset) {
     878             :                                 const void *restrict v = BUNtail(bi, o - b->hseqbase);
     879             :                                 c = hash_any(h, v);
     880             :                                 hget = HASHget(h, c);
     881             :                                 if (hget == BUN_NONE) {
     882             :                                         if (h->nheads == maxslots)
     883             :                                                 TIMEOUT_LOOP_BREAK; /* mask too full */
     884             :                                         h->nheads++;
     885             :                                         h->nunique++;
     886             :                                 } else {
     887             :                                         for (hb = hget;
     888             :                                              hb != BUN_NONE;
     889             :                                              hb = HASHgetlink(h, hb)) {
     890             :                                                 if (ATOMcmp(h->type,
     891             :                                                             v,
     892             :                                                             BUNtail(bi, hb)) == 0)
     893             :                                                         break;
     894             :                                         }
     895             :                                         h->nunique += hb == BUN_NONE;
     896             :                                 }
     897             :                                 HASHputlink(h, p, hget);
     898             :                                 HASHput(h, c, p);
     899             :                                 o = canditer_next(ci);
     900             :                         }
     901        2210 :                         TIMEOUT_CHECK(timeoffset,
     902             :                                       GOTO_LABEL_TIMEOUT_HANDLER(bailout));
     903             :                         break;
     904             :                 }
     905      115861 :                 TRC_DEBUG_IF(ACCELERATOR) if (p < cnt1)
     906           0 :                         TRC_DEBUG_ENDIF(ACCELERATOR,
     907             :                                         "%s: abort starthash with "
     908             :                                 "mask " BUNFMT " at " BUNFMT " after " LLFMT " usec\n", BATgetId(b), mask, p, GDKusec() - t1);
     909      115861 :                 if (p == cnt1 || mask == maxmask)
     910             :                         break;
     911       10684 :                 mask <<= 2;
     912             :                 /* if we fill up the slots fast (p <= maxslots * 1.2)
     913             :                  * increase mask size a bit more quickly */
     914       10684 :                 if (p == h->nunique) {
     915             :                         /* only unique values so far: grow really fast */
     916             :                         mask = maxmask;
     917             :                         cnt1 = 0;
     918           0 :                 } else if (mask < maxmask && p <= maxslots * 1.2)
     919           0 :                         mask <<= 2;
     920       10684 :                 canditer_reset(ci);
     921       10684 :                 o = canditer_next(ci);
     922             :         }
     923             : 
     924             :         /* finish the hashtable with the current mask */
     925      105177 :         switch (tpe) {
     926         340 :         case TYPE_bte:
     927      103983 :                 finishhash(bte);
     928             :                 break;
     929         429 :         case TYPE_sht:
     930      213670 :                 finishhash(sht);
     931             :                 break;
     932      100936 :         case TYPE_int:
     933   256469361 :                 finishhash(int);
     934             :                 break;
     935          12 :         case TYPE_flt:
     936         499 :                 finishhash(flt);
     937             :                 break;
     938          27 :         case TYPE_dbl:
     939          92 :                 finishhash(dbl);
     940             :                 break;
     941        1257 :         case TYPE_lng:
     942    40900584 :                 finishhash(lng);
     943             :                 break;
     944             : #ifdef HAVE_HGE
     945          16 :         case TYPE_hge:
     946         292 :                 finishhash(hge);
     947             :                 break;
     948             : #endif
     949           0 :         case TYPE_uuid:
     950           0 :                 finishhash(uuid);
     951             :                 break;
     952        2160 :         default:
     953     7196090 :                 TIMEOUT_LOOP(ci->ncand - p, timeoffset) {
     954     7191596 :                         const void *restrict v = BUNtail(bi, o - b->hseqbase);
     955     7191596 :                         c = hash_any(h, v);
     956     7191516 :                         hget = HASHget(h, c);
     957     7191516 :                         h->nheads += hget == BUN_NONE;
     958     7191516 :                         if (!hascand) {
     959     7305172 :                                 for (hb = hget;
     960             :                                      hb != BUN_NONE;
     961      113610 :                                      hb = HASHgetlink(h, hb)) {
     962     7087127 :                                         if (ATOMcmp(h->type, v, BUNtail(bi, hb)) == 0)
     963             :                                                 break;
     964             :                                 }
     965     7191574 :                                 h->nunique += hb == BUN_NONE;
     966             :                         }
     967     7191528 :                         HASHputlink(h, p, hget);
     968     7191513 :                         HASHput(h, c, p);
     969     7191572 :                         o = canditer_next(ci);
     970     7191596 :                         p++;
     971             :                 }
     972        2160 :                 TIMEOUT_CHECK(timeoffset,
     973             :                               GOTO_LABEL_TIMEOUT_HANDLER(bailout));
     974             :                 break;
     975             :         }
     976      105176 :         bat_iterator_end(&bi);
     977      105177 :         h->heapbckt.parentid = b->batCacheid;
     978      105177 :         h->heaplink.parentid = b->batCacheid;
     979             :         /* if the number of unique values is equal to the bat count,
     980             :          * all values are necessarily distinct */
     981      105177 :         if (h->nunique == BATcount(b) && !b->tkey) {
     982       30711 :                 b->tkey = true;
     983       30711 :                 b->batDirtydesc = true;
     984             :         }
     985      105177 :         TRC_DEBUG_IF(ACCELERATOR) {
     986           0 :                 TRC_DEBUG_ENDIF(ACCELERATOR,
     987             :                                 "hash construction " LLFMT " usec\n", GDKusec() - t0);
     988           0 :                 HASHcollisions(b, h, __func__);
     989             :         }
     990             :         return h;
     991             : 
     992           0 :   bailout:
     993           0 :         GDKfree(h);
     994           0 :         return NULL;
     995             : }
     996             : 
     997             : gdk_return
     998     1576768 : BAThash(BAT *b)
     999             : {
    1000     1576768 :         if (ATOMstorage(b->ttype) == TYPE_msk) {
    1001           0 :                 GDKerror("No hash on msk type bats\n");
    1002           0 :                 return GDK_FAIL;
    1003             :         }
    1004     1576768 :         if (BATcheckhash(b)) {
    1005             :                 return GDK_SUCCEED;
    1006             :         }
    1007             :         for (;;) {
    1008             :                 /* If multiple threads simultaneously try to build a
    1009             :                  * hash on a bat, e.g. in order to perform a join, it
    1010             :                  * may happen that one thread succeeds in obtaining the
    1011             :                  * write lock, then builds the hash, releases the lock,
    1012             :                  * acquires the read lock, and performs the join.  The
    1013             :                  * other threads may then still be attempting to acquire
    1014             :                  * the write lock.  But now they have to wait until the
    1015             :                  * read lock is released, which can be quite a long
    1016             :                  * time.  Especially if a second thread goes through the
    1017             :                  * same process as the first. */
    1018      118256 :                 if (MT_rwlock_wrtry(&b->thashlock))
    1019             :                         break;
    1020       13144 :                 MT_sleep_ms(1);
    1021       13144 :                 if (MT_rwlock_rdtry(&b->thashlock)) {
    1022         201 :                         if (b->thash != NULL && b->thash != (Hash *) 1) {
    1023         199 :                                 MT_rwlock_rdunlock(&b->thashlock);
    1024         199 :                                 return GDK_SUCCEED;
    1025             :                         }
    1026           2 :                         MT_rwlock_rdunlock(&b->thashlock);
    1027             :                 }
    1028             :         }
    1029             :         /* we have the write lock */
    1030      105115 :         if (b->thash == NULL) {
    1031             :                 struct canditer ci;
    1032      105114 :                 canditer_init(&ci, b, NULL);
    1033      105114 :                 if ((b->thash = BAThash_impl(b, &ci, "thash")) == NULL) {
    1034           0 :                         MT_rwlock_wrunlock(&b->thashlock);
    1035        9027 :                         return GDK_FAIL;
    1036             :                 }
    1037             : #ifdef PERSISTENTHASH
    1038      105115 :                 if (BBP_status(b->batCacheid) & BBPEXISTING && !b->theap->dirty && !GDKinmemory(b->theap->farmid)) {
    1039        9027 :                         Hash *h = b->thash;
    1040        9027 :                         ((size_t *) h->heapbckt.base)[0] = (size_t) HASH_VERSION;
    1041        9027 :                         ((size_t *) h->heapbckt.base)[1] = (size_t) (h->heaplink.free / h->width);
    1042        9027 :                         ((size_t *) h->heapbckt.base)[2] = (size_t) h->nbucket;
    1043        9027 :                         ((size_t *) h->heapbckt.base)[3] = (size_t) h->width;
    1044        9027 :                         ((size_t *) h->heapbckt.base)[4] = (size_t) BATcount(b);
    1045        9027 :                         ((size_t *) h->heapbckt.base)[5] = (size_t) h->nunique;
    1046        9027 :                         ((size_t *) h->heapbckt.base)[6] = (size_t) h->nheads;
    1047             :                         MT_Id tid;
    1048        9027 :                         BBPfix(b->batCacheid);
    1049             :                         char name[MT_NAME_LEN];
    1050        9027 :                         snprintf(name, sizeof(name), "hashsync%d", b->batCacheid);
    1051        9027 :                         MT_rwlock_wrunlock(&b->thashlock);
    1052        9027 :                         if (MT_create_thread(&tid, BAThashsync, b,
    1053             :                                              MT_THR_DETACHED,
    1054             :                                              name) < 0) {
    1055             :                                 /* couldn't start thread: clean up */
    1056           0 :                                 BBPunfix(b->batCacheid);
    1057             :                         }
    1058             :                         return GDK_SUCCEED;
    1059             :                 } else
    1060       96088 :                         TRC_DEBUG(ACCELERATOR,
    1061             :                                         "NOT persisting hash %d\n", b->batCacheid);
    1062             : #endif
    1063             :         }
    1064       96089 :         MT_rwlock_wrunlock(&b->thashlock);
    1065       96088 :         return GDK_SUCCEED;
    1066             : }
    1067             : 
    1068             : /*
    1069             :  * The entry on which a value hashes can be calculated with the
    1070             :  * routine HASHprobe.
    1071             :  */
    1072             : BUN
    1073    60638259 : HASHprobe(const Hash *h, const void *v)
    1074             : {
    1075    94339646 :         switch (ATOMbasetype(h->type)) {
    1076        7205 :         case TYPE_bte:
    1077        7205 :                 return hash_bte(h, v);
    1078      382407 :         case TYPE_sht:
    1079      382407 :                 return hash_sht(h, v);
    1080    17927630 :         case TYPE_int:
    1081             :         case TYPE_flt:
    1082    17927630 :                 return hash_int(h, v);
    1083    27686134 :         case TYPE_dbl:
    1084             :         case TYPE_lng:
    1085    27686134 :                 return hash_lng(h, v);
    1086             : #ifdef HAVE_HGE
    1087       18702 :         case TYPE_hge:
    1088       18702 :                 return hash_hge(h, v);
    1089             : #endif
    1090           9 :         case TYPE_uuid:
    1091           9 :                 return hash_uuid(h, v);
    1092    14616172 :         default:
    1093    14616172 :                 return hash_any(h, v);
    1094             :         }
    1095             : }
    1096             : 
    1097             : void
    1098     1105631 : HASHappend_locked(BAT *b, BUN i, const void *v)
    1099             : {
    1100     1105631 :         Hash *h = b->thash;
    1101     1105631 :         if (h == NULL) {
    1102          54 :                 return;
    1103             :         }
    1104     1105631 :         if (h == (Hash *) 1) {
    1105          53 :                 b->thash = NULL;
    1106          53 :                 doHASHdestroy(b, h);
    1107          53 :                 GDKclrerr();
    1108          53 :                 return;
    1109             :         }
    1110     1105578 :         assert(i * h->width == h->heaplink.free);
    1111     1105578 :         if (h->nunique < b->batCount / HASH_DESTROY_UNIQUES_FRACTION) {
    1112           1 :                 b->thash = NULL;
    1113           1 :                 doHASHdestroy(b, h);
    1114           1 :                 GDKclrerr();
    1115           1 :                 return;
    1116             :         }
    1117     1105577 :         if (HASHfix(h, false, true) != GDK_SUCCEED) {
    1118           0 :                 b->thash = NULL;
    1119           0 :                 doHASHdestroy(b, h);
    1120           0 :                 GDKclrerr();
    1121           0 :                 return;
    1122             :         }
    1123     1105577 :         if (HASHwidth(i + 1) > h->width &&
    1124           0 :              HASHupgradehashheap(b) != GDK_SUCCEED) {
    1125           0 :                 GDKclrerr();
    1126           0 :                 return;
    1127             :         }
    1128     1966978 :         if ((ATOMsize(b->ttype) > 2 &&
    1129      861401 :              HASHgrowbucket(b) != GDK_SUCCEED) ||
    1130     1106557 :             ((i + 1) * h->width > h->heaplink.size &&
    1131         980 :              HEAPextend(&h->heaplink,
    1132         980 :                         i * h->width + GDK_mmap_pagesize,
    1133             :                         true) != GDK_SUCCEED)) {
    1134           0 :                 b->thash = NULL;
    1135           0 :                 HEAPfree(&h->heapbckt, true);
    1136           0 :                 HEAPfree(&h->heaplink, true);
    1137           0 :                 GDKfree(h);
    1138           0 :                 GDKclrerr();
    1139           0 :                 return;
    1140             :         }
    1141     1105577 :         h->Link = h->heaplink.base;
    1142     1105577 :         BUN c = HASHprobe(h, v);
    1143     1105577 :         h->heaplink.free += h->width;
    1144     1105577 :         BUN hb = HASHget(h, c);
    1145             :         BUN hb2;
    1146     1105577 :         BATiter bi = bat_iterator_nolock(b);
    1147     1105577 :         int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
    1148     1450972 :         for (hb2 = hb;
    1149             :              hb2 != BUN_NONE;
    1150      345395 :              hb2 = HASHgetlink(h, hb2)) {
    1151     1024711 :                 if (atomcmp(v, BUNtail(bi, hb2)) == 0)
    1152             :                         break;
    1153             :         }
    1154     1105577 :         h->nheads += hb == BUN_NONE;
    1155     1105577 :         h->nunique += hb2 == BUN_NONE;
    1156     1105577 :         HASHputlink(h, i, hb);
    1157     1105577 :         HASHput(h, c, i);
    1158     1105576 :         h->heapbckt.dirty = true;
    1159     1105576 :         h->heaplink.dirty = true;
    1160             : }
    1161             : 
    1162             : void
    1163           0 : HASHappend(BAT *b, BUN i, const void *v)
    1164             : {
    1165           0 :         MT_rwlock_wrlock(&b->thashlock);
    1166           0 :         HASHappend_locked(b, i, v);
    1167           0 :         MT_rwlock_wrunlock(&b->thashlock);
    1168           0 : }
    1169             : 
    1170             : /* insert value v at position p into the hash table of b */
    1171             : void
    1172   117386576 : HASHinsert_locked(BAT *b, BUN p, const void *v)
    1173             : {
    1174   117386576 :         Hash *h = b->thash;
    1175   117386576 :         if (h == NULL) {
    1176             :                 return;
    1177             :         }
    1178      286486 :         if (h == (Hash *) 1) {
    1179           0 :                 b->thash = NULL;
    1180           0 :                 doHASHdestroy(b, h);
    1181           0 :                 GDKclrerr();
    1182           0 :                 return;
    1183             :         }
    1184      286486 :         assert(p * h->width < h->heaplink.free);
    1185      286486 :         if (h->nunique < b->batCount / HASH_DESTROY_UNIQUES_FRACTION) {
    1186           1 :                 b->thash = NULL;
    1187           1 :                 doHASHdestroy(b, h);
    1188           1 :                 GDKclrerr();
    1189           1 :                 return;
    1190             :         }
    1191      286485 :         if (HASHfix(h, false, true) != GDK_SUCCEED) {
    1192           0 :                 b->thash = NULL;
    1193           0 :                 doHASHdestroy(b, h);
    1194           0 :                 GDKclrerr();
    1195           0 :                 return;
    1196             :         }
    1197      286485 :         BUN c = HASHprobe(h, v);
    1198      286485 :         BUN hb = HASHget(h, c);
    1199      286485 :         BATiter bi = bat_iterator_nolock(b);
    1200      286485 :         int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
    1201      286485 :         if (hb == BUN_NONE || hb < p) {
    1202             :                 /* bucket is empty, or bucket is used by lower numbered
    1203             :                  * position */
    1204       55180 :                 h->heaplink.dirty = true;
    1205       55180 :                 h->heapbckt.dirty = true;
    1206       55180 :                 HASHputlink(h, p, hb);
    1207       55180 :                 HASHput(h, c, p);
    1208       55180 :                 if (hb == BUN_NONE) {
    1209       23463 :                         h->nheads++;
    1210             :                 } else {
    1211             :                         do {
    1212       61579 :                                 if (atomcmp(v, BUNtail(bi, hb)) == 0) {
    1213             :                                         /* found another row with the
    1214             :                                          * same value, so don't
    1215             :                                          * increment nunique */
    1216             :                                         return;
    1217             :                                 }
    1218       44180 :                                 hb = HASHgetlink(h, hb);
    1219       44180 :                         } while (hb != BUN_NONE);
    1220             :                 }
    1221             :                 /* this is a new value */
    1222       37781 :                 h->nunique++;
    1223       37781 :                 return;
    1224             :         }
    1225             :         bool seen = false;
    1226             :         for (;;) {
    1227    86723636 :                 if (!seen)
    1228      240464 :                         seen = atomcmp(v, BUNtail(bi, hb)) == 0;
    1229    86723636 :                 BUN hb2 = HASHgetlink(h, hb);
    1230    86723636 :                 if (hb2 == BUN_NONE || hb2 < p) {
    1231      231305 :                         h->heaplink.dirty = true;
    1232      231305 :                         HASHputlink(h, p, hb2);
    1233      231305 :                         HASHputlink(h, hb, p);
    1234      236725 :                         while (!seen && hb2 != BUN_NONE) {
    1235        5420 :                                 seen = atomcmp(v, BUNtail(bi, hb2)) == 0;
    1236        5420 :                                 hb2 = HASHgetlink(h, hb2);
    1237             :                         }
    1238      231305 :                         if (!seen)
    1239        2981 :                                 h->nunique++;
    1240      231305 :                         return;
    1241             :                 }
    1242             :                 hb = hb2;
    1243             :         }
    1244             : }
    1245             : 
    1246             : void
    1247           2 : HASHinsert(BAT *b, BUN p, const void *v)
    1248             : {
    1249           2 :         MT_rwlock_wrlock(&b->thashlock);
    1250           2 :         HASHinsert_locked(b, p, v);
    1251           2 :         MT_rwlock_wrunlock(&b->thashlock);
    1252           2 : }
    1253             : 
    1254             : /* delete value v at position p from the hash table of b */
    1255             : void
    1256   117390314 : HASHdelete_locked(BAT *b, BUN p, const void *v)
    1257             : {
    1258   117390314 :         Hash *h = b->thash;
    1259   117390314 :         if (h == NULL) {
    1260   117143923 :                 return;
    1261             :         }
    1262      286564 :         if (h == (Hash *) 1) {
    1263          62 :                 b->thash = NULL;
    1264          62 :                 doHASHdestroy(b, h);
    1265          62 :                 GDKclrerr();
    1266          62 :                 return;
    1267             :         }
    1268      286502 :         assert(p * h->width < h->heaplink.free);
    1269      286502 :         if (h->nunique < b->batCount / HASH_DESTROY_UNIQUES_FRACTION) {
    1270          16 :                 b->thash = NULL;
    1271          16 :                 doHASHdestroy(b, h);
    1272          16 :                 GDKclrerr();
    1273          16 :                 return;
    1274             :         }
    1275      286486 :         if (HASHfix(h, false, true) != GDK_SUCCEED) {
    1276           0 :                 b->thash = NULL;
    1277           0 :                 doHASHdestroy(b, h);
    1278           0 :                 GDKclrerr();
    1279           0 :                 return;
    1280             :         }
    1281      286486 :         BUN c = HASHprobe(h, v);
    1282      286486 :         BUN hb = HASHget(h, c);
    1283      286486 :         BATiter bi = bat_iterator_nolock(b);
    1284      286486 :         int (*atomcmp)(const void *, const void *) = ATOMcompare(h->type);
    1285      286486 :         if (hb == p) {
    1286       40095 :                 BUN hb2 = HASHgetlink(h, p);
    1287       40095 :                 h->heaplink.dirty = true;
    1288       40095 :                 h->heapbckt.dirty = true;
    1289       40095 :                 HASHput(h, c, hb2);
    1290       40095 :                 HASHputlink(h, p, BUN_NONE);
    1291       40095 :                 if (hb2 == BUN_NONE) {
    1292       24477 :                         h->nheads--;
    1293             :                 } else {
    1294             :                         do {
    1295       43886 :                                 if (atomcmp(v, BUNtail(bi, hb2)) == 0) {
    1296             :                                         /* found another row with the
    1297             :                                          * same value, so don't
    1298             :                                          * decrement nunique below */
    1299             :                                         return;
    1300             :                                 }
    1301       42651 :                                 hb2 = HASHgetlink(h, hb2);
    1302       42651 :                         } while (hb2 != BUN_NONE);
    1303             :                 }
    1304             :                 /* no rows found with the same value, so number of
    1305             :                  * unique values is one lower */
    1306       38860 :                 h->nunique--;
    1307       38860 :                 return;
    1308             :         }
    1309             :         bool seen = false;
    1310             :         for (;;) {
    1311   106774775 :                 if (!seen)
    1312      252802 :                         seen = atomcmp(v, BUNtail(bi, hb)) == 0;
    1313   106774775 :                 BUN hb2 = HASHgetlink(h, hb);
    1314   106774775 :                 assert(hb2 != BUN_NONE );
    1315   106774775 :                 assert(hb2 < hb);
    1316   106774775 :                 if (hb2 == p) {
    1317      246391 :                         for (hb2 = HASHgetlink(h, hb2);
    1318      248081 :                              !seen && hb2 != BUN_NONE;
    1319        1690 :                              hb2 = HASHgetlink(h, hb2))
    1320        1690 :                                 seen = atomcmp(v, BUNtail(bi, hb2)) == 0;
    1321             :                         break;
    1322             :                 }
    1323             :                 hb = hb2;
    1324             :         }
    1325      246391 :         h->heaplink.dirty = true;
    1326      246391 :         HASHputlink(h, hb, HASHgetlink(h, p));
    1327      246391 :         HASHputlink(h, p, BUN_NONE);
    1328      246391 :         if (!seen)
    1329        1425 :                 h->nunique--;
    1330             : }
    1331             : 
    1332             : void
    1333           6 : HASHdelete(BAT *b, BUN p, const void *v)
    1334             : {
    1335           6 :         MT_rwlock_wrlock(&b->thashlock);
    1336           6 :         HASHdelete_locked(b, p, v);
    1337           6 :         MT_rwlock_wrunlock(&b->thashlock);
    1338           6 : }
    1339             : 
    1340             : BUN
    1341           0 : HASHlist(Hash *h, BUN i)
    1342             : {
    1343             :         BUN c = 1;
    1344           0 :         BUN j = HASHget(h, i);
    1345             : 
    1346           0 :         if (j == BUN_NONE)
    1347             :                 return 1;
    1348           0 :         while ((j = HASHgetlink(h, i)) != BUN_NONE) {
    1349           0 :                 c++;
    1350             :                 i = j;
    1351             :         }
    1352             :         return c;
    1353             : }
    1354             : 
    1355             : void
    1356    12439487 : HASHdestroy(BAT *b)
    1357             : {
    1358    12439487 :         if (b && b->thash) {
    1359             :                 Hash *hs;
    1360       99570 :                 MT_rwlock_wrlock(&b->thashlock);
    1361       99570 :                 hs = b->thash;
    1362       99570 :                 b->thash = NULL;
    1363       99570 :                 MT_rwlock_wrunlock(&b->thashlock);
    1364       99570 :                 doHASHdestroy(b, hs);
    1365             :         }
    1366    12439487 : }
    1367             : 
    1368             : void
    1369     4762225 : HASHfree(BAT *b)
    1370             : {
    1371     4762225 :         if (b && b->thash) {
    1372             :                 Hash *h;
    1373        7575 :                 MT_rwlock_wrlock(&b->thashlock);
    1374        7575 :                 if ((h = b->thash) != NULL && h != (Hash *) 1) {
    1375        6665 :                         bool rmheap = h->heaplink.dirty || h->heapbckt.dirty;
    1376        6665 :                         TRC_DEBUG(ACCELERATOR, ALGOBATFMT " free hash %s\n",
    1377             :                                   ALGOBATPAR(b),
    1378             :                                   rmheap ? "removing" : "keeping");
    1379             : 
    1380        6665 :                         b->thash = rmheap ? NULL : (Hash *) 1;
    1381        6665 :                         HEAPfree(&h->heapbckt, rmheap);
    1382        6665 :                         HEAPfree(&h->heaplink, rmheap);
    1383        6665 :                         GDKfree(h);
    1384             :                 }
    1385        7575 :                 MT_rwlock_wrunlock(&b->thashlock);
    1386             :         }
    1387     4762225 : }
    1388             : 
    1389             : bool
    1390           0 : HASHgonebad(BAT *b, const void *v)
    1391             : {
    1392           0 :         Hash *h = b->thash;
    1393             :         BUN cnt, hit;
    1394             : 
    1395           0 :         if (h == NULL)
    1396             :                 return true;    /* no hash is bad hash? */
    1397             : 
    1398           0 :         BATiter bi = bat_iterator(b);
    1399           0 :         if (h->nbucket * 2 < BATcount(b)) {
    1400           0 :                 int (*cmp) (const void *, const void *) = ATOMcompare(b->ttype);
    1401           0 :                 BUN i = HASHget(h, (BUN) HASHprobe(h, v));
    1402           0 :                 for (cnt = hit = 1; i != BUN_NONE; i = HASHgetlink(h, i), cnt++)
    1403           0 :                         hit += ((*cmp) (v, BUNtail(bi, (BUN) i)) == 0);
    1404             : 
    1405           0 :                 if (cnt / hit > 4) {
    1406           0 :                         bat_iterator_end(&bi);
    1407           0 :                         return true;    /* linked list too long */
    1408             :                 }
    1409             : 
    1410             :                 /* in this case, linked lists are long but contain the
    1411             :                  * desired values such hash tables may be useful for
    1412             :                  * locating all duplicates */
    1413             :         }
    1414           0 :         bat_iterator_end(&bi);
    1415           0 :         return false;           /* a-ok */
    1416             : }

Generated by: LCOV version 1.14