hamt_set.hpp

Go to the documentation of this file.

//===- include/pstore/core/hamt_set.hpp -------------------*- mode: C++ -*-===//
//*  _                     _              _    *
//* | |__   __ _ _ __ ___ | |_   ___  ___| |_  *
//* | '_ \ / _` | '_ ` _ \| __| / __|/ _ \ __| *
//* | | | | (_| | | | | | | |_  \__ \  __/ |_  *
//* |_| |_|\__,_|_| |_| |_|\__| |___/\___|\__| *
//*                                            *
//===----------------------------------------------------------------------===//
//
// Part of the pstore project, under the Apache License v2.0 with LLVM Exceptions.
// See https://github.com/SNSystems/pstore/blob/master/LICENSE.txt for license
// information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef PSTORE_CORE_HAMT_SET_HPP
#define PSTORE_CORE_HAMT_SET_HPP

// pstore includes
#include "pstore/core/hamt_map.hpp"

namespace pstore {
    namespace index {

        namespace details {
            class empty_class {};
        } // namespace details

        template <typename KeyType, typename Hash, typename KeyEqual>
        class hamt_set final : public index_base {
            using index_pointer = pstore::index::details::index_pointer;

            template <typename MapIterator>
            class set_iterator {
                static_assert (std::is_same<typename MapIterator::value_type::first_type,
                                            typename std::add_const<KeyType>::type>::value,
                               "hamt_set key type does not match the iterator key type");

            public:
                using iterator_category = std::forward_iterator_tag;
                using value_type = typename std::add_const<KeyType>::type;
                using difference_type = std::ptrdiff_t;
                using pointer = value_type *;
                using reference = value_type &;

                explicit set_iterator (MapIterator const & it)
                        : it_ (it) {}

                bool operator== (set_iterator const & other) const { return it_ == other.it_; }

                bool operator!= (set_iterator const & other) const { return it_ != other.it_; }

                reference operator* () const { return it_->first; }

                pointer operator-> () const { return &it_->first; }

                set_iterator & operator++ () {
                    ++it_;
                    return *this;
                }
                set_iterator operator++ (int) {
                    auto const old (*this);
                    it_++;
                    return old;
                }

                address get_address () const { return it_.get_address (); }

            private:
                MapIterator it_;
            };

        public:
            // types
            using key_type = KeyType;
            using value_type = key_type;
            using key_equal = KeyEqual;
            using hasher = Hash;
            using reference = value_type &;
            using const_reference = value_type const &;

            using const_iterator =
                set_iterator<typename hamt_map<value_type, details::empty_class, hasher,
                                               key_equal>::const_iterator>;
            using iterator = const_iterator;

            explicit hamt_set (
                database const & db,
                typed_address<header_block> ip = typed_address<header_block>::null (),
                hasher const & hash = hasher ())
                    : map_ (db, ip, hash) {}


            range<database, hamt_set, iterator> make_range (database & db) { return {db, *this}; }
            range<database const, hamt_set const, const_iterator>
            make_range (database const & db) const {
                return {db, *this};
            }

            iterator begin (database & db) { return iterator{map_.begin (db)}; }
            const_iterator begin (database const & db) const {
                return const_iterator{map_.cbegin (db)};
            }
            const_iterator cbegin (database const & db) const {
                return const_iterator{map_.cbegin (db)};
            }

            iterator end (database & db) { return iterator{map_.end (db)}; }
            const_iterator end (database const & db) const {
                return const_iterator{map_.cend (db)};
            }
            const_iterator cend (database const & db) const {
                return const_iterator{map_.cend (db)};
            }


            bool empty () const { return map_.empty (); }

            std::size_t size () const { return map_.size (); }

            template <typename OtherKeyType,
                      typename = typename std::enable_if<
                          serialize::is_compatible<KeyType, OtherKeyType>::value>::type>
            std::pair<iterator, bool> insert (transaction_base & transaction,
                                              OtherKeyType const & key) {
                auto it = map_.insert (transaction, std::make_pair (key, details::empty_class ()));
                return {iterator{it.first}, it.second};
            }

            template <typename OtherKeyType,
                      typename = typename std::enable_if<
                          serialize::is_compatible<KeyType, OtherKeyType>::value>::type>
            const_iterator find (database const & db, OtherKeyType const & key) const {
                return const_iterator{map_.find (db, key)};
            }

            typed_address<header_block> flush (transaction_base & transaction,
                                               unsigned generation) {
                return map_.flush (transaction, generation);
            }


            value_type load_leaf_node (database const & db, address const addr) const {
                return map_.load_leaf_node (db, addr).first;
            }

            index_pointer root () const { return map_.root (); }

        private:
            hamt_map<value_type, details::empty_class, hasher, key_equal> map_;
        };

    } // namespace index

    namespace serialize {

        template <>
        struct serializer<index::details::empty_class> {
            using value_type = index::details::empty_class;

            template <typename Archive>
            static auto write (Archive && archive, value_type const &)
                -> archive_result_type<Archive> {
                // Tell the archiver to write an array of 0 elements. This should write
                // nothing at all but yield the location at which it would have gone (with the
                // correct type).
                auto const dummy = std::uint8_t{0};
                return serialize::write (std::forward<Archive> (archive),
                                         gsl::make_span (&dummy, &dummy));
            }

            template <typename Archive>
            static void read (Archive &&, value_type & value) {
                new (&value) value_type;
            }
        };

    } // namespace serialize

} // namespace pstore
#endif // PSTORE_CORE_HAMT_SET_HPP