iOS/Pods/Realm/include/core/realm/array_integer.hpp

   1 /*************************************************************************
   2  *
   3  * Copyright 2016 Realm Inc.
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  * http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  *
  17  **************************************************************************/
  18
  19 #ifndef REALM_ARRAY_INTEGER_HPP
  20 #define REALM_ARRAY_INTEGER_HPP
  21
  22 #include <realm/array.hpp>
  23 #include <realm/util/safe_int_ops.hpp>
  24 #include <realm/util/optional.hpp>
  25
  26 namespace realm {
  27
  28 class ArrayInteger : public Array {
  29 public:
  30     typedef int64_t value_type;
  31
  32     explicit ArrayInteger(Allocator&) noexcept;
  33     ~ArrayInteger() noexcept override
  34     {
  35     }
  36
  37     // Disable copying, this is not allowed.
  38     ArrayInteger& operator=(const ArrayInteger&) = delete;
  39     ArrayInteger(const ArrayInteger&) = delete;
  40
  41     void create(Type type = type_Normal, bool context_flag = false);
  42
  43     void add(int64_t value);
  44     void set(size_t ndx, int64_t value);
  45     void set_uint(size_t ndx, uint_fast64_t value) noexcept;
  46     int64_t get(size_t ndx) const noexcept;
  47     uint64_t get_uint(size_t ndx) const noexcept;
  48     static int64_t get(const char* header, size_t ndx) noexcept;
  49     bool compare(const ArrayInteger& a) const noexcept;
  50
  51     /// Add \a diff to the element at the specified index.
  52     void adjust(size_t ndx, int_fast64_t diff);
  53
  54     /// Add \a diff to all the elements in the specified index range.
  55     void adjust(size_t begin, size_t end, int_fast64_t diff);
  56
  57     /// Add signed \a diff to all elements that are greater than, or equal to \a
  58     /// limit.
  59     void adjust_ge(int_fast64_t limit, int_fast64_t diff);
  60
  61     int64_t operator[](size_t ndx) const noexcept
  62     {
  63         return get(ndx);
  64     }
  65     int64_t front() const noexcept;
  66     int64_t back() const noexcept;
  67
  68     size_t lower_bound(int64_t value) const noexcept;
  69     size_t upper_bound(int64_t value) const noexcept;
  70
  71     std::vector<int64_t> to_vector() const;
  72
  73 private:
  74     template <size_t w>
  75     bool minmax(size_t from, size_t to, uint64_t maxdiff, int64_t* min, int64_t* max) const;
  76 };
  77
  78 class ArrayIntNull : public Array {
  79 public:
  80     using value_type = util::Optional<int64_t>;
  81
  82     explicit ArrayIntNull(Allocator&) noexcept;
  83     ~ArrayIntNull() noexcept override;
  84
  85     /// Construct an array of the specified type and size, and return just the
  86     /// reference to the underlying memory. All elements will be initialized to
  87     /// the specified value.
  88     static MemRef create_array(Type, bool context_flag, size_t size, value_type value, Allocator&);
  89     void create(Type = type_Normal, bool context_flag = false);
  90
  91     void init_from_ref(ref_type) noexcept;
  92     void init_from_mem(MemRef) noexcept;
  93     void init_from_parent() noexcept;
  94
  95     size_t size() const noexcept;
  96     bool is_empty() const noexcept;
  97
  98     void insert(size_t ndx, value_type value);
  99     void add(value_type value);
 100     void set(size_t ndx, value_type value) noexcept;
 101     value_type get(size_t ndx) const noexcept;
 102     static value_type get(const char* header, size_t ndx) noexcept;
 103     void get_chunk(size_t ndx, value_type res[8]) const noexcept;
 104     void set_null(size_t ndx) noexcept;
 105     bool is_null(size_t ndx) const noexcept;
 106     int64_t null_value() const noexcept;
 107
 108     value_type operator[](size_t ndx) const noexcept;
 109     value_type front() const noexcept;
 110     value_type back() const noexcept;
 111     void erase(size_t ndx);
 112     void erase(size_t begin, size_t end);
 113     void truncate(size_t size);
 114     void clear();
 115     void set_all_to_zero();
 116
 117     void move(size_t begin, size_t end, size_t dest_begin);
 118     void move_backward(size_t begin, size_t end, size_t dest_end);
 119
 120     size_t lower_bound(int64_t value) const noexcept;
 121     size_t upper_bound(int64_t value) const noexcept;
 122
 123     int64_t sum(size_t start = 0, size_t end = npos) const;
 124     size_t count(int64_t value) const noexcept;
 125     bool maximum(int64_t& result, size_t start = 0, size_t end = npos, size_t* return_ndx = nullptr) const;
 126     bool minimum(int64_t& result, size_t start = 0, size_t end = npos, size_t* return_ndx = nullptr) const;
 127
 128     bool find(int cond, Action action, value_type value, size_t start, size_t end, size_t baseindex,
 129               QueryState<int64_t>* state) const;
 130
 131     template <class cond, Action action, size_t bitwidth, class Callback>
 132     bool find(value_type value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
 133               Callback callback) const;
 134
 135     // This is the one installed into the m_finder slots.
 136     template <class cond, Action action, size_t bitwidth>
 137     bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state) const;
 138
 139     template <class cond, Action action, class Callback>
 140     bool find(value_type value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
 141               Callback callback) const;
 142
 143     // Optimized implementation for release mode
 144     template <class cond, Action action, size_t bitwidth, class Callback>
 145     bool find_optimized(value_type value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
 146                         Callback callback) const;
 147
 148     // Called for each search result
 149     template <Action action, class Callback>
 150     bool find_action(size_t index, value_type value, QueryState<int64_t>* state, Callback callback) const;
 151
 152     template <Action action, class Callback>
 153     bool find_action_pattern(size_t index, uint64_t pattern, QueryState<int64_t>* state, Callback callback) const;
 154
 155     // Wrappers for backwards compatibility and for simple use without
 156     // setting up state initialization etc
 157     template <class cond>
 158     size_t find_first(value_type value, size_t start = 0, size_t end = npos) const;
 159
 160     void find_all(IntegerColumn* result, value_type value, size_t col_offset = 0, size_t begin = 0,
 161                   size_t end = npos) const;
 162
 163
 164     size_t find_first(value_type value, size_t begin = 0, size_t end = npos) const;
 165
 166
 167     // Overwrite Array::bptree_leaf_insert to correctly split nodes.
 168     ref_type bptree_leaf_insert(size_t ndx, value_type value, TreeInsertBase& state);
 169
 170     MemRef slice(size_t offset, size_t slice_size, Allocator& target_alloc) const;
 171
 172     /// Construct a deep copy of the specified slice of this array using the
 173     /// specified target allocator. Subarrays will be cloned.
 174     MemRef slice_and_clone_children(size_t offset, size_t slice_size, Allocator& target_alloc) const;
 175
 176 protected:
 177     void avoid_null_collision(int64_t value);
 178
 179 private:
 180     template <bool find_max>
 181     bool minmax_helper(int64_t& result, size_t start = 0, size_t end = npos, size_t* return_ndx = nullptr) const;
 182
 183     int_fast64_t choose_random_null(int64_t incoming) const;
 184     void replace_nulls_with(int64_t new_null);
 185     bool can_use_as_null(int64_t value) const;
 186 };
 187
 188
 189 // Implementation:
 190
 191 inline ArrayInteger::ArrayInteger(Allocator& allocator) noexcept
 192     : Array(allocator)
 193 {
 194     m_is_inner_bptree_node = false;
 195 }
 196
 197 inline void ArrayInteger::add(int64_t value)
 198 {
 199     Array::add(value);
 200 }
 201
 202 inline int64_t ArrayInteger::get(size_t ndx) const noexcept
 203 {
 204     return Array::get(ndx);
 205 }
 206
 207 inline int64_t ArrayInteger::get(const char* header, size_t ndx) noexcept
 208 {
 209     return Array::get(header, ndx);
 210 }
 211
 212 inline void ArrayInteger::set(size_t ndx, int64_t value)
 213 {
 214     Array::set(ndx, value);
 215 }
 216
 217 inline void ArrayInteger::set_uint(size_t ndx, uint_fast64_t value) noexcept
 218 {
 219     // When a value of a signed type is converted to an unsigned type, the C++
 220     // standard guarantees that negative values are converted from the native
 221     // representation to 2's complement, but the effect of conversions in the
 222     // opposite direction is left unspecified by the
 223     // standard. `realm::util::from_twos_compl()` is used here to perform the
 224     // correct opposite unsigned-to-signed conversion, which reduces to a no-op
 225     // when 2's complement is the native representation of negative values.
 226     set(ndx, util::from_twos_compl<int_fast64_t>(value));
 227 }
 228
 229 inline bool ArrayInteger::compare(const ArrayInteger& a) const noexcept
 230 {
 231     if (a.size() != size())
 232         return false;
 233
 234     for (size_t i = 0; i < size(); ++i) {
 235         if (get(i) != a.get(i))
 236             return false;
 237     }
 238
 239     return true;
 240 }
 241
 242 inline int64_t ArrayInteger::front() const noexcept
 243 {
 244     return Array::front();
 245 }
 246
 247 inline int64_t ArrayInteger::back() const noexcept
 248 {
 249     return Array::back();
 250 }
 251
 252 inline void ArrayInteger::adjust(size_t ndx, int_fast64_t diff)
 253 {
 254     Array::adjust(ndx, diff);
 255 }
 256
 257 inline void ArrayInteger::adjust(size_t begin, size_t end, int_fast64_t diff)
 258 {
 259     Array::adjust(begin, end, diff);
 260 }
 261
 262 inline void ArrayInteger::adjust_ge(int_fast64_t limit, int_fast64_t diff)
 263 {
 264     Array::adjust_ge(limit, diff);
 265 }
 266
 267 inline size_t ArrayInteger::lower_bound(int64_t value) const noexcept
 268 {
 269     return lower_bound_int(value);
 270 }
 271
 272 inline size_t ArrayInteger::upper_bound(int64_t value) const noexcept
 273 {
 274     return upper_bound_int(value);
 275 }
 276
 277
 278 inline ArrayIntNull::ArrayIntNull(Allocator& allocator) noexcept
 279     : Array(allocator)
 280 {
 281 }
 282
 283 inline ArrayIntNull::~ArrayIntNull() noexcept
 284 {
 285 }
 286
 287 inline void ArrayIntNull::create(Type type, bool context_flag)
 288 {
 289     MemRef r = create_array(type, context_flag, 0, util::none, m_alloc);
 290     init_from_mem(r);
 291 }
 292
 293
 294 inline size_t ArrayIntNull::size() const noexcept
 295 {
 296     return Array::size() - 1;
 297 }
 298
 299 inline bool ArrayIntNull::is_empty() const noexcept
 300 {
 301     return size() == 0;
 302 }
 303
 304 inline void ArrayIntNull::insert(size_t ndx, value_type value)
 305 {
 306     if (value) {
 307         avoid_null_collision(*value);
 308         Array::insert(ndx + 1, *value);
 309     }
 310     else {
 311         Array::insert(ndx + 1, null_value());
 312     }
 313 }
 314
 315 inline void ArrayIntNull::add(value_type value)
 316 {
 317     if (value) {
 318         avoid_null_collision(*value);
 319         Array::add(*value);
 320     }
 321     else {
 322         Array::add(null_value());
 323     }
 324 }
 325
 326 inline void ArrayIntNull::set(size_t ndx, value_type value) noexcept
 327 {
 328     if (value) {
 329         avoid_null_collision(*value);
 330         Array::set(ndx + 1, *value);
 331     }
 332     else {
 333         Array::set(ndx + 1, null_value());
 334     }
 335 }
 336
 337 inline void ArrayIntNull::set_null(size_t ndx) noexcept
 338 {
 339     Array::set(ndx + 1, null_value());
 340 }
 341
 342 inline ArrayIntNull::value_type ArrayIntNull::get(size_t ndx) const noexcept
 343 {
 344     int64_t value = Array::get(ndx + 1);
 345     if (value == null_value()) {
 346         return util::none;
 347     }
 348     return util::some<int64_t>(value);
 349 }
 350
 351 inline ArrayIntNull::value_type ArrayIntNull::get(const char* header, size_t ndx) noexcept
 352 {
 353     int64_t null_value = Array::get(header, 0);
 354     int64_t value = Array::get(header, ndx + 1);
 355     if (value == null_value) {
 356         return util::none;
 357     }
 358     else {
 359         return util::some<int64_t>(value);
 360     }
 361 }
 362
 363 inline bool ArrayIntNull::is_null(size_t ndx) const noexcept
 364 {
 365     return !get(ndx);
 366 }
 367
 368 inline int64_t ArrayIntNull::null_value() const noexcept
 369 {
 370     return Array::get(0);
 371 }
 372
 373 inline ArrayIntNull::value_type ArrayIntNull::operator[](size_t ndx) const noexcept
 374 {
 375     return get(ndx);
 376 }
 377
 378 inline ArrayIntNull::value_type ArrayIntNull::front() const noexcept
 379 {
 380     return get(0);
 381 }
 382
 383 inline ArrayIntNull::value_type ArrayIntNull::back() const noexcept
 384 {
 385     return Array::back();
 386 }
 387
 388 inline void ArrayIntNull::erase(size_t ndx)
 389 {
 390     Array::erase(ndx + 1);
 391 }
 392
 393 inline void ArrayIntNull::erase(size_t begin, size_t end)
 394 {
 395     Array::erase(begin + 1, end + 1);
 396 }
 397
 398 inline void ArrayIntNull::truncate(size_t to_size)
 399 {
 400     Array::truncate(to_size + 1);
 401 }
 402
 403 inline void ArrayIntNull::clear()
 404 {
 405     truncate(0);
 406 }
 407
 408 inline void ArrayIntNull::set_all_to_zero()
 409 {
 410     // FIXME: Array::set_all_to_zero does something else
 411     for (size_t i = 0; i < size(); ++i) {
 412         set(i, 0);
 413     }
 414 }
 415
 416 inline void ArrayIntNull::move(size_t begin, size_t end, size_t dest_begin)
 417 {
 418     Array::move(begin + 1, end + 1, dest_begin + 1);
 419 }
 420
 421 inline void ArrayIntNull::move_backward(size_t begin, size_t end, size_t dest_end)
 422 {
 423     Array::move_backward(begin + 1, end + 1, dest_end + 1);
 424 }
 425
 426 inline size_t ArrayIntNull::lower_bound(int64_t value) const noexcept
 427 {
 428     // FIXME: Consider this behaviour with NULLs.
 429     // Array::lower_bound_int assumes an already sorted array, but
 430     // this array could be sorted with nulls first or last.
 431     return Array::lower_bound_int(value);
 432 }
 433
 434 inline size_t ArrayIntNull::upper_bound(int64_t value) const noexcept
 435 {
 436     // FIXME: see lower_bound
 437     return Array::upper_bound_int(value);
 438 }
 439
 440 inline int64_t ArrayIntNull::sum(size_t start, size_t end) const
 441 {
 442     // FIXME: Optimize
 443     int64_t sum_of_range = 0;
 444     if (end == npos)
 445         end = size();
 446     for (size_t i = start; i < end; ++i) {
 447         value_type x = get(i);
 448         if (x) {
 449             sum_of_range += *x;
 450         }
 451     }
 452     return sum_of_range;
 453 }
 454
 455 inline size_t ArrayIntNull::count(int64_t value) const noexcept
 456 {
 457     size_t count_of_value = Array::count(value);
 458     if (value == null_value()) {
 459         --count_of_value;
 460     }
 461     return count_of_value;
 462 }
 463
 464 // FIXME: Optimize
 465 template <bool find_max>
 466 inline bool ArrayIntNull::minmax_helper(int64_t& result, size_t start, size_t end, size_t* return_ndx) const
 467 {
 468     size_t best_index = 1;
 469
 470     if (end == npos) {
 471         end = m_size;
 472     }
 473
 474     ++start;
 475
 476     REALM_ASSERT(start < m_size && end <= m_size && start < end);
 477
 478     if (m_size == 1) {
 479         // empty array
 480         return false;
 481     }
 482
 483     if (m_width == 0) {
 484         if (return_ndx)
 485             *return_ndx = best_index - 1;
 486         result = 0;
 487         return true;
 488     }
 489
 490     int64_t m = Array::get(start);
 491
 492     const int64_t null_val = null_value();
 493     for (; start < end; ++start) {
 494         const int64_t v = Array::get(start);
 495         if (find_max ? v > m : v < m) {
 496             if (v == null_val) {
 497                 continue;
 498             }
 499             m = v;
 500             best_index = start;
 501         }
 502     }
 503
 504     result = m;
 505     if (return_ndx) {
 506         *return_ndx = best_index - 1;
 507     }
 508     return true;
 509 }
 510
 511 inline bool ArrayIntNull::maximum(int64_t& result, size_t start, size_t end, size_t* return_ndx) const
 512 {
 513     return minmax_helper<true>(result, start, end, return_ndx);
 514 }
 515
 516 inline bool ArrayIntNull::minimum(int64_t& result, size_t start, size_t end, size_t* return_ndx) const
 517 {
 518     return minmax_helper<false>(result, start, end, return_ndx);
 519 }
 520
 521 inline bool ArrayIntNull::find(int cond, Action action, value_type value, size_t start, size_t end, size_t baseindex,
 522                                QueryState<int64_t>* state) const
 523 {
 524     if (value) {
 525         return Array::find(cond, action, *value, start, end, baseindex, state, true /*treat as nullable array*/,
 526                            false /*search parameter given in 'value' argument*/);
 527     }
 528     else {
 529         return Array::find(cond, action, 0 /* unused dummy*/, start, end, baseindex, state,
 530                            true /*treat as nullable array*/, true /*search for null, ignore value argument*/);
 531     }
 532 }
 533
 534 template <class cond, Action action, size_t bitwidth, class Callback>
 535 bool ArrayIntNull::find(value_type value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
 536                         Callback callback) const
 537 {
 538     if (value) {
 539         return Array::find<cond, action>(*value, start, end, baseindex, state, std::forward<Callback>(callback),
 540                                          true /*treat as nullable array*/,
 541                                          false /*search parameter given in 'value' argument*/);
 542     }
 543     else {
 544         return Array::find<cond, action>(0 /*ignored*/, start, end, baseindex, state,
 545                                          std::forward<Callback>(callback), true /*treat as nullable array*/,
 546                                          true /*search for null, ignore value argument*/);
 547     }
 548 }
 549
 550
 551 template <class cond, Action action, size_t bitwidth>
 552 bool ArrayIntNull::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state) const
 553 {
 554     return Array::find<cond, action>(value, start, end, baseindex, state, true /*treat as nullable array*/,
 555                                      false /*search parameter given in 'value' argument*/);
 556 }
 557
 558
 559 template <class cond, Action action, class Callback>
 560 bool ArrayIntNull::find(value_type value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
 561                         Callback callback) const
 562 {
 563     if (value) {
 564         return Array::find<cond, action>(*value, start, end, baseindex, state, std::forward<Callback>(callback),
 565                                          true /*treat as nullable array*/,
 566                                          false /*search parameter given in 'value' argument*/);
 567     }
 568     else {
 569         return Array::find<cond, action>(0 /*ignored*/, start, end, baseindex, state,
 570                                          std::forward<Callback>(callback), true /*treat as nullable array*/,
 571                                          true /*search for null, ignore value argument*/);
 572     }
 573 }
 574
 575
 576 template <Action action, class Callback>
 577 bool ArrayIntNull::find_action(size_t index, value_type value, QueryState<int64_t>* state, Callback callback) const
 578 {
 579     if (value) {
 580         return Array::find_action<action, Callback>(index, *value, state, callback, true /*treat as nullable array*/,
 581                                                     false /*search parameter given in 'value' argument*/);
 582     }
 583     else {
 584         return Array::find_action<action, Callback>(index, 0 /* ignored */, state, callback,
 585                                                     true /*treat as nullable array*/,
 586                                                     true /*search for null, ignore value argument*/);
 587     }
 588 }
 589
 590
 591 template <Action action, class Callback>
 592 bool ArrayIntNull::find_action_pattern(size_t index, uint64_t pattern, QueryState<int64_t>* state,
 593                                        Callback callback) const
 594 {
 595     return Array::find_action_pattern<action, Callback>(index, pattern, state, callback,
 596                                                         true /*treat as nullable array*/,
 597                                                         false /*search parameter given in 'value' argument*/);
 598 }
 599
 600
 601 template <class cond>
 602 size_t ArrayIntNull::find_first(value_type value, size_t start, size_t end) const
 603 {
 604     QueryState<int64_t> state;
 605     state.init(act_ReturnFirst, nullptr, 1);
 606     if (value) {
 607         Array::find<cond, act_ReturnFirst>(*value, start, end, 0, &state, Array::CallbackDummy(),
 608                                            true /*treat as nullable array*/,
 609                                            false /*search parameter given in 'value' argument*/);
 610     }
 611     else {
 612         Array::find<cond, act_ReturnFirst>(0 /*ignored*/, start, end, 0, &state, Array::CallbackDummy(),
 613                                            true /*treat as nullable array*/,
 614                                            true /*search for null, ignore value argument*/);
 615     }
 616
 617     if (state.m_match_count > 0)
 618         return to_size_t(state.m_state);
 619     else
 620         return not_found;
 621 }
 622
 623 inline size_t ArrayIntNull::find_first(value_type value, size_t begin, size_t end) const
 624 {
 625     return find_first<Equal>(value, begin, end);
 626 }
 627 }
 628
 629 #endif // REALM_ARRAY_INTEGER_HPP