chromium/third_party/angle/src/common/base/anglebase/containers/mru_cache.h

// Copyright (c) 2011 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.

// This file contains a template for a Most Recently Used cache that allows
// constant-time access to items using a key, but easy identification of the
// least-recently-used items for removal.  Each key can only be associated with
// one payload item at a time.
//
// The key object will be stored twice, so it should support efficient copying.
//
// NOTE: While all operations are O(1), this code is written for
// legibility rather than optimality. If future profiling identifies this as
// a bottleneck, there is room for smaller values of 1 in the O(1). :]

#ifndef ANGLEBASE_CONTAINERS_MRU_CACHE_H_
#define ANGLEBASE_CONTAINERS_MRU_CACHE_H_

#include <stddef.h>

#include <algorithm>
#include <functional>
#include <list>
#include <map>
#include <unordered_map>
#include <utility>

#include "anglebase/logging.h"
#include "anglebase/macros.h"

namespace angle
{

namespace base
{

// MRUCacheBase ----------------------------------------------------------------

// This template is used to standardize map type containers that can be used
// by MRUCacheBase. This level of indirection is necessary because of the way
// that template template params and default template params interact.
template <class KeyType, class ValueType, class CompareType>
struct MRUCacheStandardMap
{ … };

// Base class for the MRU cache specializations defined below.
template <class KeyType,
          class PayloadType,
          class HashOrCompareType,
          template <typename, typename, typename> class MapType = MRUCacheStandardMap>
class MRUCacheBase
{ … };

// MRUCache --------------------------------------------------------------------

// A container that does not do anything to free its data. Use this when storing
// value types (as opposed to pointers) in the list.
template <class KeyType, class PayloadType, class CompareType = std::less<KeyType>>
class MRUCache : public MRUCacheBase<KeyType, PayloadType, CompareType>
{
  private:
    using ParentType = MRUCacheBase<KeyType, PayloadType, CompareType>;

  public:
    // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
    explicit MRUCache(typename ParentType::size_type max_size) : … { … }
    virtual ~MRUCache() { … }

  private:
    DISALLOW_COPY_AND_ASSIGN(MRUCache);
};

// HashingMRUCache ------------------------------------------------------------

template <class KeyType, class ValueType, class HashType>
struct MRUCacheHashMap
{ … };

// This class is similar to MRUCache, except that it uses std::unordered_map as
// the map type instead of std::map. Note that your KeyType must be hashable to
// use this cache or you need to provide a hashing class.
template <class KeyType, class PayloadType, class HashType = std::hash<KeyType>>
class HashingMRUCache : public MRUCacheBase<KeyType, PayloadType, HashType, MRUCacheHashMap>
{
  private:
    using ParentType = MRUCacheBase<KeyType, PayloadType, HashType, MRUCacheHashMap>;

  public:
    // See MRUCacheBase, noting the possibility of using NO_AUTO_EVICT.
    explicit HashingMRUCache(typename ParentType::size_type max_size) : … { … }
    virtual ~HashingMRUCache() override { … }

  private:
    DISALLOW_COPY_AND_ASSIGN(HashingMRUCache);
};

}  // namespace base

}  // namespace angle

#endif  // ANGLEBASE_CONTAINERS_MRU_CACHE_H_