#pragma once

#include <cstdint>

#include <iosfwd>

#include <queue>

#include "envoy/upstream/scheduler.h"

#include "source/common/common/assert.h"

namespace Envoy {

namespace Upstream {

// It's not sufficient to use trace level logging, since it becomes far too noisy for a number of

// tests, so we can kill trace debug here.

#define EDF_DEBUG 0

#if EDF_DEBUG

#define EDF_TRACE(...) ENVOY_LOG_MISC(trace, __VA_ARGS__)

#else

#define EDF_TRACE(...)

#endif

// Earliest Deadline First (EDF) scheduler

// (https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling) used for weighted round robin.

// Each pick from the schedule has the earliest deadline entry selected. Entries have deadlines set

// at current time + 1 / weight, providing weighted round robin behavior with floating point

// weights and an O(log n) pick time.

template <class C> class EdfScheduler : public Scheduler<C> {

public:

  // See scheduler.h for an explanation of each public method.

      // In this case the entry was added back during peekAgain so don't re-add.

  // Creates an EdfScheduler with the given weights and their corresponding

  // entries, and emulating a number of initial picks to be performed. Note that

  // the internal state of the scheduler will be very similar to creating an empty

  // scheduler, adding the entries one after the other, and then performing

  // "picks" pickAndAdd operation without modifying the entries' weights.

  // The only thing that may be different is that entries with the same weight

  // may be chosen a bit differently (the order_offset_ values may be different).

  // Breaking the ties of same weight entries will be kept in future picks from

  // the scheduler.

  static EdfScheduler<C> createWithPicks(const std::vector<std::shared_ptr<C>>& entries,

                                         std::function<double(const C&)> calculate_weight,

    // Limiting the number of picks, as over 400M picks should be sufficient

    // for most scenarios.

    // Assume no non-positive weights.

    // Nothing to do if there are no entries.

    // Augment the weight computation to add some epsilon to each entry's

    // weight to avoid cases where weights are multiplies of each other. For

    // example if there are 2 weights: 25 and 75, and picks=23, then the

    // floor_picks will be {5, 17} (respectively), and the deadlines will be

    // {0.24000000000000002 and 0.24} (respectively). This small difference will

    // cause a "wrong" pick compared to when starting from an empty scheduler

    // and picking 23 times. Adding a small value to each weight circumvents

    // this problem. This was added as a result of the following comment:

    // https://github.com/envoyproxy/envoy/pull/31592#issuecomment-1877663769.

    // Take a snapshot of entry weights so they remain consistent during scheduling.

    // Let weights {w_1, w_2, ..., w_N} be the per-entry weight where (w_i > 0),

    // W = sum(w_i), and P be the number of times to "pick" from the scheduler.

    // Let p'_i = floor(P * w_i/W), then the number of times each entry is being

    // picked is p_i >= p'_i. Note that 0 <= P - sum(p'_i) < N.

    //

    // The following code does P picks, by first emulating p'_i picks for each

    // entry, and then executing the leftover P - sum(p'_i) picks.

                     // Getting the lower-bound by casting to an integer.

    // Pre-compute the priority-queue entries to use an O(N) initialization c'tor.

    // Emulate a per-entry addition to a deadline that is applicable to N picks.

      // Add the entry with p'_i picks. As there were p'_i picks, the entry's

      // next deadline is (p'_i + 1) / w_i.

      // While validating the algorithm there were a few cases where the math

      // and floating-point arithmetic did not agree (specifically floor(A*B)

      // was greater than A*B). The following if statement solves the problem by

      // reducing floor-picks for the entry, which may result in more iterations

      // in the code after the loop.

    // The scheduler's current_time_ needs to be the largest time that some entry was picked.

    // Left to do some picks, execute them one after the other.

private:

  friend class EdfSchedulerTest;

  /**

   * Clears expired entries and pops the next unexpired entry in the queue.

   */

      // Entry has been removed, let's see if there's another one.

  struct EdfEntry {

    double deadline_;

    // Tie breaker for entries with the same deadline. This is used to provide FIFO behavior.

    uint64_t order_offset_;

    // We only hold a weak pointer, since we don't support a remove operator. This allows entries to

    // be lazily unloaded from the queue.

    std::weak_ptr<C> entry_;

    // Flip < direction to make this a min queue.

  };

  EdfScheduler(std::vector<EdfEntry>&& scheduler_entries, double current_time,

               uint32_t order_offset)

  // Current time in EDF scheduler.

  // TODO(htuch): Is it worth the small extra complexity to use integer time for performance

  // reasons?

  double current_time_{};

  // Offset used during addition to break ties when entries have the same weight but should reflect

  // FIFO insertion order in picks.

  uint64_t order_offset_{};

  // Min priority queue for EDF.

  std::priority_queue<EdfEntry> queue_;

  std::list<std::weak_ptr<C>> prepick_list_;

};

#undef EDF_DEBUG

} // namespace Upstream

} // namespace Envoy