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 |