data_file_set.h

Go to the documentation of this file.

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you 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.
 */
 
#pragma once
 
 
#include <cstdint>
#include <iterator>
#include <memory>
#include <optional>
#include <span>
#include <string>
#include <string_view>
#include <unordered_map>
#include <vector>
 
#include "iceberg/iceberg_export.h"
#include "iceberg/manifest/manifest_entry.h"
#include "iceberg/util/string_util.h"
 
namespace iceberg {
 
class ICEBERG_EXPORT DataFileSet {
 public:
  using value_type = std::shared_ptr<DataFile>;
  using iterator = typename std::vector<value_type>::iterator;
  using const_iterator = typename std::vector<value_type>::const_iterator;
  using difference_type = typename std::vector<value_type>::difference_type;
 
  DataFileSet() = default;
  DataFileSet(const DataFileSet& other) : elements_(other.elements_) { RebuildIndex(); }
  DataFileSet& operator=(const DataFileSet& other) {
    if (this != &other) {
      elements_ = other.elements_;
      RebuildIndex();
    }
    return *this;
  }
  DataFileSet(DataFileSet&&) noexcept = default;
  DataFileSet& operator=(DataFileSet&&) noexcept = default;
 
  std::pair<iterator, bool> insert(const value_type& file) { return InsertImpl(file); }
 
  std::pair<iterator, bool> insert(value_type&& file) {
    return InsertImpl(std::move(file));
  }
 
  bool contains(const DataFile& file) const {
    return index_by_path_.contains(file.file_path);
  }
 
  bool contains(const value_type& file) const {
    return file != nullptr && contains(*file);
  }
 
  size_t size() const { return elements_.size(); }
 
  bool empty() const { return elements_.empty(); }
 
  void clear() {
    elements_.clear();
    index_by_path_.clear();
  }
 
  iterator begin() { return elements_.begin(); }
  const_iterator begin() const { return elements_.begin(); }
  const_iterator cbegin() const { return elements_.cbegin(); }
 
  iterator end() { return elements_.end(); }
  const_iterator end() const { return elements_.end(); }
  const_iterator cend() const { return elements_.cend(); }
 
  std::span<const value_type> as_span() const { return elements_; }
 
 private:
  std::pair<iterator, bool> InsertImpl(value_type file) {
    if (!file) {
      return {elements_.end(), false};
    }
 
    auto [index_iter, inserted] =
        index_by_path_.try_emplace(file->file_path, elements_.size());
    if (!inserted) {
      auto pos = static_cast<difference_type>(index_iter->second);
      return {elements_.begin() + pos, false};
    }
 
    elements_.push_back(std::move(file));
    return {std::prev(elements_.end()), true};
  }
 
  void RebuildIndex() {
    index_by_path_.clear();
    for (size_t i = 0; i < elements_.size(); ++i) {
      if (elements_[i] != nullptr) {
        index_by_path_.try_emplace(elements_[i]->file_path, i);
      }
    }
  }
 
  // Vector to preserve insertion order
  std::vector<value_type> elements_;
  std::unordered_map<std::string_view, size_t, StringHash, StringEqual> index_by_path_;
};
 
class ICEBERG_EXPORT DeleteFileSet {
 public:
  using value_type = std::shared_ptr<DataFile>;
  using iterator = typename std::vector<value_type>::iterator;
  using const_iterator = typename std::vector<value_type>::const_iterator;
  using difference_type = typename std::vector<value_type>::difference_type;
 
  DeleteFileSet() = default;
  DeleteFileSet(const DeleteFileSet& other) : elements_(other.elements_) {
    RebuildIndex();
  }
  DeleteFileSet& operator=(const DeleteFileSet& other) {
    if (this != &other) {
      elements_ = other.elements_;
      RebuildIndex();
    }
    return *this;
  }
  DeleteFileSet(DeleteFileSet&&) noexcept = default;
  DeleteFileSet& operator=(DeleteFileSet&&) noexcept = default;
 
  std::pair<iterator, bool> insert(const value_type& file) { return InsertImpl(file); }
 
  std::pair<iterator, bool> insert(value_type&& file) {
    return InsertImpl(std::move(file));
  }
 
  bool contains(const DataFile& file) const {
    return index_by_file_.contains(DeleteFileKey(file));
  }
 
  bool contains(const value_type& file) const {
    return file != nullptr && contains(*file);
  }
 
  size_t size() const { return elements_.size(); }
 
  bool empty() const { return elements_.empty(); }
 
  void clear() {
    elements_.clear();
    index_by_file_.clear();
  }
 
  iterator begin() { return elements_.begin(); }
  const_iterator begin() const { return elements_.begin(); }
  const_iterator cbegin() const { return elements_.cbegin(); }
 
  iterator end() { return elements_.end(); }
  const_iterator end() const { return elements_.end(); }
  const_iterator cend() const { return elements_.cend(); }
 
  std::span<const value_type> as_span() const { return elements_; }
 
 private:
  struct DeleteFileKey {
    explicit DeleteFileKey(const DataFile& file)
        : path(file.file_path),
          content_offset(file.content_offset),
          content_size_in_bytes(file.content_size_in_bytes) {}
 
    std::string path;
    std::optional<int64_t> content_offset;
    std::optional<int64_t> content_size_in_bytes;
 
    bool operator==(const DeleteFileKey& other) const = default;
  };
 
  struct DeleteFileKeyHash {
    size_t operator()(const DeleteFileKey& key) const {
      size_t hash = std::hash<std::string>{}(key.path);
      auto combine = [&hash](const auto& value) {
        size_t value_hash = value.has_value() ? std::hash<int64_t>{}(*value) : 0;
        hash ^= value_hash + 0x9e3779b9 + (hash << 6) + (hash >> 2);
      };
      combine(key.content_offset);
      combine(key.content_size_in_bytes);
      return hash;
    }
  };
 
  std::pair<iterator, bool> InsertImpl(value_type file) {
    if (!file) {
      return {elements_.end(), false};
    }
 
    auto [index_iter, inserted] =
        index_by_file_.try_emplace(DeleteFileKey(*file), elements_.size());
    if (!inserted) {
      auto pos = static_cast<difference_type>(index_iter->second);
      return {elements_.begin() + pos, false};
    }
 
    elements_.push_back(std::move(file));
    return {std::prev(elements_.end()), true};
  }
 
  void RebuildIndex() {
    index_by_file_.clear();
    for (size_t i = 0; i < elements_.size(); ++i) {
      if (elements_[i] != nullptr) {
        index_by_file_.try_emplace(DeleteFileKey(*elements_[i]), i);
      }
    }
  }
 
  // Vector to preserve insertion order.
  std::vector<value_type> elements_;
  std::unordered_map<DeleteFileKey, size_t, DeleteFileKeyHash> index_by_file_;
};
 
}  // namespace iceberg