bin/mediaplayer/demux/sparse_byte_buffer.h

// Copyright 2016 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.

#ifndef GARNET_BIN_MEDIAPLAYER_DEMUX_SPARSE_BYTE_BUFFER_H_
#define GARNET_BIN_MEDIAPLAYER_DEMUX_SPARSE_BYTE_BUFFER_H_

#include <map>
#include <optional>
#include <vector>

namespace media_player {

class SparseByteBuffer {
 public:
  struct Hole {
    Hole();
    Hole(const Hole& other);
    ~Hole();

    size_t position() { return iter_->first; }
    size_t size() { return iter_->second; }

   private:
    explicit Hole(std::map<size_t, size_t>::iterator iter);

    std::map<size_t, size_t>::iterator iter_;

    friend bool operator==(const Hole& a, const Hole& b);
    friend bool operator!=(const Hole& a, const Hole& b);
    friend class SparseByteBuffer;
  };

  struct Region {
    Region();
    Region(const Region& other);
    ~Region();

    size_t position() { return iter_->first; }
    size_t size() { return iter_->second.size(); }
    uint8_t* data() { return iter_->second.data(); }

   private:
    explicit Region(std::map<size_t, std::vector<uint8_t>>::iterator iter);

    std::map<size_t, std::vector<uint8_t>>::iterator iter_;

    friend bool operator==(const Region& a, const Region& b);
    friend bool operator!=(const Region& a, const Region& b);
    friend class SparseByteBuffer;
  };

  SparseByteBuffer();

  ~SparseByteBuffer();

  Hole null_hole() { return Hole(holes_.end()); }

  Region null_region() { return Region(regions_.end()); }

  // Initialized the buffer.
  void Initialize(size_t size);

  // Reads a range of data from the SparseBuffer, which may span multiple
  // regions. Reading will begin at |start| in the SparseBuffer and stop when
  // |size| bytes have been copied into |dest_buffer| or a hole in the
  // SparseBuffer is encountered.
  //
  // For example, when reading the range [0, 100) in a Sparsebuffer with regions
  // [0, 50) and [50, 100), ReadRange will read across them both and read the
  // regions' content into the first and second half of the destination buffer
  // respectively.
  size_t ReadRange(size_t start, size_t size, uint8_t* dest_buffer);

  // Finds a region containing the specified position. This method will check
  // hint and its successor, if they're valid, before doing a search.
  Region FindRegionContaining(size_t position, Region hint);

  // Returns the number of bytes stored in the buffer across all regions.
  size_t BytesStored();

  // Returns the next missing byte in the buffer. If no bytes are missing ahead
  // of |start|, |std::nullopt| is returned.
  std::optional<size_t> NextMissingByte(size_t start);

  // Finds or creates a hole at the specified position. This method will check
  // hint, if it's valid, before doing a search.
  Hole FindOrCreateHole(size_t position, Hole hint);

  // Finds a hole containing the specified position.
  Hole FindHoleContaining(size_t position);

  // Finds or creates holes which fully describe the buffer's gaps in the given
  // range.
  std::vector<Hole> FindOrCreateHolesInRange(size_t start, size_t size);

  // Counts the number of bytes missing in the buffer from |start| to
  // |start+size|.
  size_t BytesMissingInRange(size_t start, size_t size);

  // Creates a region that starts at hole.position(). The new region must not
  // overlap other existing regions and cannot extend beyond the size of this
  // sparse buffer. Holes are updated to accommodate the region. Fill returns
  // the first hole that follows the new region in the wraparound sense. If
  // this sparse buffer is completely filled (there are no holes), this method
  // return null_hole().
  Hole Fill(Hole hole, std::vector<uint8_t>&& buffer);

  // Frees and shrinks regions outside the protected range until |goal| bytes
  // have been freed from the buffer or nothing remains to free. Returns the
  // bytes actually freed.
  //
  // Frees and shrinks regions outside the protected range as they are found,
  // first cleaning up regions before the protected range, and then regions
  // after after the protected range. In both traversals regions farther from
  // the protected range are cleaned up first.
  size_t CleanUpExcept(size_t goal, size_t protected_start,
                       size_t protected_size);

  // Shrinks the front of a region (e.g. shrinking [{1, 2, 3}] by 1 yields
  // [hole, {2, 3}]). This may require a copy. Returns an updated Region handle.
  // The handle is equal to null_region() if the region was shrunk by its whole
  // size and therefore freed.
  Region ShrinkRegionFront(Region region, size_t shrink_amount);

  // Shrinks the back of a region (e.g. shrinking [{1, 2, 3}] by 1 yields
  // [{1, 2}, hole]). Returns an updated Region handle. The handle is equal to
  // null_region() if the region was shrunk by its whole size and therefore
  // freed.
  Region ShrinkRegionBack(Region region, size_t shrink_amount);

  // Drops a region and coalesces (may modify) any adjacent holes.
  Hole Free(Region region);

 private:
  using HolesIter = std::map<size_t, size_t>::iterator;
  using RegionsIter = std::map<size_t, std::vector<uint8_t>>::iterator;

  size_t size_ = 0u;
  std::map<size_t, size_t> holes_;                  // Hole sizes by position.
  std::map<size_t, std::vector<uint8_t>> regions_;  // Buffers by position.
};

bool operator==(const SparseByteBuffer::Hole& a,
                const SparseByteBuffer::Hole& b);

bool operator!=(const SparseByteBuffer::Hole& a,
                const SparseByteBuffer::Hole& b);

bool operator==(const SparseByteBuffer::Region& a,
                const SparseByteBuffer::Region& b);

bool operator!=(const SparseByteBuffer::Region& a,
                const SparseByteBuffer::Region& b);

}  // namespace media_player

#endif  // GARNET_BIN_MEDIAPLAYER_DEMUX_SPARSE_BYTE_BUFFER_H_