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