// Copyright 2018 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/storage/blobfs/iterator/node_populator.h"

#include <stdint.h>
#include <zircon/types.h>

#include <vector>

#include <safemath/safe_conversions.h>

#include "src/storage/blobfs/allocator/base_allocator.h"
#include "src/storage/blobfs/format.h"
#include "src/storage/blobfs/iterator/extent_iterator.h"

namespace blobfs {

NodePopulator::NodePopulator(BaseAllocator* allocator, std::vector<ReservedExtent> extents,
                             std::vector<ReservedNode> nodes)
    : allocator_(allocator), extents_(std::move(extents)), nodes_(std::move(nodes)) {
  ZX_DEBUG_ASSERT(extents_.size() <= kMaxExtentsPerBlob);
  ZX_DEBUG_ASSERT(nodes_.size() >= NodeCountForExtents(extents_.size()));
}

uint64_t NodePopulator::NodeCountForExtents(uint64_t extent_count) {
  bool out_of_line_extents = extent_count > kInlineMaxExtents;
  uint64_t remaining_extents = out_of_line_extents ? extent_count - kInlineMaxExtents : 0;
  return 1 + ((remaining_extents + kContainerMaxExtents - 1) / kContainerMaxExtents);
}

zx_status_t NodePopulator::Walk(OnNodeCallback on_node, OnExtentCallback on_extent) {
  // The first node is not an extent container, and must be treated differently.
  size_t node_count = 0;
  uint32_t node_index = nodes_[node_count].index();

  auto inode = allocator_->GetNode(node_index);
  if (inode.is_error()) {
    return inode.status_value();
  }
  allocator_->MarkInodeAllocated(std::move(nodes_[node_count]));
  on_node(node_index);

  ExtentContainer* container = nullptr;
  uint64_t local_index = 0;
  for (uint64_t extent_index = 0; extent_index < extents_.size(); extent_index++) {
    bool next_container = false;
    if (extent_index == kInlineMaxExtents) {
      // At capacity for the extents inside the inode; moving to a container.
      ZX_DEBUG_ASSERT_MSG(nodes_.size() > node_count, "Not enough nodes to hold extents");
      inode->header.next_node = nodes_[node_count + 1].index();
      next_container = true;
    } else if (local_index == kContainerMaxExtents) {
      // At capacity for the extents within a container; moving to another container.
      ZX_DEBUG_ASSERT_MSG(nodes_.size() > node_count, "Not enough nodes to hold extents");
      next_container = true;
    }

    if (next_container) {
      // Acquire the next container node, and connect it to the previous node.
      ReservedNode& node = nodes_[node_count + 1];
      uint32_t next = node.index();
      allocator_->MarkContainerNodeAllocated(std::move(node), node_index);
      container = allocator_->GetNode(next)->AsExtentContainer();
      on_node(next);
      node_index = next;

      node_count++;
      local_index = 0;
    }

    // Copy the extent into the chosen container.
    IterationCommand command = on_extent(extents_[extent_index]);
    if (extent_index < kInlineMaxExtents) {
      inode->extents[local_index] = extents_[extent_index].extent();
    } else {
      container->extents[local_index] = extents_[extent_index].extent();
      container->extent_count++;
    }

    inode->extent_count++;

    if (command == IterationCommand::Stop) {
      break;
    }

    local_index++;
  }

  return ZX_OK;
}

}  // namespace blobfs