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