X-Git-Url: https://git.mdrn.pl/wl-app.git/blobdiff_plain/53b27422d140022594fc241cca91c3183be57bca..48b2fe9f7c2dc3d9aeaaa6dbfb27c7da4f3235ff:/iOS/Pods/Realm/include/core/realm/array.hpp diff --git a/iOS/Pods/Realm/include/core/realm/array.hpp b/iOS/Pods/Realm/include/core/realm/array.hpp new file mode 100644 index 0000000..cb3d7d9 --- /dev/null +++ b/iOS/Pods/Realm/include/core/realm/array.hpp @@ -0,0 +1,3100 @@ +/************************************************************************* + * + * 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. + * + **************************************************************************/ + +/* +Searching: The main finding function is: + template + void find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState *state, Callback callback) const + + cond: One of Equal, NotEqual, Greater, etc. classes + Action: One of act_ReturnFirst, act_FindAll, act_Max, act_CallbackIdx, etc, constants + Callback: Optional function to call for each search result. Will be called if action == act_CallbackIdx + + find() will call find_action_pattern() or find_action() that again calls match() for each search result which + optionally calls callback(): + + find() -> find_action() -------> bool match() -> bool callback() + | ^ + +-> find_action_pattern()----+ + + If callback() returns false, find() will exit, otherwise it will keep searching remaining items in array. +*/ + +#ifndef REALM_ARRAY_HPP +#define REALM_ARRAY_HPP + +#include +#include // size_t +#include +#include +#include +#include + +#include // unint8_t etc + +#include +#include +#include +#include +#include +#include +#include +#include + +/* + MMX: mmintrin.h + SSE: xmmintrin.h + SSE2: emmintrin.h + SSE3: pmmintrin.h + SSSE3: tmmintrin.h + SSE4A: ammintrin.h + SSE4.1: smmintrin.h + SSE4.2: nmmintrin.h +*/ +#ifdef REALM_COMPILER_SSE +#include // SSE2 +#include // SSE42 +#endif + +namespace realm { + +enum Action { + act_ReturnFirst, + act_Sum, + act_Max, + act_Min, + act_Count, + act_FindAll, + act_CallIdx, + act_CallbackIdx, + act_CallbackVal, + act_CallbackNone, + act_CallbackBoth, + act_Average +}; + +template +inline T no0(T v) +{ + return v == 0 ? 1 : v; +} + +/// Special index value. It has various meanings depending on +/// context. It is returned by some search functions to indicate 'not +/// found'. It is similar in function to std::string::npos. +const size_t npos = size_t(-1); + +// Maximum number of bytes that the payload of an array can be +const size_t max_array_payload = 0x00ffffffL; +const size_t max_array_payload_aligned = 0x00fffff8L; + +/// Alias for realm::npos. +const size_t not_found = npos; + +// Pre-definitions +class Array; +class StringColumn; +class GroupWriter; +template +class QueryState; +namespace _impl { +class ArrayWriterBase; +} + + +struct MemStats { + size_t allocated = 0; + size_t used = 0; + size_t array_count = 0; +}; + +#ifdef REALM_DEBUG +template +std::basic_ostream& operator<<(std::basic_ostream& out, MemStats stats); +#endif + + +// Stores a value obtained from Array::get(). It is a ref if the least +// significant bit is clear, otherwise it is a tagged integer. A tagged interger +// is obtained from a logical integer value by left shifting by one bit position +// (multiplying by two), and then setting the least significant bit to +// one. Clearly, this means that the maximum value that can be stored as a +// tagged integer is 2**63 - 1. +class RefOrTagged { +public: + bool is_ref() const noexcept; + bool is_tagged() const noexcept; + ref_type get_as_ref() const noexcept; + uint_fast64_t get_as_int() const noexcept; + + static RefOrTagged make_ref(ref_type) noexcept; + static RefOrTagged make_tagged(uint_fast64_t) noexcept; + +private: + int_fast64_t m_value; + RefOrTagged(int_fast64_t) noexcept; + friend class Array; +}; + + +class ArrayParent { +public: + virtual ~ArrayParent() noexcept + { + } + +protected: + virtual void update_child_ref(size_t child_ndx, ref_type new_ref) = 0; + + virtual ref_type get_child_ref(size_t child_ndx) const noexcept = 0; + + // Used only by Array::to_dot(). + virtual std::pair get_to_dot_parent(size_t ndx_in_parent) const = 0; + + friend class Array; +}; + +struct TreeInsertBase { + size_t m_split_offset; + size_t m_split_size; +}; + +/// Provides access to individual array nodes of the database. +/// +/// This class serves purely as an accessor, it assumes no ownership of the +/// referenced memory. +/// +/// An array accessor can be in one of two states: attached or unattached. It is +/// in the attached state if, and only if is_attached() returns true. Most +/// non-static member functions of this class have undefined behaviour if the +/// accessor is in the unattached state. The exceptions are: is_attached(), +/// detach(), create(), init_from_ref(), init_from_mem(), init_from_parent(), +/// has_parent(), get_parent(), set_parent(), get_ndx_in_parent(), +/// set_ndx_in_parent(), adjust_ndx_in_parent(), and get_ref_from_parent(). +/// +/// An array accessor contains information about the parent of the referenced +/// array node. This 'reverse' reference is not explicitely present in the +/// underlying node hierarchy, but it is needed when modifying an array. A +/// modification may lead to relocation of the underlying array node, and the +/// parent must be updated accordingly. Since this applies recursivly all the +/// way to the root node, it is essential that the entire chain of parent +/// accessors is constructed and propperly maintained when a particular array is +/// modified. +/// +/// The parent reference (`pointer to parent`, `index in parent`) is updated +/// independently from the state of attachment to an underlying node. In +/// particular, the parent reference remains valid and is unannfected by changes +/// in attachment. These two aspects of the state of the accessor is updated +/// independently, and it is entirely the responsibility of the caller to update +/// them such that they are consistent with the underlying node hierarchy before +/// calling any method that modifies the underlying array node. +/// +/// FIXME: This class currently has fragments of ownership, in particular the +/// constructors that allocate underlying memory. On the other hand, the +/// destructor never frees the memory. This is a problematic situation, because +/// it so easily becomes an obscure source of leaks. There are three options for +/// a fix of which the third is most attractive but hardest to implement: (1) +/// Remove all traces of ownership semantics, that is, remove the constructors +/// that allocate memory, but keep the trivial copy constructor. For this to +/// work, it is important that the constness of the accessor has nothing to do +/// with the constness of the underlying memory, otherwise constness can be +/// violated simply by copying the accessor. (2) Disallov copying but associate +/// the constness of the accessor with the constness of the underlying +/// memory. (3) Provide full ownership semantics like is done for Table +/// accessors, and provide a proper copy constructor that really produces a copy +/// of the array. For this to work, the class should assume ownership if, and +/// only if there is no parent. A copy produced by a copy constructor will not +/// have a parent. Even if the original was part of a database, the copy will be +/// free-standing, that is, not be part of any database. For intra, or inter +/// database copying, one would have to also specify the target allocator. +class Array : public ArrayParent { +public: + // void state_init(int action, QueryState *state); + // bool match(int action, size_t index, int64_t value, QueryState *state); + + /// Create an array accessor in the unattached state. + explicit Array(Allocator&) noexcept; + + ~Array() noexcept override + { + } + + enum Type { + type_Normal, + + /// This array is the main array of an innner node of a B+-tree as used + /// in table columns. + type_InnerBptreeNode, + + /// This array may contain refs to subarrays. An element whose least + /// significant bit is zero, is a ref pointing to a subarray. An element + /// whose least significant bit is one, is just a value. It is the + /// responsibility of the application to ensure that non-ref values have + /// their least significant bit set. This will generally be done by + /// shifting the desired vlue to the left by one bit position, and then + /// setting the vacated bit to one. + type_HasRefs + }; + + /// Create a new integer array of the specified type and size, and filled + /// with the specified value, and attach this accessor to it. This does not + /// modify the parent reference information of this accessor. + /// + /// Note that the caller assumes ownership of the allocated underlying + /// node. It is not owned by the accessor. + void create(Type, bool context_flag = false, size_t size = 0, int_fast64_t value = 0); + + /// Reinitialize this array accessor to point to the specified new + /// underlying memory. This does not modify the parent reference information + /// of this accessor. + void init_from_ref(ref_type) noexcept; + + /// Same as init_from_ref(ref_type) but avoid the mapping of 'ref' to memory + /// pointer. + void init_from_mem(MemRef) noexcept; + + /// Same as `init_from_ref(get_ref_from_parent())`. + void init_from_parent() noexcept; + + /// Update the parents reference to this child. This requires, of course, + /// that the parent information stored in this child is up to date. If the + /// parent pointer is set to null, this function has no effect. + void update_parent(); + + /// Called in the context of Group::commit() to ensure that attached + /// accessors stay valid across a commit. Please note that this works only + /// for non-transactional commits. Accessors obtained during a transaction + /// are always detached when the transaction ends. + /// + /// Returns true if, and only if the array has changed. If the array has not + /// changed, then its children are guaranteed to also not have changed. + bool update_from_parent(size_t old_baseline) noexcept; + + /// Change the type of an already attached array node. + /// + /// The effect of calling this function on an unattached accessor is + /// undefined. + void set_type(Type); + + /// Construct a complete copy of this array (including its subarrays) using + /// the specified target allocator and return just the reference to the + /// underlying memory. + MemRef clone_deep(Allocator& target_alloc) const; + + /// Construct an empty integer array of the specified type, and return just + /// the reference to the underlying memory. + static MemRef create_empty_array(Type, bool context_flag, Allocator&); + + /// Construct an integer array of the specified type and size, and return + /// just the reference to the underlying memory. All elements will be + /// initialized to the specified value. + static MemRef create_array(Type, bool context_flag, size_t size, int_fast64_t value, Allocator&); + + /// Construct a shallow copy of the specified slice of this array using the + /// specified target allocator. Subarrays will **not** be cloned. See + /// slice_and_clone_children() for an alternative. + MemRef slice(size_t offset, size_t slice_size, Allocator& target_alloc) const; + + /// Construct a deep copy of the specified slice of this array using the + /// specified target allocator. Subarrays will be cloned. + MemRef slice_and_clone_children(size_t offset, size_t slice_size, Allocator& target_alloc) const; + + // Parent tracking + bool has_parent() const noexcept; + ArrayParent* get_parent() const noexcept; + + /// Setting a new parent affects ownership of the attached array node, if + /// any. If a non-null parent is specified, and there was no parent + /// originally, then the caller passes ownership to the parent, and vice + /// versa. This assumes, of course, that the change in parentship reflects a + /// corresponding change in the list of children in the affected parents. + 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) noexcept; + void adjust_ndx_in_parent(int diff) noexcept; + + /// Get the ref of this array as known to the parent. The caller must ensure + /// that the parent information ('pointer to parent' and 'index in parent') + /// is correct before calling this function. + ref_type get_ref_from_parent() const noexcept; + + bool is_attached() const noexcept; + + /// Detach from the underlying array node. This method has no effect if the + /// accessor is currently unattached (idempotency). + void detach() noexcept; + + size_t size() const noexcept; + bool is_empty() const noexcept; + Type get_type() const noexcept; + + static void add_to_column(IntegerColumn* column, int64_t value); + + void insert(size_t ndx, int_fast64_t value); + void add(int_fast64_t value); + + /// This function is guaranteed to not throw if the current width is + /// sufficient for the specified value (e.g. if you have called + /// ensure_minimum_width(value)) and get_alloc().is_read_only(get_ref()) + /// returns false (noexcept:array-set). Note that for a value of zero, the + /// first criterion is trivially satisfied. + void set(size_t ndx, int64_t value); + + void set_as_ref(size_t ndx, ref_type ref); + + template + void set(size_t ndx, int64_t value); + + int64_t get(size_t ndx) const noexcept; + + template + int64_t get(size_t ndx) const noexcept; + + void get_chunk(size_t ndx, int64_t res[8]) const noexcept; + + template + void get_chunk(size_t ndx, int64_t res[8]) const noexcept; + + ref_type get_as_ref(size_t ndx) const noexcept; + + RefOrTagged get_as_ref_or_tagged(size_t ndx) const noexcept; + void set(size_t ndx, RefOrTagged); + void add(RefOrTagged); + void ensure_minimum_width(RefOrTagged); + + int64_t front() const noexcept; + int64_t back() const noexcept; + + /// Remove the element at the specified index, and move elements at higher + /// indexes to the next lower index. + /// + /// This function does **not** destroy removed subarrays. That is, if the + /// erased element is a 'ref' pointing to a subarray, then that subarray + /// will not be destroyed automatically. + /// + /// This function guarantees that no exceptions will be thrown if + /// get_alloc().is_read_only(get_ref()) would return false before the + /// call. This is automatically guaranteed if the array is used in a + /// non-transactional context, or if the array has already been successfully + /// modified within the current write transaction. + void erase(size_t ndx); + + /// Same as erase(size_t), but remove all elements in the specified + /// range. + /// + /// Please note that this function does **not** destroy removed subarrays. + /// + /// This function guarantees that no exceptions will be thrown if + /// get_alloc().is_read_only(get_ref()) would return false before the call. + void erase(size_t begin, size_t end); + + /// Reduce the size of this array to the specified number of elements. It is + /// an error to specify a size that is greater than the current size of this + /// array. The effect of doing so is undefined. This is just a shorthand for + /// calling the ranged erase() function with appropriate arguments. + /// + /// Please note that this function does **not** destroy removed + /// subarrays. See clear_and_destroy_children() for an alternative. + /// + /// This function guarantees that no exceptions will be thrown if + /// get_alloc().is_read_only(get_ref()) would return false before the call. + void truncate(size_t new_size); + + /// Reduce the size of this array to the specified number of elements. It is + /// an error to specify a size that is greater than the current size of this + /// array. The effect of doing so is undefined. Subarrays will be destroyed + /// recursively, as if by a call to `destroy_deep(subarray_ref, alloc)`. + /// + /// This function is guaranteed not to throw if + /// get_alloc().is_read_only(get_ref()) returns false. + void truncate_and_destroy_children(size_t new_size); + + /// Remove every element from this array. This is just a shorthand for + /// calling truncate(0). + /// + /// Please note that this function does **not** destroy removed + /// subarrays. See clear_and_destroy_children() for an alternative. + /// + /// This function guarantees that no exceptions will be thrown if + /// get_alloc().is_read_only(get_ref()) would return false before the call. + void clear(); + + /// Remove every element in this array. Subarrays will be destroyed + /// recursively, as if by a call to `destroy_deep(subarray_ref, + /// alloc)`. This is just a shorthand for calling + /// truncate_and_destroy_children(0). + /// + /// This function guarantees that no exceptions will be thrown if + /// get_alloc().is_read_only(get_ref()) would return false before the call. + void clear_and_destroy_children(); + + /// If neccessary, expand the representation so that it can store the + /// specified value. + void ensure_minimum_width(int_fast64_t value); + + /// This one may change the represenation of the array, so be carefull if + /// you call it after ensure_minimum_width(). + void set_all_to_zero(); + + /// Add \a diff to the element at the specified index. + void adjust(size_t ndx, int_fast64_t diff); + + /// Add \a diff to all the elements in the specified index range. + void adjust(size_t begin, size_t end, int_fast64_t diff); + + /// Add signed \a diff to all elements that are greater than, or equal to \a + /// limit. + void adjust_ge(int_fast64_t limit, int_fast64_t diff); + + //@{ + /// These are similar in spirit to std::move() and std::move_backward from + /// ``. \a dest_begin must not be in the range [`begin`,`end`), and + /// \a dest_end must not be in the range (`begin`,`end`]. + /// + /// These functions are guaranteed to not throw if + /// `get_alloc().is_read_only(get_ref())` returns false. + void move(size_t begin, size_t end, size_t dest_begin); + void move_backward(size_t begin, size_t end, size_t dest_end); + //@} + + /// move_rotate moves one element from \a from to be located at index \a to, + /// shifting all elements inbetween by one. + /// + /// If \a from is larger than \a to, the elements inbetween are shifted down. + /// If \a to is larger than \a from, the elements inbetween are shifted up. + /// + /// This function is guaranteed to not throw if + /// `get_alloc().is_read_only(get_ref())` returns false. + void move_rotate(size_t from, size_t to, size_t num_elems = 1); + + //@{ + /// Find the lower/upper bound of the specified value in a sequence of + /// integers which must already be sorted ascendingly. + /// + /// For an integer value '`v`', lower_bound_int(v) returns the index '`l`' + /// of the first element such that `get(l) ≥ v`, and upper_bound_int(v) + /// returns the index '`u`' of the first element such that `get(u) > + /// v`. In both cases, if no such element is found, the returned value is + /// the number of elements in the array. + /// + /// 3 3 3 4 4 4 5 6 7 9 9 9 + /// ^ ^ ^ ^ ^ + /// | | | | | + /// | | | | -- Lower and upper bound of 15 + /// | | | | + /// | | | -- Lower and upper bound of 8 + /// | | | + /// | | -- Upper bound of 4 + /// | | + /// | -- Lower bound of 4 + /// | + /// -- Lower and upper bound of 1 + /// + /// These functions are similar to std::lower_bound() and + /// std::upper_bound(). + /// + /// We currently use binary search. See for example + /// http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary. + /// + /// FIXME: It may be worth considering if overall efficiency can be improved + /// by doing a linear search for short sequences. + size_t lower_bound_int(int64_t value) const noexcept; + size_t upper_bound_int(int64_t value) const noexcept; + //@} + + /// \brief Search the \c Array for a value greater or equal than \a target, + /// starting the search at the \a start index. If \a indirection is + /// provided, use it as a look-up table to iterate over the \c Array. + /// + /// If \a indirection is not provided, then the \c Array must be sorted in + /// ascending order. If \a indirection is provided, then its values should + /// point to indices in this \c Array in such a way that iteration happens + /// in ascending order. + /// + /// Behaviour is undefined if: + /// - a value in \a indirection is out of bounds for this \c Array; + /// - \a indirection does not contain at least as many elements as this \c + /// Array; + /// - sorting conditions are not respected; + /// - \a start is greater than the number of elements in this \c Array or + /// \a indirection (if provided). + /// + /// \param target the smallest value to search for + /// \param start the offset at which to start searching in the array + /// \param indirection an \c Array containing valid indices of values in + /// this \c Array, sorted in ascending order + /// \return the index of the value if found, or realm::not_found otherwise + size_t find_gte(const int64_t target, size_t start, size_t end = size_t(-1)) const; + + void preset(int64_t min, int64_t max, size_t num_items); + void preset(size_t bitwidth, size_t num_items); + + int64_t sum(size_t start = 0, size_t end = size_t(-1)) const; + size_t count(int64_t value) const noexcept; + + bool maximum(int64_t& result, size_t start = 0, size_t end = size_t(-1), size_t* return_ndx = nullptr) const; + + bool minimum(int64_t& result, size_t start = 0, size_t end = size_t(-1), size_t* return_ndx = nullptr) const; + + /// This information is guaranteed to be cached in the array accessor. + bool is_inner_bptree_node() const noexcept; + + /// Returns true if type is either type_HasRefs or type_InnerColumnNode. + /// + /// This information is guaranteed to be cached in the array accessor. + bool has_refs() const noexcept; + void set_has_refs(bool) noexcept; + + /// This information is guaranteed to be cached in the array accessor. + /// + /// Columns and indexes can use the context bit to differentiate leaf types. + bool get_context_flag() const noexcept; + void set_context_flag(bool) noexcept; + + ref_type get_ref() const noexcept; + MemRef get_mem() const noexcept; + + /// Destroy only the array that this accessor is attached to, not the + /// children of that array. See non-static destroy_deep() for an + /// alternative. If this accessor is already in the detached state, this + /// function has no effect (idempotency). + void destroy() noexcept; + + /// Recursively destroy children (as if calling + /// clear_and_destroy_children()), then put this accessor into the detached + /// state (as if calling detach()), then free the allocated memory. If this + /// accessor is already in the detached state, this function has no effect + /// (idempotency). + void destroy_deep() noexcept; + + /// Shorthand for `destroy(MemRef(ref, alloc), alloc)`. + static void destroy(ref_type ref, Allocator& alloc) noexcept; + + /// Destroy only the specified array node, not its children. See also + /// destroy_deep(MemRef, Allocator&). + static void destroy(MemRef, Allocator&) noexcept; + + /// Shorthand for `destroy_deep(MemRef(ref, alloc), alloc)`. + static void destroy_deep(ref_type ref, Allocator& alloc) noexcept; + + /// Destroy the specified array node and all of its children, recursively. + /// + /// This is done by freeing the specified array node after calling + /// destroy_deep() for every contained 'ref' element. + static void destroy_deep(MemRef, Allocator&) noexcept; + + Allocator& get_alloc() const noexcept + { + return m_alloc; + } + + // Serialization + + /// Returns the ref (position in the target stream) of the written copy of + /// this array, or the ref of the original array if \a only_if_modified is + /// true, and this array is unmodified (Alloc::is_read_only()). + /// + /// The number of bytes that will be written by a non-recursive invocation + /// of this function is exactly the number returned by get_byte_size(). + /// + /// \param out The destination stream (writer). + /// + /// \param deep If true, recursively write out subarrays, but still subject + /// to \a only_if_modified. + /// + /// \param only_if_modified Set to `false` to always write, or to `true` to + /// only write the array if it has been modified. + ref_type write(_impl::ArrayWriterBase& out, bool deep, bool only_if_modified) const; + + /// Same as non-static write() with `deep` set to true. This is for the + /// cases where you do not already have an array accessor available. + static ref_type write(ref_type, Allocator&, _impl::ArrayWriterBase&, bool only_if_modified); + + // Main finding function - used for find_first, find_all, sum, max, min, etc. + bool find(int cond, Action action, int64_t value, size_t start, size_t end, size_t baseindex, + QueryState* state, bool nullable_array = false, bool find_null = false) const; + + // Templated find function to avoid conversion to and from integer represenation of condition + template + bool find(Action action, int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + bool nullable_array = false, bool find_null = false) const + { + if (action == act_ReturnFirst) { + REALM_TEMPEX3(return find, cond, act_ReturnFirst, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + else if (action == act_Sum) { + REALM_TEMPEX3(return find, cond, act_Sum, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + else if (action == act_Min) { + REALM_TEMPEX3(return find, cond, act_Min, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + else if (action == act_Max) { + REALM_TEMPEX3(return find, cond, act_Max, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + else if (action == act_Count) { + REALM_TEMPEX3(return find, cond, act_Count, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + else if (action == act_FindAll) { + REALM_TEMPEX3(return find, cond, act_FindAll, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + else if (action == act_CallbackIdx) { + REALM_TEMPEX3(return find, cond, act_CallbackIdx, m_width, + (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null)) + } + REALM_ASSERT_DEBUG(false); + return false; + } + + + /* + bool find(int cond, Action action, null, size_t start, size_t end, size_t baseindex, + QueryState* state) const; + */ + + template + bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback, bool nullable_array = false, bool find_null = false) const; + + // This is the one installed into the m_vtable->finder slots. + template + bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state) const; + + template + bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback, bool nullable_array = false, bool find_null = false) const; + + /* + template + bool find(null, size_t start, size_t end, size_t baseindex, + QueryState* state, Callback callback) const; + */ + + // Optimized implementation for release mode + template + bool find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback, bool nullable_array = false, bool find_null = false) const; + + // Called for each search result + template + bool find_action(size_t index, util::Optional value, QueryState* state, + Callback callback) const; + + template + bool find_action_pattern(size_t index, uint64_t pattern, QueryState* state, Callback callback) const; + + // Wrappers for backwards compatibility and for simple use without + // setting up state initialization etc + template + size_t find_first(int64_t value, size_t start = 0, size_t end = size_t(-1)) const; + + void find_all(IntegerColumn* result, int64_t value, size_t col_offset = 0, size_t begin = 0, + size_t end = size_t(-1)) const; + + size_t find_first(int64_t value, size_t begin = 0, size_t end = size_t(-1)) const; + + // Non-SSE find for the four functions Equal/NotEqual/Less/Greater + template + bool compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const; + + // Non-SSE find for Equal/NotEqual + template + inline bool compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, + QueryState* state, Callback callback) const; + + // Non-SSE find for Less/Greater + template + bool compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const; + + template + bool compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const; + + template + bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const; + + template + bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const; + + template + bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const; + +// SSE find for the four functions Equal/NotEqual/Less/Greater +#ifdef REALM_COMPILER_SSE + template + bool find_sse(int64_t value, __m128i* data, size_t items, QueryState* state, size_t baseindex, + Callback callback) const; + + template + REALM_FORCEINLINE bool find_sse_intern(__m128i* action_data, __m128i* data, size_t items, + QueryState* state, size_t baseindex, Callback callback) const; + +#endif + + template + inline bool test_zero(uint64_t value) const; // Tests value for 0-elements + + template + size_t find_zero(uint64_t v) const; // Finds position of 0/non-zero element + + template + uint64_t cascade(uint64_t a) const; // Sets lowermost bits of zero or non-zero elements + + template + int64_t + find_gtlt_magic(int64_t v) const; // Compute magic constant needed for searching for value 'v' using bit hacks + + template + inline int64_t lower_bits() const; // Return chunk with lower bit set in each element + + size_t first_set_bit(unsigned int v) const; + size_t first_set_bit64(int64_t v) const; + + template + int64_t get_universal(const char* const data, const size_t ndx) const; + + // Find value greater/less in 64-bit chunk - only works for positive values + template + bool find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryState* state, size_t baseindex, + Callback callback) const; + + // Find value greater/less in 64-bit chunk - no constraints + template + bool find_gtlt(int64_t v, uint64_t chunk, QueryState* state, size_t baseindex, Callback callback) const; + + ref_type bptree_leaf_insert(size_t ndx, int64_t, TreeInsertBase& state); + + /// Get the specified element without the cost of constructing an + /// array instance. If an array instance is already available, or + /// you need to get multiple values, then this method will be + /// slower. + static int_fast64_t get(const char* header, size_t ndx) noexcept; + + /// Like get(const char*, size_t) but gets two consecutive + /// elements. + static std::pair get_two(const char* header, size_t ndx) noexcept; + + static void get_three(const char* data, size_t ndx, ref_type& v0, ref_type& v1, ref_type& v2) noexcept; + + /// The meaning of 'width' depends on the context in which this + /// array is used. + size_t get_width() const noexcept + { + return m_width; + } + + static char* get_data_from_header(char*) noexcept; + static char* get_header_from_data(char*) noexcept; + static const char* get_data_from_header(const char*) noexcept; + + enum WidthType { + wtype_Bits = 0, + wtype_Multiply = 1, + wtype_Ignore = 2, + }; + + static bool get_is_inner_bptree_node_from_header(const char*) noexcept; + static bool get_hasrefs_from_header(const char*) noexcept; + static bool get_context_flag_from_header(const char*) noexcept; + static WidthType get_wtype_from_header(const char*) noexcept; + static uint_least8_t get_width_from_header(const char*) noexcept; + static size_t get_size_from_header(const char*) noexcept; + + static Type get_type_from_header(const char*) noexcept; + + /// Get the number of bytes currently in use by this array. This + /// includes the array header, but it does not include allocated + /// bytes corresponding to excess capacity. The result is + /// guaranteed to be a multiple of 8 (i.e., 64-bit aligned). + /// + /// This number is exactly the number of bytes that will be + /// written by a non-recursive invocation of write(). + size_t get_byte_size() const noexcept; + + /// Get the maximum number of bytes that can be written by a + /// non-recursive invocation of write() on an array with the + /// specified number of elements, that is, the maximum value that + /// can be returned by get_byte_size(). + static size_t get_max_byte_size(size_t num_elems) noexcept; + + /// FIXME: Belongs in IntegerArray + static size_t calc_aligned_byte_size(size_t size, int width); + + class MemUsageHandler { + public: + virtual void handle(ref_type ref, size_t allocated, size_t used) = 0; + }; + + void report_memory_usage(MemUsageHandler&) const; + + void stats(MemStats& stats_dest) const noexcept; + +#ifdef REALM_DEBUG + void print() const; + void verify() const; + typedef size_t (*LeafVerifier)(MemRef, Allocator&); + void verify_bptree(LeafVerifier) const; + typedef void (*LeafDumper)(MemRef, Allocator&, std::ostream&, int level); + void dump_bptree_structure(std::ostream&, int level, LeafDumper) const; + void to_dot(std::ostream&, StringData title = StringData()) const; + class ToDotHandler { + public: + virtual void to_dot(MemRef leaf_mem, ArrayParent*, size_t ndx_in_parent, std::ostream&) = 0; + ~ToDotHandler() + { + } + }; + void bptree_to_dot(std::ostream&, ToDotHandler&) const; + void to_dot_parent_edge(std::ostream&) const; +#endif + + static const int header_size = 8; // Number of bytes used by header + + // The encryption layer relies on headers always fitting within a single page. + static_assert(header_size == 8, "Header must always fit in entirely on a page"); + + Array& operator=(const Array&) = delete; // not allowed + Array(const Array&) = delete; // not allowed +protected: + typedef bool (*CallbackDummy)(int64_t); + +protected: + // Includes array header. Not necessarily 8-byte aligned. + virtual size_t calc_byte_len(size_t num_items, size_t width) const; + + virtual size_t calc_item_count(size_t bytes, size_t width) const noexcept; + + bool get_is_inner_bptree_node_from_header() const noexcept; + bool get_hasrefs_from_header() const noexcept; + bool get_context_flag_from_header() const noexcept; + WidthType get_wtype_from_header() const noexcept; + uint_least8_t get_width_from_header() const noexcept; + size_t get_size_from_header() const noexcept; + + // Undefined behavior if m_alloc.is_read_only(m_ref) returns true + size_t get_capacity_from_header() const noexcept; + + void set_header_is_inner_bptree_node(bool value) noexcept; + void set_header_hasrefs(bool value) noexcept; + void set_header_context_flag(bool value) noexcept; + void set_header_wtype(WidthType value) noexcept; + void set_header_width(int value) noexcept; + void set_header_size(size_t value) noexcept; + void set_header_capacity(size_t value) noexcept; + + static void set_header_is_inner_bptree_node(bool value, char* header) noexcept; + static void set_header_hasrefs(bool value, char* header) noexcept; + static void set_header_context_flag(bool value, char* header) noexcept; + static void set_header_wtype(WidthType value, char* header) noexcept; + static void set_header_width(int value, char* header) noexcept; + static void set_header_size(size_t value, char* header) noexcept; + static void set_header_capacity(size_t value, char* header) noexcept; + + static void init_header(char* header, bool is_inner_bptree_node, bool has_refs, bool context_flag, + WidthType width_type, int width, size_t size, size_t capacity) noexcept; + + + // This returns the minimum value ("lower bound") of the representable values + // for the given bit width. Valid widths are 0, 1, 2, 4, 8, 16, 32, and 64. + template + static int_fast64_t lbound_for_width() noexcept; + + static int_fast64_t lbound_for_width(size_t width) noexcept; + + // This returns the maximum value ("inclusive upper bound") of the representable values + // for the given bit width. Valid widths are 0, 1, 2, 4, 8, 16, 32, and 64. + template + static int_fast64_t ubound_for_width() noexcept; + + static int_fast64_t ubound_for_width(size_t width) noexcept; + + template + void set_width() noexcept; + void set_width(size_t) noexcept; + void alloc(size_t init_size, size_t width); + void copy_on_write(); + +private: + void do_copy_on_write(size_t minimum_size = 0); + void do_ensure_minimum_width(int_fast64_t); + + template + int64_t sum(size_t start, size_t end) const; + + template + bool minmax(int64_t& result, size_t start, size_t end, size_t* return_ndx) const; + + template + size_t find_gte(const int64_t target, size_t start, size_t end) const; + + template + size_t adjust_ge(size_t start, size_t end, int_fast64_t limit, int_fast64_t diff); + +protected: + /// The total size in bytes (including the header) of a new empty + /// array. Must be a multiple of 8 (i.e., 64-bit aligned). + static const size_t initial_capacity = 128; + + /// It is an error to specify a non-zero value unless the width + /// type is wtype_Bits. It is also an error to specify a non-zero + /// size if the width type is wtype_Ignore. + static MemRef create(Type, bool context_flag, WidthType, size_t size, int_fast64_t value, Allocator&); + + static MemRef clone(MemRef header, Allocator& alloc, Allocator& target_alloc); + + /// Get the address of the header of this array. + char* get_header() noexcept; + + /// Same as get_byte_size(). + static size_t get_byte_size_from_header(const char*) noexcept; + + // Undefined behavior if array is in immutable memory + static size_t get_capacity_from_header(const char*) noexcept; + + // Overriding method in ArrayParent + void update_child_ref(size_t, ref_type) override; + + // Overriding method in ArrayParent + ref_type get_child_ref(size_t) const noexcept override; + + void destroy_children(size_t offset = 0) noexcept; + + std::pair get_to_dot_parent(size_t ndx_in_parent) const override; + + bool is_read_only() const noexcept; + +protected: + // Getters and Setters for adaptive-packed arrays + typedef int64_t (Array::*Getter)(size_t) const; // Note: getters must not throw + typedef void (Array::*Setter)(size_t, int64_t); + typedef bool (Array::*Finder)(int64_t, size_t, size_t, size_t, QueryState*) const; + typedef void (Array::*ChunkGetter)(size_t, int64_t res[8]) const; // Note: getters must not throw + + struct VTable { + Getter getter; + ChunkGetter chunk_getter; + Setter setter; + Finder finder[cond_VTABLE_FINDER_COUNT]; // one for each active function pointer + }; + template + struct VTableForWidth; + +protected: + /// Takes a 64-bit value and returns the minimum number of bits needed + /// to fit the value. For alignment this is rounded up to nearest + /// log2. Posssible results {0, 1, 2, 4, 8, 16, 32, 64} + static size_t bit_width(int64_t value); + + void report_memory_usage_2(MemUsageHandler&) const; + +private: + Getter m_getter = nullptr; // cached to avoid indirection + const VTable* m_vtable = nullptr; + +public: + // FIXME: Should not be public + char* m_data = nullptr; // Points to first byte after header + +#if REALM_ENABLE_MEMDEBUG + // If m_no_relocation is false, then copy_on_write() will always relocate this array, regardless if it's + // required or not. If it's true, then it will never relocate, which is currently only expeted inside + // GroupWriter::write_group() due to a unique chicken/egg problem (see description there). + bool m_no_relocation = false; +#endif + +protected: + int64_t m_lbound; // min number that can be stored with current m_width + int64_t m_ubound; // max number that can be stored with current m_width + + size_t m_size = 0; // Number of elements currently stored. + size_t m_capacity = 0; // Number of elements that fit inside the allocated memory. + + Allocator& m_alloc; + +private: + size_t m_ref; + ArrayParent* m_parent = nullptr; + size_t m_ndx_in_parent = 0; // Ignored if m_parent is null. + +protected: + uint_least8_t m_width = 0; // Size of an element (meaning depend on type of array). + bool m_is_inner_bptree_node; // This array is an inner node of B+-tree. + bool m_has_refs; // Elements whose first bit is zero are refs to subarrays. + bool m_context_flag; // Meaning depends on context. + +private: + ref_type do_write_shallow(_impl::ArrayWriterBase&) const; + ref_type do_write_deep(_impl::ArrayWriterBase&, bool only_if_modified) const; + static size_t calc_byte_size(WidthType wtype, size_t size, uint_least8_t width) noexcept; + + friend class SlabAlloc; + friend class GroupWriter; + friend class StringColumn; +}; + + +// Implementation: + +class QueryStateBase { + virtual void dyncast() + { + } +}; + +template <> +class QueryState : public QueryStateBase { +public: + int64_t m_state; + size_t m_match_count; + size_t m_limit; + size_t m_minmax_index; // used only for min/max, to save index of current min/max value + + template + bool uses_val() + { + if (action == act_Max || action == act_Min || action == act_Sum) + return true; + else + return false; + } + + void init(Action action, IntegerColumn* akku, size_t limit) + { + m_match_count = 0; + m_limit = limit; + m_minmax_index = not_found; + + if (action == act_Max) + m_state = -0x7fffffffffffffffLL - 1LL; + else if (action == act_Min) + m_state = 0x7fffffffffffffffLL; + else if (action == act_ReturnFirst) + m_state = not_found; + else if (action == act_Sum) + m_state = 0; + else if (action == act_Count) + m_state = 0; + else if (action == act_FindAll) + m_state = reinterpret_cast(akku); + else if (action == act_CallbackIdx) { + } + else { + REALM_ASSERT_DEBUG(false); + } + } + + template + inline bool match(size_t index, uint64_t indexpattern, int64_t value) + { + if (pattern) { + if (action == act_Count) { + // If we are close to 'limit' argument in query, we cannot count-up a complete chunk. Count up single + // elements instead + if (m_match_count + 64 >= m_limit) + return false; + + m_state += fast_popcount64(indexpattern); + m_match_count = size_t(m_state); + return true; + } + // Other aggregates cannot (yet) use bit pattern for anything. Make Array-finder call with pattern = false + // instead + return false; + } + + ++m_match_count; + + if (action == act_Max) { + if (value > m_state) { + m_state = value; + m_minmax_index = index; + } + } + else if (action == act_Min) { + if (value < m_state) { + m_state = value; + m_minmax_index = index; + } + } + else if (action == act_Sum) + m_state += value; + else if (action == act_Count) { + m_state++; + m_match_count = size_t(m_state); + } + else if (action == act_FindAll) { + Array::add_to_column(reinterpret_cast(m_state), index); + } + else if (action == act_ReturnFirst) { + m_state = index; + return false; + } + else { + REALM_ASSERT_DEBUG(false); + } + return (m_limit > m_match_count); + } + + template + inline bool match(size_t index, uint64_t indexpattern, util::Optional value) + { + // FIXME: This is a temporary hack for nullable integers. + if (value) { + return match(index, indexpattern, *value); + } + + // If value is null, the only sensible actions are count, find_all, and return first. + // Max, min, and sum should all have no effect. + if (action == act_Count) { + m_state++; + m_match_count = size_t(m_state); + } + else if (action == act_FindAll) { + Array::add_to_column(reinterpret_cast(m_state), index); + } + else if (action == act_ReturnFirst) { + m_match_count++; + m_state = index; + return false; + } + return m_limit > m_match_count; + } +}; + +// Used only for Basic-types: currently float and double +template +class QueryState : public QueryStateBase { +public: + R m_state; + size_t m_match_count; + size_t m_limit; + size_t m_minmax_index; // used only for min/max, to save index of current min/max value + + template + bool uses_val() + { + return (action == act_Max || action == act_Min || action == act_Sum || action == act_Count); + } + + void init(Action action, Array*, size_t limit) + { + REALM_ASSERT((std::is_same::value || std::is_same::value)); + m_match_count = 0; + m_limit = limit; + m_minmax_index = not_found; + + if (action == act_Max) + m_state = -std::numeric_limits::infinity(); + else if (action == act_Min) + m_state = std::numeric_limits::infinity(); + else if (action == act_Sum) + m_state = 0.0; + else { + REALM_ASSERT_DEBUG(false); + } + } + + template + inline bool match(size_t index, uint64_t /*indexpattern*/, resulttype value) + { + if (pattern) + return false; + + static_assert(action == act_Sum || action == act_Max || action == act_Min || action == act_Count, + "Search action not supported"); + + if (action == act_Count) { + ++m_match_count; + } + else if (!null::is_null_float(value)) { + ++m_match_count; + if (action == act_Max) { + if (value > m_state) { + m_state = value; + m_minmax_index = index; + } + } + else if (action == act_Min) { + if (value < m_state) { + m_state = value; + m_minmax_index = index; + } + } + else if (action == act_Sum) + m_state += value; + else { + REALM_ASSERT_DEBUG(false); + } + } + + return (m_limit > m_match_count); + } +}; + +inline bool RefOrTagged::is_ref() const noexcept +{ + return (m_value & 1) == 0; +} + +inline bool RefOrTagged::is_tagged() const noexcept +{ + return !is_ref(); +} + +inline ref_type RefOrTagged::get_as_ref() const noexcept +{ + // to_ref() is defined in + return to_ref(m_value); +} + +inline uint_fast64_t RefOrTagged::get_as_int() const noexcept +{ + // The bitwise AND is there in case uint_fast64_t is wider than 64 bits. + return (uint_fast64_t(m_value) & 0xFFFFFFFFFFFFFFFFULL) >> 1; +} + +inline RefOrTagged RefOrTagged::make_ref(ref_type ref) noexcept +{ + // from_ref() is defined in + int_fast64_t value = from_ref(ref); + return RefOrTagged(value); +} + +inline RefOrTagged RefOrTagged::make_tagged(uint_fast64_t i) noexcept +{ + REALM_ASSERT(i < (1ULL << 63)); + int_fast64_t value = util::from_twos_compl((i << 1) | 1); + return RefOrTagged(value); +} + +inline RefOrTagged::RefOrTagged(int_fast64_t value) noexcept + : m_value(value) +{ +} + +inline Array::Array(Allocator& allocator) noexcept + : m_alloc(allocator) +{ +} + +inline void Array::create(Type type, bool context_flag, size_t length, int_fast64_t value) +{ + MemRef mem = create_array(type, context_flag, length, value, m_alloc); // Throws + init_from_mem(mem); +} + + +inline void Array::init_from_ref(ref_type ref) noexcept +{ + REALM_ASSERT_DEBUG(ref); + char* header = m_alloc.translate(ref); + init_from_mem(MemRef(header, ref, m_alloc)); +} + + +inline void Array::init_from_parent() noexcept +{ + ref_type ref = get_ref_from_parent(); + init_from_ref(ref); +} + + +inline Array::Type Array::get_type() const noexcept +{ + if (m_is_inner_bptree_node) { + REALM_ASSERT_DEBUG(m_has_refs); + return type_InnerBptreeNode; + } + if (m_has_refs) + return type_HasRefs; + return type_Normal; +} + + +inline void Array::get_chunk(size_t ndx, int64_t res[8]) const noexcept +{ + REALM_ASSERT_DEBUG(ndx < m_size); + (this->*(m_vtable->chunk_getter))(ndx, res); +} + + +inline int64_t Array::get(size_t ndx) const noexcept +{ + REALM_ASSERT_DEBUG(is_attached()); + REALM_ASSERT_DEBUG(ndx < m_size); + return (this->*m_getter)(ndx); + + // Two ideas that are not efficient but may be worth looking into again: + /* + // Assume correct width is found early in REALM_TEMPEX, which is the case for B tree offsets that + // are probably either 2^16 long. Turns out to be 25% faster if found immediately, but 50-300% slower + // if found later + REALM_TEMPEX(return get, (ndx)); + */ + /* + // Slightly slower in both of the if-cases. Also needs an matchcount m_size check too, to avoid + // reading beyond array. + if (m_width >= 8 && m_size > ndx + 7) + return get<64>(ndx >> m_shift) & m_widthmask; + else + return (this->*(m_vtable->getter))(ndx); + */ +} + +inline int64_t Array::front() const noexcept +{ + return get(0); +} + +inline int64_t Array::back() const noexcept +{ + return get(m_size - 1); +} + +inline ref_type Array::get_as_ref(size_t ndx) const noexcept +{ + REALM_ASSERT_DEBUG(is_attached()); + REALM_ASSERT_DEBUG(m_has_refs); + int64_t v = get(ndx); + return to_ref(v); +} + +inline RefOrTagged Array::get_as_ref_or_tagged(size_t ndx) const noexcept +{ + REALM_ASSERT(has_refs()); + return RefOrTagged(get(ndx)); +} + +inline void Array::set(size_t ndx, RefOrTagged ref_or_tagged) +{ + REALM_ASSERT(has_refs()); + set(ndx, ref_or_tagged.m_value); // Throws +} + +inline void Array::add(RefOrTagged ref_or_tagged) +{ + REALM_ASSERT(has_refs()); + add(ref_or_tagged.m_value); // Throws +} + +inline void Array::ensure_minimum_width(RefOrTagged ref_or_tagged) +{ + REALM_ASSERT(has_refs()); + ensure_minimum_width(ref_or_tagged.m_value); // Throws +} + +inline bool Array::is_inner_bptree_node() const noexcept +{ + return m_is_inner_bptree_node; +} + +inline bool Array::has_refs() const noexcept +{ + return m_has_refs; +} + +inline void Array::set_has_refs(bool value) noexcept +{ + if (m_has_refs != value) { + REALM_ASSERT(!is_read_only()); + m_has_refs = value; + set_header_hasrefs(value); + } +} + +inline bool Array::get_context_flag() const noexcept +{ + return m_context_flag; +} + +inline void Array::set_context_flag(bool value) noexcept +{ + if (m_context_flag != value) { + REALM_ASSERT(!is_read_only()); + m_context_flag = value; + set_header_context_flag(value); + } +} + +inline ref_type Array::get_ref() const noexcept +{ + return m_ref; +} + +inline MemRef Array::get_mem() const noexcept +{ + return MemRef(get_header_from_data(m_data), m_ref, m_alloc); +} + +inline void Array::destroy() noexcept +{ + if (!is_attached()) + return; + char* header = get_header_from_data(m_data); + m_alloc.free_(m_ref, header); + m_data = nullptr; +} + +inline void Array::destroy_deep() noexcept +{ + if (!is_attached()) + return; + + if (m_has_refs) + destroy_children(); + + char* header = get_header_from_data(m_data); + m_alloc.free_(m_ref, header); + m_data = nullptr; +} + +inline ref_type Array::write(_impl::ArrayWriterBase& out, bool deep, bool only_if_modified) const +{ + REALM_ASSERT(is_attached()); + + if (only_if_modified && m_alloc.is_read_only(m_ref)) + return m_ref; + + if (!deep || !m_has_refs) + return do_write_shallow(out); // Throws + + return do_write_deep(out, only_if_modified); // Throws +} + +inline ref_type Array::write(ref_type ref, Allocator& alloc, _impl::ArrayWriterBase& out, bool only_if_modified) +{ + if (only_if_modified && alloc.is_read_only(ref)) + return ref; + + Array array(alloc); + array.init_from_ref(ref); + + if (!array.m_has_refs) + return array.do_write_shallow(out); // Throws + + return array.do_write_deep(out, only_if_modified); // Throws +} + +inline void Array::add(int_fast64_t value) +{ + insert(m_size, value); +} + +inline void Array::erase(size_t ndx) +{ + // This can throw, but only if array is currently in read-only + // memory. + move(ndx + 1, size(), ndx); + + // Update size (also in header) + --m_size; + set_header_size(m_size); +} + + +inline void Array::erase(size_t begin, size_t end) +{ + if (begin != end) { + // This can throw, but only if array is currently in read-only memory. + move(end, size(), begin); // Throws + + // Update size (also in header) + m_size -= end - begin; + set_header_size(m_size); + } +} + +inline void Array::clear() +{ + truncate(0); // Throws +} + +inline void Array::clear_and_destroy_children() +{ + truncate_and_destroy_children(0); +} + +inline void Array::destroy(ref_type ref, Allocator& alloc) noexcept +{ + destroy(MemRef(ref, alloc), alloc); +} + +inline void Array::destroy(MemRef mem, Allocator& alloc) noexcept +{ + alloc.free_(mem); +} + +inline void Array::destroy_deep(ref_type ref, Allocator& alloc) noexcept +{ + destroy_deep(MemRef(ref, alloc), alloc); +} + +inline void Array::destroy_deep(MemRef mem, Allocator& alloc) noexcept +{ + if (!get_hasrefs_from_header(mem.get_addr())) { + alloc.free_(mem); + return; + } + Array array(alloc); + array.init_from_mem(mem); + array.destroy_deep(); +} + + +inline void Array::adjust(size_t ndx, int_fast64_t diff) +{ + REALM_ASSERT_3(ndx, <=, m_size); + if (diff != 0) { + // FIXME: Should be optimized + int_fast64_t v = get(ndx); + set(ndx, int64_t(v + diff)); // Throws + } +} + +inline void Array::adjust(size_t begin, size_t end, int_fast64_t diff) +{ + if (diff != 0) { + // FIXME: Should be optimized + for (size_t i = begin; i != end; ++i) + adjust(i, diff); // Throws + } +} + + +//------------------------------------------------- + +inline bool Array::get_is_inner_bptree_node_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return (int(h[4]) & 0x80) != 0; +} +inline bool Array::get_hasrefs_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return (int(h[4]) & 0x40) != 0; +} +inline bool Array::get_context_flag_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return (int(h[4]) & 0x20) != 0; +} +inline Array::WidthType Array::get_wtype_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return WidthType((int(h[4]) & 0x18) >> 3); +} +inline uint_least8_t Array::get_width_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return uint_least8_t((1 << (int(h[4]) & 0x07)) >> 1); +} +inline size_t Array::get_size_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return (size_t(h[5]) << 16) + (size_t(h[6]) << 8) + h[7]; +} +inline size_t Array::get_capacity_from_header(const char* header) noexcept +{ + typedef unsigned char uchar; + const uchar* h = reinterpret_cast(header); + return (size_t(h[0]) << 16) + (size_t(h[1]) << 8) + h[2]; +} + + +inline char* Array::get_data_from_header(char* header) noexcept +{ + return header + header_size; +} +inline char* Array::get_header_from_data(char* data) noexcept +{ + return data - header_size; +} +inline const char* Array::get_data_from_header(const char* header) noexcept +{ + return get_data_from_header(const_cast(header)); +} + + +inline bool Array::get_is_inner_bptree_node_from_header() const noexcept +{ + return get_is_inner_bptree_node_from_header(get_header_from_data(m_data)); +} +inline bool Array::get_hasrefs_from_header() const noexcept +{ + return get_hasrefs_from_header(get_header_from_data(m_data)); +} +inline bool Array::get_context_flag_from_header() const noexcept +{ + return get_context_flag_from_header(get_header_from_data(m_data)); +} +inline Array::WidthType Array::get_wtype_from_header() const noexcept +{ + return get_wtype_from_header(get_header_from_data(m_data)); +} +inline uint_least8_t Array::get_width_from_header() const noexcept +{ + return get_width_from_header(get_header_from_data(m_data)); +} +inline size_t Array::get_size_from_header() const noexcept +{ + return get_size_from_header(get_header_from_data(m_data)); +} +inline size_t Array::get_capacity_from_header() const noexcept +{ + return get_capacity_from_header(get_header_from_data(m_data)); +} + + +inline void Array::set_header_is_inner_bptree_node(bool value, char* header) noexcept +{ + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[4] = uchar((int(h[4]) & ~0x80) | int(value) << 7); +} + +inline void Array::set_header_hasrefs(bool value, char* header) noexcept +{ + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[4] = uchar((int(h[4]) & ~0x40) | int(value) << 6); +} + +inline void Array::set_header_context_flag(bool value, char* header) noexcept +{ + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[4] = uchar((int(h[4]) & ~0x20) | int(value) << 5); +} + +inline void Array::set_header_wtype(WidthType value, char* header) noexcept +{ + // Indicates how to calculate size in bytes based on width + // 0: bits (width/8) * size + // 1: multiply width * size + // 2: ignore 1 * size + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[4] = uchar((int(h[4]) & ~0x18) | int(value) << 3); +} + +inline void Array::set_header_width(int value, char* header) noexcept +{ + // Pack width in 3 bits (log2) + int w = 0; + while (value) { + ++w; + value >>= 1; + } + REALM_ASSERT_3(w, <, 8); + + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[4] = uchar((int(h[4]) & ~0x7) | w); +} + +inline void Array::set_header_size(size_t value, char* header) noexcept +{ + REALM_ASSERT_3(value, <=, max_array_payload); + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[5] = uchar((value >> 16) & 0x000000FF); + h[6] = uchar((value >> 8) & 0x000000FF); + h[7] = uchar(value & 0x000000FF); +} + +// Note: There is a copy of this function is test_alloc.cpp +inline void Array::set_header_capacity(size_t value, char* header) noexcept +{ + REALM_ASSERT_3(value, <=, max_array_payload); + typedef unsigned char uchar; + uchar* h = reinterpret_cast(header); + h[0] = uchar((value >> 16) & 0x000000FF); + h[1] = uchar((value >> 8) & 0x000000FF); + h[2] = uchar(value & 0x000000FF); +} + + +inline void Array::set_header_is_inner_bptree_node(bool value) noexcept +{ + set_header_is_inner_bptree_node(value, get_header_from_data(m_data)); +} +inline void Array::set_header_hasrefs(bool value) noexcept +{ + set_header_hasrefs(value, get_header_from_data(m_data)); +} +inline void Array::set_header_context_flag(bool value) noexcept +{ + set_header_context_flag(value, get_header_from_data(m_data)); +} +inline void Array::set_header_wtype(WidthType value) noexcept +{ + set_header_wtype(value, get_header_from_data(m_data)); +} +inline void Array::set_header_width(int value) noexcept +{ + set_header_width(value, get_header_from_data(m_data)); +} +inline void Array::set_header_size(size_t value) noexcept +{ + set_header_size(value, get_header_from_data(m_data)); +} +inline void Array::set_header_capacity(size_t value) noexcept +{ + set_header_capacity(value, get_header_from_data(m_data)); +} + + +inline Array::Type Array::get_type_from_header(const char* header) noexcept +{ + if (get_is_inner_bptree_node_from_header(header)) + return type_InnerBptreeNode; + if (get_hasrefs_from_header(header)) + return type_HasRefs; + return type_Normal; +} + + +inline char* Array::get_header() noexcept +{ + return get_header_from_data(m_data); +} + +inline size_t Array::calc_byte_size(WidthType wtype, size_t size, uint_least8_t width) noexcept +{ + size_t num_bytes = 0; + switch (wtype) { + case wtype_Bits: { + // Current assumption is that size is at most 2^24 and that width is at most 64. + // In that case the following will never overflow. (Assuming that size_t is at least 32 bits) + REALM_ASSERT_3(size, <, 0x1000000); + size_t num_bits = size * width; + num_bytes = (num_bits + 7) >> 3; + break; + } + case wtype_Multiply: { + num_bytes = size * width; + break; + } + case wtype_Ignore: + num_bytes = size; + break; + } + + // Ensure 8-byte alignment + num_bytes = (num_bytes + 7) & ~size_t(7); + + num_bytes += header_size; + + return num_bytes; +} + +inline size_t Array::get_byte_size() const noexcept +{ + const char* header = get_header_from_data(m_data); + WidthType wtype = get_wtype_from_header(header); + size_t num_bytes = calc_byte_size(wtype, m_size, m_width); + + REALM_ASSERT_7(m_alloc.is_read_only(m_ref), ==, true, ||, num_bytes, <=, get_capacity_from_header(header)); + + return num_bytes; +} + + +inline size_t Array::get_byte_size_from_header(const char* header) noexcept +{ + size_t size = get_size_from_header(header); + uint_least8_t width = get_width_from_header(header); + WidthType wtype = get_wtype_from_header(header); + size_t num_bytes = calc_byte_size(wtype, size, width); + + return num_bytes; +} + + +inline void Array::init_header(char* header, bool is_inner_bptree_node, bool has_refs, bool context_flag, + WidthType width_type, int width, size_t size, size_t capacity) noexcept +{ + // Note: Since the header layout contains unallocated bit and/or + // bytes, it is important that we put the entire header into a + // well defined state initially. + std::fill(header, header + header_size, 0); + set_header_is_inner_bptree_node(is_inner_bptree_node, header); + set_header_hasrefs(has_refs, header); + set_header_context_flag(context_flag, header); + set_header_wtype(width_type, header); + set_header_width(width, header); + set_header_size(size, header); + set_header_capacity(capacity, header); +} + + +//------------------------------------------------- + +inline MemRef Array::clone_deep(Allocator& target_alloc) const +{ + char* header = get_header_from_data(m_data); + return clone(MemRef(header, m_ref, m_alloc), m_alloc, target_alloc); // Throws +} + +inline MemRef Array::create_empty_array(Type type, bool context_flag, Allocator& alloc) +{ + size_t size = 0; + int_fast64_t value = 0; + return create_array(type, context_flag, size, value, alloc); // Throws +} + +inline MemRef Array::create_array(Type type, bool context_flag, size_t size, int_fast64_t value, Allocator& alloc) +{ + return create(type, context_flag, wtype_Bits, size, value, alloc); // Throws +} + +inline bool Array::has_parent() const noexcept +{ + return m_parent != nullptr; +} + +inline ArrayParent* Array::get_parent() const noexcept +{ + return m_parent; +} + +inline void Array::set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept +{ + m_parent = parent; + m_ndx_in_parent = ndx_in_parent; +} + +inline size_t Array::get_ndx_in_parent() const noexcept +{ + return m_ndx_in_parent; +} + +inline void Array::set_ndx_in_parent(size_t ndx) noexcept +{ + m_ndx_in_parent = ndx; +} + +inline void Array::adjust_ndx_in_parent(int diff) noexcept +{ + // Note that `diff` is promoted to an unsigned type, and that + // C++03 still guarantees the expected result regardless of the + // sizes of `int` and `decltype(m_ndx_in_parent)`. + m_ndx_in_parent += diff; +} + +inline ref_type Array::get_ref_from_parent() const noexcept +{ + ref_type ref = m_parent->get_child_ref(m_ndx_in_parent); + return ref; +} + +inline bool Array::is_attached() const noexcept +{ + return m_data != nullptr; +} + +inline void Array::detach() noexcept +{ + m_data = nullptr; +} + +inline size_t Array::size() const noexcept +{ + REALM_ASSERT_DEBUG(is_attached()); + return m_size; +} + +inline bool Array::is_empty() const noexcept +{ + return size() == 0; +} + +inline size_t Array::get_max_byte_size(size_t num_elems) noexcept +{ + int max_bytes_per_elem = 8; + return header_size + num_elems * max_bytes_per_elem; +} + +inline void Array::update_parent() +{ + if (m_parent) + m_parent->update_child_ref(m_ndx_in_parent, m_ref); +} + + +inline void Array::update_child_ref(size_t child_ndx, ref_type new_ref) +{ + set(child_ndx, new_ref); +} + +inline ref_type Array::get_child_ref(size_t child_ndx) const noexcept +{ + return get_as_ref(child_ndx); +} + +inline bool Array::is_read_only() const noexcept +{ + REALM_ASSERT_DEBUG(is_attached()); + return m_alloc.is_read_only(m_ref); +} + +inline void Array::copy_on_write() +{ +#if REALM_ENABLE_MEMDEBUG + // We want to relocate this array regardless if there is a need or not, in order to catch use-after-free bugs. + // Only exception is inside GroupWriter::write_group() (see explanation at the definition of the m_no_relocation + // member) + if (!m_no_relocation) { +#else + if (is_read_only()) { +#endif + do_copy_on_write(); + } +} + +inline void Array::ensure_minimum_width(int_fast64_t value) +{ + if (value >= m_lbound && value <= m_ubound) + return; + do_ensure_minimum_width(value); +} + + +//************************************************************************************* +// Finding code * +//************************************************************************************* + +template +int64_t Array::get(size_t ndx) const noexcept +{ + return get_universal(m_data, ndx); +} + +template +int64_t Array::get_universal(const char* data, size_t ndx) const +{ + if (w == 0) { + return 0; + } + else if (w == 1) { + size_t offset = ndx >> 3; + return (data[offset] >> (ndx & 7)) & 0x01; + } + else if (w == 2) { + size_t offset = ndx >> 2; + return (data[offset] >> ((ndx & 3) << 1)) & 0x03; + } + else if (w == 4) { + size_t offset = ndx >> 1; + return (data[offset] >> ((ndx & 1) << 2)) & 0x0F; + } + else if (w == 8) { + return *reinterpret_cast(data + ndx); + } + else if (w == 16) { + size_t offset = ndx * 2; + return *reinterpret_cast(data + offset); + } + else if (w == 32) { + size_t offset = ndx * 4; + return *reinterpret_cast(data + offset); + } + else if (w == 64) { + size_t offset = ndx * 8; + return *reinterpret_cast(data + offset); + } + else { + REALM_ASSERT_DEBUG(false); + return int64_t(-1); + } +} + +/* +find() (calls find_optimized()) will call match() for each search result. + +If pattern == true: + 'indexpattern' contains a 64-bit chunk of elements, each of 'width' bits in size where each element indicates a + match if its lower bit is set, otherwise it indicates a non-match. 'index' tells the database row index of the + first element. You must return true if you chose to 'consume' the chunk or false if not. If not, then Array-finder + will afterwards call match() successive times with pattern == false. + +If pattern == false: + 'index' tells the row index of a single match and 'value' tells its value. Return false to make Array-finder break + its search or return true to let it continue until 'end' or 'limit'. + +Array-finder decides itself if - and when - it wants to pass you an indexpattern. It depends on array bit width, match +frequency, and whether the arithemetic and computations for the given search criteria makes it feasible to construct +such a pattern. +*/ + +// These wrapper functions only exist to enable a possibility to make the compiler see that 'value' and/or 'index' are +// unused, such that caller's computation of these values will not be made. Only works if find_action() and +// find_action_pattern() rewritten as macros. Note: This problem has been fixed in next upcoming array.hpp version +template +bool Array::find_action(size_t index, util::Optional value, QueryState* state, + Callback callback) const +{ + if (action == act_CallbackIdx) + return callback(index); + else + return state->match(index, 0, value); +} +template +bool Array::find_action_pattern(size_t index, uint64_t pattern, QueryState* state, Callback callback) const +{ + static_cast(callback); + if (action == act_CallbackIdx) { + // Possible future optimization: call callback(index) like in above find_action(), in a loop for each bit set + // in 'pattern' + return false; + } + return state->match(index, pattern, 0); +} + + +template +uint64_t Array::cascade(uint64_t a) const +{ + // Takes a chunk of values as argument and sets the least significant bit for each + // element which is zero or non-zero, depending on the template parameter. + // Example for zero=true: + // width == 4 and a = 0x5fd07a107610f610 + // will return: 0x0001000100010001 + + // static values needed for fast population count + const uint64_t m1 = 0x5555555555555555ULL; + + if (width == 1) { + return zero ? ~a : a; + } + else if (width == 2) { + // Masks to avoid spillover between segments in cascades + const uint64_t c1 = ~0ULL / 0x3 * 0x1; + + a |= (a >> 1) & c1; // cascade ones in non-zeroed segments + a &= m1; // isolate single bit in each segment + if (zero) + a ^= m1; // reverse isolated bits if checking for zeroed segments + + return a; + } + else if (width == 4) { + const uint64_t m = ~0ULL / 0xF * 0x1; + + // Masks to avoid spillover between segments in cascades + const uint64_t c1 = ~0ULL / 0xF * 0x7; + const uint64_t c2 = ~0ULL / 0xF * 0x3; + + a |= (a >> 1) & c1; // cascade ones in non-zeroed segments + a |= (a >> 2) & c2; + a &= m; // isolate single bit in each segment + if (zero) + a ^= m; // reverse isolated bits if checking for zeroed segments + + return a; + } + else if (width == 8) { + const uint64_t m = ~0ULL / 0xFF * 0x1; + + // Masks to avoid spillover between segments in cascades + const uint64_t c1 = ~0ULL / 0xFF * 0x7F; + const uint64_t c2 = ~0ULL / 0xFF * 0x3F; + const uint64_t c3 = ~0ULL / 0xFF * 0x0F; + + a |= (a >> 1) & c1; // cascade ones in non-zeroed segments + a |= (a >> 2) & c2; + a |= (a >> 4) & c3; + a &= m; // isolate single bit in each segment + if (zero) + a ^= m; // reverse isolated bits if checking for zeroed segments + + return a; + } + else if (width == 16) { + const uint64_t m = ~0ULL / 0xFFFF * 0x1; + + // Masks to avoid spillover between segments in cascades + const uint64_t c1 = ~0ULL / 0xFFFF * 0x7FFF; + const uint64_t c2 = ~0ULL / 0xFFFF * 0x3FFF; + const uint64_t c3 = ~0ULL / 0xFFFF * 0x0FFF; + const uint64_t c4 = ~0ULL / 0xFFFF * 0x00FF; + + a |= (a >> 1) & c1; // cascade ones in non-zeroed segments + a |= (a >> 2) & c2; + a |= (a >> 4) & c3; + a |= (a >> 8) & c4; + a &= m; // isolate single bit in each segment + if (zero) + a ^= m; // reverse isolated bits if checking for zeroed segments + + return a; + } + + else if (width == 32) { + const uint64_t m = ~0ULL / 0xFFFFFFFF * 0x1; + + // Masks to avoid spillover between segments in cascades + const uint64_t c1 = ~0ULL / 0xFFFFFFFF * 0x7FFFFFFF; + const uint64_t c2 = ~0ULL / 0xFFFFFFFF * 0x3FFFFFFF; + const uint64_t c3 = ~0ULL / 0xFFFFFFFF * 0x0FFFFFFF; + const uint64_t c4 = ~0ULL / 0xFFFFFFFF * 0x00FFFFFF; + const uint64_t c5 = ~0ULL / 0xFFFFFFFF * 0x0000FFFF; + + a |= (a >> 1) & c1; // cascade ones in non-zeroed segments + a |= (a >> 2) & c2; + a |= (a >> 4) & c3; + a |= (a >> 8) & c4; + a |= (a >> 16) & c5; + a &= m; // isolate single bit in each segment + if (zero) + a ^= m; // reverse isolated bits if checking for zeroed segments + + return a; + } + else if (width == 64) { + return (a == 0) == zero; + } + else { + REALM_ASSERT_DEBUG(false); + return uint64_t(-1); + } +} + +// This is the main finding function for Array. Other finding functions are just wrappers around this one. +// Search for 'value' using condition cond (Equal, NotEqual, Less, etc) and call find_action() or +// find_action_pattern() for each match. Break and return if find_action() returns false or 'end' is reached. + +// If nullable_array is set, then find_optimized() will treat the array is being nullable, i.e. it will skip the +// first entry and compare correctly against null, etc. +// +// If find_null is set, it means that we search for a null. In that case, `value` is ignored. If find_null is set, +// then nullable_array must be set too. +template +bool Array::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback, bool nullable_array, bool find_null) const +{ + REALM_ASSERT(!(find_null && !nullable_array)); + REALM_ASSERT_DEBUG(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end); + + size_t start2 = start; + cond c; + + if (end == npos) + end = nullable_array ? size() - 1 : size(); + + if (nullable_array) { + // We were called by find() of a nullable array. So skip first entry, take nulls in count, etc, etc. Fixme: + // Huge speed optimizations are possible here! This is a very simple generic method. + for (; start2 < end; start2++) { + int64_t v = get(start2 + 1); + if (c(v, value, v == get(0), find_null)) { + util::Optional v2(v == get(0) ? util::none : util::make_optional(v)); + if (!find_action(start2 + baseindex, v2, state, callback)) + return false; // tell caller to stop aggregating/search + } + } + return true; // tell caller to continue aggregating/search (on next array leafs) + } + + + // Test first few items with no initial time overhead + if (start2 > 0) { + if (m_size > start2 && c(get(start2), value) && start2 < end) { + if (!find_action(start2 + baseindex, get(start2), state, callback)) + return false; + } + + ++start2; + + if (m_size > start2 && c(get(start2), value) && start2 < end) { + if (!find_action(start2 + baseindex, get(start2), state, callback)) + return false; + } + + ++start2; + + if (m_size > start2 && c(get(start2), value) && start2 < end) { + if (!find_action(start2 + baseindex, get(start2), state, callback)) + return false; + } + + ++start2; + + if (m_size > start2 && c(get(start2), value) && start2 < end) { + if (!find_action(start2 + baseindex, get(start2), state, callback)) + return false; + } + + ++start2; + } + + if (!(m_size > start2 && start2 < end)) + return true; + + if (end == size_t(-1)) + end = m_size; + + // Return immediately if no items in array can match (such as if cond == Greater && value == 100 && + // m_ubound == 15) + if (!c.can_match(value, m_lbound, m_ubound)) + return true; + + // optimization if all items are guaranteed to match (such as cond == NotEqual && value == 100 && m_ubound == 15) + if (c.will_match(value, m_lbound, m_ubound)) { + size_t end2; + + if (action == act_CallbackIdx) + end2 = end; + else { + REALM_ASSERT_DEBUG(state->m_match_count < state->m_limit); + size_t process = state->m_limit - state->m_match_count; + end2 = end - start2 > process ? start2 + process : end; + } + if (action == act_Sum || action == act_Max || action == act_Min) { + int64_t res; + size_t res_ndx = 0; + if (action == act_Sum) + res = Array::sum(start2, end2); + if (action == act_Max) + Array::maximum(res, start2, end2, &res_ndx); + if (action == act_Min) + Array::minimum(res, start2, end2, &res_ndx); + + find_action(res_ndx + baseindex, res, state, callback); + // find_action will increment match count by 1, so we need to `-1` from the number of elements that + // we performed the fast Array methods on. + state->m_match_count += end2 - start2 - 1; + } + else if (action == act_Count) { + state->m_state += end2 - start2; + } + else { + for (; start2 < end2; start2++) + if (!find_action(start2 + baseindex, get(start2), state, callback)) + return false; + } + return true; + } + + // finder cannot handle this bitwidth + REALM_ASSERT_3(m_width, !=, 0); + +#if defined(REALM_COMPILER_SSE) + // Only use SSE if payload is at least one SSE chunk (128 bits) in size. Also note taht SSE doesn't support + // Less-than comparison for 64-bit values. + if ((!(std::is_same::value && m_width == 64)) && end - start2 >= sizeof(__m128i) && m_width >= 8 && + (sseavx<42>() || (sseavx<30>() && std::is_same::value && m_width < 64))) { + + // find_sse() must start2 at 16-byte boundary, so search area before that using compare_equality() + __m128i* const a = reinterpret_cast<__m128i*>(round_up(m_data + start2 * bitwidth / 8, sizeof(__m128i))); + __m128i* const b = reinterpret_cast<__m128i*>(round_down(m_data + end * bitwidth / 8, sizeof(__m128i))); + + if (!compare( + value, start2, (reinterpret_cast(a) - m_data) * 8 / no0(bitwidth), baseindex, state, callback)) + return false; + + // Search aligned area with SSE + if (b > a) { + if (sseavx<42>()) { + if (!find_sse( + value, a, b - a, state, + baseindex + ((reinterpret_cast(a) - m_data) * 8 / no0(bitwidth)), callback)) + return false; + } + else if (sseavx<30>()) { + + if (!find_sse( + value, a, b - a, state, + baseindex + ((reinterpret_cast(a) - m_data) * 8 / no0(bitwidth)), callback)) + return false; + } + } + + // Search remainder with compare_equality() + if (!compare( + value, (reinterpret_cast(b) - m_data) * 8 / no0(bitwidth), end, baseindex, state, callback)) + return false; + + return true; + } + else { + return compare(value, start2, end, baseindex, state, callback); + } +#else + return compare(value, start2, end, baseindex, state, callback); +#endif +} + +template +inline int64_t Array::lower_bits() const +{ + if (width == 1) + return 0xFFFFFFFFFFFFFFFFULL; + else if (width == 2) + return 0x5555555555555555ULL; + else if (width == 4) + return 0x1111111111111111ULL; + else if (width == 8) + return 0x0101010101010101ULL; + else if (width == 16) + return 0x0001000100010001ULL; + else if (width == 32) + return 0x0000000100000001ULL; + else if (width == 64) + return 0x0000000000000001ULL; + else { + REALM_ASSERT_DEBUG(false); + return int64_t(-1); + } +} + +// Tests if any chunk in 'value' is 0 +template +inline bool Array::test_zero(uint64_t value) const +{ + uint64_t hasZeroByte; + uint64_t lower = lower_bits(); + uint64_t upper = lower_bits() * 1ULL << (width == 0 ? 0 : (width - 1ULL)); + hasZeroByte = (value - lower) & ~value & upper; + return hasZeroByte != 0; +} + +// Finds first zero (if eq == true) or non-zero (if eq == false) element in v and returns its position. +// IMPORTANT: This function assumes that at least 1 item matches (test this with test_zero() or other means first)! +template +size_t Array::find_zero(uint64_t v) const +{ + size_t start = 0; + uint64_t hasZeroByte; + // Warning free way of computing (1ULL << width) - 1 + uint64_t mask = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) - 1ULL)); + + if (eq == (((v >> (width * start)) & mask) == 0)) { + return 0; + } + + // Bisection optimization, speeds up small bitwidths with high match frequency. More partions than 2 do NOT pay + // off because the work done by test_zero() is wasted for the cases where the value exists in first half, but + // useful if it exists in last half. Sweet spot turns out to be the widths and partitions below. + if (width <= 8) { + hasZeroByte = test_zero(v | 0xffffffff00000000ULL); + if (eq ? !hasZeroByte : (v & 0x00000000ffffffffULL) == 0) { + // 00?? -> increasing + start += 64 / no0(width) / 2; + if (width <= 4) { + hasZeroByte = test_zero(v | 0xffff000000000000ULL); + if (eq ? !hasZeroByte : (v & 0x0000ffffffffffffULL) == 0) { + // 000? + start += 64 / no0(width) / 4; + } + } + } + else { + if (width <= 4) { + // ??00 + hasZeroByte = test_zero(v | 0xffffffffffff0000ULL); + if (eq ? !hasZeroByte : (v & 0x000000000000ffffULL) == 0) { + // 0?00 + start += 64 / no0(width) / 4; + } + } + } + } + + while (eq == (((v >> (width * start)) & mask) != 0)) { + // You must only call find_zero() if you are sure that at least 1 item matches + REALM_ASSERT_3(start, <=, 8 * sizeof(v)); + start++; + } + + return start; +} + +// Generate a magic constant used for later bithacks +template +int64_t Array::find_gtlt_magic(int64_t v) const +{ + uint64_t mask1 = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) - + 1ULL)); // Warning free way of computing (1ULL << width) - 1 + uint64_t mask2 = mask1 >> 1; + uint64_t magic = gt ? (~0ULL / no0(mask1) * (mask2 - v)) : (~0ULL / no0(mask1) * v); + return magic; +} + +template +bool Array::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryState* state, size_t baseindex, + Callback callback) const +{ + // Tests if a a chunk of values contains values that are greater (if gt == true) or less (if gt == false) than v. + // Fast, but limited to work when all values in the chunk are positive. + + uint64_t mask1 = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) - + 1ULL)); // Warning free way of computing (1ULL << width) - 1 + uint64_t mask2 = mask1 >> 1; + uint64_t m = gt ? (((chunk + magic) | chunk) & ~0ULL / no0(mask1) * (mask2 + 1)) + : ((chunk - magic) & ~chunk & ~0ULL / no0(mask1) * (mask2 + 1)); + size_t p = 0; + while (m) { + if (find_action_pattern(baseindex, m >> (no0(width) - 1), state, callback)) + break; // consumed, so do not call find_action() + + size_t t = first_set_bit64(m) / no0(width); + p += t; + if (!find_action(p + baseindex, (chunk >> (p * width)) & mask1, state, callback)) + return false; + + if ((t + 1) * width == 64) + m = 0; + else + m >>= (t + 1) * width; + p++; + } + + return true; +} + +// clang-format off +template +bool Array::find_gtlt(int64_t v, uint64_t chunk, QueryState* state, size_t baseindex, Callback callback) const +{ + // Find items in 'chunk' that are greater (if gt == true) or smaller (if gt == false) than 'v'. Fixme, __forceinline can make it crash in vS2010 - find out why + if (width == 1) { + for (size_t t = 0; t < 64; t++) { + if (gt ? static_cast(chunk & 0x1) > v : static_cast(chunk & 0x1) < v) {if (!find_action( t + baseindex, static_cast(chunk & 0x1), state, callback)) return false;} + chunk >>= 1; + } + } + else if (width == 2) { + // Alot (50% +) faster than loop/compiler-unrolled loop + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 0 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 1 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 2 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 3 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 4 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 5 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 6 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 7 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 8 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 9 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 10 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 11 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 12 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 13 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 14 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 15 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 16 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 17 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 18 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 19 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 20 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 21 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 22 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 23 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 24 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 25 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 26 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 27 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 28 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 29 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 30 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + if (gt ? static_cast(chunk & 0x3) > v : static_cast(chunk & 0x3) < v) {if (!find_action( 31 + baseindex, static_cast(chunk & 0x3), state, callback)) return false;} + chunk >>= 2; + } + else if (width == 4) { + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 0 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 1 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 2 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 3 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 4 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 5 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 6 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 7 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 8 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 9 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 10 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 11 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 12 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 13 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 14 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + if (gt ? static_cast(chunk & 0xf) > v : static_cast(chunk & 0xf) < v) {if (!find_action( 15 + baseindex, static_cast(chunk & 0xf), state, callback)) return false;} + chunk >>= 4; + } + else if (width == 8) { + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 0 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 1 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 2 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 3 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 4 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 5 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 6 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 7 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 8; + } + else if (width == 16) { + + if (gt ? static_cast(chunk >> 0 * 16) > v : static_cast(chunk >> 0 * 16) < v) {if (!find_action( 0 + baseindex, static_cast(chunk >> 0 * 16), state, callback)) return false;}; + if (gt ? static_cast(chunk >> 1 * 16) > v : static_cast(chunk >> 1 * 16) < v) {if (!find_action( 1 + baseindex, static_cast(chunk >> 1 * 16), state, callback)) return false;}; + if (gt ? static_cast(chunk >> 2 * 16) > v : static_cast(chunk >> 2 * 16) < v) {if (!find_action( 2 + baseindex, static_cast(chunk >> 2 * 16), state, callback)) return false;}; + if (gt ? static_cast(chunk >> 3 * 16) > v : static_cast(chunk >> 3 * 16) < v) {if (!find_action( 3 + baseindex, static_cast(chunk >> 3 * 16), state, callback)) return false;}; + } + else if (width == 32) { + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 0 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 32; + if (gt ? static_cast(chunk) > v : static_cast(chunk) < v) {if (!find_action( 1 + baseindex, static_cast(chunk), state, callback)) return false;} + chunk >>= 32; + } + else if (width == 64) { + if (gt ? static_cast(v) > v : static_cast(v) < v) {if (!find_action( 0 + baseindex, static_cast(v), state, callback)) return false;}; + } + + return true; +} +// clang-format on + +/// Find items in this Array that are equal (eq == true) or different (eq = false) from 'value' +template +inline bool Array::compare_equality(int64_t value, size_t start, size_t end, size_t baseindex, + QueryState* state, Callback callback) const +{ + REALM_ASSERT_DEBUG(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end); + + size_t ee = round_up(start, 64 / no0(width)); + ee = ee > end ? end : ee; + for (; start < ee; ++start) + if (eq ? (get(start) == value) : (get(start) != value)) { + if (!find_action(start + baseindex, get(start), state, callback)) + return false; + } + + if (start >= end) + return true; + + if (width != 32 && width != 64) { + const int64_t* p = reinterpret_cast(m_data + (start * width / 8)); + const int64_t* const e = reinterpret_cast(m_data + (end * width / 8)) - 1; + const uint64_t mask = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) - + 1ULL)); // Warning free way of computing (1ULL << width) - 1 + const uint64_t valuemask = + ~0ULL / no0(mask) * (value & mask); // the "== ? :" is to avoid division by 0 compiler error + + while (p < e) { + uint64_t chunk = *p; + uint64_t v2 = chunk ^ valuemask; + start = (p - reinterpret_cast(m_data)) * 8 * 8 / no0(width); + size_t a = 0; + + while (eq ? test_zero(v2) : v2) { + + if (find_action_pattern(start + baseindex, cascade(v2), state, callback)) + break; // consumed + + size_t t = find_zero(v2); + a += t; + + if (a >= 64 / no0(width)) + break; + + if (!find_action(a + start + baseindex, get(start + t), state, callback)) + return false; + v2 >>= (t + 1) * width; + a += 1; + } + + ++p; + } + + // Loop ended because we are near end or end of array. No need to optimize search in remainder in this case + // because end of array means that + // lots of search work has taken place prior to ending here. So time spent searching remainder is relatively + // tiny + start = (p - reinterpret_cast(m_data)) * 8 * 8 / no0(width); + } + + while (start < end) { + if (eq ? get(start) == value : get(start) != value) { + if (!find_action(start + baseindex, get(start), state, callback)) + return false; + } + ++start; + } + + return true; +} + +// There exists a couple of find() functions that take more or less template arguments. Always call the one that +// takes as most as possible to get best performance. + +// This is the one installed into the m_vtable->finder slots. +template +bool Array::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state) const +{ + return find(value, start, end, baseindex, state, CallbackDummy()); +} + +template +bool Array::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback, bool nullable_array, bool find_null) const +{ + REALM_TEMPEX4(return find, cond, action, m_width, Callback, + (value, start, end, baseindex, state, callback, nullable_array, find_null)); +} + +template +bool Array::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback, bool nullable_array, bool find_null) const +{ + return find_optimized(value, start, end, baseindex, state, callback, + nullable_array, find_null); +} + +#ifdef REALM_COMPILER_SSE +// 'items' is the number of 16-byte SSE chunks. Returns index of packed element relative to first integer of first +// chunk +template +bool Array::find_sse(int64_t value, __m128i* data, size_t items, QueryState* state, size_t baseindex, + Callback callback) const +{ + __m128i search = {0}; + + if (width == 8) + search = _mm_set1_epi8(static_cast(value)); + else if (width == 16) + search = _mm_set1_epi16(static_cast(value)); + else if (width == 32) + search = _mm_set1_epi32(static_cast(value)); + else if (width == 64) { + if (std::is_same::value) + REALM_ASSERT(false); + else + search = _mm_set_epi64x(value, value); + } + + return find_sse_intern(data, &search, items, state, baseindex, callback); +} + +// Compares packed action_data with packed data (equal, less, etc) and performs aggregate action (max, min, sum, +// find_all, etc) on value inside action_data for first match, if any +template +REALM_FORCEINLINE bool Array::find_sse_intern(__m128i* action_data, __m128i* data, size_t items, + QueryState* state, size_t baseindex, Callback callback) const +{ + size_t i = 0; + __m128i compare_result = {0}; + unsigned int resmask; + + // Search loop. Unrolling it has been tested to NOT increase performance (apparently mem bound) + for (i = 0; i < items; ++i) { + // equal / not-equal + if (std::is_same::value || std::is_same::value) { + if (width == 8) + compare_result = _mm_cmpeq_epi8(action_data[i], *data); + if (width == 16) + compare_result = _mm_cmpeq_epi16(action_data[i], *data); + if (width == 32) + compare_result = _mm_cmpeq_epi32(action_data[i], *data); + if (width == 64) { + compare_result = _mm_cmpeq_epi64(action_data[i], *data); // SSE 4.2 only + } + } + + // greater + else if (std::is_same::value) { + if (width == 8) + compare_result = _mm_cmpgt_epi8(action_data[i], *data); + if (width == 16) + compare_result = _mm_cmpgt_epi16(action_data[i], *data); + if (width == 32) + compare_result = _mm_cmpgt_epi32(action_data[i], *data); + if (width == 64) + compare_result = _mm_cmpgt_epi64(action_data[i], *data); + } + // less + else if (std::is_same::value) { + if (width == 8) + compare_result = _mm_cmplt_epi8(action_data[i], *data); + else if (width == 16) + compare_result = _mm_cmplt_epi16(action_data[i], *data); + else if (width == 32) + compare_result = _mm_cmplt_epi32(action_data[i], *data); + else + REALM_ASSERT(false); + } + + resmask = _mm_movemask_epi8(compare_result); + + if (std::is_same::value) + resmask = ~resmask & 0x0000ffff; + + size_t s = i * sizeof(__m128i) * 8 / no0(width); + + while (resmask != 0) { + + uint64_t upper = lower_bits() << (no0(width / 8) - 1); + uint64_t pattern = + resmask & + upper; // fixme, bits at wrong offsets. Only OK because we only use them in 'count' aggregate + if (find_action_pattern(s + baseindex, pattern, state, callback)) + break; + + size_t idx = first_set_bit(resmask) * 8 / no0(width); + s += idx; + if (!find_action( + s + baseindex, get_universal(reinterpret_cast(action_data), s), state, callback)) + return false; + resmask >>= (idx + 1) * no0(width) / 8; + ++s; + } + } + + return true; +} +#endif // REALM_COMPILER_SSE + +template +bool Array::compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, + QueryState* state, Callback callback) const +{ + cond c; + REALM_ASSERT_3(start, <=, end); + if (start == end) + return true; + + + int64_t v; + + // We can compare first element without checking for out-of-range + v = get(start); + if (c(v, foreign->get(start))) { + if (!find_action(start + baseindex, v, state, callback)) + return false; + } + + start++; + + if (start + 3 < end) { + v = get(start); + if (c(v, foreign->get(start))) + if (!find_action(start + baseindex, v, state, callback)) + return false; + + v = get(start + 1); + if (c(v, foreign->get(start + 1))) + if (!find_action(start + 1 + baseindex, v, state, callback)) + return false; + + v = get(start + 2); + if (c(v, foreign->get(start + 2))) + if (!find_action(start + 2 + baseindex, v, state, callback)) + return false; + + start += 3; + } + else if (start == end) { + return true; + } + + bool r; + REALM_TEMPEX4(r = compare_leafs, cond, action, m_width, Callback, + (foreign, start, end, baseindex, state, callback)) + return r; +} + + +template +bool Array::compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, + QueryState* state, Callback callback) const +{ + size_t fw = foreign->m_width; + bool r; + REALM_TEMPEX5(r = compare_leafs_4, cond, action, width, Callback, fw, + (foreign, start, end, baseindex, state, callback)) + return r; +} + + +template +bool Array::compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, + QueryState* state, Callback callback) const +{ + cond c; + char* foreign_m_data = foreign->m_data; + + if (width == 0 && foreign_width == 0) { + if (c(0, 0)) { + while (start < end) { + if (!find_action(start + baseindex, 0, state, callback)) + return false; + start++; + } + } + else { + return true; + } + } + + +#if defined(REALM_COMPILER_SSE) + if (sseavx<42>() && width == foreign_width && (width == 8 || width == 16 || width == 32)) { + // We can only use SSE if both bitwidths are equal and above 8 bits and all values are signed + while (start < end && (((reinterpret_cast(m_data) & 0xf) * 8 + start * width) % (128) != 0)) { + int64_t v = get_universal(m_data, start); + int64_t fv = get_universal(foreign_m_data, start); + if (c(v, fv)) { + if (!find_action(start + baseindex, v, state, callback)) + return false; + } + start++; + } + if (start == end) + return true; + + + size_t sse_items = (end - start) * width / 128; + size_t sse_end = start + sse_items * 128 / no0(width); + + while (start < sse_end) { + __m128i* a = reinterpret_cast<__m128i*>(m_data + start * width / 8); + __m128i* b = reinterpret_cast<__m128i*>(foreign_m_data + start * width / 8); + + bool continue_search = + find_sse_intern(a, b, 1, state, baseindex + start, callback); + + if (!continue_search) + return false; + + start += 128 / no0(width); + } + } +#endif + + while (start < end) { + int64_t v = get_universal(m_data, start); + int64_t fv = get_universal(foreign_m_data, start); + + if (c(v, fv)) { + if (!find_action(start + baseindex, v, state, callback)) + return false; + } + + start++; + } + + return true; +} + + +template +bool Array::compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const +{ + bool ret = false; + + if (std::is_same::value) + ret = compare_equality(value, start, end, baseindex, state, callback); + else if (std::is_same::value) + ret = compare_equality(value, start, end, baseindex, state, callback); + else if (std::is_same::value) + ret = compare_relation(value, start, end, baseindex, state, callback); + else if (std::is_same::value) + ret = compare_relation(value, start, end, baseindex, state, callback); + else + REALM_ASSERT_DEBUG(false); + + return ret; +} + +template +bool Array::compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryState* state, + Callback callback) const +{ + REALM_ASSERT(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end); + uint64_t mask = (bitwidth == 64 ? ~0ULL : ((1ULL << (bitwidth == 64 ? 0 : bitwidth)) - + 1ULL)); // Warning free way of computing (1ULL << width) - 1 + + size_t ee = round_up(start, 64 / no0(bitwidth)); + ee = ee > end ? end : ee; + for (; start < ee; start++) { + if (gt ? (get(start) > value) : (get(start) < value)) { + if (!find_action(start + baseindex, get(start), state, callback)) + return false; + } + } + + if (start >= end) + return true; // none found, continue (return true) regardless what find_action() would have returned on match + + const int64_t* p = reinterpret_cast(m_data + (start * bitwidth / 8)); + const int64_t* const e = reinterpret_cast(m_data + (end * bitwidth / 8)) - 1; + + // Matches are rare enough to setup fast linear search for remaining items. We use + // bit hacks from http://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord + + if (bitwidth == 1 || bitwidth == 2 || bitwidth == 4 || bitwidth == 8 || bitwidth == 16) { + uint64_t magic = find_gtlt_magic(value); + + // Bit hacks only work if searched item has its most significant bit clear for 'greater than' or + // 'item <= 1 << bitwidth' for 'less than' + if (value != int64_t((magic & mask)) && value >= 0 && bitwidth >= 2 && + value <= static_cast((mask >> 1) - (gt ? 1 : 0))) { + // 15 ms + while (p < e) { + uint64_t upper = lower_bits() << (no0(bitwidth) - 1); + + const int64_t v = *p; + size_t idx; + + // Bit hacks only works if all items in chunk have their most significant bit clear. Test this: + upper = upper & v; + + if (!upper) { + idx = find_gtlt_fast( + v, magic, state, (p - reinterpret_cast(m_data)) * 8 * 8 / no0(bitwidth) + baseindex, + callback); + } + else + idx = find_gtlt( + value, v, state, (p - reinterpret_cast(m_data)) * 8 * 8 / no0(bitwidth) + baseindex, + callback); + + if (!idx) + return false; + ++p; + } + } + else { + // 24 ms + while (p < e) { + int64_t v = *p; + if (!find_gtlt( + value, v, state, (p - reinterpret_cast(m_data)) * 8 * 8 / no0(bitwidth) + baseindex, + callback)) + return false; + ++p; + } + } + start = (p - reinterpret_cast(m_data)) * 8 * 8 / no0(bitwidth); + } + + // matchcount logic in SIMD no longer pays off for 32/64 bit ints because we have just 4/2 elements + + // Test unaligned end and/or values of width > 16 manually + while (start < end) { + if (gt ? get(start) > value : get(start) < value) { + if (!find_action(start + baseindex, get(start), state, callback)) + return false; + } + ++start; + } + return true; +} + +template +size_t Array::find_first(int64_t value, size_t start, size_t end) const +{ + REALM_ASSERT(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end); + QueryState state; + state.init(act_ReturnFirst, nullptr, + 1); // todo, would be nice to avoid this in order to speed up find_first loops + Finder finder = m_vtable->finder[cond::condition]; + (this->*finder)(value, start, end, 0, &state); + + return static_cast(state.m_state); +} + +//************************************************************************************* +// Finding code ends * +//************************************************************************************* + + +} // namespace realm + +#endif // REALM_ARRAY_HPP