2 * Copyright 2019 Philippe Proulx <pproulx@efficios.com>
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 #define BT_LOG_TAG "LIB/INT-RANGE-SET"
24 #include "lib/logging.h"
26 #include <babeltrace2/babeltrace.h>
27 #include "lib/assert-pre.h"
28 #include "common/assert.h"
29 #include "func-status.h"
30 #include "integer-range-set.h"
32 uint64_t bt_integer_range_unsigned_get_lower(const struct bt_integer_range_unsigned
*u_range
)
34 const struct bt_integer_range
*range
= (const void *) u_range
;
36 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Range");
37 return range
->lower
.u
;
40 uint64_t bt_integer_range_unsigned_get_upper(const struct bt_integer_range_unsigned
*u_range
)
42 const struct bt_integer_range
*range
= (const void *) u_range
;
44 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Range");
45 return range
->upper
.u
;
48 int64_t bt_integer_range_signed_get_lower(const struct bt_integer_range_signed
*i_range
)
50 const struct bt_integer_range
*range
= (const void *) i_range
;
52 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Range");
53 return range
->lower
.i
;
56 int64_t bt_integer_range_signed_get_upper(const struct bt_integer_range_signed
*i_range
)
58 const struct bt_integer_range
*range
= (const void *) i_range
;
60 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Range");
61 return range
->upper
.i
;
65 bool compare_ranges(const struct bt_integer_range
*range_a
,
66 const struct bt_integer_range
*range_b
)
68 return range_a
->lower
.u
== range_b
->lower
.u
&&
69 range_a
->upper
.u
== range_b
->upper
.u
;
72 bt_bool
bt_integer_range_unsigned_compare(
73 const struct bt_integer_range_unsigned
*range_a
,
74 const struct bt_integer_range_unsigned
*range_b
)
76 BT_ASSERT_PRE_DEV_NON_NULL(range_a
, "Range A");
77 BT_ASSERT_PRE_DEV_NON_NULL(range_b
, "Range B");
78 return (bt_bool
) compare_ranges((const void *) range_a
,
79 (const void *) range_b
);
82 bt_bool
bt_integer_range_signed_compare(
83 const struct bt_integer_range_signed
*range_a
,
84 const struct bt_integer_range_signed
*range_b
)
86 BT_ASSERT_PRE_DEV_NON_NULL(range_a
, "Range A");
87 BT_ASSERT_PRE_DEV_NON_NULL(range_b
, "Range B");
88 return (bt_bool
) compare_ranges((const void *) range_a
,
89 (const void *) range_b
);
92 uint64_t bt_integer_range_set_get_range_count(
93 const bt_integer_range_set
*range_set
)
95 BT_ASSERT_PRE_DEV_NON_NULL(range_set
, "Range set");
96 return (uint64_t) range_set
->ranges
->len
;
99 const struct bt_integer_range_unsigned
*bt_integer_range_set_unsigned_borrow_range_by_index_const(
100 const bt_integer_range_set_unsigned
*u_range_set
, uint64_t index
)
102 const struct bt_integer_range_set
*range_set
= (const void *) u_range_set
;
104 BT_ASSERT_PRE_DEV_NON_NULL(range_set
, "Range set");
105 BT_ASSERT_PRE_DEV_VALID_INDEX(index
, range_set
->ranges
->len
);
106 return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, index
);
109 const struct bt_integer_range_signed
*bt_integer_range_set_signed_borrow_range_by_index_const(
110 const bt_integer_range_set_signed
*i_range_set
, uint64_t index
)
112 const struct bt_integer_range_set
*range_set
= (const void *) i_range_set
;
114 BT_ASSERT_PRE_DEV_NON_NULL(range_set
, "Range set");
115 BT_ASSERT_PRE_DEV_VALID_INDEX(index
, range_set
->ranges
->len
);
116 return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, index
);
120 void destroy_range_set(struct bt_object
*obj
)
122 struct bt_integer_range_set
*range_set
= (void *) obj
;
124 if (range_set
->ranges
) {
125 g_array_free(range_set
->ranges
, TRUE
);
126 range_set
->ranges
= NULL
;
133 struct bt_integer_range_set
*create_range_set(void)
135 struct bt_integer_range_set
*range_set
= g_new0(struct bt_integer_range_set
, 1);
138 BT_LIB_LOGE_APPEND_CAUSE("Failed to allocate one range set.");
142 bt_object_init_shared(&range_set
->base
, destroy_range_set
);
143 range_set
->ranges
= g_array_new(FALSE
, TRUE
,
144 sizeof(struct bt_integer_range
));
145 if (!range_set
->ranges
) {
146 BT_LIB_LOGE_APPEND_CAUSE(
147 "Failed to allocate range set's range array.");
154 BT_OBJECT_PUT_REF_AND_RESET(range_set
);
160 struct bt_integer_range_set_unsigned
*bt_integer_range_set_unsigned_create(void)
162 return (void *) create_range_set();
165 struct bt_integer_range_set_signed
*bt_integer_range_set_signed_create(void)
167 return (void *) create_range_set();
170 void add_range_to_range_set(struct bt_integer_range_set
*range_set
,
171 uint64_t u_lower
, uint64_t u_upper
)
173 struct bt_integer_range range
= {
178 BT_ASSERT_PRE_NON_NULL(range_set
, "Range set");
179 BT_ASSERT_PRE_DEV_HOT(range_set
, "Range set", ": addr=%p", range_set
);
180 g_array_append_val(range_set
->ranges
, range
);
181 BT_LIB_LOGD("Added range to range set: "
182 "range-set-addr=%p, lower-unsigned=%" PRIu64
", "
183 "upper-unsigned=%" PRIu64
,
184 range_set
, u_lower
, u_upper
);
187 enum bt_integer_range_set_add_range_status
bt_integer_range_set_unsigned_add_range(
188 struct bt_integer_range_set_unsigned
*range_set
,
189 uint64_t lower
, uint64_t upper
)
191 BT_ASSERT_PRE(lower
<= upper
,
192 "Range's upper bound is less than lower bound: "
193 "upper=%" PRIu64
", lower=%" PRIu64
, lower
, upper
);
194 add_range_to_range_set((void *) range_set
, lower
, upper
);
195 return BT_FUNC_STATUS_OK
;
198 enum bt_integer_range_set_add_range_status
bt_integer_range_set_signed_add_range(
199 struct bt_integer_range_set_signed
*range_set
,
200 int64_t lower
, int64_t upper
)
202 BT_ASSERT_PRE(lower
<= upper
,
203 "Range's upper bound is less than lower bound: "
204 "upper=%" PRId64
", lower=%" PRId64
, lower
, upper
);
205 add_range_to_range_set((void *) range_set
,
206 (int64_t) lower
, (int64_t) upper
);
207 return BT_FUNC_STATUS_OK
;
211 void _bt_integer_range_set_freeze(const struct bt_integer_range_set
*range_set
)
213 BT_ASSERT(range_set
);
214 BT_LIB_LOGD("Freezing range set: addr=%p", range_set
);
215 ((struct bt_integer_range_set
*) range_set
)->frozen
= true;
219 bool bt_integer_range_set_unsigned_has_overlaps(const struct bt_integer_range_set
*range_set
)
222 bool has_overlap
= false;
224 BT_ASSERT(range_set
);
226 for (i
= 0; i
< range_set
->ranges
->len
; i
++) {
227 const struct bt_integer_range
*range_i
=
228 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, i
);
230 for (j
= 0; j
< range_set
->ranges
->len
; j
++) {
231 const struct bt_integer_range
*range_j
=
232 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, j
);
238 if (range_i
->lower
.u
<= range_j
->upper
.u
&&
239 range_j
->lower
.u
<= range_i
->upper
.u
) {
251 bool bt_integer_range_set_signed_has_overlaps(const struct bt_integer_range_set
*range_set
)
254 bool has_overlap
= false;
256 BT_ASSERT(range_set
);
258 for (i
= 0; i
< range_set
->ranges
->len
; i
++) {
259 const struct bt_integer_range
*range_i
=
260 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, i
);
262 for (j
= 0; j
< range_set
->ranges
->len
; j
++) {
263 const struct bt_integer_range
*range_j
=
264 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, j
);
270 if (range_i
->lower
.i
<= range_j
->upper
.i
&&
271 range_j
->lower
.i
<= range_i
->upper
.i
) {
283 bool compare_range_sets(const struct bt_integer_range_set
*range_set_a
,
284 const struct bt_integer_range_set
*range_set_b
)
287 bool is_equal
= true;
289 BT_ASSERT(range_set_a
);
290 BT_ASSERT(range_set_b
);
292 if (range_set_a
== range_set_b
) {
297 * Not super effective for the moment: do a O(N²) compare, also
298 * checking that the sizes match.
300 if (range_set_a
->ranges
->len
!= range_set_b
->ranges
->len
) {
305 for (a_i
= 0; a_i
< range_set_a
->ranges
->len
; a_i
++) {
306 const struct bt_integer_range
*range_a
=
307 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set_a
,
309 bool b_has_range
= false;
311 for (b_i
= 0; b_i
< range_set_b
->ranges
->len
; b_i
++) {
312 const struct bt_integer_range
*range_b
=
313 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
316 if (compare_ranges(range_a
, range_b
)) {
332 bt_bool
bt_integer_range_set_unsigned_compare(
333 const struct bt_integer_range_set_unsigned
*range_set_a
,
334 const struct bt_integer_range_set_unsigned
*range_set_b
)
336 BT_ASSERT_PRE_DEV_NON_NULL(range_set_a
, "Range set A");
337 BT_ASSERT_PRE_DEV_NON_NULL(range_set_b
, "Range set B");
338 return (bt_bool
) compare_range_sets((const void *) range_set_a
,
339 (const void *) range_set_b
);
342 bt_bool
bt_integer_range_set_signed_compare(
343 const struct bt_integer_range_set_signed
*range_set_a
,
344 const struct bt_integer_range_set_signed
*range_set_b
)
346 BT_ASSERT_PRE_DEV_NON_NULL(range_set_a
, "Range set A");
347 BT_ASSERT_PRE_DEV_NON_NULL(range_set_b
, "Range set B");
348 return (bt_bool
) compare_range_sets((const void *) range_set_a
,
349 (const void *) range_set_b
);
352 void bt_integer_range_set_unsigned_get_ref(
353 const struct bt_integer_range_set_unsigned
*range_set
)
355 bt_object_get_ref(range_set
);
358 void bt_integer_range_set_unsigned_put_ref(
359 const struct bt_integer_range_set_unsigned
*range_set
)
361 bt_object_put_ref(range_set
);
364 void bt_integer_range_set_signed_get_ref(const struct bt_integer_range_set_signed
*range_set
)
366 bt_object_get_ref(range_set
);
369 void bt_integer_range_set_signed_put_ref(const struct bt_integer_range_set_signed
*range_set
)
371 bt_object_put_ref(range_set
);