iOS/Pods/Realm/include/core/realm/column_linklist.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_LINKLIST_HPP
  20 #define REALM_COLUMN_LINKLIST_HPP
  21
  22 #include <algorithm>
  23 #include <vector>
  24
  25 #include <realm/column.hpp>
  26 #include <realm/column_linkbase.hpp>
  27 #include <realm/table.hpp>
  28 #include <realm/column_backlink.hpp>
  29 #include <realm/link_view_fwd.hpp>
  30
  31 namespace realm {
  32
  33 namespace _impl {
  34 class TransactLogConvenientEncoder;
  35 }
  36
  37
  38 /// A column of link lists (LinkListColumn) is a single B+-tree, and the root of
  39 /// the column is the root of the B+-tree. All leaf nodes are single arrays of
  40 /// type Array with the hasRefs bit set.
  41 ///
  42 /// The individual values in the column are either refs to Columns containing the
  43 /// row positions in the target table, or in the case where they are empty, a zero
  44 /// ref.
  45 class LinkListColumn : public LinkColumnBase, public ArrayParent {
  46 public:
  47     using LinkColumnBase::LinkColumnBase;
  48     using value_type = ConstLinkViewRef;
  49     LinkListColumn(Allocator& alloc, ref_type ref, Table* table, size_t column_ndx);
  50     ~LinkListColumn() noexcept override;
  51
  52     static ref_type create(Allocator&, size_t size = 0);
  53
  54     bool is_nullable() const noexcept final;
  55
  56     bool has_links(size_t row_ndx) const noexcept;
  57     size_t get_link_count(size_t row_ndx) const noexcept;
  58
  59     ConstLinkViewRef get(size_t row_ndx) const;
  60     LinkViewRef get(size_t row_ndx);
  61
  62     bool is_null(size_t row_ndx) const noexcept final;
  63     void set_null(size_t row_ndx) final;
  64
  65     /// Compare two columns for equality.
  66     bool compare_link_list(const LinkListColumn&) const;
  67
  68     void to_json_row(size_t row_ndx, std::ostream& out) const;
  69
  70     void insert_rows(size_t, size_t, size_t, bool) override;
  71     void erase_rows(size_t, size_t, size_t, bool) override;
  72     void move_last_row_over(size_t, size_t, bool) override;
  73     void swap_rows(size_t, size_t) override;
  74     void clear(size_t, bool) override;
  75     void cascade_break_backlinks_to(size_t, CascadeState&) override;
  76     void cascade_break_backlinks_to_all_rows(size_t, CascadeState&) override;
  77     void update_from_parent(size_t) noexcept override;
  78     void adj_acc_clear_root_table() noexcept override;
  79     void adj_acc_insert_rows(size_t, size_t) noexcept override;
  80     void adj_acc_erase_row(size_t) noexcept override;
  81     void adj_acc_move_over(size_t, size_t) noexcept override;
  82     void adj_acc_swap_rows(size_t, size_t) noexcept override;
  83     void adj_acc_move_row(size_t, size_t) noexcept override;
  84     void adj_acc_merge_rows(size_t, size_t) noexcept override;
  85     void refresh_accessor_tree(size_t, const Spec&) override;
  86
  87     void verify() const override;
  88     void verify(const Table&, size_t) const override;
  89
  90 protected:
  91     void do_discard_child_accessors() noexcept override;
  92
  93 private:
  94     struct list_entry {
  95         size_t m_row_ndx;
  96         std::weak_ptr<LinkView> m_list;
  97         bool operator<(const list_entry& other) const
  98         {
  99             return m_row_ndx < other.m_row_ndx;
 100         }
 101     };
 102
 103     // The accessors stored in `m_list_accessors` are sorted by their row index.
 104     // When a LinkList accessor is destroyed because the last shared_ptr pointing
 105     // to it dies, its entry is implicitly replaced by a tombstone (an entry with
 106     // an empty `m_list`). These tombstones are pruned at a later time by
 107     // `prune_list_accessor_tombstones`. This is done to amortize the O(n) cost
 108     // of `std::vector::erase` that would otherwise be incurred each time an
 109     // accessor is removed.
 110     mutable std::vector<list_entry> m_list_accessors;
 111     mutable std::atomic<bool> m_list_accessors_contains_tombstones;
 112
 113     std::shared_ptr<LinkView> get_ptr(size_t row_ndx) const;
 114
 115     void do_nullify_link(size_t row_ndx, size_t old_target_row_ndx) override;
 116     void do_update_link(size_t row_ndx, size_t old_target_row_ndx, size_t new_target_row_ndx) override;
 117     void do_swap_link(size_t row_ndx, size_t target_row_ndx_1, size_t target_row_ndx_2) override;
 118
 119     void unregister_linkview();
 120     ref_type get_row_ref(size_t row_ndx) const noexcept;
 121     void set_row_ref(size_t row_ndx, ref_type new_ref);
 122     void add_backlink(size_t target_row, size_t source_row);
 123     void remove_backlink(size_t target_row, size_t source_row);
 124
 125     // ArrayParent overrides
 126     void update_child_ref(size_t child_ndx, ref_type new_ref) override;
 127     ref_type get_child_ref(size_t child_ndx) const noexcept override;
 128
 129     // These helpers are needed because of the way the B+-tree of links is
 130     // traversed in cascade_break_backlinks_to() and
 131     // cascade_break_backlinks_to_all_rows().
 132     void cascade_break_backlinks_to__leaf(size_t row_ndx, const Array& link_list_leaf, CascadeState&);
 133     void cascade_break_backlinks_to_all_rows__leaf(const Array& link_list_leaf, CascadeState&);
 134
 135     void discard_child_accessors() noexcept;
 136
 137     template <bool fix_ndx_in_parent>
 138     void adj_insert_rows(size_t row_ndx, size_t num_rows_inserted) noexcept;
 139
 140     template <bool fix_ndx_in_parent>
 141     void adj_erase_rows(size_t row_ndx, size_t num_rows_erased) noexcept;
 142
 143     template <bool fix_ndx_in_parent>
 144     void adj_move_over(size_t from_row_ndx, size_t to_row_ndx) noexcept;
 145
 146     template <bool fix_ndx_in_parent>
 147     void adj_move(size_t from_ndx, size_t to_ndx) noexcept;
 148
 149     template <bool fix_ndx_in_parent>
 150     void adj_swap(size_t row_ndx_1, size_t row_ndx_2) noexcept;
 151
 152     void prune_list_accessor_tombstones() noexcept;
 153     void validate_list_accessors() const noexcept;
 154
 155     std::pair<ref_type, size_t> get_to_dot_parent(size_t) const override;
 156
 157     friend class BacklinkColumn;
 158     friend class LinkView;
 159     friend class _impl::TransactLogConvenientEncoder;
 160 };
 161
 162
 163 // Implementation
 164
 165 inline LinkListColumn::LinkListColumn(Allocator& alloc, ref_type ref, Table* table, size_t column_ndx)
 166     : LinkColumnBase(alloc, ref, table, column_ndx)
 167 {
 168     m_list_accessors_contains_tombstones.store(false);
 169 }
 170
 171 inline LinkListColumn::~LinkListColumn() noexcept
 172 {
 173     discard_child_accessors();
 174 }
 175
 176 inline ref_type LinkListColumn::create(Allocator& alloc, size_t size)
 177 {
 178     return IntegerColumn::create(alloc, Array::type_HasRefs, size); // Throws
 179 }
 180
 181 inline bool LinkListColumn::is_nullable() const noexcept
 182 {
 183     return false;
 184 }
 185
 186 inline bool LinkListColumn::has_links(size_t row_ndx) const noexcept
 187 {
 188     ref_type ref = LinkColumnBase::get_as_ref(row_ndx);
 189     return (ref != 0);
 190 }
 191
 192 inline size_t LinkListColumn::get_link_count(size_t row_ndx) const noexcept
 193 {
 194     ref_type ref = LinkColumnBase::get_as_ref(row_ndx);
 195     if (ref == 0)
 196         return 0;
 197     return ColumnBase::get_size_from_ref(ref, get_alloc());
 198 }
 199
 200 inline ConstLinkViewRef LinkListColumn::get(size_t row_ndx) const
 201 {
 202     return get_ptr(row_ndx);
 203 }
 204
 205 inline LinkViewRef LinkListColumn::get(size_t row_ndx)
 206 {
 207     return get_ptr(row_ndx);
 208 }
 209
 210 inline bool LinkListColumn::is_null(size_t) const noexcept
 211 {
 212     return false;
 213 }
 214
 215 inline void LinkListColumn::set_null(size_t)
 216 {
 217     throw LogicError{LogicError::column_not_nullable};
 218 }
 219
 220 inline void LinkListColumn::do_discard_child_accessors() noexcept
 221 {
 222     discard_child_accessors();
 223 }
 224
 225 inline ref_type LinkListColumn::get_row_ref(size_t row_ndx) const noexcept
 226 {
 227     return LinkColumnBase::get_as_ref(row_ndx);
 228 }
 229
 230 inline void LinkListColumn::set_row_ref(size_t row_ndx, ref_type new_ref)
 231 {
 232     LinkColumnBase::set(row_ndx, new_ref); // Throws
 233 }
 234
 235 inline void LinkListColumn::add_backlink(size_t target_row, size_t source_row)
 236 {
 237     m_backlink_column->add_backlink(target_row, source_row); // Throws
 238 }
 239
 240 inline void LinkListColumn::remove_backlink(size_t target_row, size_t source_row)
 241 {
 242     m_backlink_column->remove_one_backlink(target_row, source_row); // Throws
 243 }
 244
 245
 246 } // namespace realm
 247
 248 #endif // REALM_COLUMN_LINKLIST_HPP