services/media/framework/parts/sparse_byte_buffer.cc

// Copyright 2016 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 "base/logging.h"
#include "services/media/framework/parts/sparse_byte_buffer.h"

namespace mojo {
namespace media {

SparseByteBuffer::Hole::Hole() {}

SparseByteBuffer::Hole::Hole(std::map<size_t, size_t>::iterator iter)
    : iter_(iter) {}

SparseByteBuffer::Hole::Hole(const Hole& other) : iter_(other.iter_) {}

SparseByteBuffer::Hole::~Hole() {}

SparseByteBuffer::Region::Region() {}

SparseByteBuffer::Region::Region(
    std::map<size_t, std::vector<uint8_t>>::iterator iter)
    : iter_(iter) {}

SparseByteBuffer::Region::Region(const Region& other) : iter_(other.iter_) {}

SparseByteBuffer::Region::~Region() {}

SparseByteBuffer::SparseByteBuffer() {}

SparseByteBuffer::~SparseByteBuffer() {}

void SparseByteBuffer::Initialize(size_t size) {
  holes_.clear();
  regions_.clear();
  size_ = size;
  // Create one hole spanning the entire buffer.
  holes_[0] = size_;
}

SparseByteBuffer::Region SparseByteBuffer::FindRegionContaining(size_t position,
                                                                Region hint) {
  DCHECK(size_ > 0u);
  DCHECK(position < size_);

  RegionsIter iter = hint.iter_;

  if (iter != regions_.end() && iter->first <= position) {
    if (iter->first + iter->second.size() <= position) {
      // iter is too close to the front. See if the next region is correct.
      ++iter;
      if (iter != regions_.end() && iter->first <= position &&
          position < iter->first + iter->second.size()) {
        return Region(iter);
      }
    } else if (position < iter->first + iter->second.size()) {
      return Region(iter);
    }
  }

  iter = regions_.lower_bound(position);
  if (iter != regions_.begin() &&
      (iter == regions_.end() || iter->first > position)) {
    --iter;
    DCHECK(iter->first <= position);
    if (iter->first + iter->second.size() <= position) {
      iter = regions_.end();
    }
  }

  return Region(iter);
}

SparseByteBuffer::Hole SparseByteBuffer::FindOrCreateHole(size_t position,
                                                          Hole hint) {
  DCHECK(size_ > 0u);
  DCHECK(!holes_.empty());

  HolesIter result = hint.iter_;

  if (result == holes_.end()) {
    result = holes_.begin();
  }

  if (result->first != position) {
    if (result->first > position ||
        result->first + result->second <= position) {
      // Need to find the hole containing the requested position.
      result = FindHoleContaining(position).iter_;
      DCHECK(result != holes_.end());
    }

    if (result->first != position) {
      // Need to split this hole.
      DCHECK(position > result->first);
      size_t front_size = position - result->first;

      DCHECK(result->second > front_size);
      size_t back_size = result->second - front_size;

      result->second = front_size;

      result = holes_.insert(++result,
                             std::pair<size_t, size_t>(position, back_size));
    }
  }

  DCHECK(result->first == position);

  return Hole(result);
}

SparseByteBuffer::Hole SparseByteBuffer::FindHoleContaining(size_t position) {
  DCHECK(size_ > 0u);
  HolesIter iter = holes_.lower_bound(position);
  if (iter != holes_.begin() &&
      (iter == holes_.end() || iter->first > position)) {
    --iter;
    DCHECK(iter->first <= position);
    if (iter->first + iter->second < position) {
      iter = holes_.end();
    }
  }

  return Hole(iter);
}

SparseByteBuffer::Hole SparseByteBuffer::Fill(Hole hole,
                                              std::vector<uint8_t>&& buffer) {
  DCHECK(size_ > 0u);
  DCHECK(hole.iter_ != holes_.end());
  DCHECK(buffer.size() != 0);
  DCHECK(buffer.size() <= hole.size());

  HolesIter holes_iter = hole.iter_;

  size_t buffer_size = buffer.size();
  size_t position = holes_iter->first;

  regions_.emplace(std::make_pair(position, std::move(buffer)));

  // Remove the region from holes_.
  while (buffer_size != 0) {
    DCHECK(holes_iter != holes_.end());
    DCHECK(holes_iter->first == position);

    if (buffer_size < holes_iter->second) {
      // We've filled part of *holes_iter. Insert a hole after it to
      // represent the remainder.
      HolesIter hint = holes_iter;
      holes_.insert(
          ++hint, std::pair<size_t, size_t>(holes_iter->first + buffer_size,
                                            holes_iter->second - buffer_size));

      // When we've erased holes_iter, we'll have accounted for the entire
      // filled region.
      position += buffer_size;
      buffer_size = 0;
    } else {
      // Calculate where we'll be when we've erased holes_iter.
      position += holes_iter->second;
      buffer_size -= holes_iter->second;
    }

    holes_iter = holes_.erase(holes_iter);
    if (holes_iter == holes_.end()) {
      DCHECK(buffer_size == 0);
      holes_iter = holes_.begin();
    }
  }

  return Hole(holes_iter);
}

bool operator==(const SparseByteBuffer::Hole& a,
                const SparseByteBuffer::Hole& b) {
  return a.iter_ == b.iter_;
}

bool operator!=(const SparseByteBuffer::Hole& a,
                const SparseByteBuffer::Hole& b) {
  return a.iter_ != b.iter_;
}

bool operator==(const SparseByteBuffer::Region& a,
                const SparseByteBuffer::Region& b) {
  return a.iter_ == b.iter_;
}

bool operator!=(const SparseByteBuffer::Region& a,
                const SparseByteBuffer::Region& b) {
  return a.iter_ != b.iter_;
}

}  // namespace media
}  // namespace mojo