Line data    Source code

       1             : /*
       2             :  * SPDX-License-Identifier: MPL-2.0
       3             :  *
       4             :  * This Source Code Form is subject to the terms of the Mozilla Public
       5             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       6             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       7             :  *
       8             :  * Copyright 2024 MonetDB Foundation;
       9             :  * Copyright August 2008 - 2023 MonetDB B.V.;
      10             :  * Copyright 1997 - July 2008 CWI.
      11             :  */
      12             : 
      13             : #ifndef _GDK_CAND_H_
      14             : #define _GDK_CAND_H_
      15             : 
      16             : /* candidates by design are ordered oid lists, besides native oid bats
      17             :  * there are
      18             :  *      void bats for dense oid lists,
      19             :  *      negative oid lists
      20             :  *      masked oid lists
      21             :  */
      22             : 
      23             : #define CAND_NEGOID 0
      24             : #define CAND_MSK 1
      25             : 
      26             : typedef struct {
      27             :         uint64_t
      28             :                 type:1,
      29             : //              mask:1,
      30             :                 firstbit:48;
      31             : } ccand_t;
      32             : 
      33             : #define CCAND(b)        ((ccand_t *) (b)->tvheap->base)
      34             : #define complex_cand(b) ((b)->ttype == TYPE_void && (b)->tvheap != NULL)
      35             : #define negoid_cand(b)  (complex_cand(b) && CCAND(b)->type == CAND_NEGOID)
      36             : #define mask_cand(b)    (complex_cand(b) && CCAND(b)->type == CAND_MSK)
      37             : #define ccand_first(b)  ((b)->tvheap->base + sizeof(ccand_t))
      38             : #define ccand_free(b)   ((b)->tvheap->free - sizeof(ccand_t))
      39             : 
      40             : enum cand_type {
      41             :         cand_dense,     /* simple dense BAT, i.e. no look ups */
      42             :         cand_materialized, /* simple materialized OID list */
      43             :         cand_except,    /* list of exceptions in vheap */
      44             :         cand_mask,      /* bitmask (TYPE_msk) bat as candidate list */
      45             : };
      46             : 
      47             : struct canditer {
      48             :         BAT *s;                 /* candidate BAT the iterator is based on */
      49             :         union {
      50             :                 struct {        /* for all except cand_mask */
      51             :                         const oid *oids; /* candidate or exceptions for non-dense */
      52             :                         BUN offset;     /* how much of candidate list BAT we skipped */
      53             :                         oid add;        /* value to add because of exceptions seen */
      54             :                 };
      55             :                 struct {        /* only for cand_mask */
      56             :                         const uint32_t *mask; /* bitmask */
      57             :                         BUN nextmsk;
      58             :                         oid mskoff;
      59             :                         uint8_t nextbit;
      60             :                         uint8_t firstbit;
      61             :                         uint8_t lastbit;
      62             :                 };
      63             :         };
      64             :         oid seq;                /* first candidate */
      65             :         oid hseq;               /* hseqbase from s/b for first candidate */
      66             :         BUN nvals;              /* number of values in .oids/.mask */
      67             :         BUN ncand;              /* number of candidates */
      68             :         BUN next;               /* next BUN to return value for */
      69             :         enum cand_type tpe;
      70             : };
      71             : 
      72             : /* iterate CI->ncand times using an anonymous index variable, and
      73             :  * evaluating the loop count only once */
      74             : #define CAND_LOOP(CI)   for (BUN CCTR = 0, CREPS = (CI)->ncand; CCTR < CREPS; CCTR++)
      75             : /* iterate CI->ncand times using the given index variable, and
      76             :  * evaluating the loop count only once */
      77             : #define CAND_LOOP_IDX(CI, IDX)  for (BUN CREPS = (IDX = 0, (CI)->ncand); IDX < CREPS; IDX++)
      78             : 
      79             : /* returns the position of the lowest order bit in x, i.e. the
      80             :  * smallest n such that (x & (1<<n)) != 0; must not be called with 0 */
      81             : static inline int __attribute__((__const__))
      82    34176530 : candmask_lobit(uint32_t x)
      83             : {
      84    34176530 :         assert(x != 0);
      85             : #if defined(__GNUC__)
      86    34176530 :         return __builtin_ctz(x) /* ffs(x) - 1 */;
      87             : #elif defined(_MSC_VER)
      88             :         unsigned long idx;
      89             :         if (_BitScanForward(&idx, x))
      90             :                 return (int) idx;
      91             :         return -1;
      92             : #else
      93             :         /* use binary search for the lowest set bit */
      94             :         int n = 1;
      95             :         if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
      96             :         if ((x & 0x000000FF) == 0) { n +=  8; x >>=  8; }
      97             :         if ((x & 0x0000000F) == 0) { n +=  4; x >>=  4; }
      98             :         if ((x & 0x00000003) == 0) { n +=  2; x >>=  2; }
      99             :         return n - (x & 1);
     100             : #endif
     101             : }
     102             : 
     103             : /* population count: count number of 1 bits in a value */
     104             : static inline uint32_t __attribute__((__const__))
     105    83045122 : candmask_pop(uint32_t x)
     106             : {
     107             : #if defined(__GNUC__)
     108    83045122 :         return (uint32_t) __builtin_popcount(x);
     109             : #elif defined(_MSC_VER)
     110             :         return (uint32_t) __popcnt((unsigned int) (x));
     111             : #else
     112             :         /* divide and conquer implementation (the two versions are
     113             :          * essentially equivalent, but the first version is written a
     114             :          * bit smarter) */
     115             : #if 1
     116             :         x -= (x >> 1) & ~0U/3 /* 0x55555555 */; /* 3-1=2; 2-1=1; 1-0=1; 0-0=0 */
     117             :         x = (x & ~0U/5) + ((x >> 2) & ~0U/5) /* 0x33333333 */;
     118             :         x = (x + (x >> 4)) & ~0UL/0x11 /* 0x0F0F0F0F */;
     119             :         x = (x + (x >> 8)) & ~0UL/0x101 /* 0x00FF00FF */;
     120             :         x = (x + (x >> 16)) & 0xFFFF /* ~0UL/0x10001 */;
     121             : #else
     122             :         x = (x & 0x55555555) + ((x >>  1) & 0x55555555);
     123             :         x = (x & 0x33333333) + ((x >>  2) & 0x33333333);
     124             :         x = (x & 0x0F0F0F0F) + ((x >>  4) & 0x0F0F0F0F);
     125             :         x = (x & 0x00FF00FF) + ((x >>  8) & 0x00FF00FF);
     126             :         x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
     127             : #endif
     128             :         return x;
     129             : #endif
     130             : }
     131             : 
     132             : #define canditer_next_dense(ci)         ((ci)->seq + (ci)->next++)
     133             : #define canditer_next_mater(ci)         ((ci)->oids[(ci)->next++])
     134             : static inline oid
     135   156828392 : canditer_next_except(struct canditer *ci)
     136             : {
     137   156828392 :         oid o = ci->seq + ci->add + ci->next++;
     138   196168033 :         while (ci->add < ci->nvals && o == ci->oids[ci->add]) {
     139    39339641 :                 ci->add++;
     140    39339641 :                 o++;
     141             :         }
     142   156828392 :         return o;
     143             : }
     144             : static inline oid
     145    34073520 : canditer_next_mask(struct canditer *ci)
     146             : {
     147             :         /* since .next < .ncand, we know there must be another
     148             :          * candidate */
     149    34105231 :         while ((ci->mask[ci->nextmsk] >> ci->nextbit) == 0) {
     150       31711 :                 ci->nextmsk++;
     151       31711 :                 ci->nextbit = 0;
     152             :         }
     153    34073520 :         ci->nextbit += candmask_lobit(ci->mask[ci->nextmsk] >> ci->nextbit);
     154    34073520 :         oid o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
     155    34073520 :         if (++ci->nextbit == 32) {
     156     1094329 :                 ci->nextbit = 0;
     157     1094329 :                 ci->nextmsk++;
     158             :         }
     159    34073520 :         ci->next++;
     160    34073520 :         return o;
     161             : }
     162             : 
     163             : static inline oid
     164  1603749885 : canditer_next(struct canditer *ci)
     165             : {
     166  1603749885 :         if (ci->next == ci->ncand)
     167       61838 :                 return oid_nil;
     168  1603688047 :         switch (ci->tpe) {
     169   899108942 :         case cand_dense:
     170   899108942 :                 return canditer_next_dense(ci);
     171   513677308 :         case cand_materialized:
     172   513677308 :                 assert(ci->next < ci->nvals);
     173   513677308 :                 return canditer_next_mater(ci);
     174   156828392 :         case cand_except:
     175   156828392 :                 return canditer_next_except(ci);
     176    34073405 :         case cand_mask:
     177    34073405 :                 return canditer_next_mask(ci);
     178             :         default:
     179           0 :                 MT_UNREACHABLE();
     180             :         }
     181             : }
     182             : 
     183             : #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)
     184             : 
     185             : gdk_export void canditer_init(struct canditer *ci, BAT *b, BAT *s);
     186             : gdk_export oid canditer_peek(struct canditer *ci);
     187             : gdk_export oid canditer_last(const struct canditer *ci);
     188             : gdk_export oid canditer_prev(struct canditer *ci);
     189             : gdk_export oid canditer_peekprev(struct canditer *ci);
     190             : gdk_export oid canditer_idx(const struct canditer *ci, BUN p);
     191             : #define canditer_idx_dense(ci, p) ((p >= (ci)->ncand)?oid_nil:((ci)->seq + p))
     192             : gdk_export void canditer_setidx(struct canditer *ci, BUN p);
     193             : gdk_export void canditer_reset(struct canditer *ci);
     194             : gdk_export BUN canditer_search(const struct canditer *ci, oid o, bool next);
     195             : static inline bool
     196      228021 : canditer_contains(struct canditer *ci, oid o)
     197             : {
     198      228021 :         if (ci->tpe == cand_mask) {
     199      145665 :                 if (o < ci->mskoff)
     200             :                         return false;
     201      145665 :                 o -= ci->mskoff;
     202      145665 :                 BUN p = o / 32;
     203      145665 :                 if (p >= ci->nvals)
     204             :                         return false;
     205      145665 :                 o %= 32;
     206      145665 :                 if (p == ci->nvals - 1 && o >= ci->lastbit)
     207             :                         return false;
     208      145665 :                 return ci->mask[p] & (1U << o);
     209             :         }
     210       82356 :         return canditer_search(ci, o, false) != BUN_NONE;
     211             : }
     212             : gdk_export oid canditer_mask_next(const struct canditer *ci, oid o, bool next);
     213             : gdk_export BAT *canditer_slice(const struct canditer *ci, BUN lo, BUN hi);
     214             : gdk_export BAT *canditer_sliceval(const struct canditer *ci, oid lo, oid hi);
     215             : gdk_export BAT *canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2);
     216             : gdk_export BAT *canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2);
     217             : gdk_export BAT *BATnegcands(BUN nr, BAT *odels);
     218             : gdk_export BAT *BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected);
     219             : gdk_export BAT *BATunmask(BAT *b);
     220             : 
     221             : gdk_export BAT *BATmergecand(BAT *a, BAT *b);
     222             : gdk_export BAT *BATintersectcand(BAT *a, BAT *b);
     223             : gdk_export BAT *BATdiffcand(BAT *a, BAT *b);
     224             : 
     225             : #endif  /* _GDK_CAND_H_ */