Change QpackHeaderTable::observer_ type and swap RegisterObserver() argument order.
No functional change, prework for fixing a crasher. The motivation for moving
away from std::priority is that it does not allow deletion of random elements.
gfe-relnote: n/a, change to QUIC v99-only code. Protected by existing disabled gfe2_reloadable_flag_quic_enable_version_99.
PiperOrigin-RevId: 272559408
Change-Id: I3f18909201e218627eee3638249aea007b317cd1
diff --git a/quic/core/qpack/qpack_header_table.cc b/quic/core/qpack/qpack_header_table.cc
index bb28f72..30f15a5 100644
--- a/quic/core/qpack/qpack_header_table.cc
+++ b/quic/core/qpack/qpack_header_table.cc
@@ -131,10 +131,13 @@
}
// Notify and deregister observers whose threshold is met, if any.
- while (!observers_.empty() &&
- observers_.top().required_insert_count <= inserted_entry_count()) {
- Observer* observer = observers_.top().observer;
- observers_.pop();
+ while (!observers_.empty()) {
+ auto it = observers_.begin();
+ if (it->first > inserted_entry_count()) {
+ break;
+ }
+ Observer* observer = it->second;
+ observers_.erase(it);
observer->OnInsertCountReachedThreshold();
}
@@ -188,10 +191,10 @@
max_entries_ = maximum_dynamic_table_capacity / 32;
}
-void QpackHeaderTable::RegisterObserver(Observer* observer,
- uint64_t required_insert_count) {
+void QpackHeaderTable::RegisterObserver(uint64_t required_insert_count,
+ Observer* observer) {
DCHECK_GT(required_insert_count, 0u);
- observers_.push({observer, required_insert_count});
+ observers_.insert({required_insert_count, observer});
}
uint64_t QpackHeaderTable::draining_index(float draining_fraction) const {
@@ -219,11 +222,6 @@
return it->InsertionIndex();
}
-bool QpackHeaderTable::ObserverWithThreshold::operator>(
- const ObserverWithThreshold& other) const {
- return required_insert_count > other.required_insert_count;
-}
-
void QpackHeaderTable::EvictDownToCurrentCapacity() {
while (dynamic_table_size_ > dynamic_table_capacity_) {
DCHECK(!dynamic_entries_.empty());
diff --git a/quic/core/qpack/qpack_header_table.h b/quic/core/qpack/qpack_header_table.h
index f251894..919a4eb 100644
--- a/quic/core/qpack/qpack_header_table.h
+++ b/quic/core/qpack/qpack_header_table.h
@@ -96,8 +96,8 @@
// Register an observer to be notified when inserted_entry_count() reaches
// |required_insert_count|. After the notification, |observer| automatically
- // gets unregistered.
- void RegisterObserver(Observer* observer, uint64_t required_insert_count);
+ // gets unregistered. Each observer must only be registered at most once.
+ void RegisterObserver(uint64_t required_insert_count, Observer* observer);
// Used on request streams to encode and decode Required Insert Count.
uint64_t max_entries() const { return max_entries_; }
@@ -179,21 +179,8 @@
// The number of entries dropped from the dynamic table.
uint64_t dropped_entry_count_;
- // Data structure to hold an Observer and its threshold.
- struct ObserverWithThreshold {
- Observer* observer;
- uint64_t required_insert_count;
- bool operator>(const ObserverWithThreshold& other) const;
- };
-
- // Use std::greater so that entry with smallest |required_insert_count|
- // is on top.
- using ObserverHeap = std::priority_queue<ObserverWithThreshold,
- std::vector<ObserverWithThreshold>,
- std::greater<ObserverWithThreshold>>;
-
- // Observers waiting to be notified.
- ObserverHeap observers_;
+ // Observers waiting to be notified, sorted by required insert count.
+ std::multimap<uint64_t, Observer*> observers_;
};
} // namespace quic
diff --git a/quic/core/qpack/qpack_header_table_test.cc b/quic/core/qpack/qpack_header_table_test.cc
index 00f36e5..5a97c20 100644
--- a/quic/core/qpack/qpack_header_table_test.cc
+++ b/quic/core/qpack/qpack_header_table_test.cc
@@ -89,9 +89,9 @@
return table_.SetDynamicTableCapacity(capacity);
}
- void RegisterObserver(QpackHeaderTable::Observer* observer,
- uint64_t required_insert_count) {
- table_.RegisterObserver(observer, required_insert_count);
+ void RegisterObserver(uint64_t required_insert_count,
+ QpackHeaderTable::Observer* observer) {
+ table_.RegisterObserver(required_insert_count, observer);
}
uint64_t max_entries() const { return table_.max_entries(); }
@@ -418,7 +418,7 @@
TEST_F(QpackHeaderTableTest, Observer) {
StrictMock<MockObserver> observer1;
- RegisterObserver(&observer1, 1);
+ RegisterObserver(1, &observer1);
EXPECT_CALL(observer1, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
EXPECT_EQ(1u, inserted_entry_count());
@@ -427,8 +427,8 @@
// Registration order does not matter.
StrictMock<MockObserver> observer2;
StrictMock<MockObserver> observer3;
- RegisterObserver(&observer3, 3);
- RegisterObserver(&observer2, 2);
+ RegisterObserver(3, &observer3);
+ RegisterObserver(2, &observer2);
EXPECT_CALL(observer2, OnInsertCountReachedThreshold);
InsertEntry("foo", "bar");
@@ -444,8 +444,8 @@
// notified.
StrictMock<MockObserver> observer4;
StrictMock<MockObserver> observer5;
- RegisterObserver(&observer4, 4);
- RegisterObserver(&observer5, 4);
+ RegisterObserver(4, &observer4);
+ RegisterObserver(4, &observer5);
EXPECT_CALL(observer4, OnInsertCountReachedThreshold);
EXPECT_CALL(observer5, OnInsertCountReachedThreshold);
diff --git a/quic/core/qpack/qpack_progressive_decoder.cc b/quic/core/qpack/qpack_progressive_decoder.cc
index 5ce0612..5632286 100644
--- a/quic/core/qpack/qpack_progressive_decoder.cc
+++ b/quic/core/qpack/qpack_progressive_decoder.cc
@@ -295,7 +295,7 @@
OnError("Limit on number of blocked streams exceeded.");
return false;
}
- header_table_->RegisterObserver(this, required_insert_count_);
+ header_table_->RegisterObserver(required_insert_count_, this);
}
return true;