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(const struct bt_integer_range_unsigned *u_range)
  33 {
  34         const struct bt_integer_range *range = (const void *) u_range;
  35
  36         BT_ASSERT_PRE_DEV_NON_NULL(range, "Range");
  37         return range->lower.u;
  38 }
  39
  40 uint64_t bt_integer_range_unsigned_get_upper(const struct bt_integer_range_unsigned *u_range)
  41 {
  42         const struct bt_integer_range *range = (const void *) u_range;
  43
  44         BT_ASSERT_PRE_DEV_NON_NULL(range, "Range");
  45         return range->upper.u;
  46 }
  47
  48 int64_t bt_integer_range_signed_get_lower(const struct bt_integer_range_signed *i_range)
  49 {
  50         const struct bt_integer_range *range = (const void *) i_range;
  51
  52         BT_ASSERT_PRE_DEV_NON_NULL(range, "Range");
  53         return range->lower.i;
  54 }
  55
  56 int64_t bt_integer_range_signed_get_upper(const struct bt_integer_range_signed *i_range)
  57 {
  58         const struct bt_integer_range *range = (const void *) i_range;
  59
  60         BT_ASSERT_PRE_DEV_NON_NULL(range, "Range");
  61         return range->upper.i;
  62 }
  63
  64 static
  65 bool compare_ranges(const struct bt_integer_range *range_a,
  66                 const struct bt_integer_range *range_b)
  67 {
  68         return range_a->lower.u == range_b->lower.u &&
  69                 range_a->upper.u == range_b->upper.u;
  70 }
  71
  72 bt_bool bt_integer_range_unsigned_compare(
  73                 const struct bt_integer_range_unsigned *range_a,
  74                 const struct bt_integer_range_unsigned *range_b)
  75 {
  76         BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Range A");
  77         BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Range B");
  78         return (bt_bool) compare_ranges((const void *) range_a,
  79                 (const void *) range_b);
  80 }
  81
  82 bt_bool bt_integer_range_signed_compare(
  83                 const struct bt_integer_range_signed *range_a,
  84                 const struct bt_integer_range_signed *range_b)
  85 {
  86         BT_ASSERT_PRE_DEV_NON_NULL(range_a, "Range A");
  87         BT_ASSERT_PRE_DEV_NON_NULL(range_b, "Range B");
  88         return (bt_bool) compare_ranges((const void *) range_a,
  89                 (const void *) range_b);
  90 }
  91
  92 uint64_t bt_integer_range_set_get_range_count(
  93                 const bt_integer_range_set *range_set)
  94 {
  95         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Range set");
  96         return (uint64_t) range_set->ranges->len;
  97 }
  98
  99 const struct bt_integer_range_unsigned *bt_integer_range_set_unsigned_borrow_range_by_index_const(
 100                 const bt_integer_range_set_unsigned *u_range_set, uint64_t index)
 101 {
 102         const struct bt_integer_range_set *range_set = (const void *) u_range_set;
 103
 104         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "Range set");
 105         BT_ASSERT_PRE_DEV_VALID_INDEX(index, range_set->ranges->len);
 106         return (const void *) BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, index);
 107 }
 108
 109 const struct bt_integer_range_signed *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 = (const void *) i_range_set;
 113
 114         BT_ASSERT_PRE_DEV_NON_NULL(range_set, "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, index);
 117 }
 118
 119 static
 120 void destroy_range_set(struct bt_object *obj)
 121 {
 122         struct bt_integer_range_set *range_set = (void *) obj;
 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 = g_new0(struct bt_integer_range_set, 1);
 136
 137         if (!range_set) {
 138                 BT_LIB_LOGE_APPEND_CAUSE("Failed to allocate one range set.");
 139                 goto error;
 140         }
 141
 142         bt_object_init_shared(&range_set->base, destroy_range_set);
 143         range_set->ranges = g_array_new(FALSE, TRUE,
 144                 sizeof(struct bt_integer_range));
 145         if (!range_set->ranges) {
 146                 BT_LIB_LOGE_APPEND_CAUSE(
 147                         "Failed to allocate range set's range array.");
 148                 goto error;
 149         }
 150
 151         goto end;
 152
 153 error:
 154         BT_OBJECT_PUT_REF_AND_RESET(range_set);
 155
 156 end:
 157         return range_set;
 158 }
 159
 160 struct bt_integer_range_set_unsigned *bt_integer_range_set_unsigned_create(void)
 161 {
 162         return (void *) create_range_set();
 163 }
 164
 165 struct bt_integer_range_set_signed *bt_integer_range_set_signed_create(void)
 166 {
 167         return (void *) create_range_set();
 168 }
 169
 170 void add_range_to_range_set(struct bt_integer_range_set *range_set,
 171                 uint64_t u_lower, uint64_t u_upper)
 172 {
 173         struct bt_integer_range range = {
 174                 .lower.u = u_lower,
 175                 .upper.u = u_upper,
 176         };
 177
 178         BT_ASSERT_PRE_NON_NULL(range_set, "Range set");
 179         BT_ASSERT_PRE_DEV_HOT(range_set, "Range set", ": addr=%p", range_set);
 180         g_array_append_val(range_set->ranges, range);
 181         BT_LIB_LOGD("Added range to range set: "
 182                 "range-set-addr=%p, lower-unsigned=%" PRIu64 ", "
 183                 "upper-unsigned=%" PRIu64,
 184                 range_set, u_lower, u_upper);
 185 }
 186
 187 enum bt_integer_range_set_add_range_status bt_integer_range_set_unsigned_add_range(
 188                 struct bt_integer_range_set_unsigned *range_set,
 189                 uint64_t lower, uint64_t upper)
 190 {
 191         BT_ASSERT_PRE(lower <= upper,
 192                 "Range's upper bound is less than lower bound: "
 193                 "upper=%" PRIu64 ", lower=%" PRIu64, lower, upper);
 194         add_range_to_range_set((void *) range_set, lower, upper);
 195         return BT_FUNC_STATUS_OK;
 196 }
 197
 198 enum bt_integer_range_set_add_range_status bt_integer_range_set_signed_add_range(
 199                 struct bt_integer_range_set_signed *range_set,
 200                 int64_t lower, int64_t upper)
 201 {
 202         BT_ASSERT_PRE(lower <= upper,
 203                 "Range's upper bound is less than lower bound: "
 204                 "upper=%" PRId64 ", lower=%" PRId64, lower, upper);
 205         add_range_to_range_set((void *) range_set,
 206                 (int64_t) lower, (int64_t) upper);
 207         return BT_FUNC_STATUS_OK;
 208 }
 209
 210 BT_HIDDEN
 211 void _bt_integer_range_set_freeze(const struct bt_integer_range_set *range_set)
 212 {
 213         BT_ASSERT(range_set);
 214         BT_LIB_LOGD("Freezing range set: addr=%p", range_set);
 215         ((struct bt_integer_range_set *) range_set)->frozen = true;
 216 }
 217
 218 BT_HIDDEN
 219 bool bt_integer_range_set_unsigned_has_overlaps(const struct bt_integer_range_set *range_set)
 220 {
 221         uint64_t i, j;
 222         bool has_overlap = false;
 223
 224         BT_ASSERT(range_set);
 225
 226         for (i = 0; i < range_set->ranges->len; i++) {
 227                 const struct bt_integer_range *range_i =
 228                         BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i);
 229
 230                 for (j = 0; j < range_set->ranges->len; j++) {
 231                         const struct bt_integer_range *range_j =
 232                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, j);
 233
 234                         if (i == j) {
 235                                 continue;
 236                         }
 237
 238                         if (range_i->lower.u <= range_j->upper.u &&
 239                                         range_j->lower.u <= range_i->upper.u) {
 240                                 has_overlap = true;
 241                                 goto end;
 242                         }
 243                 }
 244         }
 245
 246 end:
 247         return has_overlap;
 248 }
 249
 250 BT_HIDDEN
 251 bool bt_integer_range_set_signed_has_overlaps(const struct bt_integer_range_set *range_set)
 252 {
 253         uint64_t i, j;
 254         bool has_overlap = false;
 255
 256         BT_ASSERT(range_set);
 257
 258         for (i = 0; i < range_set->ranges->len; i++) {
 259                 const struct bt_integer_range *range_i =
 260                         BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, i);
 261
 262                 for (j = 0; j < range_set->ranges->len; j++) {
 263                         const struct bt_integer_range *range_j =
 264                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set, j);
 265
 266                         if (i == j) {
 267                                 continue;
 268                         }
 269
 270                         if (range_i->lower.i <= range_j->upper.i &&
 271                                         range_j->lower.i <= range_i->upper.i) {
 272                                 has_overlap = true;
 273                                 goto end;
 274                         }
 275                 }
 276         }
 277
 278 end:
 279         return has_overlap;
 280 }
 281
 282 static
 283 bool compare_range_sets(const struct bt_integer_range_set *range_set_a,
 284                 const struct bt_integer_range_set *range_set_b)
 285 {
 286         uint64_t a_i, b_i;
 287         bool is_equal = true;
 288
 289         BT_ASSERT(range_set_a);
 290         BT_ASSERT(range_set_b);
 291
 292         if (range_set_a == range_set_b) {
 293                 goto end;
 294         }
 295
 296         /*
 297          * Not super effective for the moment: do a O(N²) compare, also
 298          * checking that the sizes match.
 299          */
 300         if (range_set_a->ranges->len != range_set_b->ranges->len) {
 301                 is_equal = false;
 302                 goto end;
 303         }
 304
 305         for (a_i = 0; a_i < range_set_a->ranges->len; a_i++) {
 306                 const struct bt_integer_range *range_a =
 307                         BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(range_set_a,
 308                                 a_i);
 309                 bool b_has_range = false;
 310
 311                 for (b_i = 0; b_i < range_set_b->ranges->len; b_i++) {
 312                         const struct bt_integer_range *range_b =
 313                                 BT_INTEGER_RANGE_SET_RANGE_AT_INDEX(
 314                                         range_set_b, b_i);
 315
 316                         if (compare_ranges(range_a, range_b)) {
 317                                 b_has_range = true;
 318                                 break;
 319                         }
 320                 }
 321
 322                 if (!b_has_range) {
 323                         is_equal = false;
 324                         goto end;
 325                 }
 326         }
 327
 328 end:
 329         return is_equal;
 330 }
 331
 332 bt_bool bt_integer_range_set_unsigned_compare(
 333                 const struct bt_integer_range_set_unsigned *range_set_a,
 334                 const struct bt_integer_range_set_unsigned *range_set_b)
 335 {
 336         BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A");
 337         BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B");
 338         return (bt_bool) compare_range_sets((const void *) range_set_a,
 339                 (const void *) range_set_b);
 340 }
 341
 342 bt_bool bt_integer_range_set_signed_compare(
 343                 const struct bt_integer_range_set_signed *range_set_a,
 344                 const struct bt_integer_range_set_signed *range_set_b)
 345 {
 346         BT_ASSERT_PRE_DEV_NON_NULL(range_set_a, "Range set A");
 347         BT_ASSERT_PRE_DEV_NON_NULL(range_set_b, "Range set B");
 348         return (bt_bool) compare_range_sets((const void *) range_set_a,
 349                 (const void *) range_set_b);
 350 }
 351
 352 void bt_integer_range_set_unsigned_get_ref(
 353                 const struct bt_integer_range_set_unsigned *range_set)
 354 {
 355         bt_object_get_ref(range_set);
 356 }
 357
 358 void bt_integer_range_set_unsigned_put_ref(
 359                 const struct bt_integer_range_set_unsigned *range_set)
 360 {
 361         bt_object_put_ref(range_set);
 362 }
 363
 364 void bt_integer_range_set_signed_get_ref(const struct bt_integer_range_set_signed *range_set)
 365 {
 366         bt_object_get_ref(range_set);
 367 }
 368
 369 void bt_integer_range_set_signed_put_ref(const struct bt_integer_range_set_signed *range_set)
 370 {
 371         bt_object_put_ref(range_set);
 372 }