1 /*************************************************************************
3 * Copyright 2016 Realm Inc.
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
17 **************************************************************************/
20 Searching: The main finding function is:
21 template <class cond, Action action, size_t bitwidth, class Callback>
22 void find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState *state, Callback callback) const
24 cond: One of Equal, NotEqual, Greater, etc. classes
25 Action: One of act_ReturnFirst, act_FindAll, act_Max, act_CallbackIdx, etc, constants
26 Callback: Optional function to call for each search result. Will be called if action == act_CallbackIdx
28 find() will call find_action_pattern() or find_action() that again calls match() for each search result which
29 optionally calls callback():
31 find() -> find_action() -------> bool match() -> bool callback()
33 +-> find_action_pattern()----+
35 If callback() returns false, find() will exit, otherwise it will keep searching remaining items in array.
38 #ifndef REALM_ARRAY_HPP
39 #define REALM_ARRAY_HPP
42 #include <cstdlib> // size_t
48 #include <cstdint> // unint8_t etc
50 #include <realm/util/assert.hpp>
51 #include <realm/util/file_mapper.hpp>
52 #include <realm/utilities.hpp>
53 #include <realm/alloc.hpp>
54 #include <realm/string_data.hpp>
55 #include <realm/query_conditions.hpp>
56 #include <realm/column_fwd.hpp>
57 #include <realm/array_direct.hpp>
69 #ifdef REALM_COMPILER_SSE
70 #include <emmintrin.h> // SSE2
71 #include <realm/realm_nmmintrin.h> // SSE42
94 return v == 0 ? 1 : v;
97 /// Special index value. It has various meanings depending on
98 /// context. It is returned by some search functions to indicate 'not
99 /// found'. It is similar in function to std::string::npos.
100 const size_t npos = size_t(-1);
102 // Maximum number of bytes that the payload of an array can be
103 const size_t max_array_payload = 0x00ffffffL;
104 const size_t max_array_payload_aligned = 0x00fffff8L;
106 /// Alias for realm::npos.
107 const size_t not_found = npos;
116 class ArrayWriterBase;
121 size_t allocated = 0;
123 size_t array_count = 0;
127 template <class C, class T>
128 std::basic_ostream<C, T>& operator<<(std::basic_ostream<C, T>& out, MemStats stats);
132 // Stores a value obtained from Array::get(). It is a ref if the least
133 // significant bit is clear, otherwise it is a tagged integer. A tagged interger
134 // is obtained from a logical integer value by left shifting by one bit position
135 // (multiplying by two), and then setting the least significant bit to
136 // one. Clearly, this means that the maximum value that can be stored as a
137 // tagged integer is 2**63 - 1.
140 bool is_ref() const noexcept;
141 bool is_tagged() const noexcept;
142 ref_type get_as_ref() const noexcept;
143 uint_fast64_t get_as_int() const noexcept;
145 static RefOrTagged make_ref(ref_type) noexcept;
146 static RefOrTagged make_tagged(uint_fast64_t) noexcept;
149 int_fast64_t m_value;
150 RefOrTagged(int_fast64_t) noexcept;
157 virtual ~ArrayParent() noexcept
162 virtual void update_child_ref(size_t child_ndx, ref_type new_ref) = 0;
164 virtual ref_type get_child_ref(size_t child_ndx) const noexcept = 0;
166 // Used only by Array::to_dot().
167 virtual std::pair<ref_type, size_t> get_to_dot_parent(size_t ndx_in_parent) const = 0;
172 struct TreeInsertBase {
173 size_t m_split_offset;
177 /// Provides access to individual array nodes of the database.
179 /// This class serves purely as an accessor, it assumes no ownership of the
180 /// referenced memory.
182 /// An array accessor can be in one of two states: attached or unattached. It is
183 /// in the attached state if, and only if is_attached() returns true. Most
184 /// non-static member functions of this class have undefined behaviour if the
185 /// accessor is in the unattached state. The exceptions are: is_attached(),
186 /// detach(), create(), init_from_ref(), init_from_mem(), init_from_parent(),
187 /// has_parent(), get_parent(), set_parent(), get_ndx_in_parent(),
188 /// set_ndx_in_parent(), adjust_ndx_in_parent(), and get_ref_from_parent().
190 /// An array accessor contains information about the parent of the referenced
191 /// array node. This 'reverse' reference is not explicitely present in the
192 /// underlying node hierarchy, but it is needed when modifying an array. A
193 /// modification may lead to relocation of the underlying array node, and the
194 /// parent must be updated accordingly. Since this applies recursivly all the
195 /// way to the root node, it is essential that the entire chain of parent
196 /// accessors is constructed and propperly maintained when a particular array is
199 /// The parent reference (`pointer to parent`, `index in parent`) is updated
200 /// independently from the state of attachment to an underlying node. In
201 /// particular, the parent reference remains valid and is unannfected by changes
202 /// in attachment. These two aspects of the state of the accessor is updated
203 /// independently, and it is entirely the responsibility of the caller to update
204 /// them such that they are consistent with the underlying node hierarchy before
205 /// calling any method that modifies the underlying array node.
207 /// FIXME: This class currently has fragments of ownership, in particular the
208 /// constructors that allocate underlying memory. On the other hand, the
209 /// destructor never frees the memory. This is a problematic situation, because
210 /// it so easily becomes an obscure source of leaks. There are three options for
211 /// a fix of which the third is most attractive but hardest to implement: (1)
212 /// Remove all traces of ownership semantics, that is, remove the constructors
213 /// that allocate memory, but keep the trivial copy constructor. For this to
214 /// work, it is important that the constness of the accessor has nothing to do
215 /// with the constness of the underlying memory, otherwise constness can be
216 /// violated simply by copying the accessor. (2) Disallov copying but associate
217 /// the constness of the accessor with the constness of the underlying
218 /// memory. (3) Provide full ownership semantics like is done for Table
219 /// accessors, and provide a proper copy constructor that really produces a copy
220 /// of the array. For this to work, the class should assume ownership if, and
221 /// only if there is no parent. A copy produced by a copy constructor will not
222 /// have a parent. Even if the original was part of a database, the copy will be
223 /// free-standing, that is, not be part of any database. For intra, or inter
224 /// database copying, one would have to also specify the target allocator.
225 class Array : public ArrayParent {
227 // void state_init(int action, QueryState *state);
228 // bool match(int action, size_t index, int64_t value, QueryState *state);
230 /// Create an array accessor in the unattached state.
231 explicit Array(Allocator&) noexcept;
233 ~Array() noexcept override
240 /// This array is the main array of an innner node of a B+-tree as used
241 /// in table columns.
242 type_InnerBptreeNode,
244 /// This array may contain refs to subarrays. An element whose least
245 /// significant bit is zero, is a ref pointing to a subarray. An element
246 /// whose least significant bit is one, is just a value. It is the
247 /// responsibility of the application to ensure that non-ref values have
248 /// their least significant bit set. This will generally be done by
249 /// shifting the desired vlue to the left by one bit position, and then
250 /// setting the vacated bit to one.
254 /// Create a new integer array of the specified type and size, and filled
255 /// with the specified value, and attach this accessor to it. This does not
256 /// modify the parent reference information of this accessor.
258 /// Note that the caller assumes ownership of the allocated underlying
259 /// node. It is not owned by the accessor.
260 void create(Type, bool context_flag = false, size_t size = 0, int_fast64_t value = 0);
262 /// Reinitialize this array accessor to point to the specified new
263 /// underlying memory. This does not modify the parent reference information
264 /// of this accessor.
265 void init_from_ref(ref_type) noexcept;
267 /// Same as init_from_ref(ref_type) but avoid the mapping of 'ref' to memory
269 void init_from_mem(MemRef) noexcept;
271 /// Same as `init_from_ref(get_ref_from_parent())`.
272 void init_from_parent() noexcept;
274 /// Update the parents reference to this child. This requires, of course,
275 /// that the parent information stored in this child is up to date. If the
276 /// parent pointer is set to null, this function has no effect.
277 void update_parent();
279 /// Called in the context of Group::commit() to ensure that attached
280 /// accessors stay valid across a commit. Please note that this works only
281 /// for non-transactional commits. Accessors obtained during a transaction
282 /// are always detached when the transaction ends.
284 /// Returns true if, and only if the array has changed. If the array has not
285 /// changed, then its children are guaranteed to also not have changed.
286 bool update_from_parent(size_t old_baseline) noexcept;
288 /// Change the type of an already attached array node.
290 /// The effect of calling this function on an unattached accessor is
294 /// Construct a complete copy of this array (including its subarrays) using
295 /// the specified target allocator and return just the reference to the
296 /// underlying memory.
297 MemRef clone_deep(Allocator& target_alloc) const;
299 /// Construct an empty integer array of the specified type, and return just
300 /// the reference to the underlying memory.
301 static MemRef create_empty_array(Type, bool context_flag, Allocator&);
303 /// Construct an integer array of the specified type and size, and return
304 /// just the reference to the underlying memory. All elements will be
305 /// initialized to the specified value.
306 static MemRef create_array(Type, bool context_flag, size_t size, int_fast64_t value, Allocator&);
308 /// Construct a shallow copy of the specified slice of this array using the
309 /// specified target allocator. Subarrays will **not** be cloned. See
310 /// slice_and_clone_children() for an alternative.
311 MemRef slice(size_t offset, size_t slice_size, Allocator& target_alloc) const;
313 /// Construct a deep copy of the specified slice of this array using the
314 /// specified target allocator. Subarrays will be cloned.
315 MemRef slice_and_clone_children(size_t offset, size_t slice_size, Allocator& target_alloc) const;
318 bool has_parent() const noexcept;
319 ArrayParent* get_parent() const noexcept;
321 /// Setting a new parent affects ownership of the attached array node, if
322 /// any. If a non-null parent is specified, and there was no parent
323 /// originally, then the caller passes ownership to the parent, and vice
324 /// versa. This assumes, of course, that the change in parentship reflects a
325 /// corresponding change in the list of children in the affected parents.
326 void set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept;
328 size_t get_ndx_in_parent() const noexcept;
329 void set_ndx_in_parent(size_t) noexcept;
330 void adjust_ndx_in_parent(int diff) noexcept;
332 /// Get the ref of this array as known to the parent. The caller must ensure
333 /// that the parent information ('pointer to parent' and 'index in parent')
334 /// is correct before calling this function.
335 ref_type get_ref_from_parent() const noexcept;
337 bool is_attached() const noexcept;
339 /// Detach from the underlying array node. This method has no effect if the
340 /// accessor is currently unattached (idempotency).
341 void detach() noexcept;
343 size_t size() const noexcept;
344 bool is_empty() const noexcept;
345 Type get_type() const noexcept;
347 static void add_to_column(IntegerColumn* column, int64_t value);
349 void insert(size_t ndx, int_fast64_t value);
350 void add(int_fast64_t value);
352 /// This function is guaranteed to not throw if the current width is
353 /// sufficient for the specified value (e.g. if you have called
354 /// ensure_minimum_width(value)) and get_alloc().is_read_only(get_ref())
355 /// returns false (noexcept:array-set). Note that for a value of zero, the
356 /// first criterion is trivially satisfied.
357 void set(size_t ndx, int64_t value);
359 void set_as_ref(size_t ndx, ref_type ref);
362 void set(size_t ndx, int64_t value);
364 int64_t get(size_t ndx) const noexcept;
367 int64_t get(size_t ndx) const noexcept;
369 void get_chunk(size_t ndx, int64_t res[8]) const noexcept;
372 void get_chunk(size_t ndx, int64_t res[8]) const noexcept;
374 ref_type get_as_ref(size_t ndx) const noexcept;
376 RefOrTagged get_as_ref_or_tagged(size_t ndx) const noexcept;
377 void set(size_t ndx, RefOrTagged);
378 void add(RefOrTagged);
379 void ensure_minimum_width(RefOrTagged);
381 int64_t front() const noexcept;
382 int64_t back() const noexcept;
384 /// Remove the element at the specified index, and move elements at higher
385 /// indexes to the next lower index.
387 /// This function does **not** destroy removed subarrays. That is, if the
388 /// erased element is a 'ref' pointing to a subarray, then that subarray
389 /// will not be destroyed automatically.
391 /// This function guarantees that no exceptions will be thrown if
392 /// get_alloc().is_read_only(get_ref()) would return false before the
393 /// call. This is automatically guaranteed if the array is used in a
394 /// non-transactional context, or if the array has already been successfully
395 /// modified within the current write transaction.
396 void erase(size_t ndx);
398 /// Same as erase(size_t), but remove all elements in the specified
401 /// Please note that this function does **not** destroy removed subarrays.
403 /// This function guarantees that no exceptions will be thrown if
404 /// get_alloc().is_read_only(get_ref()) would return false before the call.
405 void erase(size_t begin, size_t end);
407 /// Reduce the size of this array to the specified number of elements. It is
408 /// an error to specify a size that is greater than the current size of this
409 /// array. The effect of doing so is undefined. This is just a shorthand for
410 /// calling the ranged erase() function with appropriate arguments.
412 /// Please note that this function does **not** destroy removed
413 /// subarrays. See clear_and_destroy_children() for an alternative.
415 /// This function guarantees that no exceptions will be thrown if
416 /// get_alloc().is_read_only(get_ref()) would return false before the call.
417 void truncate(size_t new_size);
419 /// Reduce the size of this array to the specified number of elements. It is
420 /// an error to specify a size that is greater than the current size of this
421 /// array. The effect of doing so is undefined. Subarrays will be destroyed
422 /// recursively, as if by a call to `destroy_deep(subarray_ref, alloc)`.
424 /// This function is guaranteed not to throw if
425 /// get_alloc().is_read_only(get_ref()) returns false.
426 void truncate_and_destroy_children(size_t new_size);
428 /// Remove every element from this array. This is just a shorthand for
429 /// calling truncate(0).
431 /// Please note that this function does **not** destroy removed
432 /// subarrays. See clear_and_destroy_children() for an alternative.
434 /// This function guarantees that no exceptions will be thrown if
435 /// get_alloc().is_read_only(get_ref()) would return false before the call.
438 /// Remove every element in this array. Subarrays will be destroyed
439 /// recursively, as if by a call to `destroy_deep(subarray_ref,
440 /// alloc)`. This is just a shorthand for calling
441 /// truncate_and_destroy_children(0).
443 /// This function guarantees that no exceptions will be thrown if
444 /// get_alloc().is_read_only(get_ref()) would return false before the call.
445 void clear_and_destroy_children();
447 /// If neccessary, expand the representation so that it can store the
449 void ensure_minimum_width(int_fast64_t value);
451 /// This one may change the represenation of the array, so be carefull if
452 /// you call it after ensure_minimum_width().
453 void set_all_to_zero();
455 /// Add \a diff to the element at the specified index.
456 void adjust(size_t ndx, int_fast64_t diff);
458 /// Add \a diff to all the elements in the specified index range.
459 void adjust(size_t begin, size_t end, int_fast64_t diff);
461 /// Add signed \a diff to all elements that are greater than, or equal to \a
463 void adjust_ge(int_fast64_t limit, int_fast64_t diff);
466 /// These are similar in spirit to std::move() and std::move_backward from
467 /// `<algorithm>`. \a dest_begin must not be in the range [`begin`,`end`), and
468 /// \a dest_end must not be in the range (`begin`,`end`].
470 /// These functions are guaranteed to not throw if
471 /// `get_alloc().is_read_only(get_ref())` returns false.
472 void move(size_t begin, size_t end, size_t dest_begin);
473 void move_backward(size_t begin, size_t end, size_t dest_end);
476 /// move_rotate moves one element from \a from to be located at index \a to,
477 /// shifting all elements inbetween by one.
479 /// If \a from is larger than \a to, the elements inbetween are shifted down.
480 /// If \a to is larger than \a from, the elements inbetween are shifted up.
482 /// This function is guaranteed to not throw if
483 /// `get_alloc().is_read_only(get_ref())` returns false.
484 void move_rotate(size_t from, size_t to, size_t num_elems = 1);
487 /// Find the lower/upper bound of the specified value in a sequence of
488 /// integers which must already be sorted ascendingly.
490 /// For an integer value '`v`', lower_bound_int(v) returns the index '`l`'
491 /// of the first element such that `get(l) ≥ v`, and upper_bound_int(v)
492 /// returns the index '`u`' of the first element such that `get(u) >
493 /// v`. In both cases, if no such element is found, the returned value is
494 /// the number of elements in the array.
496 /// 3 3 3 4 4 4 5 6 7 9 9 9
499 /// | | | | -- Lower and upper bound of 15
501 /// | | | -- Lower and upper bound of 8
503 /// | | -- Upper bound of 4
505 /// | -- Lower bound of 4
507 /// -- Lower and upper bound of 1
509 /// These functions are similar to std::lower_bound() and
510 /// std::upper_bound().
512 /// We currently use binary search. See for example
513 /// http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary.
515 /// FIXME: It may be worth considering if overall efficiency can be improved
516 /// by doing a linear search for short sequences.
517 size_t lower_bound_int(int64_t value) const noexcept;
518 size_t upper_bound_int(int64_t value) const noexcept;
521 /// \brief Search the \c Array for a value greater or equal than \a target,
522 /// starting the search at the \a start index. If \a indirection is
523 /// provided, use it as a look-up table to iterate over the \c Array.
525 /// If \a indirection is not provided, then the \c Array must be sorted in
526 /// ascending order. If \a indirection is provided, then its values should
527 /// point to indices in this \c Array in such a way that iteration happens
528 /// in ascending order.
530 /// Behaviour is undefined if:
531 /// - a value in \a indirection is out of bounds for this \c Array;
532 /// - \a indirection does not contain at least as many elements as this \c
534 /// - sorting conditions are not respected;
535 /// - \a start is greater than the number of elements in this \c Array or
536 /// \a indirection (if provided).
538 /// \param target the smallest value to search for
539 /// \param start the offset at which to start searching in the array
540 /// \param indirection an \c Array containing valid indices of values in
541 /// this \c Array, sorted in ascending order
542 /// \return the index of the value if found, or realm::not_found otherwise
543 size_t find_gte(const int64_t target, size_t start, size_t end = size_t(-1)) const;
545 void preset(int64_t min, int64_t max, size_t num_items);
546 void preset(size_t bitwidth, size_t num_items);
548 int64_t sum(size_t start = 0, size_t end = size_t(-1)) const;
549 size_t count(int64_t value) const noexcept;
551 bool maximum(int64_t& result, size_t start = 0, size_t end = size_t(-1), size_t* return_ndx = nullptr) const;
553 bool minimum(int64_t& result, size_t start = 0, size_t end = size_t(-1), size_t* return_ndx = nullptr) const;
555 /// This information is guaranteed to be cached in the array accessor.
556 bool is_inner_bptree_node() const noexcept;
558 /// Returns true if type is either type_HasRefs or type_InnerColumnNode.
560 /// This information is guaranteed to be cached in the array accessor.
561 bool has_refs() const noexcept;
562 void set_has_refs(bool) noexcept;
564 /// This information is guaranteed to be cached in the array accessor.
566 /// Columns and indexes can use the context bit to differentiate leaf types.
567 bool get_context_flag() const noexcept;
568 void set_context_flag(bool) noexcept;
570 ref_type get_ref() const noexcept;
571 MemRef get_mem() const noexcept;
573 /// Destroy only the array that this accessor is attached to, not the
574 /// children of that array. See non-static destroy_deep() for an
575 /// alternative. If this accessor is already in the detached state, this
576 /// function has no effect (idempotency).
577 void destroy() noexcept;
579 /// Recursively destroy children (as if calling
580 /// clear_and_destroy_children()), then put this accessor into the detached
581 /// state (as if calling detach()), then free the allocated memory. If this
582 /// accessor is already in the detached state, this function has no effect
584 void destroy_deep() noexcept;
586 /// Shorthand for `destroy(MemRef(ref, alloc), alloc)`.
587 static void destroy(ref_type ref, Allocator& alloc) noexcept;
589 /// Destroy only the specified array node, not its children. See also
590 /// destroy_deep(MemRef, Allocator&).
591 static void destroy(MemRef, Allocator&) noexcept;
593 /// Shorthand for `destroy_deep(MemRef(ref, alloc), alloc)`.
594 static void destroy_deep(ref_type ref, Allocator& alloc) noexcept;
596 /// Destroy the specified array node and all of its children, recursively.
598 /// This is done by freeing the specified array node after calling
599 /// destroy_deep() for every contained 'ref' element.
600 static void destroy_deep(MemRef, Allocator&) noexcept;
602 Allocator& get_alloc() const noexcept
609 /// Returns the ref (position in the target stream) of the written copy of
610 /// this array, or the ref of the original array if \a only_if_modified is
611 /// true, and this array is unmodified (Alloc::is_read_only()).
613 /// The number of bytes that will be written by a non-recursive invocation
614 /// of this function is exactly the number returned by get_byte_size().
616 /// \param out The destination stream (writer).
618 /// \param deep If true, recursively write out subarrays, but still subject
619 /// to \a only_if_modified.
621 /// \param only_if_modified Set to `false` to always write, or to `true` to
622 /// only write the array if it has been modified.
623 ref_type write(_impl::ArrayWriterBase& out, bool deep, bool only_if_modified) const;
625 /// Same as non-static write() with `deep` set to true. This is for the
626 /// cases where you do not already have an array accessor available.
627 static ref_type write(ref_type, Allocator&, _impl::ArrayWriterBase&, bool only_if_modified);
629 // Main finding function - used for find_first, find_all, sum, max, min, etc.
630 bool find(int cond, Action action, int64_t value, size_t start, size_t end, size_t baseindex,
631 QueryState<int64_t>* state, bool nullable_array = false, bool find_null = false) const;
633 // Templated find function to avoid conversion to and from integer represenation of condition
634 template <class cond>
635 bool find(Action action, int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
636 bool nullable_array = false, bool find_null = false) const
638 if (action == act_ReturnFirst) {
639 REALM_TEMPEX3(return find, cond, act_ReturnFirst, m_width,
640 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
642 else if (action == act_Sum) {
643 REALM_TEMPEX3(return find, cond, act_Sum, m_width,
644 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
646 else if (action == act_Min) {
647 REALM_TEMPEX3(return find, cond, act_Min, m_width,
648 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
650 else if (action == act_Max) {
651 REALM_TEMPEX3(return find, cond, act_Max, m_width,
652 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
654 else if (action == act_Count) {
655 REALM_TEMPEX3(return find, cond, act_Count, m_width,
656 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
658 else if (action == act_FindAll) {
659 REALM_TEMPEX3(return find, cond, act_FindAll, m_width,
660 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
662 else if (action == act_CallbackIdx) {
663 REALM_TEMPEX3(return find, cond, act_CallbackIdx, m_width,
664 (value, start, end, baseindex, state, CallbackDummy(), nullable_array, find_null))
666 REALM_ASSERT_DEBUG(false);
672 bool find(int cond, Action action, null, size_t start, size_t end, size_t baseindex,
673 QueryState<int64_t>* state) const;
676 template <class cond, Action action, size_t bitwidth, class Callback>
677 bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
678 Callback callback, bool nullable_array = false, bool find_null = false) const;
680 // This is the one installed into the m_vtable->finder slots.
681 template <class cond, Action action, size_t bitwidth>
682 bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state) const;
684 template <class cond, Action action, class Callback>
685 bool find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
686 Callback callback, bool nullable_array = false, bool find_null = false) const;
689 template <class cond, Action action, class Callback>
690 bool find(null, size_t start, size_t end, size_t baseindex,
691 QueryState<int64_t>* state, Callback callback) const;
694 // Optimized implementation for release mode
695 template <class cond, Action action, size_t bitwidth, class Callback>
696 bool find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
697 Callback callback, bool nullable_array = false, bool find_null = false) const;
699 // Called for each search result
700 template <Action action, class Callback>
701 bool find_action(size_t index, util::Optional<int64_t> value, QueryState<int64_t>* state,
702 Callback callback) const;
704 template <Action action, class Callback>
705 bool find_action_pattern(size_t index, uint64_t pattern, QueryState<int64_t>* state, Callback callback) const;
707 // Wrappers for backwards compatibility and for simple use without
708 // setting up state initialization etc
709 template <class cond>
710 size_t find_first(int64_t value, size_t start = 0, size_t end = size_t(-1)) const;
712 void find_all(IntegerColumn* result, int64_t value, size_t col_offset = 0, size_t begin = 0,
713 size_t end = size_t(-1)) const;
715 size_t find_first(int64_t value, size_t begin = 0, size_t end = size_t(-1)) const;
717 // Non-SSE find for the four functions Equal/NotEqual/Less/Greater
718 template <class cond, Action action, size_t bitwidth, class Callback>
719 bool compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
720 Callback callback) const;
722 // Non-SSE find for Equal/NotEqual
723 template <bool eq, Action action, size_t width, class Callback>
724 inline bool compare_equality(int64_t value, size_t start, size_t end, size_t baseindex,
725 QueryState<int64_t>* state, Callback callback) const;
727 // Non-SSE find for Less/Greater
728 template <bool gt, Action action, size_t bitwidth, class Callback>
729 bool compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
730 Callback callback) const;
732 template <class cond, Action action, size_t foreign_width, class Callback, size_t width>
733 bool compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
734 Callback callback) const;
736 template <class cond, Action action, class Callback, size_t bitwidth, size_t foreign_bitwidth>
737 bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
738 Callback callback) const;
740 template <class cond, Action action, class Callback>
741 bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
742 Callback callback) const;
744 template <class cond, Action action, size_t width, class Callback>
745 bool compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
746 Callback callback) const;
748 // SSE find for the four functions Equal/NotEqual/Less/Greater
749 #ifdef REALM_COMPILER_SSE
750 template <class cond, Action action, size_t width, class Callback>
751 bool find_sse(int64_t value, __m128i* data, size_t items, QueryState<int64_t>* state, size_t baseindex,
752 Callback callback) const;
754 template <class cond, Action action, size_t width, class Callback>
755 REALM_FORCEINLINE bool find_sse_intern(__m128i* action_data, __m128i* data, size_t items,
756 QueryState<int64_t>* state, size_t baseindex, Callback callback) const;
760 template <size_t width>
761 inline bool test_zero(uint64_t value) const; // Tests value for 0-elements
763 template <bool eq, size_t width>
764 size_t find_zero(uint64_t v) const; // Finds position of 0/non-zero element
766 template <size_t width, bool zero>
767 uint64_t cascade(uint64_t a) const; // Sets lowermost bits of zero or non-zero elements
769 template <bool gt, size_t width>
771 find_gtlt_magic(int64_t v) const; // Compute magic constant needed for searching for value 'v' using bit hacks
773 template <size_t width>
774 inline int64_t lower_bits() const; // Return chunk with lower bit set in each element
776 size_t first_set_bit(unsigned int v) const;
777 size_t first_set_bit64(int64_t v) const;
780 int64_t get_universal(const char* const data, const size_t ndx) const;
782 // Find value greater/less in 64-bit chunk - only works for positive values
783 template <bool gt, Action action, size_t width, class Callback>
784 bool find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryState<int64_t>* state, size_t baseindex,
785 Callback callback) const;
787 // Find value greater/less in 64-bit chunk - no constraints
788 template <bool gt, Action action, size_t width, class Callback>
789 bool find_gtlt(int64_t v, uint64_t chunk, QueryState<int64_t>* state, size_t baseindex, Callback callback) const;
791 ref_type bptree_leaf_insert(size_t ndx, int64_t, TreeInsertBase& state);
793 /// Get the specified element without the cost of constructing an
794 /// array instance. If an array instance is already available, or
795 /// you need to get multiple values, then this method will be
797 static int_fast64_t get(const char* header, size_t ndx) noexcept;
799 /// Like get(const char*, size_t) but gets two consecutive
801 static std::pair<int64_t, int64_t> get_two(const char* header, size_t ndx) noexcept;
803 static void get_three(const char* data, size_t ndx, ref_type& v0, ref_type& v1, ref_type& v2) noexcept;
805 /// The meaning of 'width' depends on the context in which this
807 size_t get_width() const noexcept
812 static char* get_data_from_header(char*) noexcept;
813 static char* get_header_from_data(char*) noexcept;
814 static const char* get_data_from_header(const char*) noexcept;
822 static bool get_is_inner_bptree_node_from_header(const char*) noexcept;
823 static bool get_hasrefs_from_header(const char*) noexcept;
824 static bool get_context_flag_from_header(const char*) noexcept;
825 static WidthType get_wtype_from_header(const char*) noexcept;
826 static uint_least8_t get_width_from_header(const char*) noexcept;
827 static size_t get_size_from_header(const char*) noexcept;
829 static Type get_type_from_header(const char*) noexcept;
831 /// Get the number of bytes currently in use by this array. This
832 /// includes the array header, but it does not include allocated
833 /// bytes corresponding to excess capacity. The result is
834 /// guaranteed to be a multiple of 8 (i.e., 64-bit aligned).
836 /// This number is exactly the number of bytes that will be
837 /// written by a non-recursive invocation of write().
838 size_t get_byte_size() const noexcept;
840 /// Get the maximum number of bytes that can be written by a
841 /// non-recursive invocation of write() on an array with the
842 /// specified number of elements, that is, the maximum value that
843 /// can be returned by get_byte_size().
844 static size_t get_max_byte_size(size_t num_elems) noexcept;
846 /// FIXME: Belongs in IntegerArray
847 static size_t calc_aligned_byte_size(size_t size, int width);
849 class MemUsageHandler {
851 virtual void handle(ref_type ref, size_t allocated, size_t used) = 0;
854 void report_memory_usage(MemUsageHandler&) const;
856 void stats(MemStats& stats_dest) const noexcept;
861 typedef size_t (*LeafVerifier)(MemRef, Allocator&);
862 void verify_bptree(LeafVerifier) const;
863 typedef void (*LeafDumper)(MemRef, Allocator&, std::ostream&, int level);
864 void dump_bptree_structure(std::ostream&, int level, LeafDumper) const;
865 void to_dot(std::ostream&, StringData title = StringData()) const;
868 virtual void to_dot(MemRef leaf_mem, ArrayParent*, size_t ndx_in_parent, std::ostream&) = 0;
873 void bptree_to_dot(std::ostream&, ToDotHandler&) const;
874 void to_dot_parent_edge(std::ostream&) const;
877 static const int header_size = 8; // Number of bytes used by header
879 // The encryption layer relies on headers always fitting within a single page.
880 static_assert(header_size == 8, "Header must always fit in entirely on a page");
882 Array& operator=(const Array&) = delete; // not allowed
883 Array(const Array&) = delete; // not allowed
885 typedef bool (*CallbackDummy)(int64_t);
888 // Includes array header. Not necessarily 8-byte aligned.
889 virtual size_t calc_byte_len(size_t num_items, size_t width) const;
891 virtual size_t calc_item_count(size_t bytes, size_t width) const noexcept;
893 bool get_is_inner_bptree_node_from_header() const noexcept;
894 bool get_hasrefs_from_header() const noexcept;
895 bool get_context_flag_from_header() const noexcept;
896 WidthType get_wtype_from_header() const noexcept;
897 uint_least8_t get_width_from_header() const noexcept;
898 size_t get_size_from_header() const noexcept;
900 // Undefined behavior if m_alloc.is_read_only(m_ref) returns true
901 size_t get_capacity_from_header() const noexcept;
903 void set_header_is_inner_bptree_node(bool value) noexcept;
904 void set_header_hasrefs(bool value) noexcept;
905 void set_header_context_flag(bool value) noexcept;
906 void set_header_wtype(WidthType value) noexcept;
907 void set_header_width(int value) noexcept;
908 void set_header_size(size_t value) noexcept;
909 void set_header_capacity(size_t value) noexcept;
911 static void set_header_is_inner_bptree_node(bool value, char* header) noexcept;
912 static void set_header_hasrefs(bool value, char* header) noexcept;
913 static void set_header_context_flag(bool value, char* header) noexcept;
914 static void set_header_wtype(WidthType value, char* header) noexcept;
915 static void set_header_width(int value, char* header) noexcept;
916 static void set_header_size(size_t value, char* header) noexcept;
917 static void set_header_capacity(size_t value, char* header) noexcept;
919 static void init_header(char* header, bool is_inner_bptree_node, bool has_refs, bool context_flag,
920 WidthType width_type, int width, size_t size, size_t capacity) noexcept;
923 // This returns the minimum value ("lower bound") of the representable values
924 // for the given bit width. Valid widths are 0, 1, 2, 4, 8, 16, 32, and 64.
925 template <size_t width>
926 static int_fast64_t lbound_for_width() noexcept;
928 static int_fast64_t lbound_for_width(size_t width) noexcept;
930 // This returns the maximum value ("inclusive upper bound") of the representable values
931 // for the given bit width. Valid widths are 0, 1, 2, 4, 8, 16, 32, and 64.
932 template <size_t width>
933 static int_fast64_t ubound_for_width() noexcept;
935 static int_fast64_t ubound_for_width(size_t width) noexcept;
937 template <size_t width>
938 void set_width() noexcept;
939 void set_width(size_t) noexcept;
940 void alloc(size_t init_size, size_t width);
941 void copy_on_write();
944 void do_copy_on_write(size_t minimum_size = 0);
945 void do_ensure_minimum_width(int_fast64_t);
948 int64_t sum(size_t start, size_t end) const;
950 template <bool max, size_t w>
951 bool minmax(int64_t& result, size_t start, size_t end, size_t* return_ndx) const;
954 size_t find_gte(const int64_t target, size_t start, size_t end) const;
957 size_t adjust_ge(size_t start, size_t end, int_fast64_t limit, int_fast64_t diff);
960 /// The total size in bytes (including the header) of a new empty
961 /// array. Must be a multiple of 8 (i.e., 64-bit aligned).
962 static const size_t initial_capacity = 128;
964 /// It is an error to specify a non-zero value unless the width
965 /// type is wtype_Bits. It is also an error to specify a non-zero
966 /// size if the width type is wtype_Ignore.
967 static MemRef create(Type, bool context_flag, WidthType, size_t size, int_fast64_t value, Allocator&);
969 static MemRef clone(MemRef header, Allocator& alloc, Allocator& target_alloc);
971 /// Get the address of the header of this array.
972 char* get_header() noexcept;
974 /// Same as get_byte_size().
975 static size_t get_byte_size_from_header(const char*) noexcept;
977 // Undefined behavior if array is in immutable memory
978 static size_t get_capacity_from_header(const char*) noexcept;
980 // Overriding method in ArrayParent
981 void update_child_ref(size_t, ref_type) override;
983 // Overriding method in ArrayParent
984 ref_type get_child_ref(size_t) const noexcept override;
986 void destroy_children(size_t offset = 0) noexcept;
988 std::pair<ref_type, size_t> get_to_dot_parent(size_t ndx_in_parent) const override;
990 bool is_read_only() const noexcept;
993 // Getters and Setters for adaptive-packed arrays
994 typedef int64_t (Array::*Getter)(size_t) const; // Note: getters must not throw
995 typedef void (Array::*Setter)(size_t, int64_t);
996 typedef bool (Array::*Finder)(int64_t, size_t, size_t, size_t, QueryState<int64_t>*) const;
997 typedef void (Array::*ChunkGetter)(size_t, int64_t res[8]) const; // Note: getters must not throw
1001 ChunkGetter chunk_getter;
1003 Finder finder[cond_VTABLE_FINDER_COUNT]; // one for each active function pointer
1006 struct VTableForWidth;
1009 /// Takes a 64-bit value and returns the minimum number of bits needed
1010 /// to fit the value. For alignment this is rounded up to nearest
1011 /// log2. Posssible results {0, 1, 2, 4, 8, 16, 32, 64}
1012 static size_t bit_width(int64_t value);
1014 void report_memory_usage_2(MemUsageHandler&) const;
1017 Getter m_getter = nullptr; // cached to avoid indirection
1018 const VTable* m_vtable = nullptr;
1021 // FIXME: Should not be public
1022 char* m_data = nullptr; // Points to first byte after header
1024 #if REALM_ENABLE_MEMDEBUG
1025 // If m_no_relocation is false, then copy_on_write() will always relocate this array, regardless if it's
1026 // required or not. If it's true, then it will never relocate, which is currently only expeted inside
1027 // GroupWriter::write_group() due to a unique chicken/egg problem (see description there).
1028 bool m_no_relocation = false;
1032 int64_t m_lbound; // min number that can be stored with current m_width
1033 int64_t m_ubound; // max number that can be stored with current m_width
1035 size_t m_size = 0; // Number of elements currently stored.
1036 size_t m_capacity = 0; // Number of elements that fit inside the allocated memory.
1042 ArrayParent* m_parent = nullptr;
1043 size_t m_ndx_in_parent = 0; // Ignored if m_parent is null.
1046 uint_least8_t m_width = 0; // Size of an element (meaning depend on type of array).
1047 bool m_is_inner_bptree_node; // This array is an inner node of B+-tree.
1048 bool m_has_refs; // Elements whose first bit is zero are refs to subarrays.
1049 bool m_context_flag; // Meaning depends on context.
1052 ref_type do_write_shallow(_impl::ArrayWriterBase&) const;
1053 ref_type do_write_deep(_impl::ArrayWriterBase&, bool only_if_modified) const;
1054 static size_t calc_byte_size(WidthType wtype, size_t size, uint_least8_t width) noexcept;
1056 friend class SlabAlloc;
1057 friend class GroupWriter;
1058 friend class StringColumn;
1064 class QueryStateBase {
1065 virtual void dyncast()
1071 class QueryState<int64_t> : public QueryStateBase {
1074 size_t m_match_count;
1076 size_t m_minmax_index; // used only for min/max, to save index of current min/max value
1078 template <Action action>
1081 if (action == act_Max || action == act_Min || action == act_Sum)
1087 void init(Action action, IntegerColumn* akku, size_t limit)
1091 m_minmax_index = not_found;
1093 if (action == act_Max)
1094 m_state = -0x7fffffffffffffffLL - 1LL;
1095 else if (action == act_Min)
1096 m_state = 0x7fffffffffffffffLL;
1097 else if (action == act_ReturnFirst)
1098 m_state = not_found;
1099 else if (action == act_Sum)
1101 else if (action == act_Count)
1103 else if (action == act_FindAll)
1104 m_state = reinterpret_cast<int64_t>(akku);
1105 else if (action == act_CallbackIdx) {
1108 REALM_ASSERT_DEBUG(false);
1112 template <Action action, bool pattern>
1113 inline bool match(size_t index, uint64_t indexpattern, int64_t value)
1116 if (action == act_Count) {
1117 // If we are close to 'limit' argument in query, we cannot count-up a complete chunk. Count up single
1119 if (m_match_count + 64 >= m_limit)
1122 m_state += fast_popcount64(indexpattern);
1123 m_match_count = size_t(m_state);
1126 // Other aggregates cannot (yet) use bit pattern for anything. Make Array-finder call with pattern = false
1133 if (action == act_Max) {
1134 if (value > m_state) {
1136 m_minmax_index = index;
1139 else if (action == act_Min) {
1140 if (value < m_state) {
1142 m_minmax_index = index;
1145 else if (action == act_Sum)
1147 else if (action == act_Count) {
1149 m_match_count = size_t(m_state);
1151 else if (action == act_FindAll) {
1152 Array::add_to_column(reinterpret_cast<IntegerColumn*>(m_state), index);
1154 else if (action == act_ReturnFirst) {
1159 REALM_ASSERT_DEBUG(false);
1161 return (m_limit > m_match_count);
1164 template <Action action, bool pattern>
1165 inline bool match(size_t index, uint64_t indexpattern, util::Optional<int64_t> value)
1167 // FIXME: This is a temporary hack for nullable integers.
1169 return match<action, pattern>(index, indexpattern, *value);
1172 // If value is null, the only sensible actions are count, find_all, and return first.
1173 // Max, min, and sum should all have no effect.
1174 if (action == act_Count) {
1176 m_match_count = size_t(m_state);
1178 else if (action == act_FindAll) {
1179 Array::add_to_column(reinterpret_cast<IntegerColumn*>(m_state), index);
1181 else if (action == act_ReturnFirst) {
1186 return m_limit > m_match_count;
1190 // Used only for Basic-types: currently float and double
1192 class QueryState : public QueryStateBase {
1195 size_t m_match_count;
1197 size_t m_minmax_index; // used only for min/max, to save index of current min/max value
1199 template <Action action>
1202 return (action == act_Max || action == act_Min || action == act_Sum || action == act_Count);
1205 void init(Action action, Array*, size_t limit)
1207 REALM_ASSERT((std::is_same<R, float>::value || std::is_same<R, double>::value));
1210 m_minmax_index = not_found;
1212 if (action == act_Max)
1213 m_state = -std::numeric_limits<R>::infinity();
1214 else if (action == act_Min)
1215 m_state = std::numeric_limits<R>::infinity();
1216 else if (action == act_Sum)
1219 REALM_ASSERT_DEBUG(false);
1223 template <Action action, bool pattern, typename resulttype>
1224 inline bool match(size_t index, uint64_t /*indexpattern*/, resulttype value)
1229 static_assert(action == act_Sum || action == act_Max || action == act_Min || action == act_Count,
1230 "Search action not supported");
1232 if (action == act_Count) {
1235 else if (!null::is_null_float(value)) {
1237 if (action == act_Max) {
1238 if (value > m_state) {
1240 m_minmax_index = index;
1243 else if (action == act_Min) {
1244 if (value < m_state) {
1246 m_minmax_index = index;
1249 else if (action == act_Sum)
1252 REALM_ASSERT_DEBUG(false);
1256 return (m_limit > m_match_count);
1260 inline bool RefOrTagged::is_ref() const noexcept
1262 return (m_value & 1) == 0;
1265 inline bool RefOrTagged::is_tagged() const noexcept
1270 inline ref_type RefOrTagged::get_as_ref() const noexcept
1272 // to_ref() is defined in <alloc.hpp>
1273 return to_ref(m_value);
1276 inline uint_fast64_t RefOrTagged::get_as_int() const noexcept
1278 // The bitwise AND is there in case uint_fast64_t is wider than 64 bits.
1279 return (uint_fast64_t(m_value) & 0xFFFFFFFFFFFFFFFFULL) >> 1;
1282 inline RefOrTagged RefOrTagged::make_ref(ref_type ref) noexcept
1284 // from_ref() is defined in <alloc.hpp>
1285 int_fast64_t value = from_ref(ref);
1286 return RefOrTagged(value);
1289 inline RefOrTagged RefOrTagged::make_tagged(uint_fast64_t i) noexcept
1291 REALM_ASSERT(i < (1ULL << 63));
1292 int_fast64_t value = util::from_twos_compl<int_fast64_t>((i << 1) | 1);
1293 return RefOrTagged(value);
1296 inline RefOrTagged::RefOrTagged(int_fast64_t value) noexcept
1301 inline Array::Array(Allocator& allocator) noexcept
1302 : m_alloc(allocator)
1306 inline void Array::create(Type type, bool context_flag, size_t length, int_fast64_t value)
1308 MemRef mem = create_array(type, context_flag, length, value, m_alloc); // Throws
1313 inline void Array::init_from_ref(ref_type ref) noexcept
1315 REALM_ASSERT_DEBUG(ref);
1316 char* header = m_alloc.translate(ref);
1317 init_from_mem(MemRef(header, ref, m_alloc));
1321 inline void Array::init_from_parent() noexcept
1323 ref_type ref = get_ref_from_parent();
1328 inline Array::Type Array::get_type() const noexcept
1330 if (m_is_inner_bptree_node) {
1331 REALM_ASSERT_DEBUG(m_has_refs);
1332 return type_InnerBptreeNode;
1335 return type_HasRefs;
1340 inline void Array::get_chunk(size_t ndx, int64_t res[8]) const noexcept
1342 REALM_ASSERT_DEBUG(ndx < m_size);
1343 (this->*(m_vtable->chunk_getter))(ndx, res);
1347 inline int64_t Array::get(size_t ndx) const noexcept
1349 REALM_ASSERT_DEBUG(is_attached());
1350 REALM_ASSERT_DEBUG(ndx < m_size);
1351 return (this->*m_getter)(ndx);
1353 // Two ideas that are not efficient but may be worth looking into again:
1355 // Assume correct width is found early in REALM_TEMPEX, which is the case for B tree offsets that
1356 // are probably either 2^16 long. Turns out to be 25% faster if found immediately, but 50-300% slower
1358 REALM_TEMPEX(return get, (ndx));
1361 // Slightly slower in both of the if-cases. Also needs an matchcount m_size check too, to avoid
1362 // reading beyond array.
1363 if (m_width >= 8 && m_size > ndx + 7)
1364 return get<64>(ndx >> m_shift) & m_widthmask;
1366 return (this->*(m_vtable->getter))(ndx);
1370 inline int64_t Array::front() const noexcept
1375 inline int64_t Array::back() const noexcept
1377 return get(m_size - 1);
1380 inline ref_type Array::get_as_ref(size_t ndx) const noexcept
1382 REALM_ASSERT_DEBUG(is_attached());
1383 REALM_ASSERT_DEBUG(m_has_refs);
1384 int64_t v = get(ndx);
1388 inline RefOrTagged Array::get_as_ref_or_tagged(size_t ndx) const noexcept
1390 REALM_ASSERT(has_refs());
1391 return RefOrTagged(get(ndx));
1394 inline void Array::set(size_t ndx, RefOrTagged ref_or_tagged)
1396 REALM_ASSERT(has_refs());
1397 set(ndx, ref_or_tagged.m_value); // Throws
1400 inline void Array::add(RefOrTagged ref_or_tagged)
1402 REALM_ASSERT(has_refs());
1403 add(ref_or_tagged.m_value); // Throws
1406 inline void Array::ensure_minimum_width(RefOrTagged ref_or_tagged)
1408 REALM_ASSERT(has_refs());
1409 ensure_minimum_width(ref_or_tagged.m_value); // Throws
1412 inline bool Array::is_inner_bptree_node() const noexcept
1414 return m_is_inner_bptree_node;
1417 inline bool Array::has_refs() const noexcept
1422 inline void Array::set_has_refs(bool value) noexcept
1424 if (m_has_refs != value) {
1425 REALM_ASSERT(!is_read_only());
1427 set_header_hasrefs(value);
1431 inline bool Array::get_context_flag() const noexcept
1433 return m_context_flag;
1436 inline void Array::set_context_flag(bool value) noexcept
1438 if (m_context_flag != value) {
1439 REALM_ASSERT(!is_read_only());
1440 m_context_flag = value;
1441 set_header_context_flag(value);
1445 inline ref_type Array::get_ref() const noexcept
1450 inline MemRef Array::get_mem() const noexcept
1452 return MemRef(get_header_from_data(m_data), m_ref, m_alloc);
1455 inline void Array::destroy() noexcept
1459 char* header = get_header_from_data(m_data);
1460 m_alloc.free_(m_ref, header);
1464 inline void Array::destroy_deep() noexcept
1472 char* header = get_header_from_data(m_data);
1473 m_alloc.free_(m_ref, header);
1477 inline ref_type Array::write(_impl::ArrayWriterBase& out, bool deep, bool only_if_modified) const
1479 REALM_ASSERT(is_attached());
1481 if (only_if_modified && m_alloc.is_read_only(m_ref))
1484 if (!deep || !m_has_refs)
1485 return do_write_shallow(out); // Throws
1487 return do_write_deep(out, only_if_modified); // Throws
1490 inline ref_type Array::write(ref_type ref, Allocator& alloc, _impl::ArrayWriterBase& out, bool only_if_modified)
1492 if (only_if_modified && alloc.is_read_only(ref))
1496 array.init_from_ref(ref);
1498 if (!array.m_has_refs)
1499 return array.do_write_shallow(out); // Throws
1501 return array.do_write_deep(out, only_if_modified); // Throws
1504 inline void Array::add(int_fast64_t value)
1506 insert(m_size, value);
1509 inline void Array::erase(size_t ndx)
1511 // This can throw, but only if array is currently in read-only
1513 move(ndx + 1, size(), ndx);
1515 // Update size (also in header)
1517 set_header_size(m_size);
1521 inline void Array::erase(size_t begin, size_t end)
1524 // This can throw, but only if array is currently in read-only memory.
1525 move(end, size(), begin); // Throws
1527 // Update size (also in header)
1528 m_size -= end - begin;
1529 set_header_size(m_size);
1533 inline void Array::clear()
1535 truncate(0); // Throws
1538 inline void Array::clear_and_destroy_children()
1540 truncate_and_destroy_children(0);
1543 inline void Array::destroy(ref_type ref, Allocator& alloc) noexcept
1545 destroy(MemRef(ref, alloc), alloc);
1548 inline void Array::destroy(MemRef mem, Allocator& alloc) noexcept
1553 inline void Array::destroy_deep(ref_type ref, Allocator& alloc) noexcept
1555 destroy_deep(MemRef(ref, alloc), alloc);
1558 inline void Array::destroy_deep(MemRef mem, Allocator& alloc) noexcept
1560 if (!get_hasrefs_from_header(mem.get_addr())) {
1565 array.init_from_mem(mem);
1566 array.destroy_deep();
1570 inline void Array::adjust(size_t ndx, int_fast64_t diff)
1572 REALM_ASSERT_3(ndx, <=, m_size);
1574 // FIXME: Should be optimized
1575 int_fast64_t v = get(ndx);
1576 set(ndx, int64_t(v + diff)); // Throws
1580 inline void Array::adjust(size_t begin, size_t end, int_fast64_t diff)
1583 // FIXME: Should be optimized
1584 for (size_t i = begin; i != end; ++i)
1585 adjust(i, diff); // Throws
1590 //-------------------------------------------------
1592 inline bool Array::get_is_inner_bptree_node_from_header(const char* header) noexcept
1594 typedef unsigned char uchar;
1595 const uchar* h = reinterpret_cast<const uchar*>(header);
1596 return (int(h[4]) & 0x80) != 0;
1598 inline bool Array::get_hasrefs_from_header(const char* header) noexcept
1600 typedef unsigned char uchar;
1601 const uchar* h = reinterpret_cast<const uchar*>(header);
1602 return (int(h[4]) & 0x40) != 0;
1604 inline bool Array::get_context_flag_from_header(const char* header) noexcept
1606 typedef unsigned char uchar;
1607 const uchar* h = reinterpret_cast<const uchar*>(header);
1608 return (int(h[4]) & 0x20) != 0;
1610 inline Array::WidthType Array::get_wtype_from_header(const char* header) noexcept
1612 typedef unsigned char uchar;
1613 const uchar* h = reinterpret_cast<const uchar*>(header);
1614 return WidthType((int(h[4]) & 0x18) >> 3);
1616 inline uint_least8_t Array::get_width_from_header(const char* header) noexcept
1618 typedef unsigned char uchar;
1619 const uchar* h = reinterpret_cast<const uchar*>(header);
1620 return uint_least8_t((1 << (int(h[4]) & 0x07)) >> 1);
1622 inline size_t Array::get_size_from_header(const char* header) noexcept
1624 typedef unsigned char uchar;
1625 const uchar* h = reinterpret_cast<const uchar*>(header);
1626 return (size_t(h[5]) << 16) + (size_t(h[6]) << 8) + h[7];
1628 inline size_t Array::get_capacity_from_header(const char* header) noexcept
1630 typedef unsigned char uchar;
1631 const uchar* h = reinterpret_cast<const uchar*>(header);
1632 return (size_t(h[0]) << 16) + (size_t(h[1]) << 8) + h[2];
1636 inline char* Array::get_data_from_header(char* header) noexcept
1638 return header + header_size;
1640 inline char* Array::get_header_from_data(char* data) noexcept
1642 return data - header_size;
1644 inline const char* Array::get_data_from_header(const char* header) noexcept
1646 return get_data_from_header(const_cast<char*>(header));
1650 inline bool Array::get_is_inner_bptree_node_from_header() const noexcept
1652 return get_is_inner_bptree_node_from_header(get_header_from_data(m_data));
1654 inline bool Array::get_hasrefs_from_header() const noexcept
1656 return get_hasrefs_from_header(get_header_from_data(m_data));
1658 inline bool Array::get_context_flag_from_header() const noexcept
1660 return get_context_flag_from_header(get_header_from_data(m_data));
1662 inline Array::WidthType Array::get_wtype_from_header() const noexcept
1664 return get_wtype_from_header(get_header_from_data(m_data));
1666 inline uint_least8_t Array::get_width_from_header() const noexcept
1668 return get_width_from_header(get_header_from_data(m_data));
1670 inline size_t Array::get_size_from_header() const noexcept
1672 return get_size_from_header(get_header_from_data(m_data));
1674 inline size_t Array::get_capacity_from_header() const noexcept
1676 return get_capacity_from_header(get_header_from_data(m_data));
1680 inline void Array::set_header_is_inner_bptree_node(bool value, char* header) noexcept
1682 typedef unsigned char uchar;
1683 uchar* h = reinterpret_cast<uchar*>(header);
1684 h[4] = uchar((int(h[4]) & ~0x80) | int(value) << 7);
1687 inline void Array::set_header_hasrefs(bool value, char* header) noexcept
1689 typedef unsigned char uchar;
1690 uchar* h = reinterpret_cast<uchar*>(header);
1691 h[4] = uchar((int(h[4]) & ~0x40) | int(value) << 6);
1694 inline void Array::set_header_context_flag(bool value, char* header) noexcept
1696 typedef unsigned char uchar;
1697 uchar* h = reinterpret_cast<uchar*>(header);
1698 h[4] = uchar((int(h[4]) & ~0x20) | int(value) << 5);
1701 inline void Array::set_header_wtype(WidthType value, char* header) noexcept
1703 // Indicates how to calculate size in bytes based on width
1704 // 0: bits (width/8) * size
1705 // 1: multiply width * size
1706 // 2: ignore 1 * size
1707 typedef unsigned char uchar;
1708 uchar* h = reinterpret_cast<uchar*>(header);
1709 h[4] = uchar((int(h[4]) & ~0x18) | int(value) << 3);
1712 inline void Array::set_header_width(int value, char* header) noexcept
1714 // Pack width in 3 bits (log2)
1720 REALM_ASSERT_3(w, <, 8);
1722 typedef unsigned char uchar;
1723 uchar* h = reinterpret_cast<uchar*>(header);
1724 h[4] = uchar((int(h[4]) & ~0x7) | w);
1727 inline void Array::set_header_size(size_t value, char* header) noexcept
1729 REALM_ASSERT_3(value, <=, max_array_payload);
1730 typedef unsigned char uchar;
1731 uchar* h = reinterpret_cast<uchar*>(header);
1732 h[5] = uchar((value >> 16) & 0x000000FF);
1733 h[6] = uchar((value >> 8) & 0x000000FF);
1734 h[7] = uchar(value & 0x000000FF);
1737 // Note: There is a copy of this function is test_alloc.cpp
1738 inline void Array::set_header_capacity(size_t value, char* header) noexcept
1740 REALM_ASSERT_3(value, <=, max_array_payload);
1741 typedef unsigned char uchar;
1742 uchar* h = reinterpret_cast<uchar*>(header);
1743 h[0] = uchar((value >> 16) & 0x000000FF);
1744 h[1] = uchar((value >> 8) & 0x000000FF);
1745 h[2] = uchar(value & 0x000000FF);
1749 inline void Array::set_header_is_inner_bptree_node(bool value) noexcept
1751 set_header_is_inner_bptree_node(value, get_header_from_data(m_data));
1753 inline void Array::set_header_hasrefs(bool value) noexcept
1755 set_header_hasrefs(value, get_header_from_data(m_data));
1757 inline void Array::set_header_context_flag(bool value) noexcept
1759 set_header_context_flag(value, get_header_from_data(m_data));
1761 inline void Array::set_header_wtype(WidthType value) noexcept
1763 set_header_wtype(value, get_header_from_data(m_data));
1765 inline void Array::set_header_width(int value) noexcept
1767 set_header_width(value, get_header_from_data(m_data));
1769 inline void Array::set_header_size(size_t value) noexcept
1771 set_header_size(value, get_header_from_data(m_data));
1773 inline void Array::set_header_capacity(size_t value) noexcept
1775 set_header_capacity(value, get_header_from_data(m_data));
1779 inline Array::Type Array::get_type_from_header(const char* header) noexcept
1781 if (get_is_inner_bptree_node_from_header(header))
1782 return type_InnerBptreeNode;
1783 if (get_hasrefs_from_header(header))
1784 return type_HasRefs;
1789 inline char* Array::get_header() noexcept
1791 return get_header_from_data(m_data);
1794 inline size_t Array::calc_byte_size(WidthType wtype, size_t size, uint_least8_t width) noexcept
1796 size_t num_bytes = 0;
1799 // Current assumption is that size is at most 2^24 and that width is at most 64.
1800 // In that case the following will never overflow. (Assuming that size_t is at least 32 bits)
1801 REALM_ASSERT_3(size, <, 0x1000000);
1802 size_t num_bits = size * width;
1803 num_bytes = (num_bits + 7) >> 3;
1806 case wtype_Multiply: {
1807 num_bytes = size * width;
1815 // Ensure 8-byte alignment
1816 num_bytes = (num_bytes + 7) & ~size_t(7);
1818 num_bytes += header_size;
1823 inline size_t Array::get_byte_size() const noexcept
1825 const char* header = get_header_from_data(m_data);
1826 WidthType wtype = get_wtype_from_header(header);
1827 size_t num_bytes = calc_byte_size(wtype, m_size, m_width);
1829 REALM_ASSERT_7(m_alloc.is_read_only(m_ref), ==, true, ||, num_bytes, <=, get_capacity_from_header(header));
1835 inline size_t Array::get_byte_size_from_header(const char* header) noexcept
1837 size_t size = get_size_from_header(header);
1838 uint_least8_t width = get_width_from_header(header);
1839 WidthType wtype = get_wtype_from_header(header);
1840 size_t num_bytes = calc_byte_size(wtype, size, width);
1846 inline void Array::init_header(char* header, bool is_inner_bptree_node, bool has_refs, bool context_flag,
1847 WidthType width_type, int width, size_t size, size_t capacity) noexcept
1849 // Note: Since the header layout contains unallocated bit and/or
1850 // bytes, it is important that we put the entire header into a
1851 // well defined state initially.
1852 std::fill(header, header + header_size, 0);
1853 set_header_is_inner_bptree_node(is_inner_bptree_node, header);
1854 set_header_hasrefs(has_refs, header);
1855 set_header_context_flag(context_flag, header);
1856 set_header_wtype(width_type, header);
1857 set_header_width(width, header);
1858 set_header_size(size, header);
1859 set_header_capacity(capacity, header);
1863 //-------------------------------------------------
1865 inline MemRef Array::clone_deep(Allocator& target_alloc) const
1867 char* header = get_header_from_data(m_data);
1868 return clone(MemRef(header, m_ref, m_alloc), m_alloc, target_alloc); // Throws
1871 inline MemRef Array::create_empty_array(Type type, bool context_flag, Allocator& alloc)
1874 int_fast64_t value = 0;
1875 return create_array(type, context_flag, size, value, alloc); // Throws
1878 inline MemRef Array::create_array(Type type, bool context_flag, size_t size, int_fast64_t value, Allocator& alloc)
1880 return create(type, context_flag, wtype_Bits, size, value, alloc); // Throws
1883 inline bool Array::has_parent() const noexcept
1885 return m_parent != nullptr;
1888 inline ArrayParent* Array::get_parent() const noexcept
1893 inline void Array::set_parent(ArrayParent* parent, size_t ndx_in_parent) noexcept
1896 m_ndx_in_parent = ndx_in_parent;
1899 inline size_t Array::get_ndx_in_parent() const noexcept
1901 return m_ndx_in_parent;
1904 inline void Array::set_ndx_in_parent(size_t ndx) noexcept
1906 m_ndx_in_parent = ndx;
1909 inline void Array::adjust_ndx_in_parent(int diff) noexcept
1911 // Note that `diff` is promoted to an unsigned type, and that
1912 // C++03 still guarantees the expected result regardless of the
1913 // sizes of `int` and `decltype(m_ndx_in_parent)`.
1914 m_ndx_in_parent += diff;
1917 inline ref_type Array::get_ref_from_parent() const noexcept
1919 ref_type ref = m_parent->get_child_ref(m_ndx_in_parent);
1923 inline bool Array::is_attached() const noexcept
1925 return m_data != nullptr;
1928 inline void Array::detach() noexcept
1933 inline size_t Array::size() const noexcept
1935 REALM_ASSERT_DEBUG(is_attached());
1939 inline bool Array::is_empty() const noexcept
1944 inline size_t Array::get_max_byte_size(size_t num_elems) noexcept
1946 int max_bytes_per_elem = 8;
1947 return header_size + num_elems * max_bytes_per_elem;
1950 inline void Array::update_parent()
1953 m_parent->update_child_ref(m_ndx_in_parent, m_ref);
1957 inline void Array::update_child_ref(size_t child_ndx, ref_type new_ref)
1959 set(child_ndx, new_ref);
1962 inline ref_type Array::get_child_ref(size_t child_ndx) const noexcept
1964 return get_as_ref(child_ndx);
1967 inline bool Array::is_read_only() const noexcept
1969 REALM_ASSERT_DEBUG(is_attached());
1970 return m_alloc.is_read_only(m_ref);
1973 inline void Array::copy_on_write()
1975 #if REALM_ENABLE_MEMDEBUG
1976 // We want to relocate this array regardless if there is a need or not, in order to catch use-after-free bugs.
1977 // Only exception is inside GroupWriter::write_group() (see explanation at the definition of the m_no_relocation
1979 if (!m_no_relocation) {
1981 if (is_read_only()) {
1987 inline void Array::ensure_minimum_width(int_fast64_t value)
1989 if (value >= m_lbound && value <= m_ubound)
1991 do_ensure_minimum_width(value);
1995 //*************************************************************************************
1997 //*************************************************************************************
2000 int64_t Array::get(size_t ndx) const noexcept
2002 return get_universal<w>(m_data, ndx);
2006 int64_t Array::get_universal(const char* data, size_t ndx) const
2012 size_t offset = ndx >> 3;
2013 return (data[offset] >> (ndx & 7)) & 0x01;
2016 size_t offset = ndx >> 2;
2017 return (data[offset] >> ((ndx & 3) << 1)) & 0x03;
2020 size_t offset = ndx >> 1;
2021 return (data[offset] >> ((ndx & 1) << 2)) & 0x0F;
2024 return *reinterpret_cast<const signed char*>(data + ndx);
2027 size_t offset = ndx * 2;
2028 return *reinterpret_cast<const int16_t*>(data + offset);
2031 size_t offset = ndx * 4;
2032 return *reinterpret_cast<const int32_t*>(data + offset);
2035 size_t offset = ndx * 8;
2036 return *reinterpret_cast<const int64_t*>(data + offset);
2039 REALM_ASSERT_DEBUG(false);
2045 find() (calls find_optimized()) will call match() for each search result.
2048 'indexpattern' contains a 64-bit chunk of elements, each of 'width' bits in size where each element indicates a
2049 match if its lower bit is set, otherwise it indicates a non-match. 'index' tells the database row index of the
2050 first element. You must return true if you chose to 'consume' the chunk or false if not. If not, then Array-finder
2051 will afterwards call match() successive times with pattern == false.
2053 If pattern == false:
2054 'index' tells the row index of a single match and 'value' tells its value. Return false to make Array-finder break
2055 its search or return true to let it continue until 'end' or 'limit'.
2057 Array-finder decides itself if - and when - it wants to pass you an indexpattern. It depends on array bit width, match
2058 frequency, and whether the arithemetic and computations for the given search criteria makes it feasible to construct
2062 // These wrapper functions only exist to enable a possibility to make the compiler see that 'value' and/or 'index' are
2063 // unused, such that caller's computation of these values will not be made. Only works if find_action() and
2064 // find_action_pattern() rewritten as macros. Note: This problem has been fixed in next upcoming array.hpp version
2065 template <Action action, class Callback>
2066 bool Array::find_action(size_t index, util::Optional<int64_t> value, QueryState<int64_t>* state,
2067 Callback callback) const
2069 if (action == act_CallbackIdx)
2070 return callback(index);
2072 return state->match<action, false>(index, 0, value);
2074 template <Action action, class Callback>
2075 bool Array::find_action_pattern(size_t index, uint64_t pattern, QueryState<int64_t>* state, Callback callback) const
2077 static_cast<void>(callback);
2078 if (action == act_CallbackIdx) {
2079 // Possible future optimization: call callback(index) like in above find_action(), in a loop for each bit set
2083 return state->match<action, true>(index, pattern, 0);
2087 template <size_t width, bool zero>
2088 uint64_t Array::cascade(uint64_t a) const
2090 // Takes a chunk of values as argument and sets the least significant bit for each
2091 // element which is zero or non-zero, depending on the template parameter.
2092 // Example for zero=true:
2093 // width == 4 and a = 0x5fd07a107610f610
2094 // will return: 0x0001000100010001
2096 // static values needed for fast population count
2097 const uint64_t m1 = 0x5555555555555555ULL;
2100 return zero ? ~a : a;
2102 else if (width == 2) {
2103 // Masks to avoid spillover between segments in cascades
2104 const uint64_t c1 = ~0ULL / 0x3 * 0x1;
2106 a |= (a >> 1) & c1; // cascade ones in non-zeroed segments
2107 a &= m1; // isolate single bit in each segment
2109 a ^= m1; // reverse isolated bits if checking for zeroed segments
2113 else if (width == 4) {
2114 const uint64_t m = ~0ULL / 0xF * 0x1;
2116 // Masks to avoid spillover between segments in cascades
2117 const uint64_t c1 = ~0ULL / 0xF * 0x7;
2118 const uint64_t c2 = ~0ULL / 0xF * 0x3;
2120 a |= (a >> 1) & c1; // cascade ones in non-zeroed segments
2122 a &= m; // isolate single bit in each segment
2124 a ^= m; // reverse isolated bits if checking for zeroed segments
2128 else if (width == 8) {
2129 const uint64_t m = ~0ULL / 0xFF * 0x1;
2131 // Masks to avoid spillover between segments in cascades
2132 const uint64_t c1 = ~0ULL / 0xFF * 0x7F;
2133 const uint64_t c2 = ~0ULL / 0xFF * 0x3F;
2134 const uint64_t c3 = ~0ULL / 0xFF * 0x0F;
2136 a |= (a >> 1) & c1; // cascade ones in non-zeroed segments
2139 a &= m; // isolate single bit in each segment
2141 a ^= m; // reverse isolated bits if checking for zeroed segments
2145 else if (width == 16) {
2146 const uint64_t m = ~0ULL / 0xFFFF * 0x1;
2148 // Masks to avoid spillover between segments in cascades
2149 const uint64_t c1 = ~0ULL / 0xFFFF * 0x7FFF;
2150 const uint64_t c2 = ~0ULL / 0xFFFF * 0x3FFF;
2151 const uint64_t c3 = ~0ULL / 0xFFFF * 0x0FFF;
2152 const uint64_t c4 = ~0ULL / 0xFFFF * 0x00FF;
2154 a |= (a >> 1) & c1; // cascade ones in non-zeroed segments
2158 a &= m; // isolate single bit in each segment
2160 a ^= m; // reverse isolated bits if checking for zeroed segments
2165 else if (width == 32) {
2166 const uint64_t m = ~0ULL / 0xFFFFFFFF * 0x1;
2168 // Masks to avoid spillover between segments in cascades
2169 const uint64_t c1 = ~0ULL / 0xFFFFFFFF * 0x7FFFFFFF;
2170 const uint64_t c2 = ~0ULL / 0xFFFFFFFF * 0x3FFFFFFF;
2171 const uint64_t c3 = ~0ULL / 0xFFFFFFFF * 0x0FFFFFFF;
2172 const uint64_t c4 = ~0ULL / 0xFFFFFFFF * 0x00FFFFFF;
2173 const uint64_t c5 = ~0ULL / 0xFFFFFFFF * 0x0000FFFF;
2175 a |= (a >> 1) & c1; // cascade ones in non-zeroed segments
2179 a |= (a >> 16) & c5;
2180 a &= m; // isolate single bit in each segment
2182 a ^= m; // reverse isolated bits if checking for zeroed segments
2186 else if (width == 64) {
2187 return (a == 0) == zero;
2190 REALM_ASSERT_DEBUG(false);
2191 return uint64_t(-1);
2195 // This is the main finding function for Array. Other finding functions are just wrappers around this one.
2196 // Search for 'value' using condition cond (Equal, NotEqual, Less, etc) and call find_action() or
2197 // find_action_pattern() for each match. Break and return if find_action() returns false or 'end' is reached.
2199 // If nullable_array is set, then find_optimized() will treat the array is being nullable, i.e. it will skip the
2200 // first entry and compare correctly against null, etc.
2202 // If find_null is set, it means that we search for a null. In that case, `value` is ignored. If find_null is set,
2203 // then nullable_array must be set too.
2204 template <class cond, Action action, size_t bitwidth, class Callback>
2205 bool Array::find_optimized(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
2206 Callback callback, bool nullable_array, bool find_null) const
2208 REALM_ASSERT(!(find_null && !nullable_array));
2209 REALM_ASSERT_DEBUG(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end);
2211 size_t start2 = start;
2215 end = nullable_array ? size() - 1 : size();
2217 if (nullable_array) {
2218 // We were called by find() of a nullable array. So skip first entry, take nulls in count, etc, etc. Fixme:
2219 // Huge speed optimizations are possible here! This is a very simple generic method.
2220 for (; start2 < end; start2++) {
2221 int64_t v = get<bitwidth>(start2 + 1);
2222 if (c(v, value, v == get(0), find_null)) {
2223 util::Optional<int64_t> v2(v == get(0) ? util::none : util::make_optional(v));
2224 if (!find_action<action, Callback>(start2 + baseindex, v2, state, callback))
2225 return false; // tell caller to stop aggregating/search
2228 return true; // tell caller to continue aggregating/search (on next array leafs)
2232 // Test first few items with no initial time overhead
2234 if (m_size > start2 && c(get<bitwidth>(start2), value) && start2 < end) {
2235 if (!find_action<action, Callback>(start2 + baseindex, get<bitwidth>(start2), state, callback))
2241 if (m_size > start2 && c(get<bitwidth>(start2), value) && start2 < end) {
2242 if (!find_action<action, Callback>(start2 + baseindex, get<bitwidth>(start2), state, callback))
2248 if (m_size > start2 && c(get<bitwidth>(start2), value) && start2 < end) {
2249 if (!find_action<action, Callback>(start2 + baseindex, get<bitwidth>(start2), state, callback))
2255 if (m_size > start2 && c(get<bitwidth>(start2), value) && start2 < end) {
2256 if (!find_action<action, Callback>(start2 + baseindex, get<bitwidth>(start2), state, callback))
2263 if (!(m_size > start2 && start2 < end))
2266 if (end == size_t(-1))
2269 // Return immediately if no items in array can match (such as if cond == Greater && value == 100 &&
2271 if (!c.can_match(value, m_lbound, m_ubound))
2274 // optimization if all items are guaranteed to match (such as cond == NotEqual && value == 100 && m_ubound == 15)
2275 if (c.will_match(value, m_lbound, m_ubound)) {
2278 if (action == act_CallbackIdx)
2281 REALM_ASSERT_DEBUG(state->m_match_count < state->m_limit);
2282 size_t process = state->m_limit - state->m_match_count;
2283 end2 = end - start2 > process ? start2 + process : end;
2285 if (action == act_Sum || action == act_Max || action == act_Min) {
2288 if (action == act_Sum)
2289 res = Array::sum(start2, end2);
2290 if (action == act_Max)
2291 Array::maximum(res, start2, end2, &res_ndx);
2292 if (action == act_Min)
2293 Array::minimum(res, start2, end2, &res_ndx);
2295 find_action<action, Callback>(res_ndx + baseindex, res, state, callback);
2296 // find_action will increment match count by 1, so we need to `-1` from the number of elements that
2297 // we performed the fast Array methods on.
2298 state->m_match_count += end2 - start2 - 1;
2300 else if (action == act_Count) {
2301 state->m_state += end2 - start2;
2304 for (; start2 < end2; start2++)
2305 if (!find_action<action, Callback>(start2 + baseindex, get<bitwidth>(start2), state, callback))
2311 // finder cannot handle this bitwidth
2312 REALM_ASSERT_3(m_width, !=, 0);
2314 #if defined(REALM_COMPILER_SSE)
2315 // Only use SSE if payload is at least one SSE chunk (128 bits) in size. Also note taht SSE doesn't support
2316 // Less-than comparison for 64-bit values.
2317 if ((!(std::is_same<cond, Less>::value && m_width == 64)) && end - start2 >= sizeof(__m128i) && m_width >= 8 &&
2318 (sseavx<42>() || (sseavx<30>() && std::is_same<cond, Equal>::value && m_width < 64))) {
2320 // find_sse() must start2 at 16-byte boundary, so search area before that using compare_equality()
2321 __m128i* const a = reinterpret_cast<__m128i*>(round_up(m_data + start2 * bitwidth / 8, sizeof(__m128i)));
2322 __m128i* const b = reinterpret_cast<__m128i*>(round_down(m_data + end * bitwidth / 8, sizeof(__m128i)));
2324 if (!compare<cond, action, bitwidth, Callback>(
2325 value, start2, (reinterpret_cast<char*>(a) - m_data) * 8 / no0(bitwidth), baseindex, state, callback))
2328 // Search aligned area with SSE
2331 if (!find_sse<cond, action, bitwidth, Callback>(
2332 value, a, b - a, state,
2333 baseindex + ((reinterpret_cast<char*>(a) - m_data) * 8 / no0(bitwidth)), callback))
2336 else if (sseavx<30>()) {
2338 if (!find_sse<Equal, action, bitwidth, Callback>(
2339 value, a, b - a, state,
2340 baseindex + ((reinterpret_cast<char*>(a) - m_data) * 8 / no0(bitwidth)), callback))
2345 // Search remainder with compare_equality()
2346 if (!compare<cond, action, bitwidth, Callback>(
2347 value, (reinterpret_cast<char*>(b) - m_data) * 8 / no0(bitwidth), end, baseindex, state, callback))
2353 return compare<cond, action, bitwidth, Callback>(value, start2, end, baseindex, state, callback);
2356 return compare<cond, action, bitwidth, Callback>(value, start2, end, baseindex, state, callback);
2360 template <size_t width>
2361 inline int64_t Array::lower_bits() const
2364 return 0xFFFFFFFFFFFFFFFFULL;
2365 else if (width == 2)
2366 return 0x5555555555555555ULL;
2367 else if (width == 4)
2368 return 0x1111111111111111ULL;
2369 else if (width == 8)
2370 return 0x0101010101010101ULL;
2371 else if (width == 16)
2372 return 0x0001000100010001ULL;
2373 else if (width == 32)
2374 return 0x0000000100000001ULL;
2375 else if (width == 64)
2376 return 0x0000000000000001ULL;
2378 REALM_ASSERT_DEBUG(false);
2383 // Tests if any chunk in 'value' is 0
2384 template <size_t width>
2385 inline bool Array::test_zero(uint64_t value) const
2387 uint64_t hasZeroByte;
2388 uint64_t lower = lower_bits<width>();
2389 uint64_t upper = lower_bits<width>() * 1ULL << (width == 0 ? 0 : (width - 1ULL));
2390 hasZeroByte = (value - lower) & ~value & upper;
2391 return hasZeroByte != 0;
2394 // Finds first zero (if eq == true) or non-zero (if eq == false) element in v and returns its position.
2395 // IMPORTANT: This function assumes that at least 1 item matches (test this with test_zero() or other means first)!
2396 template <bool eq, size_t width>
2397 size_t Array::find_zero(uint64_t v) const
2400 uint64_t hasZeroByte;
2401 // Warning free way of computing (1ULL << width) - 1
2402 uint64_t mask = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) - 1ULL));
2404 if (eq == (((v >> (width * start)) & mask) == 0)) {
2408 // Bisection optimization, speeds up small bitwidths with high match frequency. More partions than 2 do NOT pay
2409 // off because the work done by test_zero() is wasted for the cases where the value exists in first half, but
2410 // useful if it exists in last half. Sweet spot turns out to be the widths and partitions below.
2412 hasZeroByte = test_zero<width>(v | 0xffffffff00000000ULL);
2413 if (eq ? !hasZeroByte : (v & 0x00000000ffffffffULL) == 0) {
2414 // 00?? -> increasing
2415 start += 64 / no0(width) / 2;
2417 hasZeroByte = test_zero<width>(v | 0xffff000000000000ULL);
2418 if (eq ? !hasZeroByte : (v & 0x0000ffffffffffffULL) == 0) {
2420 start += 64 / no0(width) / 4;
2427 hasZeroByte = test_zero<width>(v | 0xffffffffffff0000ULL);
2428 if (eq ? !hasZeroByte : (v & 0x000000000000ffffULL) == 0) {
2430 start += 64 / no0(width) / 4;
2436 while (eq == (((v >> (width * start)) & mask) != 0)) {
2437 // You must only call find_zero() if you are sure that at least 1 item matches
2438 REALM_ASSERT_3(start, <=, 8 * sizeof(v));
2445 // Generate a magic constant used for later bithacks
2446 template <bool gt, size_t width>
2447 int64_t Array::find_gtlt_magic(int64_t v) const
2449 uint64_t mask1 = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) -
2450 1ULL)); // Warning free way of computing (1ULL << width) - 1
2451 uint64_t mask2 = mask1 >> 1;
2452 uint64_t magic = gt ? (~0ULL / no0(mask1) * (mask2 - v)) : (~0ULL / no0(mask1) * v);
2456 template <bool gt, Action action, size_t width, class Callback>
2457 bool Array::find_gtlt_fast(uint64_t chunk, uint64_t magic, QueryState<int64_t>* state, size_t baseindex,
2458 Callback callback) const
2460 // Tests if a a chunk of values contains values that are greater (if gt == true) or less (if gt == false) than v.
2461 // Fast, but limited to work when all values in the chunk are positive.
2463 uint64_t mask1 = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) -
2464 1ULL)); // Warning free way of computing (1ULL << width) - 1
2465 uint64_t mask2 = mask1 >> 1;
2466 uint64_t m = gt ? (((chunk + magic) | chunk) & ~0ULL / no0(mask1) * (mask2 + 1))
2467 : ((chunk - magic) & ~chunk & ~0ULL / no0(mask1) * (mask2 + 1));
2470 if (find_action_pattern<action, Callback>(baseindex, m >> (no0(width) - 1), state, callback))
2471 break; // consumed, so do not call find_action()
2473 size_t t = first_set_bit64(m) / no0(width);
2475 if (!find_action<action, Callback>(p + baseindex, (chunk >> (p * width)) & mask1, state, callback))
2478 if ((t + 1) * width == 64)
2481 m >>= (t + 1) * width;
2489 template <bool gt, Action action, size_t width, class Callback>
2490 bool Array::find_gtlt(int64_t v, uint64_t chunk, QueryState<int64_t>* state, size_t baseindex, Callback callback) const
2492 // 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
2494 for (size_t t = 0; t < 64; t++) {
2495 if (gt ? static_cast<int64_t>(chunk & 0x1) > v : static_cast<int64_t>(chunk & 0x1) < v) {if (!find_action<action, Callback>( t + baseindex, static_cast<int64_t>(chunk & 0x1), state, callback)) return false;}
2499 else if (width == 2) {
2500 // Alot (50% +) faster than loop/compiler-unrolled loop
2501 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 0 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2503 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 1 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2505 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 2 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2507 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 3 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2509 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 4 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2511 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 5 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2513 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 6 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2515 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 7 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2518 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 8 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2520 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 9 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2522 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 10 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2524 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 11 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2526 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 12 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2528 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 13 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2530 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 14 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2532 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 15 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2535 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 16 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2537 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 17 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2539 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 18 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2541 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 19 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2543 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 20 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2545 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 21 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2547 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 22 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2549 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 23 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2552 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 24 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2554 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 25 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2556 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 26 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2558 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 27 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2560 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 28 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2562 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 29 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2564 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 30 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2566 if (gt ? static_cast<int64_t>(chunk & 0x3) > v : static_cast<int64_t>(chunk & 0x3) < v) {if (!find_action<action, Callback>( 31 + baseindex, static_cast<int64_t>(chunk & 0x3), state, callback)) return false;}
2569 else if (width == 4) {
2570 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 0 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2572 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 1 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2574 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 2 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2576 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 3 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2578 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 4 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2580 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 5 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2582 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 6 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2584 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 7 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2587 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 8 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2589 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 9 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2591 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 10 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2593 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 11 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2595 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 12 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2597 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 13 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2599 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 14 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2601 if (gt ? static_cast<int64_t>(chunk & 0xf) > v : static_cast<int64_t>(chunk & 0xf) < v) {if (!find_action<action, Callback>( 15 + baseindex, static_cast<int64_t>(chunk & 0xf), state, callback)) return false;}
2604 else if (width == 8) {
2605 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 0 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2607 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 1 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2609 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 2 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2611 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 3 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2613 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 4 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2615 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 5 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2617 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 6 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2619 if (gt ? static_cast<int8_t>(chunk) > v : static_cast<int8_t>(chunk) < v) {if (!find_action<action, Callback>( 7 + baseindex, static_cast<int8_t>(chunk), state, callback)) return false;}
2622 else if (width == 16) {
2624 if (gt ? static_cast<short int>(chunk >> 0 * 16) > v : static_cast<short int>(chunk >> 0 * 16) < v) {if (!find_action<action, Callback>( 0 + baseindex, static_cast<short int>(chunk >> 0 * 16), state, callback)) return false;};
2625 if (gt ? static_cast<short int>(chunk >> 1 * 16) > v : static_cast<short int>(chunk >> 1 * 16) < v) {if (!find_action<action, Callback>( 1 + baseindex, static_cast<short int>(chunk >> 1 * 16), state, callback)) return false;};
2626 if (gt ? static_cast<short int>(chunk >> 2 * 16) > v : static_cast<short int>(chunk >> 2 * 16) < v) {if (!find_action<action, Callback>( 2 + baseindex, static_cast<short int>(chunk >> 2 * 16), state, callback)) return false;};
2627 if (gt ? static_cast<short int>(chunk >> 3 * 16) > v : static_cast<short int>(chunk >> 3 * 16) < v) {if (!find_action<action, Callback>( 3 + baseindex, static_cast<short int>(chunk >> 3 * 16), state, callback)) return false;};
2629 else if (width == 32) {
2630 if (gt ? static_cast<int>(chunk) > v : static_cast<int>(chunk) < v) {if (!find_action<action, Callback>( 0 + baseindex, static_cast<int>(chunk), state, callback)) return false;}
2632 if (gt ? static_cast<int>(chunk) > v : static_cast<int>(chunk) < v) {if (!find_action<action, Callback>( 1 + baseindex, static_cast<int>(chunk), state, callback)) return false;}
2635 else if (width == 64) {
2636 if (gt ? static_cast<int64_t>(v) > v : static_cast<int64_t>(v) < v) {if (!find_action<action, Callback>( 0 + baseindex, static_cast<int64_t>(v), state, callback)) return false;};
2643 /// Find items in this Array that are equal (eq == true) or different (eq = false) from 'value'
2644 template <bool eq, Action action, size_t width, class Callback>
2645 inline bool Array::compare_equality(int64_t value, size_t start, size_t end, size_t baseindex,
2646 QueryState<int64_t>* state, Callback callback) const
2648 REALM_ASSERT_DEBUG(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end);
2650 size_t ee = round_up(start, 64 / no0(width));
2651 ee = ee > end ? end : ee;
2652 for (; start < ee; ++start)
2653 if (eq ? (get<width>(start) == value) : (get<width>(start) != value)) {
2654 if (!find_action<action, Callback>(start + baseindex, get<width>(start), state, callback))
2661 if (width != 32 && width != 64) {
2662 const int64_t* p = reinterpret_cast<const int64_t*>(m_data + (start * width / 8));
2663 const int64_t* const e = reinterpret_cast<int64_t*>(m_data + (end * width / 8)) - 1;
2664 const uint64_t mask = (width == 64 ? ~0ULL : ((1ULL << (width == 64 ? 0 : width)) -
2665 1ULL)); // Warning free way of computing (1ULL << width) - 1
2666 const uint64_t valuemask =
2667 ~0ULL / no0(mask) * (value & mask); // the "== ? :" is to avoid division by 0 compiler error
2670 uint64_t chunk = *p;
2671 uint64_t v2 = chunk ^ valuemask;
2672 start = (p - reinterpret_cast<int64_t*>(m_data)) * 8 * 8 / no0(width);
2675 while (eq ? test_zero<width>(v2) : v2) {
2677 if (find_action_pattern<action, Callback>(start + baseindex, cascade<width, eq>(v2), state, callback))
2680 size_t t = find_zero<eq, width>(v2);
2683 if (a >= 64 / no0(width))
2686 if (!find_action<action, Callback>(a + start + baseindex, get<width>(start + t), state, callback))
2688 v2 >>= (t + 1) * width;
2695 // Loop ended because we are near end or end of array. No need to optimize search in remainder in this case
2696 // because end of array means that
2697 // lots of search work has taken place prior to ending here. So time spent searching remainder is relatively
2699 start = (p - reinterpret_cast<int64_t*>(m_data)) * 8 * 8 / no0(width);
2702 while (start < end) {
2703 if (eq ? get<width>(start) == value : get<width>(start) != value) {
2704 if (!find_action<action, Callback>(start + baseindex, get<width>(start), state, callback))
2713 // There exists a couple of find() functions that take more or less template arguments. Always call the one that
2714 // takes as most as possible to get best performance.
2716 // This is the one installed into the m_vtable->finder slots.
2717 template <class cond, Action action, size_t bitwidth>
2718 bool Array::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state) const
2720 return find<cond, action, bitwidth>(value, start, end, baseindex, state, CallbackDummy());
2723 template <class cond, Action action, class Callback>
2724 bool Array::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
2725 Callback callback, bool nullable_array, bool find_null) const
2727 REALM_TEMPEX4(return find, cond, action, m_width, Callback,
2728 (value, start, end, baseindex, state, callback, nullable_array, find_null));
2731 template <class cond, Action action, size_t bitwidth, class Callback>
2732 bool Array::find(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
2733 Callback callback, bool nullable_array, bool find_null) const
2735 return find_optimized<cond, action, bitwidth, Callback>(value, start, end, baseindex, state, callback,
2736 nullable_array, find_null);
2739 #ifdef REALM_COMPILER_SSE
2740 // 'items' is the number of 16-byte SSE chunks. Returns index of packed element relative to first integer of first
2742 template <class cond, Action action, size_t width, class Callback>
2743 bool Array::find_sse(int64_t value, __m128i* data, size_t items, QueryState<int64_t>* state, size_t baseindex,
2744 Callback callback) const
2746 __m128i search = {0};
2749 search = _mm_set1_epi8(static_cast<char>(value));
2750 else if (width == 16)
2751 search = _mm_set1_epi16(static_cast<short int>(value));
2752 else if (width == 32)
2753 search = _mm_set1_epi32(static_cast<int>(value));
2754 else if (width == 64) {
2755 if (std::is_same<cond, Less>::value)
2756 REALM_ASSERT(false);
2758 search = _mm_set_epi64x(value, value);
2761 return find_sse_intern<cond, action, width, Callback>(data, &search, items, state, baseindex, callback);
2764 // Compares packed action_data with packed data (equal, less, etc) and performs aggregate action (max, min, sum,
2765 // find_all, etc) on value inside action_data for first match, if any
2766 template <class cond, Action action, size_t width, class Callback>
2767 REALM_FORCEINLINE bool Array::find_sse_intern(__m128i* action_data, __m128i* data, size_t items,
2768 QueryState<int64_t>* state, size_t baseindex, Callback callback) const
2771 __m128i compare_result = {0};
2772 unsigned int resmask;
2774 // Search loop. Unrolling it has been tested to NOT increase performance (apparently mem bound)
2775 for (i = 0; i < items; ++i) {
2776 // equal / not-equal
2777 if (std::is_same<cond, Equal>::value || std::is_same<cond, NotEqual>::value) {
2779 compare_result = _mm_cmpeq_epi8(action_data[i], *data);
2781 compare_result = _mm_cmpeq_epi16(action_data[i], *data);
2783 compare_result = _mm_cmpeq_epi32(action_data[i], *data);
2785 compare_result = _mm_cmpeq_epi64(action_data[i], *data); // SSE 4.2 only
2790 else if (std::is_same<cond, Greater>::value) {
2792 compare_result = _mm_cmpgt_epi8(action_data[i], *data);
2794 compare_result = _mm_cmpgt_epi16(action_data[i], *data);
2796 compare_result = _mm_cmpgt_epi32(action_data[i], *data);
2798 compare_result = _mm_cmpgt_epi64(action_data[i], *data);
2801 else if (std::is_same<cond, Less>::value) {
2803 compare_result = _mm_cmplt_epi8(action_data[i], *data);
2804 else if (width == 16)
2805 compare_result = _mm_cmplt_epi16(action_data[i], *data);
2806 else if (width == 32)
2807 compare_result = _mm_cmplt_epi32(action_data[i], *data);
2809 REALM_ASSERT(false);
2812 resmask = _mm_movemask_epi8(compare_result);
2814 if (std::is_same<cond, NotEqual>::value)
2815 resmask = ~resmask & 0x0000ffff;
2817 size_t s = i * sizeof(__m128i) * 8 / no0(width);
2819 while (resmask != 0) {
2821 uint64_t upper = lower_bits<width / 8>() << (no0(width / 8) - 1);
2824 upper; // fixme, bits at wrong offsets. Only OK because we only use them in 'count' aggregate
2825 if (find_action_pattern<action, Callback>(s + baseindex, pattern, state, callback))
2828 size_t idx = first_set_bit(resmask) * 8 / no0(width);
2830 if (!find_action<action, Callback>(
2831 s + baseindex, get_universal<width>(reinterpret_cast<char*>(action_data), s), state, callback))
2833 resmask >>= (idx + 1) * no0(width) / 8;
2840 #endif // REALM_COMPILER_SSE
2842 template <class cond, Action action, class Callback>
2843 bool Array::compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex,
2844 QueryState<int64_t>* state, Callback callback) const
2847 REALM_ASSERT_3(start, <=, end);
2854 // We can compare first element without checking for out-of-range
2856 if (c(v, foreign->get(start))) {
2857 if (!find_action<action, Callback>(start + baseindex, v, state, callback))
2863 if (start + 3 < end) {
2865 if (c(v, foreign->get(start)))
2866 if (!find_action<action, Callback>(start + baseindex, v, state, callback))
2870 if (c(v, foreign->get(start + 1)))
2871 if (!find_action<action, Callback>(start + 1 + baseindex, v, state, callback))
2875 if (c(v, foreign->get(start + 2)))
2876 if (!find_action<action, Callback>(start + 2 + baseindex, v, state, callback))
2881 else if (start == end) {
2886 REALM_TEMPEX4(r = compare_leafs, cond, action, m_width, Callback,
2887 (foreign, start, end, baseindex, state, callback))
2892 template <class cond, Action action, size_t width, class Callback>
2893 bool Array::compare_leafs(const Array* foreign, size_t start, size_t end, size_t baseindex,
2894 QueryState<int64_t>* state, Callback callback) const
2896 size_t fw = foreign->m_width;
2898 REALM_TEMPEX5(r = compare_leafs_4, cond, action, width, Callback, fw,
2899 (foreign, start, end, baseindex, state, callback))
2904 template <class cond, Action action, size_t width, class Callback, size_t foreign_width>
2905 bool Array::compare_leafs_4(const Array* foreign, size_t start, size_t end, size_t baseindex,
2906 QueryState<int64_t>* state, Callback callback) const
2909 char* foreign_m_data = foreign->m_data;
2911 if (width == 0 && foreign_width == 0) {
2913 while (start < end) {
2914 if (!find_action<action, Callback>(start + baseindex, 0, state, callback))
2925 #if defined(REALM_COMPILER_SSE)
2926 if (sseavx<42>() && width == foreign_width && (width == 8 || width == 16 || width == 32)) {
2927 // We can only use SSE if both bitwidths are equal and above 8 bits and all values are signed
2928 while (start < end && (((reinterpret_cast<size_t>(m_data) & 0xf) * 8 + start * width) % (128) != 0)) {
2929 int64_t v = get_universal<width>(m_data, start);
2930 int64_t fv = get_universal<foreign_width>(foreign_m_data, start);
2932 if (!find_action<action, Callback>(start + baseindex, v, state, callback))
2941 size_t sse_items = (end - start) * width / 128;
2942 size_t sse_end = start + sse_items * 128 / no0(width);
2944 while (start < sse_end) {
2945 __m128i* a = reinterpret_cast<__m128i*>(m_data + start * width / 8);
2946 __m128i* b = reinterpret_cast<__m128i*>(foreign_m_data + start * width / 8);
2948 bool continue_search =
2949 find_sse_intern<cond, action, width, Callback>(a, b, 1, state, baseindex + start, callback);
2951 if (!continue_search)
2954 start += 128 / no0(width);
2959 while (start < end) {
2960 int64_t v = get_universal<width>(m_data, start);
2961 int64_t fv = get_universal<foreign_width>(foreign_m_data, start);
2964 if (!find_action<action, Callback>(start + baseindex, v, state, callback))
2975 template <class cond, Action action, size_t bitwidth, class Callback>
2976 bool Array::compare(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
2977 Callback callback) const
2981 if (std::is_same<cond, Equal>::value)
2982 ret = compare_equality<true, action, bitwidth, Callback>(value, start, end, baseindex, state, callback);
2983 else if (std::is_same<cond, NotEqual>::value)
2984 ret = compare_equality<false, action, bitwidth, Callback>(value, start, end, baseindex, state, callback);
2985 else if (std::is_same<cond, Greater>::value)
2986 ret = compare_relation<true, action, bitwidth, Callback>(value, start, end, baseindex, state, callback);
2987 else if (std::is_same<cond, Less>::value)
2988 ret = compare_relation<false, action, bitwidth, Callback>(value, start, end, baseindex, state, callback);
2990 REALM_ASSERT_DEBUG(false);
2995 template <bool gt, Action action, size_t bitwidth, class Callback>
2996 bool Array::compare_relation(int64_t value, size_t start, size_t end, size_t baseindex, QueryState<int64_t>* state,
2997 Callback callback) const
2999 REALM_ASSERT(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end);
3000 uint64_t mask = (bitwidth == 64 ? ~0ULL : ((1ULL << (bitwidth == 64 ? 0 : bitwidth)) -
3001 1ULL)); // Warning free way of computing (1ULL << width) - 1
3003 size_t ee = round_up(start, 64 / no0(bitwidth));
3004 ee = ee > end ? end : ee;
3005 for (; start < ee; start++) {
3006 if (gt ? (get<bitwidth>(start) > value) : (get<bitwidth>(start) < value)) {
3007 if (!find_action<action, Callback>(start + baseindex, get<bitwidth>(start), state, callback))
3013 return true; // none found, continue (return true) regardless what find_action() would have returned on match
3015 const int64_t* p = reinterpret_cast<const int64_t*>(m_data + (start * bitwidth / 8));
3016 const int64_t* const e = reinterpret_cast<int64_t*>(m_data + (end * bitwidth / 8)) - 1;
3018 // Matches are rare enough to setup fast linear search for remaining items. We use
3019 // bit hacks from http://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord
3021 if (bitwidth == 1 || bitwidth == 2 || bitwidth == 4 || bitwidth == 8 || bitwidth == 16) {
3022 uint64_t magic = find_gtlt_magic<gt, bitwidth>(value);
3024 // Bit hacks only work if searched item has its most significant bit clear for 'greater than' or
3025 // 'item <= 1 << bitwidth' for 'less than'
3026 if (value != int64_t((magic & mask)) && value >= 0 && bitwidth >= 2 &&
3027 value <= static_cast<int64_t>((mask >> 1) - (gt ? 1 : 0))) {
3030 uint64_t upper = lower_bits<bitwidth>() << (no0(bitwidth) - 1);
3032 const int64_t v = *p;
3035 // Bit hacks only works if all items in chunk have their most significant bit clear. Test this:
3039 idx = find_gtlt_fast<gt, action, bitwidth, Callback>(
3040 v, magic, state, (p - reinterpret_cast<int64_t*>(m_data)) * 8 * 8 / no0(bitwidth) + baseindex,
3044 idx = find_gtlt<gt, action, bitwidth, Callback>(
3045 value, v, state, (p - reinterpret_cast<int64_t*>(m_data)) * 8 * 8 / no0(bitwidth) + baseindex,
3057 if (!find_gtlt<gt, action, bitwidth, Callback>(
3058 value, v, state, (p - reinterpret_cast<int64_t*>(m_data)) * 8 * 8 / no0(bitwidth) + baseindex,
3064 start = (p - reinterpret_cast<int64_t*>(m_data)) * 8 * 8 / no0(bitwidth);
3067 // matchcount logic in SIMD no longer pays off for 32/64 bit ints because we have just 4/2 elements
3069 // Test unaligned end and/or values of width > 16 manually
3070 while (start < end) {
3071 if (gt ? get<bitwidth>(start) > value : get<bitwidth>(start) < value) {
3072 if (!find_action<action, Callback>(start + baseindex, get<bitwidth>(start), state, callback))
3080 template <class cond>
3081 size_t Array::find_first(int64_t value, size_t start, size_t end) const
3083 REALM_ASSERT(start <= m_size && (end <= m_size || end == size_t(-1)) && start <= end);
3084 QueryState<int64_t> state;
3085 state.init(act_ReturnFirst, nullptr,
3086 1); // todo, would be nice to avoid this in order to speed up find_first loops
3087 Finder finder = m_vtable->finder[cond::condition];
3088 (this->*finder)(value, start, end, 0, &state);
3090 return static_cast<size_t>(state.m_state);
3093 //*************************************************************************************
3094 // Finding code ends *
3095 //*************************************************************************************
3098 } // namespace realm
3100 #endif // REALM_ARRAY_HPP