quiche/quic/core/quic_interval_deque.h

// Copyright (c) 2019 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.

#ifndef QUICHE_QUIC_CORE_QUIC_INTERVAL_DEQUE_H_
#define QUICHE_QUIC_CORE_QUIC_INTERVAL_DEQUE_H_

#include <algorithm>

#include "absl/types/optional.h"
#include "quiche/quic/core/quic_interval.h"
#include "quiche/quic/core/quic_types.h"
#include "quiche/quic/platform/api/quic_bug_tracker.h"
#include "quiche/quic/platform/api/quic_export.h"
#include "quiche/quic/platform/api/quic_logging.h"
#include "quiche/common/quiche_circular_deque.h"

namespace quic {

namespace test {
class QuicIntervalDequePeer;
}  // namespace test

// QuicIntervalDeque<T, C> is a templated wrapper container, wrapping random
// access data structures. The wrapper allows items to be added to the
// underlying container with intervals associated with each item. The intervals
// _should_ be added already sorted and represent searchable indices. The search
// is optimized for sequential usage.
//
// As the intervals are to be searched sequentially the search for the next
// interval can be achieved in O(1), by simply remembering the last interval
// consumed. The structure also checks for an "off-by-one" use case wherein the
// |cached_index_| is off by one index as the caller didn't call operator |++|
// to increment the index. Other intervals can be found in O(log(n)) as they are
// binary searchable. A use case for this structure is packet buffering: Packets
// are sent sequentially but can sometimes needed for retransmission. The
// packets and their payloads are added with associated intervals representing
// data ranges they carry. When a user asks for a particular interval it's very
// likely they are requesting the next sequential interval, receiving it in O(1)
// time. Updating the sequential index is done automatically through the
// |DataAt| method and its iterator operator |++|.
//
// The intervals are represented using the usual C++ STL convention, namely as
// the half-open QuicInterval [min, max). A point p is considered to be
// contained in the QuicInterval iff p >= min && p < max. One consequence of
// this definition is that for any non-empty QuicInterval, min is contained in
// the QuicInterval but max is not. There is no canonical representation for the
// empty QuicInterval; and empty intervals are forbidden from being added to
// this container as they would be unsearchable.
//
// The type T is required to be copy-constructable or move-constructable. The
// type T is also expected to have an |interval()| method returning a
// QuicInterval<std::size> for the particular value. The type C is required to
// be a random access container supporting the methods |pop_front|, |push_back|,
// |operator[]|, |size|, and iterator support for |std::lower_bound| eg. a
// |deque| or |vector|.
//
// The QuicIntervalDeque<T, C>, like other C++ STL random access containers,
// doesn't have any explicit support for any equality operators.
//
//
// Examples with internal state:
//
//   // An example class to be stored inside the Interval Deque.
//   struct IntervalVal {
//     const int32_t val;
//     const size_t interval_begin, interval_end;
//     QuicInterval<size_t> interval();
//   };
//   typedef IntervalVal IV;
//   QuicIntervialDeque<IntervalValue> deque;
//
//   // State:
//   //   cached_index -> None
//   //   container -> {}
//
//   // Add interval items
//   deque.PushBack(IV(val: 0, interval_begin: 0, interval_end: 10));
//   deque.PushBack(IV(val: 1, interval_begin: 20, interval_end: 25));
//   deque.PushBack(IV(val: 2, interval_begin: 25, interval_end: 30));
//
//   // State:
//   //   cached_index -> 0
//   //   container -> {{0, [0, 10)}, {1, [20, 25)}, {2, [25, 30)}}
//
//   // Look for 0 and return [0, 10). Time: O(1)
//   auto it = deque.DataAt(0);
//   assert(it->val == 0);
//   it++;  // Increment and move the |cached_index_| over [0, 10) to [20, 25).
//   assert(it->val == 1);
//
//   // State:
//   //   cached_index -> 1
//   //   container -> {{0, [0, 10)}, {1, [20, 25)}, {2, [25, 30)}}
//
//   // Look for 20 and return [20, 25). Time: O(1)
//   auto it = deque.DataAt(20); // |cached_index_| remains unchanged.
//   assert(it->val == 1);
//
//   // State:
//   //   cached_index -> 1
//   //   container -> {{0, [0, 10)}, {1, [20, 25)}, {2, [25, 30)}}
//
//   // Look for 15 and return deque.DataEnd(). Time: O(log(n))
//   auto it = deque.DataAt(15); // |cached_index_| remains unchanged.
//   assert(it == deque.DataEnd());
//
//   // Look for 25 and return [25, 30). Time: O(1) with off-by-one.
//   auto it = deque.DataAt(25); // |cached_index_| is updated to 2.
//   assert(it->val == 2);
//   it++; // |cached_index_| is set to |None| as all data has been iterated.
//
//
//   // State:
//   //   cached_index -> None
//   //   container -> {{0, [0, 10)}, {1, [20, 25)}, {2, [25, 30)}}
//
//   // Look again for 0 and return [0, 10). Time: O(log(n))
//   auto it = deque.DataAt(0);
//
//
//   deque.PopFront();  // Pop -> {0, [0, 10)}
//
//   // State:
//   //   cached_index -> None
//   //   container -> {{1, [20, 25)}, {2, [25, 30)}}
//
//   deque.PopFront();  // Pop -> {1, [20, 25)}
//
//   // State:
//   //   cached_index -> None
//   //   container -> {{2, [25, 30)}}
//
//   deque.PushBack(IV(val: 3, interval_begin: 35, interval_end: 50));
//
//   // State:
//   //   cached_index -> 1
//   //   container -> {{2, [25, 30)}, {3, [35, 50)}}

template <class T, class C = quiche::QuicheCircularDeque<T>>
class QUIC_NO_EXPORT QuicIntervalDeque {
 public:
  class QUIC_NO_EXPORT Iterator {
   public:
    // Used by |std::lower_bound|
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

