tpl_file_bplus_map.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  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 AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
# ifndef TPL_FILE_BPLUS_MAP_H
# define TPL_FILE_BPLUS_MAP_H
 
# include <array>
# include <bit>
# include <cstddef>
# include <cstring>
# include <optional>
# include <ostream>
# include <string>
# include <type_traits>
# include <utility>
 
# include <ah-concepts.H>
# include <ah-errors.H>
# include <tpl_array.H>
# include <tpl_file_bplus_tree.H>
 
namespace Aleph
{
  template <typename Key,
            typename Value,
            class Compare = Aleph::less<Key>,
            size_t MinDegree = 16,
            typename KeyCodec = detail::Paged_Value_Codec<Key>,
            typename ValueCodec = detail::Paged_Value_Codec<Value>>
    requires StrictWeakOrder<Compare, Key>
  class Gen_File_BPlus_Map
  {
    using key_codec = KeyCodec;
    using value_codec = ValueCodec;
 
    struct Record
    {
      std::array<unsigned char,
                 key_codec::encoded_size + value_codec::encoded_size> bytes = {};
 
      friend std::ostream & operator << (std::ostream & out, const Record &)
      {
        return out << "<record>";
      }
 
      [[nodiscard]] Key get_key() const
      {
        return key_codec::decode(bytes.data());
      }
 
      [[nodiscard]] Value get_value() const
      {
        return value_codec::decode(bytes.data() + key_codec::encoded_size);
      }
    };
 
    struct Record_Codec
    {
      static constexpr std::uint32_t storage_id =
        detail::mix_codec_id(detail::mix_codec_id(0x52000000u,
                                                  key_codec::storage_id),
                             value_codec::storage_id);
      static constexpr size_t encoded_size =
        key_codec::encoded_size + value_codec::encoded_size;
 
      static void encode(const Record & record, unsigned char * out) noexcept
      {
        std::memcpy(out, record.bytes.data(), record.bytes.size());
      }
 
      [[nodiscard]] static Record decode(const unsigned char * in) noexcept
      {
        Record record;
        std::memcpy(record.bytes.data(), in, record.bytes.size());
        return record;
      }
 
      [[nodiscard]] static std::uint32_t add_to_crc(
        const std::uint32_t crc,
        const Record & record) noexcept
      {
        return detail::crc32_add_bytes(crc, record.bytes.data(),
                                       record.bytes.size());
      }
    };
 
    struct Record_Compare
    {
      Compare cmp;
 
      bool operator () (const Record & lhs, const Record & rhs) const
      {
        return cmp(lhs.get_key(), rhs.get_key());
      }
    };
 
    using tree_impl_type =
      Gen_File_BPlus_Tree<Record, Record_Compare, MinDegree, Record_Codec>;
 
    static_assert(detail::Fixed_Paged_Value_Codec<key_codec, Key>,
                  "File_BPlus_Map requires a fixed-size key codec");
    static_assert(detail::Fixed_Paged_Value_Codec<value_codec, Value>,
                  "File_BPlus_Map requires a fixed-size mapped-value codec");
    static_assert(std::is_trivially_copyable_v<Record>,
                  "File_BPlus_Map requires trivially copyable records");
 
    tree_impl_type tree_;
 
    [[nodiscard]] static Record make_probe(const Key & key)
    {
      Record record;
      key_codec::encode(key, record.bytes.data());
      return record;
    }
 
    [[nodiscard]] static Record make_record(const Key & key,
                                            const Value & value)
    {
      Record record;
      key_codec::encode(key, record.bytes.data());
      value_codec::encode(value, record.bytes.data() + key_codec::encoded_size);
      return record;
    }
 
    [[nodiscard]] static std::pair<Key, Value>
    to_pair(const Record & record)
    {
      return std::pair<Key, Value>(record.get_key(), record.get_value());
    }
 
    [[nodiscard]] static Array<std::pair<Key, Value>>
    to_pairs(const Array<Record> & records)
    {
      Array<std::pair<Key, Value>> out;
      out.reserve(records.size() == 0 ? 1 : records.size());
      for (size_t i = 0; i < records.size(); ++i)
        out.append(to_pair(records[i]));
      return out;
    }
 
