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"
28 #include <babeltrace2/babeltrace.h>
30 #include "lib/assert-pre.h"
31 #include "common/assert.h"
32 #include "func-status.h"
33 #include "integer-range-set.h"
35 uint64_t bt_integer_range_unsigned_get_lower(
36 const struct bt_integer_range_unsigned
*u_range
)
38 const struct bt_integer_range
*range
= (const void *) u_range
;
40 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Integer range");
41 return range
->lower
.u
;
44 uint64_t bt_integer_range_unsigned_get_upper(
45 const struct bt_integer_range_unsigned
*u_range
)
47 const struct bt_integer_range
*range
= (const void *) u_range
;
49 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Integer range");
50 return range
->upper
.u
;
53 int64_t bt_integer_range_signed_get_lower(
54 const struct bt_integer_range_signed
*i_range
)
56 const struct bt_integer_range
*range
= (const void *) i_range
;
58 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Integer range");
59 return range
->lower
.i
;
62 int64_t bt_integer_range_signed_get_upper(
63 const struct bt_integer_range_signed
*i_range
)
65 const struct bt_integer_range
*range
= (const void *) i_range
;
67 BT_ASSERT_PRE_DEV_NON_NULL(range
, "Integer range");
68 return range
->upper
.i
;
72 bool compare_ranges(const struct bt_integer_range
*range_a
,
73 const struct bt_integer_range
*range_b
)
75 return range_a
->lower
.u
== range_b
->lower
.u
&&
76 range_a
->upper
.u
== range_b
->upper
.u
;
79 bt_bool
bt_integer_range_unsigned_is_equal(
80 const struct bt_integer_range_unsigned
*range_a
,
81 const struct bt_integer_range_unsigned
*range_b
)
83 BT_ASSERT_PRE_DEV_NON_NULL(range_a
, "Integer range A");
84 BT_ASSERT_PRE_DEV_NON_NULL(range_b
, "Integer range B");
85 return (bt_bool
) compare_ranges((const void *) range_a
,
86 (const void *) range_b
);
89 bt_bool
bt_integer_range_signed_is_equal(
90 const struct bt_integer_range_signed
*range_a
,
91 const struct bt_integer_range_signed
*range_b
)
93 BT_ASSERT_PRE_DEV_NON_NULL(range_a
, "Integer range A");
94 BT_ASSERT_PRE_DEV_NON_NULL(range_b
, "Integer range B");
95 return (bt_bool
) compare_ranges((const void *) range_a
,
96 (const void *) range_b
);
99 uint64_t bt_integer_range_set_get_range_count(
100 const bt_integer_range_set
*range_set
)
102 BT_ASSERT_PRE_DEV_NON_NULL(range_set
, "Integer range set");
103 return (uint64_t) range_set
->ranges
->len
;
106 const struct bt_integer_range_unsigned
*
107 bt_integer_range_set_unsigned_borrow_range_by_index_const(
108 const bt_integer_range_set_unsigned
*u_range_set
,
111 const struct bt_integer_range_set
*range_set
=
112 (const void *) u_range_set
;
114 BT_ASSERT_PRE_DEV_NON_NULL(range_set
, "Integer 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
,
120 const struct bt_integer_range_signed
*
121 bt_integer_range_set_signed_borrow_range_by_index_const(
122 const bt_integer_range_set_signed
*i_range_set
, uint64_t index
)
124 const struct bt_integer_range_set
*range_set
=
125 (const void *) i_range_set
;
127 BT_ASSERT_PRE_DEV_NON_NULL(range_set
, "Integer range set");
128 BT_ASSERT_PRE_DEV_VALID_INDEX(index
, range_set
->ranges
->len
);
129 return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
,
134 void destroy_range_set(struct bt_object
*obj
)
136 struct bt_integer_range_set
*range_set
= (void *) obj
;
138 BT_LIB_LOGD("Destroying integer range set: %!+R", range_set
);
140 if (range_set
->ranges
) {
141 g_array_free(range_set
->ranges
, TRUE
);
142 range_set
->ranges
= NULL
;
149 struct bt_integer_range_set
*create_range_set(void)
151 struct bt_integer_range_set
*range_set
;
153 BT_LOGD_STR("Creating empty integer range set.");
154 range_set
= g_new0(struct bt_integer_range_set
, 1);
157 BT_LIB_LOGE_APPEND_CAUSE(
158 "Failed to allocate one integer range set.");
162 bt_object_init_shared(&range_set
->base
, destroy_range_set
);
163 range_set
->ranges
= g_array_new(FALSE
, TRUE
,
164 sizeof(struct bt_integer_range
));
165 if (!range_set
->ranges
) {
166 BT_LIB_LOGE_APPEND_CAUSE(
167 "Failed to allocate integer range set's range array.");
171 BT_LOGD_STR("Created empty integer range set.");
175 BT_OBJECT_PUT_REF_AND_RESET(range_set
);
181 struct bt_integer_range_set_unsigned
*bt_integer_range_set_unsigned_create(void)
183 return (void *) create_range_set();
186 struct bt_integer_range_set_signed
*bt_integer_range_set_signed_create(void)
188 return (void *) create_range_set();
192 void add_range_to_range_set(struct bt_integer_range_set
*range_set
,
193 uint64_t u_lower
, uint64_t u_upper
)
195 struct bt_integer_range range
= {
200 BT_ASSERT_PRE_NON_NULL(range_set
, "Integer range set");
201 BT_ASSERT_PRE_DEV_HOT(range_set
, "Integer range set", ": %!+R",
203 g_array_append_val(range_set
->ranges
, range
);
204 BT_LIB_LOGD("Added integer range to integer range set: "
205 "%![range-set-]+R, lower-unsigned=%" PRIu64
", "
206 "upper-unsigned=%" PRIu64
, range_set
, u_lower
, u_upper
);
209 enum bt_integer_range_set_add_range_status
210 bt_integer_range_set_unsigned_add_range(
211 struct bt_integer_range_set_unsigned
*range_set
,
212 uint64_t lower
, uint64_t upper
)
214 BT_ASSERT_PRE(lower
<= upper
,
215 "Range's upper bound is less than lower bound: "
216 "upper=%" PRIu64
", lower=%" PRIu64
, lower
, upper
);
217 add_range_to_range_set((void *) range_set
, lower
, upper
);
218 return BT_FUNC_STATUS_OK
;
221 enum bt_integer_range_set_add_range_status
222 bt_integer_range_set_signed_add_range(
223 struct bt_integer_range_set_signed
*range_set
,
224 int64_t lower
, int64_t upper
)
226 BT_ASSERT_PRE(lower
<= upper
,
227 "Range's upper bound is less than lower bound: "
228 "upper=%" PRId64
", lower=%" PRId64
, lower
, upper
);
229 add_range_to_range_set((void *) range_set
,
230 (int64_t) lower
, (int64_t) upper
);
231 return BT_FUNC_STATUS_OK
;
235 void _bt_integer_range_set_freeze(const struct bt_integer_range_set
*range_set
)
237 BT_ASSERT(range_set
);
238 BT_LIB_LOGD("Freezing integer range set: %!+R", range_set
);
239 ((struct bt_integer_range_set
*) range_set
)->frozen
= true;
243 bool bt_integer_range_set_unsigned_has_overlaps(
244 const struct bt_integer_range_set
*range_set
)
247 bool has_overlap
= false;
249 BT_ASSERT(range_set
);
251 for (i
= 0; i
< range_set
->ranges
->len
; i
++) {
252 const struct bt_integer_range
*range_i
=
253 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, i
);
255 for (j
= 0; j
< range_set
->ranges
->len
; j
++) {
256 const struct bt_integer_range
*range_j
=
257 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
264 if (range_i
->lower
.u
<= range_j
->upper
.u
&&
265 range_j
->lower
.u
<= range_i
->upper
.u
) {
277 bool bt_integer_range_set_signed_has_overlaps(
278 const struct bt_integer_range_set
*range_set
)
281 bool has_overlap
= false;
283 BT_ASSERT(range_set
);
285 for (i
= 0; i
< range_set
->ranges
->len
; i
++) {
286 const struct bt_integer_range
*range_i
=
287 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set
, i
);
289 for (j
= 0; j
< range_set
->ranges
->len
; j
++) {
290 const struct bt_integer_range
*range_j
=
291 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
298 if (range_i
->lower
.i
<= range_j
->upper
.i
&&
299 range_j
->lower
.i
<= range_i
->upper
.i
) {
311 bool compare_range_sets(const struct bt_integer_range_set
*range_set_a
,
312 const struct bt_integer_range_set
*range_set_b
)
315 bool is_equal
= true;
317 BT_ASSERT_DBG(range_set_a
);
318 BT_ASSERT_DBG(range_set_b
);
320 if (range_set_a
== range_set_b
) {
325 * Not super effective for the moment: do a O(N²) compare, also
326 * checking that the sizes match.
328 if (range_set_a
->ranges
->len
!= range_set_b
->ranges
->len
) {
333 for (a_i
= 0; a_i
< range_set_a
->ranges
->len
; a_i
++) {
334 const struct bt_integer_range
*range_a
=
335 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set_a
,
337 bool b_has_range
= false;
339 for (b_i
= 0; b_i
< range_set_b
->ranges
->len
; b_i
++) {
340 const struct bt_integer_range
*range_b
=
341 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
344 if (compare_ranges(range_a
, range_b
)) {
360 bt_bool
bt_integer_range_set_unsigned_is_equal(
361 const struct bt_integer_range_set_unsigned
*range_set_a
,
362 const struct bt_integer_range_set_unsigned
*range_set_b
)
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
);
370 bt_bool
bt_integer_range_set_signed_is_equal(
371 const struct bt_integer_range_set_signed
*range_set_a
,
372 const struct bt_integer_range_set_signed
*range_set_b
)
374 BT_ASSERT_PRE_DEV_NON_NULL(range_set_a
, "Range set A");
375 BT_ASSERT_PRE_DEV_NON_NULL(range_set_b
, "Range set B");
376 return (bt_bool
) compare_range_sets((const void *) range_set_a
,
377 (const void *) range_set_b
);
380 void bt_integer_range_set_unsigned_get_ref(
381 const struct bt_integer_range_set_unsigned
*range_set
)
383 bt_object_get_ref(range_set
);
386 void bt_integer_range_set_unsigned_put_ref(
387 const struct bt_integer_range_set_unsigned
*range_set
)
389 bt_object_put_ref(range_set
);
392 void bt_integer_range_set_signed_get_ref(
393 const struct bt_integer_range_set_signed
*range_set
)
395 bt_object_get_ref(range_set
);
398 void bt_integer_range_set_signed_put_ref(
399 const struct bt_integer_range_set_signed
*range_set
)
401 bt_object_put_ref(range_set
);