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