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