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