iOS/Pods/Realm/include/core/realm/array_basic_tpl.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_BASIC_TPL_HPP
  20 #define REALM_ARRAY_BASIC_TPL_HPP
  21
  22 #include <algorithm>
  23 #include <limits>
  24 #include <stdexcept>
  25 #include <iomanip>
  26
  27 #include <realm/impl/destroy_guard.hpp>
  28
  29 namespace realm {
  30
  31 template <class T>
  32 inline BasicArray<T>::BasicArray(Allocator& allocator) noexcept
  33     : Array(allocator)
  34 {
  35 }
  36
  37 template <class T>
  38 inline MemRef BasicArray<T>::create_array(size_t init_size, Allocator& allocator)
  39 {
  40     size_t byte_size_0 = calc_aligned_byte_size(init_size); // Throws
  41     // Adding zero to Array::initial_capacity to avoid taking the
  42     // address of that member
  43     size_t byte_size = std::max(byte_size_0, Array::initial_capacity + 0); // Throws
  44
  45     MemRef mem = allocator.alloc(byte_size); // Throws
  46
  47     bool is_inner_bptree_node = false;
  48     bool has_refs = false;
  49     bool context_flag = false;
  50     int width = sizeof(T);
  51     init_header(mem.get_addr(), is_inner_bptree_node, has_refs, context_flag, wtype_Multiply, width, init_size,
  52                 byte_size);
  53
  54     return mem;
  55 }
  56
  57
  58 template <class T>
  59 inline MemRef BasicArray<T>::create_array(Array::Type type, bool context_flag, size_t init_size, T value,
  60                                           Allocator& allocator)
  61 {
  62     REALM_ASSERT(type == Array::type_Normal);
  63     REALM_ASSERT(!context_flag);
  64     MemRef mem = create_array(init_size, allocator);
  65     if (init_size) {
  66         BasicArray<T> tmp(allocator);
  67         tmp.init_from_mem(mem);
  68         T* p = reinterpret_cast<T*>(tmp.m_data);
  69         T* end = p + init_size;
  70         while (p < end) {
  71             *p++ = value;
  72         }
  73     }
  74     return mem;
  75 }
  76
  77
  78 template <class T>
  79 inline void BasicArray<T>::create(Array::Type type, bool context_flag)
  80 {
  81     REALM_ASSERT(type == Array::type_Normal);
  82     REALM_ASSERT(!context_flag);
  83     size_t length = 0;
  84     MemRef mem = create_array(length, get_alloc()); // Throws
  85     init_from_mem(mem);
  86 }
  87
  88
  89 template <class T>
  90 MemRef BasicArray<T>::slice(size_t offset, size_t slice_size, Allocator& target_alloc) const
  91 {
  92     REALM_ASSERT(is_attached());
  93
  94     // FIXME: This can be optimized as a single contiguous copy
  95     // operation.
  96     BasicArray array_slice(target_alloc);
  97     _impl::ShallowArrayDestroyGuard dg(&array_slice);
  98     array_slice.create(); // Throws
  99     size_t begin = offset;
 100     size_t end = offset + slice_size;
 101     for (size_t i = begin; i != end; ++i) {
 102         T value = get(i);
 103         array_slice.add(value); // Throws
 104     }
 105     dg.release();
 106     return array_slice.get_mem();
 107 }
 108
 109 template <class T>
 110 MemRef BasicArray<T>::slice_and_clone_children(size_t offset, size_t slice_size, Allocator& target_alloc) const
 111 {
 112     // BasicArray<T> never contains refs, so never has children.
 113     return slice(offset, slice_size, target_alloc);
 114 }
 115
 116
 117 template <class T>
 118 inline void BasicArray<T>::add(T value)
 119 {
 120     insert(m_size, value);
 121 }
 122
 123
 124 template <class T>
 125 inline T BasicArray<T>::get(size_t ndx) const noexcept
 126 {
 127     return *(reinterpret_cast<const T*>(m_data) + ndx);
 128 }
 129
 130
 131 template <class T>
 132 inline bool BasicArray<T>::is_null(size_t ndx) const noexcept
 133 {
 134     // FIXME: This assumes BasicArray will only ever be instantiated for float-like T.
 135     static_assert(realm::is_any<T, float, double>::value, "T can only be float or double");
 136     auto x = get(ndx);
 137     return null::is_null_float(x);
 138 }
 139
 140
 141 template <class T>
 142 inline T BasicArray<T>::get(const char* header, size_t ndx) noexcept
 143 {
 144     const char* data = get_data_from_header(header);
 145     // This casting assumes that T can be aliged on an 8-bype
 146     // boundary (since data is aligned on an 8-byte boundary.)
 147     return *(reinterpret_cast<const T*>(data) + ndx);
 148 }
 149
 150
 151 template <class T>
 152 inline void BasicArray<T>::set(size_t ndx, T value)
 153 {
 154     REALM_ASSERT_3(ndx, <, m_size);
 155     if (get(ndx) == value)
 156         return;
 157
 158     // Check if we need to copy before modifying
 159     copy_on_write(); // Throws
 160
 161     // Set the value
 162     T* data = reinterpret_cast<T*>(m_data) + ndx;
 163     *data = value;
 164 }
 165
 166 template <class T>
 167 inline void BasicArray<T>::set_null(size_t ndx)
 168 {
 169     // FIXME: This assumes BasicArray will only ever be instantiated for float-like T.
 170     set(ndx, null::get_null_float<T>());
 171 }
 172
 173 template <class T>
 174 void BasicArray<T>::insert(size_t ndx, T value)
 175 {
 176     REALM_ASSERT_3(ndx, <=, m_size);
 177
 178     // Check if we need to copy before modifying
 179     copy_on_write(); // Throws
 180
 181     // Make room for the new value
 182     alloc(m_size + 1, m_width); // Throws
 183
 184     // Move values below insertion
 185     if (ndx != m_size) {
 186         char* src_begin = m_data + ndx * m_width;
 187         char* src_end = m_data + m_size * m_width;
 188         char* dst_end = src_end + m_width;
 189         std::copy_backward(src_begin, src_end, dst_end);
 190     }
 191
 192     // Set the value
 193     T* data = reinterpret_cast<T*>(m_data) + ndx;
 194     *data = value;
 195
 196     ++m_size;
 197 }
 198
 199 template <class T>
 200 void BasicArray<T>::erase(size_t ndx)
 201 {
 202     REALM_ASSERT_3(ndx, <, m_size);
 203
 204     // Check if we need to copy before modifying
 205     copy_on_write(); // Throws
 206
 207     // move data under deletion up
 208     if (ndx < m_size - 1) {
 209         char* dst_begin = m_data + ndx * m_width;
 210         const char* src_begin = dst_begin + m_width;
 211         const char* src_end = m_data + m_size * m_width;
 212         realm::safe_copy_n(src_begin, src_end - src_begin, dst_begin);
 213     }
 214
 215     // Update size (also in header)
 216     --m_size;
 217     set_header_size(m_size);
 218 }
 219
 220 template <class T>
 221 void BasicArray<T>::truncate(size_t to_size)
 222 {
 223     REALM_ASSERT(is_attached());
 224     REALM_ASSERT_3(to_size, <=, m_size);
 225
 226     copy_on_write(); // Throws
 227
 228     // Update size in accessor and in header. This leaves the capacity
 229     // unchanged.
 230     m_size = to_size;
 231     set_header_size(to_size);
 232 }
 233
 234 template <class T>
 235 inline void BasicArray<T>::clear()
 236 {
 237     truncate(0); // Throws
 238 }
 239
 240 template <class T>
 241 bool BasicArray<T>::compare(const BasicArray<T>& a) const
 242 {
 243     size_t n = size();
 244     if (a.size() != n)
 245         return false;
 246     const T* data_1 = reinterpret_cast<const T*>(m_data);
 247     const T* data_2 = reinterpret_cast<const T*>(a.m_data);
 248     return realm::safe_equal(data_1, data_1 + n, data_2);
 249 }
 250
 251
 252 template <class T>
 253 size_t BasicArray<T>::calc_byte_len(size_t for_size, size_t) const
 254 {
 255     // FIXME: Consider calling `calc_aligned_byte_size(size)`
 256     // instead. Note however, that calc_byte_len() is supposed to return
 257     // the unaligned byte size. It is probably the case that no harm
 258     // is done by returning the aligned version, and most callers of
 259     // calc_byte_len() will actually benefit if calc_byte_len() was
 260     // changed to always return the aligned byte size.
 261     return header_size + for_size * sizeof(T);
 262 }
 263
 264 template <class T>
 265 size_t BasicArray<T>::calc_item_count(size_t bytes, size_t) const noexcept
 266 {
 267     size_t bytes_without_header = bytes - header_size;
 268     return bytes_without_header / sizeof(T);
 269 }
 270
 271 template <class T>
 272 size_t BasicArray<T>::find(T value, size_t begin, size_t end) const
 273 {
 274     if (end == npos)
 275         end = m_size;
 276     REALM_ASSERT(begin <= m_size && end <= m_size && begin <= end);
 277     const T* data = reinterpret_cast<const T*>(m_data);
 278     const T* i = std::find(data + begin, data + end, value);
 279     return i == data + end ? not_found : size_t(i - data);
 280 }
 281
 282 template <class T>
 283 inline size_t BasicArray<T>::find_first(T value, size_t begin, size_t end) const
 284 {
 285     return this->find(value, begin, end);
 286 }
 287
 288 template <class T>
 289 void BasicArray<T>::find_all(IntegerColumn* result, T value, size_t add_offset, size_t begin, size_t end) const
 290 {
 291     size_t first = begin - 1;
 292     for (;;) {
 293         first = this->find(value, first + 1, end);
 294         if (first == not_found)
 295             break;
 296
 297         Array::add_to_column(result, first + add_offset);
 298     }
 299 }
 300
 301 template <class T>
 302 size_t BasicArray<T>::count(T value, size_t begin, size_t end) const
 303 {
 304     if (end == npos)
 305         end = m_size;
 306     REALM_ASSERT(begin <= m_size && end <= m_size && begin <= end);
 307     const T* data = reinterpret_cast<const T*>(m_data);
 308     return std::count(data + begin, data + end, value);
 309 }
 310
 311 #if 0
 312 // currently unused
 313 template <class T>
 314 double BasicArray<T>::sum(size_t begin, size_t end) const
 315 {
 316     if (end == npos)
 317         end = m_size;
 318     REALM_ASSERT(begin <= m_size && end <= m_size && begin <= end);
 319     const T* data = reinterpret_cast<const T*>(m_data);
 320     return std::accumulate(data + begin, data + end, double(0));
 321 }
 322 #endif
 323
 324 template <class T>
 325 template <bool find_max>
 326 bool BasicArray<T>::minmax(T& result, size_t begin, size_t end) const
 327 {
 328     if (end == npos)
 329         end = m_size;
 330     if (m_size == 0)
 331         return false;
 332     REALM_ASSERT(begin < m_size && end <= m_size && begin < end);
 333
 334     T m = get(begin);
 335     ++begin;
 336     for (; begin < end; ++begin) {
 337         T val = get(begin);
 338         if (find_max ? val > m : val < m)
 339             m = val;
 340     }
 341     result = m;
 342     return true;
 343 }
 344
 345 template <class T>
 346 bool BasicArray<T>::maximum(T& result, size_t begin, size_t end) const
 347 {
 348     return minmax<true>(result, begin, end);
 349 }
 350
 351 template <class T>
 352 bool BasicArray<T>::minimum(T& result, size_t begin, size_t end) const
 353 {
 354     return minmax<false>(result, begin, end);
 355 }
 356
 357
 358 template <class T>
 359 ref_type BasicArray<T>::bptree_leaf_insert(size_t ndx, T value, TreeInsertBase& state)
 360 {
 361     size_t leaf_size = size();
 362     REALM_ASSERT_3(leaf_size, <=, REALM_MAX_BPNODE_SIZE);
 363     if (leaf_size < ndx)
 364         ndx = leaf_size;
 365     if (REALM_LIKELY(leaf_size < REALM_MAX_BPNODE_SIZE)) {
 366         insert(ndx, value);
 367         return 0; // Leaf was not split
 368     }
 369
 370     // Split leaf node
 371     BasicArray<T> new_leaf(get_alloc());
 372     new_leaf.create(); // Throws
 373     if (ndx == leaf_size) {
 374         new_leaf.add(value);
 375         state.m_split_offset = ndx;
 376     }
 377     else {
 378         // FIXME: Could be optimized by first resizing the target
 379         // array, then copy elements with std::copy().
 380         for (size_t i = ndx; i != leaf_size; ++i)
 381             new_leaf.add(get(i));
 382         truncate(ndx);
 383         add(value);
 384         state.m_split_offset = ndx + 1;
 385     }
 386     state.m_split_size = leaf_size + 1;
 387     return new_leaf.get_ref();
 388 }
 389
 390 template <class T>
 391 inline size_t BasicArray<T>::lower_bound(T value) const noexcept
 392 {
 393     const T* begin = reinterpret_cast<const T*>(m_data);
 394     const T* end = begin + size();
 395     return std::lower_bound(begin, end, value) - begin;
 396 }
 397
 398 template <class T>
 399 inline size_t BasicArray<T>::upper_bound(T value) const noexcept
 400 {
 401     const T* begin = reinterpret_cast<const T*>(m_data);
 402     const T* end = begin + size();
 403     return std::upper_bound(begin, end, value) - begin;
 404 }
 405
 406 template <class T>
 407 inline size_t BasicArray<T>::calc_aligned_byte_size(size_t size)
 408 {
 409     size_t max = std::numeric_limits<size_t>::max();
 410     size_t max_2 = max & ~size_t(7); // Allow for upwards 8-byte alignment
 411     if (size > (max_2 - header_size) / sizeof(T))
 412         throw std::runtime_error("Byte size overflow");
 413     size_t byte_size = header_size + size * sizeof(T);
 414     REALM_ASSERT_3(byte_size, >, 0);
 415     size_t aligned_byte_size = ((byte_size - 1) | 7) + 1; // 8-byte alignment
 416     return aligned_byte_size;
 417 }
 418
 419
 420 #ifdef REALM_DEBUG
 421
 422 // LCOV_EXCL_START
 423 template <class T>
 424 void BasicArray<T>::to_dot(std::ostream& out, StringData title) const
 425 {
 426     ref_type ref = get_ref();
 427     if (title.size() != 0) {
 428         out << "subgraph cluster_" << ref << " {\n";
 429         out << " label = \"" << title << "\";\n";
 430         out << " color = white;\n";
 431     }
 432
 433     out << "n" << std::hex << ref << std::dec << "[shape=none,label=<";
 434     out << "<TABLE BORDER=\"0\" CELLBORDER=\"1\" CELLSPACING=\"0\" CELLPADDING=\"4\"><TR>\n";
 435
 436     // Header
 437     out << "<TD BGCOLOR=\"lightgrey\"><FONT POINT-SIZE=\"7\"> ";
 438     out << "0x" << std::hex << ref << std::dec << "<BR/>";
 439     out << "</FONT></TD>\n";
 440
 441     // Values
 442     size_t n = m_size;
 443     for (size_t i = 0; i != n; ++i)
 444         out << "<TD>" << get(i) << "</TD>\n";
 445
 446     out << "</TR></TABLE>>];\n";
 447
 448     if (title.size() != 0)
 449         out << "}\n";
 450
 451     to_dot_parent_edge(out);
 452 }
 453 // LCOV_EXCL_STOP
 454
 455 #endif // REALM_DEBUG
 456
 457
 458 } // namespace realm
 459
 460 #endif // REALM_ARRAY_BASIC_TPL_HPP