Commit | Line | Data |
---|---|---|
fb91c0ef | 1 | /* |
0235b0db | 2 | * SPDX-License-Identifier: MIT |
fb91c0ef | 3 | * |
0235b0db | 4 | * Copyright 2019 Philippe Proulx <pproulx@efficios.com> |
fb91c0ef PP |
5 | */ |
6 | ||
7 | #define BT_LOG_TAG "LIB/INT-RANGE-SET" | |
8 | #include "lib/logging.h" | |
9 | ||
c4f23e30 FD |
10 | #include <stdbool.h> |
11 | ||
fb91c0ef | 12 | #include <babeltrace2/babeltrace.h> |
c4f23e30 | 13 | |
fb91c0ef PP |
14 | #include "lib/assert-pre.h" |
15 | #include "common/assert.h" | |
16 | #include "func-status.h" | |
17 | #include "integer-range-set.h" | |
18 | ||
6769570a PP |
19 | uint64_t bt_integer_range_unsigned_get_lower( |
20 | const struct bt_integer_range_unsigned *u_range) | |
fb91c0ef PP |
21 | { |
22 | const struct bt_integer_range *range = (const void *) u_range; | |
23 | ||
6769570a | 24 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
25 | return range->lower.u; |
26 | } | |
27 | ||
6769570a PP |
28 | uint64_t bt_integer_range_unsigned_get_upper( |
29 | const struct bt_integer_range_unsigned *u_range) | |
fb91c0ef PP |
30 | { |
31 | const struct bt_integer_range *range = (const void *) u_range; | |
32 | ||
6769570a | 33 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
34 | return range->upper.u; |
35 | } | |
36 | ||
6769570a PP |
37 | int64_t bt_integer_range_signed_get_lower( |
38 | const struct bt_integer_range_signed *i_range) | |
fb91c0ef PP |
39 | { |
40 | const struct bt_integer_range *range = (const void *) i_range; | |
41 | ||
6769570a | 42 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
43 | return range->lower.i; |
44 | } | |
45 | ||
6769570a PP |
46 | int64_t bt_integer_range_signed_get_upper( |
47 | const struct bt_integer_range_signed *i_range) | |
fb91c0ef PP |
48 | { |
49 | const struct bt_integer_range *range = (const void *) i_range; | |
50 | ||
6769570a | 51 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
52 | return range->upper.i; |
53 | } | |
54 | ||
55 | static | |
56 | bool compare_ranges(const struct bt_integer_range *range_a, | |
57 | const struct bt_integer_range *range_b) | |
58 | { | |
59 | return range_a->lower.u == range_b->lower.u && | |
60 | range_a->upper.u == range_b->upper.u; | |
61 | } | |
62 | ||
cd933d89 | 63 | bt_bool bt_integer_range_unsigned_is_equal( |
fb91c0ef PP |
64 | const struct bt_integer_range_unsigned *range_a, |
65 | const struct bt_integer_range_unsigned *range_b) | |
66 | { | |
6769570a PP |
67 | BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A"); |
68 | BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B"); | |
fb91c0ef PP |
69 | return (bt_bool) compare_ranges((const void *) range_a, |
70 | (const void *) range_b); | |
71 | } | |
72 | ||
cd933d89 | 73 | bt_bool bt_integer_range_signed_is_equal( |
fb91c0ef PP |
74 | const struct bt_integer_range_signed *range_a, |
75 | const struct bt_integer_range_signed *range_b) | |
76 | { | |
6769570a PP |
77 | BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A"); |
78 | BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B"); | |
fb91c0ef PP |
79 | return (bt_bool) compare_ranges((const void *) range_a, |
80 | (const void *) range_b); | |
81 | } | |
82 | ||
83 | uint64_t bt_integer_range_set_get_range_count( | |
84 | const bt_integer_range_set *range_set) | |
85 | { | |
6769570a | 86 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
fb91c0ef PP |
87 | return (uint64_t) range_set->ranges->len; |
88 | } | |
89 | ||
6769570a PP |
90 | const struct bt_integer_range_unsigned * |
91 | bt_integer_range_set_unsigned_borrow_range_by_index_const( | |
92 | const bt_integer_range_set_unsigned *u_range_set, | |
93 | uint64_t index) | |
fb91c0ef | 94 | { |
6769570a PP |
95 | const struct bt_integer_range_set *range_set = |
96 | (const void *) u_range_set; | |
fb91c0ef | 97 | |
6769570a | 98 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
fb91c0ef | 99 | BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len); |
6769570a PP |
100 | return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, |
101 | index); | |
fb91c0ef PP |
102 | } |
103 | ||
6769570a PP |
104 | const struct bt_integer_range_signed * |
105 | bt_integer_range_set_signed_borrow_range_by_index_const( | |
fb91c0ef PP |
106 | const bt_integer_range_set_signed *i_range_set, uint64_t index) |
107 | { | |
6769570a PP |
108 | const struct bt_integer_range_set *range_set = |
109 | (const void *) i_range_set; | |
fb91c0ef | 110 | |
6769570a | 111 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
fb91c0ef | 112 | BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len); |
6769570a PP |
113 | return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, |
114 | index); | |
fb91c0ef PP |
115 | } |
116 | ||
117 | static | |
118 | void destroy_range_set(struct bt_object *obj) | |
119 | { | |
120 | struct bt_integer_range_set *range_set = (void *) obj; | |
121 | ||
6769570a PP |
122 | BT_LIB_LOGD("Destroying integer range set: %!+R", range_set); |
123 | ||
fb91c0ef PP |
124 | if (range_set->ranges) { |
125 | g_array_free(range_set->ranges, TRUE); | |
126 | range_set->ranges = NULL; | |
127 | } | |
128 | ||
129 | g_free(range_set); | |
130 | } | |
131 | ||
132 | static | |
133 | struct bt_integer_range_set *create_range_set(void) | |
134 | { | |
6769570a PP |
135 | struct bt_integer_range_set *range_set; |
136 | ||
137 | BT_LOGD_STR("Creating empty integer range set."); | |
138 | range_set = g_new0(struct bt_integer_range_set, 1); | |
fb91c0ef PP |
139 | |
140 | if (!range_set) { | |
6769570a PP |
141 | BT_LIB_LOGE_APPEND_CAUSE( |
142 | "Failed to allocate one integer range set."); | |
fb91c0ef PP |
143 | goto error; |
144 | } | |
145 | ||
146 | bt_object_init_shared(&range_set->base, destroy_range_set); | |
147 | range_set->ranges = g_array_new(FALSE, TRUE, | |
148 | sizeof(struct bt_integer_range)); | |
149 | if (!range_set->ranges) { | |
150 | BT_LIB_LOGE_APPEND_CAUSE( | |
6769570a | 151 | "Failed to allocate integer range set's range array."); |
fb91c0ef PP |
152 | goto error; |
153 | } | |
154 | ||
6769570a | 155 | BT_LOGD_STR("Created empty integer range set."); |
fb91c0ef PP |
156 | goto end; |
157 | ||
158 | error: | |
159 | BT_OBJECT_PUT_REF_AND_RESET(range_set); | |
160 | ||
161 | end: | |
162 | return range_set; | |
163 | } | |
164 | ||
165 | struct bt_integer_range_set_unsigned *bt_integer_range_set_unsigned_create(void) | |
166 | { | |
17f3083a SM |
167 | BT_ASSERT_PRE_NO_ERROR(); |
168 | ||
fb91c0ef PP |
169 | return (void *) create_range_set(); |
170 | } | |
171 | ||
172 | struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void) | |
173 | { | |
17f3083a SM |
174 | BT_ASSERT_PRE_NO_ERROR(); |
175 | ||
fb91c0ef PP |
176 | return (void *) create_range_set(); |
177 | } | |
178 | ||
7c7301d5 | 179 | static |
fb91c0ef PP |
180 | void add_range_to_range_set(struct bt_integer_range_set *range_set, |
181 | uint64_t u_lower, uint64_t u_upper) | |
182 | { | |
183 | struct bt_integer_range range = { | |
184 | .lower.u = u_lower, | |
185 | .upper.u = u_upper, | |
186 | }; | |
187 | ||
6769570a PP |
188 | BT_ASSERT_PRE_NON_NULL(range_set, "Integer range set"); |
189 | BT_ASSERT_PRE_DEV_HOT(range_set, "Integer range set", ": %!+R", | |
190 | range_set); | |
fb91c0ef | 191 | g_array_append_val(range_set->ranges, range); |
6769570a PP |
192 | BT_LIB_LOGD("Added integer range to integer range set: " |
193 | "%![range-set-]+R, lower-unsigned=%" PRIu64 ", " | |
194 | "upper-unsigned=%" PRIu64, range_set, u_lower, u_upper); | |
fb91c0ef PP |
195 | } |
196 | ||
6769570a PP |
197 | enum bt_integer_range_set_add_range_status |
198 | bt_integer_range_set_unsigned_add_range( | |
fb91c0ef PP |
199 | struct bt_integer_range_set_unsigned *range_set, |
200 | uint64_t lower, uint64_t upper) | |
201 | { | |
17f3083a | 202 | BT_ASSERT_PRE_NO_ERROR(); |
fb91c0ef PP |
203 | BT_ASSERT_PRE(lower <= upper, |
204 | "Range's upper bound is less than lower bound: " | |
205 | "upper=%" PRIu64 ", lower=%" PRIu64, lower, upper); | |
206 | add_range_to_range_set((void *) range_set, lower, upper); | |
207 | return BT_FUNC_STATUS_OK; | |
208 | } | |
209 | ||
6769570a PP |
210 | enum bt_integer_range_set_add_range_status |
211 | bt_integer_range_set_signed_add_range( | |
fb91c0ef PP |
212 | struct bt_integer_range_set_signed *range_set, |
213 | int64_t lower, int64_t upper) | |
214 | { | |
17f3083a | 215 | BT_ASSERT_PRE_NO_ERROR(); |
fb91c0ef PP |
216 | BT_ASSERT_PRE(lower <= upper, |
217 | "Range's upper bound is less than lower bound: " | |
218 | "upper=%" PRId64 ", lower=%" PRId64, lower, upper); | |
219 | add_range_to_range_set((void *) range_set, | |
220 | (int64_t) lower, (int64_t) upper); | |
221 | return BT_FUNC_STATUS_OK; | |
222 | } | |
223 | ||
224 | BT_HIDDEN | |
225 | void _bt_integer_range_set_freeze(const struct bt_integer_range_set *range_set) | |
226 | { | |
227 | BT_ASSERT(range_set); | |
6769570a | 228 | BT_LIB_LOGD("Freezing integer range set: %!+R", range_set); |
fb91c0ef PP |
229 | ((struct bt_integer_range_set *) range_set)->frozen = true; |
230 | } | |
231 | ||
232 | BT_HIDDEN | |
6769570a PP |
233 | bool bt_integer_range_set_unsigned_has_overlaps( |
234 | const struct bt_integer_range_set *range_set) | |
fb91c0ef PP |
235 | { |
236 | uint64_t i, j; | |
237 | bool has_overlap = false; | |
238 | ||
239 | BT_ASSERT(range_set); | |
240 | ||
241 | for (i = 0; i < range_set->ranges->len; i++) { | |
242 | const struct bt_integer_range *range_i = | |
243 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i); | |
244 | ||
245 | for (j = 0; j < range_set->ranges->len; j++) { | |
246 | const struct bt_integer_range *range_j = | |
6769570a PP |
247 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( |
248 | range_set, j); | |
fb91c0ef PP |
249 | |
250 | if (i == j) { | |
251 | continue; | |
252 | } | |
253 | ||
254 | if (range_i->lower.u <= range_j->upper.u && | |
255 | range_j->lower.u <= range_i->upper.u) { | |
256 | has_overlap = true; | |
257 | goto end; | |
258 | } | |
259 | } | |
260 | } | |
261 | ||
262 | end: | |
263 | return has_overlap; | |
264 | } | |
265 | ||
266 | BT_HIDDEN | |
6769570a PP |
267 | bool bt_integer_range_set_signed_has_overlaps( |
268 | const struct bt_integer_range_set *range_set) | |
fb91c0ef PP |
269 | { |
270 | uint64_t i, j; | |
271 | bool has_overlap = false; | |
272 | ||
273 | BT_ASSERT(range_set); | |
274 | ||
275 | for (i = 0; i < range_set->ranges->len; i++) { | |
276 | const struct bt_integer_range *range_i = | |
277 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i); | |
278 | ||
279 | for (j = 0; j < range_set->ranges->len; j++) { | |
280 | const struct bt_integer_range *range_j = | |
6769570a PP |
281 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( |
282 | range_set, j); | |
fb91c0ef PP |
283 | |
284 | if (i == j) { | |
285 | continue; | |
286 | } | |
287 | ||
288 | if (range_i->lower.i <= range_j->upper.i && | |
289 | range_j->lower.i <= range_i->upper.i) { | |
290 | has_overlap = true; | |
291 | goto end; | |
292 | } | |
293 | } | |
294 | } | |
295 | ||
296 | end: | |
297 | return has_overlap; | |
298 | } | |
299 | ||
300 | static | |
301 | bool compare_range_sets(const struct bt_integer_range_set *range_set_a, | |
302 | const struct bt_integer_range_set *range_set_b) | |
303 | { | |
304 | uint64_t a_i, b_i; | |
305 | bool is_equal = true; | |
306 | ||
98b15851 PP |
307 | BT_ASSERT_DBG(range_set_a); |
308 | BT_ASSERT_DBG(range_set_b); | |
fb91c0ef PP |
309 | |
310 | if (range_set_a == range_set_b) { | |
311 | goto end; | |
312 | } | |
313 | ||
314 | /* | |
315 | * Not super effective for the moment: do a O(N²) compare, also | |
316 | * checking that the sizes match. | |
317 | */ | |
318 | if (range_set_a->ranges->len != range_set_b->ranges->len) { | |
319 | is_equal = false; | |
320 | goto end; | |
321 | } | |
322 | ||
323 | for (a_i = 0; a_i < range_set_a->ranges->len; a_i++) { | |
324 | const struct bt_integer_range *range_a = | |
325 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set_a, | |
326 | a_i); | |
327 | bool b_has_range = false; | |
328 | ||
329 | for (b_i = 0; b_i < range_set_b->ranges->len; b_i++) { | |
330 | const struct bt_integer_range *range_b = | |
331 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( | |
332 | range_set_b, b_i); | |
333 | ||
334 | if (compare_ranges(range_a, range_b)) { | |
335 | b_has_range = true; | |
336 | break; | |
337 | } | |
338 | } | |
339 | ||
340 | if (!b_has_range) { | |
341 | is_equal = false; | |
342 | goto end; | |
343 | } | |
344 | } | |
345 | ||
346 | end: | |
347 | return is_equal; | |
348 | } | |
349 | ||
cd933d89 | 350 | bt_bool bt_integer_range_set_unsigned_is_equal( |
fb91c0ef PP |
351 | const struct bt_integer_range_set_unsigned *range_set_a, |
352 | const struct bt_integer_range_set_unsigned *range_set_b) | |
353 | { | |
354 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A"); | |
355 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B"); | |
356 | return (bt_bool) compare_range_sets((const void *) range_set_a, | |
357 | (const void *) range_set_b); | |
358 | } | |
359 | ||
cd933d89 | 360 | bt_bool bt_integer_range_set_signed_is_equal( |
fb91c0ef PP |
361 | const struct bt_integer_range_set_signed *range_set_a, |
362 | const struct bt_integer_range_set_signed *range_set_b) | |
363 | { | |
364 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A"); | |
365 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B"); | |
366 | return (bt_bool) compare_range_sets((const void *) range_set_a, | |
367 | (const void *) range_set_b); | |
368 | } | |
369 | ||
370 | void bt_integer_range_set_unsigned_get_ref( | |
371 | const struct bt_integer_range_set_unsigned *range_set) | |
372 | { | |
373 | bt_object_get_ref(range_set); | |
374 | } | |
375 | ||
376 | void bt_integer_range_set_unsigned_put_ref( | |
377 | const struct bt_integer_range_set_unsigned *range_set) | |
378 | { | |
379 | bt_object_put_ref(range_set); | |
380 | } | |
381 | ||
6769570a PP |
382 | void bt_integer_range_set_signed_get_ref( |
383 | const struct bt_integer_range_set_signed *range_set) | |
fb91c0ef PP |
384 | { |
385 | bt_object_get_ref(range_set); | |
386 | } | |
387 | ||
6769570a PP |
388 | void bt_integer_range_set_signed_put_ref( |
389 | const struct bt_integer_range_set_signed *range_set) | |
fb91c0ef PP |
390 | { |
391 | bt_object_put_ref(range_set); | |
392 | } |