LCOV - code coverage report
Current view: top level - gdk - gdk_cand.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 44 44 100.0 %
Date: 2021-09-14 19:48:19 Functions: 5 5 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             : #ifndef _GDK_CAND_H_
      10             : #define _GDK_CAND_H_
      11             : 
      12             : /* candidates by design are ordered oid lists, besides native oid bats
      13             :  * there are
      14             :  *      void bats for dense oid lists,
      15             :  *      negative oid lists
      16             :  *      masked oid lists
      17             :  */
      18             : 
      19             : #define CAND_NEGOID 0
      20             : #define CAND_MSK 1
      21             : 
      22             : typedef struct {
      23             :         uint64_t
      24             :                 type:1,
      25             : //              mask:1,
      26             :                 firstbit:48;
      27             : } ccand_t;
      28             : 
      29             : #define CCAND(b)        ((ccand_t *) (b)->tvheap->base)
      30             : #define complex_cand(b) ((b)->ttype == TYPE_void && (b)->tvheap != NULL)
      31             : #define negoid_cand(b)  (complex_cand(b) && CCAND(b)->type == CAND_NEGOID)
      32             : #define mask_cand(b)    (complex_cand(b) && CCAND(b)->type == CAND_MSK)
      33             : #define ccand_first(b)  ((b)->tvheap->base + sizeof(ccand_t))
      34             : #define ccand_free(b)   ((b)->tvheap->free - sizeof(ccand_t))
      35             : 
      36             : struct canditer {
      37             :         BAT *s;                 /* candidate BAT the iterator is based on */
      38             :         union {
      39             :                 struct {        /* for all except cand_mask */
      40             :                         const oid *oids; /* candidate or exceptions for non-dense */
      41             :                         BUN offset;     /* how much of candidate list BAT we skipped */
      42             :                         oid add;        /* value to add because of exceptions seen */
      43             :                 };
      44             :                 struct {        /* only for cand_mask */
      45             :                         const uint32_t *mask; /* bitmask */
      46             :                         BUN nextmsk;
      47             :                         oid mskoff;
      48             :                         uint8_t nextbit;
      49             :                         uint8_t firstbit;
      50             :                         uint8_t lastbit;
      51             :                 };
      52             :         };
      53             :         oid seq;                /* first candidate */
      54             :         oid hseq;               /* hseqbase from s/b for first candidate */
      55             :         BUN nvals;              /* number of values in .oids/.mask */
      56             :         BUN ncand;              /* number of candidates */
      57             :         BUN next;               /* next BUN to return value for */
      58             :         enum {
      59             :                 cand_dense,     /* simple dense BAT, i.e. no look ups */
      60             :                 cand_materialized, /* simple materialized OID list */
      61             :                 cand_except,    /* list of exceptions in vheap */
      62             :                 cand_mask,      /* bitmask (TYPE_msk) bat as candidate list */
      63             :         } tpe;
      64             : };
      65             : 
      66             : /* returns the position of the lowest order bit in x, i.e. the
      67             :  * smallest n such that (x & (1<<n)) != 0; must not be called with 0 */
      68             : static inline int __attribute__((__const__))
      69     6895310 : candmask_lobit(uint32_t x)
      70             : {
      71     6895310 :         assert(x != 0);
      72             : #if defined(__GNUC__)
      73     6895310 :         return __builtin_ctz(x) /* ffs(x) - 1 */;
      74             : #elif defined(_MSC_VER)
      75             :         unsigned long idx;
      76             :         if (_BitScanForward(&idx, x))
      77             :                 return (int) idx;
      78             :         return -1;
      79             : #else
      80             :         /* use binary search for the lowest set bit */
      81             :         int n = 1;
      82             :         if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
      83             :         if ((x & 0x000000FF) == 0) { n +=  8; x >>=  8; }
      84             :         if ((x & 0x0000000F) == 0) { n +=  4; x >>=  4; }
      85             :         if ((x & 0x00000003) == 0) { n +=  2; x >>=  2; }
      86             :         return n - (x & 1);
      87             : #endif
      88             : }
      89             : 
      90             : /* population count: count number of 1 bits in a value */
      91             : static inline uint32_t __attribute__((__const__))
      92             : candmask_pop(uint32_t x)
      93             : {
      94             : #if defined(__GNUC__)
      95    15240989 :         return (uint32_t) __builtin_popcount(x);
      96             : #elif defined(_MSC_VER)
      97             :         return (uint32_t) __popcnt((unsigned int) (x));
      98             : #else
      99             :         /* divide and conquer implementation (the two versions are
     100             :          * essentially equivalent, but the first version is written a
     101             :          * bit smarter) */
     102             : #if 1
     103             :         x -= (x >> 1) & ~0U/3 /* 0x55555555 */; /* 3-1=2; 2-1=1; 1-0=1; 0-0=0 */
     104             :         x = (x & ~0U/5) + ((x >> 2) & ~0U/5) /* 0x33333333 */;
     105             :         x = (x + (x >> 4)) & ~0UL/0x11 /* 0x0F0F0F0F */;
     106             :         x = (x + (x >> 8)) & ~0UL/0x101 /* 0x00FF00FF */;
     107             :         x = (x + (x >> 16)) & 0xFFFF /* ~0UL/0x10001 */;
     108             : #else
     109             :         x = (x & 0x55555555) + ((x >>  1) & 0x55555555);
     110             :         x = (x & 0x33333333) + ((x >>  2) & 0x33333333);
     111             :         x = (x & 0x0F0F0F0F) + ((x >>  4) & 0x0F0F0F0F);
     112             :         x = (x & 0x00FF00FF) + ((x >>  8) & 0x00FF00FF);
     113             :         x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
     114             : #endif
     115             :         return x;
     116             : #endif
     117             : }
     118             : 
     119             : #define canditer_next_dense(ci)         ((ci)->seq + (ci)->next++)
     120             : #define canditer_next_mater(ci)         ((ci)->oids[(ci)->next++])
     121             : static inline oid
     122      277229 : canditer_next_except(struct canditer *ci)
     123             : {
     124      277229 :         oid o = ci->seq + ci->add + ci->next++;
     125      333399 :         while (ci->add < ci->nvals && o == ci->oids[ci->add]) {
     126       56170 :                 ci->add++;
     127       56170 :                 o++;
     128             :         }
     129      277229 :         return o;
     130             : }
     131             : static inline oid
     132     6647020 : canditer_next_mask(struct canditer *ci)
     133             : {
     134             :         /* since .next < .ncand, we know there must be another
     135             :          * candidate */
     136     6697872 :         while ((ci->mask[ci->nextmsk] >> ci->nextbit) == 0) {
     137       50852 :                 ci->nextmsk++;
     138       50852 :                 ci->nextbit = 0;
     139             :         }
     140     6647020 :         ci->nextbit += candmask_lobit(ci->mask[ci->nextmsk] >> ci->nextbit);
     141     6647020 :         oid o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
     142     6647020 :         if (++ci->nextbit == 32) {
     143      201387 :                 ci->nextbit = 0;
     144      201387 :                 ci->nextmsk++;
     145             :         }
     146     6647020 :         ci->next++;
     147     6647020 :         return o;
     148             : }
     149             : 
     150             : static inline oid
     151   806536841 : canditer_next(struct canditer *ci)
     152             : {
     153   806536841 :         if (ci->next == ci->ncand)
     154       75620 :                 return oid_nil;
     155   806461221 :         switch (ci->tpe) {
     156   658064485 :         case cand_dense:
     157   658064485 :                 return canditer_next_dense(ci);
     158   141468450 :         case cand_materialized:
     159   141468450 :                 assert(ci->next < ci->nvals);
     160   141468450 :                 return canditer_next_mater(ci);
     161      277192 :         case cand_except:
     162      277192 :                 return canditer_next_except(ci);
     163             :         case cand_mask:
     164             :                 /* work around compiler error: control reaches end of
     165             :                  * non-void function */
     166             :                 break;
     167             :         }
     168     6651094 :         assert(ci->tpe == cand_mask);
     169     6651094 :         return canditer_next_mask(ci);
     170             : }
     171             : 
     172             : #define canditer_search_dense(ci, o, next) ((o) < (ci)->seq ? next ? 0 : BUN_NONE : (o) >= (ci)->seq + (ci)->ncand ? next ? (ci)->ncand : BUN_NONE : (o) - (ci)->seq)
     173             : 
     174             : gdk_export BUN canditer_init(struct canditer *ci, BAT *b, BAT *s);
     175             : gdk_export oid canditer_peek(struct canditer *ci);
     176             : gdk_export oid canditer_last(const struct canditer *ci);
     177             : gdk_export oid canditer_prev(struct canditer *ci);
     178             : gdk_export oid canditer_peekprev(struct canditer *ci);
     179             : gdk_export oid canditer_idx(const struct canditer *ci, BUN p);
     180             : #define canditer_idx_dense(ci, p) ((p >= (ci)->ncand)?oid_nil:((ci)->seq + p))
     181             : gdk_export void canditer_setidx(struct canditer *ci, BUN p);
     182             : gdk_export void canditer_reset(struct canditer *ci);
     183             : gdk_export BUN canditer_search(const struct canditer *ci, oid o, bool next);
     184             : static inline bool
     185     3655903 : canditer_contains(struct canditer *ci, oid o)
     186             : {
     187     3655903 :         if (ci->tpe == cand_mask) {
     188      345688 :                 if (o < ci->mskoff)
     189             :                         return false;
     190      345688 :                 o -= ci->mskoff;
     191      345688 :                 BUN p = o / 32;
     192      345688 :                 if (p >= ci->nvals)
     193             :                         return false;
     194      345688 :                 o %= 32;
     195      345688 :                 if (p == ci->nvals - 1 && o >= ci->lastbit)
     196             :                         return false;
     197      345688 :                 return ci->mask[p] & (1U << o);
     198             :         }
     199     3310215 :         return canditer_search(ci, o, false) != BUN_NONE;
     200             : }
     201             : gdk_export oid canditer_mask_next(const struct canditer *ci, oid o, bool next);
     202             : gdk_export BAT *canditer_slice(const struct canditer *ci, BUN lo, BUN hi);
     203             : gdk_export BAT *canditer_sliceval(const struct canditer *ci, oid lo, oid hi);
     204             : gdk_export BAT *canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2);
     205             : gdk_export BAT *canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2);
     206             : gdk_export BAT *BATnegcands(BUN nr, BAT *odels);
     207             : gdk_export BAT *BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected);
     208             : gdk_export BAT *BATunmask(BAT *b);
     209             : 
     210             : gdk_export BAT *BATmergecand(BAT *a, BAT *b);
     211             : gdk_export BAT *BATintersectcand(BAT *a, BAT *b);
     212             : gdk_export BAT *BATdiffcand(BAT *a, BAT *b);
     213             : 
     214             : #endif  /* _GDK_CAND_H_ */

Generated by: LCOV version 1.14