iOS/Pods/Realm/include/core/realm/column_string.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_STRING_HPP
  20 #define REALM_COLUMN_STRING_HPP
  21
  22 #include <memory>
  23 #include <realm/array_string.hpp>
  24 #include <realm/array_string_long.hpp>
  25 #include <realm/array_blobs_big.hpp>
  26 #include <realm/column.hpp>
  27 #include <realm/column_tpl.hpp>
  28
  29 namespace realm {
  30
  31 // Pre-declarations
  32 class StringIndex;
  33
  34
  35 /// A string column (StringColumn) is a single B+-tree, and
  36 /// the root of the column is the root of the B+-tree. Leaf nodes are
  37 /// either of type ArrayString (array of small strings),
  38 /// ArrayStringLong (array of medium strings), or ArrayBigBlobs (array
  39 /// of big strings).
  40 ///
  41 /// A string column can optionally be equipped with a search index. If
  42 /// it is, then the root ref of the index is stored in
  43 /// Table::m_columns immediately after the root ref of the string
  44 /// column.
  45 class StringColumn : public ColumnBaseSimple {
  46 public:
  47     typedef StringData value_type;
  48
  49     StringColumn(Allocator&, ref_type, bool nullable = false, size_t column_ndx = npos);
  50     ~StringColumn() noexcept override;
  51
  52     void destroy() noexcept override;
  53
  54     size_t size() const noexcept final;
  55     bool is_empty() const noexcept
  56     {
  57         return size() == 0;
  58     }
  59
  60     bool is_null(size_t ndx) const noexcept final;
  61     void set_null(size_t ndx) final;
  62     StringData get(size_t ndx) const noexcept;
  63     void set(size_t ndx, StringData);
  64     void add();
  65     void add(StringData value);
  66     void insert(size_t ndx);
  67     void insert(size_t ndx, StringData value);
  68     void erase(size_t row_ndx);
  69     void move_last_over(size_t row_ndx);
  70     void swap_rows(size_t row_ndx_1, size_t row_ndx_2) override;
  71     void clear();
  72
  73     size_t count(StringData value) const;
  74     size_t find_first(StringData value, size_t begin = 0, size_t end = npos) const;
  75     void find_all(IntegerColumn& result, StringData value, size_t begin = 0, size_t end = npos) const;
  76     FindRes find_all_no_copy(StringData value, InternalFindResult& result) const;
  77
  78     int compare_values(size_t, size_t) const noexcept override;
  79
  80     //@{
  81     /// Find the lower/upper bound for the specified value assuming
  82     /// that the elements are already sorted in ascending order
  83     /// according to StringData::operator<().
  84     size_t lower_bound_string(StringData value) const noexcept;
  85     size_t upper_bound_string(StringData value) const noexcept;
  86     //@}
  87
  88     void set_string(size_t, StringData) override;
  89
  90     bool is_nullable() const noexcept final;
  91
  92     // Search index
  93     StringData get_index_data(size_t ndx, StringIndex::StringConversionBuffer& buffer) const noexcept final;
  94     bool has_search_index() const noexcept override;
  95     void set_search_index_ref(ref_type, ArrayParent*, size_t) override;
  96     StringIndex* get_search_index() noexcept override;
  97     const StringIndex* get_search_index() const noexcept override;
  98     std::unique_ptr<StringIndex> release_search_index() noexcept;
  99     bool supports_search_index() const noexcept final
 100     {
 101         return true;
 102     }
 103     StringIndex* create_search_index() override;
 104
 105     // Simply inserts all column values in the index in a loop
 106     void populate_search_index();
 107     void destroy_search_index() noexcept override;
 108
 109     // Optimizing data layout. enforce == true will enforce enumeration;
 110     // enforce == false will auto-evaluate if it should be enumerated or not
 111     bool auto_enumerate(ref_type& keys, ref_type& values, bool enforce = false) const;
 112
 113     /// Compare two string columns for equality.
 114     bool compare_string(const StringColumn&) const;
 115
 116     enum LeafType {
 117         leaf_type_Small,  ///< ArrayString
 118         leaf_type_Medium, ///< ArrayStringLong
 119         leaf_type_Big     ///< ArrayBigBlobs
 120     };
 121
 122     std::unique_ptr<const ArrayParent> get_leaf(size_t ndx, size_t& out_ndx_in_parent, LeafType& out_leaf_type) const;
 123
 124     static ref_type create(Allocator&, size_t size = 0);
 125
 126     static size_t get_size_from_ref(ref_type root_ref, Allocator&) noexcept;
 127
 128     // Overrriding method in ColumnBase
 129     ref_type write(size_t, size_t, size_t, _impl::OutputStream&) const override;
 130
 131     void insert_rows(size_t, size_t, size_t, bool) override;
 132     void erase_rows(size_t, size_t, size_t, bool) override;
 133     void move_last_row_over(size_t, size_t, bool) override;
 134     void clear(size_t, bool) override;
 135     void set_ndx_in_parent(size_t ndx_in_parent) noexcept override;
 136     void update_from_parent(size_t old_baseline) noexcept override;
 137     void refresh_accessor_tree(size_t, const Spec&) override;
 138
 139     void verify() const override;
 140     void verify(const Table&, size_t) const override;
 141     void to_dot(std::ostream&, StringData title) const override;
 142     void do_dump_node_structure(std::ostream&, int) const override;
 143
 144 private:
 145     std::unique_ptr<StringIndex> m_search_index;
 146     bool m_nullable;
 147
 148     LeafType get_block(size_t ndx, ArrayParent**, size_t& off, bool use_retval = false) const;
 149
 150     /// If you are appending and have the size of the column readily available,
 151     /// call the 4 argument version instead. If you are not appending, either
 152     /// one is fine.
 153     ///
 154     /// \param row_ndx Must be `realm::npos` if appending.
 155     void do_insert(size_t row_ndx, StringData value, size_t num_rows);
 156
 157     /// If you are appending and you do not have the size of the column readily
 158     /// available, call the 3 argument version instead. If you are not
 159     /// appending, either one is fine.
 160     ///
 161     /// \param is_append Must be true if, and only if `row_ndx` is equal to the
 162     /// size of the column (before insertion).
 163     void do_insert(size_t row_ndx, StringData value, size_t num_rows, bool is_append);
 164
 165     /// \param row_ndx Must be `realm::npos` if appending.
 166     void bptree_insert(size_t row_ndx, StringData value, size_t num_rows);
 167
 168     // Called by Array::bptree_insert().
 169     static ref_type leaf_insert(MemRef leaf_mem, ArrayParent&, size_t ndx_in_parent, Allocator&, size_t insert_ndx,
 170                                 BpTreeNode::TreeInsert<StringColumn>& state);
 171
 172     class EraseLeafElem;
 173     class CreateHandler;
 174     class SliceHandler;
 175
 176     void do_erase(size_t row_ndx, bool is_last);
 177     void do_move_last_over(size_t row_ndx, size_t last_row_ndx);
 178     void do_swap_rows(size_t row_ndx_1, size_t row_ndx_2);
 179     void do_clear();
 180
 181     /// Root must be a leaf. Upgrades the root leaf as
 182     /// necessary. Returns the type of the root leaf as it is upon
 183     /// return.
 184     LeafType upgrade_root_leaf(size_t value_size);
 185
 186     void refresh_root_accessor();
 187
 188     void leaf_to_dot(MemRef, ArrayParent*, size_t ndx_in_parent, std::ostream&) const override;
 189
 190     friend class BpTreeNode;
 191     friend class ColumnBase;
 192 };
 193
 194
 195 // Implementation:
 196
 197 inline size_t StringColumn::size() const noexcept
 198 {
 199     if (root_is_leaf()) {
 200         bool long_strings = m_array->has_refs();
 201         if (!long_strings) {
 202             // Small strings root leaf
 203             ArrayString* leaf = static_cast<ArrayString*>(m_array.get());
 204             return leaf->size();
 205         }
 206         bool is_big = m_array->get_context_flag();
 207         if (!is_big) {
 208             // Medium strings root leaf
 209             ArrayStringLong* leaf = static_cast<ArrayStringLong*>(m_array.get());
 210             return leaf->size();
 211         }
 212         // Big strings root leaf
 213         ArrayBigBlobs* leaf = static_cast<ArrayBigBlobs*>(m_array.get());
 214         return leaf->size();
 215     }
 216     // Non-leaf root
 217     BpTreeNode* node = static_cast<BpTreeNode*>(m_array.get());
 218     return node->get_bptree_size();
 219 }
 220
 221 inline void StringColumn::add(StringData value)
 222 {
 223     REALM_ASSERT(!(value.is_null() && !m_nullable));
 224     size_t row_ndx = realm::npos;
 225     size_t num_rows = 1;
 226     do_insert(row_ndx, value, num_rows); // Throws
 227 }
 228
 229 inline void StringColumn::add()
 230 {
 231     add(m_nullable ? realm::null() : StringData(""));
 232 }
 233
 234 inline void StringColumn::insert(size_t row_ndx, StringData value)
 235 {
 236     REALM_ASSERT(!(value.is_null() && !m_nullable));
 237     size_t column_size = this->size();
 238     REALM_ASSERT_3(row_ndx, <=, column_size);
 239     size_t num_rows = 1;
 240     bool is_append = row_ndx == column_size;
 241     do_insert(row_ndx, value, num_rows, is_append); // Throws
 242 }
 243
 244 inline void StringColumn::insert(size_t row_ndx)
 245 {
 246     insert(row_ndx, m_nullable ? realm::null() : StringData(""));
 247 }
 248
 249 inline void StringColumn::erase(size_t row_ndx)
 250 {
 251     size_t last_row_ndx = size() - 1; // Note that size() is slow
 252     bool is_last = row_ndx == last_row_ndx;
 253     do_erase(row_ndx, is_last); // Throws
 254 }
 255
 256 inline void StringColumn::move_last_over(size_t row_ndx)
 257 {
 258     size_t last_row_ndx = size() - 1;         // Note that size() is slow
 259     do_move_last_over(row_ndx, last_row_ndx); // Throws
 260 }
 261
 262 inline void StringColumn::swap_rows(size_t row_ndx_1, size_t row_ndx_2)
 263 {
 264     do_swap_rows(row_ndx_1, row_ndx_2); // Throws
 265 }
 266
 267 inline void StringColumn::clear()
 268 {
 269     do_clear(); // Throws
 270 }
 271
 272 inline int StringColumn::compare_values(size_t row1, size_t row2) const noexcept
 273 {
 274     StringData a = get(row1);
 275     StringData b = get(row2);
 276
 277     if (a.is_null() && !b.is_null())
 278         return 1;
 279     else if (b.is_null() && !a.is_null())
 280         return -1;
 281     else if (a.is_null() && b.is_null())
 282         return 0;
 283
 284     if (a == b)
 285         return 0;
 286     return utf8_compare(a, b) ? 1 : -1;
 287 }
 288
 289 inline void StringColumn::set_string(size_t row_ndx, StringData value)
 290 {
 291     REALM_ASSERT(!(value.is_null() && !m_nullable));
 292     set(row_ndx, value); // Throws
 293 }
 294
 295 inline bool StringColumn::has_search_index() const noexcept
 296 {
 297     return m_search_index != 0;
 298 }
 299
 300 inline StringIndex* StringColumn::get_search_index() noexcept
 301 {
 302     return m_search_index.get();
 303 }
 304
 305 inline const StringIndex* StringColumn::get_search_index() const noexcept
 306 {
 307     return m_search_index.get();
 308 }
 309
 310 inline size_t StringColumn::get_size_from_ref(ref_type root_ref, Allocator& alloc) noexcept
 311 {
 312     const char* root_header = alloc.translate(root_ref);
 313     bool root_is_leaf = !Array::get_is_inner_bptree_node_from_header(root_header);
 314     if (root_is_leaf) {
 315         bool long_strings = Array::get_hasrefs_from_header(root_header);
 316         if (!long_strings) {
 317             // Small strings leaf
 318             return ArrayString::get_size_from_header(root_header);
 319         }
 320         bool is_big = Array::get_context_flag_from_header(root_header);
 321         if (!is_big) {
 322             // Medium strings leaf
 323             return ArrayStringLong::get_size_from_header(root_header, alloc);
 324         }
 325         // Big strings leaf
 326         return ArrayBigBlobs::get_size_from_header(root_header);
 327     }
 328
 329     return BpTreeNode::get_bptree_size_from_header(root_header);
 330 }
 331
 332 // Implementing pure virtual method of ColumnBase.
 333 inline void StringColumn::insert_rows(size_t row_ndx, size_t num_rows_to_insert, size_t prior_num_rows,
 334                                       bool insert_nulls)
 335 {
 336     REALM_ASSERT_DEBUG(prior_num_rows == size());
 337     REALM_ASSERT(row_ndx <= prior_num_rows);
 338     REALM_ASSERT(!insert_nulls || m_nullable);
 339
 340     StringData value = m_nullable ? realm::null() : StringData("");
 341     bool is_append = (row_ndx == prior_num_rows);
 342     do_insert(row_ndx, value, num_rows_to_insert, is_append); // Throws
 343 }
 344
 345 // Implementing pure virtual method of ColumnBase.
 346 inline void StringColumn::erase_rows(size_t row_ndx, size_t num_rows_to_erase, size_t prior_num_rows, bool)
 347 {
 348     REALM_ASSERT_DEBUG(prior_num_rows == size());
 349     REALM_ASSERT(num_rows_to_erase <= prior_num_rows);
 350     REALM_ASSERT(row_ndx <= prior_num_rows - num_rows_to_erase);
 351
 352     bool is_last = (row_ndx + num_rows_to_erase == prior_num_rows);
 353     for (size_t i = num_rows_to_erase; i > 0; --i) {
 354         size_t row_ndx_2 = row_ndx + i - 1;
 355         do_erase(row_ndx_2, is_last); // Throws
 356     }
 357 }
 358
 359 // Implementing pure virtual method of ColumnBase.
 360 inline void StringColumn::move_last_row_over(size_t row_ndx, size_t prior_num_rows, bool)
 361 {
 362     REALM_ASSERT_DEBUG(prior_num_rows == size());
 363     REALM_ASSERT(row_ndx < prior_num_rows);
 364
 365     size_t last_row_ndx = prior_num_rows - 1;
 366     do_move_last_over(row_ndx, last_row_ndx); // Throws
 367 }
 368
 369 // Implementing pure virtual method of ColumnBase.
 370 inline void StringColumn::clear(size_t, bool)
 371 {
 372     do_clear(); // Throws
 373 }
 374
 375 } // namespace realm
 376
 377 #endif // REALM_COLUMN_STRING_HPP