// Copyright (c) 2015 The Chromium 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 "net/quic/quic_frame_list.h"

#include <algorithm>

#include "base/logging.h"

using std::list;
using std::string;

namespace net {

QuicFrameList::FrameData::FrameData(QuicStreamOffset offset,
                                    string segment,
                                    const QuicTime timestamp)
    : offset(offset), segment(segment), timestamp(timestamp) {}

QuicFrameList::QuicFrameList() {}

QuicFrameList::~QuicFrameList() {
  Clear();
}

void QuicFrameList::Clear() {
  frame_list_.clear();
  num_bytes_buffered_ = 0;
}

bool QuicFrameList::Empty() const {
  return frame_list_.empty();
}

QuicErrorCode QuicFrameList::OnStreamData(QuicStreamOffset offset,
                                          base::StringPiece data,
                                          QuicTime timestamp,
                                          size_t* const bytes_buffered) {
  *bytes_buffered = 0;
  const size_t data_len = data.size();
  auto insertion_point = FindInsertionPoint(offset, data_len);
  if (IsDuplicate(offset, data_len, insertion_point)) {
    return QUIC_NO_ERROR;
  }

  if (FrameOverlapsBufferedData(offset, data_len, insertion_point)) {
    return QUIC_INVALID_STREAM_DATA;
  }

  DVLOG(1) << "Buffering stream data at offset " << offset;
  // Inserting an empty string and then copying to avoid the extra copy.
  insertion_point =
      frame_list_.insert(insertion_point, FrameData(offset, "", timestamp));
  data.CopyToString(&insertion_point->segment);
  *bytes_buffered = data_len;
  num_bytes_buffered_ += data_len;
  return QUIC_NO_ERROR;
}

// Finds the place the frame should be inserted.  If an identical frame is
// present, stops on the identical frame.
list<QuicFrameList::FrameData>::iterator QuicFrameList::FindInsertionPoint(
    QuicStreamOffset offset,
    size_t len) {
  if (frame_list_.empty()) {
    return frame_list_.begin();
  }
  // If it's after all buffered_frames, return the end.
  if (offset >=
      (frame_list_.rbegin()->offset + frame_list_.rbegin()->segment.length())) {
    return frame_list_.end();
  }
  auto iter = frame_list_.begin();
  // Only advance the iterator if the data begins after the already received
  // frame.  If the new frame overlaps with an existing frame, the iterator will
  // still point to the frame it overlaps with.
  while (iter != frame_list_.end() &&
         offset >= iter->offset + iter->segment.length()) {
    ++iter;
  }
  return iter;
}

// Returns true if |frame| contains data which overlaps buffered data
// (indicating an invalid stream frame has been received).
bool QuicFrameList::FrameOverlapsBufferedData(
    QuicStreamOffset offset,
    size_t data_len,
    list<FrameData>::const_iterator insertion_point) const {
  if (frame_list_.empty() || insertion_point == frame_list_.end()) {
    return false;
  }
  // If there is a buffered frame with a higher starting offset, then check to
  // see if the new frame overlaps the beginning of the higher frame.
  if (offset < insertion_point->offset &&
      offset + data_len > insertion_point->offset) {
    DVLOG(1) << "New frame overlaps next frame: " << offset << " + " << data_len
             << " > " << insertion_point->offset;
    return true;
  }
  // If there is a buffered frame with a lower starting offset, then check to
  // see if the buffered frame runs into the new frame.
  if (offset >= insertion_point->offset &&
      offset < insertion_point->offset + insertion_point->segment.length()) {
    DVLOG(1) << "Preceeding frame overlaps new frame: "
             << insertion_point->offset << " + "
             << insertion_point->segment.length() << " > " << offset;
    return true;
  }

  return false;
}

// Returns true if the sequencer has received this frame before.
bool QuicFrameList::IsDuplicate(
    QuicStreamOffset offset,
    size_t data_len,
    list<FrameData>::const_iterator insertion_point) const {
  // A frame is duplicate if the frame offset is smaller than the bytes consumed
  // or identical to an already received frame.
  return offset < total_bytes_read_ || (insertion_point != frame_list_.end() &&
                                        offset == insertion_point->offset);
}

int QuicFrameList::GetReadableRegions(struct iovec* iov, int iov_len) const {
  list<FrameData>::const_iterator it = frame_list_.begin();
  int index = 0;
  QuicStreamOffset offset = total_bytes_read_;
  while (it != frame_list_.end() && index < iov_len) {
    if (it->offset != offset) {
      return index;
    }

    iov[index].iov_base =
        static_cast<void*>(const_cast<char*>(it->segment.data()));
    iov[index].iov_len = it->segment.size();
    offset += it->segment.size();

    ++index;
    ++it;
  }
  return index;
}

bool QuicFrameList::GetReadableRegion(iovec* iov, QuicTime* timestamp) const {
  list<FrameData>::const_iterator it = frame_list_.begin();
  if (it == frame_list_.end() || it->offset != total_bytes_read_) {
    return false;
  }
  iov->iov_base = static_cast<void*>(const_cast<char*>(it->segment.data()));
  iov->iov_len = it->segment.size();
  *timestamp = it->timestamp;
  return true;
}

bool QuicFrameList::MarkConsumed(size_t bytes_used) {
  size_t end_offset = total_bytes_read_ + bytes_used;
  while (!frame_list_.empty() && end_offset != total_bytes_read_) {
    list<FrameData>::iterator it = frame_list_.begin();
    if (it->offset != total_bytes_read_) {
      return false;
    }

    if (it->offset + it->segment.length() <= end_offset) {
      total_bytes_read_ += it->segment.length();
      num_bytes_buffered_ -= it->segment.length();
      // This chunk is entirely consumed.
      frame_list_.erase(it);
      continue;
    }

    // Partially consume this frame.
    size_t delta = end_offset - it->offset;
    total_bytes_read_ += delta;
    num_bytes_buffered_ -= delta;
    string new_data = it->segment.substr(delta);
    const QuicTime timestamp = it->timestamp;
    frame_list_.erase(it);
    frame_list_.push_front(FrameData(total_bytes_read_, new_data, timestamp));
    break;
  }
  return true;
}

size_t QuicFrameList::Readv(const struct iovec* iov, size_t iov_len) {
  list<FrameData>::iterator it = frame_list_.begin();
  size_t iov_index = 0;
  size_t iov_offset = 0;
  size_t frame_offset = 0;
  QuicStreamOffset initial_bytes_consumed = total_bytes_read_;

  while (iov_index < iov_len && it != frame_list_.end() &&
         it->offset == total_bytes_read_) {
    int bytes_to_read = std::min(iov[iov_index].iov_len - iov_offset,
                                 it->segment.size() - frame_offset);

    char* iov_ptr = static_cast<char*>(iov[iov_index].iov_base) + iov_offset;
    memcpy(iov_ptr, it->segment.data() + frame_offset, bytes_to_read);
    frame_offset += bytes_to_read;
    iov_offset += bytes_to_read;

    if (iov[iov_index].iov_len == iov_offset) {
      // We've filled this buffer.
      iov_offset = 0;
      ++iov_index;
    }
    if (it->segment.size() == frame_offset) {
      // We've copied this whole frame
      total_bytes_read_ += it->segment.size();
      num_bytes_buffered_ -= it->segment.size();
      frame_list_.erase(it);
      it = frame_list_.begin();
      frame_offset = 0;
    }
  }
  // Done copying.  If there is a partial frame, update it.
  if (frame_offset != 0) {
    frame_list_.push_front(FrameData(it->offset + frame_offset,
                                     it->segment.substr(frame_offset),
                                     it->timestamp));
    frame_list_.erase(it);
    total_bytes_read_ += frame_offset;
    num_bytes_buffered_ -= frame_offset;
  }
  return total_bytes_read_ - initial_bytes_consumed;
}

size_t QuicFrameList::FlushBufferedFrames() {
  QuicStreamOffset initial_bytes_consumed = total_bytes_read_;
  if (!frame_list_.empty()) {
    // Consume all of the bytes up to the last byte yet seen, including the
    // ones that haven't arrived yet.
    auto it = frame_list_.back();
    total_bytes_read_ = it.offset + it.segment.length();
    frame_list_.clear();
  }
  return total_bytes_read_ - initial_bytes_consumed;
}

bool QuicFrameList::HasBytesToRead() const {
  return !frame_list_.empty() &&
         frame_list_.begin()->offset == total_bytes_read_;
}

QuicStreamOffset QuicFrameList::BytesConsumed() const {
  return total_bytes_read_;
}

size_t QuicFrameList::BytesBuffered() const {
  return num_bytes_buffered_;
}

}  // namespace net