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