blob: aca3761e2eb1b2755dacd09d039ea07269ba43a4 [file] [log] [blame]
//===--- Cache.h - Caching mechanism interface ------------------*- C++ -*-===//
// This source file is part of the open source project
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
// See for license information
// See for the list of Swift project authors
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/IntrusiveRefCntPtr.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/Optional.h"
namespace swift {
namespace sys {
template <typename T>
struct CacheKeyHashInfo {
static uintptr_t getHashValue(const T &Val) {
return llvm::DenseMapInfo<T>::getHashValue(Val);
static bool isEqual(void *LHS, void *RHS) {
return llvm::DenseMapInfo<T>::isEqual(*static_cast<T*>(LHS),
template <typename T>
struct CacheKeyInfo : public CacheKeyHashInfo<T> {
static void *enterCache(const T &Val) { return new T(Val); }
static void exitCache(void *Ptr) { delete static_cast<T*>(Ptr); }
static const void *getLookupKey(const T *Val) { return Val; }
static const T &getFromCache(void *Ptr) { return *static_cast<T*>(Ptr); }
template <typename T>
struct CacheValueCostInfo {
static size_t getCost(const T &Val) { return sizeof(Val); }
template <typename T>
struct CacheValueInfo : public CacheValueCostInfo<T> {
static void *enterCache(const T &Val) { return new T(Val); }
static void retain(void *Ptr) {}
static void release(void *Ptr) { delete static_cast<T *>(Ptr); }
static const T &getFromCache(void *Ptr) { return *static_cast<T *>(Ptr); }
/// The underlying implementation of the caching mechanism.
/// It should be inherently thread-safe.
class CacheImpl {
using ImplTy = void *;
struct CallBacks {
void *UserData;
uintptr_t (*keyHashCB)(void *Key, void *UserData);
bool (*keyIsEqualCB)(void *Key1, void *Key2, void *UserData);
void (*keyDestroyCB)(void *Key, void *UserData);
void (*valueRetainCB)(void *Value, void *UserData);
void (*valueReleaseCB)(void *Value, void *UserData);
CacheImpl() = default;
ImplTy Impl = nullptr;
static ImplTy create(llvm::StringRef Name, const CallBacks &CBs);
/// Sets value for key.
/// \param Key Key to add. Must not be nullptr.
/// \param Value Value to add. If value is nullptr, key is associated with the
/// value nullptr.
/// \param Cost Cost of maintaining value in cache.
/// Sets value for key. Value is retained until released using
/// \c releaseValue().
/// Replaces previous key and value if present. Invokes the key destroy
/// callback immediately for the previous key. Invokes the value destroy
/// callback once the previous value's retain count is zero.
/// Cost indicates the relative cost of maintaining value in the cache
/// (e.g., size of value in bytes) and may be used by the cache under
/// memory pressure to select which cache values to evict. Zero is a
/// valid cost.
void setAndRetain(void *Key, void *Value, size_t Cost);
/// Fetches value for key.
/// \param Key Key used to lookup value. Must not be nullptr.
/// \param Value_out Value is stored here if found. Must not be nullptr.
/// \returns True if the key was found, false otherwise.
/// Fetches value for key, retains value, and stores value in value_out.
/// Caller should release value using \c releaseValue().
bool getAndRetain(const void *Key, void **Value_out);
/// Releases a previously retained cache value.
/// \param Value Value to release. Must not be nullptr.
/// Releases a previously retained cache value. When the reference count
/// reaches zero the cache may destroy the value.
void releaseValue(void *Value);
/// Removes a key and its value.
/// \param Key Key to remove. Must not be nullptr.
/// \returns True if the key was found, false otherwise.
/// Removes a key and its value from the cache such that \c getAndRetain()
/// will return false. Invokes the key destroy callback immediately.
/// Invokes the value destroy callback once value's retain count is zero.
bool remove(const void *Key);
/// Invokes \c remove on all keys.
void removeAll();
/// Destroys cache.
void destroy();
/// Caching mechanism, that is thread-safe and can evict its entries when there
/// is memory pressure.
/// This works like a dictionary, you use a key to store and retrieve a value.
/// The value is copied (during storing or retrieval), but an IntrusiveRefCntPtr
/// can be used directly as a value.
/// It is important to provide a proper 'cost' function for the value (via
/// \c CacheValueCostInfo trait); e.g. the cost for an ASTContext would be the
/// memory usage of the data structures it owns.
template <typename KeyT, typename ValueT,
typename KeyInfoT = CacheKeyInfo<KeyT>,
typename ValueInfoT = CacheValueInfo<ValueT> >
class Cache : CacheImpl {
explicit Cache(llvm::StringRef Name) {
CallBacks CBs = {
Impl = create(Name, CBs);
~Cache() {
void set(const KeyT &Key, const ValueT &Value) {
void *CacheKeyPtr = KeyInfoT::enterCache(Key);
void *CacheValuePtr = ValueInfoT::enterCache(Value);
setAndRetain(CacheKeyPtr, CacheValuePtr, ValueInfoT::getCost(Value));
llvm::Optional<ValueT> get(const KeyT &Key) {
const void *CacheKeyPtr = KeyInfoT::getLookupKey(&Key);
void *CacheValuePtr;
bool Found = getAndRetain(CacheKeyPtr, &CacheValuePtr);
if (!Found)
return llvm::None;
ValueT Val(ValueInfoT::getFromCache(CacheValuePtr));
return std::move(Val);
/// \returns True if the key was found, false otherwise.
bool remove(const KeyT &Key) {
const void *CacheKeyPtr = KeyInfoT::getLookupKey(&Key);
return CacheImpl::remove(CacheKeyPtr);
void clear() {
static uintptr_t keyHash(void *Key, void *UserData) {
return KeyInfoT::getHashValue(*static_cast<KeyT*>(Key));
static bool keyIsEqual(void *Key1, void *Key2, void *UserData) {
return KeyInfoT::isEqual(Key1, Key2);
static void keyDestroy(void *Key, void *UserData) {
static void valueRetain(void *Value, void *UserData) {
static void valueRelease(void *Value, void *UserData) {
template <typename T>
struct CacheValueInfo<llvm::IntrusiveRefCntPtr<T>>{
static void *enterCache(const llvm::IntrusiveRefCntPtr<T> &Val) {
return const_cast<T *>(Val.get());
static void retain(void *Ptr) {
static void release(void *Ptr) {
static llvm::IntrusiveRefCntPtr<T> getFromCache(void *Ptr) {
return static_cast<T*>(Ptr);
static size_t getCost(const llvm::IntrusiveRefCntPtr<T> &Val) {
return CacheValueCostInfo<T>::getCost(*Val);
} // end namespace sys
} // end namespace swift