    // Every increment of the iterator will increment the |cached_index_| if
    // |index_| is larger than the current |cached_index_|. |index_| is bounded
    // at |deque_.size()| and any attempt to increment above that will be
    // ignored. Once an iterator has iterated all elements the |cached_index_|
    // will be reset.
    Iterator(std::size_t index, QuicIntervalDeque* deque)
        : index_(index), deque_(deque) {}
    // Only the ++ operator attempts to update the cached index. Other operators
    // are used by |lower_bound| to binary search and are thus private.
    Iterator& operator++() {
      // Don't increment when we are at the end.
      const std::size_t container_size = deque_->container_.size();
      if (index_ >= container_size) {
        QUIC_BUG(quic_bug_10862_1) << "Iterator out of bounds.";
        return *this;
      }
      index_++;
      if (deque_->cached_index_.has_value()) {
        const std::size_t cached_index = deque_->cached_index_.value();
        // If all items are iterated then reset the |cached_index_|
        if (index_ == container_size) {
          deque_->cached_index_.reset();
        } else {
          // Otherwise the new |cached_index_| is the max of itself and |index_|
          if (cached_index < index_) {
            deque_->cached_index_ = index_;
          }
        }
      }
      return *this;
    }
    Iterator operator++(int) {
      Iterator copy = *this;
      ++(*this);
      return copy;
    }
    reference operator*() { return deque_->container_[index_]; }
    reference operator*() const { return deque_->container_[index_]; }
    pointer operator->() { return &deque_->container_[index_]; }
    bool operator==(const Iterator& rhs) const {
      return index_ == rhs.index_ && deque_ == rhs.deque_;
    }
    bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }

   private:
    // A set of private operators for |std::lower_bound|
    Iterator operator+(difference_type amount) const {
      Iterator copy = *this;
      copy.index_ += amount;
      QUICHE_DCHECK(copy.index_ < copy.deque_->size());
      return copy;
    }
    Iterator& operator+=(difference_type amount) {
      index_ += amount;
      QUICHE_DCHECK(index_ < deque_->size());
      return *this;
    }
    difference_type operator-(const Iterator& rhs) const {
      return static_cast<difference_type>(index_) -
             static_cast<difference_type>(rhs.index_);
    }

    // |index_| is the index of the item in |*deque_|.
    std::size_t index_;
    // |deque_| is a pointer to the container the iterator came from.
    QuicIntervalDeque* deque_;

    friend class QuicIntervalDeque;
  };

  QuicIntervalDeque();

  // Adds an item to the underlying container. The |item|'s interval _should_ be
  // strictly greater than the last interval added.
  void PushBack(T&& item);
  void PushBack(const T& item);
  // Removes the front/top of the underlying container and the associated
  // interval.
  void PopFront();
  // Returns an iterator to the beginning of the data. The iterator will move
  // the |cached_index_| as the iterator moves.
  Iterator DataBegin();
  // Returns an iterator to the end of the data.
  Iterator DataEnd();
  // Returns an iterator pointing to the item in |interval_begin|. The iterator
  // will move the |cached_index_| as the iterator moves.
  Iterator DataAt(const std::size_t interval_begin);

  // Returns the number of items contained inside the structure.
  std::size_t Size() const;
  // Returns whether the structure is empty.
  bool Empty() const;

 private:
  struct QUIC_NO_EXPORT IntervalCompare {
    bool operator()(const T& item, std::size_t interval_begin) const {
      return item.interval().max() <= interval_begin;
    }
  };

