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 : __attribute__((__const__))
82 : static inline int
83 5660437 : candmask_lobit(uint32_t x)
84 : {
85 5660437 : assert(x != 0);
86 : #ifdef __has_builtin
87 : #if __has_builtin(__builtin_ctz)
88 5660437 : return __builtin_ctz(x) /* ffs(x) - 1 */;
89 : #define BUILTIN_USED
90 : #endif
91 : #endif
92 : #ifndef BUILTIN_USED
93 : #if defined(_MSC_VER)
94 : unsigned long idx;
95 : if (_BitScanForward(&idx, x))
96 : return (int) idx;
97 : return -1;
98 : #else
99 : /* use binary search for the lowest set bit */
100 : int n = 1;
101 : if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
102 : if ((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
103 : if ((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
104 : if ((x & 0x00000003) == 0) { n += 2; x >>= 2; }
105 : return n - (x & 1);
106 : #endif
107 : #endif
108 : #undef BUILTIN_USED
109 : }
110 :
111 : /* population count: count number of 1 bits in a value */
112 : __attribute__((__const__))
113 : static inline uint32_t
114 198162521 : candmask_pop(uint32_t x)
115 : {
116 : #ifdef __has_builtin
117 : #if __has_builtin(__builtin_popcount)
118 198162521 : return (uint32_t) __builtin_popcount(x);
119 : #define BUILTIN_USED
120 : #endif
121 : #endif
122 : #ifndef BUILTIN_USED
123 : #if defined(_MSC_VER)
124 : return (uint32_t) __popcnt((unsigned int) (x));
125 : #else
126 : /* divide and conquer implementation (the two versions are
127 : * essentially equivalent, but the first version is written a
128 : * bit smarter) */
129 : #if 1
130 : x -= (x >> 1) & ~0U/3 /* 0x55555555 */; /* 3-1=2; 2-1=1; 1-0=1; 0-0=0 */
131 : x = (x & ~0U/5) + ((x >> 2) & ~0U/5) /* 0x33333333 */;
132 : x = (x + (x >> 4)) & ~0UL/0x11 /* 0x0F0F0F0F */;
133 : x = (x + (x >> 8)) & ~0UL/0x101 /* 0x00FF00FF */;
134 : x = (x + (x >> 16)) & 0xFFFF /* ~0UL/0x10001 */;
135 : #else
136 : x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
137 : x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
138 : x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
139 : x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
140 : x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
141 : #endif
142 : return x;
143 : #endif
144 : #endif
145 : #undef BUILTIN_USED
146 : }
147 :
148 : #define canditer_next_dense(ci) ((ci)->seq + (ci)->next++)
149 : static inline oid
150 1615469534 : canditer_next(struct canditer *ci)
151 : {
152 1615469534 : oid o;
153 1615469534 : if (ci->next == ci->ncand)
154 62658 : return oid_nil;
155 1615406876 : switch (ci->tpe) {
156 1010114715 : case cand_dense:
157 1010114715 : return canditer_next_dense(ci);
158 296811211 : case cand_materialized:
159 296811211 : assert(ci->next < ci->nvals);
160 296811211 : return ci->oids[ci->next++];
161 303000644 : case cand_except:
162 303000644 : o = ci->seq + ci->add + ci->next++;
163 349070657 : while (ci->add < ci->nvals && o == ci->oids[ci->add]) {
164 46070013 : ci->add++;
165 46070013 : o++;
166 : }
167 : return o;
168 : case cand_mask:
169 5635102 : while ((ci->mask[ci->nextmsk] >> ci->nextbit) == 0) {
170 154796 : ci->nextmsk++;
171 154796 : ci->nextbit = 0;
172 : }
173 5480306 : ci->nextbit += candmask_lobit(ci->mask[ci->nextmsk] >> ci->nextbit);
174 5480306 : o = ci->mskoff + ci->nextmsk * 32 + ci->nextbit;
175 5480306 : if (++ci->nextbit == 32) {
176 193415 : ci->nextbit = 0;
177 193415 : ci->nextmsk++;
178 : }
179 5480306 : ci->next++;
180 5480306 : return o;
181 : default:
182 0 : MT_UNREACHABLE();
183 : }
184 : }
185 :
186 : gdk_export void canditer_init(struct canditer *ci, BAT *b, BAT *s)
187 : __attribute__((__access__(write_only, 1)));
188 : gdk_export oid canditer_peek(const struct canditer *ci)
189 : __attribute__((__pure__));
190 : gdk_export oid canditer_last(const struct canditer *ci)
191 : __attribute__((__pure__));
192 : gdk_export oid canditer_prev(struct canditer *ci);
193 : gdk_export oid canditer_peekprev(const struct canditer *ci)
194 : __attribute__((__pure__));
195 : gdk_export oid canditer_idx(const struct canditer *ci, BUN p)
196 : __attribute__((__pure__));
197 : #define canditer_idx_dense(ci, p) ((p >= (ci)->ncand)?oid_nil:((ci)->seq + p))
198 : gdk_export void canditer_setidx(struct canditer *ci, BUN p);
199 : gdk_export void canditer_reset(struct canditer *ci);
200 :
201 : __attribute__((__pure__))
202 : static inline BUN
203 297481405 : canditer_search_dense(const struct canditer *ci, oid o, bool next)
204 : {
205 297481405 : if (o < ci->seq)
206 : return next ? 0 : BUN_NONE;
207 297387490 : else if (o >= ci->seq + ci->ncand)
208 : return next ? ci->ncand : BUN_NONE;
209 : else
210 297977616 : return o - ci->seq;
211 : }
212 : gdk_export BUN canditer_search(const struct canditer *ci, oid o, bool next)
213 : __attribute__((__pure__));
214 :
215 : __attribute__((__pure__))
216 : static inline bool
217 81340 : canditer_contains(const struct canditer *ci, oid o)
218 : {
219 81340 : if (ci->tpe == cand_mask) {
220 490 : if (o < ci->mskoff)
221 : return false;
222 490 : o -= ci->mskoff;
223 490 : BUN p = o / 32;
224 490 : if (p >= ci->nvals)
225 : return false;
226 490 : o %= 32;
227 490 : if (p == ci->nvals - 1 && o >= ci->lastbit)
228 : return false;
229 490 : return ci->mask[p] & (1U << o);
230 : }
231 80850 : return canditer_search(ci, o, false) != BUN_NONE;
232 : }
233 : gdk_export oid canditer_mask_next(const struct canditer *ci, oid o, bool next)
234 : __attribute__((__pure__));
235 :
236 : gdk_export BAT *canditer_slice(const struct canditer *ci, BUN lo, BUN hi);
237 : gdk_export BAT *canditer_sliceval(const struct canditer *ci, oid lo, oid hi);
238 : gdk_export BAT *canditer_slice2(const struct canditer *ci, BUN lo1, BUN hi1, BUN lo2, BUN hi2);
239 : gdk_export BAT *canditer_slice2val(const struct canditer *ci, oid lo1, oid hi1, oid lo2, oid hi2);
240 :
241 : gdk_export BAT *BATnegcands(oid tseq, BUN nr, BAT *odels);
242 : gdk_export BAT *BATmaskedcands(oid hseq, BUN nr, BAT *masked, bool selected);
243 : gdk_export BAT *BATunmask(BAT *b);
244 :
245 : gdk_export BAT *BATmergecand(BAT *a, BAT *b);
246 : gdk_export BAT *BATintersectcand(BAT *a, BAT *b);
247 : gdk_export BAT *BATdiffcand(BAT *a, BAT *b);
248 :
249 : #endif /* _GDK_CAND_H_ */
|
