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