    [[nodiscard]] bool equals_key(const Key & lhs, const Key & rhs) const
    {
      const auto & cmp = tree_.key_comp().cmp;
      return not cmp(lhs, rhs) and not cmp(rhs, lhs);
    }
 
    [[nodiscard]] std::optional<Record> find_record(const Key & key) const
    {
      const auto probe = make_probe(key);
      auto candidate = tree_.lower_bound(probe);
      if (candidate.has_value() and equals_key(candidate->get_key(), key))
        return candidate;
      return std::nullopt;
    }
 
  public:
    using key_type = Key;
    using mapped_type = Value;
    using value_type = std::pair<Key, Value>;
    using tree_type = tree_impl_type;
    using open_mode_type = typename tree_type::open_mode_type;
 
    static constexpr auto Read_Write = tree_type::Read_Write;
    static constexpr auto Read_Only = tree_type::Read_Only;
 
    class Iterator
    {
      typename tree_type::Iterator it_;
 
    public:
      Iterator() noexcept = default;
 
      explicit Iterator(typename tree_type::Iterator it) noexcept
        : it_(std::move(it)) {}
 
      [[nodiscard]] bool has_curr() const noexcept
      {
        return it_.has_curr();
      }
 
      [[nodiscard]] value_type get_curr() const
      {
        return to_pair(it_.get_curr());
      }
 
      [[nodiscard]] Key get_key() const
      {
        return it_.get_curr().get_key();
      }
 
      [[nodiscard]] Value get_value() const
      {
        return it_.get_curr().get_value();
      }
 
      void next_ne()
      {
        it_.next_ne();
      }
 
      void next()
      {
        next_ne();
      }
    };
 
    explicit Gen_File_BPlus_Map(std::string file_path,
                                const bool auto_sync = true,
                                const Compare & cmp = Compare())
      : tree_(std::move(file_path), auto_sync, Record_Compare{cmp}) {}
 
    explicit Gen_File_BPlus_Map(std::string file_path,
                                const open_mode_type open_mode,
                                const bool auto_sync = true,
                                const Compare & cmp = Compare())
      : tree_(std::move(file_path), open_mode, auto_sync, Record_Compare{cmp}) {}
 
    explicit Gen_File_BPlus_Map(const char * file_path,
                                const bool auto_sync = true,
                                const Compare & cmp = Compare())
      : tree_(file_path, auto_sync, Record_Compare{cmp}) {}
 
    explicit Gen_File_BPlus_Map(const char * file_path,
                                const open_mode_type open_mode,
                                const bool auto_sync = true,
                                const Compare & cmp = Compare())
      : tree_(file_path, open_mode, auto_sync, Record_Compare{cmp}) {}
 
    Gen_File_BPlus_Map(const Gen_File_BPlus_Map &) = delete;
 
    Gen_File_BPlus_Map & operator = (const Gen_File_BPlus_Map &) = delete;
 
    Gen_File_BPlus_Map(Gen_File_BPlus_Map &&) = delete;
 
    Gen_File_BPlus_Map & operator = (Gen_File_BPlus_Map &&) = delete;
 
    [[nodiscard]] const std::string & file_path() const noexcept
    {
      return tree_.file_path();
    }
 
    [[nodiscard]] open_mode_type open_mode() const noexcept
    {
      return tree_.open_mode();
    }
 
    [[nodiscard]] bool is_read_only() const noexcept
    {
      return tree_.is_read_only();
    }
 
    [[nodiscard]] bool auto_sync_enabled() const noexcept
    {
      return tree_.auto_sync_enabled();
    }
 
    void set_auto_sync(const bool enabled) noexcept
    {
      tree_.set_auto_sync(enabled);
    }
 
    [[nodiscard]] const Compare & key_comp() const noexcept
    {
      return tree_.key_comp().cmp;
    }
 
    [[nodiscard]] bool empty() const noexcept { return tree_.empty(); }
 
    [[nodiscard]] size_t size() const noexcept { return tree_.size(); }
 
    [[nodiscard]] size_t height() const noexcept { return tree_.height(); }
 
    [[nodiscard]] size_t page_size_bytes() const noexcept
    {
      return tree_.page_size_bytes();
    }
 
    [[nodiscard]] size_t page_count() const noexcept
    {
      return tree_.page_count();
    }
 
    [[nodiscard]] std::uint64_t checkpoint_sequence() const noexcept
    {
      return tree_.checkpoint_sequence();
    }
 
