Commit | Line | Data |
---|---|---|
fb91c0ef 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 | ||
c4f23e30 FD |
26 | #include <stdbool.h> |
27 | ||
fb91c0ef | 28 | #include <babeltrace2/babeltrace.h> |
c4f23e30 | 29 | |
fb91c0ef PP |
30 | #include "lib/assert-pre.h" |
31 | #include "common/assert.h" | |
32 | #include "func-status.h" | |
33 | #include "integer-range-set.h" | |
34 | ||
6769570a PP |
35 | uint64_t bt_integer_range_unsigned_get_lower( |
36 | const struct bt_integer_range_unsigned *u_range) | |
fb91c0ef PP |
37 | { |
38 | const struct bt_integer_range *range = (const void *) u_range; | |
39 | ||
6769570a | 40 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
41 | return range->lower.u; |
42 | } | |
43 | ||
6769570a PP |
44 | uint64_t bt_integer_range_unsigned_get_upper( |
45 | const struct bt_integer_range_unsigned *u_range) | |
fb91c0ef PP |
46 | { |
47 | const struct bt_integer_range *range = (const void *) u_range; | |
48 | ||
6769570a | 49 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
50 | return range->upper.u; |
51 | } | |
52 | ||
6769570a PP |
53 | int64_t bt_integer_range_signed_get_lower( |
54 | const struct bt_integer_range_signed *i_range) | |
fb91c0ef PP |
55 | { |
56 | const struct bt_integer_range *range = (const void *) i_range; | |
57 | ||
6769570a | 58 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef PP |
59 | return range->lower.i; |
60 | } | |
61 | ||
6769570a PP |
62 | int64_t bt_integer_range_signed_get_upper( |
63 | const struct bt_integer_range_signed *i_range) | |
fb91c0ef PP |
64 | { |
65 | const struct bt_integer_range *range = (const void *) i_range; | |
66 | ||
6769570a | 67 | BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range"); |
fb91c0ef 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 | ||
cd933d89 | 79 | bt_bool bt_integer_range_unsigned_is_equal( |
fb91c0ef PP |
80 | const struct bt_integer_range_unsigned *range_a, |
81 | const struct bt_integer_range_unsigned *range_b) | |
82 | { | |
6769570a 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"); | |
fb91c0ef PP |
85 | return (bt_bool) compare_ranges((const void *) range_a, |
86 | (const void *) range_b); | |
87 | } | |
88 | ||
cd933d89 | 89 | bt_bool bt_integer_range_signed_is_equal( |
fb91c0ef PP |
90 | const struct bt_integer_range_signed *range_a, |
91 | const struct bt_integer_range_signed *range_b) | |
92 | { | |
6769570a 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"); | |
fb91c0ef 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 | { | |
6769570a | 102 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
fb91c0ef PP |
103 | return (uint64_t) range_set->ranges->len; |
104 | } | |
105 | ||
6769570a 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) | |
fb91c0ef | 110 | { |
6769570a PP |
111 | const struct bt_integer_range_set *range_set = |
112 | (const void *) u_range_set; | |
fb91c0ef | 113 | |
6769570a | 114 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
fb91c0ef | 115 | BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len); |
6769570a PP |
116 | return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, |
117 | index); | |
fb91c0ef PP |
118 | } |
119 | ||
6769570a PP |
120 | const struct bt_integer_range_signed * |
121 | bt_integer_range_set_signed_borrow_range_by_index_const( | |
fb91c0ef PP |
122 | const bt_integer_range_set_signed *i_range_set, uint64_t index) |
123 | { | |
6769570a PP |
124 | const struct bt_integer_range_set *range_set = |
125 | (const void *) i_range_set; | |
fb91c0ef | 126 | |
6769570a | 127 | BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set"); |
fb91c0ef | 128 | BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len); |
6769570a PP |
129 | return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, |
130 | index); | |
fb91c0ef 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 | ||
6769570a PP |
138 | BT_LIB_LOGD("Destroying integer range set: %!+R", range_set); |
139 | ||
fb91c0ef 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 | { | |
6769570a 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); | |
fb91c0ef PP |
155 | |
156 | if (!range_set) { | |
6769570a PP |
157 | BT_LIB_LOGE_APPEND_CAUSE( |
158 | "Failed to allocate one integer range set."); | |
fb91c0ef 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( | |
6769570a | 167 | "Failed to allocate integer range set's range array."); |
fb91c0ef PP |
168 | goto error; |
169 | } | |
170 | ||
6769570a | 171 | BT_LOGD_STR("Created empty integer range set."); |
fb91c0ef 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 | { | |
17f3083a SM |
183 | BT_ASSERT_PRE_NO_ERROR(); |
184 | ||
fb91c0ef PP |
185 | return (void *) create_range_set(); |
186 | } | |
187 | ||
188 | struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void) | |
189 | { | |
17f3083a SM |
190 | BT_ASSERT_PRE_NO_ERROR(); |
191 | ||
fb91c0ef PP |
192 | return (void *) create_range_set(); |
193 | } | |
194 | ||
7c7301d5 | 195 | static |
fb91c0ef PP |
196 | void add_range_to_range_set(struct bt_integer_range_set *range_set, |
197 | uint64_t u_lower, uint64_t u_upper) | |
198 | { | |
199 | struct bt_integer_range range = { | |
200 | .lower.u = u_lower, | |
201 | .upper.u = u_upper, | |
202 | }; | |
203 | ||
6769570a PP |
204 | BT_ASSERT_PRE_NON_NULL(range_set, "Integer range set"); |
205 | BT_ASSERT_PRE_DEV_HOT(range_set, "Integer range set", ": %!+R", | |
206 | range_set); | |
fb91c0ef | 207 | g_array_append_val(range_set->ranges, range); |
6769570a PP |
208 | BT_LIB_LOGD("Added integer range to integer range set: " |
209 | "%![range-set-]+R, lower-unsigned=%" PRIu64 ", " | |
210 | "upper-unsigned=%" PRIu64, range_set, u_lower, u_upper); | |
fb91c0ef PP |
211 | } |
212 | ||
6769570a PP |
213 | enum bt_integer_range_set_add_range_status |
214 | bt_integer_range_set_unsigned_add_range( | |
fb91c0ef PP |
215 | struct bt_integer_range_set_unsigned *range_set, |
216 | uint64_t lower, uint64_t upper) | |
217 | { | |
17f3083a | 218 | BT_ASSERT_PRE_NO_ERROR(); |
fb91c0ef PP |
219 | BT_ASSERT_PRE(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 | ||
6769570a PP |
226 | enum bt_integer_range_set_add_range_status |
227 | bt_integer_range_set_signed_add_range( | |
fb91c0ef PP |
228 | struct bt_integer_range_set_signed *range_set, |
229 | int64_t lower, int64_t upper) | |
230 | { | |
17f3083a | 231 | BT_ASSERT_PRE_NO_ERROR(); |
fb91c0ef PP |
232 | BT_ASSERT_PRE(lower <= upper, |
233 | "Range's upper bound is less than lower bound: " | |
234 | "upper=%" PRId64 ", lower=%" PRId64, lower, upper); | |
235 | add_range_to_range_set((void *) range_set, | |
236 | (int64_t) lower, (int64_t) upper); | |
237 | return BT_FUNC_STATUS_OK; | |
238 | } | |
239 | ||
240 | BT_HIDDEN | |
241 | void _bt_integer_range_set_freeze(const struct bt_integer_range_set *range_set) | |
242 | { | |
243 | BT_ASSERT(range_set); | |
6769570a | 244 | BT_LIB_LOGD("Freezing integer range set: %!+R", range_set); |
fb91c0ef PP |
245 | ((struct bt_integer_range_set *) range_set)->frozen = true; |
246 | } | |
247 | ||
248 | BT_HIDDEN | |
6769570a PP |
249 | bool bt_integer_range_set_unsigned_has_overlaps( |
250 | const struct bt_integer_range_set *range_set) | |
fb91c0ef PP |
251 | { |
252 | uint64_t i, j; | |
253 | bool has_overlap = false; | |
254 | ||
255 | BT_ASSERT(range_set); | |
256 | ||
257 | for (i = 0; i < range_set->ranges->len; i++) { | |
258 | const struct bt_integer_range *range_i = | |
259 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i); | |
260 | ||
261 | for (j = 0; j < range_set->ranges->len; j++) { | |
262 | const struct bt_integer_range *range_j = | |
6769570a PP |
263 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( |
264 | range_set, j); | |
fb91c0ef PP |
265 | |
266 | if (i == j) { | |
267 | continue; | |
268 | } | |
269 | ||
270 | if (range_i->lower.u <= range_j->upper.u && | |
271 | range_j->lower.u <= range_i->upper.u) { | |
272 | has_overlap = true; | |
273 | goto end; | |
274 | } | |
275 | } | |
276 | } | |
277 | ||
278 | end: | |
279 | return has_overlap; | |
280 | } | |
281 | ||
282 | BT_HIDDEN | |
6769570a PP |
283 | bool bt_integer_range_set_signed_has_overlaps( |
284 | const struct bt_integer_range_set *range_set) | |
fb91c0ef PP |
285 | { |
286 | uint64_t i, j; | |
287 | bool has_overlap = false; | |
288 | ||
289 | BT_ASSERT(range_set); | |
290 | ||
291 | for (i = 0; i < range_set->ranges->len; i++) { | |
292 | const struct bt_integer_range *range_i = | |
293 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i); | |
294 | ||
295 | for (j = 0; j < range_set->ranges->len; j++) { | |
296 | const struct bt_integer_range *range_j = | |
6769570a PP |
297 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( |
298 | range_set, j); | |
fb91c0ef PP |
299 | |
300 | if (i == j) { | |
301 | continue; | |
302 | } | |
303 | ||
304 | if (range_i->lower.i <= range_j->upper.i && | |
305 | range_j->lower.i <= range_i->upper.i) { | |
306 | has_overlap = true; | |
307 | goto end; | |
308 | } | |
309 | } | |
310 | } | |
311 | ||
312 | end: | |
313 | return has_overlap; | |
314 | } | |
315 | ||
316 | static | |
317 | bool compare_range_sets(const struct bt_integer_range_set *range_set_a, | |
318 | const struct bt_integer_range_set *range_set_b) | |
319 | { | |
320 | uint64_t a_i, b_i; | |
321 | bool is_equal = true; | |
322 | ||
98b15851 PP |
323 | BT_ASSERT_DBG(range_set_a); |
324 | BT_ASSERT_DBG(range_set_b); | |
fb91c0ef PP |
325 | |
326 | if (range_set_a == range_set_b) { | |
327 | goto end; | |
328 | } | |
329 | ||
330 | /* | |
331 | * Not super effective for the moment: do a O(N²) compare, also | |
332 | * checking that the sizes match. | |
333 | */ | |
334 | if (range_set_a->ranges->len != range_set_b->ranges->len) { | |
335 | is_equal = false; | |
336 | goto end; | |
337 | } | |
338 | ||
339 | for (a_i = 0; a_i < range_set_a->ranges->len; a_i++) { | |
340 | const struct bt_integer_range *range_a = | |
341 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set_a, | |
342 | a_i); | |
343 | bool b_has_range = false; | |
344 | ||
345 | for (b_i = 0; b_i < range_set_b->ranges->len; b_i++) { | |
346 | const struct bt_integer_range *range_b = | |
347 | BT_INTEGER_RANGE_SET_RANGE_AT_INDEX( | |
348 | range_set_b, b_i); | |
349 | ||
350 | if (compare_ranges(range_a, range_b)) { | |
351 | b_has_range = true; | |
352 | break; | |
353 | } | |
354 | } | |
355 | ||
356 | if (!b_has_range) { | |
357 | is_equal = false; | |
358 | goto end; | |
359 | } | |
360 | } | |
361 | ||
362 | end: | |
363 | return is_equal; | |
364 | } | |
365 | ||
cd933d89 | 366 | bt_bool bt_integer_range_set_unsigned_is_equal( |
fb91c0ef PP |
367 | const struct bt_integer_range_set_unsigned *range_set_a, |
368 | const struct bt_integer_range_set_unsigned *range_set_b) | |
369 | { | |
370 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A"); | |
371 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B"); | |
372 | return (bt_bool) compare_range_sets((const void *) range_set_a, | |
373 | (const void *) range_set_b); | |
374 | } | |
375 | ||
cd933d89 | 376 | bt_bool bt_integer_range_set_signed_is_equal( |
fb91c0ef PP |
377 | const struct bt_integer_range_set_signed *range_set_a, |
378 | const struct bt_integer_range_set_signed *range_set_b) | |
379 | { | |
380 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A"); | |
381 | BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B"); | |
382 | return (bt_bool) compare_range_sets((const void *) range_set_a, | |
383 | (const void *) range_set_b); | |
384 | } | |
385 | ||
386 | void bt_integer_range_set_unsigned_get_ref( | |
387 | const struct bt_integer_range_set_unsigned *range_set) | |
388 | { | |
389 | bt_object_get_ref(range_set); | |
390 | } | |
391 | ||
392 | void bt_integer_range_set_unsigned_put_ref( | |
393 | const struct bt_integer_range_set_unsigned *range_set) | |
394 | { | |
395 | bt_object_put_ref(range_set); | |
396 | } | |
397 | ||
6769570a PP |
398 | void bt_integer_range_set_signed_get_ref( |
399 | const struct bt_integer_range_set_signed *range_set) | |
fb91c0ef PP |
400 | { |
401 | bt_object_get_ref(range_set); | |
402 | } | |
403 | ||
6769570a PP |
404 | void bt_integer_range_set_signed_put_ref( |
405 | const struct bt_integer_range_set_signed *range_set) | |
fb91c0ef PP |
406 | { |
407 | bt_object_put_ref(range_set); | |
408 | } |