1/*
2 *  Copyright (c) 2015 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11#include <assert.h>
12
13#include "webrtc/modules/remote_bitrate_estimator/include/send_time_history.h"
14
15namespace webrtc {
16
17SendTimeHistory::SendTimeHistory(Clock* clock, int64_t packet_age_limit)
18    : clock_(clock),
19      packet_age_limit_(packet_age_limit),
20      oldest_sequence_number_(0) {}
21
22SendTimeHistory::~SendTimeHistory() {
23}
24
25void SendTimeHistory::Clear() {
26  history_.clear();
27}
28
29void SendTimeHistory::AddAndRemoveOld(uint16_t sequence_number,
30                                      size_t length,
31                                      bool was_paced) {
32  EraseOld();
33
34  if (history_.empty())
35    oldest_sequence_number_ = sequence_number;
36
37  history_.insert(std::pair<uint16_t, PacketInfo>(
38      sequence_number, PacketInfo(clock_->TimeInMilliseconds(), 0, -1,
39                                  sequence_number, length, was_paced)));
40}
41
42bool SendTimeHistory::OnSentPacket(uint16_t sequence_number,
43                                   int64_t send_time_ms) {
44  auto it = history_.find(sequence_number);
45  if (it == history_.end())
46    return false;
47  it->second.send_time_ms = send_time_ms;
48  return true;
49}
50
51void SendTimeHistory::EraseOld() {
52  while (!history_.empty()) {
53    auto it = history_.find(oldest_sequence_number_);
54    assert(it != history_.end());
55
56    if (clock_->TimeInMilliseconds() - it->second.creation_time_ms <=
57        packet_age_limit_) {
58      return;  // Oldest packet within age limit, return.
59    }
60
61    // TODO(sprang): Warn if erasing (too many) old items?
62    history_.erase(it);
63    UpdateOldestSequenceNumber();
64  }
65}
66
67void SendTimeHistory::UpdateOldestSequenceNumber() {
68  // After removing an element from the map, update oldest_sequence_number_ to
69  // the element with the lowest sequence number higher than the previous
70  // value (there might be gaps).
71  if (history_.empty())
72    return;
73  auto it = history_.upper_bound(oldest_sequence_number_);
74  if (it == history_.end()) {
75    // No element with higher sequence number than oldest_sequence_number_
76    // found, check wrap around. Note that history_.upper_bound(0) will not
77    // find 0 even if it is there, need to explicitly check for 0.
78    it = history_.find(0);
79    if (it == history_.end())
80      it = history_.upper_bound(0);
81  }
82  assert(it != history_.end());
83  oldest_sequence_number_ = it->first;
84}
85
86bool SendTimeHistory::GetInfo(PacketInfo* packet, bool remove) {
87  auto it = history_.find(packet->sequence_number);
88  if (it == history_.end())
89    return false;
90  int64_t receive_time = packet->arrival_time_ms;
91  *packet = it->second;
92  packet->arrival_time_ms = receive_time;
93  if (remove) {
94    history_.erase(it);
95    if (packet->sequence_number == oldest_sequence_number_)
96      UpdateOldestSequenceNumber();
97  }
98  return true;
99}
100
101}  // namespace webrtc
102