    void sync() const
    {
      tree_.sync();
    }
 
    void checkpoint() const
    {
      tree_.checkpoint();
    }
 
    void reload()
    {
      tree_.reload();
    }
 
    void clear()
    {
      tree_.clear();
    }
 
    [[nodiscard]] bool contains(const Key & key) const
    {
      return find_record(key).has_value();
    }
 
    [[nodiscard]] bool search(const Key & key) const
    {
      return contains(key);
    }
 
    [[nodiscard]] std::optional<Value> find(const Key & key) const
    {
      const auto record = find_record(key);
      if (not record.has_value())
        return std::nullopt;
      return record->get_value();
    }
 
    [[nodiscard]] Value at(const Key & key) const
    {
      const auto value = find(key);
      ah_domain_error_if(not value.has_value())
        << "File_BPlus_Map::at(): key not found";
      return *value;
    }
 
    bool insert(const Key & key, const Value & value)
    {
      return tree_.insert(make_record(key, value));
    }
 
    bool insert_or_assign(const Key & key, const Value & value)
    {
      const auto probe = make_probe(key);
      const auto record = make_record(key, value);
      if (tree_.insert(record))
        return true;
      ah_runtime_error_unless(tree_.remove(probe))
        << "File_BPlus_Map::insert_or_assign(): internal replace failed";
      ah_runtime_error_unless(tree_.insert(record))
        << "File_BPlus_Map::insert_or_assign(): internal reinsert failed";
      return false;
    }
 
    bool remove(const Key & key)
    {
      return tree_.remove(make_probe(key));
    }
 
    [[nodiscard]] std::optional<value_type> min_item() const
    {
      const auto record = tree_.min_key();
      if (not record.has_value())
        return std::nullopt;
      return to_pair(*record);
    }
 
    [[nodiscard]] std::optional<value_type> max_item() const
    {
      const auto record = tree_.max_key();
      if (not record.has_value())
        return std::nullopt;
      return to_pair(*record);
    }
 
    [[nodiscard]] std::optional<value_type> lower_bound(const Key & key) const
    {
      const auto record = tree_.lower_bound(make_probe(key));
      if (not record.has_value())
        return std::nullopt;
      return to_pair(*record);
    }
 
    [[nodiscard]] std::optional<value_type> upper_bound(const Key & key) const
    {
      const auto record = tree_.upper_bound(make_probe(key));
      if (not record.has_value())
        return std::nullopt;
      return to_pair(*record);
    }
 
    [[nodiscard]] Array<value_type> range(const Key & first, const Key & last) const
    {
      return to_pairs(tree_.range(make_probe(first), make_probe(last)));
    }
 
    [[nodiscard]] Array<Key> keys() const
    {
      Array<Key> out;
      const auto records = tree_.keys();
      out.reserve(records.size() == 0 ? 1 : records.size());
      for (size_t i = 0; i < records.size(); ++i)
        out.append(records[i].get_key());
      return out;
    }
 
    [[nodiscard]] Array<Value> values() const
    {
      Array<Value> out;
      const auto records = tree_.keys();
      out.reserve(records.size() == 0 ? 1 : records.size());
      for (size_t i = 0; i < records.size(); ++i)
        out.append(records[i].get_value());
      return out;
    }
 
    [[nodiscard]] Array<value_type> items() const
    {
      return to_pairs(tree_.keys());
    }
 
    [[nodiscard]] Iterator get_it() const noexcept
    {
      return Iterator(tree_.get_it());
    }
 
    [[nodiscard]] Iterator get_range_it(const Key & first, const Key & last) const
    {
      return Iterator(tree_.get_range_it(make_probe(first), make_probe(last)));
    }
 
    [[nodiscard]] bool verify() const
    {
      return tree_.verify();
    }
  };
 
  template <typename Key,
            typename Value,
            class Compare = Aleph::less<Key>,
            size_t MinDegree = 16,
            typename KeyCodec = detail::Paged_Value_Codec<Key>,
            typename ValueCodec = detail::Paged_Value_Codec<Value>>
  using File_BPlus_Map = Gen_File_BPlus_Map<Key, Value, Compare, MinDegree,
                                            KeyCodec, ValueCodec>;
} // namespace Aleph
 
# endif // TPL_FILE_BPLUS_MAP_H