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