src/lib/integer-range-set.c

   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
  26 #include <babeltrace2/babeltrace.h>
  27 #include "lib/assert-pre.h"
  28 #include "common/assert.h"
  29 #include "func-status.h"
  30 #include "integer-range-set.h"
  31
  32 uint64_t bt_integer_range_unsigned_get_lower(
  33                 const struct bt_integer_range_unsigned *u_range)
  34 {
  35         const struct bt_integer_range *range = (const void *) u_range;
  36
  37         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  38         return range->lower.u;
  39 }
  40
  41 uint64_t bt_integer_range_unsigned_get_upper(
  42                 const struct bt_integer_range_unsigned *u_range)
  43 {
  44         const struct bt_integer_range *range = (const void *) u_range;
  45
  46         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  47         return range->upper.u;
  48 }
  49
  50 int64_t bt_integer_range_signed_get_lower(
  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_NON_NULL(range, "Integer range");
  56         return range->lower.i;
  57 }
  58
  59 int64_t bt_integer_range_signed_get_upper(
  60                 const struct bt_integer_range_signed *i_range)
  61 {
  62         const struct bt_integer_range *range = (const void *) i_range;
  63
  64         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  65         return range->upper.i;
  66 }
  67
  68 static
  69 bool compare_ranges(const struct bt_integer_range *range_a,
  70                 const struct bt_integer_range *range_b)
  71 {
  72         return range_a->lower.u == range_b->lower.u &&
  73                 range_a->upper.u == range_b->upper.u;
  74 }
  75
  76 bt_bool bt_integer_range_unsigned_is_equal(
  77                 const struct bt_integer_range_unsigned *range_a,
  78                 const struct bt_integer_range_unsigned *range_b)
  79 {
  80         BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A");
  81         BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B");
  82         return (bt_bool) compare_ranges((const void *) range_a,
  83                 (const void *) range_b);
  84 }
  85
  86 bt_bool bt_integer_range_signed_is_equal(
  87                 const struct bt_integer_range_signed *range_a,
  88                 const struct bt_integer_range_signed *range_b)
  89 {
  90         BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A");
  91         BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B");
  92         return (bt_bool) compare_ranges((const void *) range_a,
  93                 (const void *) range_b);
  94 }
  95
  96 uint64_t bt_integer_range_set_get_range_count(
  97                 const bt_integer_range_set *range_set)
  98 {
  99         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
 100         return (uint64_t) range_set->ranges->len;
 101 }
 102
 103 const struct bt_integer_range_unsigned *
 104 bt_integer_range_set_unsigned_borrow_range_by_index_const(
 105                 const bt_integer_range_set_unsigned *u_range_set,
 106                 uint64_t index)
 107 {
 108         const struct bt_integer_range_set *range_set =
 109                 (const void *) u_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 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_NON_NULL(range_set, "Integer 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 struct bt_integer_range_set_unsigned *bt_integer_range_set_unsigned_create(void)
 179 {
 180         return (void *) create_range_set();
 181 }
 182
 183 struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void)
 184 {
 185         return (void *) create_range_set();
 186 }
 187
 188 static
 189 void add_range_to_range_set(struct bt_integer_range_set *range_set,
 190                 uint64_t u_lower, uint64_t u_upper)
 191 {
 192         struct bt_integer_range range = {
 193                 .lower.u = u_lower,
 194                 .upper.u = u_upper,
 195         };
 196
 197         BT_ASSERT_PRE_NON_NULL(range_set, "Integer range set");
 198         BT_ASSERT_PRE_DEV_HOT(range_set, "Integer range set", ": %!+R",
 199                 range_set);
 200         g_array_append_val(range_set->ranges, range);
 201         BT_LIB_LOGD("Added integer range to integer range set: "
 202                 "%![range-set-]+R, lower-unsigned=%" PRIu64 ", "
 203                 "upper-unsigned=%" PRIu64, range_set, u_lower, u_upper);
 204 }
 205
 206 enum bt_integer_range_set_add_range_status
 207 bt_integer_range_set_unsigned_add_range(
 208                 struct bt_integer_range_set_unsigned *range_set,
 209                 uint64_t lower, uint64_t upper)
 210 {
 211         BT_ASSERT_PRE(lower <= upper,
 212                 "Range's upper bound is less than lower bound: "
 213                 "upper=%" PRIu64 ", lower=%" PRIu64, lower, upper);
 214         add_range_to_range_set((void *) range_set, lower, upper);
 215         return BT_FUNC_STATUS_OK;
 216 }
 217
 218 enum bt_integer_range_set_add_range_status
 219 bt_integer_range_set_signed_add_range(
 220                 struct bt_integer_range_set_signed *range_set,
 221                 int64_t lower, int64_t upper)
 222 {
 223         BT_ASSERT_PRE(lower <= upper,
 224                 "Range's upper bound is less than lower bound: "
 225                 "upper=%" PRId64 ", lower=%" PRId64, lower, upper);
 226         add_range_to_range_set((void *) range_set,
 227                 (int64_t) lower, (int64_t) upper);
 228         return BT_FUNC_STATUS_OK;
 229 }
 230
 231 BT_HIDDEN
 232 void _bt_integer_range_set_freeze(const struct bt_integer_range_set *range_set)
 233 {
 234         BT_ASSERT(range_set);
 235         BT_LIB_LOGD("Freezing integer range set: %!+R", range_set);
 236         ((struct bt_integer_range_set *) range_set)->frozen = true;
 237 }
 238
 239 BT_HIDDEN
 240 bool bt_integer_range_set_unsigned_has_overlaps(
 241                 const struct bt_integer_range_set *range_set)
 242 {
 243         uint64_t i, j;
 244         bool has_overlap = false;
 245
 246         BT_ASSERT(range_set);
 247
 248         for (i = 0; i < range_set->ranges->len; i++) {
 249                 const struct bt_integer_range *range_i =
 250                         BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i);
 251
 252                 for (j = 0; j < range_set->ranges->len; j++) {
 253                         const struct bt_integer_range *range_j =
 254                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
 255                                         range_set, j);
 256
 257                         if (i == j) {
 258                                 continue;
 259                         }
 260
 261                         if (range_i->lower.u <= range_j->upper.u &&
 262                                         range_j->lower.u <= range_i->upper.u) {
 263                                 has_overlap = true;
 264                                 goto end;
 265                         }
 266                 }
 267         }
 268
 269 end:
 270         return has_overlap;
 271 }
 272
 273 BT_HIDDEN
 274 bool bt_integer_range_set_signed_has_overlaps(
 275                 const struct bt_integer_range_set *range_set)
 276 {
 277         uint64_t i, j;
 278         bool has_overlap = false;
 279
 280         BT_ASSERT(range_set);
 281
 282         for (i = 0; i < range_set->ranges->len; i++) {
 283                 const struct bt_integer_range *range_i =
 284                         BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i);
 285
 286                 for (j = 0; j < range_set->ranges->len; j++) {
 287                         const struct bt_integer_range *range_j =
 288                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
 289                                         range_set, j);
 290
 291                         if (i == j) {
 292                                 continue;
 293                         }
 294
 295                         if (range_i->lower.i <= range_j->upper.i &&
 296                                         range_j->lower.i <= range_i->upper.i) {
 297                                 has_overlap = true;
 298                                 goto end;
 299                         }
 300                 }
 301         }
 302
 303 end:
 304         return has_overlap;
 305 }
 306
 307 static
 308 bool compare_range_sets(const struct bt_integer_range_set *range_set_a,
 309                 const struct bt_integer_range_set *range_set_b)
 310 {
 311         uint64_t a_i, b_i;
 312         bool is_equal = true;
 313
 314         BT_ASSERT_DBG(range_set_a);
 315         BT_ASSERT_DBG(range_set_b);
 316
 317         if (range_set_a == range_set_b) {
 318                 goto end;
 319         }
 320
 321         /*
 322          * Not super effective for the moment: do a O(N²) compare, also
 323          * checking that the sizes match.
 324          */
 325         if (range_set_a->ranges->len != range_set_b->ranges->len) {
 326                 is_equal = false;
 327                 goto end;
 328         }
 329
 330         for (a_i = 0; a_i < range_set_a->ranges->len; a_i++) {
 331                 const struct bt_integer_range *range_a =
 332                         BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set_a,
 333                                 a_i);
 334                 bool b_has_range = false;
 335
 336                 for (b_i = 0; b_i < range_set_b->ranges->len; b_i++) {
 337                         const struct bt_integer_range *range_b =
 338                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
 339                                         range_set_b, b_i);
 340
 341                         if (compare_ranges(range_a, range_b)) {
 342                                 b_has_range = true;
 343                                 break;
 344                         }
 345                 }
 346
 347                 if (!b_has_range) {
 348                         is_equal = false;
 349                         goto end;
 350                 }
 351         }
 352
 353 end:
 354         return is_equal;
 355 }
 356
 357 bt_bool bt_integer_range_set_unsigned_is_equal(
 358                 const struct bt_integer_range_set_unsigned *range_set_a,
 359                 const struct bt_integer_range_set_unsigned *range_set_b)
 360 {
 361         BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A");
 362         BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B");
 363         return (bt_bool) compare_range_sets((const void *) range_set_a,
 364                 (const void *) range_set_b);
 365 }
 366
 367 bt_bool bt_integer_range_set_signed_is_equal(
 368                 const struct bt_integer_range_set_signed *range_set_a,
 369                 const struct bt_integer_range_set_signed *range_set_b)
 370 {
 371         BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A");
 372         BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B");
 373         return (bt_bool) compare_range_sets((const void *) range_set_a,
 374                 (const void *) range_set_b);
 375 }
 376
 377 void bt_integer_range_set_unsigned_get_ref(
 378                 const struct bt_integer_range_set_unsigned *range_set)
 379 {
 380         bt_object_get_ref(range_set);
 381 }
 382
 383 void bt_integer_range_set_unsigned_put_ref(
 384                 const struct bt_integer_range_set_unsigned *range_set)
 385 {
 386         bt_object_put_ref(range_set);
 387 }
 388
 389 void bt_integer_range_set_signed_get_ref(
 390                 const struct bt_integer_range_set_signed *range_set)
 391 {
 392         bt_object_get_ref(range_set);
 393 }
 394
 395 void bt_integer_range_set_signed_put_ref(
 396                 const struct bt_integer_range_set_signed *range_set)
 397 {
 398         bt_object_put_ref(range_set);
 399 }