LCOV - code coverage report
Current view: top level - gdk - gdk_unique.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 126 152 82.9 %
Date: 2021-09-14 19:48:19 Functions: 1 1 100.0 %

          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             : #include "monetdb_config.h"
      10             : #include "gdk.h"
      11             : #include "gdk_private.h"
      12             : #include "gdk_calc_private.h"
      13             : 
      14             : #define VALUE(x)        (vars ? vars + VarHeapVal(vals, (x), width) : vals + (x) * width)
      15             : /* BATunique returns a bat that indicates the unique tail values of
      16             :  * the input bat.  This is essentially the same output as the
      17             :  * "extents" output of BATgroup.  The difference is that BATunique
      18             :  * does not return the grouping bat.
      19             :  *
      20             :  * The first input is the bat from which unique rows are selected, the
      21             :  * second input is an optional candidate list.
      22             :  *
      23             :  * The return value is a candidate list.
      24             :  */
      25             : BAT *
      26         646 : BATunique(BAT *b, BAT *s)
      27             : {
      28             :         BAT *bn;
      29             :         BUN cnt;
      30             :         const void *v;
      31             :         const char *vals;
      32             :         const char *vars;
      33             :         int width;
      34             :         oid i, o;
      35             :         uint16_t *seen = NULL;
      36             :         const char *nme;
      37             :         Hash *hs = NULL;
      38             :         BUN hb;
      39             :         BATiter bi;
      40             :         int (*cmp)(const void *, const void *);
      41             :         struct canditer ci;
      42             :         const ValRecord *prop;
      43             :         const char *algomsg = "";
      44             :         lng t0 = 0;
      45             : 
      46         646 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
      47             : 
      48         646 :         BATcheck(b, NULL);
      49         646 :         cnt = canditer_init(&ci, b, s);
      50             : 
      51         646 :         if (b->tkey || cnt <= 1 || BATtdense(b)) {
      52             :                 /* trivial: already unique */
      53         245 :                 bn = canditer_slice(&ci, 0, ci.ncand);
      54         245 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT
      55             :                           ",s=" ALGOOPTBATFMT " -> " ALGOOPTBATFMT
      56             :                           " (already unique, slice candidates -- "
      57             :                           LLFMT "usec)\n",
      58             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s),
      59             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
      60         245 :                 return bn;
      61             :         }
      62             : 
      63         401 :         if ((BATordered(b) && BATordered_rev(b)) ||
      64         332 :             (b->ttype == TYPE_void && is_oid_nil(b->tseqbase))) {
      65             :                 /* trivial: all values are the same */
      66          69 :                 bn = BATdense(0, ci.seq, 1);
      67          69 :                 TRC_DEBUG(ALGO, "b=" ALGOBATFMT
      68             :                           ",s=" ALGOOPTBATFMT " -> " ALGOOPTBATFMT
      69             :                           " (all equal -- "
      70             :                           LLFMT "usec)\n",
      71             :                           ALGOBATPAR(b), ALGOOPTBATPAR(s),
      72             :                           ALGOOPTBATPAR(bn), GDKusec() - t0);
      73          69 :                 return bn;
      74             :         }
      75             : 
      76         332 :         assert(b->ttype != TYPE_void);
      77             : 
      78             :         BUN initsize = BUN_NONE;
      79         332 :         if (s == NULL) {
      80         266 :                 MT_rwlock_rdlock(&b->thashlock);
      81         266 :                 if (b->thash != NULL && b->thash != (Hash *) 1)
      82           2 :                         initsize = b->thash->nunique;
      83         266 :                 MT_rwlock_rdunlock(&b->thashlock);
      84         266 :                 if (initsize == BUN_NONE) {
      85         264 :                         MT_lock_set(&b->theaplock);
      86         264 :                         if ((prop = BATgetprop_nolock(b, GDK_NUNIQUE)) != NULL)
      87           0 :                                 initsize = prop->val.oval;
      88         264 :                         else if ((prop = BATgetprop_nolock(b, GDK_UNIQUE_ESTIMATE)) != NULL)
      89          13 :                                 initsize = (BUN) prop->val.dval;
      90         264 :                         MT_lock_unset(&b->theaplock);
      91             :                 }
      92             :         }
      93         266 :         if (initsize == BUN_NONE)
      94             :                 initsize = 1024;
      95         332 :         bn = COLnew(0, TYPE_oid, initsize, TRANSIENT);
      96         332 :         if (bn == NULL)
      97             :                 return NULL;
      98         332 :         bi = bat_iterator(b);
      99         332 :         vals = bi.base;
     100         332 :         if (b->tvarsized && b->ttype)
     101          97 :                 vars = bi.vh->base;
     102             :         else
     103             :                 vars = NULL;
     104         332 :         width = bi.width;
     105         332 :         cmp = ATOMcompare(b->ttype);
     106             : 
     107         332 :         if (BATordered(b) || BATordered_rev(b)) {
     108             :                 const void *prev = NULL;
     109             :                 algomsg = "unique: sorted";
     110      255378 :                 for (i = 0; i < ci.ncand; i++) {
     111      255301 :                         o = canditer_next(&ci);
     112      255301 :                         v = VALUE(o - b->hseqbase);
     113      255301 :                         if (prev == NULL || (*cmp)(v, prev) != 0) {
     114       39657 :                                 if (bunfastappTYPE(oid, bn, &o) != GDK_SUCCEED)
     115           0 :                                         goto bunins_failed;
     116             :                         }
     117             :                         prev = v;
     118             :                 }
     119         255 :         } else if (ATOMbasetype(b->ttype) == TYPE_bte) {
     120             :                 unsigned char val;
     121             : 
     122             :                 algomsg = "unique: byte-sized atoms";
     123          20 :                 assert(vars == NULL);
     124          20 :                 seen = GDKzalloc((256 / 16) * sizeof(seen[0]));
     125          20 :                 if (seen == NULL)
     126           0 :                         goto bunins_failed;
     127       20148 :                 for (i = 0; i < ci.ncand; i++) {
     128       20128 :                         o = canditer_next(&ci);
     129       20128 :                         val = ((const unsigned char *) vals)[o - b->hseqbase];
     130       20128 :                         if (!(seen[val >> 4] & (1U << (val & 0xF)))) {
     131          40 :                                 seen[val >> 4] |= 1U << (val & 0xF);
     132          40 :                                 if (bunfastappTYPE(oid, bn, &o) != GDK_SUCCEED)
     133           0 :                                         goto bunins_failed;
     134          40 :                                 if (bn->batCount == 256) {
     135             :                                         /* there cannot be more than
     136             :                                          * 256 distinct values */
     137             :                                         break;
     138             :                                 }
     139             :                         }
     140             :                 }
     141          20 :                 GDKfree(seen);
     142             :                 seen = NULL;
     143         235 :         } else if (ATOMbasetype(b->ttype) == TYPE_sht) {
     144             :                 unsigned short val;
     145             : 
     146             :                 algomsg = "unique: short-sized atoms";
     147           9 :                 assert(vars == NULL);
     148           9 :                 seen = GDKzalloc((65536 / 16) * sizeof(seen[0]));
     149           9 :                 if (seen == NULL)
     150           0 :                         goto bunins_failed;
     151        3169 :                 for (i = 0; i < ci.ncand; i++) {
     152        3160 :                         o = canditer_next(&ci);
     153        3160 :                         val = ((const unsigned short *) vals)[o - b->hseqbase];
     154        3160 :                         if (!(seen[val >> 4] & (1U << (val & 0xF)))) {
     155          26 :                                 seen[val >> 4] |= 1U << (val & 0xF);
     156          26 :                                 if (bunfastappTYPE(oid, bn, &o) != GDK_SUCCEED)
     157           0 :                                         goto bunins_failed;
     158          26 :                                 if (bn->batCount == 65536) {
     159             :                                         /* there cannot be more than
     160             :                                          * 65536 distinct values */
     161             :                                         break;
     162             :                                 }
     163             :                         }
     164             :                 }
     165           9 :                 GDKfree(seen);
     166             :                 seen = NULL;
     167         226 :         } else if (BATcheckhash(b) ||
     168         224 :                    (!b->batTransient &&
     169          78 :                     cnt == BATcount(b) &&
     170          80 :                     BAThash(b) == GDK_SUCCEED)) {
     171             :                 BUN lo = 0;
     172             :                 oid seq;
     173             : 
     174             :                 /* we already have a hash table on b, or b is
     175             :                  * persistent and we could create a hash table, or b
     176             :                  * is a view on a bat that already has a hash table */
     177             :                 algomsg = "unique: existing hash";
     178          41 :                 seq = b->hseqbase;
     179          41 :                 MT_rwlock_rdlock(&b->thashlock);
     180          41 :                 hs = b->thash;
     181          41 :                 if (hs == NULL) {
     182           0 :                         MT_rwlock_rdunlock(&b->thashlock);
     183           0 :                         goto lost_hash;
     184             :                 }
     185         306 :                 for (i = 0; i < ci.ncand; i++) {
     186             :                         BUN p;
     187             : 
     188         265 :                         o = canditer_next(&ci);
     189         265 :                         p = o - seq;
     190         265 :                         v = VALUE(p);
     191         274 :                         for (hb = HASHgetlink(hs, p + lo);
     192             :                              hb != BUN_NONE && hb >= lo;
     193           9 :                              hb = HASHgetlink(hs, hb)) {
     194         168 :                                 assert(hb < p + lo);
     195         327 :                                 if (cmp(v, BUNtail(bi, hb)) == 0 &&
     196         159 :                                     canditer_contains(&ci, hb - lo + seq)) {
     197             :                                         /* we've seen this value
     198             :                                          * before */
     199             :                                         break;
     200             :                                 }
     201             :                         }
     202         265 :                         if (hb == BUN_NONE || hb < lo) {
     203         106 :                                 if (bunfastappTYPE(oid, bn, &o) != GDK_SUCCEED) {
     204           0 :                                         MT_rwlock_rdunlock(&b->thashlock);
     205             :                                         hs = NULL;
     206           0 :                                         goto bunins_failed;
     207             :                                 }
     208             :                         }
     209             :                 }
     210          41 :                 MT_rwlock_rdunlock(&b->thashlock);
     211             :         } else {
     212             :                 BUN prb;
     213             :                 BUN p;
     214             :                 BUN mask;
     215             : 
     216         185 :           lost_hash:
     217         185 :                 GDKclrerr();    /* not interested in BAThash errors */
     218             :                 algomsg = "unique: new partial hash";
     219         185 :                 nme = BBP_physical(b->batCacheid);
     220         185 :                 if (ATOMbasetype(b->ttype) == TYPE_bte) {
     221             :                         mask = (BUN) 1 << 8;
     222             :                         cmp = NULL; /* no compare needed, "hash" is perfect */
     223         185 :                 } else if (ATOMbasetype(b->ttype) == TYPE_sht) {
     224             :                         mask = (BUN) 1 << 16;
     225             :                         cmp = NULL; /* no compare needed, "hash" is perfect */
     226             :                 } else {
     227         185 :                         mask = HASHmask(cnt);
     228             :                         if (mask < ((BUN) 1 << 16))
     229             :                                 mask = (BUN) 1 << 16;
     230             :                 }
     231         185 :                 if ((hs = GDKzalloc(sizeof(Hash))) == NULL) {
     232           0 :                         GDKerror("cannot allocate hash table\n");
     233           0 :                         goto bunins_failed;
     234             :                 }
     235         185 :                 if ((hs->heaplink.farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap)) < 0 ||
     236         185 :                     (hs->heapbckt.farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap)) < 0 ||
     237         185 :                     snprintf(hs->heaplink.filename, sizeof(hs->heaplink.filename), "%s.thshunil%x", nme, (unsigned) THRgettid()) >= (int) sizeof(hs->heaplink.filename) ||
     238         370 :                     snprintf(hs->heapbckt.filename, sizeof(hs->heapbckt.filename), "%s.thshunib%x", nme, (unsigned) THRgettid()) >= (int) sizeof(hs->heapbckt.filename) ||
     239         185 :                     HASHnew(hs, b->ttype, BUNlast(b), mask, BUN_NONE, false) != GDK_SUCCEED) {
     240           0 :                         GDKfree(hs);
     241             :                         hs = NULL;
     242           0 :                         GDKerror("cannot allocate hash table\n");
     243           0 :                         goto bunins_failed;
     244             :                 }
     245      221198 :                 for (i = 0; i < ci.ncand; i++) {
     246      221013 :                         o = canditer_next(&ci);
     247      197431 :                         v = VALUE(o - b->hseqbase);
     248      197431 :                         prb = HASHprobe(hs, v);
     249      220892 :                         for (hb = HASHget(hs, prb);
     250             :                              hb != BUN_NONE;
     251       22863 :                              hb = HASHgetlink(hs, hb)) {
     252      146554 :                                 if (cmp == NULL || cmp(v, BUNtail(bi, hb)) == 0)
     253             :                                         break;
     254             :                         }
     255      220487 :                         if (hb == BUN_NONE) {
     256       74221 :                                 p = o - b->hseqbase;
     257       74221 :                                 if (bunfastappTYPE(oid, bn, &o) != GDK_SUCCEED)
     258           0 :                                         goto bunins_failed;
     259             :                                 /* enter into hash table */
     260       74221 :                                 HASHputlink(hs, p, HASHget(hs, prb));
     261       74191 :                                 HASHput(hs, prb, p);
     262             :                         }
     263             :                 }
     264         185 :                 HEAPfree(&hs->heaplink, true);
     265         185 :                 HEAPfree(&hs->heapbckt, true);
     266         185 :                 GDKfree(hs);
     267             :         }
     268         332 :         bat_iterator_end(&bi);
     269             : 
     270         332 :         bn->theap->dirty = true;
     271         332 :         bn->tsorted = true;
     272         332 :         bn->trevsorted = BATcount(bn) <= 1;
     273         332 :         bn->tkey = true;
     274         332 :         bn->tnil = false;
     275         332 :         bn->tnonil = true;
     276         332 :         if (BATcount(bn) == BATcount(b)) {
     277             :                 /* it turns out all values are distinct */
     278         105 :                 assert(b->tnokey[0] == 0);
     279         105 :                 assert(b->tnokey[1] == 0);
     280         105 :                 b->tkey = true;
     281         105 :                 b->batDirtydesc = true;
     282             :         }
     283         332 :         bn = virtualize(bn);
     284         332 :         MT_thread_setalgorithm(algomsg);
     285         332 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT
     286             :                   ",s=" ALGOOPTBATFMT " -> " ALGOOPTBATFMT
     287             :                   " (%s -- " LLFMT "usec)\n",
     288             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
     289             :                   ALGOOPTBATPAR(bn), algomsg, GDKusec() - t0);
     290             :         return bn;
     291             : 
     292           0 :   bunins_failed:
     293           0 :         bat_iterator_end(&bi);
     294           0 :         if (seen)
     295           0 :                 GDKfree(seen);
     296           0 :         if (hs != NULL) {
     297           0 :                 HEAPfree(&hs->heaplink, true);
     298           0 :                 HEAPfree(&hs->heapbckt, true);
     299           0 :                 GDKfree(hs);
     300             :         }
     301           0 :         BBPreclaim(bn);
     302           0 :         return NULL;
     303             : }

Generated by: LCOV version 1.14