-
Notifications
You must be signed in to change notification settings - Fork 262
/
containers.h
295 lines (266 loc) · 10.6 KB
/
containers.h
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
295
#ifndef CONTAINERS_CONTAINERS_H
#define CONTAINERS_CONTAINERS_H
#include <stdbool.h>
#include <assert.h>
#include "bitset.h"
#include "array.h"
#include "run.h"
#include "convert.h"
// don't use an enum: needs constant folding
// should revisit
#define BITSET_CONTAINER_TYPE_CODE 3
#define ARRAY_CONTAINER_TYPE_CODE 1
#define RUN_CONTAINER_TYPE_CODE 2
//UNINITIALIZED_TYPE_CODE=0}; // can probably avoid using uninit code
/**
* Get the container name from the typecode
*/
inline char * get_container_name(uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
return "bitset";
case ARRAY_CONTAINER_TYPE_CODE:
return "array";
case RUN_CONTAINER_TYPE_CODE:
return "run";
}
return "unknown";
}
/**
* Get the container cardinality (number of elements), requires a typecode
*/
inline uint32_t container_get_cardinality(void *container, uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
return bitset_container_cardinality(container);
case ARRAY_CONTAINER_TYPE_CODE:
return array_container_cardinality(container);
case RUN_CONTAINER_TYPE_CODE:
return run_container_cardinality(container);
}
return 0; // unreached
}
/**
* Checks whether a container is not empty, requires a typecode
*/
inline bool container_nonzero_cardinality(void *container, uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
return bitset_container_nonzero_cardinality(container);
case ARRAY_CONTAINER_TYPE_CODE:
return array_container_nonzero_cardinality(container);
case RUN_CONTAINER_TYPE_CODE:
return run_container_nonzero_cardinality(container);
}
return 0;//unreached
}
/**
* Recover memory from a container, requires a typecode
*/
inline void container_free( void *container, uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
bitset_container_free( (bitset_container_t *) container); break;
case ARRAY_CONTAINER_TYPE_CODE:
array_container_free( (array_container_t *) container); break;
case RUN_CONTAINER_TYPE_CODE:
run_container_free( (run_container_t *) container); break;
// case UNINITIALIZED_TYPE_CODE: break;
}
}
/**
* Convert a container to an array of values, requires a typecode as well as a "base" (most significant values)
*/
inline void container_to_uint32_array( uint32_t *output, void *container, uint8_t typecode, uint32_t base) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
bitset_container_to_uint32_array( output, container, base); break;
case ARRAY_CONTAINER_TYPE_CODE:
array_container_to_uint32_array( output, container, base); break;
case RUN_CONTAINER_TYPE_CODE:
run_container_to_uint32_array( output, container, base); break;
// case UNINITIALIZED_TYPE_CODE: break;
}
}
/**
* Add a value to a container, requires a typecode, fills in new_typecode and return (possibly different) container.
* This function may allocate a new container, and caller is responsible for memory deallocation
*/
inline void *container_add( void *container, uint16_t val, uint8_t typecode, uint8_t *new_typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
bitset_container_set( (bitset_container_t *) container, val);
*new_typecode = BITSET_CONTAINER_TYPE_CODE;
return container;
case ARRAY_CONTAINER_TYPE_CODE: ;
array_container_t *ac = (array_container_t *) container;
array_container_add(ac, val);
if (array_container_cardinality(ac) > DEFAULT_MAX_SIZE) {
*new_typecode = BITSET_CONTAINER_TYPE_CODE;
return bitset_container_from_array(ac);
}
else {
*new_typecode = ARRAY_CONTAINER_TYPE_CODE;
return ac;
}
case RUN_CONTAINER_TYPE_CODE:
// per Java, no container type adjustments are done (revisit?)
run_container_add( (run_container_t *) container, val);
*new_typecode = RUN_CONTAINER_TYPE_CODE;
return container;
default:
assert(0);
return NULL;
}
}
/**
* Check whether a value is in a container, requires a typecode
*/
inline bool container_contains( void *container, uint16_t val, uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
return bitset_container_get( (bitset_container_t *) container, val);
case ARRAY_CONTAINER_TYPE_CODE: ;
return array_container_contains( (array_container_t *) container, val);
case RUN_CONTAINER_TYPE_CODE:
return run_container_contains( (run_container_t *) container, val);
default:
assert(0);
return NULL;
}
}
/**
* Copies a container, requires a typecode. This allocates new memory, caller
* is responsible for deallocation.
*/
inline void *container_clone(void *container, uint8_t typecode) {
switch (typecode) {
case BITSET_CONTAINER_TYPE_CODE:
return bitset_container_clone( (bitset_container_t *) container);
case ARRAY_CONTAINER_TYPE_CODE:
return array_container_clone( (array_container_t *) container);
case RUN_CONTAINER_TYPE_CODE:
return run_container_clone( (run_container_t *) container);
default:
assert(0);
return NULL;
}
}
#if 0
// TODO enable and debug this equality stuff
inline bool container_equals(void *c1, uint8_t type1, void *c2, uint8_t type2) {
switch (type1*4 + type2) {
case BITSET_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return bitset_container_equals( (bitset_container_t *) c1, (bitset_container_t *) c2);
case BITSET_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_equals_bitset( (run_container_t *) c2, (bitset_container_t *) c1);
case RUN_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return run_container_equals_bitset( (run_container_t *) c1, (bitset_container_t *) c2);
case BITSET_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return false;
case ARRAY_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return false;
case ARRAY_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_equals_array( (run_container_t *) c2, (array_container_t *) c1);
case RUN_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return run_container_equals_array( (run_container_t *) c1, (array_container_t *) c2);
case ARRAY_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return array_container_equals( (array_container_t *) c1, (array_container_t *) c2);
case RUN_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_equals( (run_container_t *) c1, (run_container_t *) c2);
}
}
#endif
// macro-izations possibilities for generic non-inplace binary-op dispatch
/**
* Compute intersection between two containers, generate a new container (having type result_type), requires a typecode. This allocates new memory, caller
* is responsible for deallocation.
*/
inline void *container_and(void *c1, uint8_t type1, void *c2, uint8_t type2,
uint8_t *result_type) {
void *result;
switch (type1 * 4 + type2) {
case (BITSET_CONTAINER_TYPE_CODE * 4 + BITSET_CONTAINER_TYPE_CODE):
result = bitset_container_create();
// temp temp, type signature is to return an int, destination param is third
int result_card = bitset_container_and(c1, c2, result);
if (result_card <= DEFAULT_MAX_SIZE) {
// temp temp, container conversion?? Better not here!
*result_type = ARRAY_CONTAINER_TYPE_CODE;
return (void *) array_container_from_bitset(result); // assume it recycles memory as necessary
}
*result_type = BITSET_CONTAINER_TYPE_CODE;
return result;
case ARRAY_CONTAINER_TYPE_CODE * 4 + ARRAY_CONTAINER_TYPE_CODE:
result = array_container_create();
array_container_intersection(c1, c2, result);
*result_type = ARRAY_CONTAINER_TYPE_CODE;
return result;
case RUN_CONTAINER_TYPE_CODE * 4 + RUN_CONTAINER_TYPE_CODE:
result = run_container_create();
run_container_intersection(c1, c2, result);
*result_type = RUN_CONTAINER_TYPE_CODE;
// ToDo, conversion to bitset or array
return result;
#if 0
case BITSET_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_and_bitset( (run_container_t *) c2, (bitset_container_t *) c1);
case RUN_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return run_container_and_bitset( (run_container_t *) c1, (bitset_container_t *) c2);
case BITSET_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return bitset_container_and_array( (bitset_container t *) c1, (array_container_t *) c2);
case ARRAY_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return bitset_container_and_array( (bitset_container t *) c2, (array_container_t *) c1);
case ARRAY_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_and_array( (run_container_t) c2, (array_container_t) c1);
case RUN_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return run_container_and_array( (run_container_t) c1, (array_container_t) c2);
#endif
}
return 0; // unreached
}
/**
* Compute union between two containers, generate a new container (having type result_type), requires a typecode. This allocates new memory, caller
* is responsible for deallocation.
*/
inline void *container_or(void *c1, uint8_t type1, void *c2, uint8_t type2,
uint8_t *result_type) {
void *result;
switch (type1 * 4 + type2) {
case (BITSET_CONTAINER_TYPE_CODE * 4 + BITSET_CONTAINER_TYPE_CODE):
result = bitset_container_create();
//int result_card =
bitset_container_or(c1, c2, result);
*result_type = BITSET_CONTAINER_TYPE_CODE;
return result;
case ARRAY_CONTAINER_TYPE_CODE * 4 + ARRAY_CONTAINER_TYPE_CODE:
result = array_container_create();
// TODO: this is not correct
array_container_union(c1, c2, result);
*result_type = ARRAY_CONTAINER_TYPE_CODE;
return result;
case RUN_CONTAINER_TYPE_CODE * 4 + RUN_CONTAINER_TYPE_CODE:
result = run_container_create();
// TODO: this is not correct
run_container_union(c1, c2, result);
*result_type = RUN_CONTAINER_TYPE_CODE;
// ToDo, conversion to bitset or array
return result;
#if 0
case BITSET_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_or_bitset( (run_container_t *) c2, (bitset_container_t *) c1);
case RUN_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return run_container_or_bitset( (run_container_t *) c1, (bitset_container_t *) c2);
case BITSET_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return bitset_container_or_array( (bitset_container t *) c1, (array_container_t *) c2);
case ARRAY_CONTAINER_TYPE_CODE*4 + BITSET_CONTAINER_TYPE_CODE:
return bitset_container_or_array( (bitset_container t *) c2, (array_container_t *) c1);
case ARRAY_CONTAINER_TYPE_CODE*4 + RUN_CONTAINER_TYPE_CODE:
return run_container_or_array( (run_container_t) c2, (array_container_t) c1);
case RUN_CONTAINER_TYPE_CODE*4 + ARRAY_CONTAINER_TYPE_CODE:
return run_container_or_array( (run_container_t) c1, (array_container_t) c2);
#endif
}
return 0; // unreached
}
#endif