23 #define CONCAT_1(a, b) a##b
24 #define CONCAT(a, b) CONCAT_1(a, b)
29 #define CONCAT3(a, b, c) CONCAT(a, CONCAT(b, c))
32 #if !(defined(UINT_T) && defined(UINT_C) && defined(UINT_FMT_S) && defined(DECORATE_NAME))
33 #ifdef __INTELLISENSE__
34 #define UINT_T uint32_t
35 #define UINT_C UINT32_C
36 #define UINT_FMT_S PRIu32
37 #define DECORATE_NAME(Name) Name##_u32
39 #error All of UINT_T, UINT_C, UINT_FMT_S, UINT_FMT_ARG, and DECORATE_NAME must be defined before #including this file
43 #define BITS (sizeof(UINT_T) * CHAR_BIT)
45 #define ZERO UINT_C(0)
49 #define UINT_FMT_ARG(X) X
54 #define UINT_LESSTHAN(A, B) ((A) < (B))
58 #define MC_UINT_MAX ~(UINT_C(0))
63 #define UINT_ADD(A, B) ((A) + (B))
66 #define UINT_SUB(A, B) ((A) - (B))
71 static inline UINT_T
DECORATE_NAME(_mc_default_lshift)(UINT_T lhs,
int off) {
79 #define UINT_LSHIFT DECORATE_NAME(_mc_default_lshift)
83 #define UINT_BITOR(A, B) ((A) | (B))
86 static inline int DECORATE_NAME(_mc_compare)(UINT_T lhs, UINT_T rhs) {
87 if (UINT_LESSTHAN(lhs, rhs)) {
89 }
else if (UINT_LESSTHAN(rhs, lhs)) {
96 #define UINT_COMPARE DECORATE_NAME(_mc_compare)
104 uint32_t _trimFactor;
116 BSON_ASSERT_PARAM(status);
118 if (UINT_COMPARE(rangeMin, rangeMax) > 0) {
119 CLIENT_ERR(
"Range min (%" UINT_FMT_S
") must be less than or equal to range max (%" UINT_FMT_S
120 ") for range search",
121 UINT_FMT_ARG(rangeMin),
122 UINT_FMT_ARG(rangeMax));
125 if (UINT_COMPARE(rangeMax, max) > 0) {
126 CLIENT_ERR(
"Range max (%" UINT_FMT_S
") must be less than or equal to max (%" UINT_FMT_S
") for range search",
127 UINT_FMT_ARG(rangeMax),
133 CLIENT_ERR(
"Sparsity must be > 0");
136 size_t maxlen = (size_t)BITS -
DECORATE_NAME(mc_count_leading_zeros)(max);
137 if (trimFactor != 0 && trimFactor >= maxlen) {
138 CLIENT_ERR(
"Trim factor must be less than the number of bits (%zu) used to represent an element of the domain",
143 mcg->_rangeMin = rangeMin;
144 mcg->_rangeMax = rangeMax;
145 mcg->_maxlen = (size_t)BITS -
DECORATE_NAME(mc_count_leading_zeros)(max);
146 mcg->_sparsity = sparsity;
147 mcg->_trimFactor = trimFactor;
157 static inline UINT_T
DECORATE_NAME(applyMask)(UINT_T value,
size_t maskedBits) {
158 const UINT_T ones = MC_UINT_MAX;
160 BSON_ASSERT(maskedBits <= (
size_t)BITS);
161 BSON_ASSERT(maskedBits >= 0);
163 if (maskedBits == 0) {
167 const size_t shift = ((size_t)BITS - maskedBits);
168 const UINT_T mask = UINT_LSHIFT(ones, -(
int)shift);
169 return UINT_BITOR(value, mask);
174 BSON_ASSERT_PARAM(mcg);
175 size_t level = mcg->_maxlen - maskedBits;
176 return 0 == maskedBits || (level >= mcg->_trimFactor && 0 == (level % mcg->_sparsity));
181 BSON_ASSERT_PARAM(mcg);
182 BSON_ASSERT(maskedBits <= mcg->_maxlen);
183 BSON_ASSERT(maskedBits <= (
size_t)BITS);
184 BSON_ASSERT(maskedBits >= 0);
186 if (maskedBits == mcg->_maxlen) {
187 return bson_strdup(
"root");
190 UINT_T shifted = UINT_LSHIFT(start, -(
int)maskedBits);
191 mc_bitstring valueBin =
DECORATE_NAME(mc_convert_to_bitstring)(shifted);
192 char *ret = bson_strndup(valueBin.str + ((
size_t)BITS - mcg->_maxlen + maskedBits), mcg->_maxlen + maskedBits);
200 BSON_ASSERT_PARAM(mcg);
201 BSON_ASSERT_PARAM(c);
202 const UINT_T blockEnd =
DECORATE_NAME(applyMask)(blockStart, maskedBits);
204 if (UINT_COMPARE(blockEnd, mcg->_rangeMin) < 0 || UINT_COMPARE(blockStart, mcg->_rangeMax) > 0) {
208 if (UINT_COMPARE(blockStart, mcg->_rangeMin) >= 0 && UINT_COMPARE(blockEnd, mcg->_rangeMax) <= 0
209 &&
DECORATE_NAME(MinCoverGenerator_isLevelStored)(mcg, maskedBits)) {
210 char *edge =
DECORATE_NAME(MinCoverGenerator_toString)(mcg, blockStart, maskedBits);
211 _mc_array_append_val(c, edge);
215 BSON_ASSERT(maskedBits > 0);
217 const size_t newBits = maskedBits - 1u;
218 DECORATE_NAME(MinCoverGenerator_minCoverRec)(mcg, c, blockStart, newBits);
220 (mcg, c, UINT_BITOR(blockStart, UINT_LSHIFT(UINT_C(1), (
int)newBits)), newBits);
224 BSON_ASSERT_PARAM(mcg);
225 mc_mincover_t *mc = mc_mincover_new();
227 (mcg, &mc->mincover, ZERO, mcg->_maxlen);
236 bool includeLowerBound,
239 bool includeUpperBound,
242 BSON_ASSERT_PARAM(lowerBound);
243 BSON_ASSERT_PARAM(upperBound);
245 if (!includeLowerBound) {
246 if (UINT_COMPARE(*lowerBound, max) >= 0) {
247 CLIENT_ERR(
"Lower bound (%" UINT_FMT_S
") must be less than the range maximum (%" UINT_FMT_S
248 ") if lower bound is excluded from range.",
249 UINT_FMT_ARG(*lowerBound),
253 *lowerBound = UINT_ADD(*lowerBound, UINT_C(1));
255 if (!includeUpperBound) {
256 if (UINT_COMPARE(*upperBound, min) <= 0) {
257 CLIENT_ERR(
"Upper bound (%" UINT_FMT_S
") must be greater than the range minimum (%" UINT_FMT_S
258 ") if upper bound is excluded from range.",
259 UINT_FMT_ARG(*upperBound),
263 *upperBound = UINT_SUB(*upperBound, UINT_C(1));
struct _mongocrypt_status_t mongocrypt_status_t
Definition: mongocrypt.h:152
Definition: mc-range-mincover-generator.template.h:100