1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
|
#include <roaring/containers/containers.h>
#include <roaring/memory.h>
#ifdef __cplusplus
extern "C" { namespace roaring { namespace internal {
#endif
extern inline const container_t *container_unwrap_shared(
const container_t *candidate_shared_container, uint8_t *type);
extern inline container_t *container_mutable_unwrap_shared(
container_t *candidate_shared_container, uint8_t *type);
extern inline int container_get_cardinality(
const container_t *c, uint8_t typecode);
extern inline container_t *container_iand(
container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_ior(
container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_ixor(
container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_iandnot(
container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
void container_free(container_t *c, uint8_t type) {
switch (type) {
case BITSET_CONTAINER_TYPE:
bitset_container_free(CAST_bitset(c));
break;
case ARRAY_CONTAINER_TYPE:
array_container_free(CAST_array(c));
break;
case RUN_CONTAINER_TYPE:
run_container_free(CAST_run(c));
break;
case SHARED_CONTAINER_TYPE:
shared_container_free(CAST_shared(c));
break;
default:
assert(false);
roaring_unreachable;
}
}
void container_printf(const container_t *c, uint8_t type) {
c = container_unwrap_shared(c, &type);
switch (type) {
case BITSET_CONTAINER_TYPE:
bitset_container_printf(const_CAST_bitset(c));
return;
case ARRAY_CONTAINER_TYPE:
array_container_printf(const_CAST_array(c));
return;
case RUN_CONTAINER_TYPE:
run_container_printf(const_CAST_run(c));
return;
default:
roaring_unreachable;
}
}
void container_printf_as_uint32_array(
const container_t *c, uint8_t typecode,
uint32_t base
){
c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
bitset_container_printf_as_uint32_array(
const_CAST_bitset(c), base);
return;
case ARRAY_CONTAINER_TYPE:
array_container_printf_as_uint32_array(
const_CAST_array(c), base);
return;
case RUN_CONTAINER_TYPE:
run_container_printf_as_uint32_array(
const_CAST_run(c), base);
return;
default:
roaring_unreachable;
}
}
bool container_internal_validate(const container_t *container,
uint8_t typecode, const char **reason) {
if (container == NULL) {
*reason = "container is NULL";
return false;
}
// Not using container_unwrap_shared because it asserts if shared containers are nested
if (typecode == SHARED_CONTAINER_TYPE) {
const shared_container_t *shared_container = const_CAST_shared(container);
if (croaring_refcount_get(&shared_container->counter) == 0) {
*reason = "shared container has zero refcount";
return false;
}
if (shared_container->typecode == SHARED_CONTAINER_TYPE) {
*reason = "shared container is nested";
return false;
}
if (shared_container->container == NULL) {
*reason = "shared container has NULL container";
return false;
}
container = shared_container->container;
typecode = shared_container->typecode;
}
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_validate(const_CAST_bitset(container), reason);
case ARRAY_CONTAINER_TYPE:
return array_container_validate(const_CAST_array(container), reason);
case RUN_CONTAINER_TYPE:
return run_container_validate(const_CAST_run(container), reason);
default:
*reason = "invalid typecode";
return false;
}
}
extern inline bool container_nonzero_cardinality(
const container_t *c, uint8_t typecode);
extern inline int container_to_uint32_array(
uint32_t *output,
const container_t *c, uint8_t typecode,
uint32_t base);
extern inline container_t *container_add(
container_t *c,
uint16_t val,
uint8_t typecode, // !!! 2nd arg?
uint8_t *new_typecode);
extern inline bool container_contains(
const container_t *c,
uint16_t val,
uint8_t typecode); // !!! 2nd arg?
extern inline container_t *container_and(
const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_or(
const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_xor(
const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
container_t *get_copy_of_container(
container_t *c, uint8_t *typecode,
bool copy_on_write
){
if (copy_on_write) {
shared_container_t *shared_container;
if (*typecode == SHARED_CONTAINER_TYPE) {
shared_container = CAST_shared(c);
croaring_refcount_inc(&shared_container->counter);
return shared_container;
}
assert(*typecode != SHARED_CONTAINER_TYPE);
if ((shared_container = (shared_container_t *)roaring_malloc(
sizeof(shared_container_t))) == NULL) {
return NULL;
}
shared_container->container = c;
shared_container->typecode = *typecode;
// At this point, we are creating new shared container
// so there should be no other references, and setting
// the counter to 2 - even non-atomically - is safe as
// long as the value is set before the return statement.
shared_container->counter = 2;
*typecode = SHARED_CONTAINER_TYPE;
return shared_container;
} // copy_on_write
// otherwise, no copy on write...
const container_t *actual_container = container_unwrap_shared(c, typecode);
assert(*typecode != SHARED_CONTAINER_TYPE);
return container_clone(actual_container, *typecode);
}
/**
* Copies a container, requires a typecode. This allocates new memory, caller
* is responsible for deallocation.
*/
container_t *container_clone(const container_t *c, uint8_t typecode) {
// We do not want to allow cloning of shared containers.
// c = container_unwrap_shared(c, &typecode);
switch (typecode) {
case BITSET_CONTAINER_TYPE:
return bitset_container_clone(const_CAST_bitset(c));
case ARRAY_CONTAINER_TYPE:
return array_container_clone(const_CAST_array(c));
case RUN_CONTAINER_TYPE:
return run_container_clone(const_CAST_run(c));
case SHARED_CONTAINER_TYPE:
// Shared containers are not cloneable. Are you mixing COW and non-COW bitmaps?
return NULL;
default:
assert(false);
roaring_unreachable;
return NULL;
}
}
container_t *shared_container_extract_copy(
shared_container_t *sc, uint8_t *typecode
){
assert(sc->typecode != SHARED_CONTAINER_TYPE);
*typecode = sc->typecode;
container_t *answer;
if (croaring_refcount_dec(&sc->counter)) {
answer = sc->container;
sc->container = NULL; // paranoid
roaring_free(sc);
} else {
answer = container_clone(sc->container, *typecode);
}
assert(*typecode != SHARED_CONTAINER_TYPE);
return answer;
}
void shared_container_free(shared_container_t *container) {
if (croaring_refcount_dec(&container->counter)) {
assert(container->typecode != SHARED_CONTAINER_TYPE);
container_free(container->container, container->typecode);
container->container = NULL; // paranoid
roaring_free(container);
}
}
extern inline container_t *container_not(
const container_t *c1, uint8_t type1,
uint8_t *result_type);
extern inline container_t *container_not_range(
const container_t *c1, uint8_t type1,
uint32_t range_start, uint32_t range_end,
uint8_t *result_type);
extern inline container_t *container_inot(
container_t *c1, uint8_t type1,
uint8_t *result_type);
extern inline container_t *container_inot_range(
container_t *c1, uint8_t type1,
uint32_t range_start, uint32_t range_end,
uint8_t *result_type);
extern inline container_t *container_range_of_ones(
uint32_t range_start, uint32_t range_end,
uint8_t *result_type);
// where are the correponding things for union and intersection??
extern inline container_t *container_lazy_xor(
const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_lazy_ixor(
container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
extern inline container_t *container_andnot(
const container_t *c1, uint8_t type1,
const container_t *c2, uint8_t type2,
uint8_t *result_type);
#ifdef __cplusplus
} } } // extern "C" { namespace roaring { namespace internal {
#endif
|