  template <class U>
  void PushBackUniversal(U&& item);

  Iterator Search(const std::size_t interval_begin,
                  const std::size_t begin_index, const std::size_t end_index);

  // For accessing the |cached_index_|
  friend class test::QuicIntervalDequePeer;

  C container_;
  absl::optional<std::size_t> cached_index_;
};

template <class T, class C>
QuicIntervalDeque<T, C>::QuicIntervalDeque() {}

template <class T, class C>
void QuicIntervalDeque<T, C>::PushBack(T&& item) {
  PushBackUniversal(std::move(item));
}

template <class T, class C>
void QuicIntervalDeque<T, C>::PushBack(const T& item) {
  PushBackUniversal(item);
}

template <class T, class C>
void QuicIntervalDeque<T, C>::PopFront() {
  if (container_.size() == 0) {
    QUIC_BUG(quic_bug_10862_2) << "Trying to pop from an empty container.";
    return;
  }
  container_.pop_front();
  if (container_.size() == 0) {
    cached_index_.reset();
  }
  if (cached_index_.value_or(0) > 0) {
    cached_index_ = cached_index_.value() - 1;
  }
}

template <class T, class C>
typename QuicIntervalDeque<T, C>::Iterator
QuicIntervalDeque<T, C>::DataBegin() {
  return Iterator(0, this);
}

template <class T, class C>
typename QuicIntervalDeque<T, C>::Iterator QuicIntervalDeque<T, C>::DataEnd() {
  return Iterator(container_.size(), this);
}

template <class T, class C>
typename QuicIntervalDeque<T, C>::Iterator QuicIntervalDeque<T, C>::DataAt(
    const std::size_t interval_begin) {
  // No |cached_index_| value means all items can be searched.
  if (!cached_index_.has_value()) {
    return Search(interval_begin, 0, container_.size());
  }

  const std::size_t cached_index = cached_index_.value();
  QUICHE_DCHECK(cached_index < container_.size());

  const QuicInterval<size_t> cached_interval =
      container_[cached_index].interval();
  // Does our cached index point directly to what we want?
  if (cached_interval.Contains(interval_begin)) {
    return Iterator(cached_index, this);
  }

  // Are we off-by-one?
  const std::size_t next_index = cached_index + 1;
  if (next_index < container_.size()) {
    if (container_[next_index].interval().Contains(interval_begin)) {
      cached_index_ = next_index;
      return Iterator(next_index, this);
    }
  }

  // Small optimization:
  // Determine if we should binary search above or below the cached interval.
  const std::size_t cached_begin = cached_interval.min();
  bool looking_below = interval_begin < cached_begin;
  const std::size_t lower = looking_below ? 0 : cached_index + 1;
  const std::size_t upper = looking_below ? cached_index : container_.size();
  Iterator ret = Search(interval_begin, lower, upper);
  if (ret == DataEnd()) {
    return ret;
  }
  // Update the |cached_index_| to point to the higher index.
  if (!looking_below) {
    cached_index_ = ret.index_;
  }
  return ret;
}

template <class T, class C>
std::size_t QuicIntervalDeque<T, C>::Size() const {
  return container_.size();
}

template <class T, class C>
bool QuicIntervalDeque<T, C>::Empty() const {
  return container_.size() == 0;
}

template <class T, class C>
template <class U>
void QuicIntervalDeque<T, C>::PushBackUniversal(U&& item) {
  QuicInterval<std::size_t> interval = item.interval();
  // Adding an empty interval is a bug.
  if (interval.Empty()) {
    QUIC_BUG(quic_bug_10862_3)
        << "Trying to save empty interval to quiche::QuicheCircularDeque.";
    return;
  }
  container_.push_back(std::forward<U>(item));
  if (!cached_index_.has_value()) {
    cached_index_ = container_.size() - 1;
  }
}

template <class T, class C>
typename QuicIntervalDeque<T, C>::Iterator QuicIntervalDeque<T, C>::Search(
    const std::size_t interval_begin, const std::size_t begin_index,
    const std::size_t end_index) {
  auto begin = container_.begin() + begin_index;
  auto end = container_.begin() + end_index;
  auto res = std::lower_bound(begin, end, interval_begin, IntervalCompare());
  // Just because we run |lower_bound| and it didn't return |container_.end()|
  // doesn't mean we found our desired interval.
  if (res != end && res->interval().Contains(interval_begin)) {
    return Iterator(std::distance(begin, res) + begin_index, this);
  }
  return DataEnd();
}

}  // namespace quic

#endif  // QUICHE_QUIC_CORE_QUIC_INTERVAL_DEQUE_H_