iOS/Pods/Realm/include/core/realm/column_binary.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_COLUMN_BINARY_HPP
  20 #define REALM_COLUMN_BINARY_HPP
  21
  22 #include <realm/column.hpp>
  23 #include <realm/array_binary.hpp>
  24 #include <realm/array_blobs_big.hpp>
  25
  26 namespace realm {
  27
  28
  29 /// A binary column (BinaryColumn) is a single B+-tree, and the root
  30 /// of the column is the root of the B+-tree. Leaf nodes are either of
  31 /// type ArrayBinary (array of small blobs) or ArrayBigBlobs (array of
  32 /// big blobs).
  33 class BinaryColumn : public ColumnBaseSimple {
  34 public:
  35     typedef BinaryData value_type;
  36
  37     BinaryColumn(Allocator&, ref_type, bool nullable = false, size_t column_ndx = npos);
  38
  39     size_t size() const noexcept final;
  40     bool is_empty() const noexcept
  41     {
  42         return size() == 0;
  43     }
  44     bool is_nullable() const noexcept override;
  45
  46     BinaryData get(size_t ndx) const noexcept;
  47
  48     /// Return data from position 'pos' and onwards. If the blob is distributed
  49     /// across multiple arrays (if bigger than ~ 16M), you will only get data
  50     /// from one array. 'pos' will be updated to be an index to next available
  51     /// data. It will be 0 if no more data.
  52     BinaryData get_at(size_t ndx, size_t& pos) const noexcept;
  53
  54     bool is_null(size_t ndx) const noexcept override;
  55     StringData get_index_data(size_t, StringIndex::StringConversionBuffer&) const noexcept final;
  56
  57     void add(BinaryData value);
  58     void set(size_t ndx, BinaryData value, bool add_zero_term = false);
  59     void set_null(size_t ndx) override;
  60     void insert(size_t ndx, BinaryData value);
  61     void erase(size_t row_ndx);
  62     void erase(size_t row_ndx, bool is_last);
  63     void move_last_over(size_t row_ndx);
  64     void swap_rows(size_t row_ndx_1, size_t row_ndx_2) override;
  65     void clear();
  66     size_t find_first(BinaryData value) const;
  67
  68     // Requires that the specified entry was inserted as StringData.
  69     StringData get_string(size_t ndx) const noexcept;
  70
  71     void add_string(StringData value);
  72     void set_string(size_t ndx, StringData value) override;
  73     void insert_string(size_t ndx, StringData value);
  74
  75     /// Compare two binary columns for equality.
  76     bool compare_binary(const BinaryColumn&) const;
  77
  78     int compare_values(size_t row1, size_t row2) const noexcept override;
  79
  80     static ref_type create(Allocator&, size_t size, bool nullable);
  81
  82     static size_t get_size_from_ref(ref_type root_ref, Allocator&) noexcept;
  83
  84     // Overrriding method in ColumnBase
  85     ref_type write(size_t, size_t, size_t, _impl::OutputStream&) const override;
  86
  87     void insert_rows(size_t, size_t, size_t, bool) override;
  88     void erase_rows(size_t, size_t, size_t, bool) override;
  89     void move_last_row_over(size_t, size_t, bool) override;
  90     void clear(size_t, bool) override;
  91     void update_from_parent(size_t) noexcept override;
  92     void refresh_accessor_tree(size_t, const Spec&) override;
  93
  94     /// In contrast to update_from_parent(), this function is able to handle
  95     /// cases where the accessed payload data has changed. In particular, it
  96     /// handles cases where the B+-tree switches from having one level (root is
  97     /// a leaf node), to having multiple levels (root is an inner node). Note
  98     /// that this is at the expense of loosing the `noexcept` guarantee.
  99     void update_from_ref(ref_type ref);
 100
 101     void verify() const override;
 102     void to_dot(std::ostream&, StringData title) const override;
 103     void do_dump_node_structure(std::ostream&, int) const override;
 104
 105 private:
 106     /// \param row_ndx Must be `realm::npos` if appending.
 107     void do_insert(size_t row_ndx, BinaryData value, bool add_zero_term, size_t num_rows);
 108
 109     // Called by Array::bptree_insert().
 110     static ref_type leaf_insert(MemRef leaf_mem, ArrayParent&, size_t ndx_in_parent, Allocator&, size_t insert_ndx,
 111                                 BpTreeNode::TreeInsert<BinaryColumn>& state);
 112
 113     struct InsertState : BpTreeNode::TreeInsert<BinaryColumn> {
 114         bool m_add_zero_term;
 115     };
 116
 117     class EraseLeafElem;
 118     class CreateHandler;
 119     class SliceHandler;
 120
 121     void do_move_last_over(size_t row_ndx, size_t last_row_ndx);
 122     void do_clear();
 123
 124     /// Root must be a leaf. Upgrades the root leaf if
 125     /// necessary. Returns true if, and only if the root is a 'big
 126     /// blobs' leaf upon return.
 127     bool upgrade_root_leaf(size_t value_size);
 128
 129     bool m_nullable = false;
 130
 131     void leaf_to_dot(MemRef, ArrayParent*, size_t ndx_in_parent, std::ostream&) const override;
 132
 133     friend class BpTreeNode;
 134     friend class ColumnBase;
 135 };
 136
 137 class BinaryIterator {
 138 public:
 139     BinaryIterator()
 140     {
 141     }
 142     // TODO: When WriteLogCollector is removed, there is no need for this
 143     BinaryIterator(BinaryData binary)
 144         : m_binary(binary)
 145     {
 146     }
 147
 148     BinaryIterator(const BinaryColumn* col, size_t ndx)
 149         : m_binary_col(col)
 150         , m_ndx(ndx)
 151     {
 152     }
 153
 154     BinaryData get_next() noexcept
 155     {
 156         if (!end_of_data) {
 157             if (m_binary_col) {
 158                 BinaryData ret = m_binary_col->get_at(m_ndx, m_pos);
 159                 end_of_data = (m_pos == 0);
 160                 return ret;
 161             }
 162             else if (!m_binary.is_null()) {
 163                 end_of_data = true;
 164                 return m_binary;
 165             }
 166         }
 167         return {};
 168     }
 169
 170 private:
 171     bool end_of_data = false;
 172     const BinaryColumn* m_binary_col = nullptr;
 173     size_t m_ndx = 0;
 174     size_t m_pos = 0;
 175     BinaryData m_binary;
 176 };
 177
 178
 179 // Implementation
 180
 181 // LCOV_EXCL_START
 182 inline StringData BinaryColumn::get_index_data(size_t, StringIndex::StringConversionBuffer&) const noexcept
 183 {
 184     REALM_ASSERT(false && "Index not implemented for BinaryColumn.");
 185     REALM_UNREACHABLE();
 186 }
 187 // LCOV_EXCL_STOP
 188
 189 inline size_t BinaryColumn::size() const noexcept
 190 {
 191     if (root_is_leaf()) {
 192         bool is_big = m_array->get_context_flag();
 193         if (!is_big) {
 194             // Small blobs root leaf
 195             ArrayBinary* leaf = static_cast<ArrayBinary*>(m_array.get());
 196             return leaf->size();
 197         }
 198         // Big blobs root leaf
 199         ArrayBigBlobs* leaf = static_cast<ArrayBigBlobs*>(m_array.get());
 200         return leaf->size();
 201     }
 202     // Non-leaf root
 203     return static_cast<BpTreeNode*>(m_array.get())->get_bptree_size();
 204 }
 205
 206 inline bool BinaryColumn::is_nullable() const noexcept
 207 {
 208     return m_nullable;
 209 }
 210
 211 inline void BinaryColumn::update_from_parent(size_t old_baseline) noexcept
 212 {
 213     if (root_is_leaf()) {
 214         bool is_big = m_array->get_context_flag();
 215         if (!is_big) {
 216             // Small blobs root leaf
 217             REALM_ASSERT(dynamic_cast<ArrayBinary*>(m_array.get()));
 218             ArrayBinary* leaf = static_cast<ArrayBinary*>(m_array.get());
 219             leaf->update_from_parent(old_baseline);
 220             return;
 221         }
 222         // Big blobs root leaf
 223         REALM_ASSERT(dynamic_cast<ArrayBigBlobs*>(m_array.get()));
 224         ArrayBigBlobs* leaf = static_cast<ArrayBigBlobs*>(m_array.get());
 225         leaf->update_from_parent(old_baseline);
 226         return;
 227     }
 228     // Non-leaf root
 229     m_array->update_from_parent(old_baseline);
 230 }
 231
 232 inline BinaryData BinaryColumn::get(size_t ndx) const noexcept
 233 {
 234     REALM_ASSERT_DEBUG(ndx < size());
 235     if (root_is_leaf()) {
 236         bool is_big = m_array->get_context_flag();
 237         BinaryData ret;
 238         if (!is_big) {
 239             // Small blobs root leaf
 240             ArrayBinary* leaf = static_cast<ArrayBinary*>(m_array.get());
 241             ret = leaf->get(ndx);
 242         }
 243         else {
 244             // Big blobs root leaf
 245             ArrayBigBlobs* leaf = static_cast<ArrayBigBlobs*>(m_array.get());
 246             ret = leaf->get(ndx);
 247         }
 248         if (!m_nullable && ret.is_null())
 249             return BinaryData("", 0); // return empty string (non-null)
 250         return ret;
 251     }
 252
 253     // Non-leaf root
 254     std::pair<MemRef, size_t> p = static_cast<BpTreeNode*>(m_array.get())->get_bptree_leaf(ndx);
 255     const char* leaf_header = p.first.get_addr();
 256     size_t ndx_in_leaf = p.second;
 257     Allocator& alloc = m_array->get_alloc();
 258     bool is_big = Array::get_context_flag_from_header(leaf_header);
 259     if (!is_big) {
 260         // Small blobs
 261         return ArrayBinary::get(leaf_header, ndx_in_leaf, alloc);
 262     }
 263     // Big blobs
 264     return ArrayBigBlobs::get(leaf_header, ndx_in_leaf, alloc);
 265 }
 266
 267 inline bool BinaryColumn::is_null(size_t ndx) const noexcept
 268 {
 269     return m_nullable && get(ndx).is_null();
 270 }
 271
 272 inline StringData BinaryColumn::get_string(size_t ndx) const noexcept
 273 {
 274     BinaryData bin = get(ndx);
 275     REALM_ASSERT_3(0, <, bin.size());
 276     return StringData(bin.data(), bin.size() - 1);
 277 }
 278
 279 inline void BinaryColumn::set_string(size_t ndx, StringData value)
 280 {
 281     if (value.is_null() && !m_nullable)
 282         throw LogicError(LogicError::column_not_nullable);
 283
 284     BinaryData bin(value.data(), value.size());
 285     bool add_zero_term = true;
 286     set(ndx, bin, add_zero_term);
 287 }
 288
 289 inline void BinaryColumn::add(BinaryData value)
 290 {
 291     if (value.is_null() && !m_nullable)
 292         throw LogicError(LogicError::column_not_nullable);
 293
 294     size_t row_ndx = realm::npos;
 295     bool add_zero_term = false;
 296     size_t num_rows = 1;
 297     do_insert(row_ndx, value, add_zero_term, num_rows); // Throws
 298 }
 299
 300 inline void BinaryColumn::insert(size_t row_ndx, BinaryData value)
 301 {
 302     if (value.is_null() && !m_nullable)
 303         throw LogicError(LogicError::column_not_nullable);
 304
 305     size_t column_size = this->size(); // Slow
 306     REALM_ASSERT_3(row_ndx, <=, column_size);
 307     size_t row_ndx_2 = row_ndx == column_size ? realm::npos : row_ndx;
 308     bool add_zero_term = false;
 309     size_t num_rows = 1;
 310     do_insert(row_ndx_2, value, add_zero_term, num_rows); // Throws
 311 }
 312
 313 inline void BinaryColumn::set_null(size_t row_ndx)
 314 {
 315     set(row_ndx, BinaryData{});
 316 }
 317
 318 inline size_t BinaryColumn::find_first(BinaryData value) const
 319 {
 320     for (size_t t = 0; t < size(); t++)
 321         if (get(t) == value)
 322             return t;
 323
 324     return not_found;
 325 }
 326
 327
 328 inline void BinaryColumn::erase(size_t row_ndx)
 329 {
 330     size_t last_row_ndx = size() - 1; // Note that size() is slow
 331     bool is_last = row_ndx == last_row_ndx;
 332     erase(row_ndx, is_last); // Throws
 333 }
 334
 335 inline void BinaryColumn::move_last_over(size_t row_ndx)
 336 {
 337     size_t last_row_ndx = size() - 1;         // Note that size() is slow
 338     do_move_last_over(row_ndx, last_row_ndx); // Throws
 339 }
 340
 341 inline void BinaryColumn::clear()
 342 {
 343     do_clear(); // Throws
 344 }
 345
 346 // Implementing pure virtual method of ColumnBase.
 347 inline void BinaryColumn::insert_rows(size_t row_ndx, size_t num_rows_to_insert, size_t prior_num_rows,
 348                                       bool insert_nulls)
 349 {
 350     REALM_ASSERT_DEBUG(prior_num_rows == size());
 351     REALM_ASSERT(row_ndx <= prior_num_rows);
 352     REALM_ASSERT(!insert_nulls || m_nullable);
 353
 354     size_t row_ndx_2 = (row_ndx == prior_num_rows ? realm::npos : row_ndx);
 355     BinaryData value = m_nullable ? BinaryData() : BinaryData("", 0);
 356     bool add_zero_term = false;
 357     do_insert(row_ndx_2, value, add_zero_term, num_rows_to_insert); // Throws
 358 }
 359
 360 // Implementing pure virtual method of ColumnBase.
 361 inline void BinaryColumn::erase_rows(size_t row_ndx, size_t num_rows_to_erase, size_t prior_num_rows, bool)
 362 {
 363     REALM_ASSERT_DEBUG(prior_num_rows == size());
 364     REALM_ASSERT(num_rows_to_erase <= prior_num_rows);
 365     REALM_ASSERT(row_ndx <= prior_num_rows - num_rows_to_erase);
 366
 367     bool is_last = (row_ndx + num_rows_to_erase == prior_num_rows);
 368     for (size_t i = num_rows_to_erase; i > 0; --i) {
 369         size_t row_ndx_2 = row_ndx + i - 1;
 370         erase(row_ndx_2, is_last); // Throws
 371     }
 372 }
 373
 374 // Implementing pure virtual method of ColumnBase.
 375 inline void BinaryColumn::move_last_row_over(size_t row_ndx, size_t prior_num_rows, bool)
 376 {
 377     REALM_ASSERT_DEBUG(prior_num_rows == size());
 378     REALM_ASSERT(row_ndx < prior_num_rows);
 379
 380     size_t last_row_ndx = prior_num_rows - 1;
 381     do_move_last_over(row_ndx, last_row_ndx); // Throws
 382 }
 383
 384 // Implementing pure virtual method of ColumnBase.
 385 inline void BinaryColumn::clear(size_t, bool)
 386 {
 387     do_clear(); // Throws
 388 }
 389
 390 inline void BinaryColumn::add_string(StringData value)
 391 {
 392     size_t row_ndx = realm::npos;
 393     BinaryData value_2(value.data(), value.size());
 394     bool add_zero_term = true;
 395     size_t num_rows = 1;
 396     do_insert(row_ndx, value_2, add_zero_term, num_rows); // Throws
 397 }
 398
 399 inline void BinaryColumn::insert_string(size_t row_ndx, StringData value)
 400 {
 401     size_t column_size = this->size(); // Slow
 402     REALM_ASSERT_3(row_ndx, <=, column_size);
 403     size_t row_ndx_2 = row_ndx == column_size ? realm::npos : row_ndx;
 404     BinaryData value_2(value.data(), value.size());
 405     bool add_zero_term = false;
 406     size_t num_rows = 1;
 407     do_insert(row_ndx_2, value_2, add_zero_term, num_rows); // Throws
 408 }
 409
 410 inline size_t BinaryColumn::get_size_from_ref(ref_type root_ref, Allocator& alloc) noexcept
 411 {
 412     const char* root_header = alloc.translate(root_ref);
 413     bool root_is_leaf = !Array::get_is_inner_bptree_node_from_header(root_header);
 414     if (root_is_leaf) {
 415         bool is_big = Array::get_context_flag_from_header(root_header);
 416         if (!is_big) {
 417             // Small blobs leaf
 418             return ArrayBinary::get_size_from_header(root_header, alloc);
 419         }
 420         // Big blobs leaf
 421         return ArrayBigBlobs::get_size_from_header(root_header);
 422     }
 423     return BpTreeNode::get_bptree_size_from_header(root_header);
 424 }
 425
 426
 427 } // namespace realm
 428
 429 #endif // REALM_COLUMN_BINARY_HPP