X-Git-Url: https://git.mdrn.pl/wl-app.git/blobdiff_plain/53b27422d140022594fc241cca91c3183be57bca..48b2fe9f7c2dc3d9aeaaa6dbfb27c7da4f3235ff:/iOS/Pods/Realm/include/core/realm/sync/object_id.hpp diff --git a/iOS/Pods/Realm/include/core/realm/sync/object_id.hpp b/iOS/Pods/Realm/include/core/realm/sync/object_id.hpp new file mode 100644 index 0000000..db3794a --- /dev/null +++ b/iOS/Pods/Realm/include/core/realm/sync/object_id.hpp @@ -0,0 +1,241 @@ +/************************************************************************* + * + * Copyright 2017 Realm Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + * + **************************************************************************/ + +#ifndef REALM_SYNC_OBJECT_ID_HPP +#define REALM_SYNC_OBJECT_ID_HPP + +#include // std::hash +#include +#include // operator<< +#include +#include + +#include + +#include +#include +#include + +// Only set this to one when testing the code paths that exercise object ID +// hash collisions. It artificially limits the "optimistic" local ID to use +// only the lower 15 bits of the ID rather than the lower 63 bits, making it +// feasible to generate collisions within reasonable time. +#define REALM_EXERCISE_OBJECT_ID_COLLISION 0 + +namespace realm { + +class Group; + +namespace sync { + +/// ObjectIDs are globally unique, and up to 128 bits wide. They are represented +/// as two 64-bit integers, each of which may frequently be small, for best +/// on-wire compressibility. +struct ObjectID { + constexpr ObjectID(uint64_t hi, uint64_t lo); + static ObjectID from_string(StringData); + + // FIXME: Remove "empty" ObjectIDs, wrap in Optional instead. + constexpr ObjectID(realm::util::None = realm::util::none); + constexpr ObjectID(const ObjectID&) noexcept = default; + ObjectID& operator=(const ObjectID&) noexcept = default; + + constexpr uint64_t lo() const { return m_lo; } + constexpr uint64_t hi() const { return m_hi; } + + std::string to_string() const; + + constexpr bool operator<(const ObjectID& other) const; + constexpr bool operator==(const ObjectID& other) const; + constexpr bool operator!=(const ObjectID& other) const; + +private: + uint64_t m_lo; + uint64_t m_hi; +}; + +/// Implementors of this interface should define a way to map from 128-bit +/// on-write ObjectIDs to local 64-bit object IDs. +/// +/// The three object ID types are: +/// a. Object IDs for objects in tables without primary keys. +/// b. Object IDs for objects in tables with integer primary keys. +/// c. Object IDs for objects in tables with other primary key types. +/// +/// For integer primary keys (b), the Object ID is just the integer value. +/// +/// For objects without primary keys (a), a "squeezed" tuple of the +/// client_file_ident and a peer-local sequence number is used as the local +/// Object ID. The on-write Object ID is the "unsqueezed" format. The methods on +/// this interface ending in "_squeezed" aid in the creation and conversion of +/// these IDs. +/// +/// For objects with other types of primary keys (c), the ObjectID +/// is a 128-bit hash of the primary key value. However, the local object ID +/// must be a 64-bit integer, because that is the maximum size integer that +/// Realm is able to store. The solution is to optimistically use the lower 63 +/// bits of the on-wire Object ID, and use a local ID with the upper 64th bit +/// set when there is a collision in the lower 63 bits between two different +/// hash values. +class ObjectIDProvider { +public: + using LocalObjectID = int_fast64_t; + + /// Calculate optimistic local ID that may collide with others. It is up to + /// the caller to ensure that collisions are detected and that + /// allocate_local_id_after_collision() is called to obtain a non-colliding + /// ID. + static LocalObjectID get_optimistic_local_id_hashed(ObjectID global_id); + + /// Find the local 64-bit object ID for the provided global 128-bit ID. + virtual LocalObjectID global_to_local_object_id_hashed(size_t table_ndx, ObjectID global_id) const = 0; + + /// After a local ID collision has been detected, this function may be + /// called to obtain a non-colliding local ID in such a way that subsequence + /// calls to global_to_local_object_id() will return the correct local ID + /// for both \a incoming_id and \a colliding_id. + virtual LocalObjectID allocate_local_id_after_hash_collision(size_t table_ndx, + ObjectID incoming_id, + ObjectID colliding_id, + LocalObjectID colliding_local_id) = 0; + static LocalObjectID make_tagged_local_id_after_hash_collision(uint64_t sequence_number); + virtual void free_local_id_after_hash_collision(size_t table_ndx, ObjectID object_id) = 0; + + /// Some Object IDs are generated as a tuple of the client_file_ident and a + /// local sequence number. This function takes the next number in the + /// sequence for the given table and returns an appropriate globally unique + /// ObjectID. + virtual ObjectID allocate_object_id_squeezed(size_t table_ndx) = 0; + static LocalObjectID global_to_local_object_id_squeezed(ObjectID); + static ObjectID local_to_global_object_id_squeezed(LocalObjectID); + + virtual int_fast64_t get_client_file_ident() const = 0; +}; + +// ObjectIDSet is a set of (table name, object id) +class ObjectIDSet { +public: + + void insert(StringData table, ObjectID object_id); + void erase(StringData table, ObjectID object_id); + bool contains(StringData table, ObjectID object_id) const noexcept; + +private: + + // A map from table name to a set of object ids. + std::map, std::less<>> m_objects; +}; + +/// Implementation: + + +constexpr ObjectID::ObjectID(uint64_t hi, uint64_t lo): m_lo(lo), m_hi(hi) +{ +} + +constexpr ObjectID::ObjectID(realm::util::None): m_lo(-1), m_hi(-1) +{ +} + +constexpr bool ObjectID::operator<(const ObjectID& other) const +{ + return (m_hi == other.m_hi) ? (m_lo < other.m_lo) : (m_hi < other.m_hi); +} + +constexpr bool ObjectID::operator==(const ObjectID& other) const +{ + return m_hi == other.m_hi && m_lo == other.m_lo; +} + +constexpr bool ObjectID::operator!=(const ObjectID& other) const +{ + return !(*this == other); +} + +std::ostream& operator<<(std::ostream&, const realm::sync::ObjectID&); + +inline ObjectIDProvider::LocalObjectID +ObjectIDProvider::get_optimistic_local_id_hashed(ObjectID global_id) +{ +#if REALM_EXERCISE_OBJECT_ID_COLLISION + const uint64_t optimistic_mask = 0xff; +#else + const uint64_t optimistic_mask = 0x7fffffffffffffff; +#endif + static_assert(optimistic_mask < 0x8000000000000000, "optimistic Object ID mask must leave the 64th bit zero"); + return global_id.lo() & optimistic_mask; +} + +inline ObjectIDProvider::LocalObjectID +ObjectIDProvider::make_tagged_local_id_after_hash_collision(uint64_t sequence_number) +{ + REALM_ASSERT(sequence_number < 0x8000000000000000); + return 0x8000000000000000 | sequence_number; +} + +inline ObjectIDProvider::LocalObjectID +ObjectIDProvider::global_to_local_object_id_squeezed(ObjectID object_id) +{ + REALM_ASSERT(object_id.hi() <= std::numeric_limits::max()); + REALM_ASSERT(object_id.lo() <= std::numeric_limits::max()); + + uint64_t a = object_id.lo() & 0xff; + uint64_t b = (object_id.hi() & 0xff) << 8; + uint64_t c = (object_id.lo() & 0xffffff00) << 8; + uint64_t d = (object_id.hi() & 0xffffff00) << 32; + union { + uint64_t u; + int64_t s; + } bitcast; + bitcast.u = a | b | c | d; + return bitcast.s; +} + +inline ObjectID +ObjectIDProvider::local_to_global_object_id_squeezed(LocalObjectID squeezed) +{ + union { + uint64_t u; + int64_t s; + } bitcast; + bitcast.s = squeezed; + + uint64_t u = bitcast.u; + + uint64_t lo = (u & 0xff) | ((u & 0xffffff0000) >> 8); + uint64_t hi = ((u & 0xff00) >> 8) | ((u & 0xffffff0000000000) >> 32); + return ObjectID{hi, lo}; +} + +} // namespace sync +} // namespace realm + +namespace std { + +template <> +struct hash { + size_t operator()(realm::sync::ObjectID oid) const + { + return std::hash{}(oid.lo()) ^ std::hash{}(oid.hi()); + } +}; + +} // namespace std + +#endif // REALM_SYNC_OBJECT_ID_HPP +