iOS/Pods/Realm/include/core/realm/column_backlink.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_BACKLINK_HPP
  20 #define REALM_COLUMN_BACKLINK_HPP
  21
  22 #include <vector>
  23
  24 #include <realm/column.hpp>
  25 #include <realm/column_linkbase.hpp>
  26 #include <realm/table.hpp>
  27
  28 namespace realm {
  29
  30 /// A column of backlinks (BacklinkColumn) is a single B+-tree, and the root of
  31 /// the column is the root of the B+-tree. All leaf nodes are single arrays of
  32 /// type Array with the hasRefs bit set.
  33 ///
  34 /// The individual values in the column are either refs to Columns containing
  35 /// the row indexes in the origin table that links to it, or in the case where
  36 /// there is a single link, a tagged ref encoding the origin row position.
  37 class BacklinkColumn : public IntegerColumn, public ArrayParent {
  38 public:
  39     BacklinkColumn(Allocator&, ref_type, size_t col_ndx = npos);
  40     ~BacklinkColumn() noexcept override
  41     {
  42     }
  43
  44     static ref_type create(Allocator&, size_t size = 0);
  45
  46     bool has_backlinks(size_t row_ndx) const noexcept;
  47     size_t get_backlink_count(size_t row_ndx) const noexcept;
  48     size_t get_backlink(size_t row_ndx, size_t backlink_ndx) const noexcept;
  49
  50     void add_backlink(size_t row_ndx, size_t origin_row_ndx);
  51     void remove_one_backlink(size_t row_ndx, size_t origin_row_ndx);
  52     void remove_all_backlinks(size_t num_rows);
  53     void update_backlink(size_t row_ndx, size_t old_origin_row_ndx, size_t new_origin_row_ndx);
  54     void swap_backlinks(size_t row_ndx, size_t origin_row_ndx_1, size_t origin_row_ndx_2);
  55
  56     void add_row();
  57
  58     // Link origination info
  59     Table& get_origin_table() const noexcept;
  60     void set_origin_table(Table&) noexcept;
  61     LinkColumnBase& get_origin_column() const noexcept;
  62     size_t get_origin_column_index() const noexcept;
  63     void set_origin_column(LinkColumnBase& column) noexcept;
  64
  65     void insert_rows(size_t, size_t, size_t, bool) override;
  66     void erase_rows(size_t, size_t, size_t, bool) override;
  67     void move_last_row_over(size_t, size_t, bool) override;
  68     void swap_rows(size_t, size_t) override;
  69     void clear(size_t, bool) override;
  70     void adj_acc_insert_rows(size_t, size_t) noexcept override;
  71     void adj_acc_erase_row(size_t) noexcept override;
  72     void adj_acc_move_over(size_t, size_t) noexcept override;
  73     void adj_acc_swap_rows(size_t, size_t) noexcept override;
  74     void adj_acc_move_row(size_t, size_t) noexcept override;
  75     void adj_acc_merge_rows(size_t, size_t) noexcept override;
  76     void adj_acc_clear_root_table() noexcept override;
  77     void mark(int) noexcept override;
  78
  79     void bump_link_origin_table_version() noexcept override;
  80
  81     void cascade_break_backlinks_to(size_t row_ndx, CascadeState& state) override;
  82     void cascade_break_backlinks_to_all_rows(size_t num_rows, CascadeState&) override;
  83
  84     int compare_values(size_t, size_t) const noexcept override;
  85
  86     void verify() const override;
  87     void verify(const Table&, size_t) const override;
  88 #ifdef REALM_DEBUG
  89     struct VerifyPair {
  90         size_t origin_row_ndx, target_row_ndx;
  91         bool operator<(const VerifyPair&) const noexcept;
  92     };
  93     void get_backlinks(std::vector<VerifyPair>&); // Sorts
  94 #endif
  95
  96 protected:
  97     // ArrayParent overrides
  98     void update_child_ref(size_t child_ndx, ref_type new_ref) override;
  99     ref_type get_child_ref(size_t child_ndx) const noexcept override;
 100
 101     std::pair<ref_type, size_t> get_to_dot_parent(size_t) const override;
 102
 103 private:
 104     TableRef m_origin_table;
 105     LinkColumnBase* m_origin_column = nullptr;
 106
 107     template <typename Func>
 108     size_t for_each_link(size_t row_ndx, bool do_destroy, Func&& f);
 109 };
 110
 111
 112 // Implementation
 113
 114 inline BacklinkColumn::BacklinkColumn(Allocator& alloc, ref_type ref, size_t col_ndx)
 115     : IntegerColumn(alloc, ref, col_ndx) // Throws
 116 {
 117 }
 118
 119 inline ref_type BacklinkColumn::create(Allocator& alloc, size_t size)
 120 {
 121     return IntegerColumn::create(alloc, Array::type_HasRefs, size); // Throws
 122 }
 123
 124 inline bool BacklinkColumn::has_backlinks(size_t ndx) const noexcept
 125 {
 126     return IntegerColumn::get(ndx) != 0;
 127 }
 128
 129 inline Table& BacklinkColumn::get_origin_table() const noexcept
 130 {
 131     return *m_origin_table;
 132 }
 133
 134 inline void BacklinkColumn::set_origin_table(Table& table) noexcept
 135 {
 136     REALM_ASSERT(!m_origin_table);
 137     m_origin_table = table.get_table_ref();
 138 }
 139
 140 inline LinkColumnBase& BacklinkColumn::get_origin_column() const noexcept
 141 {
 142     return *m_origin_column;
 143 }
 144
 145 inline size_t BacklinkColumn::get_origin_column_index() const noexcept
 146 {
 147     return m_origin_column ? m_origin_column->get_column_index() : npos;
 148 }
 149
 150 inline void BacklinkColumn::set_origin_column(LinkColumnBase& column) noexcept
 151 {
 152     m_origin_column = &column;
 153 }
 154
 155 inline void BacklinkColumn::add_row()
 156 {
 157     IntegerColumn::add(0);
 158 }
 159
 160 inline void BacklinkColumn::adj_acc_insert_rows(size_t row_ndx, size_t num_rows) noexcept
 161 {
 162     IntegerColumn::adj_acc_insert_rows(row_ndx, num_rows);
 163
 164     typedef _impl::TableFriend tf;
 165     tf::mark(*m_origin_table);
 166 }
 167
 168 inline void BacklinkColumn::adj_acc_erase_row(size_t row_ndx) noexcept
 169 {
 170     IntegerColumn::adj_acc_erase_row(row_ndx);
 171
 172     typedef _impl::TableFriend tf;
 173     tf::mark(*m_origin_table);
 174 }
 175
 176 inline void BacklinkColumn::adj_acc_move_over(size_t from_row_ndx, size_t to_row_ndx) noexcept
 177 {
 178     IntegerColumn::adj_acc_move_over(from_row_ndx, to_row_ndx);
 179
 180     typedef _impl::TableFriend tf;
 181     tf::mark(*m_origin_table);
 182 }
 183
 184 inline void BacklinkColumn::adj_acc_swap_rows(size_t row_ndx_1, size_t row_ndx_2) noexcept
 185 {
 186     Column::adj_acc_swap_rows(row_ndx_1, row_ndx_2);
 187
 188     using tf = _impl::TableFriend;
 189     tf::mark(*m_origin_table);
 190 }
 191
 192 inline void BacklinkColumn::adj_acc_move_row(size_t from_ndx, size_t to_ndx) noexcept
 193 {
 194     Column::adj_acc_move_row(from_ndx, to_ndx);
 195
 196     using tf = _impl::TableFriend;
 197     tf::mark(*m_origin_table);
 198 }
 199
 200 inline void BacklinkColumn::adj_acc_merge_rows(size_t old_row_ndx, size_t new_row_ndx) noexcept
 201 {
 202     Column::adj_acc_merge_rows(old_row_ndx, new_row_ndx);
 203
 204     using tf = _impl::TableFriend;
 205     tf::mark(*m_origin_table);
 206 }
 207
 208 inline void BacklinkColumn::adj_acc_clear_root_table() noexcept
 209 {
 210     IntegerColumn::adj_acc_clear_root_table();
 211
 212     typedef _impl::TableFriend tf;
 213     tf::mark(*m_origin_table);
 214 }
 215
 216 inline void BacklinkColumn::mark(int type) noexcept
 217 {
 218     if (type & mark_LinkOrigins) {
 219         typedef _impl::TableFriend tf;
 220         tf::mark(*m_origin_table);
 221     }
 222 }
 223
 224 inline void BacklinkColumn::bump_link_origin_table_version() noexcept
 225 {
 226     // It is important to mark connected tables as modified.
 227     // Also see LinkColumnBase::bump_link_origin_table_version().
 228     typedef _impl::TableFriend tf;
 229     if (m_origin_table) {
 230         bool bump_global = false;
 231         tf::bump_version(*m_origin_table, bump_global);
 232     }
 233 }
 234
 235 #ifdef REALM_DEBUG
 236
 237 inline bool BacklinkColumn::VerifyPair::operator<(const VerifyPair& p) const noexcept
 238 {
 239     return origin_row_ndx < p.origin_row_ndx;
 240 }
 241
 242 #endif // REALM_DEBUG
 243
 244 } // namespace realm
 245
 246 #endif // REALM_COLUMN_BACKLINK_HPP