1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 // Simple max sized map. Automatically deletes the oldest element when the 6 // max limit is reached. 7 // Note: the ConstIterator will NOT be valid after an Insert or RemoveAll. 8 #ifndef NET_QUIC_CONGESTION_CONTROL_QUIC_MAX_SIZED_MAP_H_ 9 #define NET_QUIC_CONGESTION_CONTROL_QUIC_MAX_SIZED_MAP_H_ 10 11 #include <stdlib.h> 12 13 #include <list> 14 #include <map> 15 16 #include "base/basictypes.h" 17 18 namespace net { 19 20 template <class Key, class Value> 21 class QuicMaxSizedMap { 22 public: 23 typedef typename std::multimap<Key, Value>::const_iterator ConstIterator; 24 25 explicit QuicMaxSizedMap(size_t max_numer_of_items) 26 : max_numer_of_items_(max_numer_of_items) { 27 } 28 29 size_t MaxSize() const { 30 return max_numer_of_items_; 31 } 32 33 size_t Size() const { 34 return table_.size(); 35 } 36 37 void Insert(const Key& k, const Value& value) { 38 if (Size() == MaxSize()) { 39 ListIterator list_it = insert_order_.begin(); 40 table_.erase(*list_it); 41 insert_order_.pop_front(); 42 } 43 TableIterator it = table_.insert(std::pair<Key, Value>(k, value)); 44 insert_order_.push_back(it); 45 } 46 47 void RemoveAll() { 48 table_.clear(); 49 insert_order_.clear(); 50 } 51 52 // STL style const_iterator support. 53 ConstIterator Find(const Key& k) const { 54 return table_.find(k); 55 } 56 57 ConstIterator Begin() const { 58 return ConstIterator(table_.begin()); 59 } 60 61 ConstIterator End() const { 62 return ConstIterator(table_.end()); 63 } 64 65 private: 66 typedef typename std::multimap<Key, Value>::iterator TableIterator; 67 typedef typename std::list<TableIterator>::iterator ListIterator; 68 69 const size_t max_numer_of_items_; 70 std::multimap<Key, Value> table_; 71 std::list<TableIterator> insert_order_; 72 73 DISALLOW_COPY_AND_ASSIGN(QuicMaxSizedMap); 74 }; 75 76 } // namespace net 77 #endif // NET_QUIC_CONGESTION_CONTROL_QUIC_MAX_SIZED_MAP_H_ 78
