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 <stdbool.h>
  27
  28 #include <babeltrace2/babeltrace.h>
  29
  30 #include "lib/assert-pre.h"
  31 #include "common/assert.h"
  32 #include "func-status.h"
  33 #include "integer-range-set.h"
  34
  35 uint64_t bt_integer_range_unsigned_get_lower(
  36                 const struct bt_integer_range_unsigned *u_range)
  37 {
  38         const struct bt_integer_range *range = (const void *) u_range;
  39
  40         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  41         return range->lower.u;
  42 }
  43
  44 uint64_t bt_integer_range_unsigned_get_upper(
  45                 const struct bt_integer_range_unsigned *u_range)
  46 {
  47         const struct bt_integer_range *range = (const void *) u_range;
  48
  49         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  50         return range->upper.u;
  51 }
  52
  53 int64_t bt_integer_range_signed_get_lower(
  54                 const struct bt_integer_range_signed *i_range)
  55 {
  56         const struct bt_integer_range *range = (const void *) i_range;
  57
  58         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  59         return range->lower.i;
  60 }
  61
  62 int64_t bt_integer_range_signed_get_upper(
  63                 const struct bt_integer_range_signed *i_range)
  64 {
  65         const struct bt_integer_range *range = (const void *) i_range;
  66
  67         BT_ASSERT_PRE_DEV_NON_NULL(range, "Integer range");
  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
  79 bt_bool bt_integer_range_unsigned_is_equal(
  80                 const struct bt_integer_range_unsigned *range_a,
  81                 const struct bt_integer_range_unsigned *range_b)
  82 {
  83         BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A");
  84         BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B");
  85         return (bt_bool) compare_ranges((const void *) range_a,
  86                 (const void *) range_b);
  87 }
  88
  89 bt_bool bt_integer_range_signed_is_equal(
  90                 const struct bt_integer_range_signed *range_a,
  91                 const struct bt_integer_range_signed *range_b)
  92 {
  93         BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Integer range A");
  94         BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Integer range B");
  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 {
 102         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
 103         return (uint64_t) range_set->ranges->len;
 104 }
 105
 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)
 110 {
 111         const struct bt_integer_range_set *range_set =
 112                 (const void *) u_range_set;
 113
 114         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
 115         BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len);
 116         return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set,
 117                 index);
 118 }
 119
 120 const struct bt_integer_range_signed *
 121 bt_integer_range_set_signed_borrow_range_by_index_const(
 122                 const bt_integer_range_set_signed *i_range_set, uint64_t index)
 123 {
 124         const struct bt_integer_range_set *range_set =
 125                 (const void *) i_range_set;
 126
 127         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Integer range set");
 128         BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len);
 129         return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set,
 130                 index);
 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
 138         BT_LIB_LOGD("Destroying integer range set: %!+R", range_set);
 139
 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 {
 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);
 155
 156         if (!range_set) {
 157                 BT_LIB_LOGE_APPEND_CAUSE(
 158                         "Failed to allocate one integer range set.");
 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(
 167                         "Failed to allocate integer range set's range array.");
 168                 goto error;
 169         }
 170
 171         BT_LOGD_STR("Created empty integer range set.");
 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 {
 183         BT_ASSERT_PRE_NO_ERROR();
 184
 185         return (void *) create_range_set();
 186 }
 187
 188 struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void)
 189 {
 190         BT_ASSERT_PRE_NO_ERROR();
 191
 192         return (void *) create_range_set();
 193 }
 194
 195 static
 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
 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);
 207         g_array_append_val(range_set->ranges, range);
 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);
 211 }
 212
 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 <= 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 enum bt_integer_range_set_add_range_status
 227 bt_integer_range_set_signed_add_range(
 228                 struct bt_integer_range_set_signed *range_set,
 229                 int64_t lower, int64_t upper)
 230 {
 231         BT_ASSERT_PRE_NO_ERROR();
 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);
 244         BT_LIB_LOGD("Freezing integer range set: %!+R", range_set);
 245         ((struct bt_integer_range_set *) range_set)->frozen = true;
 246 }
 247
 248 BT_HIDDEN
 249 bool bt_integer_range_set_unsigned_has_overlaps(
 250                 const struct bt_integer_range_set *range_set)
 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 =
 263                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
 264                                         range_set, j);
 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
 283 bool bt_integer_range_set_signed_has_overlaps(
 284                 const struct bt_integer_range_set *range_set)
 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 =
 297                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
 298                                         range_set, j);
 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
 323         BT_ASSERT_DBG(range_set_a);
 324         BT_ASSERT_DBG(range_set_b);
 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
 366 bt_bool bt_integer_range_set_unsigned_is_equal(
 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
 376 bt_bool bt_integer_range_set_signed_is_equal(
 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
 398 void bt_integer_range_set_signed_get_ref(
 399                 const struct bt_integer_range_set_signed *range_set)
 400 {
 401         bt_object_get_ref(range_set);
 402 }
 403
 404 void bt_integer_range_set_signed_put_ref(
 405                 const struct bt_integer_range_set_signed *range_set)
 406 {
 407         bt_object_put_ref(range_set);
 408 }