8853d702be9f9064e8f54e74827c3e9f28a2a201
[babeltrace.git] / src / lib / integer-range-set.c
1 /*
2 * SPDX-License-Identifier: MIT
3 *
4 * Copyright 2019 Philippe Proulx <pproulx@efficios.com>
5 */
6
7 #define BT_LOG_TAG "LIB/INT-RANGE-SET"
8 #include "lib/logging.h"
9
10 #include <stdbool.h>
11
12 #include <babeltrace2/babeltrace.h>
13
14 #include "lib/assert-cond.h"
15 #include "common/assert.h"
16 #include "func-status.h"
17 #include "integer-range-set.h"
18
19 uint64_t bt_integer_range_unsigned_get_lower(
20 const struct bt_integer_range_unsigned *u_range)
21 {
22 const struct bt_integer_range *range = (const void *) u_range;
23
24 BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
25 return range->lower.u;
26 }
27
28 uint64_t bt_integer_range_unsigned_get_upper(
29 const struct bt_integer_range_unsigned *u_range)
30 {
31 const struct bt_integer_range *range = (const void *) u_range;
32
33 BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
34 return range->upper.u;
35 }
36
37 int64_t bt_integer_range_signed_get_lower(
38 const struct bt_integer_range_signed *i_range)
39 {
40 const struct bt_integer_range *range = (const void *) i_range;
41
42 BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
43 return range->lower.i;
44 }
45
46 int64_t bt_integer_range_signed_get_upper(
47 const struct bt_integer_range_signed *i_range)
48 {
49 const struct bt_integer_range *range = (const void *) i_range;
50
51 BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
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
63 bt_bool bt_integer_range_unsigned_is_equal(
64 const struct bt_integer_range_unsigned *range_a,
65 const struct bt_integer_range_unsigned *range_b)
66 {
67 BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A");
68 BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B");
69 return (bt_bool) compare_ranges((const void *) range_a,
70 (const void *) range_b);
71 }
72
73 bt_bool bt_integer_range_signed_is_equal(
74 const struct bt_integer_range_signed *range_a,
75 const struct bt_integer_range_signed *range_b)
76 {
77 BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A");
78 BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B");
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 {
86 BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
87 return (uint64_t) range_set->ranges->len;
88 }
89
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)
94 {
95 const struct bt_integer_range_set *range_set =
96 (const void *) u_range_set;
97
98 BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
99 BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len);
100 return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set,
101 index);
102 }
103
104 const struct bt_integer_range_signed *
105 bt_integer_range_set_signed_borrow_range_by_index_const(
106 const bt_integer_range_set_signed *i_range_set, uint64_t index)
107 {
108 const struct bt_integer_range_set *range_set =
109 (const void *) i_range_set;
110
111 BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
112 BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len);
113 return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set,
114 index);
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
122 BT_LIB_LOGD("Destroying integer range set: %!+R", range_set);
123
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 {
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);
139
140 if (!range_set) {
141 BT_LIB_LOGE_APPEND_CAUSE(
142 "Failed to allocate one integer range set.");
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(
151 "Failed to allocate integer range set's range array.");
152 goto error;
153 }
154
155 BT_LOGD_STR("Created empty integer range set.");
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 {
167 BT_ASSERT_PRE_NO_ERROR();
168
169 return (void *) create_range_set();
170 }
171
172 struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void)
173 {
174 BT_ASSERT_PRE_NO_ERROR();
175
176 return (void *) create_range_set();
177 }
178
179 static
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
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);
191 g_array_append_val(range_set->ranges, range);
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);
195 }
196
197 enum bt_integer_range_set_add_range_status
198 bt_integer_range_set_unsigned_add_range(
199 struct bt_integer_range_set_unsigned *range_set,
200 uint64_t lower, uint64_t upper)
201 {
202 BT_ASSERT_PRE_NO_ERROR();
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
210 enum bt_integer_range_set_add_range_status
211 bt_integer_range_set_signed_add_range(
212 struct bt_integer_range_set_signed *range_set,
213 int64_t lower, int64_t upper)
214 {
215 BT_ASSERT_PRE_NO_ERROR();
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);
228 BT_LIB_LOGD("Freezing integer range set: %!+R", range_set);
229 ((struct bt_integer_range_set *) range_set)->frozen = true;
230 }
231
232 BT_HIDDEN
233 bool bt_integer_range_set_unsigned_has_overlaps(
234 const struct bt_integer_range_set *range_set)
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 =
247 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
248 range_set, j);
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
267 bool bt_integer_range_set_signed_has_overlaps(
268 const struct bt_integer_range_set *range_set)
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 =
281 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
282 range_set, j);
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
307 BT_ASSERT_DBG(range_set_a);
308 BT_ASSERT_DBG(range_set_b);
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
350 bt_bool bt_integer_range_set_unsigned_is_equal(
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
360 bt_bool bt_integer_range_set_signed_is_equal(
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
382 void bt_integer_range_set_signed_get_ref(
383 const struct bt_integer_range_set_signed *range_set)
384 {
385 bt_object_get_ref(range_set);
386 }
387
388 void bt_integer_range_set_signed_put_ref(
389 const struct bt_integer_range_set_signed *range_set)
390 {
391 bt_object_put_ref(range_set);
392 }
This page took 0.036787 seconds and 3 git commands to generate.