Commit | Line | Data |
---|---|---|
ba38aae7 PP |
1 | /* |
2 | * Copyright 2019 Philippe Proulx <pproulx@efficios.com> | |
3 | * | |
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: | |
10 | * | |
11 | * The above copyright notice and this permission notice shall be included in | |
12 | * all copies or substantial portions of the Software. | |
13 | * | |
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 | |
20 | * SOFTWARE. | |
21 | */ | |
22 | ||
23 | #define BT_LOG_TAG "LIB/INT-RANGE-SET" | |
24 | #include "lib/logging.h" | |
25 | ||
969c1d8a FD |
26 | #include <stdbool.h> |
27 | ||
ba38aae7 | 28 | #include <babeltrace2/babeltrace.h> |
969c1d8a | 29 | |
ba38aae7 PP |
30 | #include "lib/assert-pre.h" |
31 | #include "common/assert.h" | |
32 | #include "func-status.h" | |
33 | #include "integer-range-set.h" | |
34 | ||
88efd0a7 PP |
35 | uint64_t bt_integer_range_unsigned_get_lower( |
36 | const struct bt_integer_range_unsigned *u_range) | |
ba38aae7 PP |
37 | { |
38 | const struct bt_integer_range *range = (const void *) u_range; | |
39 | ||
88efd0a7 | 40 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
ba38aae7 PP |
41 | return range->lower.u; |
42 | } | |
43 | ||
88efd0a7 PP |
44 | uint64_t bt_integer_range_unsigned_get_upper( |
45 | const struct bt_integer_range_unsigned *u_range) | |
ba38aae7 PP |
46 | { |
47 | const struct bt_integer_range *range = (const void *) u_range; | |
48 | ||
88efd0a7 | 49 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
ba38aae7 PP |
50 | return range->upper.u; |
51 | } | |
52 | ||
88efd0a7 PP |
53 | int64_t bt_integer_range_signed_get_lower( |
54 | const struct bt_integer_range_signed *i_range) | |
ba38aae7 PP |
55 | { |
56 | const struct bt_integer_range *range = (const void *) i_range; | |
57 | ||
88efd0a7 | 58 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
ba38aae7 PP |
59 | return range->lower.i; |
60 | } | |
61 | ||
88efd0a7 PP |
62 | int64_t bt_integer_range_signed_get_upper( |
63 | const struct bt_integer_range_signed *i_range) | |
ba38aae7 PP |
64 | { |
65 | const struct bt_integer_range *range = (const void *) i_range; | |
66 | ||
88efd0a7 | 67 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
ba38aae7 PP |
68 | return range->upper.i; |
69 | } | |
70 | ||
71 | static | |
72 | bool compare_ranges(const struct bt_integer_range *range_a, | |
73 | const struct bt_integer_range *range_b) | |
74 | { | |
75 | return range_a->lower.u == range_b->lower.u && | |
76 | range_a->upper.u == range_b->upper.u; | |
77 | } | |
78 | ||
e1c423f9 | 79 | bt_bool bt_integer_range_unsigned_is_equal( |
ba38aae7 PP |
80 | const struct bt_integer_range_unsigned *range_a, |
81 | const struct bt_integer_range_unsigned *range_b) | |
82 | { | |
88efd0a7 PP |
83 | BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A"); |
84 | BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B"); | |
ba38aae7 PP |
85 | return (bt_bool) compare_ranges((const void *) range_a, |
86 | (const void *) range_b); | |
87 | } | |
88 | ||
e1c423f9 | 89 | bt_bool bt_integer_range_signed_is_equal( |
ba38aae7 PP |
90 | const struct bt_integer_range_signed *range_a, |
91 | const struct bt_integer_range_signed *range_b) | |
92 | { | |
88efd0a7 PP |
93 | BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A"); |
94 | BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B"); | |
ba38aae7 PP |
95 | return (bt_bool) compare_ranges((const void *) range_a, |
96 | (const void *) range_b); | |
97 | } | |
98 | ||
99 | uint64_t bt_integer_range_set_get_range_count( | |
100 | const bt_integer_range_set *range_set) | |
101 | { | |
88efd0a7 | 102 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
ba38aae7 PP |
103 | return (uint64_t) range_set->ranges->len; |
104 | } | |
105 | ||
88efd0a7 PP |
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, | |
109 | uint64_t index) | |
ba38aae7 | 110 | { |
88efd0a7 PP |
111 | const struct bt_integer_range_set *range_set = |
112 | (const void *) u_range_set; | |
ba38aae7 | 113 | |
88efd0a7 | 114 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
ba38aae7 | 115 | BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len); |
88efd0a7 PP |
116 | return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, |
117 | index); | |
ba38aae7 PP |
118 | } |
119 | ||
88efd0a7 PP |
120 | const struct bt_integer_range_signed * |
121 | bt_integer_range_set_signed_borrow_range_by_index_const( | |
ba38aae7 PP |
122 | const bt_integer_range_set_signed *i_range_set, uint64_t index) |
123 | { | |
88efd0a7 PP |
124 | const struct bt_integer_range_set *range_set = |
125 | (const void *) i_range_set; | |
ba38aae7 | 126 | |
88efd0a7 | 127 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
ba38aae7 | 128 | BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len); |
88efd0a7 PP |
129 | return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, |
130 | index); | |
ba38aae7 PP |
131 | } |
132 | ||
133 | static | |
134 | void destroy_range_set(struct bt_object *obj) | |
135 | { | |
136 | struct bt_integer_range_set *range_set = (void *) obj; | |
137 | ||
88efd0a7 PP |
138 | BT_LIB_LOGD("Destroying integer range set: %!+R", range_set); |
139 | ||
ba38aae7 PP |
140 | if (range_set->ranges) { |
141 | g_array_free(range_set->ranges, TRUE); | |
142 | range_set->ranges = NULL; | |
143 | } | |
144 | ||
145 | g_free(range_set); | |
146 | } | |
147 | ||
148 | static | |
149 | struct bt_integer_range_set *create_range_set(void) | |
150 | { | |
88efd0a7 PP |
151 | struct bt_integer_range_set *range_set; |
152 | ||
153 | BT_LOGD_STR("Creating empty integer range set."); | |
154 | range_set = g_new0(struct bt_integer_range_set, 1); | |
ba38aae7 PP |
155 | |
156 | if (!range_set) { | |
88efd0a7 PP |
157 | BT_LIB_LOGE_APPEND_CAUSE( |
158 | "Failed to allocate one integer range set."); | |
ba38aae7 PP |
159 | goto error; |
160 | } | |
161 | ||
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( | |
88efd0a7 | 167 | "Failed to allocate integer range set's range array."); |
ba38aae7 PP |
168 | goto error; |
169 | } | |
170 | ||
88efd0a7 | 171 | BT_LOGD_STR("Created empty integer range set."); |
ba38aae7 PP |
172 | goto end; |
173 | ||
174 | error: | |
175 | BT_OBJECT_PUT_REF_AND_RESET(range_set); | |
176 | ||
177 | end: | |
178 | return range_set; | |
179 | } | |
180 | ||
181 | struct bt_integer_range_set_unsigned *bt_integer_range_set_unsigned_create(void) | |
182 | { | |
183 | return (void *) create_range_set(); | |
184 | } | |
185 | ||
186 | struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void) | |
187 | { | |
188 | return (void *) create_range_set(); | |
189 | } | |
190 | ||
f3847c75 | 191 | static |
ba38aae7 PP |
192 | void add_range_to_range_set(struct bt_integer_range_set *range_set, |
193 | uint64_t u_lower, uint64_t u_upper) | |
194 | { | |
195 | struct bt_integer_range range = { | |
196 | .lower.u = u_lower, | |
197 | .upper.u = u_upper, | |
198 | }; | |
199 | ||
88efd0a7 PP |
200 | BT_ASSERT_PRE_NON_NULL(range_set, "Integer range set"); |
201 | BT_ASSERT_PRE_DEV_HOT(range_set, "Integer range set", ": %!+R", | |
202 | range_set); | |
ba38aae7 | 203 | g_array_append_val(range_set->ranges, range); |
88efd0a7 PP |
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); | |
ba38aae7 PP |
207 | } |
208 | ||
88efd0a7 PP |
209 | enum bt_integer_range_set_add_range_status |
210 | bt_integer_range_set_unsigned_add_range( | |
ba38aae7 PP |
211 | struct bt_integer_range_set_unsigned *range_set, |
212 | uint64_t lower, uint64_t upper) | |
213 | { | |
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; | |
219 | } | |
220 | ||
88efd0a7 PP |
221 | enum bt_integer_range_set_add_range_status |
222 | bt_integer_range_set_signed_add_range( | |
ba38aae7 PP |
223 | struct bt_integer_range_set_signed *range_set, |
224 | int64_t lower, int64_t upper) | |
225 | { | |
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; | |
232 | } | |
233 | ||
234 | BT_HIDDEN | |
235 | void _bt_integer_range_set_freeze(const struct bt_integer_range_set *range_set) | |
236 | { | |
237 | BT_ASSERT(range_set); | |
88efd0a7 | 238 | BT_LIB_LOGD("Freezing integer range set: %!+R", range_set); |
ba38aae7 PP |
239 | ((struct bt_integer_range_set *) range_set)->frozen = true; |
240 | } | |
241 | ||
242 | BT_HIDDEN | |
88efd0a7 PP |
243 | bool bt_integer_range_set_unsigned_has_overlaps( |
244 | const struct bt_integer_range_set *range_set) | |
ba38aae7 PP |
245 | { |
246 | uint64_t i, j; | |
247 | bool has_overlap = false; | |
248 | ||
249 | BT_ASSERT(range_set); | |
250 | ||
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); | |
254 | ||
255 | for (j = 0; j < range_set->ranges->len; j++) { | |
256 | const struct bt_integer_range *range_j = | |
88efd0a7 PP |
257 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( |
258 | range_set, j); | |
ba38aae7 PP |
259 | |
260 | if (i == j) { | |
261 | continue; | |
262 | } | |
263 | ||
264 | if (range_i->lower.u <= range_j->upper.u && | |
265 | range_j->lower.u <= range_i->upper.u) { | |
266 | has_overlap = true; | |
267 | goto end; | |
268 | } | |
269 | } | |
270 | } | |
271 | ||
272 | end: | |
273 | return has_overlap; | |
274 | } | |
275 | ||
276 | BT_HIDDEN | |
88efd0a7 PP |
277 | bool bt_integer_range_set_signed_has_overlaps( |
278 | const struct bt_integer_range_set *range_set) | |
ba38aae7 PP |
279 | { |
280 | uint64_t i, j; | |
281 | bool has_overlap = false; | |
282 | ||
283 | BT_ASSERT(range_set); | |
284 | ||
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); | |
288 | ||
289 | for (j = 0; j < range_set->ranges->len; j++) { | |
290 | const struct bt_integer_range *range_j = | |
88efd0a7 PP |
291 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( |
292 | range_set, j); | |
ba38aae7 PP |
293 | |
294 | if (i == j) { | |
295 | continue; | |
296 | } | |
297 | ||
298 | if (range_i->lower.i <= range_j->upper.i && | |
299 | range_j->lower.i <= range_i->upper.i) { | |
300 | has_overlap = true; | |
301 | goto end; | |
302 | } | |
303 | } | |
304 | } | |
305 | ||
306 | end: | |
307 | return has_overlap; | |
308 | } | |
309 | ||
310 | static | |
311 | bool compare_range_sets(const struct bt_integer_range_set *range_set_a, | |
312 | const struct bt_integer_range_set *range_set_b) | |
313 | { | |
314 | uint64_t a_i, b_i; | |
315 | bool is_equal = true; | |
316 | ||
ec4a3354 PP |
317 | BT_ASSERT_DBG(range_set_a); |
318 | BT_ASSERT_DBG(range_set_b); | |
ba38aae7 PP |
319 | |
320 | if (range_set_a == range_set_b) { | |
321 | goto end; | |
322 | } | |
323 | ||
324 | /* | |
325 | * Not super effective for the moment: do a O(N²) compare, also | |
326 | * checking that the sizes match. | |
327 | */ | |
328 | if (range_set_a->ranges->len != range_set_b->ranges->len) { | |
329 | is_equal = false; | |
330 | goto end; | |
331 | } | |
332 | ||
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, | |
336 | a_i); | |
337 | bool b_has_range = false; | |
338 | ||
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( | |
342 | range_set_b, b_i); | |
343 | ||
344 | if (compare_ranges(range_a, range_b)) { | |
345 | b_has_range = true; | |
346 | break; | |
347 | } | |
348 | } | |
349 | ||
350 | if (!b_has_range) { | |
351 | is_equal = false; | |
352 | goto end; | |
353 | } | |
354 | } | |
355 | ||
356 | end: | |
357 | return is_equal; | |
358 | } | |
359 | ||
e1c423f9 | 360 | bt_bool bt_integer_range_set_unsigned_is_equal( |
ba38aae7 PP |
361 | const struct bt_integer_range_set_unsigned *range_set_a, |
362 | const struct bt_integer_range_set_unsigned *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 | ||
e1c423f9 | 370 | bt_bool bt_integer_range_set_signed_is_equal( |
ba38aae7 PP |
371 | const struct bt_integer_range_set_signed *range_set_a, |
372 | const struct bt_integer_range_set_signed *range_set_b) | |
373 | { | |
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); | |
378 | } | |
379 | ||
380 | void bt_integer_range_set_unsigned_get_ref( | |
381 | const struct bt_integer_range_set_unsigned *range_set) | |
382 | { | |
383 | bt_object_get_ref(range_set); | |
384 | } | |
385 | ||
386 | void bt_integer_range_set_unsigned_put_ref( | |
387 | const struct bt_integer_range_set_unsigned *range_set) | |
388 | { | |
389 | bt_object_put_ref(range_set); | |
390 | } | |
391 | ||
88efd0a7 PP |
392 | void bt_integer_range_set_signed_get_ref( |
393 | const struct bt_integer_range_set_signed *range_set) | |
ba38aae7 PP |
394 | { |
395 | bt_object_get_ref(range_set); | |
396 | } | |
397 | ||
88efd0a7 PP |
398 | void bt_integer_range_set_signed_put_ref( |
399 | const struct bt_integer_range_set_signed *range_set) | |
ba38aae7 PP |
400 | { |
401 | bt_object_put_ref(range_set); | |
402 | } |