--- /dev/null
+/*************************************************************************
+ *
+ * Copyright 2016 Realm Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ *
+ **************************************************************************/
+
+#ifndef REALM_INDEX_STRING_HPP
+#define REALM_INDEX_STRING_HPP
+
+#include <cstring>
+#include <memory>
+#include <array>
+
+#include <realm/array.hpp>
+#include <realm/column_fwd.hpp>
+
+/*
+The StringIndex class is used for both type_String and all integral types, such as type_Bool, type_OldDateTime and
+type_Int. When used for integral types, the 64-bit integer is simply casted to a string of 8 bytes through a
+pretty simple "wrapper layer" in all public methods.
+
+The StringIndex data structure is like an "inversed" B+ tree where the leafs contain row indexes and the non-leafs
+contain 4-byte chunks of payload. Imagine a table with following strings:
+
+ hello, kitty, kitten, foobar, kitty, foobar
+
+The topmost level of the index tree contains prefixes of the payload strings of length <= 4. The next level contains
+prefixes of the remaining parts of the strings. Unnecessary levels of the tree are optimized away; the prefix "foob"
+is shared only by rows that are identical ("foobar"), so "ar" is not needed to be stored in the tree.
+
+ hell kitt foob
+ | /\ |
+ 0 en y {3, 5}
+ | \
+ {1, 4} 2
+
+Each non-leafs consists of two integer arrays of the same length, one containing payload and the other containing
+references to the sublevel nodes.
+
+The leafs can be either a single value or a Column. If the reference in its parent node has its least significant
+bit set, then the remaining upper bits specify the row index at which the string is stored. If the bit is clear,
+it must be interpreted as a reference to a Column that stores the row indexes at which the string is stored.
+
+If a Column is used, then all row indexes are guaranteed to be sorted increasingly, which means you an search in it
+using our binary search functions such as upper_bound() and lower_bound(). Each duplicate value will be stored in
+the same Column, but Columns may contain more than just duplicates if the depth of the tree exceeds the value
+`s_max_offset` This is to avoid stack overflow problems with many of our recursive functions if we have two very
+long strings that have a long common prefix but differ in the last couple bytes. If a Column stores more than just
+duplicates, then the list is kept sorted in ascending order by string value and within the groups of common
+strings, the rows are sorted in ascending order.
+*/
+
+namespace realm {
+
+class Spec;
+class Timestamp;
+
+class IndexArray : public Array {
+public:
+ IndexArray(Allocator& allocator)
+ : Array(allocator)
+ {
+ }
+
+ size_t index_string_find_first(StringData value, ColumnBase* column) const;
+ void index_string_find_all(IntegerColumn& result, StringData value, ColumnBase* column, bool case_insensitive = false) const;
+ FindRes index_string_find_all_no_copy(StringData value, ColumnBase* column, InternalFindResult& result) const;
+ size_t index_string_count(StringData value, ColumnBase* column) const;
+
+private:
+ template <IndexMethod>
+ size_t from_list(StringData value, InternalFindResult& result_ref, const IntegerColumn& rows,
+ ColumnBase* column) const;
+
+ void from_list_all(StringData value, IntegerColumn& result, const IntegerColumn& rows, ColumnBase* column) const;
+
+ void from_list_all_ins(StringData value, std::vector<size_t>& result, const IntegerColumn& rows,
+ ColumnBase* column) const;
+
+ template <IndexMethod method>
+ size_t index_string(StringData value, InternalFindResult& result_ref, ColumnBase* column) const;
+
+ void index_string_all(StringData value, IntegerColumn& result, ColumnBase* column) const;
+
+ void index_string_all_ins(StringData value, IntegerColumn& result, ColumnBase* column) const;
+};
+
+
+class StringIndex {
+public:
+ StringIndex(ColumnBase* target_column, Allocator&);
+ StringIndex(ref_type, ArrayParent*, size_t ndx_in_parent, ColumnBase* target_column, Allocator&);
+ ~StringIndex() noexcept
+ {
+ }
+
+ static ref_type create_empty(Allocator& alloc);
+
+ void set_target(ColumnBase* target_column) noexcept;
+
+ // Accessor concept:
+ Allocator& get_alloc() const noexcept;
+ void destroy() noexcept;
+ void detach();
+ bool is_attached() const noexcept;
+ void set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept;
+ size_t get_ndx_in_parent() const noexcept;
+ void set_ndx_in_parent(size_t ndx_in_parent) noexcept;
+ void update_from_parent(size_t old_baseline) noexcept;
+ void refresh_accessor_tree(size_t, const Spec&);
+ ref_type get_ref() const noexcept;
+
+ // StringIndex interface:
+
+ // 12 is the biggest element size of any non-string/binary Realm type
+ static const size_t string_conversion_buffer_size = 12;
+ using StringConversionBuffer = std::array<char, string_conversion_buffer_size>;
+
+ bool is_empty() const;
+
+ template <class T>
+ void insert(size_t row_ndx, T value, size_t num_rows, bool is_append);
+ template <class T>
+ void insert(size_t row_ndx, util::Optional<T> value, size_t num_rows, bool is_append);
+
+ template <class T>
+ void set(size_t row_ndx, T new_value);
+ template <class T>
+ void set(size_t row_ndx, util::Optional<T> new_value);
+
+ template <class T>
+ void erase(size_t row_ndx, bool is_last);
+
+ template <class T>
+ size_t find_first(T value) const;
+ template <class T>
+ void find_all(IntegerColumn& result, T value, bool case_insensitive = false) const;
+ template <class T>
+ FindRes find_all_no_copy(T value, InternalFindResult& result) const;
+ template <class T>
+ size_t count(T value) const;
+ template <class T>
+ void update_ref(T value, size_t old_row_ndx, size_t new_row_ndx);
+
+ void clear();
+
+ void distinct(IntegerColumn& result) const;
+ bool has_duplicate_values() const noexcept;
+
+ void verify() const;
+#ifdef REALM_DEBUG
+ template <typename T>
+ void verify_entries(const T& column) const;
+ void do_dump_node_structure(std::ostream&, int) const;
+ void to_dot() const;
+ void to_dot(std::ostream&, StringData title = StringData()) const;
+ void to_dot_2(std::ostream&, StringData title = StringData()) const;
+#endif
+
+ typedef int32_t key_type;
+
+ // s_max_offset specifies the number of levels of recursive string indexes
+ // allowed before storing everything in lists. This is to avoid nesting
+ // to too deep of a level. Since every SubStringIndex stores 4 bytes, this
+ // means that a StringIndex is helpful for strings of a common prefix up to
+ // 4 times this limit (200 bytes shared). Lists are stored in sorted order,
+ // so strings sharing a common prefix of more than this limit will use a
+ // binary search of approximate complexity log2(n) from `std::lower_bound`.
+ static const size_t s_max_offset = 200; // max depth * s_index_key_length
+ static const size_t s_index_key_length = 4;
+ static key_type create_key(StringData) noexcept;
+ static key_type create_key(StringData, size_t) noexcept;
+
+private:
+ // m_array is a compact representation for storing the children of this StringIndex.
+ // Children can be:
+ // 1) a row number
+ // 2) a reference to a list which stores row numbers (for duplicate strings).
+ // 3) a reference to a sub-index
+ // m_array[0] is always a reference to a values array which stores the 4 byte chunk
+ // of payload data for quick string chunk comparisons. The array stored
+ // at m_array[0] lines up with the indices of values in m_array[1] so for example
+ // starting with an empty StringIndex:
+ // StringColumn::insert(target_row_ndx=42, value="test_string") would result with
+ // get_array_from_ref(m_array[0])[0] == create_key("test") and
+ // m_array[1] == 42
+ // In this way, m_array which stores one child has a size of two.
+ // Children are type 1 (row number) if the LSB of the value is set.
+ // To get the actual row value, shift value down by one.
+ // If the LSB of the value is 0 then the value is a reference and can be either
+ // type 2, or type 3 (no shifting in either case).
+ // References point to a list if the context header flag is NOT set.
+ // If the header flag is set, references point to a sub-StringIndex (nesting).
+ std::unique_ptr<IndexArray> m_array;
+ ColumnBase* m_target_column;
+
+ struct inner_node_tag {
+ };
+ StringIndex(inner_node_tag, Allocator&);
+
+ static IndexArray* create_node(Allocator&, bool is_leaf);
+
+ void insert_with_offset(size_t row_ndx, StringData value, size_t offset);
+ void insert_row_list(size_t ref, size_t offset, StringData value);
+ void insert_to_existing_list(size_t row, StringData value, IntegerColumn& list);
+ void insert_to_existing_list_at_lower(size_t row, StringData value, IntegerColumn& list,
+ const IntegerColumnIterator& lower);
+ key_type get_last_key() const;
+
+ /// Add small signed \a diff to all elements that are greater than, or equal
+ /// to \a min_row_ndx.
+ void adjust_row_indexes(size_t min_row_ndx, int diff);
+
+ struct NodeChange {
+ size_t ref1;
+ size_t ref2;
+ enum ChangeType { none, insert_before, insert_after, split } type;
+ NodeChange(ChangeType t, size_t r1 = 0, size_t r2 = 0)
+ : ref1(r1)
+ , ref2(r2)
+ , type(t)
+ {
+ }
+ NodeChange()
+ : ref1(0)
+ , ref2(0)
+ , type(none)
+ {
+ }
+ };
+
+ // B-Tree functions
+ void TreeInsert(size_t row_ndx, key_type, size_t offset, StringData value);
+ NodeChange do_insert(size_t ndx, key_type, size_t offset, StringData value);
+ /// Returns true if there is room or it can join existing entries
+ bool leaf_insert(size_t row_ndx, key_type, size_t offset, StringData value, bool noextend = false);
+ void node_insert_split(size_t ndx, size_t new_ref);
+ void node_insert(size_t ndx, size_t ref);
+ void do_delete(size_t ndx, StringData, size_t offset);
+ void do_update_ref(StringData value, size_t row_ndx, size_t new_row_ndx, size_t offset);
+
+ StringData get(size_t ndx, StringConversionBuffer& buffer) const;
+
+ void node_add_key(ref_type ref);
+
+#ifdef REALM_DEBUG
+ static void dump_node_structure(const Array& node, std::ostream&, int level);
+ static void array_to_dot(std::ostream&, const Array&);
+ static void keys_to_dot(std::ostream&, const Array&, StringData title = StringData());
+#endif
+};
+
+
+class SortedListComparator {
+public:
+ SortedListComparator(ColumnBase& column_values);
+ bool operator()(int64_t ndx, StringData needle);
+ bool operator()(StringData needle, int64_t ndx);
+
+private:
+ ColumnBase& values;
+};
+
+
+// Implementation:
+
+template <class T>
+struct GetIndexData;
+
+template <>
+struct GetIndexData<int64_t> {
+ static StringData get_index_data(const int64_t& value, StringIndex::StringConversionBuffer& buffer)
+ {
+ const char* c = reinterpret_cast<const char*>(&value);
+ realm::safe_copy_n(c, sizeof(int64_t), buffer.data());
+ return StringData{buffer.data(), sizeof(int64_t)};
+ }
+};
+
+template <>
+struct GetIndexData<StringData> {
+ static StringData get_index_data(StringData data, StringIndex::StringConversionBuffer&)
+ {
+ return data;
+ }
+};
+
+template <>
+struct GetIndexData<null> {
+ static StringData get_index_data(null, StringIndex::StringConversionBuffer&)
+ {
+ return null{};
+ }
+};
+
+template <>
+struct GetIndexData<Timestamp> {
+ static StringData get_index_data(const Timestamp&, StringIndex::StringConversionBuffer&);
+};
+
+template <class T>
+struct GetIndexData<util::Optional<T>> {
+ static StringData get_index_data(const util::Optional<T>& value, StringIndex::StringConversionBuffer& buffer)
+ {
+ if (value)
+ return GetIndexData<T>::get_index_data(*value, buffer);
+ return null{};
+ }
+};
+
+template <>
+struct GetIndexData<float> {
+ static StringData get_index_data(float, StringIndex::StringConversionBuffer&)
+ {
+ REALM_ASSERT_RELEASE(false); // LCOV_EXCL_LINE; Index on float not supported
+ }
+};
+
+template <>
+struct GetIndexData<double> {
+ static StringData get_index_data(double, StringIndex::StringConversionBuffer&)
+ {
+ REALM_ASSERT_RELEASE(false); // LCOV_EXCL_LINE; Index on float not supported
+ }
+};
+
+template <>
+struct GetIndexData<const char*> : GetIndexData<StringData> {
+};
+
+// to_str() is used by the integer index. The existing StringIndex is re-used for this
+// by making IntegerColumn convert its integers to strings by calling to_str().
+
+template <class T>
+inline StringData to_str(T&& value, StringIndex::StringConversionBuffer& buffer)
+{
+ return GetIndexData<typename std::remove_reference<T>::type>::get_index_data(value, buffer);
+}
+
+
+inline StringIndex::StringIndex(ColumnBase* target_column, Allocator& alloc)
+ : m_array(create_node(alloc, true)) // Throws
+ , m_target_column(target_column)
+{
+}
+
+inline StringIndex::StringIndex(ref_type ref, ArrayParent* parent, size_t ndx_in_parent, ColumnBase* target_column,
+ Allocator& alloc)
+ : m_array(new IndexArray(alloc))
+ , m_target_column(target_column)
+{
+ REALM_ASSERT_EX(Array::get_context_flag_from_header(alloc.translate(ref)), ref, size_t(alloc.translate(ref)));
+ m_array->init_from_ref(ref);
+ set_parent(parent, ndx_in_parent);
+}
+
+inline StringIndex::StringIndex(inner_node_tag, Allocator& alloc)
+ : m_array(create_node(alloc, false)) // Throws
+ , m_target_column(nullptr)
+{
+}
+
+// Byte order of the key is *reversed*, so that for the integer index, the least significant
+// byte comes first, so that it fits little-endian machines. That way we can perform fast
+// range-lookups and iterate in order, etc, as future features. This, however, makes the same
+// features slower for string indexes. Todo, we should reverse the order conditionally, depending
+// on the column type.
+inline StringIndex::key_type StringIndex::create_key(StringData str) noexcept
+{
+ key_type key = 0;
+
+ if (str.size() >= 4)
+ goto four;
+ if (str.size() < 2) {
+ if (str.size() == 0)
+ goto none;
+ goto one;
+ }
+ if (str.size() == 2)
+ goto two;
+ goto three;
+
+// Create 4 byte index key
+// (encoded like this to allow literal comparisons
+// independently of endianness)
+four:
+ key |= (key_type(static_cast<unsigned char>(str[3])) << 0);
+three:
+ key |= (key_type(static_cast<unsigned char>(str[2])) << 8);
+two:
+ key |= (key_type(static_cast<unsigned char>(str[1])) << 16);
+one:
+ key |= (key_type(static_cast<unsigned char>(str[0])) << 24);
+none:
+ return key;
+}
+
+// Index works as follows: All non-NULL values are stored as if they had appended an 'X' character at the end. So
+// "foo" is stored as if it was "fooX", and "" (empty string) is stored as "X". And NULLs are stored as empty strings.
+inline StringIndex::key_type StringIndex::create_key(StringData str, size_t offset) noexcept
+{
+ if (str.is_null())
+ return 0;
+
+ if (offset > str.size())
+ return 0;
+
+ // for very short strings
+ size_t tail = str.size() - offset;
+ if (tail <= sizeof(key_type) - 1) {
+ char buf[sizeof(key_type)];
+ memset(buf, 0, sizeof(key_type));
+ buf[tail] = 'X';
+ memcpy(buf, str.data() + offset, tail);
+ return create_key(StringData(buf, tail + 1));
+ }
+ // else fallback
+ return create_key(str.substr(offset));
+}
+
+template <class T>
+void StringIndex::insert(size_t row_ndx, T value, size_t num_rows, bool is_append)
+{
+ REALM_ASSERT_3(row_ndx, !=, npos);
+
+ // If the new row is inserted after the last row in the table, we don't need
+ // to adjust any row indexes.
+ if (!is_append) {
+ for (size_t i = 0; i < num_rows; ++i) {
+ size_t row_ndx_2 = row_ndx + i;
+ adjust_row_indexes(row_ndx_2, 1); // Throws
+ }
+ }
+
+ StringConversionBuffer buffer;
+
+ for (size_t i = 0; i < num_rows; ++i) {
+ size_t row_ndx_2 = row_ndx + i;
+ size_t offset = 0; // First key from beginning of string
+ insert_with_offset(row_ndx_2, to_str(value, buffer), offset); // Throws
+ }
+}
+
+template <class T>
+void StringIndex::insert(size_t row_ndx, util::Optional<T> value, size_t num_rows, bool is_append)
+{
+ if (value) {
+ insert(row_ndx, *value, num_rows, is_append);
+ }
+ else {
+ insert(row_ndx, null{}, num_rows, is_append);
+ }
+}
+
+template <class T>
+void StringIndex::set(size_t row_ndx, T new_value)
+{
+ StringConversionBuffer buffer;
+ StringConversionBuffer buffer2;
+ StringData old_value = get(row_ndx, buffer);
+ StringData new_value2 = to_str(new_value, buffer2);
+
+ // Note that insert_with_offset() throws UniqueConstraintViolation.
+
+ if (REALM_LIKELY(new_value2 != old_value)) {
+ // We must erase this row first because erase uses find_first which
+ // might find the duplicate if we insert before erasing.
+ bool is_last = true; // To avoid updating refs
+ erase<T>(row_ndx, is_last); // Throws
+
+ size_t offset = 0; // First key from beginning of string
+ insert_with_offset(row_ndx, new_value2, offset); // Throws
+ }
+}
+
+template <class T>
+void StringIndex::set(size_t row_ndx, util::Optional<T> new_value)
+{
+ if (new_value) {
+ set(row_ndx, *new_value);
+ }
+ else {
+ set(row_ndx, null{});
+ }
+}
+
+template <class T>
+void StringIndex::erase(size_t row_ndx, bool is_last)
+{
+ StringConversionBuffer buffer;
+ StringData value = get(row_ndx, buffer);
+
+ do_delete(row_ndx, value, 0);
+
+ // Collapse top nodes with single item
+ while (m_array->is_inner_bptree_node()) {
+ REALM_ASSERT(m_array->size() > 1); // node cannot be empty
+ if (m_array->size() > 2)
+ break;
+
+ ref_type ref = m_array->get_as_ref(1);
+ m_array->set(1, 1); // avoid destruction of the extracted ref
+ m_array->destroy_deep();
+ m_array->init_from_ref(ref);
+ m_array->update_parent();
+ }
+
+ // If it is last item in column, we don't have to update refs
+ if (!is_last)
+ adjust_row_indexes(row_ndx, -1);
+}
+
+template <class T>
+size_t StringIndex::find_first(T value) const
+{
+ // Use direct access method
+ StringConversionBuffer buffer;
+ return m_array->index_string_find_first(to_str(value, buffer), m_target_column);
+}
+
+template <class T>
+void StringIndex::find_all(IntegerColumn& result, T value, bool case_insensitive) const
+{
+ // Use direct access method
+ StringConversionBuffer buffer;
+ return m_array->index_string_find_all(result, to_str(value, buffer), m_target_column, case_insensitive);
+}
+
+template <class T>
+FindRes StringIndex::find_all_no_copy(T value, InternalFindResult& result) const
+{
+ // Use direct access method
+ StringConversionBuffer buffer;
+ return m_array->index_string_find_all_no_copy(to_str(value, buffer), m_target_column, result);
+}
+
+template <class T>
+size_t StringIndex::count(T value) const
+{
+ // Use direct access method
+ StringConversionBuffer buffer;
+ return m_array->index_string_count(to_str(value, buffer), m_target_column);
+}
+
+template <class T>
+void StringIndex::update_ref(T value, size_t old_row_ndx, size_t new_row_ndx)
+{
+ StringConversionBuffer buffer;
+ do_update_ref(to_str(value, buffer), old_row_ndx, new_row_ndx, 0);
+}
+
+inline void StringIndex::destroy() noexcept
+{
+ return m_array->destroy_deep();
+}
+
+inline bool StringIndex::is_attached() const noexcept
+{
+ return m_array->is_attached();
+}
+
+inline void StringIndex::refresh_accessor_tree(size_t, const Spec&)
+{
+ m_array->init_from_parent();
+}
+
+inline ref_type StringIndex::get_ref() const noexcept
+{
+ return m_array->get_ref();
+}
+
+inline void StringIndex::set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept
+{
+ m_array->set_parent(parent, ndx_in_parent);
+}
+
+inline size_t StringIndex::get_ndx_in_parent() const noexcept
+{
+ return m_array->get_ndx_in_parent();
+}
+
+inline void StringIndex::set_ndx_in_parent(size_t ndx_in_parent) noexcept
+{
+ m_array->set_ndx_in_parent(ndx_in_parent);
+}
+
+inline void StringIndex::update_from_parent(size_t old_baseline) noexcept
+{
+ m_array->update_from_parent(old_baseline);
+}
+
+} // namespace realm
+
+#endif // REALM_INDEX_STRING_HPP
fnp / wl-app.git / blobdiff