/// \file ROOT/RNTupleJoinTable.hxx /// \ingroup NTuple /// \author Florine de Geus /// \date 2024-04-02 /// \warning This is part of the ROOT 7 prototype! It will change without notice. It might trigger earthquakes. Feedback /// is welcome! /************************************************************************* * Copyright (C) 1995-2024, Rene Brun and Fons Rademakers. * * All rights reserved. * * * * For the licensing terms see $ROOTSYS/LICENSE. * * For the list of contributors see $ROOTSYS/README/CREDITS. * *************************************************************************/ #ifndef ROOT_RNTupleJoinTable #define ROOT_RNTupleJoinTable #include #include #include #include #include namespace ROOT { namespace Experimental { namespace Internal { // clang-format off /** \class ROOT::Experimental::Internal::RNTupleJoinTable \ingroup NTuple \brief Builds a join table on one or several fields of an RNTuple so it can be joined onto other RNTuples. */ // clang-format on class RNTupleJoinTable { public: using JoinValue_t = std::uint64_t; using PartitionKey_t = std::uint64_t; static constexpr PartitionKey_t kDefaultPartitionKey = PartitionKey_t(-1); private: // clang-format off /** \class ROOT::Experimental::Internal::RNTupleJoinTable::REntryMapping \ingroup NTuple \brief Provides a mapping from one or several join field values to an entry index. */ // clang-format on class REntryMapping { private: ////////////////////////////////////////////////////////////////////////// /// Container for the combined hashes of join field values. struct RCombinedJoinFieldValue { std::vector fJoinFieldValues; RCombinedJoinFieldValue(const std::vector &joinFieldValues) : fJoinFieldValues(joinFieldValues) {} inline bool operator==(const RCombinedJoinFieldValue &other) const { return other.fJoinFieldValues == fJoinFieldValues; } }; ///////////////////////////////////////////////////////////////////////////// /// Hash combining the individual join field value hashes from RCombinedJoinFieldValue. Uses the implementation /// from `boost::hash_combine`. See /// https://www.boost.org/doc/libs/1_87_0/libs/container_hash/doc/html/hash.html#notes_hash_combine for more /// background. In particular, it mentions: "Several improvements of the 64 bit function have been subsequently /// proposed, by [David Stafford](https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html), [Pelle /// Evensen](https://mostlymangling.blogspot.com/2019/12/stronger-better-morer-moremur-better.html), and [Jon /// Maiga](http://jonkagstrom.com/mx3/mx3_rev2.html). We currently use Jon Maiga’s function." /// /// \note /// \parblock /// Copyright 2005-2014 Daniel James. /// Copyright 2021, 2022 Peter Dimov. /// Distributed under the Boost Software License, Version 1.0. /// https://www.boost.org/LICENSE_1_0.txt /// /// Based on Peter Dimov's proposal /// http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf /// issue 6.18. /// /// Boost Software License - Version 1.0 - August 17th, 2003 /// /// Permission is hereby granted, free of charge, to any person or organization /// obtaining a copy of the software and accompanying documentation covered by /// this license (the "Software") to use, reproduce, display, distribute, /// execute, and transmit the Software, and to prepare derivative works of the /// Software, and to permit third-parties to whom the Software is furnished to /// do so, all subject to the following: /// /// The copyright notices in the Software and this entire statement, including /// the above license grant, this restriction and the following disclaimer, /// must be included in all copies of the Software, in whole or in part, and /// all derivative works of the Software, unless such copies or derivative /// works are solely in the form of machine-executable object code generated by /// a source language processor. /// /// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR /// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, /// FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT /// SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE /// FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, /// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER /// DEALINGS IN THE SOFTWARE. /// \endparblock struct RCombinedJoinFieldValueHash { inline std::size_t operator()(const RCombinedJoinFieldValue &joinFieldVal) const { std::size_t seed = 0; for (const auto &fieldVal : joinFieldVal.fJoinFieldValues) { seed ^= mix(seed + 0x9e3779b9 + fieldVal); } return seed; } inline std::size_t mix(std::size_t init) const { #ifdef R__B64 init ^= init >> 32; init *= 0xe9846af9b1a615d; init ^= init >> 32; init *= 0xe9846af9b1a615d; init ^= init >> 28; #else init ^= init >> 16; init *= 0x21f0aaad; init ^= init >> 15; init *= 0x735a2d97; init ^= init >> 15; #endif return init; } }; /// The mapping itself. Maps field values (or combinations thereof in case the join key is composed of multiple /// fields) to their respective entry numbers. std::unordered_map, RCombinedJoinFieldValueHash> fMapping; /// Names of the join fields used for the mapping to their respective entry indexes. std::vector fJoinFieldNames; /// The size (in bytes) for each join field, corresponding to `fJoinFieldNames`. This information is stored to be /// able to properly cast incoming void pointers to the join field values in `GetEntryIndexes`. std::vector fJoinFieldValueSizes; public: ////////////////////////////////////////////////////////////////////////// /// \brief Get the entry indexes for this entry mapping. const std::vector *GetEntryIndexes(std::vector valuePtrs) const; ////////////////////////////////////////////////////////////////////////// /// \brief Create a new entry mapping. /// /// \param[in] pageSource The page source of the RNTuple with the entries to map. /// \param[in] joinFieldNames Names of the join fields to use in the mapping. /// \param[in] entryOffset Offset to add to each entry index in the mapping. This can can be used when the /// RNTuple represented by the provided page source is part of a chain of RNTuples. REntryMapping(ROOT::Internal::RPageSource &pageSource, const std::vector &joinFieldNames, ROOT::NTupleSize_t entryOffset = 0); }; /// Names of the join fields used for the mapping to their respective entry indexes. std::vector fJoinFieldNames; /// Partitions of one or multiple entry mappings. std::unordered_map>> fPartitions; ///////////////////////////////////////////////////////////////////////////// /// \brief Create an a new RNTupleJoinTable for the RNTuple represented by the provided page source. /// /// \param[in] joinFieldNames The names of the join fields to use for the join table. Only integral-type fields are /// allowed. RNTupleJoinTable(const std::vector &joinFieldNames) : fJoinFieldNames(joinFieldNames) {} public: RNTupleJoinTable(const RNTupleJoinTable &other) = delete; RNTupleJoinTable &operator=(const RNTupleJoinTable &other) = delete; RNTupleJoinTable(RNTupleJoinTable &&other) = delete; RNTupleJoinTable &operator=(RNTupleJoinTable &&other) = delete; ~RNTupleJoinTable() = default; ///////////////////////////////////////////////////////////////////////////// /// \brief Create an RNTupleJoinTable from an existing RNTuple. /// /// \param[in] joinFieldNames The names of the join fields to use for the join table. Only integral-type fields are /// allowed. /// /// \return A pointer to the newly-created join table. static std::unique_ptr Create(const std::vector &joinFieldNames); ///////////////////////////////////////////////////////////////////////////// /// \brief Add an entry mapping to the join table. /// /// /// \param[in] pageSource The page source of the RNTuple with the entries to map. /// \param[in] partitionKey Which partition to add the mapping to. If not provided, it will be added to the default /// partition. /// \param[in] entryOffset Offset to add to each entry index in the mapping. This can can be used when the /// RNTuple represented by the provided page source is part of a chain of RNTuples. /// /// \return A reference to the updated join table. RNTupleJoinTable &Add(ROOT::Internal::RPageSource &pageSource, PartitionKey_t partitionKey = kDefaultPartitionKey, ROOT::NTupleSize_t entryOffset = 0); ///////////////////////////////////////////////////////////////////////////// /// \brief Get an entry index (if it exists) for the given join field value(s), from any partition. /// /// \param[in] valuePtrs A vector of pointers to the join field values to look up. /// /// \note If one or more corresponding entries exist for the given value(s), the first entry index found in the join /// table is returned. /// /// \return An entry number that corresponds to `valuePtrs`. When there are no corresponding entries, /// `kInvalidNTupleIndex` is returned. ROOT::NTupleSize_t GetEntryIndex(const std::vector &valuePtrs) const; }; } // namespace Internal } // namespace Experimental } // namespace ROOT #endif // ROOT_RNTupleJoinTable