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 }